Path: utzoo!attcan!uunet!mcvax!ukc!etive!lfcs!db From: db@lfcs.ed.ac.uk (Dave Berry) Newsgroups: comp.lang.misc Subject: Re: Polymorphism Message-ID: <2075@etive.ed.ac.uk> Date: 18 May 89 19:54:56 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> <6090@pdn.paradyne.com> Sender: news@etive.ed.ac.uk Reply-To: db@lfcs.ed.ac.uk (Dave Berry) Organization: Laboratory for the Foundations of Computer Science, Edinburgh U Lines: 67 In article <6090@pdn.paradyne.com> alan@oz.paradyne.com (Alan Lovejoy) writes: >In article <1941@etive.ed.ac.uk> db@lfcs.ed.ac.uk (Dave Berry) writes: >You cannot rightfully divorce "interpreter activity" from "program activity." >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 >interpretation process or part of the program execution process. I don't see how this is relevant to the discussion of the semantics of a language, as opposed to a function written in that language. Yes, if you use denotational semantics as your formal model you can describe each construct of the language by a function, but that function is then a function of the underlying formal system, not of the language being described. >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. Which would be implementing a different language. The null language would not provide assignment or recursion or any other approach. In fact you couldn't write an interpreter or compiler using it at all. >Different implementions of different languages make different decisions >about what functions exist, and at what time they are evaluated. For example, some have assignment, and some don't. >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*. Again, this seems to be arguing that you can implement a function in several different languages. This doesn't show that the languages are the same, or that they should be considered to be the same (except in the rather boring aspect of equal expressive power). The difference between physics primitives and programming language primitives is that programming languages are hierarchic; if you implement a language L' in terms of an existing language L you are not extending L, you are using it as an implementation tool. >>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. This seems more like an argument for my side, in that a comparison of two languages should include the differences between them as well as a statement of their expressive power (i.e. that they can all be modelled by a universal Turing machine). >This (functional languages must be implemented using Turing machines) is one of >of those things that cannot be proven--only disproven. Any model capable of implementing functional languages must be as powerful as a Turing machine, but it need not necessarily be a Turing machine. Dave Berry, Laboratory for Foundations db%lfcs.ed.ac.uk@nsfnet-relay.ac.uk of Computer Science, Edinburgh Uni. !mcvax!ukc!lfcs!db "It's a cute castle, but why did they build it right next to the railway?"