DEV Community

loading...
Cover image for LISP

LISP

cacilhas profile image Arĥimedeς ℳontegasppα ℭacilhας ・3 min read

From original post in Kodumaro.

Made with secret alien technology

LISP is a specification by John McCarthy, that has started a whole programming language family since 1958. It’s based on λ-calculus, formal system from Alonzo Church’s work in 1930s, designed to deal with symbolic data instead of numeric, most imperative languages’ standard.

LISP means “list processing,” and list is the specification main structure. Every data – as the code itself – are represented as lists.

For instance, the sum of 1 and 2:

(+ 1 2)
Enter fullscreen mode Exit fullscreen mode

Which is a list of the elements +, 1, and 2. This list is processed by the car (head) and cdr (tail) functions:

(+ . (1 2))
Enter fullscreen mode Exit fullscreen mode

car and cdr are IBM 704 instructions, the system where LISP was formost developed. CAR means “Contents of the Address part of Register number” and CDR means “Contents of the Decrement part of Register number.”

The head represents a lambda function, and the tail the parameters. In this case, the function is '+, which returns the sum of the parameters.

The LISP family most important languages are Common Lisp, Emacs LISP, Scheme, and Clojure.

Let’s take a look at the factorial implementation in three LISP languages. First in Common Lisp:

(defun factorial (n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))
Enter fullscreen mode Exit fullscreen mode

In R⁵RS (Scheme):

(define factorial
  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))
Enter fullscreen mode Exit fullscreen mode

In Clojure:

(defn factorial [n]
  (reduce * (range 1 (inc n))))
Enter fullscreen mode Exit fullscreen mode

Scheme

Scheme has became a family itself, with a lotta different variations, not only different implementations, but different language variations too.

Its most important variations are Guile, MIT Scheme, and Racket (formerly PLT Scheme).

Racket is a full RAD platform, containing an IDE called DrRacket, WYSIWYG interface builder called MrEd Designer, and the PLT interpreter.

The interpreter supports R⁵RS, R⁶RS, PLT, Lazy Racket, and even C.

For example, the factorial in Racket:

!#racket

(define factorial
  (λ (n)
    [if (zero? n)
      1
      (* n (factorial (- n 1)))]))
Enter fullscreen mode Exit fullscreen mode

The hash-bang line tells which language Racket must deal with:

  • R⁵RS: #!r5rs
  • R⁶RS: #!r6rs
  • PLT: #!racket
  • Lazy Racket: #!lazy
  • C: #!planet jaymccarthy/c

Accumulators

Accumulator is a functional programming design pattern for dealing with stack overflow by taking advantage of tail-call optimisation (TCO).

Let’s take the factorial again: the step is defined as the current value times its predecessor’s factorial; the stop is zero’s factorial, which equals one.

n! = n × (n-1)!
0! = 1
Enter fullscreen mode Exit fullscreen mode

If you take a look at the PLT implementation above, you can see the last call id '*; in order to enable TCO, it should be factorial.

It must exist an accumulator-driven function to make it possible, so the factorial becomes:

(define factorial
  (λ (n)
    *factorial* n 1))
Enter fullscreen mode Exit fullscreen mode

The accumulator-driven version (*factorial*) must receive the original parameter and the accumulator, returning the accumulator when it stops:

(define *factorial*
  (λ (n acc)
    [if (zero? n)
      acc
      (*factorial* (- n 1) (* acc n))]))
Enter fullscreen mode Exit fullscreen mode

Note that now the last call is *factorial*, enabling the TCO.

Lazy evaluation

The most efficient approach to deal with huge calculated data volumes is lazy evaluation, or call-by-need. Haskell, for instance, just evaluates its calls by demand, which enables to build infinite lists:

fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)
Enter fullscreen mode Exit fullscreen mode

Than on can take only how many elements one needs:

take 10 fib
Enter fullscreen mode Exit fullscreen mode

Promises

Lazy Racket uses promises to delay the evaluation, in a similar taste as Haskell.

The evaluation of a lazy function is made by the function '!!.

So the lazy factorial is:

#!lazy

(provide factorial)

(define *factorial*
  (λ (n acc)
    [if (zero? n)
      acc
      (*factorial* (- n 1) (* acc n))]))

(define factorial
  (*factorial* n 1))
Enter fullscreen mode Exit fullscreen mode

And one can evaluate it by calling:

(!! [map (λ (n) `(,n ,(factorial n))) '(0 1 2 3 4 5)])
Enter fullscreen mode Exit fullscreen mode

The result is:

'((0 1) (1 1) (2 2) (3 6) (4 24) (5 120))
Enter fullscreen mode Exit fullscreen mode

Discussion

pic
Editor guide
Collapse
jcubic profile image
Jakub T. Jankiewicz

Thanks for the post, this is great (+ . (1 2)) it evaluates in lisp interpreter, didn't realized that you can evaluate something like (+ . (1 . (3 . nil))), even that I knew that this is how lists are created.

Collapse
cacilhas profile image
Arĥimedeς ℳontegasppα ℭacilhας Author

Exactly. It’s called cons, but I had no intention in going into that deep.