Lambda calculus interpreter haskell8/6/2023 With memoization this might not be so bad. The evalWhile function also seems like a poor way to check if we've reached normal form, though I have seen other code that does this. Perhaps there is a better way to do this. The eval function feels particularly awkward to me, as every type in Expr is preceded by it's equivalent function. Notes Num is distinct from the standard type class Num. The only kinds of Values are Numbers, Functions, and Errors. The interpeter evaluates an Expression with respect to an Environment, which is a list of bindings of Names to Values. S = Abst "x" (Abst "y" (Abst "z" (App (App (Var "x") (Var "z")) (App (Var "y") (Var "z")))))įor instance: λ> evalWhile (App (App (App s k) k) k) Haskell familiarization Here is a basic lambda calculus interpreter written in Haskell. Here are a few applicative combinators for debugging. How would the implementation of a call-by-name interpreter be different from the one presented above Plotkin studied call-by-name and call-by-value strategies for evaluating the lambda calculus in the 1970s. Sub (Sub (App a b) var env) = (App (Sub a var env) (Sub b var env))Įval a b c) = sub (Sub (eval a) b (eval c)) Ivan Zakharyaschev remarked that this interpreter is call-by-value due to F f -> f (interpret env e2). | otherwise = (Abst var' (Sub body var env)) module Eval whereĪpp (App (Abst var body) env) = (Sub body var env) This code is slower than many other interpreters, and if there is a way to make the code more efficient while still conveying the reduction rules clearly, that would be an improvement. I want to be able to check whether two lambda-expressions are equal or not equal to each other. I'm presently stuck on implementing 'alpha-congruence' (also called 'alpha-equivalence' or 'alpha-equality' in some textbooks). My goal is to represent the transformation rules listed here accurately and explicitly. I am implementing an impure untyped lambda-calculus interpreter in Haskell. (Sub (App a b) var env) -> (App (Sub a var env) (Sub b var env)) (Sub (Abst var' body) var env) -> (Abst var' (Sub body var env)) (Sub (Abst var body) var env) -> (Abst var body) (App (Abst var body) env) -> (Sub body var env) This code is a representation of lambda calculus using an AST instead of text.
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |