- #Haskell lambda calculus interpreter how to#
- #Haskell lambda calculus interpreter code#
- #Haskell lambda calculus interpreter plus#
#Haskell lambda calculus interpreter code#
Having a parser serves a few purposes: first, it lets us use a better format for our lambda calculus code ( \ x y. So how do we go about actually using this data type? We could construct it manually, of course - we could define the identity function id = Lam "x" (Var "x"). encode putExprLn :: Expr -> IO () putExprLn = putStrLn. " ++ go b go ( App App _ _) f) = go e ++ " " ++ wrap f go ( App e f) = wrap e ++ " " ++ wrap f wrap Var _) = go x wrap Lam _ _) = "(" ++ go x ++ ")" wrap App _ _) = "(" ++ go x ++ ")" - Pretty printing putExpr :: Expr -> IO () putExpr = putStr. haskell - src/Lambda/Simple/Expr.hs module where import Prelude type Name = String - The expression data type data Expr = Var Name | Lam Name Expr | App Expr Expr deriving ( Show, Eq) - Encoding to string encode :: Expr -> String encode = go where go ( Var n) = n go ( Lam n Lam _ _)) = "\\ " ++ n ++ tail (go b) go ( Lam n b) = "\\ " ++ n ++ ". In addition to our data type, we've added a few convenience functions for encoding our expressions to strings, and for pretty printing them - it helps to be able to do something with what we're building. Our definition here is a lot less threatening than our earlier descriptions, don't you think? As you can see, an Expr is either a Var which is just a Name, a Lam which is a Name and another Expr, or a App which is two Exprs. The most important part is this part: data Expr = Var Name | Lam Name Expr | App Expr Expr As you can see, an expression is made up of variables, lambda abstractions, and function applications. We're going to pull in a few libraries - containers for the usual suspects, parsec for parsing, and repline for interactive input - and set some extensions (nothing fancy, just FlexibleContexts, NoImplicitPrelude, and OverloadedStrings) cabal project file - lc-simple.cabal cabal-version: 3.0 name: lc-simple version: 0.0.1 license: NONE author: Leo maintainer: build-type: Simple extra-source-files: README.md library exposed-modules: Lambda.Simple default-extensions: FlexibleContexts NoImplicitPrelude OverloadedStrings build-depends: base >= 4 & < 5, containers, parsec, repline hs-source-dirs: src default-language: Haskell2010 With that out of the way, let's get started! First off, we'll create a new cabal project file. If you've been doing Haskell, you've been doing lambda calculus the whole time, anyway. This article isn't going to explain lambda calculus in depth, as it rather serves as a nice starting point for such explorations later. Whereas Turing machines invoke clunky mechanisms, Church's calculus is a language, with a flexibility and flow not unlike that of the spoken language, and how each spoken word produces a sentence fragment that is awaiting the next word of the rest of the sentence.
#Haskell lambda calculus interpreter plus#
How do we use this, say, to add two plus five? Well, it's easy! add five two, where add is a function taking two arguments. And a function application is the act of learning what a lambda abstraction's variable is.
#Haskell lambda calculus interpreter how to#
A lambda abstraction tells us how to replace a variable with it's value when we learn it. What are these? In friendly terms, a variable is just something that we don't know yet, and so we've given it a name instead. It consists of simple expressions constructed out of 3 things: It also helps impose referential transparency.Lambda Calculus is a universal model of computation proposed by Alonzo Church in the 1930's, and it is an incredibly small one at that. this helps prevent cheating and defining recursive functions. All definitions in the language are immutible. Once something is defined, it cannot be changed.
This is called lazy evaluation or normal order evaluation, as opposed to eager or applicative order evaluation.
The last line returns true because Lambda Light substitutes a variable for it's relevant binding only when it is being called, instead of when it is an argument to a function. Λ: not := \b.b false true - Lambda Light allows you to create functions with named functions. Λ: false := \x.\y.y - Lambda Light supports bindings to a global namespace.
Λ: true := \x.\y.x - Lambda Light supports binding names to expressions. Λ: (λx.x x) (λx.x) - Lambda Light supports function application. Λ: \x.x - Lambda Light supports the creation lambda expressions using \ and the unicode λ character.
Λ: x - Lambda Light supports creating arbitrary variables. Λ: - Lambda Light supports Haskell-like single line comments
0 kommentar(er)
