Re: SETF and variable issues in Self Similar program.

In article <yxz8x418qt3.fsf@xxxxxx>,
Holger Schauer <Holger.Schauer@xxxxxx> wrote:

On 5214 September 1993, Rainer Joswig wrote:
Hmm, I would avoid tail-recursive code in Common Lisp if possible.

I sometimes find it hard to come up with a straight-forward
formulation in iterative terms for an inherent recursive problem. I
am also usually much more concerned about maintainability and
readability than about speed, so usually when a recursive solution is
more straight forward to me, I won't consider an iterative
reformulation.

The language Common Lisp was not designed with tail-call
optimization in mind. The way to get a compiler to optimize a tail-call
is clumsy in most implementations - the amount of
optimizations differ from implementation to implementation.

I would be interested to learn about what the different
implementations do. Maybe that would be a nice addition to Daniel
Weinrebs recently published lisp (implementations) survey.

There are many more things to compare. That would be
a much much longer paper.

The DEBUG declaration is used to turn that on/off in compiled (!)
code. That alone is clumsy. Say, I want full debugging, but tail
call optimization turned on.

That's the usual speed/debug trade-off, isn't it? I would go for full
debugging during development and for full speed when in production. I
can see why having full debugging and full speed at the same time is a
worthy goal, but it seems clear to me that all optimizations for some
use case probably come at a price.

Speed and Debug are different optimization angles.
Tail-call elimination is not a simple optimization
for speed or something that reduces debuggability.
It changes the semantics of the language in a big way.
It interacts with other parts of the program in a big way.
In Common Lisp it has to interact with condition handling,
special variables, rest arguments, and other stuff.
Unless there is a meaningful description how tail
call elimination fits into the language model, I would
not use it without really closely looking at the source
code and inspecting what the compiler does. Especially since
every compiler does something different for such an
unspecified language change.

I also don't want 'full speed' in production. Don't optimize
for 'full speed'. Never. Only in places where it matters.
You want safety. Not speed. When you optimize for speed,
it means in Common Lisp, that many operations are unchecked,
and semantics of operations can change from the default.

Common Lisp compilers don't do much compile-time checking
(even SBCL/CMUCL does not get very far). You need
runtime checks otherwise errors go unnoticed and
your app will instead of handling errors just crash
or deliver results you don't expect. Common Lisp
has a totally different language model from a
language where everything is done so that you can
do as much checks as possible at compile-time.
Common Lisp programs will by DEFAULT be mostly unchecked
unless you have run them. Common Lisp compilers
will happily remove all kinds of checking and error
detection/reporting when you optimize for speed (and reduce
safety). The errors that one can introduce are some
subtle that you can spend ages to find them.

A 'full speed' deployed application will be very different
from a 'full debug' and 'full safety' app in development.
Most of the time 'full speed' is simply not necessary.

The default has to be to run with 'full safety'. IMHO, of course.

I also doubt that always the distinction between development
and deployment (which is also a bunch of very diverse situations)
is true. I, for example, want the ability from a deployed app to

* get meaningful backtraces
* replace and update code and data
* have full symbols at runtime
* trace code and get the output somewhere
* call a debugger and inspector to inspect
the runtime

and so on...

The buggy applications are not those where errors happen,
the buggy applications are those where you cannot handle
the errors due to unnecessary optimizations.

It gets more problematic with graph traversal and other
things, but the typical loop is a good candidate
to be written as a LOOP and not as a tail-recursive
function.

I agree. But it's still a matter of one's focus (readability,
speed and/or debugging issues) which way to go. I'm quite neutral to
the issue in general.

A few friends of mine have written an extremely complicated piece
of software. They are using tail call optimization.
Their software would not run without it.

That's always a bad sign. Tail call optimization is an optimization,
not a problem solution.

As I said. It is not just an optimization. It is a change of
the semantics of a basic language construct (function calling)
and interacts with other elements of the language.

Common Lisp has special variables.

Simple example:

(defun foo (bar)
(let ((*foo* (something-here ...)))
...
(baz ...)))

*foo* is special. (baz ...) is possibly no longer a tail call.
Anything that sets up a scope that has to do something
when leaving it, is no longer an easy tail call.
You cannot just jump to the new place then.
You can't see from looking at the place in the source where the call is,
what it does. You have to inspect the source code around it and
also see what the compiler creates. Otherwise your code
might depend on the tail call elimination, but the
compiler was not able to do it.


Of course, if you know what you're doing and
that you can and want to rely on that particular optimization, you're
free to exploit it being available, but otherwise (i.e., your code
runs only by chance and breaks under, say, different debug settings) I
would say the code is buggy (as in "inappropriate for the input data")
and suggest trying different approaches.

Holger

The most important thing to understand is that Common Lisp
by default is an dynamic language at runtime. Runtime does
not just mean development, but also deployment. The whole
package you get with the language is not only macros,
CLOS, compiler at runtime (all the things we like)
and so on - you also get no (or few/limited) compile-time checks.
What you know from a static language just does not apply.
You cannot optimize for 'full speed' (and lower safety, debug values)
and expect the program to do the same. It doesn't.

--
http://lispm.dyndns.org/
.

Relevant Pages

  • Re: object system...
    ... When one needs to see the changes in the debugger or finds that some concurrent thread is reading a value that isn't updated, one corrects the problem by slapping 'volatile' on the lvalue and recompiling to locally prevent the optimization. ... Note that if a priori one wanted to be sure all one's lvalues behaved as the language specification is defined, one would have to put 'volatile' on every lvalue in the program, thus completely defeating the optimization. ... But because the switch statement does not provide a count of the case clauses in the syntax preamble it is impossible for an LALRcompiler to construct a jump table on the fly so cascaded IFs must be used. ...
    (comp.object)
  • Re: gcc and 2.6 kernel
    ... *any* language GCC supports, except perhaps Fortran (I don't know ... > gotten right for each construct, is gotten right for the whole language ... whether or not optimization takes place. ... later stages so much that it speeds the compiler up, ...
    (comp.os.linux.development.system)
  • Re: Interesting article by Randall Hyde
    ... >> language, not the code that the compiler generates. ... *what* code the compiler generates is up to the implementor. ... > I didn't see anything under "Optimization". ... > Perhaps because I'm not a long-experience `c` programmer, ...
    (comp.lang.asm.x86)
  • Re: Choice of language and databases
    ... Why would you want only one language? ... dynamic type system, real macros (in the Common Lisp sense, not this C ... are in the compiler, syntax and are just computations / algebraic. ... A good procedural programmer does not really need them, ...
    (comp.databases)
  • Re: introspection in SML
    ... purposes, and the "active" sense, in which you use introspection to ... if it was disabled by default and if it required a compiler switch. ... kind of language I would particularly like to program in. ... Compared to something like Common Lisp, ...
    (comp.lang.functional)