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
