What is the common internal representation for algebraic types?
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?
On 2021-06-07 at 15:53 -0700, luserdroog wrote:
What is the common internal representation for algebraic types?About the general problem of data representation (assuming you care
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 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,
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 296 |
Nodes: | 16 (2 / 14) |
Uptime: | 28:08:44 |
Calls: | 6,648 |
Calls today: | 3 |
Files: | 12,193 |
Messages: | 5,328,163 |