In this series we’ll look at PL/I, or Programming Language 1, an ambitious multi-purpose language developed by IBM.
PL/I overview
PL/I was intended to be a programming language for all users - scientific, business and systems. It was originally developed by IBM in the mid ’60s and spread to other mainframes, Multics and DEC systems. A subset of the language was used to create CP/M and IBM produced a version for OS/2 on PCs that was competitive with C. A standardised specification was produced by ECMA and ANSI from the early ’70s. Although it gained some popularity (it was even used as a teaching language at some universities) it never really took off in any of the fields it was intended for.
Language-wise, it is a procedural imperative language drawing inspiration from FORTRAN, COBOL and ALGOL. Due to its intended wide coverage, it is a very large language with a number of interesting features, some of which were incorporated into later languages such as C.
PL/I on MTS
There were three PL/I environments originally available on MTS:
*PL1F was derived from the IBM OS/360 F version 5 compiler with modifications for MTS. This is the only version available on the D6.0 tapes today and the one we will look at here. The MTS documentation refers to this as *PL1 but this name is not available; use *PL1F.
*PL1OPT was the IBM optimising compiler for PL/I and is not available due to copyright reasons. It took many of the compiler optimisation techniques developed for the FORTRAN H compiler and also offered a checkout facility for improved debugging.
*PLC was a load-and-go processor developer at Cornell. It had the unique feature that any input would compile (but maybe not produce the desired results) due to automatic substitution of syntax errors. A binary version exists but was not distributed with the D6.0 version of MTS due to copyright concerns. It may be available in future versions; see this discussion at the MTS Archive for further information.
There are also a number of utility programs for PL/I *PL1SCAN does a quick syntax check of a program and *PL1TIDY formats a PL/I source file.
Prerequisites
No special installation instructions to get PL/I 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 *PLIF
*PLIF will read source from scards (by default *source* ie standard input) and will write object files to spunch. Unlike some other MTS compilers you need to provide a filename for spunch as there is no default. You should destroy or empty the contents of the object file before recompiling.
Other compilation parameters are listed in MTS Volume 7.
To run PL/I programs you need to concatenate the runtime library *PL1LIB with the object file.
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.pl1.
# $list hello.pl1
1 /* Hello world program in PL/I */
2 HELLO: PROCEDURE OPTIONS(MAIN);
3 DECLARE I FIXED BINARY(16);
4 DO I = 1 TO 5;
5 PUT FILE (SCARDS) LIST('Hello, world!');
6 PUT FILE (SCARDS) SKIP;
7 END HELLO;
# $destroy -load
File "-LOAD" has been destroyed.
# $run *pl1f scards=hello.pl1 spunch=-load
# Execution begins 12:18:31
PROCEDURE HELLO: SYNTAX CHECK COMPLETED. COMPILATION CONTINUES.
NO ERRORS OR WARNINGS DETECTED.
# Execution terminated 12:18:31 T=0.087
# $run -load+*pl1lib
# Execution begins 12:18:34
'Hello, world!'
'Hello, world!'
'Hello, world!'
'Hello, world!'
'Hello, world!'
# Execution terminated 12:18:34 T=0.002
Further information
MTS Volume 7 describes the PL/I compilers available on MTS.
The original IBM documentation for the PL/I language and PL/I F compiler can be found at bitsavers.
One of the reasons LISP did not become more popular for scientific computing was the perception that it was slower than FORTRAN. In this post I will compare the performance of the LISP and FORTRAN implementations on MTS using a simple problem.
The problem and some caveats
We’ll use the finding emirp primes problem introduced in the FORTRAN posts on this blog as the subject. To make it simpler we will just look at the third test, finding the 10,000th emirp.
So some caveats before we start. Benchmarks are notoriously difficult to get right and this is only a single sample. I’m not an expert at optimising LISP or FORTRAN so there may well be better ways of implementing this. Finally, the UTILISP implementation is from the 1980s, MTS LISP is from the 1970s and the FORTRAN G and H compilers date from at least the 1960s so this is not a historically accurate recreation.
Having said that, it’ll be interesting to see how they stack up, so let’s start.
FORTRAN
We’ll use the source code for the FORTRAN emirp implementation discussed before, taking out the first and second test.
We compile without optimisations first (ie using FORTRAN G) and then try again with FORTRAN H. The results look like this:
# run *ftn scards=emirp3.f
# Execution begins 11:39:08
No errors in PRIME
No errors in REVRSE
No errors in EMIRP
No errors in SHOW
No errors in TEST3
No errors in MAIN
# Execution terminated 11:39:08 T=0.045
# run -load
# Execution begins 11:39:10
948349
# Execution terminated 11:39:19 T=9.05
#
# $run *ftn scards=emirp3.f par=opt=h
# Execution begins 11:39:49
**** No errors for PRIME **** SAT MAY 09/15 11:39:49
**** No errors for REVRSE **** SAT MAY 09/15 11:39:49
**** No errors for EMIRP **** SAT MAY 09/15 11:39:49
**** No errors for SHOW **** SAT MAY 09/15 11:39:49
**** No errors for TEST3 **** SAT MAY 09/15 11:39:49
**** No errors for MAIN **** SAT MAY 09/15 11:39:49
# Execution terminated 11:39:49 T=0.074
# run -load
# Execution begins 11:39:54
948349
# Execution terminated 11:39:59 T=4.281
So 9.05s for FORTRAN G and 4.28s for FORTRAN H.
MTS LISP
Let’s try the original MTS LISP first. It’s fairly easy to translate using the (GO) form to do looping.
;; Checks if n is prime using a simple division test(DEFUN PRIME-P (N)
(COND
;; Deal with numbers <= 3 ((LESS N 2) NIL)
((LESS N 4) T)
;; Check if divisible by 2 or 3 ((EQUAL (REMAIN N 2) 0) NIL)
((EQUAL (REMAIN N 3) 0) NIL)
;; See if divisible by 5, 7, ..., up to approx sqrt(n) (T (PROG (I RESULT)
(SETQ I 5)
A (SETQ RESULT (COND ((GREATER (TIMES I I) N) 'PRIME)
((EQUAL (REMAIN N I) 0) 'NOT-PRIME)
(T (SETQ I (ADD I 2)) NIL)))
(COND ((NOT RESULT) (GO A)))
(EQ RESULT 'PRIME)))))
;; Return a number that has the reversed digits in n(DEFUN REVERSE-DIGITS (N)
(PROG (REVERSED)
(SETQ REVERSED 0)
;; Take last digit from n and append to reversed (PROG ()
B (SETQ REVERSED (TIMES REVERSED 10))
(SETQ REVERSED (ADD REVERSED (REMAIN N 10)))
(SETQ N (IDIVIDE N 10))
(COND ((GREATER N 0) (GO B))))
;; CAR needed to evaluate REVERSED otherwise PROG will return;; the symbol REVERSED (CAR REVERSED)))
;; Check if a number is an emirp, ie both it and its reversed digits;; are prime.(DEFUN EMIRP-P (N)
(PROG (REVERSED)
(SETQ REVERSED (REVERSE-DIGITS N))
(AND (NOT (EQUAL N REVERSED)) (PRIME-P N) (PRIME-P REVERSED))))
(DEFUN EMIRP-10K ()
(PROG (N COUNT LAST)
(SETQ N 0)
(SETQ COUNT 0)
(SETQ LAST 0)
C (COND ((EMIRP-P N)
(SETQ COUNT (ADD COUNT 1)) (SETQ LAST N)))
(SETQ N (ADD N 1))
(COND ((LESS COUNT 10000) (GO C)))
(CAR LAST)))
(EMIRP-10K)
(STOP)
OK, so we are down from 348s to 72s (the compilation itself takes less than 0.5s). Not bad, but still 17 times slower than FORTRAN H.
UTILISP
Let’s see how UTILISP compares. We do need to change the program in quite a few places to match the different built in functions (eg + instead of ADD) but at least we can now use the do macro to create more expressive loops.
;; Checks if n is prime using a simple division test(defun prime-p (n)
(cond
;; Deal with numbers <= 3 ((<= n 1) nil)
((<= n 3) t)
;; Check if divisible by 2 or 3 ((= (remainder n 2) 0) nil)
((= (remainder n 3) 0) nil)
;; See if divisible by 5, 7, ..., up to approx sqrt(n) (t (do ((i 5 (+ i 2)) (result nil))
(result (eq result 'prime))
(setq result (cond ((> (* i i) n) 'prime)
((= (remainder n i) 0) 'not-prime)
(tnil)))))))
;; Return a number that has the reversed digits in n(defun reverse-digits (n)
(do ((reversed 0) (m n (// m 10)))
((< m 1) reversed)
;; Take last digit from n and append to reversed (setq reversed (* reversed 10))
(setq reversed (+ reversed (remainder m 10)))))
;; Check if a number is an emirp, ie both it and its reversed digits;; are prime.(defun emirp-p (n)
(let ((reversed (reverse-digits n)))
(and (neq n reversed) (prime-p n) (prime-p reversed))))
;; Return the 10,000th emirp(defun emirp-10k ()
(do ((n 0 (+ n 1)) (count0) (last0))
((eqcount10000) last)
(cond ((emirp-p n) (setqcount (+count1)) (setqlast n)))))
;; Run the test(print (emirp-10k))
(quit)
after the definitions and then adding the fix parameter to the command line to reserve memory for the compiler (again compilation takes less than 0.5s of the total):
Much better - 3 times faster than the MTS LISP compiled version but 7 times slower still than FORTRAN H.
Summary of results and final thoughts
Program
Time (s)
FORTRAN G
9.05
FORTRAN H
4.28
MTS LISP interpreted
347.52
MTS LISP compiled
72.35
UTILISP interpreted
208.35
UTILISP compiled
27.79
Compiled UTILISP puts up a good showing and it’s definitely usable for light numerical tasks but in the end FORTRAN wins on pure performance. The UTILISP implementation is much faster than MTS LISP for both interpreted and compiled code, which you’d expect given the amount of knowledge creating fast LISP implementations that was built up between the release of the two programs.
Another factor evident from this test was the lack of LISP standardisation (pre-Common Lisp) makes porting programs between implementations a chore, whereas FORTRAN was relatively standardised.
Any suggestions for optimising the code? Please let me know in the comments.
In the next post, in a couple of weeks, we’ll look at PL/1.
Further information
Full source code for the programs shown here is on github.
Let’s look at some of the language features in UTILISP compared to the original MTS LISP.
Strings
UTILISP brings support for strings, which can also be treated as a sequence of bytes that can be accessed independently.
> (setq s "hello world")
"hello world"
> (string-length s)
11
> (sref s 1)
133
> (sset s 1 134)
134
> s
"hfllo world"
> (string-search "world" s)
6
> (cutout s 0 2)
34950
In the last expression, we take the first two bytes of s and extract it as an integer. There’s also bref and bset which can be used to access individual bits in a string.
Numbers
UTILISP has both fixed and floating point numbers; arithmetic operators for floating point numbers have $ at the end of the keyword to distinguish them.
> (setq f 0.0)
+0.0000000?+00
> (setq i 0)
0
> (0= i)
T
> (0= f)
@@@ ILLEGAL ARGUMENT TYPE
+0.0000000?+00 -- C#/0=
> (0=$ f)
T
Vectors and references
Vectors are implemented as a primitive data type: they are created with vector and addressed with vref and vset. Vectors can contain any LISP data types. Here we create a four element vector, initially filled with the number 42 in each slot.
> (setq v (vector 4 42))
V#-8057044
> v
V#-8057044
> (vector-length v)
4
> (vref v 0)
42
> (vset v 0 43)
43
> (vset v 1 "hello")
"hello"
You can set references, which are pointers to elements of the vector which can then be dereferenced or updated through the reference.
> (setq r (reference v 3))
R#-8057028
> (deref r)
42
> (setref r 99)
99
> (vref v 3)
99
mapv can be used to operate on each element of a vector; it passes a reference to each element.
There is also a hash function that could be used to build efficient lookup tables using vectors.
> (hash 32)
32
> (hash "hello")
373277
Macros
UTILISP has macro support similar to modern LISPs, with selective quoting and evaluation via backtick and comma. Here we define a macro that will change a variable to nil if it is currently t.
> (defmacro t-to-nil (v)
`(cond ((eq ,v t) (setq ,v nil))))
T-TO-NIL
> (setq a 1)
1
> (setq b t)
T
> (t-to-nil a)
NIL
> (t-to-nil b)
NIL
> a
1
> b
NIL
Scope and closures
UTILISP has dynamic scope and no lexical-let. There also seems to be no funarg implementation although this was available in Maclisp. It is possible to mimic closures with macros:
Let’s look at the other LISP implementation on MTS, University of Tokyo Lisp or UTILISP.
UTILISP overview
UTILISP was originally developed at the University of Tokyo in 1980 for S/360 compatible mainframes. It was worked on there by students and staff for the following decade, moving to 68000 and SPARC processors along the way. It was distributed to several sites in Japan and the rest of the world and was used for AI research. One reason for its popularity was the speed of its compiled code.
Language wise, it is similar to Maclisp; it uses dynamic scope and has macro facilities.
UTILISP on MTS
UTILISP was made available on MTS at UM in 1984 as *UTILISP: it has some light customisation to make it work with MTS and an initial version of an MTS Volume was produced based on the original UTILISP documentation.
One key program produced using UTILISP was a Prolog implementation, PROLOG/KR; this is also available on MTS and I will look at this later.
Prerequisites
No special installation instructions to get UTILISP 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 *UTILISP
UTILISP is an interpreted environment. Running *UTILISP 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 0 parameter to *UTILISP; 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 (quit).
There is an editor available via (edit fn) but it’s easier to do this outside of UTILISP.
One improvement over *LISP is that there is online help, though not using the MTS help system: as an example, type (help car) to view a brief description of how the car function works.
Like *LISP, it’s possible to compile expressions to machine code with (compile fn); note that you have to provide some fixed space memory to UTILISP at startup by setting FIX, eg with the command $run *utilisp par=fix=100. There does not seem to be a way to write the current system state or compiled functions back to disk, however.
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.ul.
# $list hello.ul
1 ;; Hello world program for UTILISP
2 (do ((i 0 (1+ i)))
3 ((= i 5))
4 (print "Hello, world!"))
5 (quit)
# $run *utilisp 0=hello.ul
# Execution begins 12:01:48
"Hello, world!"
"Hello, world!"
"Hello, world!"
"Hello, world!"
"Hello, world!"
# Execution terminated 12:01:48 T=0.035
Further information
MTS Volume 22 describes the UTILISP implementation and how to run it on MTS.
For this sample program we will simulate a four bit adder chip by constructing it from a series of AND, OR and NOT gates. See Rosetta Code for full details.
Constructing the solution
LISP provides AND, OR and NOT functions and we can use T and NIL to represent true and false. First task is to make an XOR gate:
(DEFUN XOR (A B)
(OR (AND A (NOT B))
(AND B (NOT A))))
Next we make a half-bit and single bit adder. These return a result and a carry bit which can be fed into the next stage of the full adder. We create a cons cell containing the result and carry bit for the return type.
(DEFUN HALF-ADDER (A B)
(CONS (XOR A B) (AND A B)))
(DEFUN ADDER (A B C0)
(PROG (S1 S2)
(SETQ S1 (HALF-ADDER C0 A))
(SETQ S2 (HALF-ADDER (CAR S1) B))
(CONS (CAR S2) (OR (CDR S1) (CDR S2)))))
We then connect the adders together to form a four bit adder. As this version of LISP’s NTH returns the remainder of the list from the given position, we need a convenience function BIT to access individual values.
(DEFUN BIT (L N)
(CAR (NTH L (ADD1 N))))
(DEFUN ADDER-4 (A B)
(PROG (X1 X2 X3 X4)
(SETQ X1 (ADDER (BIT A 3) (BIT B 3) NIL))
(SETQ X2 (ADDER (BIT A 2) (BIT B 2) (CDR X1)))
(SETQ X3 (ADDER (BIT A 1) (BIT B 1) (CDR X2)))
(SETQ X4 (ADDER (BIT A 0) (BIT B 0) (CDR X3)))
(CONS (MAPCAR 'CAR (LIST X4 X3 X2 X1)) (CDR X4))))
The adder takes as input, and returns, a list of binary values, eg (NIL T NIL T) for 5. It would be convenient to have a function that can convert an integer into such a list: we can do this recursively.
(DEFUN DEC-BIN (X)
(PROG (BIT)
(SETQ BIT (NOT (ZERO (LAND X 1))))
(COND ((LESS X 2) (LIST BIT))
(T (APPEND (DEC-BIN (SHIFT X -1)) BIT)))))
;; Pad binary list L to length N by adding NILs in front
(DEFUN PAD (N L)
(COND ((LESS (LENGTH L) N)
(REPEAT '(SETQ L (CONS NIL L)) (SUB N (LENGTH L))))
(T L)))
Finally, we write a test function to take two integers (assuming each is between 0 and 15) and add them, printing the sum:
(DEFUN TEST-ADDER-4 (A B)
(PROG (AB BB RES)
(SETQ AB (PAD 4 (DEC-BIN A)))
(SETQ BB (PAD 4 (DEC-BIN B)))
(SETQ RES (ADDER-4 AB BB))
(PRIN1 AB) (PRIN1 '+) (PRIN1 BB)
(PRIN1 '=) (PRIN1 (CAR RES))
(PRIN1 'carry) (PRIN1 (CDR RES))
(TERPRI)))
(TEST-ADDER-4 3 2)
Here PRIN1 prints a single item and a space; TERPRI ends the current line.
Getting it working
The LISP REPL helps here, as you can revise functions and test them until they work; this was fairly simple to get working, though DEC-BIN was tricky until I separated out PAD into its own function. I struggled with the LISP editor and found it easier to apply changes back to the file using *EDIT as each was done.
Let’s see it in action:
# $run *lisp scards=4bitadd.l
# Execution begins 20:02:38
WELCOME TO LISP/MTS
> XOR
> HALF-ADDER
> ADDER
> BIT
> ADDER-4
> DEC-BIN
> PAD
> TEST-ADDER-4
> (NIL NIL T T) + (NIL NIL T NIL) = (NIL T NIL T) carry NIL
> NIL
# Execution terminated 20:02:38 T=0.007
Final thoughts on MTS LISP
I like Lisp a lot and even though this is a very basic Lisp compared to Common Lisp (or even Emacs Lisp) it still feels a lot higher level than the ALGOL/FORTRAN family of languages we have seen so far. One issue that we don’t have, as we are running on fast modern computers, is speed: LISP was much slower than FORTRAN for numeric work and garbage collection was very slow.
In the next post, which will be in mid-April, we’ll look at the other LISP in MTS - UTILISP.