Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!ames!lll-winken!uunet!pdn!oz!alan From: alan@oz.nm.paradyne.com (Alan Lovejoy) Newsgroups: comp.lang.misc Subject: Re: Polymorphism Message-ID: <6090@pdn.paradyne.com> Date: 10 May 89 18:32:16 GMT References: <5957@pdn.paradyne.com< <1810@etive.ed.ac.uk< <5973@pdn.paradyne.com< <1834@etive.ed.ac.uk< <6000@pdn.paradyne.com> <1859@etive.ed.ac.uk> <6032@pdn.paradyne.com> <1899@etive.ed.ac.uk> <6063@pdn.paradyne.com> <1941@etive.ed.ac.uk> Sender: news@pdn.paradyne.com Reply-To: alan@oz.paradyne.com (Alan Lovejoy) Organization: AT&T Paradyne, Largo, Florida Lines: 121 In article <1941@etive.ed.ac.uk> db@lfcs.ed.ac.uk (Dave Berry) writes: >In article <6063@pdn.paradyne.com> alan@oz.paradyne.com (Alan Lovejoy) writes: >>I assert that functional languages are Turing Machine equivalent. >>Turing machines maintain state. >>The fact that two "different" implementations of a function are possible >>says something about the relationship between those two implementations. >>The implication is that at some deeper level of abstraction, the distinction >>is meaningless. >Are you saying that a functional language can be viewed as updating something >somewhere because this is one possible model for how it could be implemented >and the user need not know exactly how it is implemented in any particular >instance? Not quite. Turing machines are the ONLY possible model I know of for how a functional language could be implemented--other than in a biobrain. Are nuerons Turing machines? This (functional languages must be implemented using Turing machines) is one of those things that cannot be proven--only disproven. Science is like that, though. I'm awaiting the disproof... >>The semantics of a language IS ULTIMATELY DEFINED BY the output of the >>canonical interpreter of the language. Defining virtual machines on >>paper makes it easy to forget all the work being done in the brain of >>the person "interpreting" the program as specified by the paper definition. >Not all semantic formalisms use the concept of a virtual machine. Are you >using an argument similar to the one above, that because they probably could >be interpreted mechanically one may view them as defining a virtual machine? "Virtual machine" was not the best term. "Axiomatic system" would have been better. I am making an analogy between axioms and virtual machine primitives. This is a stronger statement than simply noticing that axiomatic systems might be implemented via [virtual] machines. The difference between an axiom and a machine operation is that axioms are STATEMENTS of what is BELEIVED to be true, but machine operations are COMMANDS that MAKE something true. Axioms DEFINE truth, machine operations ESTABLISH it. Axioms are used to construct proofs of theorems. Machine operations are used to implement functions. A function to sum the value of the numbers in a list is analogous to the theorem that the result of evaluating the function is the sum of the members of the list. The machine operations of which the function is composed are analogous to the proof. >>You cannot rightfully divorce "interpreter activity" from "program activity." >This is what you are trying to show (I think). How does it follow from the >above? It doesn't. It follows from the below: >>What one language does in the interpreter another does in user defined code. >So? I don't understand the relevance of this. The point is that there is nothing inherent in the SEMANTICS of a function that dictates whether its evaluation is necessarily part of the language interpretaion process or part of the program execution process. Not only that, there is nothing inherent in the semantics of a function that dictates whether or not the function should be built-in to the language or left to the programmer as an exercise. In other words, different languages can choose completely disjoint sets of "built-in" or "primitive" functions. A language that left EVERYTHING to the programmer as an exercise would be the null language which ("permits" | "requires") the programmer to write his own interpreter/compiler and define his own syntax. Different implemenations of different languages make different decisions about what functions exist, and at what time they are evaluated. So these are arbitrary decisions that say nothing fundamental about programming languages in general. The question is not, "When (i.e., compile-time, run-time, etc.) is the function evaluated?" but "Is the function evaluated at all?" In Western culture, we conceptualize certain physical dimensions (mass, length, time, electric current, angle...) as *primitive* dimensions. All other physical dimensions (velocity, energy, electric charge, action, momentum, power, etc.) we conceptualize as derived dimensions which we define in terms of the primitive dimensions. Thus velocity is defined as length divided by time. This may come as a surprise to some people, but the decision as to which dimensions are primitive and which ones are derived is completely arbitrary. If we accept the traditional set of primitive dimensions, then the energy dimension is mass X length^2 / time^2. Choosing another set of primitive dimensions, say mass (electron's rest mass), velociy (speed of light), charge (eletron's charge), action (Planck's constant), entropy (Boltzmann's constant) and angle (1 radian) the formula for energy becomes mass X velocity^2. Or as Einstein wrote it: E=mc^2 (where "c" is the velocity of light). The length dimension would then be action/(mass X velocity), and time would be action/(mass X velocity^2) (or action/energy). There are two criteria for preferring one set of primitive dimensions over another: the average complexity of the formulae for the derived dimensions that result from choosing some set of primitive dimensions, and whether a dimension has some easily-measured physical constant (such as the speed of light in the case of velocity). But these are practical considerations, not "scientific" ones. What's the point? I assert that the choice of "primitives" to be provided by a programming language is like the choice of primitive dimensions: completely arbitrary. You can change the expression of the definition of a dimension and/or a data type by choosing a different set of primitives, but you haven't changed what it actually *IS*. >It seems to me that I could use your argument to show that the archetypal >toy imperative language used in semantics textbooks doesn't have the idea >of state, because I can implement it in the lambda calculus. The true nature of a thing is best comprehended as the UNION of its possible definitions, not the INTERSECTION. 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.