Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!zaphod.mps.ohio-state.edu!swrinde!ucsd!ucbvax!bloom-beacon!MOJAVE.STANFORD.EDU!daniel
From: daniel@MOJAVE.STANFORD.EDU (Daniel Weise)
Newsgroups: comp.lang.scheme
Subject: Functionality and implicit arg's (call/cc & referential transparency)
Message-ID: <9008301605.AA04344@mojave.Stanford.EDU>
Date: 30 Aug 90 16:05:33 GMT
References: <1543@anaxagoras.ils.nwu.edu>
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 46


   OK, what's the point, you ask?  Simple, I answer.  The only difference
   between code that does what I've described and code that uses CALL/CC (with
   multiple procedure reentries) is that in my code above the continuations
   (and their associated contexts) are explicit while in code using CALL/CC
   they're implicit.  

This is not true.  CALL/CC gives you access to a continuation you can
never construct yourself: the top-level one that your program is
invoked with.  It's this continuation that causes problems because it
is not a function, it does not return a value.  The other continuations
ones you explicitly construct with lambda are functions.

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

EVALUATION ORDER is the hidden state that causes problems, not
continuations per se.  CPS conversion does two things: it fixes the
evaluation order and it introduces continuations.  Steele's thesis
confused these two tasks and they have been confused ever since.  It
is making the evaluation order explicit that makes continuations
gotten by call/cc become referentially transparent.  

Think of it this way: the semantics of Scheme are non-deterministic,
they specify a set of possible evaluation orders.  An interpreter
merely has to pick one of them to be correct.  Call/cc exposes the
evaluation order chosen by the interpreter, and is therefore
referentially opaque because its use exposes hidden varying state.
CPS conversion does the choosing instead of having the interpreter
doing the choosing.  (That CPS conversion also happens to make
continuations explicit is irrelevant to this argument.)  Since there
is now only one evaluation order, there is no hidden state for call/cc
to expose, and its use becomes transparent.

Note that this argument applies to eager languages where one can
specify the order of evaluation using application.  For a lazy language,
where order of evaluation is not controllable, call/cc, which gives
access to the initial continuation, is not a functional construct.

Daniel