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
