[Jprogramming] Revisisting the Y combinator

Wed Nov 28 23:39:39 UTC 2018

I do not recall saying that tacitness was a requirement.
Sent from my iPhone
> On Nov 28, 2018, at 6:23 PM, Raul Miller <rauldmiller at gmail.com> wrote:
>> Hmm..
>> When I look at explanations of the Y combinator, I don't see any
> requirement that the implementations must be tacit. For example:
> https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus
>> Instead, I see an entirely symbolic representations (where, granted,
> the symbols are eventually intended to refer to implementations).
>> Put different: the use of references to memory which is not intended
> to be changed is not usually thought of as "state" even though that
> memory could be changed.
>> That said, I will agree that it's possible to think of all memory as
> "state". I think this would mean that only logic implemented purely in
> hardware is "not state".
>> That said, I will also agree that within a J environment, you aren't
> going to be able to changed unnamed function implementations while
> they're running without cheating (or, perhaps, being cheated). So, ...
> there's that.
>> Thanks,
>> -- 
> Raul
>> On Wed, Nov 28, 2018 at 5:38 PM Jose Mario Quintana
> <jose.mario.quintana at gmail.com> wrote:
>>>>> [Aside: if I remember right, you wrote the tacit version there at rosetta
>> code?]
>>>> That is right.
>>>>> After sleeping on this thread for a few days, I've finally realized
>>> that I don't have any idea what you mean by "ad hoc encodings".
>>>>>> If you have time for some questions: What does "ad hoc encodings"
>>> mean? Is that a good thing or a bad thing? Why?
>>>> As far as I can see, when the argument of Y, the higher-order function, for
>> which the product of Y is a fixed-point, is represented by means of
>> standard code associated with recursions in J then one can produce
>> relatively simple versions of Y which are, as much as possible (given the
>> lack of direct support of higher-order functions as arguments by the
>> current official interpreters), in compliance with the specifications of
>> the Rosetta Code (RC) task.
>>>> (Beware of line-wrapping)
>>>> As an illustration, this is a comparison between the slightly revised
>> version of my non-tacit version of the Y combinator for monadic recursions,
>>>> X=. 1 :'<(<,'':''),<(<1;~":0),<(":0);,(''u u`:6('',(5!:5<''u''),'')`:6
>> y'')'(1 :'u u`:6')
>>>> renamed as X to be able to distinguish it from the explicit version of Y in
>> the RC entry,
>>>> Explicit alternate implementation
>>>> https://rosettacode.org/wiki/Y_combinator#Explicit_alternate_implementation
>>>> (which I suppose you wrote).
>>>> Using recursive computations of factorials as an example,
>>>> M=. 1 :'1:`(* u@:<:)@.*'
>> M=. (5!:1)<'M'
>>>> Due to J`s aforementioned limitation, it is unavoidable the use of a
>> representation of the adverb (i.e., the higher-order function), the AR of
>> the adverb (M) is chosen as the argument for X,
>>>> M X ("0) i.11
>> 1 1 2 6 24 120 720 5040 40320 362880 3628800
>>>> This argument is closely related to usual ways to define recursive verbs,
>>>> ( $:M`:6) ("0) i.11
>> 1 1 2 6 24 120 720 5040 40320 362880 3628800
>> (f=. f M`:6) ("0) i.11
>> 1 1 2 6 24 120 720 5040 40320 362880 3628800
>>>> or, more generaly,
>>>> (f=. 3 :'f M`:6 y')("0) i.11
>> 1 1 2 6 24 120 720 5040 40320 362880 3628800
>>>> M=. 1 :'if. * y do. y * u <: y else. 1 end.'
>> M=. (5!:1)<'M'
>>>> (f=. 3 :'f M`:6 y')("0) i.11
>> 1 1 2 6 24 120 720 5040 40320 362880 3628800
>>>> In contrast, Y (as per the explicit RC J entry) is a noun (and a gerund)
>> and by itself does not produce anything,
>>>> wrap=. _66 [\ (5!:5)@:<
>>>> wrap'Y'
>> ,<(<,':'),<(<(,'0');3),<(,'0');3 21$'g=.y recur=
>> . sivelY`:6 g recur`:6 recur '
>>>> Not surprisingly, the argument for Y Ev (Ev is a name referring to `:6) is
>> also a noun (and a gerund) and by itself does not produce anything either,
>>>> wrap'almost_factorial'
>> ,<(<(<,':'),<(<(,'0');2),<(,'0');5 26$' if. (_1 {:: m) <: #m do.
>> v |. y;_1 }. m else. (y;m) Defer
>> v`'''' end. '),<(<(<,'0'),<,<2),<(<,':'
>> ),<(<(,'0');3),<(,'0');3 25$'''f n''=.y if. 0 >:
>> n do. 1 else. n * f`:6 n-1 end.'
>>>> and, it seems, its particular purpose is to be used as an argument for (Y
>> Ev).
>>>> On the one hand, regarding the recursive verbs produced by each of the
>> combinators,
>>>> v=. (Y Ev almost_factorial)Ev
>>>> is a verb,
>>>> wrap'v'
>> ((<,<(<(<,':'),<(<(,'0');2),<(,'0');5 26$' if. (_1 {:: m) <: #m d
>> o. v |. y;_1 }. m else. (y;m) De
>> fer v`'''' end. '),<(<(<,'0'),<(<,<(<(<,
>> ':'),<(<(,'0');2),<(,'0');5 26$' if. (_1 {:: m) <: #m do. v |.
>> y;_1 }. m else. (y;m) Defer v`''''
>> end. '),<(<(<,'0'),<,<2),<(<,':'),<(<(,
>> '0');3),<(,'0');3 25$'''f n''=.y if. 0 >: n do.
>> 1 else. n * f`:6 n-1 end.'),<2),<(<,':'),<(<(,'0');3),<(,'
>> 0');2 29$'''g recur''=.y (recursivelY`:6 g)`:6 r
>> ecur'),(<,<(<(<,':'),<(<(,'0');2),<(,'0');5 26$' if. (_1 {:: m) <
>> : #m do. v |. y;_1 }. m else. (y
>> ;m) Defer v`'''' end. '),<(<(<,'0'),<,<2
>> ),<(<,':'),<(<(,'0');3),<(,'0');3 25$'''f n''=.y
>> if. 0 >: n do. 1 else. n * f`:6 n-1 end.'),<3) (2 : 0) (3
>> : 0)
>> 'g recur x'=.y
>> (g`:6 recur`:6 recur)`:6 x
>> )
>>>> if. (_1 {:: m) <: #m do.
>> v |. y;_1 }. m
>> else.
>>>> (y;m) Defer v`''
>> end.
>>>> )
>>>> and this linear representation of (Y Ev almost_factorial)Ev is incomplete;
>> in other words, the verb produced is not stateless and consequently it is
>> vulnerable to reassignments,
>>>> (Y Ev almost_fibonacci)Ev ("0) i. 11
>> 0 1 1 2 3 5 8 13 21 34 55
>>>> Defer=. 1
>>>> (Y Ev almost_fibonacci)Ev ("0) i. 11
>> |syntax error
>> | (y;m)Defer v`''
>>>> Thus, the explicit entry in RC is not an implementation of the Y combinator
>> complying with the specifications.
>>>> On the other hand, the verb produced by M X is stateless and relatively
>> very simple,
>>>> u=. M X
>> wrap'u'
>> <(<,':'),<(<(,'0');1),<<;._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')
>>>> Furthermore, according to the interpreter (Y Ev almost_factorial)Ev seems
>> to be doing a lot of unnecessary stuff vs M X for the task at hand,
>>>> stp=. ] (([ ((<;._1 '|Sentence|Space|Time|Space * Time') , (, */&.:>@:(1
>> 2&{))@:(] ; 7!:2@:] ; 6!:2)&>) (10{a.) -.&a:@:(<;._2@,~) ]) [ (0 0 $
>> 13!:8^:((0 e. ])`(12"_)))@:(2 -:/\ ])@:(".&.>)@:((10{a.) -.&a:@:(<;._2@,~)
>> ]) ::(0 0&$@(1!:2&2)@:('Mismatch!'"_))) ".@:('0( : 0)'"_)
>>>> stp 11
>> (Y Ev almost_factorial)Ev("0) i.11
>> M X ("0) i.11
>> )
>> ┌──────────────────────────────────┬───────┬──────────┬────────────┐
>> │Sentence │Space │Time │Space * Time│
>> ├──────────────────────────────────┼───────┼──────────┼────────────┤
>> │(Y Ev almost_factorial)Ev("0) i.11│1242368│0.0142416 │17693.3 │
>> ├──────────────────────────────────┼───────┼──────────┼────────────┤
>> │M X ("0) i.11│250304 │0.00179289│448.768 │
>> └──────────────────────────────────┴───────┴──────────┴────────────┘
>>>> I hope it helps
>>>>>> On Mon, Nov 19, 2018 at 7:11 PM Jose Mario Quintana <
>> jose.mario.quintana at gmail.com> wrote:
>>>>> I am on vacation this week. I will have more time (and access to a PC)
>>> when I get back.
>>>>>>> On Monday, November 19, 2018, Raul Miller <rauldmiller at gmail.com> wrote:
>>>>>>>> [Aside: if I remember right, you wrote the tacit version there at rosetta
>>>> code?]
>>>>>>>> After sleeping on this thread for a few days, I've finally realized
>>>> that I don't have any idea what you mean by "ad hoc encodings".
>>>>>>>> If you have time for some questions: What does "ad hoc encodings"
>>>> mean? Is that a good thing or a bad thing? Why?
>>>>>>>> Thanks,
>>>>>>>> --
>>>> Raul
>>>>>>>>>>>>>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm