dorai@titan.rice.edu (Dorai Sitaram) (11/21/89)
In article <11632@phoenix.Princeton.EDU> markv@phoenix.Princeton.EDU (Mark T Vandewettering) writes: > Imagine all applications have not just and operator and an >operand, but also a continuation. The result of application is the >result of applying the continuation to the result of applying the >operator to the operand. This is the basic notion of a continuation >passing language. > >What particular feature of this is non-functional? The flow of control >is a bit more convoluted, and analysis of such programs may be more >difficult, but I fail to see any reason to toss out such constructs. >Continuations are no more complicated or unfunctional that higher order >functions. Agreed. _If_ you pass around an explicit continuation argument to your functions. While this requires you to write your entire program in continuation-passing style, the language itself never strays beyond its functional limits. However, assignment allows a similar explanation too: passing around an explicit store argument, the language once again remaining impeccably functional. Comparing explicit continuations with non-explicit stores is a bit apple/orangish. I was thinking more in terms of having continuations being available 1st-class in the language thru operators like Scheme's call/cc. Call/cc is as bad (or as good) as assignment when it comes to destroying functional behavior. It breaks the same rules that you chalk up against assignment below, viz., context independence (of course! Continuations are abstracted contexts!) "referential transpacrency," and simplicity of substitution semantics. >I have been informal in my description of what I perceive to be as a >functional language. Roughly, I would say that something evaluated >according to a simple substitution style semantics would be functional. >It is my belief that continuations can be well understood in this >framework. I would like to hear examples or counterexamples of course. I'll be informal too. Any substitution-style semantics for a call/cc-enhanced functional language is going to have a rule for call/cc-application that captures its surrounding context, and another for continuation-invocation that flips contexts. Starting from there, you should be able to break every functional rule that assignment does [1]. This is not to imply that assignment and call/cc are equivalent. They are very^2 different: they're merely equally powerful in pulling down functional behavior. This is not surprising news, insofar as call/cc is concerned, for it can produce _all_ the celebrated rat's nests of goto, and then some. Don't underestimate it. :-] --dorai [1] A Syntactic Theory of Sequential Control. [Theor. Comp. Sci. 87] ,, State. [POPL 87] ,, Control and State. [?] The authors of the above [related] papers are some combination of Friedman, Felleisen, Duba, Hieb and Kohlbecker. "Control" and "state" correspond to "continuations" and "assignment" respectively. -- ------------------------------------------------------------------------------- It may be that the gulfs will wash us down; It may be we shall touch the Happy Isles. -------------------------------------------------------------------------------