LISP

From original post in Kodumaro.

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)

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

(+ . (1 2))

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

In R⁵RS (Scheme):

(define factorial
  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))

In Clojure:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

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

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

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

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

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)

Than on can take only how many elements one needs:

take 10 fib

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
  (λ (n)
    (*factorial* n 1)))

And one can evaluate it by calling:

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

The result is:

'((0 1) (1 1) (2 2) (3 6) (4 24) (5 120))