from Mike
;
;   call this with (solve 8) or (solve 12) etc.
;

(defun solve (N)
   (setq Final-Depth N)
   (setq Actions (reverse (make-list N)))
   (search 0 nil Actions))

(defun make-list (N)
   (cond
      ((equal N 0) nil)
      (t (cons N (make-list (- N 1))))))

;
; can anyone see how to add a few characters so that it prints ALL
answers?
;

(defun search (Level State Remaining-Actions)
;    (print State) (terpri)
    (cond
      ((and (ok State) (> Level (- Final-Depth 1))) State)
      ((and (ok State)
          (search (+ Level 1)
                  (cons (list (+ Level 1) (car Actions)) State)
                  (cdr Actions))))
      ((null Remaining-Actions) nil)
      (t (search Level (cons (list Level (car Remaining-Actions)) (cdr
State))
                        (cdr Remaining-Actions)))))

(defun ok (State)
    (cond
       ((null State) t)
       ((null (cdr State)) t)
       ((attacks (car State) (car (cdr State))) nil)
       (t (ok (cons (car State) (cddr State))))))

This is grossly inefficient. Recursion is great for recursive
problems; `loop' seems better suited for this task IMHO. I would
recommend the following.

(defun make-list-of-numbers (n)
   (loop for number upfrom 1 to n collect number))

(make-list-of-numbers 5) => (1 2 3 4 5)

This also eliminates the call to reverse, which was copying the list
for no reason. You could have called nreverse, which may reuse the
list - but there really is no need to reverse the list at all.

Also, `make-list' is already defined in the common-lisp-user package
so it's probably not a good idea to redefine it. I would use another
package (actually I would rename the function since it doesn't do what
make-list does). This is of course assuming your using an ansi common
lisp.

< ... [code] ...

  that's kind of intriguing.  what distinguishes a recursive _problem_?

I was really thinking about the call to reverse and equal on top of
the recursion. I guess it is a recursive problem.

Can the stack really remain constant for this though? I don't doubt
it, as it seems to be a typical candidate for this kind of
elimination.

I always get confused and mix up the names of these optimizations. I
think the following example gets some kind of special treatment,
called `tail merging' I think, dunno how this relates to
`constant-stack' tail-elimination in recursive functions though.

The example is from the ACL manual, so it may be specific to ACL?

(defun foo (lis)
  (pprint lis)
  (list-length lis))

The following example is what usually pops to mind when hearing
mention of `tail-call-elimination'. What I don't understand is how the
stack could be kept constant with the accumulation happening in
`result'. The variable `result' must be put in the heap right? Maybe
my model of the whole lisp-function call thing is out of whack.

I probably have no idea what I'm talking about, but wouldn't the
function lookup still be just as expensive and maintained just like
normal? Maybe lisp compilers know about this stuff - wouldn't
surprise me either way.

(defun this (x)
   (cond ((zerop x)
        (setf (fdefinition 'this) #'(lambda (x) (+ x 2)))
     (this x))          ; This is tail recursive right?
    ((minusp x) (this (- x)))
  (t (this (1- x)))))

(this 4) => 2
(this 4) => 6

A bit extreme, but the function can't be stashed anywere special - a
full lookup is required as usual? So if the function location, and the
arguments can't be stored on the stack - I just don't get it.

In scheme re-defining a function inside of a function declares it as a
local function. I think I see why now. Two different ways to deal with
a problem I guess? Those being iteration and local redefinition.

Anyway, is the following function candidate for tail-call-elimination?
I just don't see how it is possible - even if the compiler knows no
redefinition is going to occur.

(defun make-nums (count &optional (result ()))
  (cond ((zerop count) result)
     (t (make-nums (1- count) (cons count result)))))

Maybe there is another optimization for when there is no accumulation
of values on the heap in a recursive call?

(defun add-all-numbers (list &optional (result 0))
  (declare (fixnum result))
  (cond ((endp list) result)
    (t (add-all-numbers (cdr list) (+ (car list) result)))))

The above function looks a bit confused. Replacing the global
definition from within itself makes code hard to read.
The new definition of THIS is being used
the next time the global function THIS is being called.

What do you think happens when you call THIS with 0 the first time?

(THIS 0)

Should it return 2?
I fear you will get an endless loop.

We better look at your other examples. ;-)

  here's the last function call compiled with tail call merging.

        leave
        movl    ebx,[esi+50]    ; make-nums
        jmp     *[edi+39]       ; tramp-two

  and here it is without:

        movl    ebx,[esi+50]    ; make-nums
        call    *[edi+39]       ; tramp-two
        leave
        ret

  (yeah, the CPU is an Intel Pentium.  sorry about that, but at least it
  may be well known.)

  to understand this, consider that a function call pushes the instruction
  pointer on the stack, _jumps_ to the new code, which sets up a stack
  frame with an ENTER instruction, does its work, performs LEAVE to unwind
  the stack, and finally returns to the caller with a RET instruction which
  pops the return address from the stack, and _jumps_ to it.

  consider the normal call case first: every call is made within the stack
  frame set up at each call, so every call consumes a fairly large amount
  of space, typically 50 to 100 bytes.  then all it does when it returns is
  unwind the stack frame and return to the its caller, which does the same
  as many times as the function has called itself.  pretty boring.  (we can
  all be thankful that CPU's aren't self-aware or they'd just revolt.)

  instead of making a new function call, we can unwind the stack frame if
  there is nothing on it that we need (even Intel has half a register left
  that can be used to pass arguments), and then call the function with our
  caller's return address still on the stack.  all we keep around is the
  address of our caller.  everything else is still set up at every call,
  but it happens over and over in the _same_ area of memory instead of new
  memory at every call.

  some people believe that a tail call is as efficient as a loop, but they
  either don't know their CPU very well (typical of some people's arrogance
  towards their tools), and/or they believe in magic or propaganda, neither
  of which are proven reliable sources of technical information.  it is
  generally unwise to assume that you can use an existing stack frame when
  entering a function anew, even the _same_ function.  to do that reliably,
  you use a looping construct that has control over the variable assignment
  and works _inside_ the stack frame and the known function body.

  in the event that the compiler actually transforms a self-recursive tail
  call into a loop, things turn a bit different, since we're no longer
  calling the function via the variable's value (in Scheme).  to make such
  a transformation, one would have to know that no side effects are made
  during the loop, as you have pointed out.  so generally, you can't, and
  the special cases where you can are probably a lot easier done with a
  real loop, anyway, despite the attraction of syntactic recursion.

* Erik Naggum <e...@naggum.no>
| that's kind of intriguing.  what distinguishes a recursive _problem_?

* jos...@lavielle.com (Rainer Joswig)
| In this case we have a data structure (a Lisp list) that is easily defined
| recursive. Recursive algorithms are very natural solutions
| for problems like traversal, creation, filtering, etc.

  pardon me for insisting, but definitions, algorithms, implementations,
  and _solutions_ are easily described as recursive.  my question relates
  to calling things recursive _problems_.  if it is "a problem for which a
  recursive solution is deemed most aesthetic", it is just meaningless, but
  if it actually means something specific, I'd like to know.  I find the
  term puzzling, apart from the more or less meaningless interpretation
  that doesn't refer to the problem at all.

(defun enumerate (n)
  "build list (1 2 3 ... n) by working backwards.  n must be positive."
  (let ((acc nil))
    (labels ((rec (n acc)
               (if (zerop n)
                   acc
                 (rec (- n 1) (cons n acc)))))
      (rec n acc))))

i probably don't need to drag `acc' around in the recursor.  i haven't
bothered to check if `enumerate' is taken.  if it is, call it
something else.  there are just so many pre-defined things out
there...

I had to laugh at this because it touched a place in my analogy engine
that I had not previously focused on as a computational issue.

I normally associate this issue with ethics.  Consider Clinton's dilemma
about getting Monica a job.  Some say he shouldn't have helped her because
she was a friend and it was a conflict of interest.  Clinton has said, on
occasion, things that lead me to believe he has what I see as the fully
symmetric position--that it wasn't fair to not try to get her a job just
because she was a friend, since he has helped many people who are not
friends.  We can all (in another forum!) debate about whether he should have
been in that situation, but it's clear to me that it's the question, not
the answer, that is the conflict of interest.

Another related point I would make, again from recent US politics:
Congress claims it cannot find Clinton innocent because that would
make a mockery of the rule of law.  Weird.  To me, the rule of law
says they should make a choice between convinction and innocence.  To
say that there is no choice for innocence is to say there is no choice
to be made.  To me, to say there is no choice to be made is what is a
mockery of the rule of law.

I have often said in political arenas: there are no political answers,
only political questions.  If a question is political, the answer is
bpolitical.  People often have a political way of viewing a situation
that obscures this symmetry, but it's there.

I've said essentially the same in ethics: there are no ethical choices,
only ethical dilemmas.

And so returning to the computational arena, and `informed by recent US
politics', here's my take:

