lisp

4 posts

The great FORTRAN-LISP shootout

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)

We'll first execute it through the interpreter:

# $run *lisp scards=emirp.l
# Execution begins   12:41:27
      WELCOME TO LISP/MTS
 >    PRIME-P
 >    REVERSE-DIGITS
 >    EMIRP-P
 >    EMIRP-10K
* GC: COLLECTED 23370 CELLS
...
* GC: COLLECTED 23370 CELLS
>    948349
# Execution terminated   12:47:15  T=347.517 

Next we'll compile the functions. Add (COMPILE PRIME-P) and so on for all the functions and rerun

# $run *lisp scards=emirp.l
     WELCOME TO LISP/MTS
>    PRIME-P
>    REVERSE-DIGITS
>    EMIRP-P
>    EMIRP-10K
* COMPILE        04-17-79 RESTORED
>    (PRIME-P)
>    (REVERSE-DIGITS)
>    (EMIRP-P)
>    (EMIRP-10K)
* GC: COLLECTED 23370 CELLS
...
* GC: COLLECTED 23370 CELLS
>    948349
# Execution terminated   12:56:39  T=72.347 

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)
                             (t nil)))))))


;; 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)) (count 0) (last 0))
      ((eq count 10000) last)
      (cond ((emirp-p n) (setq count (+ count 1)) (setq last n)))))

;; Run the test
(print (emirp-10k))
(quit)

And let's run it through the interpreter.

# $run *utilisp 0=emirp.ul
# Execution begins   18:18:02 
  948349
# Execution terminated   18:21:30  T=208.35 

So that's 40% quicker than the MTS LISP interpreted version. Let's try compiling the forms, which we can just do by putting

(compile prime-p reverse-digits emirp-p emirp-10k)

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):

$ run *utilisp 0=emirp.ul par=fix=100
# Execution begins   18:32:27 
  ; Loading Utilisp Compiler System Version(82-11-09)
  948349
# Execution terminated   18:32:54  T=27.788 

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.

LISP - 4 bit adder

The problem

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.

Further information

Full source code for this program is on github.

Comparing MTS LISP to modern Lisps

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:

* (SETQ GREETING '"Hello, world!")
>    Hello, world!
* (PRINT GREETING)
>    Hello, world!

Arrays are simulated using functions: for a 2x2 array:

* (DEFINE (A ARRAY (2 2)))
>    A
* (SETA (A 1 2) 42)
>    42
* (PRINT (A 1 2))
>    42

Standard functions

Many familiar Lisp functions for list manipulation, arithmetic and control flow are available in this version; a brief sample:

* (SETQ L1 (LIST 1 2 (SUB 10 7)))
>       (1 2 3)
* (SETQ L2 (LIST 1 2 (SHIFT 2 2)))
>       (1 2 8)
* (CADR L2)
>       2
* (RPLACA L2 42)
>       (42 2 8)
* (DELETE 8 L2)
>       (42 2)
* L2
>       (42 2)
* (MAPC 'PRINT L2)
>       42
*       2
>       NIL

Functions and scope

As expected, you can use LAMBDA to define an anonymous function and DEFUN to attach a lambda function to an atom

* ((LAMBDA (A) (ADD A 2)) 40)
>       42

* (DEFUN FACTORIAL (N) (COND ((LESS N 2) 1)
*                            (T (TIMES N (FACTORIAL (SUB1 N))))))
>       FACTORIAL
* (FACTORIAL 5)
>       120

*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.

* (SETQ X 42)
>       42
* (DEFUN GETX () X)
>       GETX
* (GETX)
>       42
* (PROG (X) (SETQ X 3) (GETX))
>       3
* (GETX)
>       42

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.

LISP - Introduction

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.

# $list hello.l

       1      ; LISP Hello World program
       2     (REPEAT '(PRINT '"Hello, world!") 5)
       3     (STOP)
# $run *lisp scards=hello.l
# Execution begins   20:54:36 
     WELCOME TO LISP/MTS
>    Hello, world!
>    Hello, world!
>    Hello, world!
>    Hello, world!
>    Hello, world!
>    Hello, world!
# Execution terminated   20:54:36  T=0.002 

Note the message is actually printed six times, as the value of the REPEAT expression is printed by the interpreter.

Further information

MTS Volume 8 describes the LISP language and its implementation in MTS *LISP.

The original LISP 1.5 reference from MIT gives a more formal description of the original version of the language.

John McCarthy's paper on the History of Lisp gives context on how and why LISP came about.