Interpreter für eine einfache imperative Programmiersprache in Haskell

imp.hs auf GitHub

Unser Informatik-Prof hat uns die Bonusaufgabe gegeben, einen Interpreter in Haskell für eine imperative Programmiersprache namens ”IMP“ in der funktionalen Programmiersprache Haskell zu schreiben.

Um die Aufgabe anzugehen habe ich mir zunächst angeschaut, ob es dazu schon Lösungen im Netz gibt. Ich bin dann auf ein Video von James Hobson gestoßen, in dem erklärt wird wie man einen Interpreter für eine sehr simple imperative Programmiersprache basteln kann. Eine andere tolle Erklärung wie man die Aufgabe ohne Monaden lösen kann liefert Stefan Holdermans auf StackOverflow.

Die in unserer Vorlesung präsentierte Sprache ”IMP“ unterscheidet sich von den hier verwendeten nur in wenigen Punkten:

1. IMP soll nicht nur numerische Ausdrücke, sondern auch boole’sche evaluieren können und
2. IMP soll relationale (=, >) und boole’sche (&&, ||, ¬) Operatoren interpretieren können und
3. IMP soll eine If-Anweisung bereitstellen.

Doch wie sich zeigte ist die Implementierung von Punkt 1. nicht trivial. Um zu verstehen wieso, schauen wir uns die Definition eines Ausdruckes (hier Exp) in dem Code¹ von Stafan Holdermans an:

infixl 6 :+:, :-:
infixl 7 :*:, :/:
data Exp
  = C Int        -- constant                                                     
  | V Var        -- variable                                                     
  | Exp :+: Exp  -- addition                                                     
  | Exp :-: Exp  -- subtraction                                                  
  | Exp :*: Exp  -- multiplication                                               
  | Exp :/: Exp  -- division

Hier kann ein Ausdruck entweder eine verknüpfung von mehreren Ausdrücken, eine Variable oder eine Konstante sein. Allerdings nimmt der Typ-Konstruktor C nur einen Int entgegen. Zunächst wollte ich einen neuen Datentypen erstellen, der entweder einen Int oder einen Bool annimmt. Diese Idee hat sich als schwierig herausgestellt, da bei der Auswertung der Ausdrücke dann immer geprüft werden müsste welchen Typ diese haben. Anstatt dessen habe ich mich daran erinnert, dass boole’sche Ausdrücke ja in den allermeisten Programmiersprachen sowieso als Zahlen, nämlich 1 -> True und 0 -> False darstellt werden. Damit hat sich Punkt 1 geklärt. Für die relationalen und boole’schen Operatoren habe ich die folgenden Zeilen hinzugefügt:

infixl 5 :=:, :>:, :||:, :&&:
...
  | Exp :=: Exp    -- equality
  | Exp :>: Exp    -- ordering
  | Exp :||: Exp   -- logical or
  | Exp :&&: Exp   -- logical and
  | Not Exp        -- negation

Um diese Ausdrücke auszuwerden, implementieren wir eine Funktion eval die einen Ausdruck und einen Zustand nimmt und einen Wert zurückgibt:

eval :: Exp -> Store -> Val
...
eval (e1 :=: e2) r  = if eval e1 r == eval e2 r then 1 else 0 
eval (e1 :>: e2) r  = if eval e1 r > eval e2 r then 1 else 0 
eval (e1 :&&: e2) r  = if eval e1 r == 1 && eval e2 r == 1 then 1 else 0 
eval (e1 :||: e2) r  = if eval e1 r == 1 || eval e2 r == 1 then 1 else 0 
eval (Not e) r  = if eval e r == 1 then 0 else 1

An dieser Stelle wird Pattern-Matching genutzt um die verschiedenn Operationen voneinander zu trennen und indiviuell auszuwerten. Dabei werden die neuen Operatoren unter dem Mantel einfach zu den Haskell-eignen übersetzt.

Ähnlich kann man vorgehen um eine If-Anweisung in unserer fiktiven Sprache zu definieren. Wir beginnen damit den Typ-Konstruktor If zu unserer Liste von Anweisungen (hier Stmt) hinzuzufügen:

data Stmt 
...
  | If Exp Stmt Stmt -- conditional

Entsprechend definieren wir eine Funktion exec, die eine Anweisung und einen Zustand nimmt und den darauffolgenden Zustand zurückgibt:

exec :: Stmt -> Store -> Store 
...
exec (If e1 s1 s2) r = if eval e1 r == 1 then exec s1 r else exec s2 r 

Da ein imperatives Programm nichts anderes ist als eine aneinanderreihung von Anweisungen hat die Funktion run, die unser Programm ausführt den Typ Prog -> Store -> Store. Dabei ist Prog ein Typ-Alias für [Stmt]. Wir führen eine Aktion in einer “Start-Welt” aus und erhalten dann eine veränderte neue Welt. Die Funktion sieht wie folgt aus:

run :: Prog -> Store -> Store
run p r = nubBy ((==) `on` fst) $ exec p r

In unserer neuen Sprache IMP können wir jetzt zum Beispiel ein Programm schreiben, dass die Fakultät einer Zahl n berechnet:

fac' :: Prog
fac' = Seq
  [ "x" := C 1
  , "i" := C 1
  , (While (V "n" :>: V "i") (Seq
    [ "x" := V "x" :*: V "i"
    , "i" := V "i" :+: C 1
    ]))
  ]

Wenn wir unseren Code in GHCi laden, liefert uns der Befehl lookup "x" $ run fac' [("n", 5)] das Ergebnis 120, genau die Fakultät von 5. Perfekt!