world as value

[Fergus Henderson]

On 25-Jun-1999, Adrian Hey <ahey@iee.org> wrote:
> 
> On Wed 23 Jun, Fergus Henderson wrote: 
> > >  First question   - What time should the computer output?
> > >  Answer           - The time of the "me ask computer" event I.E. 2:00 pm
> > >  Second quesition - When does it do this?
> > >  Answer           - When the FPGA has been placed and routed, lets say 4:15
> > > 
> > > I think most people would regard this as "intolerable behaviour". What it
> > > should do is suspend the placing and routing of the FPGA to for moment, in
> > > order to respond, telling me the time is 2:00 pm at 2:00 pm, or very shortly
> > > thereafter. But it simply can't do this if it's running a program expressed > > as a function mapping input events to output events. This would be
> > > non-deterministic.
> > 
> > You can express this as a function mapping input events to output events.
> 
> Whoa there! Now it's you who's cheating. You can implement the program by
> invoking non-deterministic pseudo functions (I.E. Haskell IO Monad or Clean
> *World). I don't think that's the same as expressing it. As far as languages
> which are supposed to be "purely functional" are concerned, I think these are
> a hack. A necessary hack perhaps, but still a hack.

These functions have a deterministic denotational semantics.
They are in that sense real functions, not pseudo functions.

The program's _behaviour_ is nondeterministic.  This is because the
program's behaviour depends not only on the deterministic function,
but also on the inputs to that function, some of which are unspecified
(i.e. nondeterministic).

> > But you can express forkIO in Haskell too, using the techniques
> > described in the papers I previously cited to handle the required
> > nondeterminism.
> 
> Have you told Simon this?
> 
> I've had a quick look at your program, you say forkIO is the problem, I'll
> take your word for that. I have a much harder time understanding how
> merge_requests is ever going to work reliably in a causal system (as any real
> system must be).
>
> Is this a model program which can only run in causality violating pseudo time,
> or a real program?

The code I gave for forkIO is only a model; a real implementation would
do things using different techniques.  Nevertheless, a real implementation
could implement the same semantics -- assuming the implementation is
allowed to choose appropriate values for the unspecified inputs.

For functional programmers, it may seem strange for the implementation of a
function to compute not just its return value but also some its arguments.
However, those familiar with logic programming will see this as perfectly
natural -- given an equation `z = f(x, y)', it makes just as much sense for
a system to find a value of `z' and `y' such that this equation holds
for a given value of `x' as it does to find a value of `z' given `x' and `y'.
This is not "cheating".  And it doesn't need to involve any violations
of causality!

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.