From the interpreter’s perspective its not really recursion, its just expanding a copy of the same function definition as many times as necessary. Every time you try to evaluate (Y G) it expands to (G (Y G)), allowing you to continue a recursive computation in G for as long as you wish. The feeling I get about the Y combinator is this. If ever F is called inside exp, the Y combinator will expand again to produce another definition of F to call “recursively”. We can then go ahead and evaluate exp with F bound to (Y (λ (F) exp)). (Y (λ (F) exp)) expands to ((λ (F) exp) (Y (λ (F) exp))) in the same way that (Y G) expands to (G (Y G)). We can then use Y to get a definition for F. The only way to bring a variable into scope is using lambda, so we might as well start there. I’ll run through a quick example of defining a function F as some an arbitrary expression exp that can call F. To understand how the Y combinator allows recursion, it is sufficient to know that it is a function with the property (Y G) = (G (Y G)). Easy Prey: Variables, Application and Numbersīecause many functions are implemented in the language itself, the grammar quite small.ĬompileExp ( Let body ) = compileExp body compileExp ( Let (( n, v ) : rest ) body ) = Lam n inner ` App ` compileExp v where inner = compileExp ( Let rest body ) Letrec.Also it means you can add any library functions you see fit, and I ended up adding some comparisons, and list operations.Īll code for the project can be found on github. This greatly reduces the complexity of the parser and the compiler. Instead of defining all the functions in the language in the compiler, I thought it would be more fun to write them in the language itself. In my implementation I needed a parser, an interpreter, and an extractor, in addition to a reimplementation of the compiler. There are several steps of the process that are missed because they are built into the Racket language. I decided I would try to implement it in Haskell instead of Racket. This whole project is based on this post by Matt Might. In simpler terms, the "value" of the numeral is equivalent to the number of times the function encapsulates its argument.į ∘ n = f ∘ f ∘ ⋯ ∘ f ⏟ n times. The higher-order function that represents natural number n is a function that maps any function f f to its n-fold composition. There are potential problems with the interpretation of results because of the difference between the intensional and extensional definition of equality.Ĭhurch numerals are the representations of natural numbers under Church encoding. Lambda calculus is usually interpreted as using intensional equality. The translation may apply the function in some way to retrieve the value it represents, or look up its value as a literal lambda term. It is not possible in general to decide if two functions are extensionally equal due to the undecidability of equivalence from Church's theorem. Additional functions are needed to translate the representation into common data types, for display to people. The assumption that functions are the only primitive data types streamlines many proofs.Ĭhurch encoding is complete but only representationally. Operations can be typed using higher-ranked types, and primitive recursion is easily accessible. Nonetheless Church encoding is often used in theoretical arguments, as it is a natural representation for partial evaluation and theorem proving. Research has shown that this can be addressed by targeted optimizations, but most functional programming languages instead expand their intermediate representations to contain algebraic data types. In the untyped lambda calculus the only primitive data type is the function.Ī straightforward implementation of Church encoding slows some access operations from O ( 1 ) O(1) to O ( n ) O(n), where n n is the size of the data structure, making Church encoding impractical. The Church-Turing thesis asserts that any computable operator (and its operands) can be represented under Church encoding. Terms that are usually considered primitive in other notations (such as integers, booleans, pairs, lists, and tagged unions) are mapped to higher-order functions under Church encoding. The method is named for Alonzo Church, who first encoded data in the lambda calculus this way. The Church numerals are a representation of the natural numbers using lambda notation. In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. Representation of the natural numbers as higher-order functions
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |