Topics

L I S P

In LISP, procedures and data have the same structure: generalized list.

•  the fundamental objects are called ATOMS;
•  groups of atoms and lists form LISTS;
•  atoms and lists are called SYMBOLIC EXPRESSIONS.

LISP means manipulating symbols.

In LISP, the procedure is always specified at the head of the list, immediately followed by arguments => prefix notation.

•  a PROCEDURE is a basic entity that specifies the way something is done;
•  a procedure predefined by the language is called a PRIMITIVE
•  a collection of procedures that work together are called a PROGRAM
•  an abstract description of a procedure or a program, that is not expressed in any specific coding language, is called an ALGORITHM.

When a right paranthesis and a left paranthesis surround something, we call the result a list and we reffer to its elements.

For example, the list (+ 3.14 2.71) has 3 elements: +, 3.14 şi 2.71.

•  The atoms of the type: 27, 3.14 are called NUMERICAL ATOMS.
•  The atoms of the type: +, MAX are called SYMBOLICAL ATOMS.

                                         Expression
                                               /\
                                              /  \
                                             /    \
                                            /      \
                                           /        \
                                     Atom      List
                                                     /\
                                                    /  \
                                                   /    \
                                                  /      \
                                          Number    Symbol
                                              /\
                                             /  \
                                            /    \
                                           /      \
                                        Integer Real

The primitives CAR and CDR

(CAR L) - returns the first element of the list L
(CDR L) - returns the list formed by the rest of the elements

Considering the expression: (A B C)
(CAR '(A B C))
returns
A
Notă: We notice that: '(A B C) == (QUOTE (A B C))and the function QUOTE returns the parameter of the function.

Whereas (CDR '(A B C)) returns (B C).

CAR şi CDR
(CAR '((A B) C)) (A B) (CDR '((A B) C)) (C)

                             -------
                    ----->| CAR |----> A ---------
                    |         -------                   |        --------
    (A B C) ==|                                   |==>| CONS |--> (A B C)
                    |        -------                    |        --------
                    ----->| CDR |----> (B C) -----
                             ------- 

The second element of the list is obtained this way:
(CAR (CDR '(A B C)))
B

The symbolical atoms can have values A value can be attributed to a symbolical atom (number or symbol or list) at which that atom will be evaluated at. This is realized by the SETQ procedure(by side effect!).

(SETQ L '(A B))
L
(A B)
'L
L
(CAR L)
A
(CDR L)
(B)

APPEND, LIST and CONS procedures

APPEND unifies lists.

LIST constructs a list out of its arguments:

CONS inserts a new first element in a list:

                             -------
                    ----->| CAR |----> A ---------
                    |         -------                   |        --------
    (A B C) ==|                                   |==>| CONS |--> (A B C)
                    |        -------                    |        --------
                    ----->| CDR |----> (B C) -----
                             -------  

LENGTH, REVERSE, SUBST and LAST procedures

LENGTH returns the length of a list.

REVERSE inverts a list:

SUBST replaces an expression with another in a list:

(SUBST <new expr> <old expr> <list>)

LAST returns a list that contains the last element:

Shapes evaluation

When the LISP interpreter receives a shape, it sends it to the primitive EVAL EVAL, which evaluates all arguments then calls the procedure from the head of the list.

  --------------------    Yes  --------------------------  Yes  -----------------------------------
< Is S an atom? >---->< Is S a number? >-------->| Return the number. |
  --------------------           ---------------------------        -----------------------------------
          |                                  |
          |                                  | No
          | No                            V
          |                  ------------------------------- 
          |                  | Ret. value of S. |
          |                  -------------------------------
         V
   ------------------------------                -------------------------------
< Is QUOTE the first >     Yes    | Return the second |
< atom of S?            >----------->| element of S.          |
  -------------------------------                --------------------------------
          |
          | No
         V
  -------------------------               -----------------------
< Does the first element      >    Yes     | Does not evaluate   |
< of S indicate a >---------->| arguments   |
< special behavior? >            | - special case. |
  --------------------------              -----------------------
         |
         | No
        V
 -----------------------------------------
 | Uses EVAL on all   |
 | elements of S except           |
 | for the first             |
 ------------------------------------------
                 |
                 |
                V
  ------------------------------------
 | Applies the first element  |
 | of S to the resulted values          |
 | and returns |
 | the result.                   |
 ------------------------------------

Problems

Problem 1. Atoms and lists.

Problem 2. Symbolical atoms. Functions.

Problem 3. CAR and CDR 1.

Problem 4. CAR and CDR 2.

Problem 5. CAR and CDR 3.

Problem 6. APPEND and LIST

Problem 7. Evaluate examples from LENGTH, REVERSE, SUBST, LAST and CONS

Problema 8. Evaluate examples from Shape evaluation