Re: How to make mod_lisp faster than php?

Marcin 'Qrczak' Kowalczyk wrote:

Barry Jones <bjones01@xxxxxxx> writes:



Ask both groups whether they are smarter. Chances are the Java group
will poll each member sequentially and produce a majority result.
In the Lisp group, the first fellow will answer, "I know my opinion,
but let me get my neighbor's opinion first, and then combine the
results." The second person says exactly the same thing. Finally,
the last person answers for herself, and that starts a return wave
through the group, with the first person finally returning an
answer.



This assumes that a non-tail recursion as deep as the data size
is considered acceptable in Lisp. I'm afraid it's not the case.

There seem to be various levels of acceptance of deep recursion
among programming styles natural to various languages:

0. Not accepted. This applies to languages like C, Java and Python.

1. Tail recursion only. I suppose Lisp is here. Particular
  implementations may be higher or lower though, so I'm not sure
  about the style imposed by the language as such.

2. Tail calls only, possibly between different functions. Most
  functional languages are here, even though in OCaml tail calls with
  a sufficiently large number of arguments (over 5) do consume stack
  (I forgot whether this applies to native code, byte code, or both).

3. Deep recursion works well: the stack size is not artificially
  limited. It's possible that Scheme is here because a standard
  implementation of call/cc which puts stack frames on the heap
  yields this property.

I recently improved the GC of my implementation of my language to not
scan the whole stack on each minor collection, because otherwise deep
non-tail recursion could make GC run in O(N^2) time. The language
promotes the 3rd level of acceptance of deep recursion. Stack frames
are not recycled by the GC - they are taken from a reallocatable array.


That was helpful, thanks.

Is the model of processing a list by processing the car, then recursively processing the cdr generally acceptable only if the recursive calls don't have to return values? I think that implies tail recursion, right?

Do we generally expect a lisp implementation to optimize tail recursion? I'm using CLisp in windows for the next three weeks, then I'll be using MCL on a Mac. I'd guess that MCL is optimized.

What kind of GC is it? Generation copying?
--
Barry
.

Relevant Pages

  • Re: Making Lisp popular - can it be done?
    ... “hack” for recursion. ... We already have to think about how to do tail ... (recur (dec n) ... experience with implementing Lisp, ...
    (comp.lang.lisp)
  • Re: Yet Another Spinoza Challenge
    ... Yes there is in a context-free language with recursion. ... have been stack frames. ... this particular case, parameters for system routines). ... It is a mark of programming incompetence to think that fixed areas are ...
    (comp.lang.c)
  • Re: kernel stack challenge
    ... > infinite loop, and eventually ... Separate logical copy of LISP program is for each ... subsystem we protect. ... > recursion is at all interesting or useful.... ...
    (Linux-Kernel)
  • Re: Beginners Question on an exercise from Grahams ACL
    ... > just been taught and to exercise my brain on them - not with some other ... Recursion might be more worthwhile as a separate item to learn, ... than binding up lisp and recursion into a single package of pain. ... Alternate places than lisp materials might teach it better, ...
    (comp.lang.lisp)
  • Re: Tail recursion
    ... Recently I read about "tail recursion" - ability of ... programming language realization to convert linear recursive proccess ... to linear iterative proccess. ...
    (comp.compilers)