LISP: back to the future (a tribute to 60th anniversary)

01 Jun, 2018

8 min read

Exactly 60 years ago a new language was born, which on its own may be considered the greatest finding in computer science since the invention of the first computer. This language was LISP, the most innovative and creative language ever designed and unfortunately undeservingly abandoned by the mainstream programming community today. In this article, I will try to show you, in short, the history of this language and what makes it different.

CONTENTS

By the way, why language is ever important? It may be not so obvious if you are experienced in mainstream languages only, such as Java, C#, JavaScript, or Python. Generally, there is no significant difference between these languages, since they all belong to one family and learning even one of them allows you to understand and learn other ones easily. In fact, a language is highly important because it determines what you can say, while being used to, it will determine your way of thinking.

Origins

The story of LISP started in 1958 although some key ideas were developed earlier through 1956 and 1957. The language itself targeted relevant Artificial Intelligence problems and was funded as a part of the project called Advice Taker. Development was carried out by the Artificial Intelligence group at M.I.T. The key person in this research and development was John McCarthy famous for being the author of the term Artificial Intelligence itself. Another not less famous figure in his team was AI pioneer and futurist Marvin Minsky. The first interpreter was implemented by Steve Russell who is known as the author of one of the earliest video games called Spacewar!

A distinguishable idea was to represent processing information in a form of lists, which seems still relevant today, and the same idea gave the language the name LISP (for List Processing). To represent such lists, McCarthy came up with a quite simple notation named s-expressions (for “symbolic expression”) consisting of ( · ) and an inﬁnite set of atomic symbols:

AB
 (A · B)
 ((AB · C) · D)
 (A·((B ·(C · NIL)) ·(D · NIL)))

The last S-expression corresponds to the list structure represented on image 1.

List structure corresponding to s-expression (A•((B •(C • NIL)) •(D • NIL)))

Image 1. List structure corresponding to s-expression A·((B ·(C · NIL)) ·(D · NIL)))

Initially, S-expressions were supposed to be used for data representation only and expected to be manipulated by another Fortran-inspired notation called M-expressions:

car[x]
 car[cons[(A · B);x]]

Very soon it appeared that there was no need in a separate notation for program logic, and S-expressions could serve that goal well if assumed that the very first element of the S-expression stood for a function applied to the rest of the list elements. Therefore, there is no significant difference in LISP between data and code, they are just interchangeable. This simple syntax unintentionally made LISP a very powerful language, having no analogous until today.

(print (string-join (list “Hello” “LISP”)))

Innovations

Even though homoiconic syntax was the key innovation that still distinguishes LISP from all other languages, it featured even more astonishing features we cannot imagine modern programming without and some exotic ones as well.

IF Statement

LISP was the very first language having the IF statement in our modern understanding. Fortran’s analog at the date was rather conditional GOTO.

; Example in Scheme
 (define a 12)
 (if (= (mod a 2) 0)
  (print “even”)
  (print “odd”))

Garbage collection

It’s hard to imagine a modern language without this feature, but 60 years ago it was a real breakthrough. Although, at the same time, this feature limited the spread of language significantly because of a much higher demand for computation power.

Functional programming

LISP featured functions as a first-class datatype as well as their definition in the form of λ-expressions. This was the birth of a new computing paradigm, which in-fact became mainstream in the last ten years. It is hard to believe, but it is much older than Object-Oriented or even Structural programming.

; Example in Racket
 (define numbers (list 1 2 3 4 5 6 7))
 (define even-numbers
 (filter (λ (x) (= (modulo x2)0))numbers))

Metaprogramming

That’s what homoiconic syntax stands for. Having no difference between code and data allows your program to compose other programs. It sounds really powerful, and it is so.

; Example in Clojure
 (defn drive-to-home [] “driving to home”)
 (defn drive-to-work [] “driving to work”)
 (defn drive-to-garage [] “driving to garage”)
 (defn recharge [] “recharging”)
; Forming the driving program
 (defn get-driving-program [] 
 (list drive-to-home drive-to-work recharge drive-to-garage))
; Evaluating the driving program
 (map #(println(%))
 (map eval (get-driving-program)))

Macros

