[Gcl-devel] Re: tak simplified

[Camm Maguire]

Greetings, and thanks for isolating this example!

Your suspicions are hardly naive -- the compiler makes a first pass over
the top level forms in sequence, collecting information as it goes,
then writes the output in pass 2 using said information.  This means
that a defun calling one further down in the file will not have
available its auto-proclamation info, etc., leaving any conflicts to
be resolved at load time.  

This will obviously get simple (i.e. self) recursion wrong, so the
compiler iterates over the pass1 processing of the single top level
form in question in this case.

In general, in the case where all functions are in the same file, it
would be possible to effectively do the recompile before writing the
output in pass2.  This will only mitigate, and not eliminate, the
necessity of recompiling at load time, which you feel is deprecated,
I'm sure with good reason.  I had thought that since this would not
solve the entire problem, best to do the conflict resolution in one
place for all cases, i.e. at load time.

I'm most interested in your example for another reason, as it exposes
a weakness in the current algorithm in the case of mutual recursion.
Chicken-and-egg ordering/bootstrapping problems aside, the signature
arrived at here was ((fixnum fixnum fixnum) *), not ((fixnum fixnum
fixnum) fixnum), (as is the case for a simple self-recursion version of
tak, as I've just confirmed).  We need to sketch out a good algorithm
here.  (Initially, I had naively thought that this could be resolved
easily using reverse type propagation, at least in this case, using
the call to tak0 using as (known fixnum) argument the result from
tak1, but this clearly won't work at all, as the function result type
could vary with input, and even return multiple values).  Somehow, we
have to do the simple-recursion iteration across multiple functions,
and again the comprehensive time to do this is at load time.  

The way the former (i.e. self-recursion) works is to assume the return
type is nil, compile the function, get an expanded return type, and
recompile until we get the same result twice.

Suggestions as always most welcome.

If it would be helpful, I can describe how the compiler sees each
function below at the various stages of the compile and load process.
You can as well by compiling one at a time and checking the contents
of (gethash 'tak0 si::*call-hash-table*) and si::*needs-recompile*.

Take care,


Robert Boyer <address@hidden> writes:

> Ok, let me try my question again, in somewhat simplified
> form, though still too long.
> 
> Why can't you do the COMPILE-FILE below "right" the first
> time?  There is only one file in sight, foo.cl.  There are
> only two functions in sight, tak0 and tak1.  My naive
> feeling is that you are probably "committing" to a signature
> for tak0 before you should, and that's why you have to
> recompile tak0 later, during the load, which is deprecated!
> 
> Bob
> 
> % cat foo.cl
> (defun tak0 (x y z) 
>   (declare (type fixnum x y z))
>   (cond ((not (< y x)) z)
>       (t (tak1 (tak0 (the fixnum (1- x)) y z)
>                (tak1 (the fixnum (1- y)) z x)
>                (tak0 (the fixnum (1- z)) x y)))))
> (defun tak1 (x y z) 
>   (declare (type fixnum x y z))
>   (cond ((not (< y x)) z)
>       (t (tak0 (tak0 (the fixnum (1- x)) y z)
>                (tak1 (the fixnum (1- y)) z x)
>                (tak0 (the fixnum (1- z)) x y)))))
> 
> % xg
> GCL (GNU Common Lisp)  2.7.0 ANSI    Jun  6 2006 15:29:37
> Source License: LGPL(gcl,gmp,pargcl), GPL(unexec,bfd)
> Binary License:  GPL due to GPL'ed components: (BFD UNEXEC)
> Modifications of this banner must retain notice of a compatible license
> Dedicated to the memory of W. Schelter
> 
> Use (help) to get some basic information on how to use GCL.
> 
> Temporary directory for compiler files set to /tmp/
> 
> >(compile-file "foo.cl")
> 
> ;; Compiling foo.cl.
> ;; End of Pass 1.  
> ;; End of Pass 2.  
> ;; OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3, 
> (Debug quality ignored)
> ;; Finished compiling foo.o.
> #P"/v/filer2/boyer/gabriel/foo.o"
> NIL
> NIL
> 
> >(bye)
> % xg
> GCL (GNU Common Lisp)  2.7.0 ANSI    Jun  6 2006 15:29:37
> Source License: LGPL(gcl,gmp,pargcl), GPL(unexec,bfd)
> Binary License:  GPL due to GPL'ed components: (BFD UNEXEC)
> Modifications of this banner must retain notice of a compatible license
> Dedicated to the memory of W. Schelter
> 
> Use (help) to get some basic information on how to use GCL.
> 
> Temporary directory for compiler files set to /tmp/
> 
> >(load "foo.o")
> 
> Loading foo.o
> Callee TAK1 sigchange NIL to ((FIXNUM FIXNUM FIXNUM) *), recompiling TAK0
> ;; Compiling /tmp/recompile.lsp.
> ;; End of Pass 1.  
> ;; End of Pass 2.  
> ;; OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3, 
> (Debug quality ignored)
> ;; Finished compiling /tmp/recompile.o.
> Loading /tmp/recompile.o
> start address -T 0xaf17650 Finished loading /tmp/recompile.o
> start address -T 0xaf12290 Finished loading foo.o
> 2156
> 
> >
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah