Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!zaphod.mps.ohio-state.edu!usc!ucsd!ucbvax!bloom-beacon!ALTDORF.AI.MIT.EDU!lyn
From: lyn@ALTDORF.AI.MIT.EDU (Franklyn Turbak)
Newsgroups: comp.lang.scheme
Subject: Functionality and implicit arg's (call/cc & referential transparency)
Message-ID: <9008300855.aa05660@mc.lcs.mit.edu>
Date: 30 Aug 90 12:55:53 GMT
References: <1543@anaxagoras.ils.nwu.edu>
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 39


In article <1543@anaxagoras.ils.nwu.edu>, Bruce Krulwich writes:

>  To conclude, CALL/CC only hurts "pure functionality" (ie, referential
>  transparency) because a portion of the information in a procedure call is
>  left implicit in Scheme.  When this is made explicit, as by CPS conversion
>  or by programmers using explicit continuations, the problems go away.

You could make the same claim about SET! and the store.  That is, SET!
only hurts "pure functionality" because a portion of the information
in a procedure call (i.e. the store) is left implicit in Scheme.  Just
as with CALL/CC, with SET! it is always possible to regain pure
functionality by passing an extra argument (the store) explicitly to
every procedure.  (In the case of stores it is also necessary to
*return* the store from every procedure call so that it is
single-threaded throughout the computation.)

The key point is that any kind of hidden state destroys referential
transparency, and making all state explicit restores referential
transparency.  This point is especially clear in the denotational
definitions of programming languages.  That is, if we want to model
the meanings of programs with mathematical functions (which of
necessity are "pure"), we are required to make all state explicit.
This is why the valuation functions for programming languages like
Scheme (see the script-E function in the Formal Semantics section of
R^3RS) typically have a signature that looks something like:

      Expression x Environment x Continuation x Store -> Ans

(Usually this is presented in a curried form, but let's ignore that
here.) Thus, an expression only has meaning with respect to three
other pieces of state: the environment, the continuation, and the
store.  The environment associated with an expression is statically
apparent from the lexical structure of the program, and so we
generally do not consider it a piece of "hidden state".  But the
continuation and store model dynamic behavior; leaving these implicit
is what destroys referential transparency.

- Lyn -