I do not recall making the statement that someone in particular was "suggesting J is weak or in-efficient in solving 'functional programming' problems." However, I noticed that a discussion on TCO and its impact on using recursion morphed to "how can one implement algorithms that needs recursion in J" to "[the Ackermann's function] looks to be so fundamentally recursive that it may be impossible to do it otherwise" to a vague assertion that this function is not solvable in J; see http://www.jsoftware.com/pipermail/programming/2009-May/014712.html http://www.jsoftware.com/pipermail/programming/2009-May/014721.html http://www.jsoftware.com/pipermail/programming/2009-May/014723.html http://www.jsoftware.com/pipermail/programming/2009-May/014724.html http://www.jsoftware.com/pipermail/programming/2009-May/014726.html My post, with the exception of the first paragraph, was mean to show Gary Ng and Devon that: 0. There are function-level alternatives for coding the Ackermann functions apart from $:. 1. Those alternatives do not appear to involve open-ended tacit iterations of the form ^:_ 2. The Ackermann function is as “solvable” in function-level J just as well as it might be in other programming languages. 3. I have strong suspicion, reinforced by Roger's comment (thank you Roger for refreshing the memory of an old conversation), that the Ackermann function is not 'TCOtable' anyway. Actually, I appreciate most of what Gary Ng and Devon wrote individually and in hindsight perhaps I should have written "potential implicit suggestion" instead of "implicit suggestion" in the last paragraph of my post. The first paragraph was mean to convey that from my function-level programming vantage point (which seems to be close to Raul Miller's and away from Tracy Harms' and your 'functional programming' viewpoint): 0. The existent function-level programming facilities currently available in J are (Turing) complete. 1. At least one large production trading system coded in a function-level programming fashion has been operating for years without incidents or regrets. I try to follow the Wikipedia descriptions of 'function-level programming' and 'functional programming' when I refer to them (for example, a 'function-level program' is a 'functional program' but the converse does not hold necessarily). So, from my perspective I would not say 'J is not a language for serious functional programming' but I think I understand why from yours you would (did?) say it. Sure, J is not a typical functional programming language; then again, J is not a typical programming language. I just hope and guess we all agree that, regardless of the personal programming style, J is for joy!
________________________________ From: bill lam <[email protected]> To: [email protected] Sent: Tuesday, May 19, 2009 6:46:29 PM Subject: Re: [Jprogramming] tail recursion/TCO? I can see no one in this thread including myself suggesting J is weak or in-efficient in solving 'functional programming' problems. I only mentioned that J lacked features of 'functional programming' language as that being taught in computer course 101. On Tue, 19 May 2009, Jose Mario Quintana wrote: > > I can only guess what "serious functional programming" means but as far as I > know J provides, in principle, sufficient means to code any computable > function in a function-level programming fashion; in practice, some > colleagues and I have been comfortably coding and maintaining a quantitative > trading system for many years in this fashion (actually, in a 'tacit-level' > programming fashion since we often bring into play some useful non-functional > primitives such as ::, (1!:1), and ?). > Regarding recursion, tail recursion and the Ackermann function, I know that > the latter is no stranger to this forum and it has been coded and recoded > several times in various styles and the issue, as Roger noted, is that the > numbers in the first column (or any column) grow extremely fast. This is no > accident, the Ackermann function is an example (see > http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm ) of a computable > function that "grows faster than any primitive recursive function" and > explains why the representation (not to mention the computations involved) of > the outputs are problematic. > The following are some of the forum implementations that I know well: > Within the limitations of floating point representations and J’s treatment of > _ the Ackermann function can be simply coded "cheating" as, > Acke=. >:@]`(2&+...@])`(3&+@(2&*)@])`(2&^&.(3&+)@])`({&13 65533 _@(1&= + 2 > * 1&<)"0...@])`({&65533 _@(0&<)"0...@])@.[ ::(_"0) > Acke"0 _~ i.15 > 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 > 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 > 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 > 5 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765 65533 131069 > 13 65533 _ _ _ _ _ _ _ _ _ _ _ _ _ > 65533 _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ > (see http://www.jsoftware.com/pipermail/programming/2007-March/005443.html ) > It can be coded recursively in disguise (showing the inputs and outputs at > each recursive call) using apply (128!:2), > Ackermann=. [: '[: (] [ [: 1!:2&2 ]) [: 1:`([: >: 0&{:: ([: (0&{:: 128!:2 > ]) ;) 0: , [: <: 2&{::)`(0&{:: ([: (0&{:: 128!:2 ]) ;) ([: <: 1&{::) , > 1:)`(0&{:: ([: (0&{:: 128!:2 ]) ;) ([: <: 1&{::) , 0&{:: ([: (0&{:: 128!:2 ]) > ;) 1&{:: , [: <: 2&{::)@.((1"_ {:: ]) ([: #. ,&*/) 2&{::) [: (] [ [: ([: > 1!:2&2 >) 1 2"_ { ]) ([ ; [: [&.> ])&>/'&([: (0&{:: 128!:2 ]) ;) , > 1 Ackermann 2 > 1 2 > 1 1 > 1 0 > 0 1 > 0 0 > 1 > 2 > 2 > 0 2 > 0 1 > 0 0 > 1 > 2 > 3 > 3 > 0 3 > 0 2 > 0 1 > 0 0 > 1 > 2 > 3 > 4 > 4 > 4 > (see http://www.jsoftware.com/pipermail/general/2005-March/020855.html ) > It can also be coded by generating the verb that computes the results for a > given row an 'applying' it (using the properties that Roger pointed out; see > also_http://www.jsoftware.com/pipermail/general/2006-January/026196.html ) > and http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm ), > header=. <@(<;._1@('`'&,)@('>:`(2&+&.(3&+))`(2&*&.(3&+))`(2&^&.(3&+))'"_)) > 1} ] > next=. '-&3@:(] ('"_ , ] , ')&.(-&3)@:]^:(>:@:[) 4:)'"_ > iter=. (0&({::) {:: 1&({::)) ::(0&({::) next@:]^:([ - 3:) _1: {:: 1&({::)) > Ack=. ((iter @: header @: ('.'&(] , ;:@:[)@:<))@[ (128!:2) ])f. > Ack > (0&({::) {:: 1&({::)) ::(0&({::) ('-&3@:(] ('"_ , ] , ')&.(-&3)@:]^:(>:@:[) > 4:)'"_)@:]^:([ - 3:) _1: {:: > 1&({::))@:(<@(<;._1@('`'&,)@('>:`(2&+&.(3&+))`(2&*&.(3&+))`(2&^&.(3&+))'"_)) > 1} ])@:('.'&(] , ;:@:[)@:<)@[ 128!:2 ] > Ack"0 _~ i.8 > 1 2 3 4 5 6 7 8 > 2 3 4 5 6 7 8 9 > 3 5 7 9 11 13 15 17 > 5 13 29 61 125 253 509 1021 > 13 65533 _ _ _ _ _ _ > 65533 _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ > _ _ _ _ _ _ _ _ > Where the generated verbs corresponding to each row are, > (iter @: header @: ('.'&(] , ;:@:[)@:<)) ("0) i.8 > >: > > > (2&+&.(3&+)) > > (2&*&.(3&+)) > > (2&^&.(3&+)) > > -&3@:(] ((2&^&.(3&+)))&.(-&3)@:]^:(>:@:[) > 4:) > > -&3@:(] (-&3@:(] ((2&^&.(3&+)))&.(-&3)@:]^:(>:@:[) 4:))&.(-&3)@:]^:(>:@:[) > 4:) > -&3@:(] (-&3@:(] (-&3@:(] ((2&^&.(3&+)))&.(-&3)@:]^:(>:@:[) > 4:))&.(-&3)@:]^:(>:@:[) 4:))&.(-&3)@:]^:(>:@:[) > 4:) > -&3@:(] (-&3@:(] (-&3@:(] (-&3@:(] ((2&^&.(3&+)))&.(-&3)@:]^:(>:@:[) > 4:))&.(-&3)@:]^:(>:@:[) 4:))&.(-&3)@:]^:(>:@:[) 4:))&.(-&3)@:]^:(>:@:[) 4:) > > Thus, J allows for a variety of implementations (in addition to the plain > recursive form) of the Ackermann function some of which could also be adapted > to use extended precision representation but in the end J will be overwhelmed > and presumably any other programming language will be as well. > In any case, I find interesting the implicit suggestion in this thread that J > is weak because is lacking a tail recursion facility and cannot handle the > computations of the Ackermann function. I am by no means an expert on tail > recursion and non-primitive recursive functions but I strongly suspect that > the Ackermann function is not even suitable for a tail recursion > implementation. Am I wrong? > > > > > > > > > ________________________________ > From: Raul Miller <[email protected]> > To: Programming forum <[email protected]> > Sent: Sunday, May 17, 2009 4:28:39 PM > Subject: Re: [Jprogramming] tail recursion/TCO? > > On Sun, May 17, 2009 at 10:49 AM, bill lam <[email protected]> wrote: > > On Sat, 16 May 2009, Raul Miller wrote: > >> On Sat, May 16, 2009 at 10:59 PM, bill lam <[email protected]> wrote: > >> > I would say 'J is not a language for serious functional programming' > >> > since J lacks all features that present in modern fp such as lazy > >> > evaluation, infinite list, abstract type, functional compositions > >> > other than adverb/conjunction and fork/hook. > >> > >> And I suppose I would say that "serious functional programming" > >> seems to have been rooted in misunderstanding. See notes > > > > I don't think that I misunderstood. Today (or perhaps from 20 years > > ago [1]) FP mean languages that similar to haskell or ml, definitely not > > lisp. > > I was speaking of the design of "functional programming languages", > in terms http://www.stanford.edu/class/cs242/readings/backus.pdf > > I did not mean to imply that your characterization of J as a > language which does not fit that design was based incorrect. > I think you are correct that J does not fit that design. But > I think the design itself was misguided (though not entirely > useless). > > I have similar feelings about the design of object oriented > databases (which seem to be rooted in a mistake C.J. Date > made, when he claimed that objects and relational tables were > incompatible). The resulting technology is not useless, but > since it is based on a misunderstanding it contains elements > which are misguided in character. > > -- > 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 -- regards, ==================================================== GPG key 1024D/4434BAB3 2008-08-24 gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3 唐詩277 柳中庸 征人怨 歲歲金河復玉關 朝朝馬策與刀環 三春白雪歸青塚 萬里黃河繞黑山 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
