world as value

Bjorn Lisper lisper@it.kth.se
Mon, 21 Jun 1999 11:43:23 +0200 (MET DST)


>On 19-Jun-1999, Adrian Hey <ahey@iee.org> wrote:
...
>> I wouldn't say that I think (world as value) i/o in functional languages
>> doesn't work soundly. It can work fine, but not as I would want. The big
>> problem is that a _purely_ functional language must express system output as
>> a (pure) function of system input. This seems to demand that external events
>> are responded to in chronological order. I know that most real systems don't
>> behave that way, nor should they.

Not necessarily. Chronological order of inputs can be modeled by sequences
if inputs in a pure functional setting, and the output does not necessarily
have to be a sequence where the elements are directly related to the
corresponding elements in the input sequence. Think of sorting, for
instance.

>> Real systems can respond to events 'out of order'. This is often called
>> non-determinism.

Non-determinism rather means that the output cannot be expressed as a
function of the input in the semantical model provided by the language. That
is, given the same (visible) inputs at different runs, the output may be
different. In a purely functional model they must be the same.

Yet I think I understand your reasoning, and there is a grain of truth to
it. I guess it can be exemplified by the classical nondeterministic merge
operator, which merges two input sequences into a single output
sequence. The nondeterministic version of this operator allows the output to
be any sequence where each element in any input sequence occurs exactly
once, and where the relative order between elements in the respective input
sequences is preserved. Given only the "local" ordering information for each
sequence, it is impossible to specify the merge operator in a purely
functional fashion without imposing restrictions on the ordering of outputs
that may force an unboundedly long wait for elements to arrive in one
sequence while unboundedly many elements are queued at the other input.

However, if the inputs are labeled with a time, then we can easily define a
purely functional merge which outputs elements in the exact time order in
which they arrive (ties must be broken, of course). The time stamps then
provide the global ordering information, missing in the pure sequence model,
that makes it possible to specify a purely functional merge.

Fergus Henderson:
>It is quite possible to model non-determinism in a purely functional
>framework. See for example the following references.
>
>     *  F. Warren Burton, ``Nondeterminism with Referential
>        Transparency in Functional Programming Languages,'' in Computer
>        Journal, 31(3), 1988, pp. 243-7.
>
>     *  John Hughes, John O'Donnell, ``Expressing and Reasoning About
>        Non-deterministic Functional Programs,'' in Proc. of the 1989
>        Glasgow Workshop on Functional Prog., pp. 308-28.

One must be careful not to mix up referential transparency and purely
functional frameworks. Yes, one can model nondeterminism in a purely
functional framework by "oracles" magically providing the missing
information (the time stamps in the merge example above is a simple example
of this). But referential transparency rather refers to the ability to
perform equational transformations of definitions (replacing "equals" with
"equals") without changing the semantics of the term being transformed.
There are purely functional languages which are not referentially
transparent (call-by-value-languages, for instance), and it is also possible
to have non-functional languages where some form of referential transparency
is retained. I once wrote a paper on the topic, see reference below.

Fergus Henderson:
>In Clean, Haskell, and Mercury, the imperative-style parts are written using
>syntax that has a very simple mapping to code using only pure functions
>(or predicates) which have a relatively simple and clear declarative
>(denotational) semantics.
>For the imperative-style parts of the program, you can reason about them
>using the operational semantics, but because they also have a declarative
>semantics, it's possible to reason about them using the declarative semantics
>too.
>
>This contrasts to the situation where the imperative-style parts of the
>program are written using syntax that does not have a simple declarative
>semantics, as would be the case if you wrote the imperative-style parts
>of the program in C, for example.

Hmm, what do you mean by "not having a simple declarative semantics"? That
one must resort to powerdomains?  Surely C programs can, at least in
principle, be given a denotational semantics as functions from states x
inputs to states x outputs (if we disregard the fact the ANSI C standard
apparently does not impose a fixed evaluation order on expressions, which
means that different ANSI-compliant compilers could generate code that
yields different results). Imperative does not imply nondeterministic (in
the sense of not having a denotational semantics), and C is, as far as I can
see, not a nondeterministic language.  But the semantics must deal with
states which are quite low-level due to the pointer-arithmetic, absence of
type- and array bounds checking, etc., so it can of course be argued whether
the resulting semantics will be "simple". Is this what you referred to?

Björn Lisper


@ARTICLE{Lisper-CAAP-TCS,
	AUTHOR = {Bj{\"o}rn Lisper},
	TITLE = {Computing in Unpredictable Environments: Semantics, Reduction Strategies, and Program Transformations},
	JOURNAL = tcs,
	YEAR = {1998},
	VOLUME = {190},
	NUMBER = {1},
	PAGES = {61--85},
	MONTH = jan,
	NOTE = {Preliminary version appeared in CAAP'96}
}

@STRING{tcs = "Theoret.\ Comput.\ Sci."}