shebs@utah-cs.UUCP (Stanley Shebs) (03/06/85)
A short time ago, I made a statement that "Lisp is polymorphic, not typeless". Bruce Smith asks if "polymorphic" means the same as for ML. After considering all of this again, it seemed to me that the terminology is a little confused/imprecise. First, polymorphism. ML is a strongly typed language, but it is considerably more flexible than Pascal, since a function argument be of several different types. ML uses the notion of a type variable when doing its typechecking. For instance, "mapcar" (as in the Lisp function) has the type [[?a -> ?b] x (list ?a) -> (list ?b)]. In words, mapcar takes two args, the first of which is a function mapping some type ?a to some type ?b, and the second of which is a list of objects of type ?a. The result is a list of type ?b. Mapcar cannot be directly implemented in Pascal, so we have an improvement in flexibility, without giving up strong typing (and all those opportunities for compiler optimization!). Typelessness. The literature on this is kind of old, not very precise, and I'm not familiar with it. I gather that "typeless" usually means that the language has exactly one type used to represent everything else. Every function is still typed, but since there's only one type, we can let it be implicit so we don't have to declare it, or infer it, or whatever. Lisp. Lisp seems to be anomalous with respect to types - it doesn't really fall into any of the normal categories. Perhaps this is what we mean by Lisp being "weakly typed". Still too vague for my tastes though. In Lisp, any function can be passed any type of object, so you could say it is polymorphic, and every function is of type [?a x ?b x ?c x ... -> ?z], where all the type variables ?a ... ?z are unrestricted in any way. On the other hand, all the types are *really* implemented as tagged pointers to objects in a heap (there are numerous technical details and exceptions to this rule), and if you view Lisp this way, then it is really typeless in the sense that I mentioned above. Lisp has the notable feature that the different types have associated predicates (atom, consp, vectorp, numberp, etc) each of which takes anything and returns t or nil. Also, many Lisp functions do typechecking internally. Good compilers will make some attempt to compile this out if possible (the PSL compiler for example), but they don't do it very well. Question: is the strong typing of ML applicable to Lisp? If so, how could it be done? Would the basic character of Lisp have to be changed, or could it be compatible with Lisp as it is currently practiced? stan shebs