From: Robert Monfera
Subject: CMUCL compiler and applicative style
Date: 
Message-ID: <xagN8.2236$oC3.2662032@news2.news.adelphia.net>
The question isn't specific to CMUCL but was triggered by my reading about
the Python compiler of CMUCL.  It does amazing levels of optimization mostly
through its type inference without the burden of making code unreadable by
silly repetitions of redundant declarations or other hand-optimization.  So
having my expectations heightened, this surprised me:

http://cvs2.cons.org/ftp-area/cmucl/doc/cmu-user/compiler-hint.html#advanced
-type-stuff

Section 5.12.4:

"One of the traditional Common Lisp programming styles is a highly
applicative one, involving the use of mapping functions and many lists to
store intermediate results. To compute the sum of the square-roots of a list
of numbers, one might say:

(apply #'+ (mapcar #'sqrt list-of-numbers))

This programming style is clear and elegant, but unfortunately results in
slow code. There are two reasons why:
- The creation of lists of intermediate results causes much consing (see
5.12.2).
- Each level of application requires another scan down the list. Thus,
disregarding other effects, the above code would probably take twice as long
as a straightforward iterative version."

All three functions are known to the compiler to be free of side effect.  It
thus seems entirely possible that the compiler translates this into a simple
iteration which does not have to cons at all, in a similar way the Series
package would do it.  There is no need for creating and consuming an
intermediate list.  Other functions that can be included for cons-less
operation could include reduce, remove-if and others.  I'd find it useful.

Since Python in general is so well-rounded, what's the reason for what seems
like a glaring omission?

Robert

From: Raymond Toy
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <4nbsailzw9.fsf@edgedsp4.rtp.ericsson.se>
>>>>> "Robert" == Robert Monfera <·······@fisec.com> writes:

    Robert> Since Python in general is so well-rounded, what's the reason for what seems
    Robert> like a glaring omission?

Like all "free" software, I guess the reasons are:

o Insufficient knowledge to make it so
o Lack of desire on the part of the maintainers
o Insufficient manpower to do everything needed to make the mythical
  sufficiently smart compiler

Ray
From: James A. Crippen
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <m3hek9fent.fsf@kappa.unlambda.com>
Raymond Toy <···@rtp.ericsson.se> writes:

> >>>>> "Robert" == Robert Monfera <·······@fisec.com> writes:
> 
>     Robert> Since Python in general is so well-rounded, what's the
>     Robert> reason for what seems like a glaring omission?
> 
> Like all "free" software, I guess the reasons are:
> 
> o Insufficient knowledge to make it so
> o Lack of desire on the part of the maintainers
> o Insufficient manpower to do everything needed to make the mythical
>   sufficiently smart compiler

Indeed.  Any extra humans involved in hacking Python would be greatly
appreciated by the CMUCL community.  It's already pretty darned good,
but there are still plenty of interesting things to do.

'james

-- 
James A. Crippen <·····@unlambda.com> ,-./-.  Anchorage, Alaska,
Lambda Unlimited: Recursion 'R' Us   |  |/  | USA, 61.20939N, -149.767W
Y = \f.(\x.f(xx)) (\x.f(xx))         |  |\  | Earth, Sol System,
Y(F) = F(Y(F))                        \_,-_/  Milky Way.
From: Nicolas Neuss
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <87heka9p7b.fsf@ortler.iwr.uni-heidelberg.de>
"Robert Monfera" <·······@fisec.com> writes:

> (apply #'+ (mapcar #'sqrt list-of-numbers))
> 
> This programming style is clear and elegant, but unfortunately results in
> slow code. There are two reasons why:
> - The creation of lists of intermediate results causes much consing (see
> 5.12.2).
> - Each level of application requires another scan down the list. Thus,
> disregarding other effects, the above code would probably take twice as long
> as a straightforward iterative version."

There is an additional problem which probably causes most of the
consing, namely that generic arithmetic is involved.

> All three functions are known to the compiler to be free of side effect.  It
> thus seems entirely possible that the compiler translates this into a simple
> iteration which does not have to cons at all, in a similar way the Series
> package would do it.  There is no need for creating and consuming an
> intermediate list.  Other functions that can be included for cons-less
> operation could include reduce, remove-if and others.  I'd find it useful.
> 
> Since Python in general is so well-rounded, what's the reason for what seems
> like a glaring omission?
> 
> Robert

Probably such that people learn about things like reduce, loop,
optimization and type declarations:-).  E.g.

(time
 (loop for i of-type (integer 0 1000) below 1000
       summing (sqrt (coerce i 'double-float)) double-float))

;;; Of course, it would be fine if Python could determine at least the
;;; range of i itself.

or

(time
 (let ((sum 0.0d0))
   (declare (type double-float sum))
   (dotimes (i 1000)
     (incf sum (sqrt (coerce i 'double-float))))))

yield:

* ;;; Evaluate time
Compiling LAMBDA NIL: 
Compiling Top-Level Form: 
 
Evaluation took:
  0.0 seconds of real time
  0.0 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  0 bytes consed.
NIL
* 

Nicolas
From: Rahul Jain
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <87elfc5svi.fsf@localhost.localdomain>
"Robert Monfera" <·······@fisec.com> writes:

> (apply #'+ (mapcar #'sqrt list-of-numbers))

how about:

(collect-sum (#Msqrt (scan-list list-of-numbers)))?

see http://series.sf.net and Appendix A of CLtL2 for more info.

-- 
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  ············@techie.com   /- <-
-> -X "Structure is nothing if it is all you got. Skeletons spook  X- <-
-> -/  people if [they] try to walk around on their own. I really  \- <-
-> -\  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    /- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.
From: Robert Monfera
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <IpSN8.2753$oC3.3118024@news2.news.adelphia.net>
Thanks Rahul, I also referred to the Series package in my question, but
Series is adding a duplicate syntax for common things.  Otherwise this is
exactly what I have in mind.

Robert

"Rahul Jain" <·····@rice.edu> wrote in message
···················@localhost.localdomain...

| how about:
|
| (collect-sum (#Msqrt (scan-list list-of-numbers)))?
From: Thomas F. Burdick
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <xcvofegndgf.fsf@conquest.OCF.Berkeley.EDU>
"Robert Monfera" <·······@fisec.com> writes:

> Since Python in general is so well-rounded, what's the reason for what seems
> like a glaring omission?

I am not nor have I ever been a Python implementor, but I am working
on a CL compiler, and I've got a guess.  First, a little story :).  I
used to have this stack of compiler papers on my desk, all fairly
short.  Then it grew and grew and took over my desk and had to be
moved into a box next to the desk.  All of these papers are on some
optimization or technique or something that I'd like to add to the
compiler or use as a starting point for research for something to add
to the compiler.  I decided some time ago that there were a few
optimizations and that without a doubt were going in, and as for the
rest, I'd wait for user complaints and inefficiencies in code
generated from real source.  Because otherwise, there's just too many
things to add, and besides, if they all got run, it would take forever
to compile anything.

As for the particular optimization, you can do it with Series.  Yes,
it's true that it duplicates sequences, but it's designed keeping in
mind being able to make this style efficient.  Plus, if Series can't
create efficient code from your source, it'll complain.  You were
using Series, so you assumed it would produce fast code, so you want
this warning.  If Python emitted these warnings for applicative code
that it couldn't optimize ... well, that'd be annoying.  Seriously, do
you really want it to be /more/ talkative ;-)

-- 
           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'                               
From: Robert Monfera
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <q%aO8.3087$oC3.3357737@news2.news.adelphia.net>
"Thomas F. Burdick" <···@conquest.OCF.Berkeley.EDU> wrote in message
····················@conquest.OCF.Berkeley.EDU...

| I am not nor have I ever been a Python implementor, but I am working
| on a CL compiler, and I've got a guess.

What will be the distinguishing feature of your new compiler?

| You were
| using Series, so you assumed it would produce fast code, so you want
| this warning.

Good point.

R
From: Thomas F. Burdick
Subject: Re: CMUCL compiler and applicative style
Date: 
Message-ID: <xcvbsadmx5u.fsf@whirlwind.OCF.Berkeley.EDU>
"Robert Monfera" <·······@fisec.com> writes:

> "Thomas F. Burdick" <···@conquest.OCF.Berkeley.EDU> wrote in message
> ····················@conquest.OCF.Berkeley.EDU...
> 
> | I am not nor have I ever been a Python implementor, but I am working
> | on a CL compiler, and I've got a guess.
> 
> What will be the distinguishing feature of your new compiler?

Tight C++ integration and multiprocessing.

-- 
           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'