SLIP

What SLIP is

SLIP stands for Symmetric LIst Processor. Weizenbaum designed it around 1962 and described it in the Communications of the ACM in 1963, when the list-processing ideas of IPL and LISP were still new. It is not a standalone language but a set of routines bolted onto a host language, first FORTRAN and then MAD. The version ELIZA used ran on MIT’s CTSS on the IBM 7094: MAD for the logic, SLIP for the lists.

Why “symmetric”

SLIP’s lists are doubly linked: every cell holds a pointer to the next cell and to the previous one. That two-way, symmetric linkage is where the name comes from. It lets a program walk a list forwards or backwards, splice cells in and out from either end, and treat any cell as a place to read from or write to. Free cells are kept on an Available Space List (AVSL); creating a list draws cells from it, deleting a list returns them.

A line of dialogue as a list

When you type to ELIZA, your words become a SLIP list, one word per cell. Here is the opening line of the 1966 conversation, Men are all alike, held the way ELIZA holds it:

What ELIZA added to SLIP

The original SLIP has two distinct modes. One handles organisation: the previous and next pointers and the sublists they string together. The other handles data, and in the original it was given short shrift, supporting only integers and real numbers. Weizenbaum extended the data half so a cell could also carry a string, spread across as many SLIP words as it needs, six characters to a word, the words of a sentence, the keywords of a script, the templates of a reply. Most of the original SLIP is pointer maintenance; most of the SLIP that ELIZA needs is datum handling.

How ELIZA uses it

Almost every structure in ELIZA is a SLIP list. The user’s input is read into a list of words. The script’s keywords live in a hash table (KEY) of lists. Each keyword’s decomposition and reassembly rules are lists of lists. The memory of what you said is a list of transformed sentences. To produce a reply, ELIZA walks these lists with SLIP’s readers, matching and rebuilding as it goes.

Reading the idioms

Once you know they are SLIP calls, the dense lines of the recovered source begin to read. A few recur throughout:

• SEQRDR / SEQLR: make a sequence reader for a list, then read its next cell left to right. This is how ELIZA scans a list. A reader is what a modern language would call an iterator.
• POPTOP / POPBOT: remove and return the cell at the top (or bottom) of a list.
• NEWTOP / NEWBOT: add a new cell at the top (or bottom) of a list.
• HASH, YMATCH, ASSMBL: hash a word into a table index, match a decomposition pattern, and assemble a reply from a template. These three sit in the SLIP listing but are not part of SLIP as published: they do ELIZA’s work, and Weizenbaum appears to have kept them there for convenience rather than as an extension of the library.
• LSSCPY, SUBST, IRALST: copy a list, substitute a cell, and return a list’s cells to free space.

These are the verbs of ELIZA. The close reading of the program follows them through the main loop, and the step-by-step demo shows the result.

Introduction

Weizenbaum developed SLIP (CACM v6n9) in 1963 as a successor to his Knotted List Structures (KLS) of the previous year (CACM v5n3). In KLS the framework of what was to become SLIP was developed, significantly with a single list pointer rather than a doubly linked list. In SLIP we see the basic ideas extended and a fuller representation of the ideas developed than in KLS.

In describing SLIP we talk about the contribution that SLIP made in the general, nascent, field of computer science. SLIP by itself was anticipated, but the unexpected nature of its contribution was in its construction as an Application Programming Interface (API) in which a set of functions are organized to perform some collective task, but the logic for the task is contained within the calling application. An API is not separately executable. With this we will give a short mention of portability within the framework of the time, and Weizenbaum’s use of portability. Then there is the subject of SLIP, what it does and how it does it.

1.0 Glossary

There is an attempt to use current terminology when talking about SLIP objects. However, current terminology was not used in the SLIP defining article in the Communications of the ACM (CACM v6n9). So here is a glossary which stretches the gap between understanding the article and understanding the blog.

address

Pointer to the first word of a SLIP object

associative list

List of <key, value> pairs where both keys and values are SLIP Datum cells

DAG

A Directed Acyclic Graph. A graph without cycles

data

The data in a SLIPData cell. Either an integer or floating point number

descriptor list

Associative list

DG

A Directed Graph. A graph which may have cycles; a DAG is a type of DG

LINKL

Pointer to the previous SLIP cell in a list

LINKR

Pointer to the next SLIP cell in a list

list

A SLIPHeader cell. A node on a graph

Name

A reference to a SLIPHeader cell. A SLIPName cell

node

A SLIPHeader cell. A node on a DAG

