![]() ![]() ![]() ![]() I don't have a good idea on how to traverse Value a, but at least I can see it evaluates example n into MuV. The reason I put scare quotes around "works" above is that I have no intuition about the λμ calculus so I don't know what it should do. Mu "delta" (Freeze "phi" (App (Var "x") (Var "y"))) I can reduce example n to the expected result: *Main> reduce (example 10) T = Lam "x" $ Lam "y" $ Mu "delta" $ Freeze "phi" $ App (Var "x") (Var "y")Įxample n = App (example (n-1)) (Var ("z_" ++ show n)) It "works" for the example from the paper: with example 0 = App (App t (Var "x")) (Var "y") (e', Any changed) -> if changed then reduce e' else e Reduce1 (Mu alpha u) = reduce0 = reduce1 u) Reduce1 (Freeze alpha e) = reduce0 = reduce1 e) Reduce1 (App f e) = reduce0 = reduce1 f reduce1 e) the formal definition of capture avoiding substitution to execute by hand -calculus programs according to its operatial semantics how our Haskell. Reduce0 (Freeze alpha (Mu beta u)) = reduceTo $ renameN beta alpha u Reduce0 (App (Mu beta u) v) = reduceTo $ Mu beta $ appN beta v u Reduce0 (App (Lam x u) v) = reduceTo $ substU x v u Go (Mu alpha u) = Mu alpha $ if alpha /= beta then go u else u Go (Freeze alpha w) = Freeze alpha $ if alpha = beta then App (go w) v else go w Go (Mu gamma u) = Mu gamma $ if gamma = beta then u else go uĪppN :: MuVar -> Expr Unnamed -> Expr n -> Expr n Go (Freeze gamma e) = Freeze (if gamma = beta then alpha else gamma) (go e) RenameN :: MuVar -> MuVar -> Expr n -> Expr n Go (Freeze alpha e) = Freeze alpha (go e) ![]() Go (Lam y e) = Lam y $ if y = x then e else go e SubstU :: Var -> Expr Unnamed -> Expr n -> Expr n Mu :: MuVar -> Expr Named -> Expr Unnamed Lam :: Var -> Expr Unnamed -> Expr UnnamedĪpp :: Expr Unnamed -> Expr Unnamed -> Expr Unnamedįreeze :: MuVar -> Expr Unnamed -> Expr Named There are three fundamental closed expressions called the SKI combinators.Here's a mindless transliteration of the reduction rules from the paper, using representation (as you'll see, when I say mindless, I really do mean mindless): This phenomenon is referred to as name shadowing. For example, the \(x\) variable in the following expression is bound on the inner lambda, while \(y\) is bound on the outer lambda. Each occurrence of a variable is then bound by the nearest enclosing binder. Multiple lambda abstractions may bind the same variable name. The first \(y\) is bound, while the second is free. In \(e_1\) both occurrences of \(x\) are bound. \(e_0\) is a combinator while \(e_1\) is not. Conversely a variable is free if it is not bound.Ī term with free variables is said to be an open term while one without free variables is said to be closed or a combinator.Į_1 &= \lambda x. A variable is said to be bound if it is contained in a lambda expression of the same variable binding. The most notable is the choice of identifiers for the binding variables. The actual implementation of the lambda calculus admits several degrees of freedom in how lambda abstractions are represented. This is merely a syntactical convention and does not change the underlying meaning. Out of convenience we often write multiple lambda abstractions with their variables on one lambda symbol. In the lambda calculus, each lambda abstraction binds a single variable, and the lambda abstraction's body may be another lambda abstraction. x_n )īy convention application extends as far to the right as is syntactically meaningful. Application of multiple expressions associates to the left. There are several syntactical conventions that we will adopt when writing lambda expressions. The variation we will discuss first is known as untyped lambda calculus, by contrast later we will discuss the typed lambda calculus which is an extension thereof. The lambda calculus is often called the "assembly language" of functional programming, and variations and extensions on it form the basis of many functional compiler intermediate forms for languages like Haskell, OCaml, Standard ML, etc. In other words, \(\lambda x.e\) is a function that takes a variable \(x\) and returns \(e\). Using the lambda calculus notation we write: The three terms are typically referred to in code by several contractions of their names:Ī lambda term is said to bind its variable. This means what you see in the picture above would translate to (\x -> x) (\y -> y), which would be equivalent to writing id id (which of course evaluates to id). This compact notation looks slightly different from what you're used to in Haskell but it's actually not: \(\lambda x.xa\) is equivalent to \x -> x a. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |