Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!mcvax!ukc!etive!lfcs!db
From: db@lfcs.ed.ac.uk (Dave Berry)
Newsgroups: comp.lang.misc
Subject: Re: Polymorphism
Message-ID: <1941@etive.ed.ac.uk>
Date: 5 May 89 18:52:57 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>
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: 50

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?

>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?

>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?

>What one language does in the interpreter another does in user defined code.

So?  I don't understand the relevance of this.

>It is possible to write a program that includes its own interpreter.

But does this define the semantics of the language?  For example, I've seen
Lisp interpreters written in Lisp that don't specify the order of evaluation.
This knowledge has to be added from outside.

Again, I don't see the relevance of this.


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.

		"You never smile, you know it wouldn't look right.	
 		 'Cause your dentures glow in ultra-violet light..." 
Dave Berry, Laboratory for Foundations      db%lfcs.ed.ac.uk@nsfnet-relay.ac.uk
    of Computer Science, Edinburgh Uni.	    <Atlantic Ocean>!mcvax!ukc!lfcs!db