*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

know:

David Gudeman.

``Representing Type Information in Dynamically Typed Languages'',

technical report,

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

like NaN-coding.

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.

Regards,

--

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".