Information Hiding in Scheme

Say you wanted to implement an abstract data typeᵂᴾ (ADT) in R5RS Scheme. How would you do it?

Could you do it? On first blush, it might appear that you can't. There is no module system, and the data structuring facilities that Scheme provides are really primitive. If you represent your data type as a list, any client code could just take it apart with car and cdr, and, worse, could cons together any other thing and pass that off as an instance of your data type.

But there are ways to do information hiding in Scheme. In this document I'll describe two of them. The first implements a classic ADT, while the second implements something closer to object-oriented programming; both approaches nevertheless provide opaque containers for data.

(An implementation of these methods as macros is available in the public-domain Scheme library define-opaque.)

1. Using Secret Tokens

The approach that gets you ADTs relies on two properties of Scheme:

• Scheme does have an opaque data structure: the function value.
• (eq? (list 1) (list 1)) is #f, that is, every cons-cell can be distinguished from every other cons-cell.

(The former would not be true if one could examine the definition of a function value. The latter would not be true if Scheme implemented hash consingᵂᴾ.)

The basic idea is straightforward. We define a function which we call a module. When called, the module generates a few values internally. One of these values is a unique cons-cell which we'll call the secret token of the module. Other values are functions, which we'll call operations.

Each operation requires a token to work, and only performs its intended function when this token matches the secret token defined by the module.

There are some restrictions on the value that the module returns to its caller. The value may contain the operations defined by the module (in fact the value may simply be a list of all these operations), but the value must not contain the secret token.

Likewise, the values returned by the operations must not contain the secret token.

(These values may be functions which have closed over the secret token. But they should not be the secret token nor return it.)

In this way, clients of the module may use the operations of the module without having to know, nor being able to alter or counterfeit, the concrete data format that the operations work on.

seal and open

Because every operation follows the same pattern — pass the secret token to a given opaque object to obtain the internal representation, examine or modify the internal representation, then possibly create a new opaque object — it is useful to write a pair of helper functions to "open" and "seal" these objects using the module's secret token, and then write all operations using these helpers.

seal takes some data, and returns a function which does the following: it takes a token, and if that token matches the secret token, it returns the data, otherwise it returns an error value.

open takes an opaque object and calls it using the secret token returning the data.

Both helper functions "know" the secret token, because they are defined inside the module where the secret token is created and used; the definitions of these functions close over the secret token value.

Example Code

See the file information-hiding.scm for an example of using this technique to implement a stack ADT.

2. Using Closures Only

Since function values in Scheme are opaque, the secret tokens we use above aren't actually necessary to achieve opacity. Your module function can simply generate a mutable value internally, and all of the operation functions can close over it. This way, they all have it in scope, and can read it and modify it as appropriate, but as long as none of the operations return it directly, their callers can never see it. No secret token is needed to prevent this.

But this introduces some complexities, which we could identify as identity and mutability.

First, identity. Unlike the structure defined with the secret token, an opaque data structure defined this way can't attest its identity. A function that takes an opaque object and expects it to be, for instance, a queue, can't require that it actually is a queue; it can only require that it "self-identifies" as a queue. This is in line with duck typing and object-oriented programming, but some applications, such as LCF architecture, require an identity guarantee which this lacks.

Second, mutability. The scheme described above works best if you're willing for your hidden value to be updated in-place. If this is acceptable, then the technique is straightforward. The module function can return, not a list of operations, but a single function; and this single function can take, as its first argument, a symbol which indicates what operation to perform.

You may note that this resembles object-oriented method dispatch, and can be used to implement object-oriented features such as inheritance. This further strengthens the idea that what are working with is no longer a classical ADT, but rather an object from OOP, and we shall call it such, because the distinction is a real one. A fascinating and persuasive read on this distinction is William R. Cook's 2009 essay On Understanding Data Abstraction, Revisited (PDF).

As an illustration of how straightforward this implementation is, see the file mutable-object.scm for an example of using this technique to implement a mutable stack object.

If you want your hidden data to be immutable dataᵂᴾ, though, it begins to get slightly trickier to arrange, because every operation of the object that modifies your hidden data — sorry, I mean: that produces a modified version of your hidden data — has to return a new, immutable instance of the object, and by association, all of its operations too.

We can continue to use the "method dispatch" approach of having all operations implemented by a single function that takes a symbol to choose the operation, but now we define that single function with letrec so that it can, essentially, return a new version of itself when necessary.

See the file immutable-object.scm for an example of using this technique to implement a stack object.

---

Document history: * Jul 2026: update primarily to note ADTs vs objects, and LCF * May 2021: initial published version