Lift: a Controlled State Operator

by Dave Herman (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.

1 Getting Started

To use this library, simply require its main module:

(require (planet dherman/lift:1))

2 Defining a Lift Channel

All lifted values must be communicated via a lift channel, a first-class value that can be created with make-lift-channel.

(make-lift-channel) → lift-channel?

Creates a new lift channel.

(lift-channel? x) → boolean?

x : any

Determines whether x is a lift channel.

(lift-channel-live? ch) → boolean?

ch : lift-channel?

Determines whether ch is live, meaning that there is a lift handler associated with ch in the current continuation. Lift handlers are installed via capture.

3 Lifting Values

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

(lift ch x) → any

ch : lift-channel?

x : any

Lifts the value x through lift channel ch.

If ch is not currently live, an exn:fail exception is raised.

4 Capturing Lifted Values

(capture (handler ...) body ...+)

handler   =   [channel-expr #:when pred-expr]     |   [channel-expr]

Evaluates the body in a dynamic context where lifts are captured by the handler forms. The expression produces m + n values, where the first m values are those produced by the body, and the remaining 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 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.

5 Example

(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))