From: His Holiness the Reverend Doktor Xenophon Fenderson, the Carbon(d)ated
Subject: Storing, accessing type information at run time
Date:
Message-ID: <w4oiu7vdfs7.fsf@nemesis.irtnog.org>
-----BEGIN PGP SIGNED MESSAGE-----
I'm thinking about writing a Lisp compiler.
My reading of the Common Lisp HyperSpec implies the existence of type
information at run time, not just at compile time. This is consistent
with how I've used Lisp in the past, i.e. as a glorified interpreter.
If type information needs to be available to a running program, what's
the best way to store (or access) type information?
In thinking about this problem, I've come up with two scenarios:
1. Store type information with each object, i.e. each object is
prefixed with a bit-field denoting its type.
Advantages: O(1) access to type information, no need to do any kind of
accounting (registration of the object with the type system), and
simplifies garbage collection (unregistration of the object).
Disadvantages: Makes interfacing to other languages more complex
(e.g. the foreign functions interface must encode/decode Lisp objects
before passing them to external functions).
I think this is how most Lisp implementations work (e.g. EMACS,
Bigloo).
2. Store type information outside of each object, e.g. in a hash.
Advantages: Passing data to foreign functions is simple (no
pre/post-processing).
Disadvantages: No longer O(1) to access type information, accounting
is more difficult (must remember to unregister the object upon
deallocation, etc.)
Since I know relatively little about run-time type systems, would
anyone point me to the relevant literature, or, better yet, comment on
my thoughts thus far? Appel's _Modern Compiler Implementation in X_
is no help (it barely even discusses run-time systems!), and
Queinnec's Scheme-to-C compiler in _Lisp in Small Pieces_ tags each
Scheme object (idea #1 above).
Actually, I don't know enough about what I'm trying to do to even
formulate a good question. Any references to useful literature would
be appreciated.
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface
iQCVAwUBN4QPxJKs3Px4OAitAQFZ1wP/Uez8SNiMJcHx7hCc2zfiWcuHjXEdg5ky
uS4RtqrymZ0hKP/jHZ7OQld3WC4SzwMQwKNA4hNFLrEV1XSjDm2m6b/AqenUt6xn
YbPCMBKcUZUdWaZ/OQiJihlEkUNBocUipAQJFJV7s2s++6hFvykrcV3PXQi8N7jT
OieO4ENuDr4=
=WM8Y
-----END PGP SIGNATURE-----
--
Rev. Dr. Xenophon Fenderson, the Carbon(d)ated, KSC, DEATH, SubGenius, mhm21x16
Pope, Patron Saint of All Things Plastic fnord, and Salted Litter of r.g.s.b
``The lyf so short, the craft so long to lerne.'' - Chaucer
From: Christopher R. Barry
Subject: Re: Storing, accessing type information at run time
Date:
Message-ID: <874sjf39w9.fsf@2xtreme.net>
"His Holiness the Reverend Doktor Xenophon Fenderson, the Carbon(d)ated" <········@irtnog.org> writes:
> My reading of the Common Lisp HyperSpec implies the existence of type
> information at run time, not just at compile time. This is consistent
> with how I've used Lisp in the past, i.e. as a glorified interpreter.
> If type information needs to be available to a running program, what's
> the best way to store (or access) type information?
Type-checking in modern Lisps is 9 times out of 10 implemented in a
client/server fashion. The type-server supports type requests from
Lisp clients over a variety of transports including HTTP over TCP/IP
and is thus truly network-transparent. SRI pioneered the technology
alongside hypertext and the mouse throughout the late 60s and 70s and
the Lisp Machine has had this technology at least since the early 80s.
> In thinking about this problem, I've come up with two scenarios:
>
> 1. Store type information with each object, i.e. each object is
> prefixed with a bit-field denoting its type.
No, this implementation strategy completely negates any possibility of
a distributed, shared types database. Large sites typically assign a
type-server to every 6 hosts as a rule-of-thumb, and they would be
very reluctant to deploy an implementation utilizing this technique.
> Actually, I don't know enough about what I'm trying to do to even
> formulate a good question. Any references to useful literature would
> be appreciated.
In the CMU sources look at $TRUNK/src/compiler/type-serve.lisp for an
excellent free implementation. It was originally written to allow Mach
server-machines at CMU to smoothly serve typing information to 20
hosts or more in congested network traffic conditions so sadly
performance over the loopback device may not be what your hoping for.
Christopher
······@2xtreme.net (Christopher R. Barry) wrote:
>Type-checking in modern Lisps is 9 times out of 10 implemented in a
>client/server fashion. The type-server supports type requests from
>Lisp clients over a variety of transports including HTTP over TCP/IP
>and is thus truly network-transparent. SRI pioneered the technology
>alongside hypertext and the mouse throughout the late 60s and 70s and
>the Lisp Machine has had this technology at least since the early 80s.
you forget to tell our friend the most important point, how to put the
nowadays most common cpu's into tagged-type-mode. type tags are usually
embedded in hardware now, you need a tag chip and you must know the
secret opcodes or CMOS flags to enable this feature. this typically
involves a reboot!
--
Reini
From: Gareth McCaughan
Subject: Re: Storing, accessing type information at run time
Date:
Message-ID: <867lobf43l.fsf@g.pet.cam.ac.uk>
Christopher R. Barry wrote:
> Type-checking in modern Lisps is 9 times out of 10 implemented in a
> client/server fashion. The type-server supports type requests from
> Lisp clients over a variety of transports including HTTP over TCP/IP
> and is thus truly network-transparent. SRI pioneered the technology
> alongside hypertext and the mouse throughout the late 60s and 70s and
> the Lisp Machine has had this technology at least since the early 80s.
...
>> 1. Store type information with each object, i.e. each object is
>> prefixed with a bit-field denoting its type.
>
> No, this implementation strategy completely negates any possibility of
> a distributed, shared types database. Large sites typically assign a
> type-server to every 6 hosts as a rule-of-thumb, and they would be
> very reluctant to deploy an implementation utilizing this technique.
...
> In the CMU sources look at $TRUNK/src/compiler/type-serve.lisp for an
> excellent free implementation. It was originally written to allow Mach
> server-machines at CMU to smoothly serve typing information to 20
> hosts or more in congested network traffic conditions so sadly
> performance over the loopback device may not be what your hoping for.
Am I missing some sort of subtle joke? Is this a parody of something?
(I don't know of any Lisp system that does type-checking "in a
client-server fashion", the number of sites that would have any
use for a "type-server" is infinitesimal, and there is no such file
as src/compiler/type-serve.lisp in the CMU sources. I have the
feeling that maybe this would be riotously funny if I knew what
it was making fun of.)
--
Gareth McCaughan Dept. of Pure Mathematics & Math. Statistics,
················@pobox.com Cambridge University, England.
From: Christopher R. Barry
Subject: Re: Storing, accessing type information at run time
Date:
Message-ID: <871zej2cwo.fsf@2xtreme.net>
Gareth McCaughan <················@pobox.com> writes:
> (I don't know of any Lisp system that does type-checking "in a
> client-server fashion"
Any _modern_ Lisp will do this. Time to ditch that copy of GCL or
MacLisp, Gareth, and step into the 90s before the're out.
> the number of sites that would have any use for a "type-server" is
> infinitesimal
Hah! Try telling that to the book-keepers at CMU!!!
> and there is no such file as src/compiler/type-serve.lisp in the CMU
> sources.
Obviously the integrity of the archive you extracted your CMU sources
from was some how compromised. Use this MD5 checksum:
1f0ca4b381af99de24aef47e0a390cdd
> I have the feeling that maybe this would be riotously funny if I
> knew what it was making fun of.)
The Brits say water flouridation rots the brains of Americans, but at
least we don't have British smiles!
Christopher
From: Rob Warnock
Subject: Re: Storing, accessing type information at run time
Date:
Message-ID: <7m2152$79crf@fido.engr.sgi.com>
<········@irtnog.org> wrote:
+---------------
| Since I know relatively little about run-time type systems, would
| anyone point me to the relevant literature...
+---------------
Go to http://www.cs.indiana.edu/scheme-repository/doc.publications.html
and you'll find lots of interesting papers, in particular:
- Gudeman. "Representing Type Information in Dynamically Typed
Languages." (typeinfo.ps.gz)
contains a nearly exhaustive survey of run-time type representations.
-Rob
p.s. If you're not already familiar with the "big bag of pages" method,
be sure and read:
- Dybvig, Eby, and Bruggeman. "Don't Stop the BIBOP: Flexible and
Efficient Storage Management for Dynamically Typed Languages",
Indiana University, March 1994. (iucstr400.ps.gz)
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. FAX: 650-933-0511
Mountain View, CA 94043 PP-ASEL-IA