Ist es möglich, die verschiedenen Bewertungsstrategien zu präsentieren, indem man diesen einfachen Reduzierer modifiziert?

Question

Ich bin die Art, die das Lernen bevorzugt, indem sie Code betrachtet anstatt lange Erklärungen zu lesen. Dies könnte einer der Gründe sein, warum ich lange wissenschaftliche Arbeiten nicht mag. Der Code ist unmissverständlich, kompakt, geräuschlos und wenn Sie nichts bekommen, können Sie einfach damit spielen - Sie müssen den Autor nicht fragen.

Dies ist eine vollständige Definition des Lambda-Kalküls:

-- A Lambda Calculus term is a function, an application or a variable. 
data Term = Lam Term | App Term Term | Var Int deriving (Show,Eq,Ord) 

-- Reduces lambda term to its normal form. 
reduce :: Term -> Term 
reduce (Var index)  = Var index 
reduce (Lam body)  = Lam (reduce body) 
reduce (App left right) = case reduce left of 
    Lam body -> reduce (substitute (reduce right) body) 
    otherwise -> App (reduce left) (reduce right) 

-- Replaces bound variables of `target` by `term` and adjusts bruijn indices. 
-- Don't mind those variables, they just keep track of the bruijn indices. 
substitute :: Term -> Term -> Term 
substitute term target = go term True 0 (-1) target where 
    go t s d w (App a b)    = App (go t s d w a) (go t s d w b) 
    go t s d w (Lam a)    = Lam (go t s (d+1) w a) 
    go t s d w (Var a) | s && a == d = go (Var 0) False (-1) d t 
    go t s d w (Var a) | otherwise = Var (a + (if a > d then w else 0)) 

-- If the evaluator is correct, this test should print the church number #4. 
main = do 
    let two = (Lam (Lam (App (Var 1) (App (Var 1) (Var 0))))) 
    print $ reduce (App two two) 

Meiner Meinung nach ist die „reduce“ über Funktion sagt viel mehr über das Lambda-Kalkül als Seiten von Erklärungen und ich wünsche, dass ich gerade bei aussehen könnte als ich anfing zu lernen. Sie können auch sehen, dass es eine sehr strenge Evaluierungsstrategie implementiert, die sogar innerhalb von Abstraktionen verläuft. Auf diesen Geist, Wie könnte dieser Code geändert werden, um die vielen verschiedenen Bewertungsstrategien zu veranschaulichen, die der LC haben kann (Rufname, Lazy Evaluation, Call-by-Value, Call-by-Sharing, Teilbewertung und bald)?

Answer 1

Call-by-Name benötigt nur wenige Änderungen:

1. nicht den Körper eines Lambda-Abstraktion Bewertung: reduce (Lam body) = (Lam body).

2. Das Argument der Anwendung nicht auswerten. Stattdessen sollten wir es ersetzen wie:

   reduce (App left right) = case reduce left of 
       Lam body -> reduce (substitute right body) 
   

Call-by-Bedarf (auch bekannt als lazy evaluation) scheint härter (oder vielleicht unmöglich) in einer vollständig deklarative Weise zu implementieren, da wir Werte müssen memoize Ausdrücke. Ich sehe keinen Weg, um es mit kleinen Änderungen zu erreichen.

Call-by-sharing ist nicht anwendbar auf einfache Lambda-Kalküle, da wir hier keine Objekte und Zuweisungen haben.

Wir könnten auch die vollständige Beta-Reduktion verwenden, aber wir müssen eine deterministische Reihenfolge der Auswertung wählen (wir können keinen "willkürlichen" Redex auswählen und ihn mit dem Code, den wir jetzt haben, reduzieren). Diese Auswahl führt zu einer Auswertungsstrategie (eine der oben beschriebenen).

Answer 2

Das Thema ist ziemlich breit. Ich werde nur über ein paar Ideen schreiben.

Die vorgeschlagene reduce führt paralleles Neuschreiben durch. Das heißt, es bildet App t1 t2 bis App t1' t2' ab (vorausgesetzt, t1' ist keine Abstraktion). Einige Strategien wie CBV und CBN sind sequenzieller, da sie nur einen einzigen Redex haben.

Um sie zu beschreiben, würde ich reduce ändern, so dass es zurückgibt, ob eine Reduzierung tatsächlich durchgeführt wurde, oder wenn stattdessen der Begriff eine normale Form war. Dies kann durch Rücksendung einer Maybe Term erfolgen, wobei Nothing Normalform bedeutet.

Auf diese Weise würde CBN

reduce :: Term -> Maybe Term 
reduce (Var index)   = Nothing -- Vars are NF 
reduce (Lam body)    = Nothing -- no reduction under Lam 
reduce (App (Lam body) right) = Just $ substitute right body 
reduce (App left right) = 
     (flip App right <$> reduce left) <|> -- try reducing left 
     (App left  <$> reduce right)  -- o.w., try reducing right 

sein, während CBV

reduce :: Term -> Maybe Term 
reduce (Var index)   = Nothing 
reduce (Lam body)    = Nothing -- no reduction under Lam 
reduce (App (Lam body) right) 
    | reduce right == Nothing   -- right must be a NF 
    = Just $ substitute right body 
reduce (App left right) = 
     (flip App right <$> reduce left) <|> 
     (App left  <$> reduce right) 

Verzögerte Auswertung (mit Sharing) Bedingungen verwendet werden können, nicht ausgedrückt wäre, wenn ich mich richtig erinnere. Es erfordert Graphen, um anzuzeigen, dass ein Unterbegriff geteilt wird.