4 ms·

Thank you for your kind remarks but I'm still unable to understand the proposed code. Testing the first expression in the current {lambda talk} evaluator doesn'

Thank you for your kind remarks but I'm still unable to understand the proposed code. Testing the first expression in the current {lambda talk} evaluator doesn't return anything: A) abstraction: 1: {{lambda {y} {lambda {x} {x y}}} arg} 2: {{lambda {y} _LAMB_0} arg} // where _lAMB_0 is {lambda {x} {x y}} 3: {_LAMB_1 arg} // where _LAMB_1 is {lambda {y} _LAMB_0} B) application: 1: {_LAMB_1 arg} 2: {{lambda {y} _LAMB_0} arg} 3: _LAMB_0 4: stop Well I don't understand your idea. I'm just an amateur. In this paper http://lambdaway.free.fr/lambdaspeech/?view=fabric_new http://lambdaway.free.fr/lambdaspeech/?view=fabric_new I give the eval_lambda() JS code (section 2.3. special forms evaluation) where inner lambdas are recursively evaluated without carrying arguments which are ipso facto unknown by inner lambdas. Until now I am unable to write a code which could carry them. In this page http://lambdaway.free.fr/workshop/?view=lambdacode http://lambdaway.free.fr/workshop/?view=lambdacode, following Peter Norvig (http://norvig.com/lispy.html http://norvig.com/lispy.html) I wrote a more "standard" evaluator tokenizing the code, building a nested tree and recursively evaluating it. The evaluator's main function ( var evaluate = function (x, env) {...} ) works in nested environments and lambdas naturally define closures. It's a very clever approach compared to "my" regexp based evaluation. And everything works fine ... but doesn't completely fit my needs in a wiki context: - First, as in most of languages, words must be quoted to be protected from any unwanted evaluation, - the {pre some code} container can't be used (spaces, tabs, line returns are destroyed during the tokenization), - I just can't imagine the cost of the AST approach for such a page http://lambdaway.free.fr/lambdaspeech/?view=jules_verne http://lambdaway.free.fr/lambdaspeech/?view=jules_verne containing 1228778 chars, simply copy/pasted from a text file, as it is. It's just text as in a text editor (plus some enrichments, a TOC, ...). The {lambda talk}'s evaluator flies quickly over the 1228778 chars, say 250000 words, words are just words, and has to evaluate a reduced number of function calls, about 180, until all curly braces have disappeared. PS.: I find the TXR language http://nongnu.org/txr/rosetta-solutions.html http://nongnu.org/txr/rosetta-solutions.html very, very impressive. Félicitations.

