Sorry about the post in the wrong thread. There should be some "Y combinator" at work in here.
f=: 13 :',([:+/\|.)^:2^:(<`(0,1:))y' f 5 0 1 1 2 3 5 8 13 21 34 f 6 0 1 1 2 3 5 8 13 21 34 55 89 I can't seem to stop at 55. Any ideas? Linda -----Original Message----- From: Programming <[email protected]> On Behalf Of Linda Alvord Sent: Friday, November 9, 2018 12:56 AM To: [email protected] Subject: Re: [Jprogramming] Revisisting the Y combinator Jose, I'm not sure I'll be able to follow your ideas. !i.11x 1 1 2 6 24 120 720 5040 40320 362880 3628800 However, Fibohacci would be a nice primitive. Linda -----Original Message----- From: Programming <[email protected]> On Behalf Of 'Pascal Jasmin' via Programming Sent: Thursday, November 8, 2018 10:41 PM To: [email protected] Subject: Re: [Jprogramming] Revisisting the Y combinator Interesting, thank you Jose. I'll note that if the argument to Y is not an ar of an adverb then J (806 and 807) will crash when the result verb is called. ________________________________ From: Jose Mario Quintana <[email protected]> To: [email protected] Sent: Thursday, November 8, 2018 7:07 PM Subject: [Jprogramming] Revisisting the Y combinator It has been very quiet here lately. To compensate, this is a very long post which only a few members might find interesting. :) The Y combinator (aka, fixed-point combinator) is a showpiece which demonstrates the strength of a functional programming language by implementing functional stateless anonymous recursion (independently of any potential native facility which might be already supported by the functional language). It has been entertained before in this forum. Moreover, for the Rosetta Code task, Y combinator https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Frosettacode.org%2Fwiki%2FY_combinator&data=02%7C01%7C%7C2f1a95ae6b404f47dbe808d646081a47%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773397940913055&sdata=aeln3OR0Wg10L9oPUkk8Qaia%2FzU9I9UEMy9e84qN%2Fxc%3D&reserved=0 there are two J entries, one tacit and one explicit, J https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Frosettacode.org%2Fwiki%2FY_combinator%23J&data=02%7C01%7C%7C2f1a95ae6b404f47dbe808d646081a47%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773397940913055&sdata=QS9sxKthtlOFXGLtvYLPuZmJyKVg0bfhe0hkzBWOEfA%3D&reserved=0 However, although those entries implement anonymous recursion, both rely on ad-hod encodings. At any rate, I have never been fully satisfied with the tacit version and decided to try again and I produced alternative versions (which are shown later). J provides native support for anonymous recursion definition of tacit verbs; the classic factorial function example can be defined as, 1:`(* $:@:<:)@.* or, naming it, as, u=. 1:`(* u@:<:)@.* The right-hand side (RHS) of =. represents a mapping (i.e., a function) of the verb u into another verb (1:`(* u@:<:)@.*); yet, the syntax means that u is a fixed-point of the mapping implied by the RHS verb (1:`(* u@:<:)@.*). Adverbs can map a verb into a verb; a mapping for the factorial function can be defined, for example, equivalently as, '1:`(* u@:<:)@.*' (1 :) or (@:<:) (*`) (`:6) (1:`) (@.*) or 'if. * y do. y * u <: y else. 1 end.' (1 :) and so forth. Typically, a Y combinator takes a mapping as an argument and produces an anonymous function which is a fixed-point under that mapping. Unfortunately, in J, an adverb cannot be an argument for anything; however, one can just use a representation; for example, the relatively reliable atomic representation (AR). Continuing with the factorial example, if M is an AR of any of the adverbs mentioned above (or any another equivalent adverb) then M Y should produce an anonymous factorial recursive verb, not based on $:, for instance, M=. (@:<:) (*`) (`:6) (1:`) (@.*) M=. (5!:1)<'M' M Y("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 Thus, the task is to define a functional anonymous stateless version of the Y adverb and use it to compute recursively factorials and Fibonacci numbers also in a functional anonymous stateless style. Ideally, any (local) names contained in Y and the anonymous verbs produced by Y should should refer only to arguments; however, local names are generally considered acceptable as long as values are assigned but not reassigned to them. Some solutions are shown after several blank lines... (Beware of line-wrapping.) A non-tacit solution is, Y=. '(5!:1<''v'')v=. 1 : (''u u`:6('',(5!:5<''u''),'')`:6 y'')'(1 :) NB. Factorials... M=. '1:`(* u@:<:)@.*' (1 :) M=. (5!:1)<'M' M Y("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 M=. (@:<:) (*`) (`:6) (1:`) (@.*) M=. (5!:1)<'M' M Y("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 M=. 'if. * y do. y * u <: y else. 1 end.' (1 :) M=. (5!:1)<'M' M Y("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 The verbs produced by M Y are anonymous recursive verbs which are (n a) trains where the noun n is the AR of the adverb a, for example, M Y <(<,':'),<(<(,'0');1),<(,'0');,:'u u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,:''if. * y do. y * u <: y else. 1 end.'')`:6 y' (1 : 'u u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,:''if. * y do. y * u <: y else. 1 end.'')`:6 y') (By the way, their linear representations are missing parentheses around the noun n.) NB. Fibonacci numbers... N=. '(u@:<:@:<: + u@:<:)^:(1 < ])' (1 :) N=. (5!:1)<'N' N Y("0) i.11 0 1 1 2 3 5 8 13 21 34 55 Once the trick is known one can derive a related XY combinator capable of implementing ambivalent recursion which embeds monadic and dyadic recursions, XY=. '(5!:1<''v'')v=. 1 : ((''u u`:6('',(5!:5<''u''),'')`:6 y''),(10{a.),'':'',(10{a.),''x(u u`:6('',(5!:5<''u''),'')`:6)y'')' (1 :) NB. Ambivalent recursion... A=. '1:`(<: u <:)@.* : (+ + 2 * u@:])' (1 :) A=. (5!:1)<'A' A XY ("0) i.11 NB. OEIS A097813 1 2 6 16 38 84 178 368 750 1516 3050 A XY "0/~ i.11 2 5 14 35 80 173 362 743 1508 3041 6110 3 6 15 36 81 174 363 744 1509 3042 6111 4 7 16 37 82 175 364 745 1510 3043 6112 5 8 17 38 83 176 365 746 1511 3044 6113 6 9 18 39 84 177 366 747 1512 3045 6114 7 10 19 40 85 178 367 748 1513 3046 6115 8 11 20 41 86 179 368 749 1514 3047 6116 9 12 21 42 87 180 369 750 1515 3048 6117 10 13 22 43 88 181 370 751 1516 3049 6118 11 14 23 44 89 182 371 752 1517 3050 6119 12 15 24 45 90 183 372 753 1518 3051 6120 NB. OEIS A097813 - main diagonal NB. OEIS A050488 = A097813 - 1 - adyacent upper off-diagonal The non-tacit version of Y is a transcription of a wicked tacit version tacit solution which I produced using a fork of J which should not be mentioned in this forum. Nevertheless, a verbose wicked tacit version can still be produced using j807. The following assumes that the J Wicked Toolkit [0] has been run in immediate execution mode but a self-contained script is shown afterward. NB. Y combinator... (9!:3)5 2 NB. Turning on the linear and boxed representations An alternative to the AR of an adverb is verbing the adverb and use this verb v as the argument for a Y combinator adverb. The sentence v Y produces the fixed-point verb; v Y is the verb (v body), where body is the adverb, body=. (_:@:((< amper ])@:>@:[) of ]) Adv which has a bonded left argument that happens to be (v body) boxed (the cute verb _: in the context of Adv is akin to u in the context of (1 :)). Thus, Y=. (< amper ]) o (ver o train <'body') adv v Y (<v@:((< amper ])@:>@:[) of ])&(v@:((< amper ])@:>@:[) of ]) ┌─────────────────────────────┬─┬───────────────────────────────────────┐ │┌───────────────────────────┐│&│┌────────────────────────────────┬──┬─┐│ ││v@:((< amper ])@:>@:[) of ]││ ││┌─┬──┬─────────────────────────┐│of│]││ │└───────────────────────────┘│ │││v│@:│┌──────────────────┬──┬─┐││ │ ││ │ │ │││ │ ││┌───────────┬──┬─┐│@:│[│││ │ ││ │ │ │││ │ │││┌─┬─────┬─┐│@:│>││ │ │││ │ ││ │ │ │││ │ ││││<│amper│]││ │ ││ │ │││ │ ││ │ │ │││ │ │││└─┴─────┴─┘│ │ ││ │ │││ │ ││ │ │ │││ │ ││└───────────┴──┴─┘│ │ │││ │ ││ │ │ │││ │ │└──────────────────┴──┴─┘││ │ ││ │ │ ││└─┴──┴─────────────────────────┘│ │ ││ │ │ │└────────────────────────────────┴──┴─┘│ └─────────────────────────────┴─┴───────────────────────────────────────┘ It is apparent from the above boxed representation that when (v Y) is provided with an argument then it first reproduces and maps itself according the adverb represented by v; in other words (v Y) is a fixed-point under the map represented by v. This version of the Y combinator makes itself and its products vulnerable to side effects because they contain names but this can be fixed, body=. (_:@:((< amper ])@:>@:[) of ]) f.Adv Y=. (< amper ]) o (ver o fix'body') f.adv NB. Factorial... M=. 1:`(* _:@:<:)@.* Adv v=. ver o fix'M' v Y("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 wrap=. _66 ]\ 5!:5@:< wrap'Y' ("_)(((`'')(&((< [:^:(0:`&) ])@:([:^:(0:`(("_)(((`'')(&([:^:(0:``: )&6@:(<@:((,'0') ,&:< ]) [^:('_:' -: ])L:_ 0 (,<(<,'3'),<(<(<'@:') ,<(<'_:'),<(<'@:'),<(<(<'@:'),<(<(<,'3'),<(<,'<'),(<(<'^:'),<(<'[: '),<(<,'0'),<;:'0:&'),<,']'),<,'>'),<,'['),(<(<'@:'),<(<(<,'&'),<( <(<'^:'),<(<'[:'),<(<,'0'),<;:'0:`:'),<(,'0');6),<(<,'3'),<(<,'[') ,(<,';'),<(<'@:'),<(<(<'@:'),<(<,'<'),<(<,'3'),<(<<;._1 ' 0 0'),(< (<'&:'),<;:',<'),<,']'),<,']'),<,']')"_)@:([:^:(0:``:)&6@:(<@:((0; 1;0)&({::))))@:[)))((`_)(`:6))))))@:([:^:(0:``:)&6@:(<@:((0;1;0)&( {::))))@:[)))((`_)(`:6))) t=. v Y wrap't' (<v@:((< [:^:(0:`&) ])@:>@:[) [:^:(0:``:)&6@:([ ; <@:((,'0') ,&:< ])@:]) ])&(v@:((< [:^:(0:`&) ])@:>@:[) [:^:(0:``:)&6@:([ ; <@:((,' 0') ,&:< ])@:]) ]) A shorter version of Y is, body=. (@: ((< amper ]) o >x)) (`(of f.`])) (`:6) Y=. (< amper ]) o (ver o fix'body') f.adv wrap'Y' ("_)(((`'')(&((< [:^:(0:`&) ])@:([:^:(0:`(((@:((< [:^:(0:`&) ])@:> @:[))(`([:^:(0:``:)&6@:([ ; <@:((,'0') ,&:< ])@:])`])))(`:6))))@:( [:^:(0:``:)&6@:(<@:((0;1;0)&({::))))@:[)))((`_)(`:6))) v Y("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 A version Z that takes the AR of an adverb can be easily derived from Y, Z=. ver o train f.adv 'Y'f. wrap'Z' (("_)(((`'')(&([:^:(0:`((0:`)([:^:)))@:(<@:((,'0') ,&:< ]))@:([:^: (0:``:)&6)@:([:^:(0:``:)&6@:(<@:((0;1;0)&({::))))@:[)))((`_)(`:6)) ))(("_)(((`'')(&((< [:^:(0:`&) ])@:([:^:(0:`(((@:((< [:^:(0:`&) ]) @:>@:[))(`([:^:(0:``:)&6@:([ ; <@:((,'0') ,&:< ])@:])`])))(`:6)))) @:([:^:(0:``:)&6@:(<@:((0;1;0)&({::))))@:[)))((`_)(`:6)))) NB. Factorials... M=. (5!:1)<'M' M Z("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 M=. 'if. * y do. y * u <: y else. 1 end.' (1 :) M=. (5!:1)<'M' M Z("0) i.11 1 1 2 6 24 120 720 5040 40320 362880 3628800 NB. Fibonacci numbers... N Z("0) i.11 0 1 1 2 3 5 8 13 21 34 55 The non-tacit version of Y is a transcription of Z changing what needs to be changed; that is, Boxed verb -> AR of adverb verb -> adverb > -> `:6 < -> AR (5!:1) and so forth. The self-contained script follows... NB. DO NOT TRY TO LOAD THIS SCRIPT!!! NB. Instead, run it using 0!:0, or similar, or paste NB. it on an J editing window and use Crtl-A Crtl-E NB. Tacit Y... NB. Utilities... o=. @: x=. @:[ y=. @:] c=. "_ ar=. 5!:1@:< NB. Atomic representation an=. <@:((,'0') ,&:< ])f. NB. Atomizing (monadic verb) Ver=. (0:`)([:^:) NB. Verbing (the atomic representations of) adverbs or NB. conjunctions as monadic or dyadic verbs Ver=. ((5!:1)@:<'Ver')Ver NB. Ver verbing itself! ver=. Ver o an f. 'evoke fix amper'=. < o Ver"0 o ;: '`: f. &' train=. evoke&6 f. of=. train o ([ ; an y) f. NB. NB. Evaluating a verb-noun gerundial (or similar) form assert (( *:`'') of 1 2 3) -: 1 4 9 assert ((< o train <'*:') of 1 2 3) -: 1 4 9 NB. adv... d=. (a0=. `'')(a1=. (@:[) ((<'&')`) (`:6))(a2=. (`(<(":0);_)) (`:6)) av=. ((ar'a0')`)(`(ar'a1'))(`(ar'a2') ) (`:6) af=. an o fix f. NB. Atomizing after fixing a word (monadic verb) aw=. < o ((0;1;0)&{::) NB. Fetching the atomic representation (monadic verb) a3=. (o (train o aw f.)) ('av'f.) NB. train o aw gets the (noun or verb) argument adv=. train o ((af'c') ; ] ; (af'a3')c) f.av erase'd a0 a1 a2 av' assert ('toJ' < o fix f.adv) -: (< o fix'toJ') NB. Adv... rv=. [^:((,'_:') -: ])L:_ 0 Adv=. (`'') ("_) (((an f.)`(rv f.))`) (`:6) (train f. @:) f.adv erase'rv' NB. Y combinator... (9!:3)5 2 NB. Turning on the linear and boxed representations body=. (_:@:((< amper ])@:>@:[) of ]) Adv Y=. (< amper ]) o (ver o train <'body') adv v Y body=. (_:@:((< amper ])@:>@:[) of ]) f.Adv Y=. (< amper ]) o (ver o fix'body') f.adv NB. Factorial... M=. 1:`(* _:@:<:)@.* Adv v=. ver o fix'M' v Y("0) i.11 wrap=. _66 ]\ 5!:5@:< wrap'Y' t=. v Y wrap't' body=. (@: ((< amper ]) o >x)) (`(of f.`])) (`:6) Y=. (< amper ]) o (ver o fix'body') f.adv wrap'Y' v Y("0) i.11 Z=. ver o train f.adv 'Y'f. wrap'Z' NB. Factorials... M=. (5!:1)<'M' M Z("0) i.11 M=. 'if. * y do. y * u <: y else. 1 end.' (1 :) M=. (5!:1)<'M' M Z("0) i.11 NB. Fibonacci numbers... N Z("0) i.11 Reference [0] J Wicked Toolkit https://nam04.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.2bestsystems.com%2Ffoundation%2Fj%2FJx.zip&data=02%7C01%7C%7C2f1a95ae6b404f47dbe808d646081a47%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773397940913055&sdata=qzYg1LEuSGB%2FtrjGMOO%2FG%2BJAD7mJ5Lv5BpzH3FMWNO8%3D&reserved=0 \Jx\J\J Wicked Toolkit.ijs ---------------------------------------------------------------------- For information about J forums see https://nam04.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7C2f1a95ae6b404f47dbe808d646081a47%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773397940913055&sdata=BW53%2FitjlkdM1t2TXhXtPIn4hXaCD%2BI4GmSHhfegQcA%3D&reserved=0 ---------------------------------------------------------------------- For information about J forums see https://nam04.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7C2f1a95ae6b404f47dbe808d646081a47%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773397940913055&sdata=BW53%2FitjlkdM1t2TXhXtPIn4hXaCD%2BI4GmSHhfegQcA%3D&reserved=0 ---------------------------------------------------------------------- For information about J forums see https://nam04.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7C2f1a95ae6b404f47dbe808d646081a47%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773397940913055&sdata=BW53%2FitjlkdM1t2TXhXtPIn4hXaCD%2BI4GmSHhfegQcA%3D&reserved=0 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