I think there probably is something to joswig's implicit claim (not
his statement per se quoted above, but his choice of terms in the
statement quoted) that there is such a thing as a recursive problem.
At least, I know of no general purpose way to reduce a recursive solution
into an iterative one.  (Well, let me constrain that: if I know of such
a technique, I don't presently acknowledge it as such.  I do know about
continuation passing and CPS conversion, and I do understand how
interpreters manage continuations as data in Scheme so that they can
implement even fully recursive programs as a kind of iterative procedure.
But I haven't convinced myself this is the same...)  But certainly, I
know of general purpose equivalences between conventional "do loops"
and "tail recursion".  And it's commonly remarked for this reason that
"tail recursion" is not really "recursion" but rather just a syntactic
way of expressing "iteration".  So maybe what I think is that when Erik
is showing that a tail recursion compiles to an iteration is that the
compiler has done a proof that certain problems are equivalent to
non-recursive problems.  And I suppose I think that's not really a proof
that there are no recursive problems--it's only a proof that there is
some set of problems that may appear to be recursive because they use
recursive solutions but that turn out not to be when the recursion is
folded out.  Maybe that means all solutions are of this kind--capable of
being reduced to a non-recursive form--and Erik is right.  Or maybe
there are some solutions that don't yield to this technique.  In which case,
Rainer is right.  Or maybe, as is more likely, the notion of a recursive
problem is like the notion of a recursive solution, and is just a way of
saying that "if you think about the problem in this formalism, you'll get
a useful point of view that may yield leverage" and not a way of saying
"this problem is fundamentally of a certain representation class".

Have I said recently that there are no total solutions, only trade-offs?
Perhaps the choice to view something as recursive is only a trade-off.
But that doesn't mean there's no value in viewing it that way.  Or that
there's only value in viewing it that way.

Our job should be to provide people with options in how to view things,
so they can optimize their pain and progress according to subjective
measures that optimize quality of life.

<many complicated political/philosophical/CS topics and something
about Bill Clinton and Monica Lewinsky. Especially this latter
part I could not really follow - maybe my thoughts are always
wandering around when it comes to this topic...>

...

...

...

Well, I just wanted to answer something to the original statement
where the poster said, that it is not a "recursive problem".
Hopefully my attempt did not puzzle him to much. If I left him
even more confused, then I have to apologize.

* Kent M Pitman <pit...@world.std.com>
| Maybe that means all solutions are of this kind--capable of being reduced
| to a non-recursive form--and Erik is right.

  that was not at all what I was trying to say or ask.  all I was wasking
  was: is it valid to talk about _problems_ as being recursive.  as I have
  already stated, the obvious meaning is "a problem for which a recursive
  solution is deemed most aesthetic", which is like defining philosphy as
  "anything whoever is called a philosopher does".

  it seems that there is nothing more to "recursive problem" that just that
  -- a problem to which a recursive solution is deemed most aesthetic.

  so, in conclusion, nothing distinguishes a recursive problem from any
  other problem other than the fact that after all has been said and done,
  the recursive solution was most appropriate.  I had initially hoped there
  had been somewhat more of an analytical approach to this, which would
  have meant that "recursive problem" actually added something to the
  nature of recursion or of problems.  maybe some other time.

     it is
     generally unwise to assume that you can use an existing stack frame when
     entering a function anew, even the _same_ function.  to do that reliably,
     you use a looping construct that has control over the variable assignment
     and works _inside_ the stack frame and the known function body.

Could you elaborate on this? I can believe that there may be some
complications in more complicated situations, but I fail to see the
problems in compiling e.g.

        (define (last lst)
          (if (null? (cdr lst))
              (car lst)
              (last (cdr lst))))

Some problems really are inherently recursive in nature.  For example,
the enumeration of the leaves of a (binary or other) tree.  You can't
write an interative algorithm for solving this problem in general, since
you would need (potentially) arbitrary amounts of memory in order to
hold the state of your traversal.

The trivial problem is that the language does not require a compiler
to optimize what you have just said if you are using CL.  Scheme
requires tail call elimination, but CL does not.  Expecting a compiler
to perform any service not required of it (even one you can convince
yourself it would be a good idea to do and one that it would not be
non-conforming not to do) is a potential pitfall by definition.  The
minimal expectation of a compiler is that it will do what it is
defined to do, and since it is not defined to do this, it is not a
reasonable minimal expectation to expect that "at minimum" it will do
this.

Does anyone have any insightful commentary on why current compilers
can't optimize out the millions of unneeded function calls for code
like the below? Finding the 40th term takes the better part of a
minute on my Pentium 200MMX, while only a small fraction of a second
with the efficient versions.

  (defun fibonacci (n)
    (if (> n 2)
        (+ (fibonacci (- n 1))
           (fibonacci (- n 2)))
      1))

  #include <stdio.h>
  #include <stdlib.h>

  int main(int argc, char *argv[])
  {
          long double i, fibonacci(long double);

          printf("%.0Lf\n", fibonacci(atof(argv[1])));

          return EXIT_SUCCESS;
  }

  long double fibonacci(long double n)
  {  
          if (n > 2.)
                  return (fibonacci(n - 1.) + fibonacci(n - 2.));
          else
                  return 1.;
  }

* p...@kuovi.cs.tut.fi (Kellom{ki Pertti)
| Could you elaborate on this?  I can believe that there may be some
| complications in more complicated situations, but I fail to see the
| problems in compiling e.g.
|
|       (define (last lst)
|         (if (null? (cdr lst))
|             (car lst)
|             (last (cdr lst))))
|
| Or are you referring to the possibility of a redefinition?

  no, redefinition is an additional reason to avoid optimizing away the
  stack frame release.

  let's consider a function call in all its glory.  the arguments are
  evaluated before anything interesting happens, but we'll skip that part
  and just assume that all the values to pass are available.  there are
  several ways to pass arguments to functions, but let's consider the
  simplest case: a stack-allocated vector.  in languages with variable
  numbers of arguments, you need to pass the length of this vector.  that's
  typically passed in a register, so not to complicate things, let's assume
  it is not part of the vector.  (the stack-allocated vector is typically
  set up with PUSH instructions, but it helps to view it as a vector.)

  the actual function call is made, and this is typically very fast, like
  keeping the next instruction address somewhere and transfering control to
  the start of the new function, but in Lisp there typically needs to be
  some lookup to find the actual address.  this is usefully handled by a
  trampoline -- a function that does something important but does not
  disturb the stack frame other than in the expected ways.  (it's called a
  trampoline because you jump on/to it and it helps you jump elsewhere.)

  we have arrived at the start of the our code, where there's an prologue
  waiting for us.  the prologue may check the argument count, do call
  counting statistics, check for interrupts, check for space on the stack,
  set up a stack frame, process the argument list (&optional with default
  values, &key arguments), initialize &aux variables, etc, and the order of
  these things is determined by a lot of factors.  the interesting things
  to us are: error handling, the location of the argument vector, the space
  requirements, the initialization of lambda-bound variables.

  the body of the function is not relevant to us, but after the body (in
  time) is an epilogue that needs to clean up from the prologue, unwind the
  stack, and return to wherever we were called from.  a function is allowed
  to maintain an inconsistent stack state as long as it unwinds correctly.
  also note that CPU's suffering from register starvation (Intel), use the
  stack for temporary memory in some cases, and that local variables are
  allocated as part of this procedure.

  now, to make a tail-call that does not need to unwind the stack, and
  which jumps to the location after the stack frame has been set up, we
  need to know the prologue very intimately.  of course, a compiler writer
  does that, but we also need to make sure that everything that happens
  before the stack frame is set up is handled by the tail-call jump.
  suppose that this is a non-trivial amount of work in the general, such as
  computing the size of a stack-allocated &rest list and such.  is it worth
  the trouble to recognize simple functions rather than go through the
  epilogue and the prologue again?

  and since you cannot actually optimize away the self-tail call completely
  in the general case, it may be a _lot_ of work to recognize the simple
  case in Common Lisp.  now, Scheme has decided to make this decision pay
  off, but I do wonder whether they actually manage to make tail calls as
  efficient as loops.  it is not possible in the general case.

  further complications, by the way, occur when you make a tail call from
  inside a let binding, and that's what we normally do.  if the values are
  stack-allocated, the semantics of tail-call changes from a jump before
  the epilogue to a jump after the epilogue.  a special binding prohibits
  the epilogue from running before the callee has returned.  etc, etc.
  these further complications are, however, fairly easy to spot and argue
  with.  the harder problems occur when even their absence makes it unsafe
  to assume you can just jump directly to the point after the prologue.

  now for an illustrative example.  when compiled with (optimize (speed 3)
  (safety 0) (debug 0)), the simple function

(defun foo (x y z)
  (list x y z))

  should cause a very simple jump to the LIST function, or whatever takes
  care of it with three arguments.  here's the SPARC disassembly with
  Allegro CL 4.1.3:

        ld      [%g4 + 95], %g2 ; qlist3
        jmp     %g2 + 0
        xor     %g0, #x3, %g3

  (the SPARC is explicitly pipelined, so the XOR is actually executed
  before the first instruction at the jump target.  %G0 is a constant 0, so
  this sets %G3 to 3.  that's the argument count register.  where the other
  argument values are is immaterial since list is given the exact same
  arguments as foo got.)

  the Intel disassembly with ACL 5.0 is somewhat different.

        pushl   ebp
        movl    ebp,esp
        pushl   esi
        subl    esp,$44
        addl    esp,$12
        pushl   [ebp+16]        ; (argument 2)
        pushl   edx
        pushl   eax
        xorl    ecx,ecx
        movb    cl,$3
        call    *[edi+95]       ; qlist3
        leave
        movl    esi,[ebp-4]
        ret

  note that the tail-call did in fact not get merged, but consider the
  slightly simpler function

(defun bar (x y)
  (list x y))

  the SPARC assembly is identical to the previous function, except that
  QLIST2 is called instead of QLIST3.  the interesting thing happens to the
  Intel code:

        xorl    ecx,ecx
        movb    cl,$2
        jmp     *[edi+47]       ; qlist2

  in other words, the number of arguments can itself be an impediment to
  certain optimizations, and the number may vary from architecture to
  architecture.

  your particular function compiles to a self-tail-call merge, but still
  goes through the symbol-function slot of the symbol naming the function.

cba...@2xtreme.net (Christopher R. Barry) writes:

To this add that AFAIK not very many C compilers can do tail recurion
optimization. Of the CL compilers around, AFAIK the only one that does
not do the right thing on tail calls (at least not completely) is GCL.

Cheers

The short answer is that the programming work wouldn't be worth the
effort.

It is obvious to smart humans how to optimize fibonacci, but it is
much harder to describe to a computer in a way that will be useful.

The problem is that you will spend a lot of effort making a
optimalization routine that will only be used very very seldom.  Most
programs do _not_ look like fibonacci.

And even those programs that can in fact be improved like fibonacci
can are different in ways that are unimportant to a human, but which
are critical to another computer program, the compiler.

  well...  apart from wanting to avoid the first recursive function call
  (which can be done with a simple iteration from a lower limit to the
  value in question, but this is not something I want the compiler to
  decide for me), optimizing fibonacci is mostly a matter of memoizing.  it
  _would_ be useful if a compiler could see that there is no way a function
  would return a different value if given the same arguments, i.e.,
  automated detection of side-effect-free functions and various means of
  propagation of this information.

Note that in the case of direct tail-recursion, the compiler often does
have enough information available to compile away the prologue and
epilogue.  It can tell that the function takes a fixed number of arguments,
and that the call has the correct number, and simply rebind the lambda
variables and do a goto as in a DO loop.

I haven't read the Sussman/Steel "Lambda: the Ultimate ..." papers in quite
a while, but I can't imagine they didn't address most of the issues you
raise.