[Jprogramming] Revisisting the Y combinator

Tue Nov 13 00:06:35 UTC 2018

On Thu, Nov 8, 2018 at 10:41 PM 'Pascal Jasmin' via Programming <
programming at jsoftware.com> wrote:
>>>> 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.
>>Right Pascal, perhaps I should have warned that one should be very careful
with this stuff unless one likes to watch J crashing, as I do. ;) A
saying or its variants has been mentioned a few times in this forum before:
"Where there is great power there is great responsibility."
One can easily crash the interpreters even when the version of Y is not
wicked and even if its argument is the AR of an adverb.
******************* SPOILER ALERT! *******************
 Y=. '(5!:1<''v'')v=. 1 : (''u u`:6('',(5!:5<''u''),'')`:6 y'')'(1 :)
and consider a J version of Curry's paradoxical combinator (C Y) where
 C=. '-.@:u'(1 :)
 C=. (5!:1)<'C'
the verb (C Y) is self-denying because for a boolean argument it says if
its product is true (1) then it is false (0) and vice-versa.
So, what does J do with the sentence C Y 0? It crashes! It also crashes
with its tautological converse when -.@:u is replaced by u,
C=. 'u'(1 :)
C=. (5!:1)<'C'
meaning the product (C Y) is the same as the product of (C Y). There is
really no mystery here; both instances are examples of runaway recursions.
By the way,
 t=. C Y
is the shortest example so far, although I have not tried much, of the
linear representation (LR) bug I mentioned,
 (5!:5)<'t'
<(<,':'),<(<(,'0');1),<(,'0');,:'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y' (1 : 'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y')
 <(<,':'),<(<(,'0');1),<(,'0');,:'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y' (1 : 'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y')
|syntax error
| <(<,':'),<(<(,'0');1),<(,'0');,:'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y'(1 :'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y')
A proper LR is,
 (<(<,':'),<(<(,'0');1),<(,'0');,:'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y') (1 : 'u
u`:6(<(<,'':''),<(<(,''0'');1),<(,''0'');,.''u'')`:6 y')
Now, the weird wicked world can be spooky. The following short version of
the script runs; however, uncommenting the line,
NB. (9!:3)2 NB. Turning on only the boxed representation
causes J to crash. That is correct: if you ask j807 to do less it does not
react very well (apparently j806 acts differently). In any case, it seems
that j807 will be the last version of Jsoftware interpreters which allow
wicked spells.
"Absolute power corrupts absolutely." :)
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
NB. (9!:3)2 NB. Turning on only the boxed representation
body=. (_:@:((< amper ])@:>@:[) of ]) Adv
Y=. (< amper ]) o (Ver<'body') adv
v Y
body=. (_:@:((< amper ])@:>@:[) of ]) f.Adv
Y=. (< amper ]) o (ver o fix'body') f.adv
M=. 1:`(* _:@:<:)@.* Adv
v=. ver o fix'M'
v Y("0) i.11
wrap=. _66 ]\ 5!:5@:<
wrap'v'