[Jprogramming] Revisisting the Y combinator

Thu Nov 29 22:56:50 UTC 2018

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