Programming Language Reminiscence

 

 

A wordstar-like text editor for Electronics BK-0010 in 1754 bytes

Electronics BK-0010 was a `home' computer manufactured in the USSR from 1985 through 1993. It was a 16-bit microcomputer (an LSI-11 clone) with the PDP-11 instruction set; it had 3MHz clock and 32KB of RAM, half of which was dedicated to video memory. Programs had only 16KB (that is, 16384 bytes) of memory for code and data. The main unit with the integrated keyboard had to be connected to a tape recorder and a TV set, on which it could display 25 lines of 64-character--wide text.

The following article presents a text editor for Electronics BK-0010, written around 1986. The description may sound hopelessly naive. Still, the features of our editor were quite similar to those of the state-of-the art editors K52 and Wordstar. One should keep in mind that these features were implemented in only 1754 bytes of code. With 512 initial bytes used by the firmware and data and 966 bytes of the custom nanoOS, there were 13 KBytes left for the document text. There was enough room for a paper.

The article was originally published in Russian in the Magazine ``Микропроцессорные Средства и Системы'' (Microprocessor tools and systems), N3, 1989, p. 56. The following is the close translation.

Universal text editor for the "Electronics BK-0010" personal computer

An important application for personal computers is using them as typewriters, for entering, storing and editing of various documents. For doing these tasks on the ``Electronics BK-0010'', in Kazan State University (named after V.I.Ulyanov-Lenin) has been developed a universal text editor. It lets us enter and edit text in full screen: change any character of the displayed page; shift characters on a line to the right to make room for new ones; delete characters; enter, delete and duplicate lines. There were many ways to quickly move the text cursor. One can scroll the text, and display the page with the given line number. If the cursor is at the top of the screen, pressing the UP key scrolls the text down, showing the previous text line if any. Likewise, the text scrolls up when pressing the DOWN key with the cursor on the bottom two screen lines. Any group of text lines (including one line and the whole text) can be marked as a block, and copied to a different place or deleted. It takes only two key presses to mark the current line as the beginning or the end line of the block. The cursor can be quickly positioned on the first or the last line of the marked block. To format text, one can split a text line in two at the cursor, and merge two lines. If the merged line turns out too wide, it is split in such a way that the first line is filled with whole words (not characters!).

The text in memory is a sequence of lines of varying length (up to the maximum of 63 characters); the trailing spaces are not stored. However, the user does not suspect such a tight storage: he may position the cursor at any point of the screen and insert any characters at any place. The user hence has the full impression of editing the fixed-width--line text -- just like a regular printed text. This feature distinguishes our editor from other well-known screen editors (such as K52). The what-you-see-is-what-you-get mode of our editor significantly improves the convenience of using it.

Besides the editing functions, the program lets us store the document on the magnetic tape, load the previously saved text and append it to the one in memory. The appended text can then be moved using the block copy operation. A universal driver supports printing on any printer with the IRPR [Centronics-like] interface. Printing has been tested on TPU, UVVPC-30-004, TC 7180, D100 (of the DVK System). On last two units one can print both in Cyrillic and Latin alphabets in lower and upper cases.

The editor program is written in position-independent code and takes just a bit over 3 kilobytes of main memory. The rest of the RAM of BK-0010 (13 KByte) can be used for the text.

The BK editor is somewhat like Wordstar (which I have never used, and did not know at the time). There was no on-screen menu though: the whole screen was used for text. The BK editor was also reminiscent of the K52 visual editor that DEC distributed with its OS RT-11 -- which I was familiar with and disliked. The most visible distinction of the BK editor was its WYSIWYG mode: if the newline character cannot be seen, it should not be felt. Therefore, the cursor moves vertically in a straight line, without any odd jumps. The editing feels like the `picture mode' of Emacs. Although the screen lines appear padded with spaces to fixed width, the trailing spaces were not stored. Such WYSIWYG mode was a feature of several editors developed in the USSR for bigger computers but it is hardly known in the West.

The first version of the program was entered into a BK in hexadecimal codes using a custom hexadecimal editor (quite like the HEXL mode in modern Emacs). Referenced below is the second version, which added minor improvements and was re-coded in PDP Macro-11. It was then transmitted to a BK via a custom network.

The code uses tables to quickly dispatch to keystroke handlers. The editor also relies on the putback keystroke buffer: quite a few keystrokes are implemented as `macros'. The previously written nanoOS provided common services via `traps'. For example, trap 14 displays and formats a message, trap 11 controls the magnetic tape, and trap 3 printer. Trap 16 saves registers and trap 17 restores them and returns to the caller of the function.

The BK Editor (sometimes called TRED) was used productively for several years and was widely distributed. It was cloned, so to speak, several times.

Version
The current version is 2.0, around 1987
References
user-guide.txt [17K]
The complete User's manual written by the users, using the editor itself (in Russian)

edwa.mac [2K]
Editor Source Code (PDP-11 Assembly): Global data definitions

edinit.mac [6K]
Global initialization and the handling of the main menu

edroot.mac [5K]
Text editing root module, with the main loop dispatching to keystroke handlers

edsymb.mac [8K]
Handle simple keystrokes (page/line up, etc)