reference

Pointer to the first word of a SLIP object

root

A node which is not a child

SLIPData

A SLIP cell containing data

SLIPHeader

A SLIP cell defining the head of a list

SLIPName

A SLIP cell containing a reference to another list (SLIPHeader)

SLIPReader

A list iterator with memory

SLIPSequencer

A list iterator without memory. A pointer to a SLIP cell

Sublist

A list contained in a list, a.k.a. a child node in a graph

2.0 SLIP Overview

In the literature SLIP was represented as a list of lists, where each list could have sublists. The representation is somewhat deceptive. It is better represented as a Directed Acyclic Graph (DAG) where each node on the graph has two lists, an associative list of key, value pairs, and a symmetric list of list atoms. In this context a list atom is a SLIP cell with a link to the previous SLIP cell and the next SLIP cell acting as a data carrier for a machine primitive (integer or single precision floating point), or a pointer to a contained list. Various Application Program Interface (API) functions supported the creation and deletion of list cells, and the modification of list cell data.

Figure 1 shows three SLIP lists in a DAG. The root list is at the top and the two subordinate lists are below it. In 1966 this would be called a list of lists, with the subordinate nodes identified as lists, and at the time, all SLIP cells would be shown. The description of the structure would be an S-Expression, as in ( () () ), where the root is the outer parenthesis and each of the two contained lists are represented as ( ). Hence a list containing two lists.

In SLIP, the root node is always a SLIPHeader data cell, and all other nodes are SLIPSublist cells. SLIPSublist cells are data cells that reference SLIPHeader cells. A SLIPHeader cell defines the list header node and references to the associative list and list.

As a DAG the dialogue and representation is clearer than being represented as a list of lists. As a DAG we can say ‘root’ with a clear and defined meaning, and we can say ‘leaf’ and interior node. As a list of lists both terminology and representation become muddled. We could say the ‘outermost list’ and then the ‘list containing no sublist’ to represent the root and leaf, and then the ‘a contained list containing sublists’ to represent an interior node. It is much clearer to reference the known statements about graphs rather than that of a list.

In a similar fashion a DAG represents a graph in which no node points to a parent node. Or if you will, a graph without cycles. Using the list of lists terminology the statement is tortuous. We will use the graphic terminology when talking about SLIP structures. And we will say that SLIP allows the representation of DAGs, a directed graph without cycles.

Figure 2 shows a representation of the DAG from Figure 1, but here, the root node contents are made clear. The root node has two lists, an associative list and a symmetric list, and references to two leaf nodes. As a DAG, the leaf node’s parent is the root node, and the root node has two siblings.

In Figure 2 the root node has two lists. An associative list with two <key, value> pairs, and a standard list with two data cells. The Figure shows that the root node points to the first and last data cell in the list, and points to the first <key, value> pair in the associative list, and the terminal data cell points to the root node, and the last value cell points to the root node. This is by design and makes best use of the available space in a SLIP cell.

2.1 Computer Architecture

The SLIP architecture is based on the computers available at that time. The ones used by Weizenbaum, the IBM 7094 and CDC 1604, accessed a full word of memory and had a maximum computer memory size of 32,768 words. An instruction could only access a word, and if address referencing using data in a word, only 15-bits were used. This meant that a 36-bit word, in the IBM 7094, and a 48-bit word, in the CDC 1604, had extra bits available for use, and that using these extra bits would not interfere with their use as an indirect reference to another word. Further, both machines could fit two addresses into a single word.

A SLIP cell consists of two adjacent physical words of memory. The first (lowest addressed) word contains SLIP dependent information. The second (next physical address) contains user data.

A SLIP cell uses two physical words of a computer. The first word has two addresses of 15-bits right aligned in a half word, plus two left aligned in a half word reserved areas for SLIP data type information.

2.2 SLIP Physical Architecture

The SLIP-centric use of a SLIP cell is to use the first word to contain the address of a previous SLIP cell in a list, and the address of the next SLIP cell in a list, and to use the reserved bits to carry SLIP cell type information.

In CACM v6n9 the identified data types are:

• 0: SLIP Data cell. Interpret the second word in a SLIP cell as data.
• 1: SLIP Name. Interpret the second word in a SLIP cell as the address of a list, a.k.a. a SLIP Header cell.
• 2: SLIP Header, a list header. Interpret the second word in a SLIP cell as the address of the node associative list. The previous address is the address of the last SLIP cell in a list, and the next address is the first SLIP cell in a list.
• 3: SLIP Reader. The cell is a list iterator. Readers are standalone SLIP cells which are not contained in a list. Therefore both the first and second word of a SLIP cell are different than for a list element. A reader contains a pointer to the current SLIP cell and the current SLIP Header, the address of the previous SLIP Reader data, and the depth of the current SLIP Reader.

