1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
# Singly Ad-Hoc Polymorphic Procedures (SAHP) with Scope
## Introduction
This is an R7RS library that implements what the title says:
* Ad-hoc: Polymorphism based on implementing specific procedures.
* Singly polymorphic: The implementation is selected based off of a single
argument.
* With scope: SAHP implementations can be overridden in dynamic scope,
and (somewhat) lexical scope. SAHPs can also be closed in lexical scope
and passed to other procedures outside of lexical scope while retaining
their bindings.
These procedures are called "SAHPs" (pronounced "saps").
This library is meant to be a system of polymorphic functions completely
indepent of any object system. It is meant to be simple and have no
surprises.
### Why Singly Polymorphic (aka Single Dispatch)?
Multiple dispatch runs into problems similar to that of multiple
inheritance, except that there is no obvious dismabiguation pattern when
two equally specific multiple dispatch methods exist.
If one wanted multiple dispatch or multiple inheritance, it would be
better to use a CLOS style system, which has much more fine-grained
control over method dispatch. Dynamic and local scoping could be added
to a CLOS style system, although the API would probably have to change.
### Why Scope?
SAHPs should behave like regular procedures wherever possible. This means
allowing for redefinition in lexical scope. Normal procedures only have
one body, while SAHPs have multiple, so local[^2] scope should only
override the procedure bodys that are specified. Locally scoped SAHPs
will also capture their lexical environment and can be passed around
like closures, while still maintaining their global state.
[^2]: I call it "local" instead of "lexical" scope because it might not
technically be "lexical scope".
If SAHPs could only be modified with lexical scope, they would not be
very useful. A library should be able to register a global change to a
SAHP for any record type that it makes. Hence SAHPs also have a global
scope which is always shadowed by a SAHP's local scope.
AHSPs also have a dynamic scope (implemented using parameters) that
can override global but not local scope. Dynamic scope allows for the
program to override default behavior for programs not in lexical scope
without mutating global state and without overriding local scope.
### On Inheritance
Scheme, both through the numeric tower (see below) and R6RS, have single
inheritance. I do not like inheritance: Rust (which inspired me to write
this) does not have inheritance at all.
Combining subtype inheritance (even when restricted to single inheritance)
with scoping introduces a form of the diamond problem. For example:
imagine if type `T` has an implementation in global scope, and its
supertype `T'` has an implementation in local scope. Which one should
be used?
SAHP
/ \
T (global) |
\ T' (local)
\ /
\ /
T
SAHPs default to selecting the closest scope. However, an implementation
for a type may be labeled `overridable`, in which case if a more specific
type occurs in a higher scope, that implementation is selected.
### The Numeric Tower
The numeric tower has two conflicts with SAHP:
1. The machine representation of types is what SAHPs dispatch against,
and the numeric tower hides this.
2. Exactness is "orthogonal to the dimension of type" (R7RS).
The exact number types that SAHPs will dispatch against are implementation
defined. They will usually consist of
* [fixnums](https://srfi.schemers.org/srfi-143/),
* bignums,
* [flonums](https://srfi.schemers.org/srfi-144/),
* proper rationals,
* irrationals,
* proper complex numbers.
Notably, exactness *is* decided by type (or more accurately, the machine
representation).
SAHPs dispatch on the following hierarchy of types:
* `exact-integer`
* `exact-rational`
* `real`
* `complex`
* `number`
This probably captures most practical uses of the numeric tower.
## API
A SAHP is a procedure object. There is no portable way to differentiate
between a SAHP and a regular procedure. A SAHP has multiple tables
(some conceptual) where an implementation is looked up. The SAHP will
dispatch on (in order of precedence):
* local scope
* dynamic scope
* global scope
The scope resolution tries to find the most specific implementation in
the closest scope. If the implementation in closest scope is not the
most specific implementation, then:
* If the implementation in closest scope is labeled `overridable`, then
the implementation in the next closest scope is selected, and this
disambiguation process continues again.
* If the implementation in closest scope is not labeled `overridable`,
then it is selected.
The SAHP will raise an error object that satisfies the predicate
`SAHP-implementation-not-found-error?` if no implementation is found.
Multiple SAHPs can share global scope tables and dynamic scope.
The procedures stored in a SAHP must take at least one argument, which
is the argument whose type is dispatched against.
The phrase "the SAHP resolves to `procedure` given `T`" means that
if the SAHP is called with a value as its first argument of type `T`,
it will call `procedure` with all of the arguments passed to it.
### Type Expressions
A type expression is defined as:
* The symbols `*` `boolean`, `char`, `null`, `pair`, `procedure`, `symbol`,
`bytevector`, `eof-object`, `port`, `string`, `vector`,
`exact-integers`, `exact-rationals`, `reals`, `complex`, or `numbers`, or
* the value bound to a name of a record type, or
* any other implementation defined value.
### The Object
(make-new-SAHP)
Create a global SAHP with empty tables. This SAHP does not share memory
with any other SAHP.
(SAHP=? sahp1 sahp2) => boolean?
Returns `#t` if the two SAHPs share the same global SAHP table and
dynamic state. SAHPs that are `SAHP=?` are not necessarily `eqv?`.
### Global Scope
(set-global-SAHP! SAHP type procedure)
or
(set-global-SAHP! SAHP type flag procedure)
The flag can be omitted, or the symbol `overridable`.
Set `SAHP` to resolve to `procedure` given `type` in global scope.
(define-global-SAHP (name (type argument) . arg-rest) body ...)
or
(define-global-SAHP (name (type flag argument) . arg-rest) body ...)
Creates a procedure with the given arguments and body. The SAHP will
resolve to this procedure given `type` in global scope.
The flag can be omitted, or the symbol `overridable`.
### Dynamic Scope
(parameterize-SAHP ((SAHP (type value) ...) ...) body ...)
or
(parameterize-SAHP ((SAHP (type flag value) ...) ...) body ...)
Each `SAHP` must resolve to an SAHP.
Each SAHP will have each `type` under it resolve to `value` in dynamic
scope. These procedures take precedence over global scope procedures.
The SAHPs are the same SAHP in the block in the sense of `eq?`.
The flag can be omitted, or the symbol `overridable`.
### Local Scope
(letrec-SAHP ((SAHP (type type value) ...) ...) body ...)
Each `SAHP` must be an identifier that resolves to a SAHP.
Each SAHP will have each `type` under it resolve to the corresponding
`value` in lexical scope. Each procedure will have the new SAHPs in
scope. These procedures will take precedence over dynamic and global
scope procedures.
The SAHPs will be bound to new SAHP objects that share their global and
dynamic scope with previous SAHP objects. If these SAHPs are passed
to another procedure or stored somewhere, they will keep their local
bindings.
If the SAHPs passed to `letrec-SAHP` had local bindings, then
`letrec-SAHP` will replace old bindings and add new ones without affecting
the previous SAHP object.
The flag can be omitted, or the symbol `overridable`.
## TODO
* Standard SAHP library.
* `if-not-exists` to provide default implementations for specific
types.
|