edgold.mac [11K]
Handle prefix commands with a table-driven 1-symbol-stack automaton

edut1.mac [9K]
Utilities: displaying a block of text, locating a line by its number, status reporting, buffer operations, etc.

lined.mac [8K]
Line editor

edwa.map [2K]
Memory map of the complete executable

BK 0010 in the Old Computer Museum
<http://oldcomputermuseum.com/elektronika_bk0010.html>

 

Language for writing text adventure, er, online courses: glimpse into the computer-assisted education of the 1970s and 1980s

Online courses have become familiar. A typical lesson shows a movie clip or several web pages, followed by the `test': a screen with several multiple-choice questions. The correct answers are then tallied and displayed. Computer-assisted education, however, pre-dates internet by several decades. Back then, it was quickly realized that the courses like the one just described are very boring.

An engaging and productive course should be more interactive. Presentation and questions should be interspersed; an answer should be evaluated on the spot. If the answer is not correct, the student should get another chance or a hint. If the correct answer is still not forthcoming, there should follow alternative lessons to explain the subject more slowly. Questions should be variable and varied, preferably with non-deterministic parts. It goes without saying that the answer should be given in a free form, as an arbitrary number or a string -- rather than as a selection from a list. All in all, an engaging course should look quite like an adventure game.

It was also realized early on that writing the script of a good course, like that of a good game, is a skill, different from programming. It is unreasonable to make course authors write in Fortran or Assembly (as computers were programmed those days). They needed good tools -- a high-level language for writing course scripts. (Game industry has realized that, too). One of such early course script languages was TUTOR, developed at the University of Illinois in late 1960s.

In Soviet Union, there was a dialect/reimplementation of TUTOR for mainframes. I have encountered it when studying and then working at the Kazan State University. Taking a computer course on a mainframe was inconvenient, to say the least: mainframes were not easily accessible -- and, in the Soviet Union, they often broke down.

Personal computers, once became available, made for a better, or at least much cheaper, platform for computer tutoring. That was the motivation to write an interpreter for a TUTOR dialect on the personal computer BK-0010. The hardware was quite less capable than the mainframe. Still, my implementation had a few advantages over its mainframe counterpart.

In the original TUTOR and its dialects, presentations were created by positioning the cursor on the screen and then writing text. My implementation supported formatted output, with text and drawing. The text template to display could contain slots to be filled with the current values of numeric or string expressions. Text templates may also include screen control codes, for color, inverse video and other screen effects. There was a special operator for line drawing.

The script language was a programming language, with numeric and string computations, and string conversion, editing and matching. The latter was necessary to evaluate student responses, which were assumed to be free-form. The language offered 26 integer and 8 string variables. It also supported branching, looping and subroutines. As a dialect of TUTOR, it had dedicated operators for accepting an answer and branching on match or mismatch with respect to the given template; advancing to the next lesson, backtracking, or switching to another lesson plan. Lessons may be grouped into sets. Course scripts may be edited with the built-in full-screen editor.

The interpreter was written in PDP-11 assembly (MACRO-11). The interpreter took 3Kbytes of memory, the editor 1.5KBytes and the simple OS, 2KBytes. The rest 9.5KBytes of the main memory of BK-0010 could then be used for the course script and materials. When a course is fully written, the editor can be removed and its memory used for the course.

I realize now that the script language was good enough to write text adventure games (actually, semi-textual: it supported drawing). Alas, neither I nor any of my friends knew of `text adventure' at the time.

I have written a couple of sample courses for illustration, and planned to port a few of the existing TUTOR courses developed at the university. It seems only the interpreter code has survived, shown below.

Just the other day (in September 2018) I took an online course on personal information handling, mandated by the university. The course consisted of a video followed by a dozen of multiple-choice questions. It is sad to realize that in 1988 -- on the computer with the clock speed of mere 3MHz and the total memory million times smaller than that on my present computer -- I could have scripted and taken a much more engaging course.

Version
The current version is June 1988
References
R.A. Avner, Paul Tenczar: The TUTOR Manual. University of Illinois. CERL Report X-4, January 1969
<https://files.eric.ed.gov/fulltext/ED050583.pdf>

paper.txt [10K]
Interpreter for training courses on the "Electronics BK-0010" personal computer (in Russian)
This paper describing the system was published in the proceedings of the XIII Joint Soviet-French Seminar "Designing the computer assisted systems for the higher school on the base of personal computers", Kazan, Oct. 10-14, 1988, p. 122-125

A wordstar-like text editor for Electronics BK-0010 in 1754 bytes
BK-0010 computer and the editor used for the course scripts

The source code of the interpreter (PDP-11 Macro-assembly), as is

 

R-Technology