What we have described is a SLIP Cell, data types 0–2, and an iterator, data type 3. Let’s look at this in a little more detail.

1. A NULL address has the value zero (0). Whenever an address has the value zero it is considered as not pointing at a SLIP cell object.
2. An empty list is indicated by the SLIP Header cell pointing to itself in the first word; the previous and next address is the address of the SLIP Header cell. A SLIP Header never has either the previous or next address NULL.
3. An associative list is not required. A SLIP Header cell without an associative list has the associative list address, the second word of a SLIP cell, equal to NULL.
4. Data. Data can be either an integer or floating point data. The application is required to know which is contained within a SLIP cell.

3.0 SLIP as an API

APIs have several definitions. We will use the definition that an API is a set of functions supporting a single task and which must be included in another program and which does not share a memory/data space with the caller. Like a sin function, an API does nothing without an externally supplied program calling it. This definition excludes a library of functions in which each member of the library is separately callable but which are independent in functionality from other library functions. This excludes, for example, a scientific library of functions in which there are sine, cosine and tangent functions.

SLIP was probably the first API. SLIP provided a complete and encapsulated set of functions whose sole purpose was to support the construction and use of a DAG. Any FORTRAN II program requiring the use of a DAG could use SLIP (subject to portability issues).

4.0 SLIP Portability

Portability of an API was constrained by the computer software language and the computer architecture. If one or the other was inconsistent in supporting portability, then the API was unportable. SLIP was ‘ported’ from an IBM 7094 to a CDC 1604 and written in the FORTRAN II programming language. What does this mean?

The language does not support bit operations, and certain other pointer operations. In order to use SLIP at all, these required language elements must be hard coded in the assembly language of the respective machines. The remainder of the functionality, up to some hardware caveats, was portable. Compiling SLIP using the IBM 7094 or CDC 1604 compilers would yield compatible functionality. Writing appropriate missing language functionality in assembly language would mean that all SLIP functionality was available for use.

The computer architectures supported creation of a SLIP cell; that is, it was possible to use two computer words to contain all required fields to enable SLIP processing.

The computer architectures did not support binary compatibility. This meant that binary data output from one computer could not be input and used on the other. This is briefly mentioned in the CACM article when portability is addressed. The reasons for this are that on computers of the day both integer and floating point number internal formats were different on different computers. Floating points were all different; there was no standardized format. Integer formats were better quantified but they could be anything from one’s complement, two’s complement, sign-magnitude, fixed point and decimal. On the IBM and CDC computers, the floating points were different and the integer formats were different, sign-magnitude on the IBM and one’s complement on the CDC.

It could be possible to generalize functionality and create a SLIP standard format for both floating point and integer, but this was not done. Indeed, the process for doing this was difficult and meant that for each hosting computer a separate package needed to be included to convert internal number formats to some standardized format. This would reduce portability.

SLIP was portable up to supporting SLIP functionality, with the addition of assembly-language functions to accommodate language ‘failures’.

5.0 SLIP Functionality

Well. What does it do? We’re going to take you through some superficial details of the workings of SLIP. And we’re going to do this through the lens of the current ideas of software and software functionality, not to criticize the product, but to identify some weak points. This is not a user’s manual so the details of operations and the functions required to support them should be looked for in the CACM v6n9 article.

SLIP in general doesn’t do much for you. The application has to know the address of SLIP cells and has to know the types of data contained in SLIP cells. We can’t take this as criticism because SLIP does everything requested of it: it allows the creation of lists and DAGs, and allows iteration through them. This is what is wanted. But it makes life harder for the application by requiring the application to know the address of SLIP cells so that the included functionality can do the mechanics of manipulation required. One wonders why Weizenbaum didn’t see this as a defect and take on the labor of providing functionality ‘hiding’ the mechanics of implementation from the application by “doing it for you”. But Weizenbaum was a creator, an innovator at a time when there was nothing like this, and no guidelines as to what to do. He did well, but I wish the mechanics were better hidden.

