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