R-technology is the method to design and graphically represent programs that was developed in Kiev's Institute of Cybernetics headed by V.M. Glushkov. It evolved from the design of the avionics software for Soviet Union's ballistic missiles and later space rockets in late 1950s and early 1960s. (Interestingly, a rather similar technique, Harel's Statecharts, was invented when David Harel was a consultant on avionics software engineering for Israeli Aircraft Industries, about two decades later.) R-technology was heavily used and promoted by the Glushkov institute: it is said that more than 600 papers were published in this area (mostly in Russian); three all-Union and one international conference were held on this topic. It has even been standardized as R-charts: ISO/IEC 8631.

I came to know the R-technology in the early 1980s from several books and articles published by the Institute of Cybernetics researchers. There was a distinct impression that anything that came from the Glushkov institute was one way or another about the R-technology. I remember looking at the diagrams (R-charts) for a complete Pascal compiler, drawn on big sheets of paper.

The R-technology is based on diagrams that depict the control-flow graph of a program. Nodes are program states and directed edges (arcs) are state transitions. Arcs are annotated with text or graphics, both above and below the arc; above is the condition/guard; below is the action to perform when the arc is followed. Arcs are laid out horizontally. When a program is in a particular state, we examine the outgoing arcs top to bottom looking for an arc whose condition is true. The action of the found arc is executed and the arc's target becomes the next program state. R-technology is closely related to flowcharts; however, what is a node in a flowchart is an annotated arc in a R-chart (and, similarly, in Harel's Statechart). We shall call an R-technology diagram an R-chart, and the abstract machine/automaton it depicts -- an R-machine, or R-tran (RTRAN).

The R-machine description above should remind one of state machines. The close similarity is no accident: Glushkov was the famous researcher in automata theory, having proposed the first algorithm to transform a regular expression into a non-deterministic finite automaton, and written the book ``Synthesis of Digital Automata'' (which brought him Lenin Prize and the membership in the Soviet Academy of Sciences). Unlike finite state automata, the condition on a R-machine state transition is not a mere test of the current input symbol; it can be arbitrarily complex. R-machine actions are also arbitrarily complex. We will see later an example: an R-machine with nominally two states. It also has mutable state, updated by its actions. Therefore, the effective number of states in unbounded. To me, an R-machine always looked like a Turing machine, but with the practical `control', whose actions go beyond the mere reading, writing and moving the tape.

R-technology diagrams are often drawn as graphs, and hence the technology is called visual programming. Nothing prevents however a (stylized) plain-text representation of the diagrams. I remember seeing in some book the form for writing R-programs. It looked somewhat like the form for entering Fortran or Cobol programs for punching. The form had four columns, for the state label, condition, action and the next label. R-programs were supposed to be entered as:

    statelabelA   condition1   action1     statelabelA
                  true         action2     statelabelB
    statelabelB   condition3   action3     statelabelA
    ...
To me, this stylized plain-text notation had the most appeal: as a way to organize thoughts about the program state and to force to consider all transitions from a given state.

Let's take an example, from a train scheduling program I wrote back in 1987 or 1988, in Algol-68. (Candidate) train schedules were represented as a tree, whose various traversals and transformations were programmed in the R-technology. The simplest was the tree print-out: a depth-first tree traversal printing out data from its nodes. The traversal was done iteratively, in constant space, without using the stack. The train scheduling program was run on ES-1033 (the Soviet clone of an IBM S\360 mainframe), which had only 1MB of memory. One had to be careful with deep recursion.

To make the tree-printing R-program easier, for the modern reader, to understand, I re-wrote it in C, as follows. Like in the original Algol-68 code, the tree is a linked data structure, whose nodes point to the right sibling, the parent and the first-born--child. One may also say that the tree is the cross-product of a single-linked list (in the sibling direction) with the double-linked list (in the parent-child direction). The payload of a node is just an integer, in our example. (The original scheduling program put more data in tree nodes.)

    typedef struct _node node;    /* forward declaration */
    
    struct _node {
      node * up;                  /* parent pointer */
      node * down;                /* first-born child */
      node * right;               /* brother */
      int data;                   /* payload: just an int in our example */
    };
    
    const node * const nil = (node *)NULL;

Below is the tree printing function, written as an R-machine. It prints the payload of nodes as it traverses the tree depth-first. The machine has only two states (not counting the finish label), but also a mutable state: the pointer to the current node n. The actions of the machine update n, to point to a neighboring node. Thus the effective number of states is unbounded.

    void dump(const node * const tree) {
      const node * n = tree;        /* current node */
      enum {finish,down,right_up} state = down;
    
      /* The R-machine execution, with two states */
      while(state != finish)
        switch(state) {
        case down:
          /*   condition            action                              next-state */
          if(n->down == nil) {printf("data %d----- leaf\n",n->data);
                                                                state = right_up;}
          else               {printf("data %d\n",n->data); n = n->down;
                                                                state = down;}
          break;
    
        case right_up:
          if      (n->right != nil) {n = n->right; state=down;}
          else if (n->up == nil)    {n = nil;      state=finish;}
          else                      {n = n->up;    state=right_up;}
          break;
    
        case finish: break;
        }
    }

Algol-68 had the notation for anonymous functions and sequences. Therefore, the machine itself was an ordinary procedure and an R-program -- an inline sequence of tuples, recalling the 4-columnar format I have seen in a book. The C code can be made to look similarly.

The C code also has a more interesting R-program: building a full binary tree iteratively, without using stack -- in constant memory, if we do not count the allocated tree nodes. The C code, including the more complicated tree builder, worked on the first try. I should also say that the tree builder (written for the sake of running the example and was not present in the original Algol-68 code) did take some thought: how many R-states I need, what is the point of each state, how much mutable state is enough. Writing this C code now, with the 50-year old technology, confirmed the R-technology lesson: think harder now, and debug none later.

Version
The current version is 1985-1987
References
William K. McHenry. R-technology: A soviet visual programming environment
Journal of Visual Languages & Computing 1(2):199-212. June 1990. DOI: 10.1016/S1045-926X(05)80016-3

Igor V. Velbitskiy. Graphical Programming and Program Correctness Proof
<http://glushkov.org/wp-content/131120CSITeng.pdf>

Ushakov I., Velbitskiy I. (1993) Visual programming in R-technology: Concepts, systems and perspectives
In: Bass L.J., Gornostaev J., Unger C. (eds) Human-Computer Interaction. EWHCI 1993. Lecture Notes in Computer Science, vol 753. Springer, Berlin, Heidelberg. doi:10.1007/3-540-57433-6_48

V.M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 1961, v16:5, 1-53. (English version) doi:10.1070/RM1961v016n05ABEH004112

bldg.bld [8K]
The R-machine in Algol-68 (one of several implementations)

dumptree.a68 [2K]
The constant-space tree traversal, as an R-program

rtran-traverse.c [4K]
The C version of dumptree.a68, omitting irrelevant details of train scheduling. The C code includes another R-program: building a full binary tree iteratively, in constant working space (not counting the allocated nodes).

RTRAN parsing and finding direct products in Algol-68 Another implementation of the R-machine in Algol-68

tpvoc.asm [12K]
An R-machine as an Assembler Macro (IBM System\360 Assembly) and a parser implemented in it

Programming in a Finite Automaton style
Advanced Finite Automaton as a simple HTML formatter
More examples of C programming in the R-tran style

 

Automating adiabatic calorimeter

Automating an adiabatic calorimeter made by Setaram was my second calorimeter automation project.

Calorimeter is an instrument to measure the amount of heat emitted or absorbed during a chemical or physical process. The Setaram calorimeter was designed for studying the process of dissolving a substance (so-called solute) in a large amount of solvent. The calorimeter has two identical reaction chambers: vessels for solvent, into which were submerged a temperature sensor, a resistor and and small enclosure for solute encased in glass beads. The chambers are well insulated, which is why the calorimeter is called adiabatic. After setting-up and waiting for the chambers to come to thermal equilibrium, the operator crashes the glass beads releasing the solute, which starts dissolving. The insulation keeps the heat in the reaction chamber, which hence changes its temperature, measured by the sensor. Multiplying the total change in temperature during the reaction by the calibration coefficient (the thermal capacity) gives the amount of heat -- the caloric effect of the reaction. The calibration coefficient is obtained by calibrating before or after the main experiment: releasing a known amount of heat (by briefly passing a certain amount of current through the submerged resistor) and measuring the temperature change just like in the main experiment.

The temperature sensor is connected to a potentiometric strip chart recorder, which draws the temperature vs. time graph on the advancing long strip of paper (chart). When the system is in the equilibrium, the graph is the flat straight line: so-called baseline. When a reaction is going on, the line curves. The area under the curve is the total change in temperature. Measuring this area by hand -- manual integration -- and computing necessary corrections was the most tedious, also time consuming and error-prone, part of the experiment. I was called for help.

The developed control program automates the tedium of conducting the experiment. Only crashing the glass beads and calibration had to be done manually. Concretely, the control program continuously acquires temperature sensor readings and filters them. In the baseline mode, it fits the acquired points to the straight line to obtain the noise level and the baseline parameters. When the experiment/calibration is in progress, the control program continuously integrates the temperature curve, determines the end of the process, computes the total effect and various corrections. The control program ran on a Electronics BK-0010 computer with a color TV monitor, which continuously displays the current status and the baseline parameters. One can see at a glance what is going on and if the equilibrium is reached. The monitor also displays a screen form, whose fields tell the possible actions (such as: start monitoring an experiment, switch to another screen form to show accumulated results) and various parameters, some of which could be changed. The actions are activated by a single keyboard key press, with a visual feedback. The control program occupied 4 Kbytes, of 16 Kbytes of memory available on BK-0010.

The automation was done on the cheap, as necessary in those times, with the minimum of extra hardware. I only needed an analog-to-digital converter (ADC) and a small oscillator circuit, built by a friend of mine. The circuit sends the timer interrupt to the control program every 3 seconds. The ADC is connected to the temperature sensor and the computer, and can be queried to give the current temperature reading, in a peculiar binary-coded decimal format.

The control program runs `on the bare metal': it is the operating system, into which BK-0010 boots. As my other control programs, it is interrupt-driven, with two foreground and a background tasks. The high-priority foreground task is activated by the timer interrupt and runs to completion, thus ensuring accurate sampling frequency and no data loss. The task acquires the temperature reading, filters by the 3-point median filter, and processes according to the current mode. In the baseline mode, it fits the current point, along with some number of previous points, to the baseline. In the reaction (effect) mode, the processing is guided by a 5-state automaton (see the reference below). The lower-priority foreground task is activated by the keyboard interrupt and handles operator commands. Refreshing the display is done by a background task. Computing the caloric effect requires more computation and is also done by a background task. Such tasks are interruptible and run when all urgent processing is completed.

