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 <[email protected]> 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 <[email protected]> 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, <[email protected]> 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 <[email protected]> > > 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 > > > > <[email protected]> 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 < > > > >> [email protected]> 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 <[email protected]> > > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
