Search notes:

Lisp

The name Lisp, which originally was spelled with upper case letters (LISP), derives from LISt Processor.

The source code of a Lisp program consists of lists.

In Lisp, everything is either

an atom, or
a list

A list contains atoms or other lists. These elements are put within parenthesis and separated with commas.

Atoms are literals like 42, "Hello World" or symbols (names of variables or functions).

A symbol is a string of (latin?) letters and digits.

Unless instructed otherwise, a list triggers a function call, the first argument being the name of the function.

S-expressions and lists

S-expression stands for symbolic expression and is sometimes abbreviated as sexpr.

An S-expression is either

an atom, or
(x . y) where both x and y are S-expressions.

A list is similarly defined as

an empty list (denoted as ()), or
a cons cell that consists of two elements, both of which are lists.

(a b c) is just a short hand notation for (a . (b . (z . NIL)))

A list may contain code or data.

NIL is the special end-of-list object, sometimes also expressed as (). (In Scheme, NIL seems to be represented as nil).

See also M-expressions which stands for meta-expression.

cons (data structure)

A cons is a data structure that contains two values.

The cons' first value is its car, the second value its *cdr).

cons (function)

(cons A B) is the function to create a cons (denoted with the S-expression (x . y)?).

> (cons 1 2)
(1 . 2)

car / cdr (functions)

car evaluates to the first element in a list.

> (car (cons (cons 1 2) (cons 3 4)))
(1 . 2)

cdr evaluates to the second element in a list (in the liturature typically referred to as «the rest»)

> (cdr (cons (cons 1 2) (cons (cons 3 4) 5)))
((3 . 4) . 5)

list (data structure)

A cons is also a list if its cdr is

nil or
a list

Examples of lists

The cdr is nil:

(cons 3 nil)

The cdr of the outer cons is a list (as per previous example):

(cons 2 (cons 3 nil))

Because the definition of a list is recursive, this can be extended ad infinitum:

(cons 1 (cons 2 (cons 3 nil)))

(list …)

list is the function to create lists

> (list 1 2 3 4 5)
(1 2 3 4 5)

The same list can also be created with a sequence of (cons…) functions. Note the nil in the last (cons 5 nil):

> (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil)))))
(1 2 3 4 5)

Representing cons

A cons is represented with with a pair of parentheses that contains its values, that are themselves separated by a dot.

A simple cons:

> (cons 1 2)
(1 . 2)

A cons whose car is a cons:

> (cons (cons 1 2) 3)
((1 . 2) . 3)

The dot and the parenthesis around the cdr are omitted when its cdr is

a cons-cell, or
nil

There is no such rule that is dependent on cons' car.

There are nine combination how cons-cell can be constructed:

atom | atom

> (cons 1 2)
(1 . 2)

atom | cons

> (cons 1 (cons 2 3))
(1 2 . 3)

atom | nil

> (cons 1 nil)
(1)

cons | atom

> (cons (cons 1 2) 3)
((1 . 2) . 3)

cons | cons

> (cons (cons 1 2) (cons 3 4))
((1 . 2) 3 . 4)

cons | nil

> (cons (cons 1 2) nil)
((1 . 2))

nil | atom

> (cons nil 1)
(() . 1)

nil | cons

> (cons nil (cons 1 2))
(() 1 . 2)

nil | nil

> (cons nil nil)
(())

(cadr X)

(cadr X) is an abreviation («syntactic sugar) for (car (cdr X)):

> (car (cdr (list 1 2 3 4)))
2

Same same, but shorter:

> (cadr (list 1 2 3 4))
2

Quoting lists

In order to prevent the evaluation of a list, the list must be quoted. This is possible with either a single apostrophe or the pseudo function quote:

> (+ 1 2 3)
6

> `(+ 1 2 3)
(+ 1 2 3)

> (quote (+ 1 2 3))
(+ 1 2 3)

lambda

> (define twice
    (lambda (x)
            (* 2 x)
    )
  )
> (twice 21)
42

Anonymous use of a lambda:

> ( 
    (lambda (x)
            (* 3 x)
    )
    14
  )
42

Sequential evaluation

(begin
   (define X 6)
   (define Y 7)
   (* X Y)
)

define vs let vs setq …

let creates a new lexical scope

setq assigns a value to an existing variable.

Then, there is also let* and letrec.

What is define doing, anyway?