Racket

Transparent Procedures🔗ℹ

Cameron Moy

(require transparent-procedure)
	package: transparent-procedure-lib

Procedures are opaque values that, at least in principle, have no properties other than their behavior upon application. In practice, most programming languages aren’t so disciplined.

> (equal? add1 add1)
#t

Equality of functions in Racket, as in many other languages, is defined as pointer equality. This capability is not strictly kosher.

> (equal? add1 (lambda (x) (add1 x)))
#f

An η-expanded version of add1 yields a different result, meaning that η-expansion does not preserve all observations of a function. This lapse is a deliberate choice to ensure that equal? remains a total function.

Usually one does not want to compare functions, but there are situations where it’s desirable. For instance, most memoization implementations use a hash table to cache previous results. As a consequence, memoization of higher-order functions is thwarted by extensionally equivalent program transformations such as η expansion. The potential of cache misses for memoized higher-order functions does not affect correctness, so it may not seem like much of a problem. However, it’s actually possible to perfectly memoize higher-order functions. The idea is to track all interactions with a higher-order input and store a first-order representation of its extensional behavior. Determining if a future application is in cache requires testing if inputs behave (extensionally) the same as anything recorded in the memo table.

This library provides transparent procedures that automatically construct these first-order representations. Given a procedure, make-procedure returns a transparent version that records all interactions with the underlying value.

> (define inc (make-procedure (λ (x) (+ x 1))))
> inc
(procedure)

Initially, the procedure has no recorded behavior so it’s printed empty.

> (void (inc 1) (inc 2) (inc 3))
> inc
(procedure [ 1 . 2 ] [ 2 . 3 ] [ 3 . 4 ])

Printing after three applications shows a partial graph of the function. Transparent procedures whose partial graphs can be made compatible are considered equal?.

> (define add1′ (make-procedure add1))
> (void (add1′ 3) (add1′ 4) (add1′ 5))
> (equal? inc add1′)
#t

After checking for equality, the partial graphs of each function are equal (as sets).

> inc
(procedure [ 1 . 2 ] [ 2 . 3 ] [ 3 . 4 ] [ 4 . 5 ] [ 5 . 6 ])
> add1′
(procedure [ 3 . 4 ] [ 4 . 5 ] [ 5 . 6 ] [ 1 . 2 ] [ 2 . 3 ])

Intuitively, think of make-procedure as similar to constructors of other mutable data structures such as make-hash. However, instead of being able to mutate the data structure using an operation such as hash-set!, application of a transparent procedure mutates the underlying data structure based on the input and output. As with other mutable data structures, equal? is interpreted as "equal now," and eq? is interpreted as "equal always." The result of equal? may change based on future interactions with the transparent procedure that reveal more of its graph.

Because higher-order functions nest arbitrarily, the graph has to be deep, in the sense that higher-order arguments and results must themselves be transparent too.

> (define map′ (make-procedure map))
> (void (map′ add1 '(1 2 3)))
> (void (map′ sub1 '(4 5 6)))
> map′
(procedure [ (procedure [ 6 . 5 ] [ 5 . 4 ] [ 4 . 3 ]) '(4 5 6) . '(3 4 5) ] [ (procedure [ 3 . 4 ] [ 2 . 3 ] [ 1 . 2 ]) '(1 2 3) . '(2 3 4) ]

Because map′ is transparent, it "infects" the higher-order inputs add1 and sub1. A consequence of this behavior is that make-procedure works correctly only for data that is inspectable.

> (struct unknown ())
> (define values′ (make-procedure values))
> (values′ (unknown))
make-procedure: cannot inspect #<unknown>

Transparent procedures are dictionaries that allow access to the partial graph.

> (define (f x) (if (zero? x) 0 (add1 x)))
> (define map′-curried (dict-ref map′ f))
> map′-curried
(procedure [ '(1 2 3) . '(2 3 4) ])
> (dict-ref map′-curried '(1 2 3))
'(2 3 4)

The nested structure of this dictionary makes it a trie where every argument is a "character."

Even though f is not the same function as add1, the dictionary lookup is successful because it behaves extensionally the same as far as map′ is concerned. The dict-ref function takes one argument at a time, leading to currying behavior.

> (dict-ref map′-curried '(10 11 12))
dict-ref: no value found for key '(10 11 12)
> (map′ f '(10 11 12))
'(11 12 13)
> (dict-ref map′-curried '(10 11 12))
'(11 12 13)

The partial graph of a pure function grows monotonically over time. Impure functions, however, can modify existing entries like any other mutable data structure.

> (define counter
    (make-procedure
     (let ([state 0])
       (λ ()
         (set! state (add1 state))
         state))))
> (begin (counter) counter)
(procedure [ . 1 ])
> (begin (counter) counter)
(procedure [ . 2 ])

Coming back to the original example, higher-order memoization works by making the underlying procedure transparent and then retrieving cached entries through the dictionary interface.

> (define (memo f)
    (define g (make-procedure f))
    (define absent (gensym))
    (λ args
      (let go ([g g] [args args])
        (match args
          [(list) g]
          [(cons arg args-rest)
           (let ([g′ (dict-ref g arg absent)])
             (if (eq? g′ absent)
                 (apply g args)
                 (go g′ args-rest)))]))))

Here, g is equivalent to the hash table of an ordinary memoization function. Upon application, the memoized function checks for each argument according to g. If the argument is not present, then the result is computed. Otherwise, the cached value is returned.

> (define filter′
    (memo
     (λ (f xs)
       (displayln "cache miss")
       (filter f xs))))
> (filter′ integer? '(1 0.5 3))
cache miss
'(1 3)
> (filter′ (λ (x) (integer? x)) '(1 0.5 3))
'(1 3)

1 Reference🔗ℹ

procedure
(make-procedure v) → transparent-procedure?
v : procedure?

Returns a transparent version of v that incrementally builds a partial graph of its behavior. Transparent procedures are comparable with equal? and procedure-includes?. A transparent procedure is also an immutable dictionary.

procedure
(procedure-includes? x y) → boolean?
x : transparent-procedure?
y : procedure?

The order imposed by procedure-includes? is precisely the same as that for function domains: f ⊑ g if and only if for all x in the domain of f, f(x) ⊑ g(x).

Returns whether the partial graph of x is contained within the behavior of y. This function interacts with y according to every entry in the partial graph of x in order to compute the result.

> (define abs′ (make-procedure abs))
> (void (abs′ 1) (abs′ -2))
> (procedure-includes? abs′ (λ (x) (if (> x 0) x (- x))))
#t
> (procedure-includes? abs′ values)
#f

procedure
(transparent-procedure? v) → boolean?
v : any/c

Returns whether v is a transparent procedure.

2 Prior Art🔗ℹ

Higher-order memoization was first described by Ralf Hinze [Hinze 2000] as a passing remark. It was explored further by Conal Elliott in a series of blog posts, which became the foundation for a memoization library for Haskell. This library is an adaptation of those ideas in ways that are ergonomic for Racket.

Bibliography🔗ℹ

[Hinze 2000]

Ralf Hinze, “Memo functions, polytypically!,” Workshop on Generic Programming (WGP), 2000. https://www.cs.ox.ac.uk/people/ralf.hinze/publications/WGP00b.ps.gz