kazinator 8y ago
What seems to be going on in (A) is a kind of inside-out reduction. The inner lambda term has been replaced by the placeholder __LAMB_0, and so now it is impossible to substitute y into it. Substitution simply has has to go outside in. We consider the call{{{lambda {y} {lambda {x} {x y}}} arg}, and so the text arg is identified with y. The job is then to substitute y <- arg in the interior of the outer lambda: {lambda {y} <interior ...>}. That interior happens to be {lambda {x} {x y}}. So we need a recursive walk procedure which performs that substitution. The procedure has a list of bindings which contains {y -> arg} which it passes down. The procedure has to recognize your special forms like lambda and let so that it handles variable shadowing. Our y = arg could be shadowed by some inner y. Once we have done the substitution, then we can convert the substituted lambda to _LAMB_0. So we have: 1: input: {{lambda {y} {lambda {x} {x y}}} arg} 2: lambda is identified, and encode dinto a _LAM term: {_LAMB_0 arg} where _LAMB_0 is {lambda {y} {lambda {x} {x y}}} 3: lambda term is called, with arg: this simply substitution y = arg into its body and then producing the substituted body: {lambda {x} {x y}} -> {lambda {x} {x arg}} 4. lambda call returns this: {lambda {x} {x arg}} 5. This converts to the _LAMB_* term: _LAMB_1 There is no captured environment in the inner lambda because the text is fully substituted; we have removed the variable y. The __LAM_1 string is effectively a closure. Closures don't require external environments if we are working with strings, which are copied and pasted in place. Environments are required when the expressions contain unsubstituted variables. Alternatively to the above evaluation strategy, we could identify and convert all LAM terms upfront: 1: input: {{lambda {y} {lambda {x} {x y}}} arg} 2: all lambdas are recursively identified: {__LAMB_0 arg}, where ... _LAMB_0 = {lambda {y} _LAMB_1}, where ... _LAMB_1 = {lambda {x} {x y}} 3: arg is applied to _LAMB_0: _LAMB_0: equates "y" with "arg" and processes the body, which consists of _LAMB_1: the result is: {lambda {x} {x arg}} RULE: when a _LAMB term undergoes substitution, it produces a new _LAMB term. 4: Thus {_LAMB_0 arg} reduces to _LAMB_2, which denotes {lambda {x} {x arg}}.
- martyalain 8y ago
  Woaaaw, thank you very much for having taken time to go inside the code and for starting these new ways. I have no more excuse to say "Well, there is a life out of closure and I don't mind because my lambdas are de facto partially applicable, etc ..." I have now a lot of work to implement closure in {lambda talk}. Maybe I can do that. Thank you again.

kazinator 8y ago

What seems to be going on in (A) is a kind of inside-out reduction. The inner lambda term has been replaced by the placeholder __LAMB_0, and so now it is impossible to substitute y into it. Substitution simply has has to go outside in. We consider the call{{{lambda {y} {lambda {x} {x y}}} arg}, and so the text arg is identified with y. The job is then to substitute y <- arg in the interior of the outer lambda: {lambda {y} <interior ...>}. That interior happens to be {lambda {x} {x y}}. So we need a recursive walk procedure which performs that substitution. The procedure has a list of bindings which contains {y -> arg} which it passes down. The procedure has to recognize your special forms like lambda and let so that it handles variable shadowing. Our y = arg could be shadowed by some inner y. Once we have done the substitution, then we can convert the substituted lambda to _LAMB_0. So we have: 1: input: {{lambda {y} {lambda {x} {x y}}} arg} 2: lambda is identified, and encode dinto a _LAM term: {_LAMB_0 arg} where _LAMB_0 is {lambda {y} {lambda {x} {x y}}} 3: lambda term is called, with arg: this simply substitution y = arg into its body and then producing the substituted body: {lambda {x} {x y}} -> {lambda {x} {x arg}} 4. lambda call returns this: {lambda {x} {x arg}} 5. This converts to the _LAMB_* term: _LAMB_1 There is no captured environment in the inner lambda because the text is fully substituted; we have removed the variable y. The __LAM_1 string is effectively a closure. Closures don't require external environments if we are working with strings, which are copied and pasted in place. Environments are required when the expressions contain unsubstituted variables. Alternatively to the above evaluation strategy, we could identify and convert all LAM terms upfront: 1: input: {{lambda {y} {lambda {x} {x y}}} arg} 2: all lambdas are recursively identified: {__LAMB_0 arg}, where ... _LAMB_0 = {lambda {y} _LAMB_1}, where ... _LAMB_1 = {lambda {x} {x y}} 3: arg is applied to _LAMB_0: _LAMB_0: equates "y" with "arg" and processes the body, which consists of _LAMB_1: the result is: {lambda {x} {x arg}} RULE: when a _LAMB term undergoes substitution, it produces a new _LAMB term. 4: Thus {_LAMB_0 arg} reduces to _LAMB_2, which denotes {lambda {x} {x arg}}.

martyalain 8y ago
Woaaaw, thank you very much for having taken time to go inside the code and for starting these new ways. I have no more excuse to say "Well, there is a life out of closure and I don't mind because my lambdas are de facto partially applicable, etc ..." I have now a lot of work to implement closure in {lambda talk}. Maybe I can do that. Thank you again.