[Gcl-devel] Re: on incf

[Camm Maguire]

Robert Boyer <address@hidden> writes:

> >   This appears to be working in my local copy at the moment.
> 
> >   This is probably not of interest to anyone but me, but its been
> >   nagging at me for a long time.
> 
> How utterly remarkable!  This may help lead the Lisp community towards much
> better programming.
> 

Its mostly intended to scratch the itch I always feel having to
remember to add :test 'eq to the end of member for a simple symbol
lookup, etc.  Hopefully others have the same itch.  GCL even had its
own si::memq hack to the same effect.  Without this of course one has
the eql function call inside the loop. 

Personally I can't ever seem to bring myself to the loop macro, though
it works in GCL just fine -- programming and English are to me two
very different things, making loop code actually less readable, IMHO.

The way the set of mods (to {member, assoc, rassoc}{ , -if, -if-not},
intersection, set-difference, subsetp, set-exclusive-or) I'm working
on at the moment operate is to look at the item and the items in the
list if possible, determine whether eql can be replaced with eq, and
write the search inline as a do loop if so.  If not, then test the
item once at the head of the loop and branch to the eq lookup loop at
runtime if appropriate.  Heavy use is made of wrapping tests and keys
in lambda functions, which in the case of fixed args to the lambda
expression pass through (funcall (lambda ...)) -> ((lambda ...) args)
-> (let* (lambda-bindings, args) lambda-body) without ever compiling
or calling a separate closure.  These are passing all Paul's tests.

Its ready to commit, I'm just struggling over the implementation.
GCL's compiler basically does macro-expansion/compiler-macro-expansion,
then type propagation and function and  variable structure
construction in pass1, then inlining and c code generation in pass2.
The right way to do this is at the level of compiler macros, which
output pure lisp and have no access to type information, so would have
to output the item test and branch explicitly in lisp and rely on
pass1 recognizing that the test was a constant t and eliminating the
branch.  The way I've done it now is in pass1 where the type info is
right there allowing me to omit the branch explicitly.  The problem
with this is that it does not allow the compiler to determine anything
about variable modifications etc. without going through pass1, as one
is never sure what lisp you'll actually run until that point.  Perhaps
we shouldn't be trying to do this anyway, but we do in auto-declaring
constant let bindings for example, though we avoid pass1 for this
purpose purely out of compile-time efficiency considerations
(e.g. compiling pcl).  The problem with the 'right-way' is making sure
the branch-test form is recognized as a constant, though perhaps this
is not so difficult. 

If we could achieve the 'right-way', then we might be able to solve
another problem -- keeping the interpreted function, compiled
function, and compiler inlining in sync.  We could do this by only
defining the compiler macro, and defining the function as its
expansion on generic arguments.

I intend to do the same with the sequence functions -- branching to
list or array loops inline when possible and eliminating the branch
when the compiler can so determine.  I don't yet know if there are
higher order array (e.g. non-vector) loop functions which can be
treated in like manner.  It would be great to be able to write a
matrix vector multiply as a loop over dot or axpy, for example.
Perhaps this is what array displacement was meant to accomplish.

> I believe that there is a significant group of academic/scientist folks
> interested in higher order function stuff, (SASL, Haskell, ML, Coq et al.)  I
> think that LOOP evolved largely because the higher order stuff in Lisp wasn't
> especially efficiently done, whereas PROG and friends, under the influence of
> FORTRAN, did offer some efficiency.
> 
> > the compiler should be smart enough to put in many of them itself.
> 
> This is somewhat true.  In the case of a declared double-float
> conglomeration, and given the nice way that floating point infinity, its
> contagion, and the IEEE rules work together, the automatic declarations can
> probably be provided.
> 
> On the other hand, in a FIXNUM vs. BIGNUM situation, things are radically
> different and harder.  It may be that most FIXNUM declarations are simply
> lies!  Reasonable input can be found that will cause BIGNUMs, not FIXNUMs, to
> be generated; but the programmer does not really know (nor does he care much
> because he is so sloppy or so pressed for time) exactly when overflow will
> happen.  It's just Y2K all over again.  Folks in the 60s and 70s (even Alan
> Greenspan) felt it was sensible to "declare" that the year was a two digit
> field.  But it simply wasn't true.  (Any more than it is true that it is now
> a four digit field!  In 8000 years, we'll have a lot of trouble.)  So
> FIXNUM/BIGNUM declaration efficiency in LISP often involves a lot of
> irresponsible guess making, and I doubt the compiler will be able to do a
> "good job" because there may be no such thing!  The GCL compiler could do
> more in the direction that the CMU compiler has taken with warnings to help
> the user know when and why FIXNUM/BIGNUM penalties are being paid.  But even
> the CMU approach commentary is frustrating to use, at least to me.  The
> essential thing is that someone smart (compiler and/or programmer) has to
> look very carefully at every open parenthesis asking, Have I declared what is
> true about the type of every argument to this form? and Have I declared what
> is true about the output of this form?
> 

I agree with this in general -- hence the importance of taking the
approach you so helpfully advocated in accelerating generic fixnum
arithmetic, etc.  Furthermore, the hooks are now in place to call gmp
functions directly from compiled code on unboxed bignum objects should
we so desire, though I don't imagine this is very important.  

There is one key area, though, which I feel the compiler should be
able to get fixnum declarations by itself, and that is when the var is
used as a sequence index (i.e. in aref or nth).  Lisp seems to have
this notion of 'safe and 'unsafe code, which I loosely understand as
"check everything and signal an error on any type mismatch",
vs. "you've written the code correctly so it won't throw an error, now
I can make assumptions about your variables".  In the latter case, one
should be able to auto-declare sequence indices in certain
circumstances.  And this appears to be the lion's share of the issue
in the first place as far as integers go, in my limited experience.

We have already made use of this so substantial effect IMHO in
auto-declaring constant let bindings.  Thus, we use compiler macros to
rewrite each aref for example as (let ((gensymed-var
(array-row-major-index ...))) (cmp-aref array gensymed-var)), the
gensymed-var is a constant binding and is auto-declared as a sequence
index from type propagation from array-row-major-index, and cmp-aref
is inlined using this knowledge to dereference the linear array body
directly.  Thus, the original incf problem is gone in the mflop
examples, for example.  Should you desire currently unenlightening
compiler verbiage at the moment, (setq 
compiler::*suppress-compiler-notes* nil).

If we could expand the auto-declaration to include variable
modifications where the new type is a subtype of the initial type, and
to include deducing fixnum bounds from loop exit conditions, then I
think we'd be done with this particular facility.  

Take care,

> Bob
> 
> 
> 

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