#lang scribble/doc

@begin[(require scribble/manual)
       (require scribble/basic)
       (require (for-label "main.ss"))]

@title[#:tag "top"]{@bold{Lift}: a Controlled State Operator}
@declare-exporting[(planet dherman/lift:1)]

by Dave Herman (@tt{dherman at ccs dot neu dot edu})

This library provides a controlled state operator for communicating values
up a continuation, rather like exceptions that do not interrupt evaluation.
This is particularly useful for tree traversals that simultaneously transform
trees and extract inner components of the tree into outer contexts. Lifting
provides a controlled form of mutable state, "catching" values lifted out of
an inner context into some outer context.

@table-of-contents[]

@section[#:tag "started"]{Getting Started}

To use this library, simply require its @tt{main} module:

@defmodule[(planet dherman/lift:1)]

@section[#:tag "channels"]{Defining a Lift Channel}

All lifted values must be communicated via a @deftech{lift channel}, a first-class
value that can be created with @scheme[make-lift-channel].

@defproc[(make-lift-channel) lift-channel?]{
Creates a new lift channel.}

@defproc[(lift-channel? [x any]) boolean?]{
Determines whether @scheme[x] is a lift channel.}

@defproc[(lift-channel-live? [ch lift-channel?]) boolean?]{
Determines whether @scheme[ch] is @deftech{live}, meaning that there is a lift handler
associated with @scheme[ch] in the current continuation. Lift handlers are installed
via @scheme[capture].}

@section[#:tag "lift"]{Lifting Values}

The @scheme[lift] procedure propagates a value outwards to the dynamic context,
to be received by the @scheme[capture] form.

@defproc[(lift [ch lift-channel?] [x any]) any]{
Lifts the value @scheme[x] through lift channel @scheme[ch].

If @scheme[ch] is not currently live, an @scheme[exn:fail] exception is raised.}

@section[#:tag "capture"]{Capturing Lifted Values}

@defform*/subs[#:id capture
               [(capture (handler ...) body ...+)]
               ([handler [channel-expr #:when pred-expr]
                         [channel-expr]])]{
Evaluates the @scheme[body] in a dynamic context where lifts are captured by
the @scheme[handler] forms. The expression produces @italic{m + n} values, where
the first @italic{m} values are those produced by the @scheme[body], and the
remaining @italic{n} values are lists of captured lifts, one for each channel
handler.

Each of the lists contains the items in the order in which they were lifted.

When a predicate is provided via a @scheme[pred-expr] for a channel, only those
values satisfying the predicate are captured. Any other values remaining in the
channel propagate outwards to the calling context.}

@section[#:tag "example"]{Example}

@schemeblock[(define (fringe tree)
               (define ch (make-lift-channel))
               (capture ([ch #:when symbol?])
                 (let search ([tree tree])
                   (cond
                     [(symbol? tree)
                      (lift ch tree)
                      (values)]
                     [(pair? tree)
                      (search (car tree))
                      (search (cdr tree))]
                     [else (values)]))))
             (define (same-fringe? t1 t2)
               (equal? (fringe t1) (fringe t2)))
             (fringe '(((((a) b) . c) (d e f g)) . (h i j k)))
             (fringe '(a b c d e f g h i j k))]