EMZETT.
Login

Emzett Wiki

Scheme: Praxis: Ein eigener Interpreter

Properties1
tagsprogrammiersprachen, scheme

4 Min. Lesezeit

Kurz: Weil Code und Daten dieselbe Form haben, ist ein Interpreter in Scheme erstaunlich kurz. Dies ist die Idee aus SICP:

Teil des Kurses Scheme

Kapitel 6 von 8 im Kurs Scheme. Mit Fortschritt, Quiz und Zertifikat auf der Lernseite.

Ein Mini-Interpreter für Rechenausdrücke

Weil Code und Daten dieselbe Form haben, ist ein Interpreter in Scheme erstaunlich kurz. Dies ist die Idee aus SICP:

(use-modules (ice-9 match))
 
(define (auswerten ausdruck umgebung)
  (match ausdruck
    ((? number? n) n)
    ((? symbol? s)
     (let ((paar (assq s umgebung)))
       (if paar (cdr paar) (error "Unbekannte Variable:" s))))
    (('+ a b) (+ (auswerten a umgebung) (auswerten b umgebung)))
    (('- a b) (- (auswerten a umgebung) (auswerten b umgebung)))
    (('* a b) (* (auswerten a umgebung) (auswerten b umgebung)))
    (('/ a b) (/ (auswerten a umgebung) (auswerten b umgebung)))
    (('if c a b) (if (not (zero? (auswerten c umgebung))) (auswerten a umgebung) (auswerten b umgebung)))
    (('let ((x wert)) rumpf)
     (auswerten rumpf (cons (cons x (auswerten wert umgebung)) umgebung)))
    (_ (error "Unbekannter Ausdruck:" ausdruck))))
 
(define (zeige x) (display x) (newline))
(zeige (auswerten '(+ 1 (* 2 3)) '()))
(zeige (auswerten '(let ((x 5)) (* x x)) '()))
(zeige (auswerten '(if 0 100 200) '()))
(zeige (auswerten '(/ 10 4) '()))
(zeige (auswerten '(+ x 1) '((x . 41))))

Ausgabe:

7
25
200
5/2
42

Symbolisches Differenzieren

Ein Klassiker: Ableitungen von Termen als Daten:

(define (variable? x) (symbol? x))
(define (gleiche-variable? a b) (and (variable? a) (variable? b) (eq? a b)))
(define (summe? x) (and (pair? x) (eq? (car x) '+)))
(define (produkt? x) (and (pair? x) (eq? (car x) '*)))
 
(define (mach-summe a b)
  (cond ((and (number? a) (= a 0)) b)
        ((and (number? b) (= b 0)) a)
        ((and (number? a) (number? b)) (+ a b))
        (else (list '+ a b))))
 
(define (mach-produkt a b)
  (cond ((or (and (number? a) (= a 0)) (and (number? b) (= b 0))) 0)
        ((and (number? a) (= a 1)) b)
        ((and (number? b) (= b 1)) a)
        ((and (number? a) (number? b)) (* a b))
        (else (list '* a b))))
 
(define (ableitung ausdruck var)
  (cond ((number? ausdruck) 0)
        ((variable? ausdruck) (if (gleiche-variable? ausdruck var) 1 0))
        ((summe? ausdruck)
         (mach-summe (ableitung (cadr ausdruck) var) (ableitung (caddr ausdruck) var)))
        ((produkt? ausdruck)
         (mach-summe
          (mach-produkt (cadr ausdruck) (ableitung (caddr ausdruck) var))
          (mach-produkt (ableitung (cadr ausdruck) var) (caddr ausdruck))))
        (else (error "Unbekannter Ausdruck" ausdruck))))
 
(define (zeige x) (write x) (newline))
(zeige (ableitung '(+ x 3) 'x))
(zeige (ableitung '(* x y) 'x))
(zeige (ableitung '(* (* x y) (+ x 3)) 'x))

Ausgabe:

1
y
(+ (* x y) (* y (+ x 3)))

Streams (verzögerte Listen)

(define (zeige x) (display x) (newline))
(define-syntax stream-cons
  (syntax-rules () ((_ a b) (cons a (delay b)))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define (ganze-zahlen n) (stream-cons n (ganze-zahlen (+ n 1))))
(define (stream-take s n)
  (if (= n 0) '() (cons (stream-car s) (stream-take (stream-cdr s) (- n 1)))))
(define (stream-map f s) (stream-cons (f (stream-car s)) (stream-map f (stream-cdr s))))
(define (stream-filter p s)
  (if (p (stream-car s))
      (stream-cons (stream-car s) (stream-filter p (stream-cdr s)))
      (stream-filter p (stream-cdr s))))
 
(zeige (stream-take (ganze-zahlen 1) 5))
(zeige (stream-take (stream-map (lambda (x) (* x x)) (ganze-zahlen 1)) 5))
(zeige (stream-take (stream-filter even? (ganze-zahlen 1)) 5))
 
(define (sieb s)
  (stream-cons (stream-car s)
               (sieb (stream-filter (lambda (x) (not (zero? (remainder x (stream-car s))))) (stream-cdr s)))))
(zeige (stream-take (sieb (ganze-zahlen 2)) 10))

Ausgabe:

(1 2 3 4 5)
(1 4 9 16 25)
(2 4 6 8 10)
(2 3 5 7 11 13 17 19 23 29)

Merke

  • Mit match und Listen entsteht ein Interpreter in wenigen Zeilen
  • Symbolisches Rechnen (Ableitungen, Vereinfachung) ist ein klassischer Scheme-Einsatz
  • delay und force bauen träge Streams
  • Diese Beispiele stammen aus SICP, dem berühmtesten Scheme-Lehrbuch

Übungsaufgabe

Erweitere den Interpreter um lambda und Funktionsaufrufe.

Quiz zur Selbstkontrolle

Weiter im Kurs

Zurück: Ein-/Ausgabe, Fehlerbehandlung und Module

Weiter: Implementierungen und Ökosystem

Alle Kapitel: Scheme im Überblick

Graphansicht

Backlinks