Macros in LISP are quite unique compared to macros in C & C++ in the sense that they are functions that can generate syntax constructs depending on their input. Those who mastered LISP macro can enrich their language with the missing features or create new Domain-Specific Languages. For instance, the following code adds while statement into the language (Racket) that does not have it by default:

; while macros definition
 (define-syntax while
 (syntax-rules (do)
 [(while cond do body …)
 (let loop ()
 (when cond  body …
  (loop)))]))
; while macros application
 (define x 10)
 (while (> x 0) do
 (displayln x)
 (set! x (– x 1))) ; prints 10 9 8 7 6 5 4 3 2 1

Continuations

Continuations in LISP are as well not just an approach of passing callbacks to asynchronous functions or continuation-passing style, they are a distinct feature that allows you to save the execution state of your program and get back to it later in time.

; Example in Racket (taken from Wikipedia)
 (define the-continuation #f)
 (define (test)
 (let ((i 0))
 ; call/cc calls its first function argument, passing
 ; a continuation variable representing this point in
 ; the program as the argument to that function.
 ; In this case, the function argument assigns that
 ; continuation to the variable the-continuation.
 (call/cc (lambda (k) (set! the-continuation k)))
 ; The next time the-continuation is called, we start here.
 (set! i (+ i 1)) 
 i))
(test) ; 1
 (the-continuation) ; 2
 (the-continuation) ; 3
 ; store the current continuation
 ; (which will print 4 next) away
 (define another-continuation the-continuation)
 ; reset the-continuation
 (test)< ; 1
 (the-continuation) ; 2
 ; use the previously stored continuation
 (another-continuation) ; 4

Multiple dynamic dispatch (aka Multimethods)

Multimethods allow you to have different function implementations based on the type of incoming arguments.

; Example in Racket
 (require multimethod) 
 (struct asteroid ())
 (struct space-ship ())
(define-generic (collide a b))
 (define-instance (
 (collide asteroid space-ship) a b)
 (println “Asteroid collided with the space ship”))
 (define-instance (
  (collide space-ship asteroid) a b)
   (println “Space ship collided with the asteroid”))

This feature may seem similar to simple methods overloading, but it is not since the dispatch of the multimethod is determined at runtime. Multimethods exist in C# as well (through dynamic keyword), but still missing in C++, Java, and many other languages, forcing programmers to implement a visitor pattern to achieve the same behavior.

Recursion

The very nature of the LISP is recursive like its distinctive list structures. Even the original McCarthy’s article that introduced LISP to the world was called “Recursive Functions of Symbolic Expressions and Their Computation by Machine”. Does your primary language support recursion well? Perhaps it supports tail call optimization, but what about mutual recursion? I bet, implementing this code in any mainstream language will fail with stack overflow exception:

; Example in Racket
 (define (r1 i)
 (if (< i 0)
 1
 (r2 (– i 1))))
 (define (r2 i)
 (if (< i 0)
 1
   (r1 (– i 1))))(r1 1000000)

Modern LISP

Even though you will not find LISP among popular, mainstream languages, be sure it is not dead. Like a secret knowledge of the past, LISP survived in an academic environment and among enlightened ones. Currently, there are at least 3 well-supported dialects of LISP:

Scheme (Racket in particular) – the weapon of choice in an academic environment;
Common LISP – standardized industry version;
Clojure – modern LISP implementation for JVM, CLR, and JS environment.

The last dialect was created by Rich Hickey who is responsible for a new wave of interest to the language. Today, the popularity of Clojure has grown high enough to make it possible to implement full-stack applications solidly in this language:

Clojure Script – for frontend;
Clojure – for backend;
Datomic (NoSQL database written in Clojure) – for the persistence layer.

LISP: Full-Clojure Stack

Image 2. Full-Clojure stack

Conclusion

I hope reading this article to the end ignited in you at least a small spark of interest to a very beautiful language called LISP. Even being initially developed 60 years ago, I believe, it is still overpowering all the mainstream languages in its features, flexibility, and simplicity. It may seem strange why being so nice and powerful LISP isn’t popular nowadays. There is a couple of reasons for that. First of all, in the 70s LISP was too demanding for common hardware to become a widely used language. Secondly, there were too many dialects of the same language and having no solid ecosystem is hard to build a solid community around it. And finally, remember that there is no real correlation between popularity and quality. Any language, after getting used to it, starts to determine the mindset of the programmers, which is hard to change.