(defun calculate-foo (bar baz)
   (+ bar (* baz +foo-constant+)))

(define-compiler-macro calculate-foo (&whole form bar baz
                                      &environment env)
  (if (and (constantp bar env)
           (constantp baz env))
      (calculate-foo bar baz)
    form))

In this case, we noticed that the function calculate-foo was
frequently, but not always, used where the arguments were available at
compile time.  The compiler macro checks to see if the arguments are
constant, and if so, computes the value at compile time and uses that.
If not, the form is left unchanged.

This one is hairier:

(defun mapfoo (function element-generator)
  (loop
      while (element-available? element-generator)
      do
        (funcall function (get-next-element element-generator))))

(define-compiler-macro mapfoo (&whole form function element-generator)
  (if (and
        ;; Look for '(FUNCTION ...)
        (consp function)
        (eq (car function) 'FUNCTION)
        (consp (cdr function))
        (null (cddr function)))
      (let ((pl (cadr function)))
        (if (and
              ;; Look for '(LAMBDA (...) ...)
              (consp pl)
              (eq (car pl) 'LAMBDA)
              (consp (cdr pl))
              (consp (cddr pl)))
            (let ((lambda-bound-variables (cadr pl))
                  (lambda-body            (caddr pl)))
              (if (and (consp lambda-bound-variables)
                       (null (cdr lambda-bound-variables)))
                (let ((generator-var (gensym))
                      (bound-variable (car lambda-bound-variables)))
                  `(let ((,generator-var ,element-generator))
                     (loop while (element-available? ,generator-var)
                        do (let ((,bound-variable (get-next-element ,generator-var)))
                             ,@lambda-body))))
               form)) ;; '(function (lambda (...) ...)) syntactically wrong.
           form)) ;; didn't find '(lambda ...)
    form)) ;; didn't find '(function ...)

In this case, we often found that MAPFOO was called with a literal
lambda expression like this:

(mapfoo #'(lambda (a-foo) (frob a-foo t nil)) (get-foo-generator))

The compiler-macro looks for this pattern, and if it finds it, turns
it into

(let ((#:G1234 (get-foo-generator)))
  (loop
    while (element-available? #:G1234)
    do (let ((a-foo (get-next-element #:G1234)))
         (frob a-foo t nil))))

So we can use the higher-order function mapfoo everywhere, but still
get the performance of the obvious loop function when we know what the
mapped function will be.  This avoids the consing of a closure, the
multiple levels of function calls, and the indirect variable lookup.

On the other hand, compiler-macros are macros, and they come with all
the variable capture problems of regular macros.  They have one great
advantage of allowing you to punt and return the original form if
things get too hairy.

But in both cases I have outlined above, the compiler-macros are
acting as a `poor-man's inliner'.  If inline declarations worked, I
could have simply declared the relevant functions as inline and not
bothered with the compiler-macros at all.  Most of our uses of
compiler-macros are to make up for this deficiency.

There are uses for compiler-macros other than getting around the lack
of inlining:  Suppose you are writing a function that has some
constraints on its arguments, e.g., the first argument should be a
compile-time constant number.  You can write a compiler macro to check
that this is the case.

USER(9): (funcall (compiler-macro-function 'match-regexp)
                  '(match-regexp "foo" "barfoobaz") nil)
(MATCH-REGEXP (LOAD-TIME-VALUE (COMPILE-REGEXP "foo")) "barfoobaz")

  "Increasing Readability and Efficiency in Common Lisp"
  Ant\'{o}nio Menenzes Leit\~{a}o
  aml AT gia DOT ist DOT utl DOT pt
  Proceedings of the European Lisp User Group Meeting '99

  Abstract:
  Common Lisp allows programmer intervention in the compilation process by
  means of macros and, more appropriately, compiler macros. A compiler
  macro describes code transformations to be done during the compilation
  process. Unfortunately, compiler macros are difficult to write, read and
  extend. This article presents a portable extension to Common Lisp's
  compiler macros. The extension allows easy definition and overloading of
  compiler macros and is based in two known techniques, namely pattern
  matching and data driven programming. Three different uses are presented:

  (1) Code optimization, (2) Code deprecation, and (3) Code quality
  assessment. The extension is being used extensively in the reengineering
  of a large AI system, with good results.

As I write this I am offline and I don't know whether the paper is also
available at a Web site. If you need a copy of the proceedings you may
contact Franz's sales department. The proceedings include another paper by
the same author, titled "FoOBaR - A Prehistoric Survivor", which
illustrates the evolution of the large AI system mentioned in the abstract.

I find that something which will show up at compile time in an ST
language will show up immediately on even the most cursory of testing in
a DT language.  Call a function with the wrong type and it'll usually
give an error the first time you run the code (whereas calling with
incorrect values may require extensive testing to find).  The bugs that
make it past testing into production code, IME, are of a very different
nature, and usually result from misunderstood specifications or poor
design.

There is an advantage in *convenience*: in an ST language I can have a
bunch of errors found for me for the effort of typing 'make' rather than
having to run tests.  OTOH, there's a cost in convenience of having to
write the type declarations (and of having to explicitly say so when you
really do want 'any type', e.g. for collection classes).  On the third
hand, I usually need to figure out what the types should be anyway from
a design point of view.  Six of one, half a dozen of the other.

I'm inclined to the opinion that this whole issue of typing errors is
worth, at a generous estimate, a tenth the amount of ink/electrons
that's been spilled over it :)

I had a minor epiphany in this direction just the other day, so I hope
you'll forgive the evangelism.

Cheers,
Michael

(But I agree with some of what you've said and other posts on this
thread show that some static type checking is possible - it varies
significantly with the implementation).

Andrew

/Jon

It's not that "static typing is downright bad, and never finds errors
for you."

It is rather the case that if you construct the "unit tests" *that should
be built* to examine boundary cases and the likes, this will indirectly
provide much of the testing of types that you suggest need to be implicit
in the type system.

  (check-type <argument> <restricted-type>) takes care of this one for you,
  or you can use assert or throw your own errors if you really have to.  I
  don't see the problem.  writing safe code isn't hard in Common Lisp.

| Static typing is dramatically useful in integration tests.  A unit test
| will not exhaustively exercise other units.  Static typing allows units
| to fit together without the piles of dumb stupid interface errors,
| allowing you to concentrate on the smart stupid logic errors :-).

  when the compiler stores away the type information, this may be true.
  when the programmers have to keep them in sync manually, it is false.

  static typing is like a religion: it has no value outside the community
  of believers.  inside the community of believers, however, it is quite
  impossible to envision a world where static types do not exist, and they
  think in terms that restrict their concept of "type" to that which fits
  the static typing religion.

  to break out of the static typing faith, you have to realize that there
  is nothing conceptually different between an object of type t that holds
  a value you either know or don't know how to deal with, and an object of
  a very narrow type that holds a value you either know or don't know how
  to deal with.  the issue is really programming pragmatics.  static typing
  buys you exactly nothing over dynamic typing when push comes to shove.
  yes, it does buy you something _superficially_, but look beneath it, and
  you find that _nothing_ has actually been gained.  the bugs you found are
  fixed, and the ones you didn't find aren't fixed.  the mistakes you made
  that escaped the testing may differ very slightly in expression, but they
  are still there.  the mistakes you did find may also differ slightly in
  expression, but they are still gone.  what did you gain by believing in
  static typing?  pain and suffering and a grumpy compiler.  what did you
  gain by rejecting this belief and understanding that neither humans nor
  the real world fits the static typing model?  freedom of expression!  of
  course, it comes with a responsibility, but so did the static typing,
  only the dynamic typing responsibility is not to abuse freedom, while the
  static typing responsibility is not to abuse the power of restriction.

  personally, I think this is _actually_ a personality issue.  either you
  want to impose control on your environment and believe in static typing,
  or you want to understand your environment and embrace whatever it is.

For the static typing believers (of which i'm not) here is a new language
that is supposed to be a "Typed Lisp" "even faster than C" "As a summary:
Pliant is typed-Lisp + C++ + reflective-C in one language"

They got rid of the GC, which is rather unusal for a lisp...

You can look at the rest here: http://pliant.cams.ehess.fr/pliant/

I freely admit, however, that with Lisp systems at least, the consequences of
no static typing are not as important as with other languages, mainly due to
the built-in abilities of the language. One just doesn't corrupt things as
easily.

It's not about "believing" in static typing. It's about being able to describe
an abstraction to an appropriate level of detail. Any tool support that can
aid in verifying it is only a win.

The responsibility is simply to do things "right" :-).

The "Lisp assumption" is that this is *not* the case.  

Alternatively, if this *should* be the case, then it may make sense to
define the function as a CLOS method, and attach typing information to
the method, at which point you get similar guarantees to those
provided by static type checking.

But at any rate, by the time you've thrown boundary case testing at
the code, it is relatively unimportant what kinds of values are
invalid.

If each function has been tested to verify that it accepts reasonable
input, and produces reasonable output, I'm not terribly worried about
how it copes with unreasonable input/output.  After all, *all* of the
functions are producing reasonable output, right?

The point here is that CLOS does "type-based" dispatching which
grapples with at least part of the "dumb stupid" interface problems.

What sort of type errors do you make that get caught in languages
with static typing?

Having to write

    #define FOO(x) do { ... } while (0)

in C is "fighting the compiler". So is having to make up names
for intermediate objects if you want to set up (at compile
time) a nested structure where the nesting is done via pointers.
So is having to allocate and free temporary objects explicitly
on account of there being no GC.

All these things are just consequences of the language being
how it is, yes. That doesn't mean that the restrictions and
annoyances aren't real. The programmer *doesn't* have complete
freedom to change things; s/he can't change the language.
I don't think that "it's unpleasant to express in C" indicates
a flaw in the design of a program. It might indicate a flaw
in the design of C.

I'm not saying that a design should take no notice of the
language it's likely to get implemented in, of course. I'm
saying that often the best design still lumbers you with some
annoyances in implementation that could have been alleviated
if the language had been slightly different, and that these
count as "fighting the compiler".

[1] I haven't done anything non-trivial in languages like ML and
    Haskell that are statically typed but have "better" type
    systems than C's.

Also, consider that unit tests often use "stub" versions of other units, since
they might not be available yet, be mutually dependent, etc. In that case
exercising your unit can test it adequately, but you can still miss bad calls
to the other units due to differences in behaviour between the stubbed
versions and the real versions. Some sort of interface specification ability
(static typing, CLOS style descriptions, whatever) can help reduce these
problems.

  (let ((p (make-point 1 2))     ; Assume representation as a list of length 2
        (r (make-rational 3 4))) ; Ditto
     (draw-to p)
     (draw-to r) ; Shouldn't be allowed.
     (draw-to (point-of r))) ; Ok, now I am being explicit

This is an example only to illustrate a type mismatches due to identical
representations. Forget for the moment that real Lisp structs and rational
numeric types exist.

Another common situation is getting parameter values right. E.g.

  (defun make-person (name age) ...)

  (let ((p1 (make-person "Joe" 5)) ; Ok.
        (p2 (make-person 15 "John"))) ; Not ok.
     ...)

Note that I don't consider C to be any sort of reasonable statically typed
language. C++ can be alright if one disciplines themselves to stick the
classes as much as possible and avoid the macros and low level features. The
primary example of a "traditional" statically typed language is Ada, with its
rich type specification ability. [Most Ada programmers are serious static
typing freaks. If people think I am a zealot about this, they haven't met the
real ones yet. I am distinctly mellow by comparison.]

Haskell and ML I would like to learn more about since they seem fundamentally
more expressive.

OTOH since a meaningful unit test will have to cover all executable
branches of code anyway, this kind of error will always be caught with
no additional testing effort, as long as the types of the arguments
and parameters that are mismatched are indeed different.  Given the
prevalence of string and integer types, this will often not be the
case, in which case both static and dynamic typing will break down.
This is one of the reasons why I think that environmental support
(automagic display of lambda lists, online HyperSpec) is the better
way to tackle issues of this sort.

Things will get a little more complicated to test when the type of a
parameter depends on dynamic properties of the program:

  (make-person (blabla <something dynamic>) 5)

OTOH in statically-typed languages the code will look like this:

  (make-person (union-string (blabla ...)) 5)

I.e. blabla now has a declared union type, and you need to explicitly
invoke the union accessor that gets you the string, for this to
type-check correctly.  BUT you'll still need to test, since the
accessor will fail (either loudly (=> strongly-typed), or silently (=>
C unions)) at run-time, if the return value isn't the string variant
expected.  You simply can't do better than run-time checking here.

Some B&D languages will make you put in a case construct, but since
you'll only raise an error in the else case anyway, this doesn't get
you more safety, but gives you more headaches.  B&D.

I believe that anyone who doesn't exercise each part[1] of a unit at
least once during testing deserves any bugs he gets.  I also believe
that static-typing would be more useful if computer programs consisted
of total, non-discrete functions.  Since they don't, it isn't.  ;-)

Regs, Pierre.

Footnotes:
[1]  Note that this is different from (and easier than) exercising
     each possible path through a program/unit/function.  The one
     grows linearly, the other grows exponentially.

    (let ((p1 (make-person :name "Joe" :age 5))
          (p2 (make-person :age 15 :name "John")))
      ...)

I suppose the point of all this is that static typing does
buy you something, but that in a well-designed dynamic language
the amount it buys you is very little unless you choose to
shoot yourself in the foot.

Let me flip to Ada for a second:

  type Seconds is range 0 .. 59;
  type Minutes is range 0 .. 59;

These are both integer types, both with exactly the same representation, and
yet because they are different types, I cannot accidently use minutes where
seconds is required, and vice versa. E.g.

  declare
    m : Minutes;
    s : Seconds;
  begin
    s := 10;
    m := s; -- won't compile
    m := Minutes(s); -- ok, explicit conversion
  end;

To me the representation of an object is in general a private thing to the
object, and a user of the object should only think in terms of the allowable
operations on the object.

  p2 := Make_Person (Age => 15, Name => "John");

Hmmm.

I think the issue here is this example is not really appropriate to Lisp, where
objects of different types have different representations by definition. If I
used real Lisp types, my example becomes good old fashioned parameter type
mismatch:

  (let ((p (make-point 1 2)) ; a struct
        (r 3/4))
    (draw-to p)  ; ok
    (draw-to r)) ; error

See my reply to Gareth for a realistic example in Ada of different types with
identical representations.

Now it all depends what you are doing, and in what language. For a smallish
system the testing of all representative paths with actual units is feasible
and will indeed catch the error. Large systems, on the other hand need every
bit of automated error detection they can reasonably get.

  class Root
  {
    public void Doit ()
    {...}
  }

  class Descendant extends Root
  {...}

  void DoADescendant(Descendant d)
  {...}

  void DoARoot(Root obj)
  {
    obj.Doit(); // I don't know the exact type, but I know I can do this.
    DoADescendant(obj); // run-time check
  }

In DoARoot, know I cannot be passed anything else but an object descended from
Root. Thus I don't have to test such cases such as trying with a string, an
integer, a whatzit. Clients cannot accidentally call DoARoot with such cases.

Static typing is only a additional tool in a programmer's bag of useful
tricks. Maybe I should really be saying "machine verifiable specification
abilities".

A question, though: does the decrease in testing time that
comes from declaring all your counts of minutes and seconds
explicitly make up for the increase in coding time that
comes from, er, declaring all your counts of minutes and
seconds explicitly?

Actually, this particular example isn't so great because
the Right Answer is almost certainly not to have separate
types for minutes and seconds, but to have objects for
holding times, or time intervals, of which minutes and
seconds would just be special cases. But there are other
parallel examples where similar options aren't available.
(Distances and angles, maybe.)

These examples make me wonder whether there's anything to
be said for giving a programming language a notion of
*units*, so that (+ (minutes 5) (seconds 5)) is (seconds 305)
and (+ (metres 10) (square-metres 10)) is a type error.
It's probably just much, much too painful. :-)

(There are systems that let you do things like this.
For instance, the "Mathcad" package does.)

In ML there are types like "list of integers" or "function
that, given an object of any type, returns a list of objects
of that type". CL's type system doesn't have those. On
the other hand, I don't think ML has the "list of objects
of any types" type.

The payoff is not so much a decrease in testing time. It is substantial
decrease in development time in general. The Ada development cycle tends to be
compile->link->run with the occasional foray into the debugger. C++, by
comparison is more like compile->link->whoops, unresolveds!->link->debug->
debug->debug->...->eventually run for real.

On the other hand, Ada is fundamentally a compiled language, with a mandatory
analysis phase. An interpreted version of Ada would be tedious to use indeed.

But this is not an Ada newsgroup, and I think I have said enough on the matter.