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.
Commit History
@master
git clone https://git.catseye.tc/define-opaque/
- Move licensing info from .reuse/dep5 file into individual files. Chris Pressey 2 months ago
- Adjust SPDX fields to better conform to the REUSE 3.0 spec. Chris Pressey 9 months ago
- Aesthetics. Chris Pressey 9 months ago
- Rearrange license info in accordance with REUSE 3.0 convention. Chris Pressey 9 months ago
- Add example based on "A Small Logic" from "Logic as Algebra". Chris Pressey 10 months ago
- Move usage examples to an `eg` directory. Chris Pressey 11 months ago
- Call `error` on undefined operation, even though it is not R5RS. Chris Pressey 11 months ago
- In version 0.2 you can supply default values for private fields. Chris Pressey 11 months ago
- Show the full expanded version next to a cleaned-up version. Chris Pressey 11 months ago
- Add an example of what the macro expands to, to aid understanding. Chris Pressey 11 months ago