Warum sind ML/Haskell-Datentypen nützlich, um "Sprachen" wie arithmetische Ausdrücke zu definieren?

Question

Dies ist eine eher weiche Frage über statische Systeme in funktionalen Sprachen wie denen der ML-Familie. Ich verstehe, warum Sie Datentypen benötigen, um Datenstrukturen wie Listen und Bäume zu beschreiben, aber das Definieren von "Ausdrücken" wie denen der Aussagenlogik innerhalb von Datentypen scheint nur einen gewissen Nutzen zu bringen und ist nicht notwendig. Zum Beispiel

datatype arithmetic_exp = Constant of int 
         | Neg of arithmetic_exp 
         | Add of (arithmetic_exp * arithmetic_exp) 
         | Mult of (arithmetic_exp * arithmetic_exp) 

definiert eine Reihe von Werten, auf dem Sie eine eval Funktion schreiben, die das Ergebnis geben würde. Sie könnten genauso gut 4 Funktionen definieren: const: int -> int, neg: int -> int, add: int * int -> int und mult: int * int -> int und dann würde ein Ausdruck der Art add (mult (const 3, neg 2), neg 4) Ihnen dasselbe ohne Verlust der statischen Sicherheit geben. Die einzige Komplikation ist, dass Sie vier statt zwei Dinge tun müssen. Während ich SML und Haskell gelernt habe, habe ich versucht darüber nachzudenken, welche Features dir etwas geben, das notwendig ist und was nur eine Annehmlichkeit ist, deshalb bin ich der Grund, warum ich frage. Ich denke, das wäre wichtig, wenn Sie den Prozess der Bewertung eines Wertes vom Wert selbst entkoppeln möchten, aber ich bin mir nicht sicher, wo das nützlich wäre.

Vielen Dank.

Answer 1

Es gibt eine Dualität zwischen initialen/erster Ordnung/Datentyp-basierten Kodierungen (auch als tiefe Einbettungen bezeichnet) und finalen/höherwertigen/Evaluator-basierten Kodierungen (auch als flache Einbettungen bezeichnet). Sie können tatsächlich typischerweise eine Typenklasse von Kombinatoren anstelle eines Datentyps verwenden (und zwischen den beiden hin und her konvertieren).

Hier ist ein Modul, die beiden Ansätze zeigt:

{-# LANGUAGE GADTs, Rank2Types #-} 

module Expr where 

data Expr where 
    Val :: Int -> Expr 
    Add :: Expr -> Expr -> Expr 

class Expr' a where 
    val :: Int -> a 
    add :: a -> a -> a 

Sie können sehen, dass die beiden Definitionen auf unheimliche Weise ähnlich aussehen. Expr' a beschreibt im Grunde eine Algebra unter Expr, was bedeutet, dass Sie eine a aus einer Expr bekommen können, wenn Sie eine solche Expr' a haben. In ähnlicher Weise, weil Sie Expr' Expr eine Instanz schreiben können, sind Sie in der Lage eine Laufzeit von Typ Exprforall a. Expr' a => a in einen syntaktischen Wert vom Typ vergegenständlichen:

expr :: Expr' a => Expr -> a 
expr e = case e of 
    Val n -> val n 
    Add p q -> add (expr p) (expr q) 

instance Expr' Expr where 
    val = Val 
    add = Add 

expr' :: (forall a. Expr' a => a) -> Expr 
expr' e = e 

Am Ende eine Darstellung über eine andere Kommissionierung hängt wirklich davon ab, was Ihre Der Hauptfokus ist: Wenn Sie die Struktur des Ausdrucks überprüfen möchten (zB wenn Sie ihn optimieren/kompilieren wollen), ist es einfacher, wenn Sie Zugang zu einem AST haben. Wenn Sie andererseits nur daran interessiert sind, eine Invariante mit einer Faltung zu berechnen (z. B. die Tiefe des Ausdrucks oder seine Auswertung), ist eine Codierung höherer Ordnung möglich.

Answer 2

Die ADT ist in einer Form, die Sie auf andere Weise als nur evaluieren untersuchen und manipulieren können. Sobald Sie alle interessanten Daten in einem Funktionsaufruf versteckt haben, können Sie nichts mehr damit tun, sondern sie auswerten. Betrachten Sie diese Definition, ähnlich der in Ihrer Frage, aber mit einem Var-Term zur Darstellung von Variablen und mit den Mul- und Neg-Termen, die entfernt wurden, um auf Addition zu fokussieren.

data Expr a = Constant a 
      | Add (Expr a) (Expr a) 
      | Var String 
      deriving Show 

Die offensichtliche Funktion zu schreiben ist eval, natürlich. Es erfordert eine Art und Weise den Wert einer Variablen zu suchen, und ist einfach:

-- cheating a little bit by assuming all Vars are defined 
eval :: Num a => Expr a -> (String -> a) -> a 
eval (Constant x) _env = x 
eval (Add x y) env = eval x env + eval y env 
eval (Var x) env = env x 

Aber nehmen Sie nicht über eine variable Zuordnung noch. Sie haben einen großen Ausdruck, den Sie viele Male für unterschiedliche Wahl der Variablen auswerten werden.Und einige dumme rekursive Funktion gebaut, um einen Ausdruck auf wie:

Add (Constant 1) 
    (Add (Constant 1) 
     (Add (Constant 1) 
       (Add (Constant 1) 
        (Add (Constant 1) 
         (Add (Constant 1) 
          (Var "x")))))) 

