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
2. This list is processed by the
car (head) and
cdr (tail) functions:
(+ . (1 2))
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.
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))))))
(defn factorial [n] (reduce * (range 1 (inc n))))
Scheme has became a family itself, with a lotta different variations, not only different implementations, but different language variations too.
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:
- Lazy Racket:
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
It must exist an accumulator-driven function to make it possible, so the
(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.
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
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))
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))