FORTRAN II has one strong liability where SLIP is concerned. FORTRAN II owned memory, and there was no facility for an application to acquire memory from some memory resource. In languages such as C and C++ they support acquisition of memory from the ‘heap’ using ‘new’ to acquire such memory, and ‘delete’ to, well, dump it when no longer needed. This did not exist in FORTRAN II (or FORTRAN IV/66, or FORTRAN 77, or FORTRAN 90). So the application had to allocate its own memory and to tell SLIP where it is. This enabled SLIP to do its own memory management, to acquire memory and delete memory to support the transitive nature of memory usage. As a note, no other procedural language at this time had a concept of transitory use of memory. This didn’t occur until C, some 7 or 8 years hence. And to those who are interested, LISP is not a procedural language.

Memory use was cooperative. An application needing a SLIP cell had to ask for it, and when it was no longer needed, had to release it. This included individual SLIPData (and the SLIPReader), and lists. At the time this would have been completely novel. FORTRAN did not have dynamic memory; once memory was allocated, it existed forever. The notion of a stack frame where locals (local variables in a function) were automatically created on function call and deleted on function exit was not known. And yet, with the artifice of the application creating a block of memory and passing it to SLIP, SLIP achieved dynamic memory usage.

A list or a DAG is a complex structure. SLIP provided two mechanisms to iterate across the structure. One was called a Sequencer, the other a Reader (SLIPReader). The Sequencer was a simple SLIP cell pointer which ‘knew’ how to traverse to the next or previous cell in a DAG. But it had no memory. This meant that traversal to a child node was one way; there was no way back to the parent. A Reader had memory. It could enter into a child node and return to the parent. But memory takes resources and with 32,768 words of memory for data and instructions, there was some caution in using a Reader.

The Sequencers and Readers are search functions. In a list there are three types of cells, the list header (SLIPHeader), the list data (SLIPData) and a child reference (SLIPSublist). You can search for the SLIPData and SLIPSublist cells. And note, with a Reader the search terminates on the root SLIPHeader cell, and with the Sequencer the search terminates on the SLIPHeader cell of the current list being searched (either the child or parent list). That means that with a Reader you can automatically go down and up a DAG, but with a Sequencer you can go down and cannot go up.

There is also a capability to implement a form of recursion (the SLIP VISIT function). By current standards it is very crude. A lot of work has to be done by the application in setting up and using what we call now a stack frame, and since true recursion is not available in FORTRAN, recursion becomes an iterative loop where each loop cycle requires attention to the created stack frame.

The data in a SLIPData cell could be retrieved by the application, but the application was required to know whether the data was an integer or a floating point number. The acquisition routine used depended on this knowledge and would return a value of the indicated type. In actuality, the access routines (INHALT, CONT) took the data in the data word and returned it as either an integer or a floating point number.

Now here are some of the present day issues in looking back at the past. Anyone could do anything. All functions were available to the application, allowing the application to change the data types of a cell, to store an integer and retrieve it as a floating point number (or vice-versa), and SLIP had no way of ensuring proper functioning. Further, as part of FORTRAN, a pointer was an integer. So anytime the user wanted to put a pointer in a SLIP cell, why, just pass it as an integer. There were few, if any, validity checks. The application was encouraged to be an adult about this, but if you weren’t, well, things would happen, most often undetected. For example, running out of SLIP memory was a “so what”.

6.0 So, Why Isn’t It Famous

Well, we have a couple of theories on this. In order to acquire fame there has to be an audience and a promoter. Weizenbaum did not promote SLIP. He left it to others, whose interest was less in using and more in changing the DAG to a DG. And there was no non-academic need. Few, if any, programs at that time dealt with lists (a terminology which was just beginning to be created). And almost no one then or now dealt with DAGs, or anything remotely like a DAG. This is not to say the need was non-existent but that it was vanishingly small, and without an advocate to tell of the existence of this API, even if there was a need there wasn’t any knowledge. So, as useful as SLIP was, it was unknown and unused.

7.0 Summation

SLIP was an API, something unique at this time. SLIP supported the creation and deletion of lists, DAGs and data, not only something unique but for which the technical vocabulary was non-existent. SLIP code is poor on documentation and poor on checking for error conditions, not much computer power or memory to include this. SLIP had dynamic memory, something we take for granted now but was truly unique in a procedural language at the time. Was it worth it? Damn’d straight it was.

8.0 Note

For those interested in pursuing a modern version of SLIP, there is a pre-production version at https://slipbits.com/gslip/. This is a modern version written in C++. It removes the mechanics of insertion/deletion, allows for several data types and the direct use of SLIPData cells in computations plus some other things. A user manual, source code, and a Win1x (x86-64) executable is provided.