README.md @master — view markup · raw · history · blame
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
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.
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
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
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
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
eg directory may help illuminate the
First-in, first-out stack, with operations
Contains a manually expanded version of the stack data structure for illustration purposes.
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.
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.