From: rif
Subject: A function-generating function question.
Date: 
Message-ID: <wj07kfzjydn.fsf@five-percent-nation.mit.edu>
I have a list of lists of integers l (example: ((3 5) (1 2 3))), and I want
to generate a function that takes an array arr and returns a new array
whose i'th element is the product of the elements of arr indexed by the
i'th element of l.  So for instance, given l as above, I want
to return a function such as

(lambda (arr)
  (let ((new (make-array 2)))
    (setf (aref new 0) (* (aref arr 3) (aref arr 5)))
    (setf (aref new 1) (* (aref arr 1) (aref arr 2) (aref arr 3)))
    new))

The reason I want to do this is that the same list of lists of integers gets
used many many millions of times, so I'd like to avoid going over the list of
lists each time I do so.  Also, the list of lists of integers is several
hundred elements long, so I don't much want to type it out by hand.

I do have a solution:

(defun gen-array-prods-fun (prod)
    (do* ((pl prod (cdr pl))
	  (pc (car pl) (car pl))
	  (i 0 (+ i 1))
	  (l (list (array-prods-fun i pc))
	     (cons (array-prods-fun i pc)
		   l)))
	((null (cdr pl))
	 (eval `(lambda (arr)
		  (let ((new (make-array ,(length prod))))
		    ,@(nreverse l)
		    new))))))

(defun array-prods (i prodlist)
  `(setf (aref new ,i)
	 (* ,@(mapcar #'(lambda (e)
			  `(aref arr ,e))
		      prodlist))))


Which I use as follows:

* (setf (symbol-function 'f) (gen-array-prods-fun '((3 5) (1 2 3))))
#<Interpreted Function (LAMBDA (ARR)
			       (LET #
				#
				#
				NEW))
{497F14F1}>
* a
#(0 1 2 3 4 5 6 7)
* (f a)
#(15 6)


I can also compile the function using (compile 'f), but I can't help but
feel that I'm missing something.  Is there a better way to do this?  More
elegant, cleaner, more idiomatic, more LISPy?  Is it possible to avoid
using eval?  Is there any reason to use macros here instead of functions?
Any advice is appreciated.

Cheers,

rif

From: Christian Nyb�
Subject: Re: A function-generating function question.
Date: 
Message-ID: <873cqne977.fsf@nybo.no>
rif <···@mit.edu> writes:

> I have a list of lists of integers l (example: ((3 5) (1 2 3))), and I want
> to generate a function that takes an array arr and returns a new array
> whose i'th element is the product of the elements of arr indexed by the
> i'th element of l.  So for instance, given l as above, I want
> to return a function such as
> 
> (lambda (arr)
>   (let ((new (make-array 2)))
>     (setf (aref new 0) (* (aref arr 3) (aref arr 5)))
>     (setf (aref new 1) (* (aref arr 1) (aref arr 2) (aref arr 3)))
>     new))
> 
> The reason I want to do this is that the same list of lists of integers gets
> used many many millions of times, so I'd like to avoid going over the list of
> lists each time I do so.  

To me it looks like the code above goes over the list - could you
elaborate on what you mean by "avoiding"?

> Also, the list of lists of integers is several
> hundred elements long, so I don't much want to type it out by hand.

Why don't you use a macro definition for this?


[...]

> I can also compile the function using (compile 'f), but I can't help but
> feel that I'm missing something.  Is there a better way to do this?  More
> elegant, cleaner, more idiomatic, more LISPy?  Is it possible to avoid
> using eval?  Is there any reason to use macros here instead of functions?
> Any advice is appreciated.

I may be missing your intentions on how you're going to speed things
up with your approach.  What's wrong with something like this:

(defun make-new-array (old-array integer-list)
  (loop with new-array = (make-array (length integer-list))
      for elem in integer-list
      and i from 0
      do (setf (aref new-array i) 
	   (reduce #'* (map 'list (lambda (index)
				    (aref old-array index))
			    elem)))
      finally (return new-array)))

Or using a lexical closure:

(let ((integer-list '((3 5) (1 2 3))))
	       (defun make-new-array (old-array)
		 (loop with new-array = (make-array (length integer-list))
		     for elem in integer-list
		     and i from 0
		     do (setf (aref new-array i) 
			  (reduce #'* (map 'list (lambda (index)
						   (aref old-array index))
					   elem)))
		     finally (return new-array))))

CL-USER(33): (make-new-array #(0 1 2 3 4 5 6 7))
#(15 6)
CL-USER(34): 
-- 
chr
From: Barry Margolin
Subject: Re: A function-generating function question.
Date: 
Message-ID: <T5%v9.31$mJ3.2939@paloalto-snr1.gtei.net>
In article <··············@nybo.no>, Christian Nyb� <···@nybo.no> wrote:
>rif <···@mit.edu> writes:
>
>> I have a list of lists of integers l (example: ((3 5) (1 2 3))), and I want
>> to generate a function that takes an array arr and returns a new array
>> whose i'th element is the product of the elements of arr indexed by the
>> i'th element of l.  So for instance, given l as above, I want
>> to return a function such as
>> 
>> (lambda (arr)
>>   (let ((new (make-array 2)))
>>     (setf (aref new 0) (* (aref arr 3) (aref arr 5)))
>>     (setf (aref new 1) (* (aref arr 1) (aref arr 2) (aref arr 3)))
>>     new))
>> 
>> The reason I want to do this is that the same list of lists of integers gets
>> used many many millions of times, so I'd like to avoid going over the list of
>> lists each time I do so.  
>
>To me it looks like the code above goes over the list - could you
>elaborate on what you mean by "avoiding"?

I don't see any references to the list in the above code.  It goes over the
array, but the values that were originally in the list have been open-coded
into the function.  What he's trying to do is avoid nested loops over the
list of lists.

My suspicion is that this is premature optimization.  Iterating over lists
is pretty efficient in Lisp, and contorting your design to avoid it is
usually wasted effort.  It will make your code harder to read and maintain,
and is not likely to buy you significant performance.  Have you profiled
your code and found that this list iteration is really a bottleneck?  How
big are these lists in practice?

-- 
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: rif
Subject: Re: A function-generating function question.
Date: 
Message-ID: <wj0ela6tqs8.fsf@five-percent-nation.mit.edu>
> 
> My suspicion is that this is premature optimization.  Iterating over lists
> is pretty efficient in Lisp, and contorting your design to avoid it is
> usually wasted effort.  It will make your code harder to read and maintain,
> and is not likely to buy you significant performance.  Have you profiled
> your code and found that this list iteration is really a bottleneck?  How
> big are these lists in practice?
> 

This operation is pretty much the whole program, and it is the
bottleneck.  The length of the lists vary in practice between several
hundred and several thousand, and I need to call the function millions
of times.  Right now, I'm comparing optimized versions of these two
functions.  First, the iterating over the list approach suggested by
Christian Nyb?:

(defun make-new-array (old-array integer-list)
  (declare (type (simple-array single-float (28)) old-array))
  (loop with new-array = (make-array 434 :element-type 'single-float)
        for elem in integer-list
        and i from 0
        do (setf (aref new-array i)
                 (reduce #'* (map 'list (lambda (index)
                                          (aref old-array index))
                                  elem)))
        finally (return new-array)))

(Note that I've hard coded in the size of the new array and the old
array for speed.  I'm compiling with (speed 3) and (safety 0).  If
there are any other obvious ways to optimize this function, I'm
definitely interested.)

In the other corner, we have the open-coded function generator:

(defun gen-array-prods-fun (name prod alen)
  (do* ((pl prod (cdr pl))
        (pc (car pl) (car pl))
        (i 0 (+ i 1))
        (l (list (array-prods-fun i pc))
           (cons (array-prods-fun i pc)
                 l)))
      ((null (cdr pl))
       (eval `(setf (symbol-function ',name)
                    #'(lambda (arr)
                        (declare (type (simple-array single-float (,alen))
                                       arr))
                        (let ((new (make-array ,(length prod)
                                               :element-type 'single-float)))
                          ,@(nreverse l)
                          new)))))))

I generate the function using (this is under CMUCL), starting from the
length-434 vector pls:

(progn 
  (gen-array-prods-fun 'genned-f pls 28)
  (with-compilation-unit (:optimize '(optimize (speed 3) (safety 0) (debug 0)))
                         (compile 'genned-f)))
        
We'll also make use of a function to create random arrays:

(defun make-random-vector (l)
  (let ((a (make-array l :element-type 'single-float)))
    (dotimes (i l)
      (setf (aref a i) (random 1.0)))
    a))


(let ((a (make-random-vector 28)))
  (equalp (genned-f a)
          (make-new-array a pls)))

return T, indicating to me that the two approaches generate identical
results.

Now we compare them in speed:
* (time (dotimes (i 10000) (make-new-array (make-random-vector 28) pls)))
Evaluation took:
  4.55 seconds of real time
  3.75 seconds of user run time
  0.79 seconds of system run time
  [Run times include 0.1 seconds GC run time]
  0 page faults and
  391666344 bytes consed.

* (time (dotimes (i 10000) (genned-f (make-random-vector 28))))
Compiling LAMBDA NIL: 
Compiling Top-Level Form: 

Evaluation took:
  0.17 seconds of real time
  0.14 seconds of user run time
  0.03 seconds of system run time
  0 page faults and
  20960192 bytes consed.

indicating that the open-coding approach seems to be much faster.
Given that this code actually has to be executed millions of times, it
seems that this optimization is worth doing.

The bad (confusing) news is that the compilation time for the
open-coded functions seems quite long --- for size 434, it took about
15 seconds to compile the function, and for size 4494, it didn't
compile in 15 minutes, when I killed it.  It seems that the
compilation time of a function, even a function that just contains a
whole bunch of open-coded setf's of aref's, is superlinear in the size
of the function?  Is this normal?  Certainly, my compiler seems to
compile several hundred line .lisp files that are much more
complicated than this in under a second, so I'm not clear why this is
compiling so slow.  Any thoughts?

I'm still left with my original question to some extent.  Nils Goesche
suggested an alternate implementation where gen-array-prods-fun was a
macro instead of a function.  What are the advantages/disadvantages of
this?  Is my gen-array-prods-fun reasonable lisp, or is there
something gross about it?  Is this a good use of eval --- I was
"taught" by books that using eval almost always indicates you're doing
something wrong, but I'm not sure what it is I'm doing wrong here.  

Thanks for the replies so far.

Cheers,

rif
From: Marcus Breiing
Subject: Re: A function-generating function question.
Date: 
Message-ID: <x3YSTi5t9HHkGPETsWvfvz@breiing.com>
rif <···@mit.edu> wrote:

> It seems that the compilation time of a function, even a function
> that just contains a whole bunch of open-coded setf's of aref's, is
> superlinear in the size of the function?  Is this normal?

Yes, it probably is.  Eg, optimizations based on flow graph analysis
tend to behave that way.  You could re-run your experiment with
different optimization settings.

-- 
Marcus Breiing
···················@breiing.com (will expire)
From: Nils Goesche
Subject: Re: A function-generating function question.
Date: 
Message-ID: <lk3cqm1k9c.fsf@cartan.de>
rif <···@mit.edu> writes:

[and Barry Margolin <······@genuity.net> wrote:]

> > My suspicion is that this is premature optimization.  Iterating
> > over lists is pretty efficient in Lisp, and contorting your design
> > to avoid it is usually wasted effort.

I tend to agree...  Measuring such things can be fun, however :-)

> This operation is pretty much the whole program, and it is the
> bottleneck.

I am not yet convinced, but that doesn't mean you're wrong, of course.

> The length of the lists vary in practice between several hundred and
> several thousand, and I need to call the function millions of times.
> Right now, I'm comparing optimized versions of these two functions.
> First, the iterating over the list approach suggested by Christian
> Nyb?:
> 
> (defun make-new-array (old-array integer-list)
>   (declare (type (simple-array single-float (28)) old-array))
>   (loop with new-array = (make-array 434 :element-type 'single-float)
>         for elem in integer-list
>         and i from 0
>         do (setf (aref new-array i)
>                  (reduce #'* (map 'list (lambda (index)
>                                           (aref old-array index))
>                                   elem)))
>         finally (return new-array)))
> 
> (Note that I've hard coded in the size of the new array and the old
> array for speed.  I'm compiling with (speed 3) and (safety 0).  If
> there are any other obvious ways to optimize this function, I'm
> definitely interested.)

To get meaningful results, you should optimize this version, too.  One
thing that comes immediately to mind is, for instance:

(reduce #'* elem :key (lambda (index)
                        (declare (fixnum index))
                        (aref old-array index)))

should cons much less than the original call to REDUCE.

> indicating that the open-coding approach seems to be much faster.
> Given that this code actually has to be executed millions of times,
> it seems that this optimization is worth doing.

Maybe, but I think you are not measuring fairly, yet.

> I'm still left with my original question to some extent.  Nils
> Goesche suggested an alternate implementation where
> gen-array-prods-fun was a macro instead of a function.  What are the
> advantages/disadvantages of this?

It looks much simpler.  And it is the standard way to do what you're
doing.

> Is my gen-array-prods-fun reasonable lisp, or is there something
> gross about it?  Is this a good use of eval --- I was "taught" by
> books that using eval almost always indicates you're doing something
> wrong, but I'm not sure what it is I'm doing wrong here.

Your code is fine, I think, even the call to EVAL.  But it's gross,
too; mainly because you are not using the functionality that is
already there in form of macros.  Macros are essentially functions
that get forms and return a new form to be used instead.  They
generate code, that's what they're there for, so use them.  As you
have seen, by writing a macro you avoid both the call to EVAL and to
(SETF SYMBOL-FUNCTION), both of which are not incorrect but, well...
gross.

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

PGP key ID 0x0655CFA0
From: rif
Subject: Re: A function-generating function question.
Date: 
Message-ID: <wj0y98emj3h.fsf@five-percent-nation.mit.edu>
Nils Goesche <······@cartan.de> writes:

> To get meaningful results, you should optimize this version, too.  One
> thing that comes immediately to mind is, for instance:
> 
> (reduce #'* elem :key (lambda (index)
>                         (declare (fixnum index))
>                         (aref old-array index)))
> 
> should cons much less than the original call to REDUCE.
> 
> > indicating that the open-coding approach seems to be much faster.
> > Given that this code actually has to be executed millions of times,
> > it seems that this optimization is worth doing.
> 
> Maybe, but I think you are not measuring fairly, yet.
> 

Fair enough.  I'm definitely interested in optimizing the
make-new-array function (at least as an exercise in learning about
Lisp optimization), but I'm not sure what else to do.  The current
version is:

(defun make-new-array (old-array integer-list)
  (declare (type (simple-array single-float (28)) old-array))
  (loop with new-array = (make-array 434 :element-type 'single-float)
        for elem in integer-list
        and i from 0
        do (setf (aref new-array i)
                 (reduce #'* elem :key (lambda (index)
                                         (declare (fixnum index))
                                         (aref old-array index))))
        finally (return new-array)))

The performance is much better now, but still far from the open-coded
version:

Evaluation took:
  3.09 seconds of real time
  2.53 seconds of user run time
  0.53 seconds of system run time
  [Run times include 0.12 seconds GC run time]
  0 page faults and
  255027984 bytes consed.

Any other ideas for improving the function?

Thanks for the comments on the macro version vs. the function version.
I have to reread my "On Lisp" and try to grok macros better.

Cheers,

rif
From: Nils Goesche
Subject: Re: A function-generating function question.
Date: 
Message-ID: <87r8e68frn.fsf@darkstar.cartan>
rif <···@mit.edu> writes:

> Fair enough.  I'm definitely interested in optimizing the
> make-new-array function (at least as an exercise in learning about
> Lisp optimization), but I'm not sure what else to do.  The current
> version is:
> 
> (defun make-new-array (old-array integer-list)
>   (declare (type (simple-array single-float (28)) old-array))
>   (loop with new-array = (make-array 434 :element-type 'single-float)
>         for elem in integer-list
>         and i from 0
>         do (setf (aref new-array i)
>                  (reduce #'* elem :key (lambda (index)
>                                          (declare (fixnum index))
>                                          (aref old-array index))))
>         finally (return new-array)))
> 
> The performance is much better now, but still far from the open-coded
> version:
> 
> Evaluation took:
>   3.09 seconds of real time
>   2.53 seconds of user run time
>   0.53 seconds of system run time
>   [Run times include 0.12 seconds GC run time]
>   0 page faults and
>   255027984 bytes consed.
> 
> Any other ideas for improving the function?

Hm, not much.  It might help to declare the type of NEW-ARRAY.

Or just declare types like hell as in

(defun make-new-array (old-array integer-list)
  (declare (type (simple-array single-float (28)) old-array)
           (list integer-list)
           (optimize speed (safety 0) (debug 0) (space 0)
                     (compilation-speed 0)))
  (loop with new-array of-type (simple-array single-float (434)) =
             (make-array 434 :element-type 'single-float)
        for elem of-type cons in integer-list
        and i fixnum from 0
        do (setf (aref new-array i)
                 (reduce #'* elem :key (lambda (index)
                                         (declare (fixnum index))
                                         (aref old-array index))))
        finally (return new-array)))

and you might also write your own specialized REDUCE:

(defun make-new-array (old-array integer-list)
  (declare (type (simple-array single-float (28)) old-array)
           (list integer-list)
           (optimize speed (safety 0) (debug 0) (space 0)
                     (compilation-speed 0)))
  (loop with new-array of-type (simple-array single-float (434)) =
             (make-array 434 :element-type 'single-float)
        for elem of-type cons in integer-list
        and i fixnum from 0
        do (setf (aref new-array i)
                 (loop with ret of-type single-float = 1.0
                       for x fixnum in elem do
                       (setq ret
                             (the single-float (* ret (aref old-array x))))
                       finally (return ret)))
        finally (return new-array)))

You seem to be using CMUCL.  CMUCL issues a lot of performance
hints when you compile with high optimization settings.  Those
are usually very helpful.  And use DISASSEMBLE.

If all this /still/ is slower than the macro version,
congratulations: You have written a cool compiler for your type
of problem :-) Peter Norvig's ``Paradigms of Artificial
Intelligence Programming'' contains lots of examples for how to
write little compilers with macros.

Regards,
-- 
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.

PGP key ID #xD26EF2A0
From: rif
Subject: Re: A function-generating function question.
Date: 
Message-ID: <wj0fzulj9eh.fsf@five-percent-nation.mit.edu>
> 
> and you might also write your own specialized REDUCE:
> 
> (defun make-new-array (old-array integer-list)
>   (declare (type (simple-array single-float (28)) old-array)
>            (list integer-list)
>            (optimize speed (safety 0) (debug 0) (space 0)
>                      (compilation-speed 0)))
>   (loop with new-array of-type (simple-array single-float (434)) =
>              (make-array 434 :element-type 'single-float)
>         for elem of-type cons in integer-list
>         and i fixnum from 0
>         do (setf (aref new-array i)
>                  (loop with ret of-type single-float = 1.0
>                        for x fixnum in elem do
>                        (setq ret
>                              (the single-float (* ret (aref old-array x))))
>                        finally (return ret)))
>         finally (return new-array)))

This version gets the time down to within a factor of 2 of the
unrolled version.  So I'd agree with your initial assessment that the
unrolling isn't very necessary.

Cheers,

rif
From: Nils Goesche
Subject: Re: A function-generating function question.
Date: 
Message-ID: <87pttrbgfz.fsf@darkstar.cartan>
rif <···@mit.edu> writes:

> I have a list of lists of integers l (example: ((3 5) (1 2 3))),
> and I want to generate a function that takes an array arr and
> returns a new array whose i'th element is the product of the
> elements of arr indexed by the i'th element of l.  So for
> instance, given l as above, I want to return a function such as
> 
> (lambda (arr)
>   (let ((new (make-array 2)))
>     (setf (aref new 0) (* (aref arr 3) (aref arr 5)))
>     (setf (aref new 1) (* (aref arr 1) (aref arr 2) (aref arr 3)))
>     new))
> 
> The reason I want to do this is that the same list of lists of
> integers gets used many many millions of times, so I'd like to
> avoid going over the list of lists each time I do so.  Also,
> the list of lists of integers is several hundred elements long,
> so I don't much want to type it out by hand.
> 
> I do have a solution:

[snip]

> Which I use as follows:
> 
> * (setf (symbol-function 'f) (gen-array-prods-fun '((3 5) (1 2 3))))
> #<Interpreted Function (LAMBDA (ARR)
> 			       (LET #
> 				#
> 				#
> 				NEW))
> {497F14F1}>
> * a
> #(0 1 2 3 4 5 6 7)
> * (f a)
> #(15 6)
> 
> 
> I can also compile the function using (compile 'f), but I can't
> help but feel that I'm missing something.  Is there a better
> way to do this?  More elegant, cleaner, more idiomatic, more
> LISPy?  Is it possible to avoid using eval?  Is there any
> reason to use macros here instead of functions?  Any advice is
> appreciated.

Looks like you have reinvented macros :-) This does more or less
the same as your version:

(defun array-prods (i prodlist arr new)
  `(setf (aref ,new ,i)
	 (* ,@(mapcar (lambda (e)
                        `(aref ,arr ,e))
		      prodlist))))

(defmacro def-array-prods (f prod)
  (let ((arr (gensym))
        (new (gensym))
        (length (length prod)))
    `(defun ,f (,arr)
       (let ((,new (make-array ,length)))
         ,@(loop for i from 0
                 for list in prod
                 collect (array-prods i list arr new))
         ,new))))

CL-USER 5 > (def-array-prods f ((3 5) (1 2 3)))
F

CL-USER 6 > (f #(0 1 2 3 4 5 6 7))
#(15 6)

However, you might run into problems with CALL-ARGUMENTS-LIMIT,
which might be as small as 50!  You might also try to generate
code that uses something like

(let ((arr #(0 1 2 3 4 5 6 7)))
  (reduce #'* '(3 5) :key (lambda (i) (aref arr i))
                     :initial-value 1))

Where you generate list literals like '(3 5).

Regards,
-- 
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.

PGP key ID #xD26EF2A0
From: Nils Goesche
Subject: Re: A function-generating function question.
Date: 
Message-ID: <87lm4fbg68.fsf@darkstar.cartan>
I <···@cartan.de> wrote:

> However, you might run into problems with CALL-ARGUMENTS-LIMIT,
> which might be as small as 50!  You might also try to generate
> code that uses something like
> 
> (let ((arr #(0 1 2 3 4 5 6 7)))
>   (reduce #'* '(3 5) :key (lambda (i) (aref arr i))
>                      :initial-value 1))

You can even omit the :initial-value here.

Regards,
-- 
Nils Goesche
Ask not for whom the <CONTROL-G> tolls.

PGP key ID #xD26EF2A0
From: Drew McDermott
Subject: Re: A function-generating function question.
Date: 
Message-ID: <3DC2EF96.5090404@yale.edu>
rif wrote:
>
> I can also compile the function using (compile 'f), but I can't help but
> feel that I'm missing something.  Is there a better way to do this?  More
> elegant, cleaner, more idiomatic, more LISPy?  Is it possible to avoid
> using eval?  Is there any reason to use macros here instead of functions?
> Any advice is appreciated.

I'm not sure what the right answer to your question is, especially given 
the danger of premature optimization, but there is a _functional_ 
solution that avoids 'eval' and does as much computation as possible up 
front.  It may of interest as a curiosity, but many compilers will 
actually produce worse code with this approach than with just iterating 
through the list each time.

(defun gen-array-prods-fun (l-l-int)
    (let ((funvec
	    (map 'vector
		 (lambda (l-int)
		    (labels ((build-prod (afl)
				(cond ((null afl)
				       (lambda (a)
					  (declare (ignore a))
					  1))
				      (t
				       (let ((df (build-prod
                                                     (cdr afl))))
					  (lambda (a)
					     (* (aref a (car afl))
						(funcall df a))))))))
		       (build-prod l-int)))
		 l-l-int))
	 (new-d (length l-l-int)))
       (lambda (a)
	 (let ((new (make-array new-d)))
	    (do ((i 0 (+ i 1)))
		((= i new-d))
	      (setf (aref new i)
		    (funcall (aref funvec i) a)))
	    new))))

The idea is to create a vector of functions, the i'th of which computes 
the i'th
element of the new array given the old array.  Carrying things to 
extremes, each such function is defined so as to embody the structure of 
the integer list, so it never consults the list at run time.  For 
instance, the 0'th function constructed for your example would be
    (lambda (a)
        (* (aref a 3)
           (funcall (lambda (a)
                       (* (aref a 5)
                          (funcall (lambda (a) 1)
                                   a)))
                     a)))

A bit more source-level optimization is possible here, but wouldn't 
enlighten the issues any further.

Note that if you compile gen-array-prods-fun, the lambda expression 
produced is already compiled, and in fact inaccessible.  The result of 
gen-array-prods-fun looks like
  #<Closure (:internal gen-array-prods-fun 1) @ #x206ff452>
or some other implementation-dependent thing.  (This one is from Allegro 
6.2)

The reason some (most?) compilers will have trouble optimizing the 
returned function is that it's not obvious that the result is equivalent to

      (lambda (a)
        (* (aref a 3)
           ((lambda (a)
               (* (aref a 5)
                  ((lambda (a) 1)
                   a)))
            a)))

which would be easy to optimize.

      -- Drew McDermott
From: Erik Naggum
Subject: Re: A function-generating function question.
Date: 
Message-ID: <3245247725231909@naggum.no>
* rif <···@mit.edu>
| I have a list of lists of integers l (example: ((3 5) (1 2 3))), and I
| want to generate a function that takes an array arr and returns a new
| array whose i'th element is the product of the elements of arr indexed by
| the i'th element of l.

  To make a new vector that contains the values of some function applied to
  each element of a list in order, you can use (map 'vector <function> ...).

  To produce a product of all values in a list, you can use (reduce #'* ...).

  To extract the nth item from a vector and use it instead of n, use an
  accessor function and specify this function as the key to reduce.

(map 'vector (lambda (l) (reduce #'* l :key (lambda (n) (aref v n)))))

  If this is not fast enough, you may want to optimize only some components
  instead of writing the whole thing out in full by hand.

-- 
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.