Es verschwenderisch wäre 1+1+1+1+1+1 jedes Mal, wenn Sie diese auswerten neu zu berechnen: wäre es nicht schön, wenn Ihr Auswerter erkennen könnte, dass dies nur eine andere Art des Schreibens Add (Constant 6) (Var "x")?

Sie schreiben also einen Ausdruck-Optimierer, der ausgeführt wird, bevor alle Variablen verfügbar sind, und versucht Ausdrücke zu vereinfachen. Es gibt natürlich viele Vereinfachungsregeln, die Sie anwenden könnten. unten habe ich nur zwei sehr einfache implementiert, um den Punkt zu veranschaulichen.

simplify :: Num a => Expr a -> Expr a 
simplify (Add (Constant x) (Constant y)) = Constant $ x + y 
simplify (Add (Constant x) (Add (Constant y) z)) = simplify $ Add (Constant $ x + y) z 
simplify x = x 

Nun, wie sieht unser dummer Ausdruck aus?

> simplify $ Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Var "x")))))) 
Add (Constant 6) (Var "x") 

all unnötigen Sachen entfernt werden, und Sie haben jetzt einen schönen, sauberen Ausdruck für verschiedene Werte von x zu versuchen.

Wie machen Sie das Gleiche mit einer Darstellung dieses Ausdrucks in Funktionen? Dies ist nicht möglich, da es zwischen der ursprünglichen Spezifikation des Ausdrucks und seiner abschließenden Bewertung keine "Zwischenform" gibt: Sie können den Ausdruck nur als einzelnen, undurchsichtigen Funktionsaufruf betrachten. Das Auswerten bei einem bestimmten Wert von x bewertet notwendigerweise jeden der Teilausdrücke neu, und es gibt keine Möglichkeit, sie zu entwirren.

Hier ist eine Erweiterung des Funktionstypen, den Sie in Ihrer Frage vorschlagen, wieder mit Variablen angereichert:

type FExpr a = (String -> a) -> a 

lit :: a -> FExpr a 
lit x _env = x 

add :: Num a => FExpr a -> FExpr a -> FExpr a 
add x y env = x env + y env 

var :: String -> FExpr a 
var x env = env x 

mit dem gleichen dummen Ausdruck oft zu bewerten:

sample :: Num a => FExpr a 
sample = add (lit 1) 
      (add (lit 1) 
        (add (lit 1) 
         (add (lit 1) 
          (add (lit 1) 
           (add (lit 1) 
             (var "x")))))) 

Es funktioniert wie erwartet :

> sample $ \_var -> 5 
11 

Aber es muss jedes Mal, wenn Sie es versuchen, eine Reihe von Zusatz machen es für eine andere x, obwohl die Addition und die Variable weitgehend unabhängig sind. Und es gibt keine Möglichkeit, den Ausdrucksbaum zu vereinfachen. Sie können es nicht vereinfachen, während Sie es definieren: das heißt, Sie können add nicht schlauer machen, weil es seine Argumente überhaupt nicht untersuchen kann: Seine Argumente sind Funktionen, die, was add angeht, überhaupt etwas tun können . Und Sie können es auch nicht vereinfachen, nachdem Sie es konstruiert haben: An diesem Punkt haben Sie nur eine undurchsichtige Funktion, die eine Variable-Lookup-Funktion übernimmt und einen Wert erzeugt.

Indem Sie die wichtigen Teile Ihres Problems als eigenständige Datentypen modellieren, machen Sie sie zu Werten, die Ihr Programm intelligent manipulieren kann. Wenn Sie sie als Funktionen belassen, erhalten Sie ein kürzeres Programm, das weniger leistungsfähig ist, da Sie alle Informationen in Lambdas sperren, die nur GHC manipulieren kann.

Und sobald Sie es mit ADTs geschrieben haben, ist es nicht schwer, diese Darstellung zurück in die kürzere funktionsbasierte Darstellung zu reduzieren, wenn Sie möchten. Das heißt, es könnte schön sein, eine Funktion vom Typ

convert :: Expr a -> FExpr a 

Aber in der Tat zu haben, haben wir dies bereits getan! Das ist genau der Typ, den eval hat. Sie haben es vielleicht nicht bemerkt, weil der Alias ​​vom Typ FExpr nicht in der Definition von eval verwendet wird.

In gewisser Weise ist die ADT-Darstellung allgemeiner und mächtiger und fungiert als Baum, den Sie auf viele verschiedene Arten zusammenfalten können. Eine dieser Möglichkeiten besteht darin, sie genau so zu bewerten, wie es die funktionsbasierte Darstellung tut. Aber es gibt andere:

• den Ausdruck vereinfachen, bevor es
• Erstellen Sie eine Liste aller Variablen bewerten, die für diesen Ausdruck definiert werden müssen, um gut
• Graf gebildet werden, wie tief die tiefste Teil des verschachtelten Baum ist, zu schätzen, wie viele Stapelrahmen könnte ein Auswerter
• den Ausdruck in einen String konvertieren brauchen eine Haskell Ausdruck annähert Sie das gleiche Ergebnis

So zu bekommen geben könnte Wenn möglich, möchten Sie möglichst lange mit informationsreichen ADTs arbeiten und dann den Baum in eine kompaktere Form bringen, sobald Sie etwas Bestimmtes damit zu tun haben.