From: Nils Goesche
Subject: Tail calls to top-level functions
Date: 
Message-ID: <lk65y2lovq.fsf@pc022.bln.elmeg.de>
Hi!

I was thinking about Norvig's (PAIP) clever trick of memoizing
functions.  Then, the following question came to my mind:

Consider

CL-USER 77 > (defun blark (n)
               (if (zerop n)
                   (pprint 'done)
                 (progn
                   (pprint 'wait)
                   (blark (1- n)))))
BLARK

CL-USER 78 > (setq *mem* #'blark)
#'(LAMBDA (N) (DECLARE (LAMBDA-NAME BLARK)) (BLOCK BLARK (IF (ZEROP N) (PPRINT (QUOTE DONE)) (PROGN (PPRINT (QUOTE WAIT)) (BLARK (1- N))))))

CL-USER 79 > (defun blark (n)
               (declare (ignore n))
               (pprint 'hihi))
BLARK

CL-USER 80 > (funcall *mem* 2)

WAIT
HIHI

But now look at

CL-USER 81 > (compile (defun blark (n)
                        (if (zerop n)
                            (pprint 'done)
                          (progn
                            (pprint 'wait)
                            (blark (1- n))))))
BLARK
NIL
NIL

CL-USER 82 > (setq *mem* #'blark)
#<function BLARK 20679D1A>

CL-USER 83 > (defun blark (n)
               (declare (ignore n))
               (pprint 'hihi))
BLARK

CL-USER 84 > (funcall *mem* 2)

WAIT
WAIT
DONE

Does this mean that my compiler (LWL) has a bug or is something
undefined happening here?  To me it seems that /if/ you do a tail call
elimination here, you should at least look up the function slot of
BLARK and jmp /then/, or does the standard permit to jump directly?

Regards,
-- 
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x0655CFA0
From: Frode Vatvedt Fjeld
Subject: Re: Tail calls to top-level functions
Date: 
Message-ID: <2hofbubtu2.fsf@vserver.cs.uit.no>
Nils Goesche <······@cartan.de> writes:

> [..] Does this mean that my compiler (LWL) has a bug or is something
> undefined happening here?  To me it seems that /if/ you do a tail
> call elimination here, you should at least look up the function slot
> of BLARK and jmp /then/, or does the standard permit to jump
> directly?

This paragraph of CLHS permits the direct jump, I believe:

  3.2.2.3 Semantic Constraints

    [...]

     o Within a function named F, the compiler may (but is not
       required to) assume that an apparent recursive call to a
       function named F refers to the same definition of F, unless
       that function has been declared notinline. The consequences of
       redefining such a recursively defined function F while it is
       executing are undefined.


-- 
Frode Vatvedt Fjeld
From: Nils Goesche
Subject: Re: Tail calls to top-level functions
Date: 
Message-ID: <lk1y8qlnjd.fsf@pc022.bln.elmeg.de>
Frode Vatvedt Fjeld <······@acm.org> writes:

> Nils Goesche <······@cartan.de> writes:
> 
> > [..] Does this mean that my compiler (LWL) has a bug or is something
> > undefined happening here?  To me it seems that /if/ you do a tail
> > call elimination here, you should at least look up the function slot
> > of BLARK and jmp /then/, or does the standard permit to jump
> > directly?
> 
> This paragraph of CLHS permits the direct jump, I believe:
> 
>   3.2.2.3 Semantic Constraints
> 
>     [...]
> 
>      o Within a function named F, the compiler may (but is not
>        required to) assume that an apparent recursive call to a
>        function named F refers to the same definition of F, unless
>        that function has been declared notinline. The consequences of
>        redefining such a recursively defined function F while it is
>        executing are undefined.

Yep, seems so.  Thanks very much!

Regards,
-- 
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x0655CFA0
comp.lang.lisp / 2002 / aug