klisp

an open source interpreter for the Kernel Programming Language.
git clone http://git.hanabi.in/repos/klisp.git
Log | Files | Refs | README

continuations.texi (9105B)


      1 @c -*-texinfo-*-
      2 @setfilename ../src/continuations
      3 
      4 @node Continuations, Encapsulations, Combiners, Top
      5 @comment  node-name,  next,  previous,  up
      6 
      7 @chapter Continuations
      8 @cindex continuations
      9 
     10   A continuation is a plan for all future computation, parameterized
     11 by a value to be provided, and contingent on the states of all mutable
     12 data structures (which notably may include environments). When the
     13 Kernel evaluator is invoked, the invoker provides a continuation to
     14 which the result of the evaluation will normally be returned.
     15 
     16   For example, when @code{$if} evaluates its test operand, the
     17 continuation provided for the result expects to be given a boolean
     18 value; and, depending on which boolean it gets, it will evaluate
     19 either the consequent or the alternative operand as a tail context —
     20 that is, the continuation provided for the result of evaluating the
     21 selected operand is the same continuation that was provided for the
     22 result of the call to @code{$if}.
     23 
     24   A Kernel program may sometimes capture a continuation; that is,
     25 acquire a reference to it as a first-class object. The basic means of
     26 continuation capture is applicative @code{call/cc}.  Given a
     27 first-class continuation @code{c}, a combiner can be constructed that
     28 will abnormally pass its operand tree to @code{c} (as opposed to the
     29 @c TODO add xref to abnormal pass
     30 normal return of values to continuations). In the simplest case, the
     31 abnormally passed value arrives at @code{c} as if it had been normally
     32 returned to @code{c}. In general, continuations bypassed by the
     33 abnormal pass may have entry/exit guards attached to them, and these
     34 guards can intercept the abnormal pass before it reaches @code{c}.
     35 Each entry/exit guard consists of a selector continuation, which
     36 designates which abnormal passes the guard will intercept, and an
     37 interceptor applicative that performs the interception when selected.
     38 @c TODO add xref to guard-continuation, continuation->applicative
     39 @c and abnormal pass
     40 
     41   Continuations are immutable, and are @code{equal?} iff @code{eq?}.
     42 The continuation type is encapsulated.
     43 
     44 @c TODO add dynamic extent & guard selection/interception to the intro
     45 @deffn Applicative continuation? (continuation? . objects)
     46   The primitive type predicate for type continuation.
     47 @code{continuation?} returns true iff all the objects in
     48 @code{objects} are of type continuation.
     49 @end deffn
     50 
     51 @deffn Applicative call/cc (call/cc combiner)
     52   Calls @code{combiner} in the dynamic environment as a tail context,
     53 passing as sole operand to it the continuation to which @code{call/cc}
     54 would normally return its result.  (That is, constructs such a
     55 combination and evaluates it in the dynamic environment.)
     56 @c TODO add xref Cf. operative $let/cc , §7.3.2.
     57 @end deffn
     58 
     59 @deffn Applicative extend-continuation (extend-continuation continuation applicative [environment]) 
     60   The @code{extend-continuation} applicative constructs and returns a
     61 new child of @code{continuation} that, when it normally receives a
     62 value v, calls the underlying combiner of @code{applicative} with
     63 dynamic environment @code{environment} (or an empty environment if
     64 none was specified) and operand tree @code{v}, the result of the call
     65 normally to be returned to @code{continuation}.
     66 
     67   The following equivalnece defines the short version:
     68 @example
     69 (extend-continuation c a) @equiv{} 
     70   (extend-continuation c a (make-environment))
     71 @end example
     72 @end deffn
     73 
     74 @deffn Applicative guard-continuation (guard-continuation entry-guards continuation exit-guards)
     75   @code{entry-guards} and @code{exit-guards} should each be a list of
     76 clauses; each clause should be a list of length two, whose first
     77 element is a continuation, and whose second element is an applicative
     78 whose underlying combiner is operative.  
     79 
     80   Applicative @code{guard-continuation} constructs two continuations:
     81 a child of continuation, called the @code{outer continuation}; and a
     82 child of the @code{outer continuation}, called the @code{inner
     83 continuation}.  The @code{inner continuation} is returned as the
     84 result of the call to @code{guard-continuation}.
     85 
     86   When the @code{inner continuation} normally receives a value, it
     87 passes the value normally to the @code{outer continuation}; and when
     88 the @code{outer continuation} normally receives a value, it passes the
     89 value normally to @code{continuation}. Thus, in the absence of
     90 abnormal passing, the inner and outer continuations each have the same
     91 behavior as @code{continuation}.
     92 
     93   The two elements of each guard clause are called, respectively, the
     94 @code{selector} and the @code{interceptor}.  The @code{selector}
     95 continuation is used in deciding whether to intercept a given abnormal
     96 pass, and the @code{interceptor} applicative is called to perform
     97 @c TODO add xref to selection and interception
     98 customized action when interception occurs.
     99 
    100 @c TODO add xref to evaluation structure
    101 At the beginning of the call to @code{guard-continuation}, internal
    102 copies are made of the evaluation structures of @code{entry-guards}
    103 and @code{exit-guards}, so that the selectors and interceptors
    104 contained in the arguments at that time remain fixed thereafter,
    105 independent of any subsequent mutations to the arguments.
    106 @end deffn
    107 
    108 @deffn Applicative continuation->applicative (continuation->applicative continuation)
    109   Returns an applicative whose underlying operative abnormally passes
    110 its operand tree to @code{continuation}, thus: A series of
    111 interceptors are selected to handle the abnormal pass, and a
    112 continuation is derived that will normally perform all the
    113 interceptions in sequence and pass some value to the destination of
    114 the originally abnormal pass.  The operand tree is then normally
    115 passed to the derived continuation.
    116 @c TODO add xref to selection and interception
    117 @end deffn
    118 
    119 @defvar root-continuation
    120   This continuation is the ancestor of all other continuations. When
    121 it normally receives a value, it terminates the Kernel session. (For
    122 example, if the system is running a read-eval-print loop, it exits the
    123 loop.)
    124 @c TODO add xref  Cf. applicative exit, §7.3.4.
    125 @end defvar
    126 
    127 @defvar error-continuation
    128   The dynamic extent of this continuation is mutually disjoint from
    129 the dynamic extent in which Kernel computation usually occurs (such as
    130 the dynamic extent in which the Kernel system would run a
    131 read-eval-print loop).  
    132 
    133   When this continuation normally receives a value, it provides a
    134 diagnostic message to the user of the Kernel system, on the assumption
    135 that the received value is an attempt to describe some error that
    136 aborted a computation; and then resumes operation of the Kernel system
    137 at some point that is outside of all user-defined computation. (For
    138 example, if the system is running a read-eval-print loop, operation
    139 may resume by continuing from the top of the loop.)
    140 
    141   The diagnostic message is not made available to any Kernel
    142 computation, and is therefore permitted to contain information that
    143 violates abstractions within the system.  
    144 
    145 @c TODO add details about klisp error messages
    146   When an error is signaled during a Kernel computation, the signaling
    147 action consists of an abnormal pass to some continuation in the
    148 dynamic extent of @code{error-continuation}.
    149 @end defvar
    150 
    151 @deffn Applicative apply-continuation (apply-continuation continuation object)
    152   Applicative @code{apply-continuation} converts its first argument to
    153 an applicative as if by @code{continuation->applicative}, and then
    154 applies it as usual.
    155 
    156   That is:
    157 @example
    158 (apply-continuation continuation object) @equiv{}
    159   (apply (continuation->applicative continuation) object)
    160 @end example
    161 @end deffn
    162 
    163 @deffn Operative $let/cc ($let/cc <symbol> . <objects>)
    164   A child environment @code{e} of the dynamic environment is created,
    165 containing a binding of @code{<symbol>} to the continuation to which
    166 the result of the call to @code{$let/cc} should normally return; then,
    167 the subexpressions of @code{<objects>} are evaluated in @code{e} from
    168 left to right, with the last (if any) evaluated as a tail context, or
    169 if @code{<objects>} is empty the result is inert.
    170 
    171   That is:
    172 @example
    173 ($let/cc symbol . objects) @equiv{} 
    174   (call/cc ($lambda (symbol) . objects))
    175 @end example
    176 @end deffn
    177 
    178 @deffn Applicative guard-dynamic-extent (guard-dynamic-extent entry-guards combiner exit-guards)
    179   This applicative extends the current continuation with the specified
    180 guards, and calls @code{combiner} in the dynamic extent of the new
    181 continuation, with no operands and the dynamic environment of the call
    182 to @code{guard-dynamic-extent}.
    183 @end deffn
    184 
    185 @deffn Applicative exit (exit [object])
    186 @c TODO add xref
    187   Applicative @code{exit} initiates an abnormal transfer of
    188 @code{object} (or @code{#inert} if @code{object} was not specified), 
    189 to @code{root-continuation}.
    190   That is:
    191 @example
    192 (exit) @equiv{} (apply-continuation root-continuation #inert)
    193 (exit obj) @equiv{} (apply-continuation root-continuation obj)
    194 @end example
    195 
    196   SOURCE NOTE: This applicative doesn't have the optional argument in
    197 the report.  It was added to klisp to allow a simple way to terminate
    198 the interpreter passing a value that is then tried to convert to an
    199 exit status.
    200 @end deffn
    201 
    202 
    203 
    204