Lambda calculus sequence combinator11/19/2023 ![]() ![]() The resulting cascade of calls and responses analogizes to abstract models of computing. ![]() Hence an initial call by certain "birds" gives rise to a cascading sequence of calls by a succession of birds.ĭeep inside the forest dwells the Mockingbird, which imitates other birds hearing themselves. Each bird has a distinctive call, which it emits when it hears the call of another bird. Each species of bird in Smullyan's forest stands for a particular kind of combinator appearing in the conventional treatment of combinatory logic. Smullyan's exposition takes the form of an imaginary account of two men going into a forest and discussing the unusual "birds" (combinators) they find there (bird watching was a hobby of one of the founders of combinatory logic, Haskell Curry, and another founder Moses Schönfinkel's name means beautiful bird). It is also a gentle and humorous introduction to combinatory logic and the associated metamathematics, built on an elaborate ornithological metaphor.Ĭombinatory logic, functionally equivalent to the lambda calculus, is a branch of symbolic logic having the expressive power of set theory, and with deep connections to questions of computability and provability. It contains many nontrivial recreational puzzles of the sort for which Smullyan is well known. The clue here is that this effectively stops the computation at each step until it's actually put into use.To Mock a Mockingbird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic (1985, ISBN 0-19-280142-2) is a book by the mathematician and logician Raymond Smullyan. In the same manner (lambda args (apply (g g) args)) is the same as (g g) and you can see that by just applying substitution rules. If you have a function add1 you can make a wrapper (lambda (x) (add1 x)) that you can use instead and it will work. We know (g g) becomes a function so we just give f a function that when applied will generate the actual function and apply it. To salvage that we don't apply (g g) right away. If you look at how this would be applied with an argument you'll notice that Y never returns since before it can apply f in (f (g g)) it needs to evaluate (g g) which in turn evaluates (f (g g)) etc. Well the normal order version looks like this: (define Y So you are asking how the evaluation gets delayed. Notice the implementations is exactly the same and the difference is how the reference to itself is handled. This can be done with Z like this: ((Z (lambda (ackermann) Imagine the Ackermann function: (define ackermann Notice this version uses apply to support multiple argument functions. It's just a little more code that does exactly the same. Now the first thing that happens when this is applied is (g g) and since you can always substitute a whole application with the expansion of it's body the body of the function can get rewritten to: (define Z ![]() The applicative version of Y is often called a Z combinator: (define Z In a lazy language like Lazy Racket you can use the normal order version, but not in any of the applicative order programming languages like Scheme. ![]()
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |