Extensible Functions

A solution to the expression problem in Typed Racket.

1 Overview

It is surprising how little people talk about the expression problem, given how frequently it manifests in everyday programming.

The expression problem is a fundamental issue in programming. It is related to the tension between abstracting over data types and abstracting over functions. Most Racket programs follow the functional-programming paradigm—though Racket has support for object-oriented programming, generally only GUI-related code takes advantage of it. So, in most Racket programs the main form of abstraction is the function. However, when working with extensible data types, functions are limited. Consider the following example:

(struct Expression () #:transparent)

(struct Expression-Integer Expression

([integer : Integer])

#:transparent)

(struct Addition Expression

([operand/left : Expression]

[operand/right : Expression])

#:transparent)

; -----------------------------------------------------------

(: pretty-print/non-extensible (-> Expression String))

(define/match (pretty-print/non-extensible expression)

[((Expression-Integer integer)) (~a integer)]

[((Addition operand/left operand/right))

(~a "(" (pretty-print/non-extensible operand/left) "+"

(pretty-print/non-extensible operand/right) ")")])

; -----------------------------------------------------------

(struct Subtraction Expression

([operand/left : Expression]

[operand/right : Expression])

#:transparent)

(define (pretty-print/non-extensible expression)

"Cannot extend “pretty-print/non-extensible” to work on “Subtraction”")

The code above starts by defining structures for arithmetic expressions. Next, it defines a pretty printer. Then, the existing data types are extended with a new type of expression, subtraction. At this point, there is no natural way to extend the pretty printer to work over subtractions.

Let us explore two non-solutions. The first is to define a new function:

(: pretty-print/extended (-> Expression String))

(define/match (pretty-print/extended expression)

[((Subtraction operand/left operand/right))

(~a "(" (pretty-print/extended operand/left) "-"

(pretty-print/extended operand/right) ")")]

[_ (pretty-print/non-extensible expression)])

The new function pretty-printer/extended handles the case of the data type extension (subtraction) and delegates to the original pretty-print/non-extensible for the other cases. This does not work: note that the pretty printer for addition recursively calls itself, but it always calls pretty-printer/non-extensible and not pretty-printer/extended. So the pretty printer would fail for an expression in which subtraction occurs in one operand of addition—for example, (Addition (Subtraction (Expression-Value 2) (Expression-Value 3)) (Expression-Value 4)).

The second non-solution is to copy and paste the body of pretty-print/non-extensible into pretty-print/extended, replacing all recursive calls accordingly. There are many problems with this approach. The most outstanding is the repeated code and the burden to maintain it. Also, this non-solution would require changing all call-sites of the original function to the newly extended version. Finally, the extensions are not composable. For example, one module extending expressions with multiplication would need to be aware of extensions already in place (subtraction). This is not manageable if extension writers are different people, working on different modules in different packages.

We introduce a solution to the expression problem: extensible functions. With extensible functions, the pretty printer is a function open for extensions. Consider the following rewrite:

Note the importance of occurrence typing for extensible functions to work in the type system.

(struct Expression () #:transparent)

(struct Expression-Integer Expression

([integer : Integer])

#:transparent)

(struct Addition Expression

([operand/left : Expression]

[operand/right : Expression])

#:transparent)

; -----------------------------------------------------------

(define/match/extensible (pretty-print expression)

: (-> Expression String)

[((Expression-Integer integer)) (~a integer)]

[((Addition operand/left operand/right))

(~a "(" (pretty-print operand/left) "+"

(pretty-print operand/right) ")")])

; -----------------------------------------------------------

(struct Subtraction Expression

([operand/left : Expression]

[operand/right : Expression])

#:transparent)

; -----------------------------------------------------------

(define/match/extension/pretty-print

[((Subtraction operand/left operand/right))

(~a "(" (pretty-print operand/left) "-"

(pretty-print operand/right) ")")])

In the code above, define/match/extensible defines pretty-print for the existing expressions, but leaves the function open for extension. Later, when subtraction is defined, the pretty printer is extended with define/match/extension/pretty-print. At this point, pretty-print supports subtraction, even if occurs inside an addition.

Shadowing existing functions with an extension that matches the same data type—or a supertype thereof—is considered bad form as it obscures the meaning of the program.

Caveat: extensible functions work by mutating the original function—in other words, extending a function is a stateful operation. This means the order of requires becomes meaningful to the program. Also, if two extensions match the same data type—or a supertype thereof—the second definition shadows the first.

2 Installation

Extensible Functions are a Racket package. Install it in DrRacket or with the following command line:

$ raco pkg install extensible-functions

3 Usage

4 Changelog

This section documents all notable changes to Extensible Functions. It follows recommendations from Keep a CHANGELOG and uses Semantic Versioning. Each released version is a Git tag.

4.1 0.0.1 · 2017-02-07

4.1.1 Added

• Basic functionality.