alan@rnms1.paradyne.com (Alan Lovejoy) (04/21/89)
vax.bbn.com (Mike Thome) writes: rnms1.paradyne.com (Alan Lovejoy) writes: >>-- Portability -- >>1) Language portability is a function of how similar the compilers for different >>systems are and the breadth and depth of STANDARD functions that are provided >>via STANDARD interfaces. This is largely an extra-linguistic issue that >>has more to do with the history and culture of different language communities >>than it has to do with the technical merits of languages as languages. >>Smalltalk is the winner here, with C++ a strong runner-up. >I'm not sure I see how this is *at all* a linguistic issue - it sounds >as thought you are talking more of programming environment and fidelity >of implementations than anything else. Frankly, I'm surprised that C++ >is listed in the same sentence as Smalltalk in this regard - Smalltalk is >an entire integrated environment implemented in itself... the only other >similar systems that come close are Lisp Machines (from various vendors) >running Flavors - perhaps some of the pascal P-machines might be grouped >in the same way. 1) How is portability a linguistic issue? Languages that lack certain amenities that users find irresistable tend to sprout nonstandard extensions in each implementation. FORTRAN and Pascal are famous examples. Then there are those languages whose programmer interface is too "physical" or perhaps "low level" (which is not necessarily the same thing!), such that it assumes too much about the architecture of a particular system. Assembly languages are good examples, although even "high-level" languages may exhibit this problem. It is often masked by the architectural similarities of modern general purpose systems, however (e.g., byte, halfword, fullword bit sizes; binary encoding; data type-machine instruction binding). 2) Why does C++ deserve mention alongside ST-80 in regards to portability? C++ inherits :-) a large supply of STANDARD fuctions and STANDARD interfaces from C. To a large extent, C's supply of standard functions arises out of its association with the UNIX operating system. While comparing UNIX and the ST-80 image is not completely kosher, it cannot be denied that both UNIX and the ST-80 image represent a LOT of code and a LOT of functionality. And that none of the other languages mentioned have anything like it to within an order of mangnitude. >>-- Object Orientation -- >>The definition of "object oriented language" is open to debate. Instead of >>debating the minimum set of attributes that an object-oriented language >>should have, it is more instructive to consider the ideal case. >> First, some definitions: A class is a set of values and the functions/relations >>defined on the members of that set. An object is an instance of a class which >>represents one of the values in the set, that is, one of values of the class. >> Inheritance is the ability to define a new class in terms of its differences >>(extensions, deletions, changes) from some other pre-existing class. >CLOS Generalizes that to "... from some other pre-existing (required for >instance instantiation) class or classes". > >>The ideal object-oriented language would: >>1) Have user-definable classes. >CLOS satisfies this requirement - methods may be specified not only on >defined classes, but also built-in data types (ie. integers vs. floats vs. >complex vs. ratios ... etc) and even single values. > >>2) Have class inheritance. >CLOS has this. In addition, it allows inheritance from multiple >(possibly disjoint) classes. > >>3) Allow function/operator overloading. >CLOS has this. Any function may be specialized on any one or more of >its required arguments. (there is no difference between operator and >function in lisp. Note that macros and special forms may not be >specialized). > >>4) Be completely polymorphic. >>Smalltalk and Lisp are highly polymorphic. Next is Objective-C and Prolog. >>Then C++, and last is Modula-2. >I would like to see the definition of "polymorphic" (for my own >education). You (and several other people, in email) asked for it! So here it is, along with three references: 1. "Polymorphic Programming Languages -- Design and Implementation" -- 1984 David M. Harland, B.Sc., M.Sc., Ph.D., University Of Glasgow Halsted Press: a division of John Wiley & Sons -- MUST READING -- 2. "Denotational Semantics -- A Methodology For Language Development" -- 1986 David A. Schmidt, Kansas State University Allyn and Bacon, Inc. 3. "Abstraction Mechanisms And Language Design" -- 1981 an ACM Distinguished Dissertation (1982) by Dr. Paul N. Hilfinger, CMU The MIT Press -- Definition Of Polymorphism -- Full polymorphism means that any component or aspect of a program, program component or programming language must behave as a value. Any and all values must be subject to inspection, modification, storage in memory, usage as a component part of some composite value, usage as a paremeter, usage as an operand in an expression, being computed as the result of evaluating an expression or function, and (re)definition of its form, structure, content or name. The protocol for invoking these common operations must be the same for all values, regardless of type. To say the same thing more concretely: numbers, characters, data types, procedures, variables, addresses, blocks, execution contexts, name bindings, scopes, processes and the number of bits in an integer must all be "first class objects." First class objects all share the same set of fundamental rights, priviliges and abilities, the protocol for the exercise of which is the same for all objects. A first class object has a value that can be inspected, changed or stored in memory. There are functions and/or relations that have been and/or can be defined for any first class object. A first class object can have its structure defined or redefined. It can be bound to a name, and its name can be changed. -- Definition of Abstraction -- Abstraction is the process of discovering and/or expressing what is INVARIANT, constant and organic in a system by taking out, leaving out or not mentioning that which is changing, temporary or accidental. -- Programming Language Abstraction Mechanisms -- User definable procedures, functions and data types are the most important (and most common) abstraction mechanisms found in modern programming languges. Generally, the abstraction mechanisms in a programming language permit one to construct GENERAL PURPOSE structures, devices or tools that are DEFINED ONCE BUT USED MANY TIMES in different contexts. Let us refer to such entities in a program as "object abstractions". Object abstractions serve as TEMPLATES from which multiple but partially identical program objects can be created. Each such "created object" in a program (or set of programs), as a separate INSTANCE of the same object abstraction, will have all the same properties, attributes, functions and structures defined for that object abstraction. The idea is to build an abstracted MASTER OBJECT, an ORIGNAL MOLD from which multiple actual instances can be generated like cookies from a cookie cutter. Ideally, the programmer will design his object abstractions in such a way that they can even be reused in totally unrelated programs or systems. By using instantiation of object abstractions to generate program objects, the workings, interfaces and functionality of the program objects are tied to the object abstraction, so that modifications or fixes need only be done to the object abstraction; the instantiation process insures that modifications are automatically propogated to the generated program objects. Instantiation of object abstractions allows multiple copies of a program object to be created with little extra effort beyond what is required to make just the first copy, saving time. Another type of abstraction mechanism called PARAMETERIZATION is also of critical importance. Parameterization is a mechanism which permits the programmer to define program objects whose full nature, whose complete composition, structure, operation and/or data is NOT DETERMINED UNTIL THE OBJECT IS ACTUALLY INSTANTIATED, OR EVEN UNTIL THE PROGRAM IS EXECUTED! For example, a square is a shape abstraction whose usefulness derives partly from the fact that it says nothing about the SIZE of square shaped objects. The concept or abstraction "square" is INDEPENDENT of size (and of horizontal/vertical orientation, location, material composition, weight, color, velocity...). All actual squares must of course have some actual size, but the ability to form such abstractions DIVORCED of certain details is incredibly useful. It is far better to write a square drawing procedure that will draw a square of any size than to have to write a different square drawing procedure for each desired size of square. Such a size-independent procedure is said to be parameterized: it accepts the size of the square to be drawn as an input "parameter". -- Polymorphism and Abstraction Mechanisms -- Polymorphism involves two invariants: everything behaves as a value, and all values have a common set of abilities and a common protocol for the exercise of those abilities. Abstraction depends upon discovering and exploiting invariants. If everything is a value, then everything can be used by abstraction mechanisms. If the protocol for exercising the fundamental abilities of all values is the same, then the same abstraction mechanisms can be applied to values of any type. What abstractions can be created by abstraction mechanisms depends upon what can be a value. The generality of the abstractions depends upon both what can be a value and the commonness of the protocol for accessing common attributes and/or behaviors of values. For example, the usefulness of the list abstraction depends upon what can be a member of the list (what can be a value), and upon the orthogonality of the protocol for manipulating values: each different protocol for loading/storing values from/to memory (e.g., "list.element := element" versus "list.element := element^") requires a different version of the abstraction. Consider the following function definition: function sum(a); begin s := 0; for i := 1 to size(a) do s := s + a(i); end; return s; end sum; The usefulness of this function depends upon what values can be input to it as parameters, upon what value types functions can return, upon what value types have the ":=", "+" and "()" operations defined on them and upon what value types have the "size()" function defined for them. In a language where the function invocation and array indexing operators are both "()", then the parameter to this function might be either an array or a function. In Pascal or Modula-2, the parameter would have to be function only, because the array indexing operator is "[]." The point is that polymorphism enhances the power of abstraction mechanisms. Lack of polymorphism cripples abstraction. -- Alan Lovejoy; alan@pdn; 813-530-2211; AT&T Paradyne: 8550 Ulmerton, Largo, FL. Disclaimer: I do not speak for AT&T Paradyne. They do not speak for me. _________________________Design Flaws Travel In Herds_________________________ Motto: If nanomachines will be able to reconstruct you, YOU AREN'T DEAD YET.
nick@lfcs.ed.ac.uk (Nick Rothwell) (04/21/89)
I've cut down the Followup distribution of this, to stop it going out to the entire universe; I think that general discussions of language issues belong in comp.lang.misc...? In article <5957@pdn.paradyne.com> alan@rnms1.paradyne.com (Alan Lovejoy) writes: >1. "Polymorphic Programming Languages -- Design and Implementation" -- 1984 > David M. Harland, B.Sc., M.Sc., Ph.D., University Of Glasgow > Halsted Press: a division of John Wiley & Sons > -- MUST READING -- > The mathematical basis for polymorphic type systems comes from Robinson's article on unification in the JACM, from around '67 (sorry, can't remember the title). From here, there's Milner's work, the LCF system, and of course (fanfare:) ML. >-- Definition Of Polymorphism -- > >Full polymorphism means that any component or aspect of a program, program >component or programming language must behave as a value. Any and all >values must be subject to inspection, modification, storage in memory, >usage as a component part of some composite value, usage as a paremeter, >usage as an operand in an expression, being computed as the result of >evaluating an expression or function, and (re)definition of its form, structure, >content or name. The protocol for invoking these common operations must be >the same for all values, regardless of type. People might disagree about the extent of "full" polymorphism. ML is certainly polymorphic, although you can't "inspect" all values (they may be abstract, or function objects). "modification" is only allowed on objects created specially for the purpose: how do you modify a function? "Storage in memory" - doesn't make sense for higher-order garbage collected languages. "(re)definition of its form" I don't understand... >To say the same thing more concretely: numbers, characters, data types, >procedures, variables, addresses, blocks, execution contexts, name bindings, >scopes, processes and the number of bits in an integer must all be "first >class objects." ...although a lot of these things (addresses? blocks?) don't exist in some languages. And I don't see that you want to allow the user to alter absolutely everything ("hey, let's change the number of bits in a word from being 32 to being yellow..."). I presume that this is David Harland's definition of polymorphism...? His approach is to provide this rich model, where everything goes, with sophisticated hardware support. But, this is a specific approach, and shouldn't be taken to imply that polymorphism encapsulates everything in this approach. >-- Definition of Abstraction -- > >Abstraction is the process of discovering and/or expressing what is INVARIANT, >constant and organic in a system by taking out, leaving out or not mentioning >that which is changing, temporary or accidental. Isn't that a rather strange way of putting it? I view abstraction as a process of distinguishing a system's interface from its implementation. >The point is that polymorphism enhances the power of abstraction mechanisms. >Lack of polymorphism cripples abstraction. Absolutely. In conventional languages, you have to be concerned with the form data structures take (is it a record? an address of a record? do I have to garbage collect it? etc. etc.). Polymorphism does away with this, but the price you pay is that polymorphism requires support (garbage collected store, special hardware, etc. etc.). A price I'm quite willing to pay, actually... Now, where's that ML session...? >Alan Lovejoy; alan@pdn; 813-530-2211; AT&T Paradyne: 8550 Ulmerton, Largo, FL. Nick. -- Nick Rothwell, Laboratory for Foundations of Computer Science, Edinburgh. nick@lfcs.ed.ac.uk <Atlantic Ocean>!mcvax!ukc!lfcs!nick ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ...while the builders of the cages sleep with bullets, bars and stone, they do not see your road to freedom that you build with flesh and bone.
jack@cs.glasgow.ac.uk (Jack Campin) (04/22/89)
alan@rnms1.paradyne.com (Alan Lovejoy) wrote: >>> [the ideal programming language should] Be completely polymorphic. >>I would like to see the definition of "polymorphic" (for my own education). > You (and several other people, in email) asked for it! So here it is, > along with three references: > 1. "Polymorphic Programming Languages -- Design and Implementation" -- 1984 > David M. Harland, B.Sc., M.Sc., Ph.D., University Of Glasgow > Halsted Press: a division of John Wiley & Sons > Full polymorphism means that any component or aspect of a program, program > component or programming language must behave as a value. Any and all > values must be subject to inspection, modification, storage in memory, > usage as a component part of some composite value, usage as a paremeter, > usage as an operand in an expression, being computed as the result of > evaluating an expression or function, and (re)definition of its form, > structure, content or name. The protocol for invoking these common > operations must be the same for all values, regardless of type. > To say the same thing more concretely: numbers, characters, data types, > procedures, variables, addresses, blocks, execution contexts, name bindings, > scopes, processes and the number of bits in an integer must all be "first > class objects." You and Harland may mean that by "polymorphic", but the rest of the world certainly doesn't. The mathematically understood senses of polymorphism are (1) the Hindley type system, as implemented in Milner's ML and most functional languages since, and (2) Girard's more powerful type system F, reinvented by Reynolds and not fully implemented in any language I can think of (Fairbairn's Ponder comes closest; Mitchell and Plotkin's SOL and Barendregt's TALE do it on paper). There are umpteen mix-and-match combinations of these with other ideas. It may be possible to construct a logical system combining the above notion of dependent type with polymorphism; but nobody has ANY real idea how to typecheck programs written in such calculi - a few flaky attempts to implement some of Martin-Lof's type theories are the nearest anyone's got. Nobody has the *faintest* idea how to coherently describe type systems in which types are assignable values, as you ask for above. Putting all three of these requirements (Milner or Girard polymorphism, dependent types, assignable types) together in one formal calculus is presently quite unimaginable, still less implementing the result in a type-safe programming language. For another cautionary example, look at Cardelli's attempts to meet a few of the same criteria in recent years: the result being a series of inconsistent type systems attempting to provide a type of all types and an algorithm for typechecking dependent types that nobody has any idea how to prove complete (or refute, for that matter). Or look at Burstall and Lampson's Pebble (dependent types and first-class bindings), still unimplemented ten years or so after its design. This does not suggest we can expect any quick answers. Yes, you might be able to hack together a language that provided all those motherhood features (though as far as I know Harland's team at Linn haven't managed to implement any significant fragment of Poly in the five years since that book came out). But you wouldn't have a hope of reasoning about programs written in it, and the appropriate formalism for verifying the compiler would be chicken sacrifices and moving your mouse in pentagrams over the source code. [ for references to this stuff, browse through a few recent LNCS's on data types and the like ] Despite this, the machine (REKURSIV/OBJEKT) that Harland designed to implement these ideas seems to be a fast engine for running object-oriented code on. -- Jack Campin * Computing Science Department, Glasgow University, 17 Lilybank Gardens, Glasgow G12 8QQ, SCOTLAND. 041 339 8855 x6045 wk 041 556 1878 ho INTERNET: jack%cs.glasgow.ac.uk@nss.cs.ucl.ac.uk USENET: jack@glasgow.uucp JANET: jack@uk.ac.glasgow.cs PLINGnet: ...mcvax!ukc!cs.glasgow.ac.uk!jack
norvell@csri.toronto.edu (Theodore Stevens Norvell) (04/23/89)
In article <2841@crete.cs.glasgow.ac.uk> jack@cs.glasgow.ac.uk (Jack Campin) makes some good points, but wrote: > >alan@rnms1.paradyne.com (Alan Lovejoy) wrote: >> To say the same thing more concretely: numbers, characters, data types, >> procedures, variables, addresses, blocks, execution contexts, name bindings, >> scopes, processes and the number of bits in an integer must all be "first >> class objects." > >You and Harland may mean that by "polymorphic", but the rest of the world >certainly doesn't. The mathematically understood senses of polymorphism are >(1) the Hindley type system, as implemented in Milner's ML and most functional >languages since, and (2) Girard's more powerful type system F, reinvented by >Reynolds and not fully implemented in any language I can think of [...] > Perhaps this is a quibble, but surely you are confusing "polymorphism" with "polymorphic type inference". Consider the following quotation describing polymorphic programming: A widely employed style of programming, particularly in structure- processing languages which impose no discipline of types (LISP is a perfect example), entails defining procedures which work well on objects of a wide variety (e.g, on lists of atoms, integers, or lists). Surely Harland's Poly is another perfect example. In Poly can one not define procedures which work well on objects of a very wide variety? The quotation, by the way, is from Milner's seminal paper `A Theory of Type Polymorphism in Programming', (J. Comp. & Sys. Sci., 17, 1978) in which he used Hindley's system (without knowing it was Hindley's) to do strong type checking in a lisp-like language (ML). The introduction of this approach did not suddenly make LISP, Prolog, or Smalltalk (or Poly, had it existed at the time) less polymorphic. Nor did it make languages that use other approaches to strong type checking of polymorphic programs (e.g., C++ and Modula-3) less polymorphic. Milner also credits the term "polymorphism" to Strachey in 1967 which predates even Hindley's work (1969). The term "polymorphic type inference", on the other hand describes perfectly the work of Hindley, Milner, Girard, Reynolds, McCracken, Cardelli, Wand, etc. Theo Norvell U of Toronto On the other hand, language is living. Perhaps I'm just out of date.