LISP is quite different from the languages we’ve looked at so far - but I will not give an introductory description, as there are plenty of resources on the Internet by better writers than me - instead I will look at how MTS LISP differs from more modern Lisps.
In the examples below, input is prefixed with a * and output with >.
Representation
MTS LISP assumes all keywords are in uppercase, but is otherwise free format. Do note that if you put the comment character ; in the first column this will be treated as a carriage control instruction to advance to the start of the next page in listings, so best prefix this with a space.
Types
As in other LISPs, the primitive data structure is the atom, which have values and property lists; atoms can be combined in s-expressions to form binary trees or lists. Here we define three atoms, a, b, c:
* (SETQ A 42)
> 42
* (SETQ B 'A)
> A
* (SETQ C (CONS A B))
> (42 . A)
There are no strings, but you can double-quote atom names to get printable output:
*LISP has dynamic scoping; variables defined in a function, or in a PROG, replace the current definitions for the life of the expression, including calls to other functions. See below, where the definition of X in the PROG is available in the GETX function.
There is no let or lexical binding in *LISP, hence no lexical closures. It may be possible to do dynamic closures but there does not seem to be function or funargs available which is needed to implement this.
There are also no macros (like defmacro) which can be expanded and evaluated at run time; there is a basic macro facility called READMACRO and PRINTMACRO where a function can be called whenever a designated atom is encountered while reading or printing.
GOTO in LISP
This rather blew my mind: a GOTO in LISP? The below will loop and read input until the user enters a number larger than 99. A and Z are labels:
(PROG (X)
A (SETQ X (READ))
(COND ((GREATER X 99) (GO Z))
(T (GO A)))
Z (PRINT 'DONE))
There is also (RETURN x), which will break out of the enclosing PROG immediately.
Super parentheses
Lisp is famously parenthesis-heavy: today we have text editors that can show matching pairs and indent code automatically but contemporary users of LISP would have had to do this by hand. To help out, *LISP defines the angle-brackets {} as super-parentheses: whenever an opening brace is encountered, the depth is remembered and when the matching close is found, the depth returns to that level. For example:
* (SETQ A (CAR (CDR (CDR (LIST 'A 'B 'C 'D)))))
> C
* (SETQ A <CAR (CDR (CDR (LIST 'A 'B 'C 'D>)
> C
Worlds
*LISP has a facility similar to database transactions where you can store the current state, change data and then either commit or rollback. (NEWWORLD) will return a ticket to the current state; you can then change data with special versions of LISP primitives such as SETQ2 or RPLACA2. (REALWORLD) can then be used to commit or (GETWORLD x) to roll back to the state at the time of ticket x.
* (SETQ2 A '42)
> NEWWORLD 04-15-82 RESTORED
> 42
* (SETQ W (NEWWORLD))
> (((0 *UNDEF* . 42)) (NIL))
* (SETQ2 A 33)
> 33
* A
> 33
* (GETWORLD W)
> NIL
* A
> 42
Further information
Chapter 3 of Successful Lisp is a good introduction to Lisp if you’ve not used it before; it’s written for Common Lisp users but most is applicable here.
I’m still trying to restore ALGOL 68 from D4.0 and although I’ve had some great help from the folks on the H390-MTS list I have not yet got a working system running. While I continue to work on this, let’s look at a completely different language - LISP.
LISP overview
LISP is one of the oldest high level languages still in use today, with the original version developed by John McCarthy at MIT in 1958. It combines procedural, functional and metaprogramming elements and has a unique syntax based on balanced parentheses that make it unlike any other language of its time.
LISP gained popularity in the 1960s and 70s during the AI boom, when the language evolved rapidly and there was even special hardware built in order to run it efficiently. This died down towards the end of the 20th century, but it remains influential with concepts from LISP such as lambdas recently being added to languages such as Java and C++. Common Lisp implementation continue to be used today, and LISP has been used as an extension language, most famously in Emacs and AutoCAD.
LISP on MTS
The primary LISP environment in MTS, *LISP, was developed at the Mental Health Research Institute at UM. (Not an organisation you’d think would be implementing a programming language; the Wikipedia article on Brian Wilcox, one of MTS LISP’s authors, mentions that it was developed in order to play the game of Go.). It is based on LISP 1.5, one of the earliest versions of LISP that was in wide use, with some extensions drawn from later LISPs and customisations for MTS.
There are a number of other LISPs available on MTS, such as the University of Tokyo’s UTILISP, that I will look at later.
Prerequisites
No special installation instructions to get LISP running - just do the standard D6.0 setup as described in this guide and then sign on as a regular user such as ST01.
Using *LISP
LISP is an interpreted environment. Running *LISP on its own will allow you to start entering expressions which will be immediately evaluated. It’s possible to load expressions from a text file by providing it as the scards parameter to *LISP; after the file is read you will remain in the LISP expression reader. To run a complete program and return to MTS afterwards, make the last expression be (STOP).
There is a rudimentary line editor available via (EDIT fn) but it’s easier to do this outside of LISP.
You can also save the current state of the system (to a binary file) with (CHECKPOINT filename) and reload it in a later session with (RESTORE filename).
It’s possible to compile expressions to machine code with (COMPILE fn) but this is unlikely to be worthwhile as MTS on Hercules is fast enough.
Hello world
Here’s a transcript of a session where we run a Hello world program. This assumes the source code is contained in the file hello.l.
For our sample ALGOL W program we’ll implement a simple priority queue.
The problem
A priority queue can be used to store items tagged with a priority value and then retrieve them in order of priority. Several operations need to be implemented
Check if the queue is empty
Insert an item
Peek at what the highest priority item is
Remove the highest priority item from the queue and return it
We will use a binary heap to implement the queue: this allows O(log n) inserts and removals, and O(1) for peeking at the highest priority item, as the queue is kept in priority order after each operation.
To test our program, we need to insert some items in random order and then see if they dequeue in priority order:
% Insert some tasks in random order %
PQ_Insert(Item(3, "Clean drains"));
PQ_Insert(Item(4, "Feed cat"));
PQ_Insert(Item(5, "Make tea"));
PQ_Insert(Item(1, "Solve RC tasks"));
PQ_Insert(Item(2, "Tax return"));
% Remove top priority item from queue and print %
while not PQ_Is_Empty() do
begin
reference(Item) First;
First := PQ_Delete_First;
write(Priority(First), Task(First));
end
Data structure and constraints
To store the queue, the binary heap implementation needs an array of items and an indication of its current size, which we can define as:
PQ_Capacity is the maximum size of the queue, which we’ll define as a constant; it does not seem possible to resize an array in ALGOL W. We’ll make the array and size global variables for simplicity: a better, if more verbose solution, would be to pass the data structure to each interface function, eg
It would also have been nice to encapsulate both PQ and PQ_Size into a record, but ALGOL W records do not allow arrays as members. One way we could combine this into one variable is to make the array have bounds 0::PQ_Capacity and store the current size at location 0.
Public function implementation
It’s then fairly simple to define the public functions:
% Initialise a queue %
procedure PQ_Init();
begin
PQ_Size := 0;
end;
% Return true if the queue is empty %
logical procedure PQ_Is_Empty();
begin
PQ_Size = 0
end;
% Add a new item to the queue %
procedure PQ_Insert(reference(Item) value New_Item);
begin
% Add to end of array and swim down to maintain %
% priority order %
PQ_Size := PQ_Size + 1;
PQ(PQ_Size) := New_Item;
PQ_Swim(PQ_Size);
end;
% Return the first item in the queue by priority %
reference(Item) procedure PQ_First;
begin
PQ(1)
end;
% Return the first item and delete from queue %
reference(Item) procedure PQ_Delete_First;
begin
reference(Item) First;
PQ_Exchange(1, PQ_Size);
First := PQ(PQ_Size);
PQ_Size := PQ_Size - 1;
PQ_Sink(1);
% Just to be safe, null out reference at end %
PQ(PQ_Size+1) := null;
First
end;
Private functions
These call a number of private functions - note that privacy is not enforced in ALGOL W however. First, to keep the heap organised, we need PQ_Swim and PQ_Sink:
procedure PQ_Swim(integer value K);
begin
while K > 1 and PQ_Greater(K div 2, K) do
begin
PQ_Exchange(K, K div 2);
K := K div 2;
end;
end;
procedure PQ_Sink(integer value k);
begin
logical Done;
Done := false;
while 2*K <= PQ_Size and not Done do
begin
integer J;
J := 2 * K;
if J < PQ_Size and PQ_Greater(J, J+1)
then
J := J + 1;
if PQ_Greater(K, J)
then begin
PQ_Exchange(K, J);
K := J;
end
else begin
Done := true;
end;
end
end;
These need to call primitive functions to exchange and compare:
logical procedure PQ_Greater(integer value I; integer value J);
begin
Priority(PQ(I)) > Priority(PQ(J))
end;
procedure PQ_Exchange(integer value I; integer value J);
begin
reference(Item) Temp;
Temp := PQ(I);
PQ(I) := PQ(J);
PQ(J) := Temp;
end;
A diversion - procedures without parameters
While writing this I got confused about the prototype for procedures without parameters; instead of
reference(Item) procedure PQ_First;
...
result := PQ_First;
I was writing
reference(Item) procedure PQ_First();
...
result := PQ_First();
and got what looked like garbage as the Item reference returned.
Trying to reproduce this with a simple example yielded the same problem:
Is the second example legal ALGOL W? I don’t think it is, based on the Stanford specification you need something in the parameter list - but there was no error from the compiler.
Running the program
Once that was fixed, compiling and running the program was simple.
ALGOL W definitely feels more polished and easy to use compared with ALGOL 60: the lack of stropping is a relief. It’s not the most powerful language - the restrictions on references stop it being much use for system programming - but I can see it would make a good choice as a teaching language. Apart from the issue I had above, the MTS compiler is much easier to use than the IBM ALGOL 60 one - I liked that it warns you if you use goto or pass by name.
Why didn’t ALGOL W become more popular? I think there were several factors
Only initially available on S/360 machines
Not as good performance as FORTRAN
Did not become the official replacement for ALGOL 60
Wirth did not work further on ALGOL W, moving on to Pascal, which does feel similar.
Next up, I will attempt to look at ALGOL 68 - if I can get it restored from the D4 tapes and running on D6.0.
Let’s look at ALGOL W in more detail, focusing how it differs from ALGOL 60.
Representation
ALGOL W is free format and case insensitive, though the convention was to have keywords in lower case and identifiers Like_This. Identifiers can be up to 255 characters long.
Keywords are reserved words so no stropping is required. A standard EBCDIC character set is used so there is no need for a different reference and hardware representation.
As well as the comment syntax from ALGOL 60, comments can be started with % and then terminated with either % or ;.
The final statement in a program or separately compiled unit (ie the last end) should end with a period.
% This is an ALGOL W program %
begin
integer Population_Count;
end.
New data types
As well as the existing types from ALGOL 60 such as real and integer, ALGOL W provides long real, complex, bit and proper string types:
begin
complex C;
bits B;
string(50) S;
c := 1 + 2I;
b := #0000010F;
s := "Hello, world";
end.
Bit values are padded to 32 bits. String variables have to be declared with their length, such as 50 above; if the length is not provided the default is 16.
New operators
div does integer division and rem yields the remainder after division. As well as the logical operators like and, there are also shl and shr for bitwise left and right shifts.
begin
write(#1 shl 2);
write(42 rem 20);
end.
The above will print #00000004 and 2.
Records and references
Records group together simple variables like a struct in C. References can point to records but not fundamental types. A reference can be initialised, at which point memory for the record is allocated. After initialisation, fields can be accessed by field(variable).
begin
record Person(integer Age; real Height; string(40) Name);
reference(Person) P, Q;
P := Person(30,, "N Wirth");
Q := Person;
Age(Q) := 42;
write(Name(P));
write(Age(Q));
end.
Note for the initialisation of P we leave Height uninitialised, and although memory for Q is allocated it is not initialised at all. This example will print “N Wirth” and 42.
References can be used to point at records but not fundamental types. null can be used to refer to an non-existent record. So a simple linked list could be defined as below, which will print 20.
begin
record List(integer Data; reference(List) Next);
reference(List) L;
L := List(10, null);
Next(L) := List(20, null);
write(Data(Next(L)));
end.
A reference can point to more than one type of record; which one can be determined at run time with the is operator.
begin
record A(real Aa);
record B(integer Bb);
reference(A, B) R, S;
R := A(3.0);
S := B(4);
S := R;
if S is A then write("Got an A") else write("Got a B");
end.
The above will print “Got an A”. I think there is no garbage collector, so the memory allocated for the B is leaked.
while and case
As well as the three types of for statements from ALGOL 60, ALGOL W has a while statement. The below will print 256.0
begin
real X;
X := 2.0;
while X < 100 do
begin
X := X * X;
end;
write(X);
end.
case allows switching by integer value; the below will print “Two”. Note there is no default case, so if J < 1 or > 4 there will be a runtime error.
begin
integer J;
string(10) Word;
J := 2;
Word := case J of ("One", "Two", "Three", "Four");
write(Word);
end.
Procedures
The syntax for procedures differs from ALGOL 60 as types and calling conventions are specified in the function header:
begin
real procedure Fn(real X; integer value Y);
begin
X * Y
end;
write(Fn(3.0, 2));
end.
The default calling convention, as used in the above, is by name, but *ALGOLW will give you a warning suggesting you use another convention instead.
Putting value after the type means pass by value. There is a new calling convention, result, which is for pass-out variables. value results allows both pass-in and pass-out without the side effects of pass by name.
begin
procedure P1(integer value A; integer result B; real value result C);
begin
A := 10;
B := A;
C := C + A
end;
integer A, B;
real C;
A := 1; B := 2; C := 3.0;
P1(A, B, C);
write(A, B, C);
end.
The above will display 1, 10, 13.
Input/Output and library
There’s an extensive input/output library that has been customised for MTS.
Basic input/output allows reading and writing each from a single channel. The below program will expect input formatted like this:
As discussed in the previous post, there were discussions on how to extend ALGOL after the experience of implementing ALGOL 60 on different systems. One such proposal was formulated by Niklaus Wirth and C A R Hoare. It did not get approved by the ALGOL committee, who chose what eventually became ALGOL 68 instead, so Wirth developed his proposal at Stanford and released it as ALGOL W.
ALGOL W overview
ALGOL W builds upon ALGOL 60 rather than making sweeping changes: its enhancements include
A simpler representation - no stropping of keywords
String, bits, complex and record types
References to records are allowed
The while keyword
A larger standard library, including input/output
ALGOL W on MTS
ALGOL W was originally implemented at Stanford in a high level assembly language called PL360, which I will look at later; this was augmented with S/360 assembler support routines at the University of Newcastle, UM and elsewhere to build the MTS compiler *ALGOLW.
It was the most popular of the ALGOL dialects on MTS, used for teaching programming fundamentals to students at several sites, and is well integrated with the operating system. The compiler features both a ‘compile, load and go’ mode suitable for learning the language and a traditional output to object deck option.
Prerequisites
No special installation instructions to get ALGOL W running - just do the standard D6.0 setup as described in this guide and then sign on as a regular user such as ST01.
Compiling using *ALGOLW
For compile, load and go mode just run *ALGOLW and type the desired program in directly. Finish it with $endfile and the system will compile it, print any errors and if OK will execute it once before returning you to the MTS prompt.
For object mode, run *ALGOLW with the command line option par=deck. It will read source from scards (by default *source* ie standard input) and will write object files to spunch (by default the temporary file -awload). The object file can then be $run directly without referencing any library.
Other *ALGOLW compilation parameters are listed in MTS Volume 16.
Hello world - compile, load and go
Here’s a simple program to print “Hello, world!” five times using the compile, load and go model. After I run *algolw I can type a compiler control statement at the = prompt but instead I enter begin, signaling that source code is being entered. *algolw prompts for the remainder of the program with :.
# $run *algolw
= begin
Compilation begins ...
: integer I;
: for I := 1 until 5 do
: write("Hello, world!");
:end.
:$endfile
Options (UN022) :- main, debug
(MAIN) 0.012 seconds to compile, size 416 bytes
Execution begins ...
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
0.001 seconds in execution
Hello world - object file
Here I use the two step process of compiling to an object file and then running it. Assume the source code is in file hello.alw.
# $list hello.alw
1 begin
2 % Hello World program for ALGOL W %
3 integer I;
4 for I := 1 until 5 do
5 begin
6 write("Hello, world!");
7 end
8 end.
# $run *algolw scards=hello.alw par=deck
Options (UN022) :- main, debug
Object program: "-AWLOAD"
(MAIN) 0.007 seconds to compile, size 416 bytes
# $run -awload
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
0.001 seconds in execution
Further information
MTS volume 16 contains a very readable description of the language, the compiler options and how it integrates with MTS.