Neben Skalaren ist die CONS-Zelle der einzige Datentyp in (Pure-)LISP. Programmieren Sie folgende Datenstrukturen in LISP:

1. Einen Stack mit den Operationen top, push und pop
2. Einen Binärbaum, dessen Blätter Zahlen sind, mit den Operationen insert, minimum, maximum

Überlegen Sie sich das Konzept eines SKI-Interpreters, d.h. eines Programms, das CL-Terme (aus S, K, I, Klammern und Konstanten) einliest und alle Redexe reduziert.

Gegeben sie das folgende Programmfragment

      
(defun f (n) 
   (cond
     ((null n)  1)
     (t         (+ n (f (- n 1))))))
      

Geben Sie unter der Annahme, das für die Interpretation eine A-Liste verwendet wird, die Entwicklung dieser A-Liste beim Aufruf (f 5) an.

Übersetzen Sie das folgende Fragment M-Code in S-Ausdrücke:

   [[e;a];
      [null[e] -> NIL;
       atom[e] -> [eq[e;T] -> T;
                   eq[e;F] -> F;
                   T       -> cdr[sassoc[e;a;[[];error[A8]]]]];
       atom[car[e]] -> [eq[car[e];QUOTE] -> cadr[e];
                        eq[car[e];COND]  -> evcon[cdr[e];a];
                        eq[car[e];FUNCTION] -> LIST[FUNARG;cadr[e];a];
                        T -> apply[car[e];evlis[cdr[e];a];a]];
       T        -> apply[car[e];evlis[cdr[e];a];a]]]