On recursive procedures

[rickyboy]

If I load the contents of http://newlisp.org/index.cgi?roman_numbers_generator in newlisp, I can time it like this:

Code: Select all

> (time (roman 2006) 1000)
470

A version with less call overhead, but still recursive, will yield:

Code: Select all

(define (roman* n val rep vrlist acc)
  (if (not val)
      (roman* n ((*ROMAN* 0) 0) ((*ROMAN* 0) 1) (1 *ROMAN*) "")
      (= n 0)
      acc
      (< n val)
      (roman* n ((vrlist 0) 0) ((vrlist 0) 1) (1 vrlist) acc)
      (roman* (- n val) val rep vrlist (string acc rep))))

> (time (roman* 2006) 1000)
266

Of course, as you know, the best performing version is the one with no extra call overhead:

Code: Select all

(define (roman** n)
  (let ((val ((*ROMAN* 0) 0))
        (rep ((*ROMAN* 0) 1))
        (vrlist (1 *ROMAN*))
        (acc ""))
    (until (= n 0)
      (cond ((< n val)
             (set 'val ((vrlist 0) 0) 'rep ((vrlist 0) 1))
             (pop vrlist))
            (true
             (set 'acc (string acc rep) 'n (- n val)))))
    acc))

> (time (roman** 2006) 1000)
94

My only problem is that the recursive ones are easier to program, read, and understand. And it would be nice if, also, both 'roman' and 'roman*' could perform about as well as 'roman**'. That is, Lutz, will tail recursive call optimization ever be forthcoming in newLISP? Curious.

[Dmi]

Btw, about tail recursion:
Imho, it isn't mandatory for newlisp - to analyze the code to determine "is this funcall - a tail recursion finisher?" - we can just to have a function, that will imitate tail-recursive call (i.e. replace current function in stack) whenever it called.
Something like an "exec()" libc function in unix...

How about this, Lutz?

[rickyboy]

Btw, about tail recursion:
Imho, it isn't mandatory for newlisp - to analyze the code to determine "is this funcall - a tail recursion finisher?" - we can just to have a function, that will imitate tail-recursive call (i.e. replace current function in stack) whenever it called.

Wow! This comment is very interesting to me because I was not aware that this could be done, in general. When I think about how this could be done, I can't avoid using a stack. (I am not a language implementor, so I am not surprised by any of my inabilities in this area :-) For instance, if I write a function which makes a non-tail recursive call, I find myself stuck thinking that there is some computation, at that level, which has to wait for the recursive call to complete, before it can complete its own computation. So, I naturally think of this as a continuation. Well, if we replace the current run-time on the stack with the recursive call, as you suggest, I'm thinking "what about the loss of the continuation?" Then I think, "well, we can remember this continuation and all further ones, down the line, by pushing them onto a list; when we then bottom out on the recursion, we call the continuations one by one, by popping them off of the list" -- the final answer ends up being a composition of the continuations. But this is just another stack! :-)

Dmi, could you elaborate on this concept for the feeble-minded among us (i.e. me). If you could also point to a written resource, I'd happily read it (if in English -- I cannot read Russkaya kniga). Thanks! --Rick

[Dmi]

Hmm... the thig I wrote isn't a big news. Look at this:

Code: Select all

(define (recur a b c)
  (some code 1)
  (recur (x y z)
  (some code 2)

This is a "regular" recursion. It must be done with stack growing because after recursive call we must return to upper level, complete (some code 2 section) and return it's result to the top level.
Now this:

Code: Select all

(define (recur a b c)
  (some code 1)
  (recur (x y z))

In this example we haven't a finish-section like (some code 2), so the result of the top-level recur will be the same as the result of recur of a sublevel and so forth. So in this case we won't need in top-level (recur) anymore and we can forgot about it - i.e., drop from stack. If the language can treat this, then we got the ability to write some of recursive code as effective as iterative one. Afaik, term "tail-recursive" is about this situation.

About implementation: PROLOG does this, "classic" LISP does this. newLISP doesn't this at present, but, really, I think this isn't a big cost for it's smallness/advantages rate.

Speaking about imlementation, I think, this isn't simpe. But we already have the (catch ... (throw)) construct, that perform a stack cleaning.
So, I have a think - is it possible to have something like (recurse .... (return)), so the return will first clean the stack and then somehow evaluate it's arguments.
Really only Lutz can know is it possible :-)

[rickyboy]

He, he, he. Yes, Dmi, I know what "tail recursion" means. :-)

I had just thought in your original message that you were claiming that it wouldn't be necessary for newlisp to determine if a recursive call was of the tail type, and I didn't know how this would be possible, i.e. not to check for "tailness" but still able to optimize the tail call. But I realize now that you were not originally claiming this. I'm sorry for any confusion.

However, this does not let Lutz off the hook. :-) So, Lutz, what do you think? Would it be a terribly difficult task to optimize tail calls in newlisp? Thanks, in advance, for any response. --Ricky

[Dmi]

heh :-)
The only new, I mean, is that if we realize a function like "return" in C, then it will _always_ can be a tail-recursive. So, meeting such function, the interpreter will not need to gess. And a programmer will not need to guess too ;-)

[Lutz]

I have several thoughts and comments to this, some against, some for tail recursion optimization. Perhaps Dmitry's suggestion is a good compromise.

The memory overhead is about 80 stack bytes per call function call for an average of 2 parameters passed. Currently the stack default is 2048 levels, which can be increased to hundreds of thousands vi the -s command line switch when starting newLISP.

Tail recursive functions are easy to rewrite as iterating functions. The benefit of code elegance and and code readability is greatest for recursive functions which are not tail recursive. The same benefit for tail recursive functions is small. As a side note: much of this judgement is subjective and a matter of taste either way.

Tail recursion in newLISP would rather slow down performance than speed it up. Checking for tail recursion would be expensive and not justify the speed performance gain of minimizing function call overhead. The benefit would be mainly in saving stack memory.

From a practical, application oriented point of view there is not enough benefit. I prefer iterative solutions most of the time because they tend to be much faster. There are algorithms like this one http://newlisp.org/index.cgi?page=S-expressions_to_XML where recursion is the best way to do it. But algorithms like this one are not tail recursive anyway and tend to be shallow enough for the default 2048 level stack allocation.

To sum it up when tail recursion optimization is possible, it doesn't give us much benefit.

Still I have looked into it again and again, simply because the feature seemed to be interesting from a theoretical point of view and have some application benefits in (imho rare) situations. But I have not found a simple way to implement this without using much resources, checking for tail recursion would be expensive speed performance wise.

BUT, what I found interesting is Dmitry's comment/suggestion of implementing an explicit tail recursive function call (replacing the current function on the function call stack). So basically let the programmer decide when a recursive call is pushing the stack or not. This solution would not burden present performance, but give the programmer a way of optimizing a tail recursive function by saving stack and call overhead space. I will look into that.

Lutz

[rickyboy]

BUT, what I found interesting is Dmitry's comment/suggestion of implementing an explicit tail recursive function call (replacing the current function on the function call stack). So basically let the programmer decide when a recursive call is pushing the stack or not. This solution would not burden present performance, but give the programmer a way of optimizing a tail recursive function by saving stack and call overhead space. I will look into that.

Thank you, Lutz. And Спасибо, Дми. --Ricky