3 ms·

I don't think this is really accurate anymore. Using the list data type as the compiler's internal representation causes problems as there is nowhere to store i

I don't think this is really accurate anymore. Using the list data type as the compiler's internal representation causes problems as there is nowhere to store information the compiler needs need, such as locations for error reporting, or value representation for optimisation, and so on. You either end up using some awful hack (e.g. the second element of each list is an a-list of compiler specific info) or you use a different data type. This latter is the approach that Racket, the Lisp I'm most familiar with, takes. Programs are represented using a "syntax" data structure that is not list, though it can be converted into one. See HLists (e.g. https://hackage.haskell.org/package/HList https://hackage.haskell.org/package/HList) for heterogeneous lists in Haskell. The techniques for implementing these are relatively (last 10 years or so).

deleted 12y ago
[deleted]
dschiptsov 12y ago
The problem is very simple - as long as a list is homogenous or it is a finite either-of algebraic data type, you could infer the type of a function on these - it could be a another homogenous list or a value if some other type. As long as a list could contain anything then it could be mapped to another list of anything (a list of symbols, numbers, etc.) Or a value. Basically, we could say a pointer or a list of pointers, which by definition could point to any kind of a type-tagged value. Types a-la (* -> *) -> [*] -> [*] are't very useful, but this is what we have in Lisps. Moreover, as long as there is no difference between a pointer to a list and pointer to a value (these are just bindings of symbols to type-tagged values) we could have procedures of type * -> * -> * Lisp stands for LISt Processing after all, for performing so-called symbolic manipulations (like our minds do) and this is a pretty good "type" for a procedure doing a symbolic transformation. So, all the values have type-tags. Add NIL and T, structural types such as arrays or structs, and you will get a crude type hierarchy of a Lisp. Our lists aren't sets (homogenous) so all the typing based on Set theory is of no use.
- noelwelsh 12y ago
  My first paragraph was referring to lists (not) being the internal representation of programs within (modern) Lisps. Nothing about heterogeneous lists or type theory there. Second paragraph is about heterogeneous lists.
  - dschiptsov 12y ago
    I am sorry, I am not a type theorist. Someone added a link to an attempt of define a statically-typed Lisp. I am suggesting to try to look deeper what a Lisp is and why it is the way it is.

deleted 12y ago

[deleted]

dschiptsov 12y ago

The problem is very simple - as long as a list is homogenous or it is a finite either-of algebraic data type, you could infer the type of a function on these - it could be a another homogenous list or a value if some other type. As long as a list could contain anything then it could be mapped to another list of anything (a list of symbols, numbers, etc.) Or a value. Basically, we could say a pointer or a list of pointers, which by definition could point to any kind of a type-tagged value. Types a-la (* -> *) -> [*] -> [*] are't very useful, but this is what we have in Lisps. Moreover, as long as there is no difference between a pointer to a list and pointer to a value (these are just bindings of symbols to type-tagged values) we could have procedures of type * -> * -> * Lisp stands for LISt Processing after all, for performing so-called symbolic manipulations (like our minds do) and this is a pretty good "type" for a procedure doing a symbolic transformation. So, all the values have type-tags. Add NIL and T, structural types such as arrays or structs, and you will get a crude type hierarchy of a Lisp. Our lists aren't sets (homogenous) so all the typing based on Set theory is of no use.

noelwelsh 12y ago
My first paragraph was referring to lists (not) being the internal representation of programs within (modern) Lisps. Nothing about heterogeneous lists or type theory there. Second paragraph is about heterogeneous lists.
- dschiptsov 12y ago
  I am sorry, I am not a type theorist. Someone added a link to an attempt of define a statically-typed Lisp. I am suggesting to try to look deeper what a Lisp is and why it is the way it is.