BK-0010, however, has only one interrupt level: interrupt priorities had to be emulated. The high-priority foreground task is run as the timer interrupt handler, with interrupts disabled, to avoid data loss. The processing is typically fast, so that interrupts remain disabled only for a short time. For any longer processing, a background job is submitted. The keyboard interrupt handler only sets a flag that the operator input is pending, and immediately exits. Reading the operator request and acting on it is done in background. The background mode scheduler is activated on return from interrupt. It first checks if keyboard input is pending, and, if so, runs the operator command task. Otherwise, other scheduled background tasks are run.

The control program is written in PDP-11 macro-assembly: Macro-11. It was developed on a "Electronics E-85" computer, a beefier PDP-11 clone; a compiled executable was then transmitted to the target computer via a custom local network.

A notable feature of the control program is structured handling of operator commands, via screen forms, or `menus'. A menu is a structure containing the text to show on screen plus the description of characters (key presses) that are accepted for this menu, and how to interpret them. Here is a typical menu:

    Menu.1::
            .word   7,10$
            .bktext <1,16.>,<\^\g>
            .bktext <6,16.>,<Mode:   \b\~A\~\guto or   \b\~M\~\ganual>
            .bktext <6,17.>,<Baseline stability>
            .bktext <12.,18.>,<\b\~T\~\ghreshold>
            .bktext <6,19.>,<\b\~N\~\g scanned>
            .bktext <6,20.>,<Start the effect managing>
            .bktext <6,21.>,<for   \b\~L\~\geft or   \b\~R\~\gight cell>
            .bktext <6,23.>,<\b\~O\~\gther>
            .bktext ,<\r>
            .byte   0
            .even
    10$:    mentry  'A,<12.,16.>,1,SetAuto
            mentry  'M,<22.,16.>,1,SetManual
            mentry  'T,<10.,18.>,2,<BLs2.thr,<23.+<18.*256.>>>,color=<\r>
            mentry  'N,<4,19.>,2,<Nscanned,<23.+<19.*256.>>>,color=<\r>
            mentry  'L,<10.,21.>,1,StinLeft
            mentry  'R,<20.,21.>,1,StinRight
            mentry  'O,<4,23.>,0,Menu.2
Here, .bktext is a macro, whose first argument (in angular brackets) is the screen position (column,row), and the second is the text to show at that position. The text may include control code such as \g for green text and \~ for toggling the inverse video mode. It should be stressed that the BK-0010 terminal is an ordinary TV monitor rather than a VT-100 terminal and is not controlled by escape-codes. To position the cursor or switch colors one has to make a dedicated BIOS call. The macro mentry describes the key accepted in the current screen form and what to do if it is pressed. In Menu.1, key 'A' invokes the SetAuto function to set the Auto mode; key 'T' lets the operator change the stability threshold (whose current value is taken from the variable BLs2.thr and displayed in red on the same line), key 'O' switches to Menu.2. Compiling such code and expanding macros took noticeable time: Macro-11 assembler felt as slow as the C compiler. (C compilation was very slow those days.)

Not only BK-0010 had no floating-point number support -- it also did not provide integer multiplication and division. I had to use fixed-point arithmetic throughout (and implement multiplication, squaring and division). I still remember what a pain it was.

Version
The current version is July 1990
References
0README.dr [7K]
The annotated directory of the complete source code (including tests). The source code files (whose names are at the left margin) are in the same directory as the 0README.dr file. A few notable files are also mentioned below.

heff.mac [8K]
A 5-state Finite Automaton (part of a high-priority foreground process) that monitors the reaction (effect) in progress, handles data points, and schedules background jobs to inform the user of the current status
effect.def [2K]
Data structures used in effect processing

bjkbdh.mac [7K]
Receive a keyboard character and interpret it in the context of the current screen form
bk.def [3K]
Definitions of macros to write a message or display a styled text
menu.def [3K]
Definition of the menu structure, and the declaration of the mentry macro
menu0.mac [3K]
Root menu of the control program
menu1.mac [2K]
Starting and stopping monitoring of effects
menu2.mac [3K]
Show and set system parameters

 

Recording neuron spikes on a stock IBM PC AT

This project was one of the neuron activity recording experiments I have automated. It used an IBM PC AT (8MHz) as it was, without any boards -- although at the limit of its processing power. One could record firings of up to four neurons, simultaneously, at 2KHz polling frequency -- for as long as there was space on disk. The results were stored in the compressed form, to be later converted to Matlab m-files and loaded into Matlab for processing. The program turned out easier to use and extend -- and also much cheaper -- than a dedicated neurophysiological equipment, which the lab could not get to work for that experiment.

This project was done for a friend of mine, who was working at that time in the Institute for Biological Physics of the Academy of Sciences of USSR, in Puschino (Moscow Region). He was studying changes in neuron firing patterns in rabbit brain in response to particular external stimuli. Talking to him in the evenings in the dorm about his work and listening to his frustrations at getting a signal acquisition equipment to work for his experiment, I said one day: you don't need any dedicated equipment. An IBM PC in your lab is enough; just make an amplifier, to bring the neuron firing potential to the level of +5V. I will write the recording program. The amplifier was a piece of cake for him: after all, he has built dedicate electrodes to insert into neurons, and all recording electronics. He had very capable hands.

To record signals one would typically use signal acquisition (extension) boards, plugged into a motherboard. Obtaining such boards was not logistically or financially possible. Therefore, in this and other automation projects I used a simple, and mainly, cheap and available, signal acquisition method: relying on RS232 (serial communication) ports, typically present in many computers (for mouse, modem, etc.). On IBM PC, these were so-called COM1/COM2 ports.

Here is the general idea of signal acquisition via a serial communication RS232 port (COM device). The trick is to use auxiliary control lines such as CTS (clear-to-send) of RS232. They are all high-impedance TTL level, that is, 0 and +5V (the threshold is at around +4.5V). The useful lines are:

One can query the status of these lines programmatically, that is, read their potential (low or high level) as a one-bit value. Often the control lines are inverted. That is, 0V on the line (line connected to the ground) will be read as logical 1; +5V on the line will be read as logical 0 (bit value 0). Here is how to read the status of the control lines in C on IBM PC:
    #define Poll_port1_no           0x3fe /* Serial Port COM1, modem status reg */  
    #define Poll_flag1              0x10  /* signal CTS, pin #5 of the 25 pin connector*/                                                                    
    #define Poll_port2_no           0x3fe /* Serial Port COM1, modem status reg  */ 
    #define Poll_flag2              0x40  /* signal RI,  pin #22 of the 25 pin connector*/                                                                    
    
    int bit = inportb(Poll_port1_no) & Poll_flag1;
When CTS is in the low state, the bit variable above gets the value 1. If the CTS line is in the high state when the above statement is executed, bit will be assigned the value 0. One can also use the port COM2, in which case replace 0x3fe with 0x2fe in the above code. An RS232 port also has lines whose state (0 or +5V) can be set programmatically, and hence used for controlling external equipment. (One needs relays since the lines carry very little power.)

My friend was researching neural firing patterns, and so was interested only in acquiring neurons' excitation state. This is a binary signal, which, after appropriate amplification can be connected to an auxiliary control line of an RS232 port and queried/polled by a program as described above. The program would poll several control lines (initially three) and, hence, record the state of several neurons. The run-length encoded spike data (that is, the intervals between two consecutive spikes) are written on disk, as a so-called .IMP file.

The structure of the program is common to other experiment automation programs of mine. It was interrupt-driven. One of the PC AT interval timers was programmed to deliver interrupts at the polling frequency. The interrupt handler polls the input channels: RS232 lines connected to the electrodes inserted into neurons. A spike manifests as reading 1 from the corresponding poll. The interrupt handler counts the intervals between two spikes, on each channel, and records them into a memory buffer. The interrupt-driven sampling not only keeps the polling interval more or less constant. It also lets us interleave sampling and writing: a filled buffer is written onto disk, as a `background task'.

