> ... 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?
I believe TCO does not handle double-recursions. To handling functions like Fibonacci you have to first convert it into a single recursion, then make the recursive call to be the last operation. (Making the recursive call the last operation is the defining characteristic of tail recursion.) ----- Original Message ----- From: bill lam <[email protected]> Date: Tuesday, May 19, 2009 15:53 Subject: Re: [Jprogramming] tail recursion/TCO? To: [email protected] > 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. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
