[Jprogramming] Revisisting the Y combinator

Fri Nov 30 19:27:03 UTC 2018

Ok, I now see what you are saying.
And, I've updated the rosettacode explicit implementation of the combinator.
Thanks,
-- 
Raul
On Thu, Nov 29, 2018 at 5:57 PM Jose Mario Quintana
<jose.mario.quintana at gmail.com> wrote:
>> I am afraid there must be a misunderstanding somewhere. Tacit entities are
> stateless but some non-tacit entities can be stateless as well (e.g.,
> neither my version of the Y combinator (renamed as X), which I was
> discussing in my post trailing below, nor the adverbs which its arguments
> represented, nor its products were tacit; but, as far as I can see, they
> are stateless). Thus, I was not trying to imply implicitly that tacitness
> was a requirement at all.
>> The RC page for the Y combinator begins,
>> "In strict functional programming and the lambda calculus, functions
> (lambda expressions) don't have state and are only allowed to refer to
> arguments of enclosing functions. This rules out the usual definition of a
> recursive function wherein a function is associated with the state of a
> variable and this variable's state is used in the body of the function.
>> The Y combinator is itself a stateless function that, when applied to
> another stateless function, returns a recursive version of the function."
>> To me, this clearly means that, for example,
>> f=. 1:`(* f@:<:)@.*
>> and
>> f=. 3 : 'if. * y do. y * f <: y else. 1 end.'
>> are both ruled out (and f, in both cases, is a "variable's state" which "is
> used in the body of the function.").
>> You wrote:
>> > > 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.
>> However, the definition of your conjunction Defer,
>> Defer
> 2 : 0
> if. (_1 {:: m) <: #m do.
> v |. y;_1 }. m
> else.
> (y;m) Defer v`''
> end.
> )
>> is a usual definition of a recursive function and Defer is a "variable's
> state" which "is used in the body of the function." Anyway, even relying
> on J's native recursion to implement recursion your Y is relatively quite
> complicated. This could be relevant because the RC page continues,
>> "The Y combinator is the simplest of the class of such functions, called
> fixed-point combinators."
>> (Although some could regard the above statement as somewhat controversial.)
>> At any rate, if piggybacking on J's native support for recursion to
> implement recursion is not considered cheating then this tacit adverb,
>> Y=. ($:`)(`:6)
>> would be hard to beat for tacit recursions,
>> M=. (@:<:)(*`)(`:6)(1:`)(@.*)
> M=. (5!:1)<'M'
>> M Y("0) i.11
> 1 1 2 6 24 120 720 5040 40320 362880 3628800
>> N=. 1 :'(u@:<:@:<: + u@:<:)^:(1 < ])'
> N=. (5!:1)<'N'
>> N Y("0) i.11
> 0 1 1 2 3 5 8 13 21 34 55
>> For completeness, the RC page task description follows,
>> "Task
> Define the stateless Y combinator and use it to compute factorials and
> Fibonacci numbers from other stateless functions or lambda expressions.
>>> Cf
> Jim Weirich: Adventures in Functional Programming"
>> Moreover, one could upload to the entry for J on the RC page, the following,
>>> M=. 1 :'1:`(* u@:<:)@.*'
> $: M 10
> 3628800
>> N=. 1 :'(u@:<:@:<: + u@:<:)^:(1 < ])'
> $: N 10
> 55
>> wrongly claiming that, in J, the Y combinator is included as the J's
> primitive $: and
> wait until somebody complains. ;)
>> I hope it helps,
>> P.D. You seem to be surprised because I pointed out that your version does
> not implement the Y combinator. However, you said as much, if I remember
> correctly, several years ago. Did your implementation, or your mind, or
> something else change?
>>> On Wed, Nov 28, 2018 at 6:53 PM Raul Miller <rauldmiller at gmail.com> wrote:
>> > You didn’t say that explicitly, but the only "statefulness" which I saw
> > required changing the definitions associated with names. And the only way
> > to avoid that kind of change is with tacit code.
> >
> > Or did I overlook something important?
> >
> > Thanks,
> >
> > —
> > Raul
> >
> > On Wednesday, November 28, 2018, <jose.mario.quintana at gmail.com> wrote:
> >
> > > 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
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm