Re: SOME (and other mapping functions)

[phil@rpal.rockwell.com (Philip L. Stubblefield)]

In article <9401040915.aa17365@paris.ics.uci.edu>
pazzani@pan.ICS.UCI.EDU (Michael Pazzani) writes:

> I prefer to use mapping functions when possible instead of do or loop.
> However, it appears that I pay a penalty for my stylistic preference
> because when using some lambda expressions as the function argument
> (e.g., one that references a lexical variable other than the parameter)
> space gets allocated.
> 
> (defun greater-some (x list)
>     (some #'(lambda(e)(> e x)) list))
> 
> (time (greater-some 7 '(1 2 3 4 5 6 7 8)))
> (GREATER-SOME 7 '(1 2 3 4 5 6 7 8)) took 0 milliseconds (0.000 seconds) to run.
>  40 bytes of memory allocated.
> T
> 
> Is there any declaration, etc that can avoid this spoce allocation.

You can use the DYNAMIC-EXTENT declaration to inform MCL that a named
function has dynamic extent, i.e., that it will never be referenced
once the establishing construct has been exited (CLtL/2 pp. 42-46). 
Given this declaration, MCL can allocate the function on the stack
(CLtL/2 pp. 232-236, especially p. 232).  The only disadvantage is that
you must use FLET or LABELS to define the function so that it has a
name.  For example:

? (defun greater-some-1 (x list)
    (flet ((greater-than-x (e)
             (> e x)))
      (declare (dynamic-extent #'greater-than-x))
      (some #'greater-than-x list)))
GREATER-SOME-1
? (time (greater-some-1 7 '(1 2 3 4 5 6 7 8)))
(GREATER-SOME-1 7 '(1 2 3 4 5 6 7 8)) took 0 milliseconds (0.000
seconds) to run.
T


Always keep the following in mind (CLtL/2, p. 236):

"The DYNAMIC-EXTENT declaration should be used with great care.  It
makes possible great performance improvements in some situations, but
if the user misdeclares something and consequently the implementation
returns a pointer into the stack (or stores it in the heap), an
undefined situation may result and the integrity of the Lisp storage
mechanism may be compromised."

In other words, don't do the following:

(defun make-adder (n)
  (flet ((add-n (x)
           (+ x n)))
    (declare (dynamic-extent #'add-n))        ;WRONG!!
    #'add-n))

If you're going to use the function after the definging construct has
been exited, then do *NOT* declare the function to have dynamic extent.



Philip L. Stubblefield                                   415/325-7165
Rockwell Palo Alto Laboratory                  phil@rpal.rockwell.com