<!--
SPDX-FileCopyrightText: In 2023, Chris Pressey, the original author of this work, placed it into the public domain.
SPDX-License-Identifier: Unlicense
For more information, please refer to <https://unlicense.org/>
-->

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`](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](eg/) may help illuminate the
usage patterns:

#### [stack.scm](eg/stack.scm)

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

#### [stack-expanded.scm](eg/stack-expanded.scm)

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

#### [proper-list.scm](eg/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](eg/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][].

[Information Hiding in Scheme]: https://codeberg.org/catseye/The-Dossier/src/branch/master/article/Information-Hiding-in-Scheme/
[LCF-style]: https://codeberg.org/catseye/The-Dossier/src/branch/master/article/LCF-style-Natural-Deduction/
[Logic as Algebra]: https://archive.org/details/logicasalgebra0000halm
[On Understanding Data Abstraction, Revisited]: https://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf