;; Die ersten drei Zeilen dieser Datei wurden von DrRacket eingefügt. Sie enthalten Metadaten
;; über die Sprachebene dieser Datei in einer Form, die DrRacket verarbeiten kann.
#reader(lib "DMdA-advanced-reader.ss" "deinprogramm")((modname mze) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f constructor repeating-decimal #t #t none datum #f ())))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Ein Auswerter für MiniScheme, das folgende Konstrukte enthält:
; 
; Definitionen:
; (define variable ausdruck)
;
; Ausdrücke: Zahlen, Variablen, quotierte Ausdruecke und
;  (prozedur exprs)
;  (if bedingung ausdruck1 ausdruck2)
;  (letrec bindungen ausdruck)
;  (begin exprs)
;  (lambda parameter ausdruck)
;  (set! variable ausdruck)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Nützliche Abkürzungen

; Berechne das 2. Element einer Liste
(: second ((list-of %a) -> %a))
(define second
  (lambda (xs) (first (rest xs))))

; Berechne das 3. Element einer Liste
(: third ((list-of %a) -> %a))
(define third
  (lambda (xs) (first (rest (rest xs)))))

; Berechne das 4. Element einer Liste
(: fourth ((list-of %a) -> %a))
(define fourth
  (lambda (xs) (first (rest (rest (rest xs))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Darstellung der betrachteten Ausdrücke

; Ein Ausdruck ist eins der Folgenden:
; - eine Zahl (number)
; - ein Wahrheitswert (boolean)
; - ein String (string)
; - ein Symbol (symbol)
; - eine Liste von Ausdrücken
; - ein Prozedurobjekt (procedure)
(define expression
  (signature
    (mixed number
           boolean
           string
           symbol
           (list-of expression)
           procedure)))

;;; Nützliches Prädikat:
;;; Ist das Argument eine Liste mit einem gegebenen ersten Symbol?
(: list-with-tag? (symbol any -> boolean))
(define list-with-tag?
  (lambda (symbol expr)
    (if (cons? expr)
        (equal? (first expr) symbol)
        #f)))


;;; Quotierungen

(: quoted? (expression -> boolean))
(define quoted?
  (lambda (expr) (list-with-tag? 'quote expr)))

(: expression-of-quotation (expression -> expression))
(define expression-of-quotation
  (lambda (expr) (second expr)))


;;; Variablen

(: variable? (expression -> boolean))
(define variable?
  (lambda (expr) (symbol? expr)))


;;; Zuweisungen

(: assignment? (expression -> boolean))
(define assignment?
  (lambda (expr) (list-with-tag? 'set! expr)))

(: assignment-variable (expression -> symbol))
(define assignment-variable
  (lambda (expr) (second expr)))

(: assignment-value (expression -> expression))
(define assignment-value
  (lambda (expr) (third expr)))


;;; Bedingte Ausdrücke: (if bedingung ausdruck1 ausdruck2)

(: if? (expression -> boolean))
(define if?
  (lambda (expr) (list-with-tag? 'if expr)))

(: if-predicate (expression -> expression))
(define if-predicate
  (lambda (expr) (second expr)))

(: if-consequent (expression -> expression))
(define if-consequent
  (lambda (expr) (third expr)))

(: if-alternative (expression -> expression))
(define if-alternative
  (lambda (expr) (fourth expr)))


;;; Abstraktionen  (lambda (x y) (+ x (* y 2)))

(: lambda? (expression -> boolean))
(define lambda?
  (lambda (expr) (list-with-tag? 'lambda expr)))

(: lambda-parameters (expression -> (list-of symbol)))
(define lambda-parameters
  (lambda (expr) (second expr)))

(: lambda-body (expression -> expression))
(define lambda-body
  (lambda (expr) (third expr)))

;;; Definitionen  (define x (+ 3 5))

(: definition? (expression -> boolean))
(define definition?
  (lambda (expr) (list-with-tag? 'define expr)))

(: definition-variable (expression -> symbol))
(define definition-variable
  (lambda (expr) (second expr)))

(: definition-value (expression -> expression))
(define definition-value
  (lambda (expr) (third expr)))



;;; Folgen von Ausdrücken: (begin ...)

(: begin? (expression -> boolean))
(define begin?
  (lambda (expr) (list-with-tag? 'begin expr)))

(: begin-actions (expression -> (list-of expression)))
(define begin-actions
  (lambda (expr) (rest expr)))




;;; Lokale Definitionen: (letrec bindings exp)

(: letrec? (expression -> boolean))
(define letrec?
  (lambda (expr) (list-with-tag? 'letrec expr)))

(: letrec-bindings (expression -> (list-of expression)))
(define letrec-bindings
  (lambda (expr) (second expr)))

(: letrec-expression (expression -> expression))
(define letrec-expression
  (lambda (expr) (third expr)))

(: letrec-binding-variable (expression -> symbol))
(define letrec-binding-variable
  (lambda (binding) (first binding)))

(: letrec-binding-expression (expression -> expression))
(define letrec-binding-expression
  (lambda (binding) (second binding)))


;;; Prozeduranwendungen

(: application? (expression -> boolean))
(define application?
  (lambda (expr) (cons? expr)))

(: operator (expression -> expression))
(define operator
  (lambda (expr) (first expr)))

(: operands (expression -> (list-of expression)))
(define operands
  (lambda (expr) (rest expr)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Darstellung von Prozedurobjekten

; Eine benutzerdefiniertes Prozedurobjekt besteht aus
; - einem lambda-Ausdruck (expression)
; - einer zugehörigen Umgebung (environment)
(define-record-procedures compound-procedure
  make-compound-procedure
  compound-procedure?
  (procedure-expression procedure-environment))

(: make-compound-procedure (expression environment -> compound-procedure))
(: compound-procedure? (any -> boolean))
(: procedure-expression (compound-procedure -> expression))
(: procedure-environment (compound-procedure -> environment))

; Parameterliste einer benutzerdefinierten Prozedur
(: procedure-parameters (compound-procedure -> (list-of symbol)))
(define procedure-parameters
  (lambda (proc)
    (lambda-parameters (procedure-expression proc))))

; Rumpf einer benutzerdefinierten Prozedur
(: procedure-body (compound-procedure -> expression))
(define procedure-body
  (lambda (proc)
    (lambda-body (procedure-expression proc))))


; Ein primitive Prozedurobjekt besteht aus
; - dem Namen der Prozedur (symbol)
(define-record-procedures
  primitive-procedure
  make-primitive-procedure
  primitive-procedure?
  (primitive-procedure-name))

(: make-primitive-procedure (symbol -> primitive-procedure))
(: primitive-procedure? (any -> boolean))
(: primitive-procedure-name (primitive-procedure -> symbol))

; Ein Prozedurobjekt ist eins der Folgenden:
; - ein benutzerdefiniertes Prozedurobjekt
; - ein primitives Prozedurobjekt
(define procedure
  (signature (mixed compound-procedure
                    primitive-procedure)))

(: procedure? (any -> boolean))
(define procedure?
  (lambda (x) (or (compound-procedure? x)
                  (primitive-procedure? x))))




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; Darstellung von Umgebungen

; Eine Umgebung (environment) besteht aus
; - einem (veränderbaren) ersten Rahmen
; - einer Vorgängerumgebung
(define-record-procedures-2
  environment
  make-environment
  environment?
  ((environment-first-frame set-environment-first-frame!)
   environment-ancestor))

; Eine Vorgängerumgebung ist eins der Folgenden:
; - eine leere Umgebung (im Falle der globalen Umgebung)
; - eine Umgebung
(define ancestor-environment
  (signature (mixed empty-list
                    environment)))
                    
(: make-environment (frame ancestor-environment -> environment))
(: environment-first-frame (environment -> frame))
(: set-environment-first-frame! (environment frame -> unspecific))
(: environment-ancestor (environment -> ancestor-environment))


;;; Darstellung von Bindungen

; Eine Bindung besteht aus
; - einer Variablen (symbol)
; - einem (veränderbaren) Ausdruck (expression)
(define-record-procedures-2
   binding
   make-binding
   binding?
   (binding-variable (binding-value set-binding-value!)))

(: make-binding (symbol expression -> binding))
(: binding? (any -> boolean))
(: binding-variable (binding -> symbol))
(: binding-value (binding -> expression))
(: set-binding-value! (binding expression -> unspecific))
   

;;; Darstellung von Bindungsrahmen

; Ein Bindungsrahmen ist eine Liste von Bindungen
(define frame (signature (list-of binding)))

;;;;;;;;;;; Fortsetzung am 4.2.2013...