OTOH the most intuitive solution in my mind is a "thin" fixed-point combinator, which solves the linear equation by finding its fixed point. The currently known best solution is to translate the whole linear equation algorithm into lambda calculus that results in a "fat" combinator, and it is specific to linear equations not fixed points. If direct application of a fixed-point combinator (to the Church encoding of the linear equations) doesn't work, what is the most intuitive way of doing so in lambda calculus?Įdit. work means the combinator terminates on the input and returns a meaningful result.īecause lambda calculus is Turing-complete, it should be able to solve such equations (our computers can). How do we characterize the class of functions that work with these combinators?Įdit. So we know they work with some, but not all functions. Y and Z combinators work with G but not F. What is a high-level description of the reason why this method fails?Īre there other fixed-point combinators that can solve this equation?
But after running this program, both Y and Z combinators enter an infinite loop (marked as err). If the combinator is clever, it may return one which is a solution. The way it tries to solve this problem is to define F(x) = 2 - x (in Church encoding) then use a combinator to compute its fixed point. Then it tries to find a solution to the arithmetic equation x = 2 - x using functional programming. (define G (lambda (_) (lambda (x) ((sub two) x))))Īs commented, this program first defines some numerals in Church encoding, some arithmetic operators on these numerals as well as Y and Z combinators. (define sub (lambda (m) (lambda (n) ((n pred) m)))) (define two (lambda (f) (lambda (x) (f (f x))))) (define one (lambda (f) (lambda (x) (f x)))) (define zero (lambda (f) (lambda (x) x))) No need for separate _fact declaration so inline: let setup = f =>īut what I've derived is: let setup = f =>ĭefining fact in terms of either seems equivalent in behavior.The question is about this Racket program: #lang lazy Rename fact to setup and abstract _fact in body by replacing with parameter f let _fact = Separate lexical scopes so safe to do: let _fact = Rename to the same variable to discover a pattern. The usage of innerFact and self look suspiciously similar. Convert let declaration to lambda expression let _fact = Move self-application from caller to body let _fact = Separate the factorial expression let _fact = f => n =>Ĩ. Declare factorial function let fact = n => Here are the steps I performed (in JavaScript) 1. What did I derive? Did I make a subtle mistake? I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator.
0 kommentar(er)