The code was written in C (Turbo C) nominally, but used quite a bit of inline assembly for speed. I would write the code first in C, then comment it out and translate to assembly by hand. Interrupt-handling and polling were especially time-critical and had to be programmed almost entirely in assembly.

A later version of the program used the polling interval 500usec (down from 1000usec) and acquired signals on four channels.

Version
The current version is Spring 1991
References
impulses.h [4K]
The declaration and description of the main data structure: the ring of buffers. The current buffer is being filled in the timer interrupt handler. A filled buffer is written to disk, in background.

impulses.c [3K]
The main module: initialization and the main loop

telling.h [<1K]
telling.c [4K]
The user-interface: the initial dialogue and the periodical status display

filling.h [3K]
filling.c [10K]
Handling the timer interrupt, polling the channels and filling in the current buffer with inter-spike intervals. This is the most time-critical part of the program, and is written largely in hand-translated inline assembly.

writing.h [2K]
writing.c [6K]
Writing filled buffers to disk

timer.h [4K]
timer.c [5K]
A small library to control the 8253/8254 timer chip; query and set interval timers. One of the timers was used to deliver interrupts at the sampling frequency.

imp2m.c [9K]
A separate program to convert an .IMP file to a set of Matlab m-files (one per channel), for loading into Matlab

 

Simple PC text-mode window system in Modula-2

This Modula-2 code is part of a larger project, an emulator of a non-traditional vector FPGA-like CPU architecture. Unlike the familiar FPGA, the processing elements (nodes) are connected in a full binary tree rather than in a regular rectangular mesh. The architecture was designed by Dr. Makarov at Kazan State University in 1987-1988. Besides the emulator, the project implemented higher-level operations like multiplication and division of integral and floating-point numbers.

Given below are general-purpose utilities and the user-interface-related code. As to the emulator proper, I do not feel I have the right to say anything more about it or the target CPU architecture. I am not aware of its further development.

I used the Modula-2 system developed by the `Interface Technologies Corporation'. The system included a smart, syntax-sensitive editor. The editor made sure that at all times the program is syntactically correct -- which sometimes was a hindrance.

Version
The current version is about 1987
References
modula2.tar.gz [12K]
Archive of the commented source code
The modules Kbd and TIO implement low-level terminal i/o via BIOS and DOS interrupts. TIO also supports character escapes and printf-like formatted output. The module Window lets one write text into rectangular areas on the screen, supporting line wrap-around, scrolling, colors, and cursor positioning. The module used BIOS interrupts and directly accessed the videoRAM. On the top of these modules, MWDr implements a line editor and a menu processor. The utility modules include Lexem (string tokenizer) and Set (finite maps).

 

Simple text editor in PL/I

This PL/I code was written for simple text editing of source code files on an IBM mainframe (clone) that had no interactive editing devices save the operator console. The only way to edit source code disk files was to punch the changes on cards and submit a batch job to apply the changes, with the help of the system utility IEBUPDTE. Even if a user had access to a machine room, he still had to punch the updates on cards and run that batch job. That was quite inconvenient. This trivial utility was written to help such users fix simple errors in their source code files from the operator console. I had used the utility on many occasions -- until our computing center got display terminals.
Version
The current version is Spring 1982
References
upd.pli [5K]
The self-contained commented PL/I source code.

 

RTRAN parsing and finding direct products in Algol-68

This old Algol68 code is a part of a database system for the results of statistical mechanical calculations. The computed data could be later retrieved for further processing. This self-contained code converted retrieval requests into the request language of the underlying hierarchical database, expanding the abbreviations for sequences of data sets.

The code illustrates parsing via a Turing-like machine -- so called Glushkov R-Technology. I implemented what I understood from a quick glance through Glushkov's book a few years earlier.

Version
The current version is about 1985
References
tpbbldrq-ann.a68 [12K]
The self-contained commented Algol68 source code
The beginning of the file has a long description of the code, in plain text. It is not part of the code and should be removed prior to compiling the code.

R-Technology
More detailed description of the R-technology, with several implementations and applications

 

File integrity checking on IBM S/360 and PDP-11

The archetype of file integrity checking is tripwire, written by Gene Kim and Eugene Spafford at Purdue University in 1992 for the purpose of detecting modifications to system files, as signs of malicious activity. In the initialization mode, tripwire computes hashes (i.e., checksums) of system files and records them in a special file. In the checking mode, the tool recomputes the file hashes and compares them with the those recorded earlier. The mismatch indicates the file has been tampered with, e.g., infected by a virus.

Back in 1988 I have written the identical tool, called CHECKDS, for an IBM System/360 clone (EC-1033). The purpose was not checking for viruses however. I was alarmed by the corruption of a file on my (29 MB) disk pack. I wanted to detect such corruption early so I could correct the file or restore it from the backup. I would run CHECKDS from time to time, checking checksums of important disk files against the previously computed values.

The program CHECKDS was quite atypical System/360 program: it was opening dynamically-named files: the names of the files (called `data sets' in System/360 parlance) to check were read from another file. Normally, all files needed for a program must be reserved in advance of program execution and hence described on JCL DD-cards. In the batch-oriented System/360, the names of all files opened by a program must be statically known. Opening files whose names are computed was very rare, requiring special knowledge and administrative privilege (so-called ``zero memory key'', to modify operating system tables).

The program CHECKDS had another peculiarity: it processed so-called library files (``partitioned data sets'', in the official terminology) as if they were ordinary (i.e., sequential) data sets, which may contain records of zero length. Such records separate library members. Normally reading a record of zero length raises the end-of-data indicator. To ignore zero-size records when reading a partitioned data set, CHECKDS installs a call-back (formally called ``IO appendix'') to be executed upon the completion of IO channel operations. The call-back will check for the zero-length record and reset the error indicator. Installing IO callbacks too required zero memory key.

About a year later, working on a micro-computer, a clone of PDP-11, I had to check for corruption of disk files again. Soviet-built computers were notably unreliable. The disk controller of that particular computer broke down. A friend of mine, a remarkable electrical engineer, identified the failure in the checksum computation circuit, which he managed to disable. The computer could work again but disk data corruption could no longer be detected. I had to compensate for faulty hardware with software.

Version
The current version is about 1988
References
checkds.asm [15K]
The commented IBM System/360 Assembler code

verify.c [9K]
The commented C code; DEC RT-11/XM operating system

 

Poster/slides directly in PostScript

PostScript is generally known as a page description language: an intermediary between a typesetting application such as TeX, and a printer. PostScript however is a general purpose language, and can be programmed in. Perhaps one of the better known examples of hand-written PostScript programs is NeWS, the technically superior alternative to the X Windows system once developed by Sun Microsystems.

