| Scheme/Racket - Lista nr 10 (17.01.13)
|
|
Zadanie 1 (10p.) Zaimplementuj w Schemie maszynę SECD
służącą do ewaluacji termów rachunku lambda. Opis maszyny można
znaleźć np. w
pracy "A
Rational Reconstruction of Landin's SECD Machine". Przyjmij jako
punkt wyjścia opis oryginalnej maszyny podany w sekcji 2.1 tej pracy.
Ponadto przyjmij następujące założenia:
- Środowisko jest reprezentowane jako lista par zmienna-wartość (np. '((x . 3) (y . 4)))
- Termy, na których operuje maszyna to: literały całkowitoliczbowe,
zmienne (reprezentowane jako symbole Scheme'a, np. 'x),
lambda-abstrakcje (reprezentowane jako listy o 3 elementach, z których
pierwszy to zawsze symbol 'lambda, np. '(lambda x
x)), oraz aplikacje (listy dwuelementowe, np. '((lambda x x)
3)).
- Główna funkcja nazywa się run i przyjmuje jako argument
konfigurację maszyny, będącą listą czteroelementową złożoną z
komponentów S, E, C, D (wg opisu).
- W celu badania struktury wyrażeń zdefiniuj odpowiednie akcesory,
np. gdy chcemy wydobyć z lambda-abstrakcji jej ciało, używamy
akcesora lambda-body zdefiniowanego tak: (define
(lambda-body exp) (caddr exp)). Dzięki temu kod będzie czytelny i
niezależny od sposobu reprezentacji danych.
- W przypadku wyrażeń o niepoprawnej strukturze wyświetlaj komunikat o błędzie.
|
|