corvara@ztivax.UUCP (Dr Gerd Venzl) (06/24/91)
To remind you, in article <5528@ztivax.UUCP> I wrote: > I've been wondering about the motivations for some decisions made in the > design of Standard ML. They concern a couple of useful concepts well known > from imperative languages, namely overloading, subtypes, and arrays. While > these could certainly provide there benefits in a functional setting as well > they have been omitted in the definition of SML. > ... > Could anyone point out to me the substantial reasons and problems that lead > to the omittance of the three named concepts in SML? Have these concepts > been embedded in other functional languages? Now, here is a summary of the answers I received. Thanks to anyone who replied. Torsten Roessel Siemens Corporate Research & Development Design Automation Department InterNet: roessel@ztivax.siemens.com ------------------------------------------------------------------------------- From: Robert Harper <rwh@cs.cmu.edu> Organization: School of Computer Science, Carnegie Mellon University ------------------------------------------------------------------------------- The main reasons for not including these features was that at the time of the design of Standard ML (1986) these features were not sufficiently well understood to merit inclusion in the language. In particular, the interaction between subtyping and polymorphism was barely, if at all, understood. The decision as to whether or not to admit user-defined overloading was hotly debated. I don't recall the exact reasons, but it was decided by consensus that it would not be admitted, even though the Edinburgh compiler at the time supported such a feature. With regard to records, the state of the art at the time was such that no reasonable scheme for integrating a more flexible record calculus into the language was available, and we had to make do with using the primitive features that we could readily define. Since then a number of studies have shed considerable light on this matter; in particular, CAML provides a very reasonable mechanism for flexible use of records. Finally, arrays are supported as part of the initial standard basis; there is no special linguistic support required. ------------------------------------------------------------------------------- From: Raul Rockwell <rockwell@socrates.umd.edu> ------------------------------------------------------------------------------- Most likely they were omitted for efficiency/simplicity reasons. And, yes, these concepts have been embedded in other functional languages. (J, for instance, has arrays and a restricted sort of overloading, though I feel a bit silly pointing this out.) I was just looking at some of the SML stuff, and I see a "list" construct. I may be confused, but doesn't this allow you to construct arrays? COMMENT: yes it does, but with two major deficiencies. First, I want an array type to restrict the set of legal (well typed) objects to the special kind of arrays I'm really working on (N x N matrices, say) which the (nested) list approach can't do for me. Second, I want an array to be a data structure with o(1) lookup time, which lists aren't neither. ------------------------------------------------------------------------------- From: John Farrell <farrell@cs.uq.oz.au> ------------------------------------------------------------------------------- The reason functional languages don't usually provide arrays is because you can't go around updating them without risking referential transparency unless you're prepared to do some pretty tricky analysis. If you have an array which is say used in an (as yet) unevaluated argument and also changed and passed on somewhere else, you have to either make a copy to update or have some tricky mechanism which shares the array between the two and remembers how they differ. If you copy, you use a lot of memory, but if you do the remembered update stuff, you lose the o(1) lookup time which was the best thing about the array in the first place. It could be the case that the update doesn't affect the use of the array in other places, in which case it is safe to do, but this is rather hard to detect. If you don't want o(1) lookup, you might as well be using a function or looking up some other data structure anyway. Arrays provide very few advantages anyway if you have stuff like lists, arbitrary constructed data types, and memoised functions. Added to the implementation difficulties, why bother? A good paper on this topic is: %T The Aggregate Update Problem in Functional Programming Systems %A Paul Hudak %A Adrienne Bloss %B 12th ACM Symposium on Principles of Programming Languages %D January 1985 ------------------------------------------------------------------------------- From: Stefan Kahrs <smk@lfcs.edinburgh.ac.uk> ------------------------------------------------------------------------------- I don't know about the reasons for the decisions to disallow overloading by the user in SML, but you also asked for languages containing overloading/subtyping etc. One language that allows polymorphism as well as overloading is ET. ET is a higher order relational language. It allows functional programming as well as logic programming, just by the observation that functions are a special case of relations and relations can be seen as predicates. There are two important restrictions for the use of overloading and polymorphism in ET: (i) The type of every top-level relational (I mentioned, ET is higher-order) must be given explicitly by the user. (ii) The type inference has to find unique types for the identifiers at their using occurrences, e.g. if you have a overloaded function '+' then you cannot get another overloaded function add by saying let val add = op + in ... (btw this is NOT ET-syntax) Instead, you can write something like let val add:int*int->int = op + and add:flo*flo->flo = op + in ... So, overloading works similar as in Ada. Another (related) restriction is that you have no corresponding type-expressions for overloading, e.g. you cannot write something like ident : T1 | T2 to express that ident has either type T1 or type T2. ET has no subtyping concept. For more information about ET, please ask the author/implementor of the language: Bernd Gersdorf (bernd@de.uni-bremen.informatik) ------------------------------------------------------------------------------- From: Dave Berry <db@lfcs.edinburgh.ac.uk> ------------------------------------------------------------------------------- Arrays weren't included in the definition of SML because their behaviour can be defined in terms of the existing primitives, excluding considerations of access time. The main implementators of SML have agreed on standard signatures for both arrays and vectors. Both overloading and subtyping were excluded because it wasn't known how to incorporate them into the type system. The overloading of the arithmetic operators on integers and reals already causes enough problems when teaching SML. Both these areas are the subject of current research. Haskell attempts to incorporate overloading, but still has some problems to be ironed out. Incidentally, SML tuples are derived forms of labelled records, and the same syntax can be used to index tuples and records. E.g. #1 ("a", "b") evaluates to "a". ------------------------------------------------------------------------------- From: Joe Fasel <jhf@c3serve.c3.lanl.gov> Organization: Los Alamos National Laboratory ------------------------------------------------------------------------------- Haskell has overloading (via type classes) and (pure functional) arrays. It doesn't have subtypes, but does have subclasses.