I first saw NeWS on an SGI IRIX workstation in the office of my boss at a lab I was visiting in mid 1991. I knew a bit of Forth and was glad to see such an impressive application of it. I then learned PostScript from the Adobe manual (`the red book') and played with NeWS from time to time. When the boss wanted to present a poster about our work, I declared that we make it in PostScript. I wrote several PostScript functions (`words') to set up a page, typeset lists, easily change fonts, etc. The boss played along and even did editing of his own. Of course we used the NeWS own PostScript interpreter (psh) to preview the results. Half a year later, in a different lab, presenting a poster at a conference came up once more. Again, I chose to do it directly in PostScript. The topic was wavelet image compression, and the poster included equations and diagrams, for which PostScript turned out especially convenient. Without an easy access to a workstation, previewing was a chore however. I use that poster as an example to introduce the postscripting.

One should be well aware that as a typesetting language, PostScript is quite low-level: by itself it does no line breaking, word placement, justification, alignment, etc. It is no TeX -- although something like TeX could well be programmed in it. Luckily, posters and slides are not supposed to contain long paragraphs of text. They should present outlines, equations and figures -- and for that, PostScript is adequate, especially with a few `words' for placement, lists, sub/superscripts, math symbols, etc.

To give the feel for manual PostScript posters, here is the beginning of the source for page 5 of the image compression poster:

    (5) newpage
    24 points TR (TRIMMING) showcenter
    newline .20 inch lineshift
    
    18 points TR
    
    { 22 points TB (      I. Uniform ) show } locally
    newline
    
    indent
    (\267 Sets  c) show (k) sups (lm) subs (   ) show s= (0) show
    (  if  ||) show (c) show (k) sups (lm) subs (    ) show (lm) Phi (||) show
    ( < T, a threshold) show
    newline -0.10 inch lineshift
    
    (\267 Keeps only ) show { HB (significant features of the image) show } locally
    newline -0.10 inch lineshift
     indent
     { TBI
      ((contrast)) show s_product ((grain-level) > threshold) show
     } locally
     end-indent
    newline -0.10 inch lineshift
    
    { HB (  uniformly ) show } locally (over the entire picture) show
    newline .15 inch lineshift
    end-indent
where indent increments the left margin and end-indent decrements. The word locally executes a sequence of words restoring the font settings afterwards.

Page 6 of the poster, about the discrete gradient, starts by defining the gradient operator

    /Dx				% Gradient Operator in x
    {
      currentfont				% Put the currentfont to the stack
      getfontsize 1.1 mul points
      TBI (D) show				% D stylish
      setfont				% Restore the font that was before
      0.05 inch neg 0 rmoveto
      (x) subs
      ( ) show
    } def
later used in a formula to compute it:
    { 22 points TB (Computation) show } locally
    newline
    (   ) show Dx (f(x,y)) show s=
        (M) (k=0) sum_sign ( ) show ( ) (l,m) sum_sign ( c) show (k) sups (lm) subs
        (     ) show Dx (lm) Phi 

Page 6 also has diagrams, drawn as typically in PostScript, with moveto, rlineto and stroke (TeX native drawing facility is similar and just as low-level, but more difficult to program).

Looking at this code 30 years later, lots of improvements come to mind. I should have used lists and defined more `environments' like indent/end-indent, borrowing ideas from LaTeX (which I barely knew at the time). As I tried to view the complete poster in Ghostscript, it displayed just as well as 30 years earlier, with no changes at all.

Version
The current version is March 1992
References
James Gosling, David S. H. Rosenthal, Michelle J. Arden
The NeWS Book: An Introduction to the Network/Extensible Window System
(Sun Technical Reference Library), Springer, 1989, ISBN 0-387-96915-2

procs.ps [7K]
local_procs.ps [2K]
Typesetting words (`macros')

page.5 [2K]
page.6 [4K]
Source for pages 5 and 6 of the poster. The same directory contains the source of the other pages: page.1..page.8 (The university did not have an easily accessible large-format printer, so the poster was a collection of individual pages -- as was common at the time.)

complete-poster.pdf [13K]
The complete poster

 

Dired mode for VAX EVE Editor

Visual file managers is something that one (re-)discovers sooner or later. After all, it is much easier and, well, intuitive to select a file for editing or removing just by `clicking on it' in a displayed file list, rather than by typing its name. As soon as computer terminals permitted full-screen display and cursor navigation, visual file managers sprang up. The iconic, although by far not the first, was Norton Commander (nc) for IBM PC.

Spoiled by nc, when working on VAX/VMS in 1990 I wanted something similar. In fact, our VAX already had it, from a DECUS tape. DECUS was a DEC User's Society, which collected and distributed user-developed software with source code and for free. (Free and open software predates FSF and FOSS by a long shot.) I was not satisfied with that file manager however.

There was already a well-optimized text user interface on VAX/VMS, which could display full screen text in several non-overlapping windows, position the cursor and act on key presses: a text editor, EVE specifically. EVE was an extensible editor built with the VMS Text Processing Utility (TPU) -- a simple, PASCAL-like programming language with built-in data types for buffers, windows, ranges of selected text, etc. Today one may say it was just like Emacs -- which is unfair: `Emacs is like TPU' seems more appropriate; after all, Emacs includes the TPU emulation.

It was natural, to me, at least, to develop a file manager within EVE. Which is what I did over several days in 1990 and used until I had to leave the VAX environment. There is not much to say about the code: it was rather straightforward -- thanks to the power and expressivity of TPU. One cannot help but feel nostalgic after looking at the code -- and sigh over the fate of TPU, and VMS.

Incidentally, Emacs dired-mode appeared in 1985-1986, it seems, but then put on a 6-year hiatus. I was not aware of it: likely it was not part of Emacs at that point. Anyway, Emacs (and Unix in general) at that time was hardly competitive with what VAX had to offer.

Version
The current version is June 1990
References
ncinit.tpu [8K]
The set-up code (allocating buffers, windows, etc.) and creating the file list

ncbody.tpu [6K]
Key handlers: actions of the file manager