[Jprogramming] Revisisting the Y combinator

Fri Nov 9 05:56:27 UTC 2018

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 <programming-bounces at forums.jsoftware.com> On Behalf Of 'Pascal Jasmin' via Programming
Sent: Thursday, November 8, 2018 10:41 PM
To: programming at jsoftware.com
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 <jose.mario.quintana at gmail.com>
To: programming at jsoftware.com 
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://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Frosettacode.org%2Fwiki%2FY_combinator&data=02%7C01%7C%7C543ddb9bfb874774c37008d645f53c82%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773316914761401&sdata=XLH%2By2YIZyBLE0IT4mcs7cPkNREiNYoWkeg3NMSZLes%3D&reserved=0
there are two J entries, one tacit and one explicit,
J
https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Frosettacode.org%2Fwiki%2FY_combinator%23J&data=02%7C01%7C%7C543ddb9bfb874774c37008d645f53c82%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773316914761401&sdata=RJF2k%2FOD1Ye3ae9RYJPaIIASBYIgJNY3kPkRSalyf4A%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://eur01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.2bestsystems.com%2Ffoundation%2Fj%2FJx.zip&data=02%7C01%7C%7C543ddb9bfb874774c37008d645f53c82%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773316914761401&sdata=%2BsBXPqCdgTWe7JkSQSYuwhyrLy%2FGX%2BbGYzrCkP0EHYI%3D&reserved=0
 \Jx\J\J Wicked Toolkit.ijs
----------------------------------------------------------------------
For information about J forums see https://eur01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7C543ddb9bfb874774c37008d645f53c82%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773316914761401&sdata=osr%2BIDYaw4jRBE18svtcNP9%2Brg37whWcFrBZ8yDLouI%3D&reserved=0
----------------------------------------------------------------------
For information about J forums see https://eur01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7C543ddb9bfb874774c37008d645f53c82%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636773316914761401&sdata=osr%2BIDYaw4jRBE18svtcNP9%2Brg37whWcFrBZ8yDLouI%3D&reserved=0