define-opaque

This is an attempt to write a macro in R5RS Scheme that defines opaque data structures. It is based on the third example given in Information Hiding in Scheme.

It is not intended to be suitable for production use. It is, however, intended to properly hide the details of the created data structure, by preventing access to it by any means other than via the defined operations.

The macro is defined in src/define-opaque-0.2.scm. Its definition easily fits on a page, and is worth reading.

The idea is that you'd just copy it into your project and (load "define-opaque-0.2.scm") where you need it.

Basic Usage

The arguments to the define-opaque macro are

• the name of the opaque data structure that will result (this name will be visible globally)
• the name of a function which creates a new instance of the data structure (this name will be visible only to the operations)
• a list of names for the data items used internally (these names will be visible only to the operations)
• a list of the values to be taken on by default by the internal names (must match length of previous list)
• a list of operations. Each operation is a 2-element list, consisting of its name, and a lambda expression giving its implementation.

The opaque data structure that results is a Scheme function. When it is called, the first argument must be the name of an operation; the remainder of the arguments are passed to the internal implementation of the operation.

If the data structure does not support an operation with the given name, a procedure called error will be called. Some Schemes, such as Chicken, provide this as a built-in procedure; if your Scheme does not, you might want to provide an implementation before loading define-opaque-0.2.scm. (But if you don't, your Scheme should error out anyway when it tries to call error, which is exactly the intent, so it shouldn't be a big deal.)

Typically, the opaque data structure that results is treated as a "protoype", and one defines an operation called new (or similar) that provides a way to initialize a new instance of the data structure, possibly based on some given initialization parameters.

If the above description is unclear, the example programs in the eg directory may help illuminate the usage patterns:

stack.scm

First-in, first-out stack, with operations push, top, and pop.

stack-expanded.scm

Contains a manually expanded version of the stack data structure for illustration purposes.

proper-list.scm

Proper cons lists, where the tail of a list must be another list (cons cell or nil) and not value of some other type, like number.

a-small-logic.scm

An LCF-style adaptation of the tiny proof system given in section 4 ("A Small Logic") in Logic as Algebra (1998) by Paul Halmos and Steven Givant. It preserves the additive properties of parity.

Our implementation of theorems in this proof system as an opaque type means we cannot create a theorem object except by application of valid deductions on existing objects. Thus, we cannot create (that is, prove) an invalid theorem.

However, as the proper-list.scm source demonstrates, there are limitations to this, and if we were to implement a slightly less trivial proof system, we would run into them.

Namely, an operation cannot require that one of its parameters is truly the same type as the opaque type on which the operation is defined. To find out the type of an opaque type, we must "ask" it (by performing one of its operations, much like a method call on an object). We are therefore trusting it to identify itself. We cannot require that (for example) the parameters to a modus ponens operation are valid theorem objects; we can only require that they "self-identify" as theorems, which is of course rather too weak a test to prevent abuse.

This could possibly be remedied by choosing one of the other approaches from Information Hiding in Scheme. The shared secret, for example, would let us confirm that another object is the same type (holds the same secret) as our opaque type.

This relates closely to the comparison of abstract data types and objects in William Cook's 2009 essay On Understanding Data Abstraction, Revisited.