Losing your continuations on the thin borderline between procedurality and functionality
Alaric B. Williams
Hello everyone...
I'm working on a language called ARGOT
(http://www.abwillms.demon.co.uk/os/argot.htm) that's designed to use
the best parts of procedural and functional programming. Basically, as
I see it, functions are the best known way to express transformations
between values, whilst procedures are the best known way to get the
computer to perform lists of instructions.
All programs "start" with a top-level procedural thread of control,
which may perform functional computations when it needs to. For
example, in C, we have lists of procedure calls, but expressions are
basically functional (until we start overloading operators :-(
Looking the the flow of time in the system, mutable bindings are at
risk of mutation during the execution of procedural forms which refer
to them, but not during the execution of functional forms. All
functional forms are implicitly procedural, and can fill positions
where only procedural code is allowed; but the opposite does not
apply, except for the (#unsafe-perform <procedural expression>) form,
which does the obvious thing of "casting" procedural code to
functional code.
The function/procedure call semantics are modified from standard Lispy
fare to keep this seperation explicit. Functions and procedures,
whilst both classing as closures, are not the same thing. They are
create like so:
(#func (<args>) <body>)
or
(#proc (<args>) <body>)
Note that it's completely valid for a function to /return/ a
procedure. Anyway, procedures are performed like so:
(#perform! <procedure> <args>...)
which is a procedural operations (thus the !), whilst functions are
applied like so:
(#apply <function> <args>...)
ARGOT is keen on parallel processing, so special functional constructs
are defined for gaining exclusive access to bindings; it would be
invalid for them to change during a functional evaluation because a
procedural execution in another thread changed them! This area is
still being researched (gulp); my current feeling is that parallel
threads get their own local environments, not shared with other
threads, apart from bindings explicitly defined as shared, which are
then governed by access mechanisms; only a stub is visible in any
environment, which can be read-claimed or write-claimed; either a
single thread has it write-claimed, which means it can read it as well
BTW, or any number of threads have it read-claimed. Write claims have
priority over read claims; if a write claim is pending during a read
cycle, further read requests go on hold until the write claims have
all been serviced.
Anyway, my problem is with continuations. Is a continuation a function
or a procedure???
A continuation that is created by a "call/cc" surrounding a
/functional/ expression can safely be considered as a function as long
as it's scope is limited to the functional expression containing the
call/cc, clearly. The continuation can be a function in this case
since applying it will never escape back up to the invoking procedural
code.
Eg:
(#perform! print! (#apply call/cc some-func))
is valid as long as the continuation never leaves the print!
statement, in which case re-applying it would cause the procedural
print! statement to be re-executed - a breach of the safety system;
and bindings used in some-func could be modified after the print
statement, but if a continuation has escaped some-func, the
application of some-func has not completed; and bindings must not be
changed during a functional operation...
But I'm still a little wooly on the uses of continuations. Are they
really useful in a functional-only context? After all, they are a
"control" operator, which implies procedurality; procedural
continuations aren't so much of a problem, since they can't "escape"
into anything more concrete than procedural code. In the case of
(#unsafe-perform ...), we must be careful in the writing of the
procedural code within to not modify global bindings anyway, so a
continuation escaping "through" a functional area back up to the
calling procedural code (the functional code can't execute it without
using another (#unsafe-perform ...) anyway) is fine.
Hum.
Any ideas?
Another fact that might bear on this is that I intend to actually pass
lists of continuations rather than continuations. call/cc merely takes
the continuation list of the current closure, called #continuation,
and does something like this:
(define (perform/cc! my-cont (what-to-call . args) . cont-args)
(#perform! what-to-call
(cons (list my-cont cont-args) #continuation) . args
)
)
(define (apply/cc! my-cont (what-to-call . args) . cont-args)
(#apply what-to-call
(cons (list my-cont cont-args) #continuation) . args
)
)
Having to define two versions of everything like this is a pain, BTW.
I could just use the procedural version, which implicitly allows
functional code as well, but that would need to be wrapped in
(#unsafe-perform ...) for functional code :-(
The continuation arguments are there to allow the easy definition of
things like catch/throw; the catch leaves a tag in the continuation
chain, which throw finds by recursing up the chain. Nice.
A normal #perform! or #apply also extends the continuation chain like
that, only implicitly.
The thing is, in this way, we could create a chain with procedural
continuations at the top where the procedural code occurs, and
functional continuations thereafter where we enter functional
operations... and since functional code cannot invoke procedural
closures, we would not be able to leap out of the functional
computation into the procedural world, but we could leap over
procedural islands created by (#unsafe-perform ...) by applying a
functional continuation above it.
But there will need to be a mechanism for preventing functional
continuations passing out of their scope, as described above, still...
Thanx,
ABW
--
"Plug and Play support: WfEWAD will autodetect any installed
Nuclear Arsenals, Laser Satellites, Battlefield Control Networks,
Radar Installations, Fighter Squadrons, and other WfEWAD compliant
devices, including the new Macrosoft Unnatural Keyboard, with
full support for the now-famous Big Red Buttom(tm)."
(Windows for Early Warning and Defence User's manual P26)
Alaric B. Williams Internet : ala...@abwillms.demon.co.uk
<A HREF="http://www.abwillms.demon.co.uk/">Hello :-)</A>
Brian Harvey
ala...@abwillms.demon.co.uk (Alaric B. Williams) writes:
>(define (perform/cc! my-cont (what-to-call . args) . cont-args)
Don't you have the same problem with any higher-order procedure/function?
(define (inc delta)
(set! global (+ global delta))
delta)
(apply/map (lambda (x) (+ x 3)) ...)
(perform/map inc ...)
Alaric B. Williams
On 2 Apr 1997 18:26:05 GMT, b...@anarres.CS.Berkeley.EDU (Brian Harvey)
wrote:
>Don't you have the same problem with any higher-order procedure/function?
Yeah :-(
Fare's suggestion was to dump the functional/procedural distinction at
the call site, and have the compiler deduce procedurality in closures
itself. Well, closures can be compiled at runtime from code read in
from The User Herself (oooh, sexist bias!), so predicting that
could be a pain. Also, I feel that procedurality or functionality
of a call/application site is something the programmer should see.
Abstracting out things like representations are good, of course, but
abstracting out the exact meaning of a closure invocation seems
perilous to me. Applying a function and performing an operation
are different operations; performance is a superset of application,
yes, but something that is a procedure rather than a function is
a dangerous thing indeed; we can't memoize it's return value,
we can't perform all it's invocations on a seperate processor
before the program even "starts" and replace it with a constant
lookup, etc.
Making the difference evident to the programmer makes sure he and the
compiler agree on what a piece of code does. The problem arises when
it doesn't amtter what a piece of code does - in the higher order
example.
Therefore, I'll have to make more of the superset relationship between
functions and procedures in the typing system, and allow it to be
arbitary in places...
(#do!? ...)
perhaps :-)
Or make 'em use macros... that's how C provides higher order
operations! Let's go down the road to ruin! Wahey!