From: jeff@aiai.edinburgh.ac.UK (Jeff Dalton)
Newsgroups: comp.lang.scheme
Subject: Abelson&Sussman; Lisp vs C in Compilers/Prog. Lang class; etc.
Date: 27 Jul 92 18:28:07 GMT
Organization: The Internet

> Date: Thu, 23 Jul 1992 20:09:58 GMT
> From: "Mark C. Carroll" <carroll@hercules.cis.udel.edu>

> >> Date: 16 Jul 92 20:36:04 GMT
> >> From: "Mark C. Carroll" <carroll@hercules.cis.udel.edu>

> >> For writing a system like a compiler, I find that the overwhelming
> >> majority of errors that I tend to make are captured by the ML
> >> typechecker, so that when I finally get a module to typecheck, that
> >> module works perfectly. (For more general types of programming,
> >> typechecking will catch some, but not all bugs. But as I said, in a
> >> compiler, the kind of errors that people seem to make are almost
> >> always revealed during the typecheck.)
> >
> >Note that you've gone from "some people (like me)" and "the majority
> >of errors I make" to "in a compiler ... the kind of errors people seem
> >to make".
> >
> >But I've just been working on some compilers, and type checking
> >wouldn't have helped _me_ very much (at least not this time), so
> >I have some doubts about your generalization.

> Well.. first, have you ever worked with an ML-like type system?
>
> If you're only typing experience is with Pascal/Ada, then you're
> certainly going to think that typing systems are not useful in a
> compiler. But the SML type system is very different... 

I am not anything like an expert on ML, but I have used it some
and I do know something about it.  In particular, I know more or
less what kind of type inference and checking it does and that
it is different (and IMHO much better) than Pascal/Ada.

I find it easy to believe that some people find the ML type system a
tremendous help in writing compilers and moreover find that it has
few, if any, disadvantages.  I'd find it a help too, but I think
languages like ML have some disadvantages.  So, on balance and all
things considered, I am happier with Lisp.  (But I've already posted
enough on that topic, I think.)

I do make type errors, but (1) they tend to be fairly easy to find,
and (2) most of them are can be caught by simple name and arity
checks.  Lisp compilers are usually capable of performing these
checks.

Another thing to bear in mind is that as soon as you start using
CLOS or some other object system you get type checking for free.
Ok, it's run-time type checking (in most cases), but since method
lookup happens at run-time anyway, and since the type error is
just "no applicable method", the checking does not involve any
additional efficiency cost.

Of course, you have to do some testing to find these errors,
since they (typically) won't be caught at compile-time.  But
a compiler will have a fairly comprehensive test suite anyway,
and in Lisp it's often pretty easy to test changes by just
typing in a test case.

> In a compiler, the typical errors seem to come from abusing the data
> structures - things like performing some kind of manipulation of the
> parse tree on a parse tree node where it's innappropriate, or
> inconsistencies in the handling of the intermediate form accross
> different constructs, etc.

So far as I can recall, I haven't had much trouble with errors of
that sort.  Except for trivial errors, most of them are things like
generating the wrong code or clearing the record of register use
at the wrong point.  But perhaps thare a lot of errors that I hardly
notice that would be caught more easily by type checking.  I suppose
it's possible.

One reason that abusing data structures seems rare may be that Lisp
programs tend to be data-driven in the sense that what-to-do is
determined by some property of the data such as its type.  Object-
oriented programming is an example.  

> In effect, for a compiler type project, typing becomes almost a system
> of checked assertions insuring that calls are consistent. 

The would certainly bne useful, but it seems to be something that
I can get by without.

Perhaps the people on this list who have written Lisp or Scheme
compilers have kept track of their bugs and can say what their
experience has been?

-- jeff