Post by luserdroog
What is the common internal representation for algebraic types?
Say I wanted to add a complex typing system to a simple homebrew
Lisp interpreter, how would I go about doing it? I suppose the contrite
answer is "lists", but does anyone have any more detail or references
to where I can learn about how to build something like this?
About the general problem of data representation (assuming you care
about efficiency) I like this old survey, which is still the best I
``Representing Type Information in Dynamically Typed Languages'',
Department of Computer Science, The University of Arizona, 1993.
Nowadays some solutions are more convenient than others; for example
tagging in the low bits is compatible with conservative-pointer-finding
garbage collection, while tagging in the high bits is not. Some people
Algebraic types, as Paul Rubin hints at, are sums of products. The
general complex case will always require boxed values; but the simple
case (equivalent to C enumerates) is important in practice and worth
optimising: it is possible to arrange for a practically unbounded amount
of distinct unique objects. In Lisp you should have already built the
required machinery when implementing Booleans and the empty list, if it
is a different object.
Luca Saiu http://ageinghacker.net
I support everyone's freedom of mocking any opinion or belief, no
matter how deeply held, with open disrespect and the same unrelented
enthusiasm of a toddler who has just learned the word "poo".