From: wilson@cs.utexas.edu (Paul Wilson)
Newsgroups: comp.lang.lisp
Subject: Re: Ideas for new LISP Machines
Date: 10 Apr 1992 17:35:48 -0500
Organization: CS Dept, University of Texas at Austin
NNTP-Posting-Host: boogie.cs.utexas.edu
Summary: tagged hardware isn't a big deal

NOTE: there's been some traffic over in comp.arch about this stuff lately,
for anybody who's really interested.

In article <19920410210242.2.SWM@SUMMER.SCRC.Symbolics.COM> SWM@sapsucker.scrc.symbolics.com (Scott McKay) writes:
>    Date: Tue, 7 Apr 1992 17:07 EDT
>    From: "David V. Wallace" <gumby@cygnus.com>
>
>       Date: 7 Apr 92 19:54:48 GMT
>       From: wilson@cs.utexas.edu (Paul Wilson)
>							     (I think most
>       of the costs of floats are the compiler's problem, not the hardware's;
>       with good inlining, dataflow analysis, etc., most floats can be raw
>       untagged values on the stack or in registers.
>
>I disagree that this is the compiler's problem.  In addition to
>providing incredibly useful hints for robust garbage collectors, tags
>also provide the same sort of hints for better debuggers.  Furthermore,
>with manifest data types in memory, the common C/C++ problem of tracking
>down wild pointers becomes a thing of the past.

My point was that the compiler can do a lot of the checking at compile
time, not that the checks aren't necessary.  Low tagging tricks and
aggressive compiler techniques can usually either do the checks in a weird
way (e.g., wrong tag causes address alignment error) or optimize them
entirely away (e.g., by inlining or customizing a method so that dataflow
analysis can tell that the check isn't necessary, because of information 
available in the sender).

>  Is a pair of tag bits
>on every memory word too high a price to pay for a giant step forward in
>robust software?

No, but you can get most of the same benefits on hardware without the
tags, so you're not going to be making a giant step.  Most of the
remaining wild pointer bugs are going to be due to the lack of array
bounds checks, dangling pointer bugs, etc.  Array bounds checks are
harder to make cheap, and you really want an agressive compiler to
help reduce the cost.  Dangling pointer bugs are due to the lack of
garbage collection, which is a language issue, not a hardware issue.

You can implement good garbage collectors on standard hardware.
Tags make it a little easier, but they're not really necessary.

Language features like undisciplined type casting and explicit pointer 
arithmetic are what make garbage collection hard, not the underlying
hardware's lack of tags.  (True real-time garbage collection is harder
to make really efficient without a write barrier, but that's going beyond
simple tags.  And the software implementation doesn't have to be too
expensive if you're willing to use a non-copying collector.)

Tags and read and write barriers are nice, but you can make a very
good implementation of Lisp without them.  Lisp machines nearly (?) killed
Lisp by distracting most of the competent implementors into side issues
like hardware at the worst possible point in the history of the language.
We ended up with Symbolics when we needed the moral equivalent of
Turbo Pascal.  We *still* don't have that---we've got Common Lisp.

Most of this is 20-20 hindsight.  But I think it's pretty clear by
now that tagged hardware is not critical for Lisp or other nice
languages.  (As I said in a recent post in comp.arch, the advantages
of tags are greater for parallelism (e.g., futures) than for dynamic 
typing.  You may want tags in hardware, but not for Lisp per se.)

  -- PRW

-- 
| Paul R. Wilson, runtime environmentalist          wilson@cs.utexas.edu      |
| U. of Texas Computer Sciences Dept.               voice: (512) 471-9555     |
| Taylor Hall 2.124, Austin, TX 78712-1188          fax:   (512) 471-8885     |
| "Inertia makes the world go 'round."              DoD M.C. # e  (Sz GS450T) |
Organization: Carnegie Mellon, Pittsburgh, PA