Programmieren Sie mit dem in der Vorlesung vorgestellten Backus-FP-System folgende Programme (n>0 sei jeweils vorausgesetzt):

1. gen: O -> O, gen : n = <1,...,n>
2. squares: O -> O, squares : n = <1,4,9,...,n2>
3. fibonacci: O -> O, gen : n = <1,1,2,3,5,...,fib(n)>

Ersetzen Sie in dem in der Vorlesung vorgestellten Backus-FP-System jeweils folgende Basisfunktionen durch andere:

1. rotl
2. distl
3. eq0
4. reverse

Beweisen Sie dann jeweils die Aequivalenz Ihrer Ersatzfunktion mit der originalen Funktion.

Übersetzen Sie den folgende M-Ausdruck in S-Ausdrücke, und lassen Sie sie in Ihrem Interpreter auswerten:

lambda[[f;k];
    cons[
     cons[H;cons[f[(U.A);k];(B.U)]];
     cons[lambda[[d];[eq[d;A]->f[R;A]]][k];G]
    ]]
[lambda[[p;s];
    [eq[s;A]->[atom[p]->p;T->cdr[p]];
     T->car[p]]]]