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
|
# 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 is difficult in the presence of inheritance (in R6RS,
for instance). It would require either disambiguation or a method
resolution order, which are complicated.
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
I am very conflicted on inheritance for subtypes of a type. The issue
is that combining it 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
There are two reasonable choices: most specific and closest scope. Closest
scope is probably the best option, but in some instances it may not
be enough. One might want to specify a default implementation without
desiring to override all specific implementations of subtypes. This could
be done by giving one the ability to specify how each implementation
should be inherited.
SAHPs currently do not automatically inherit implementations. Records
designed with SAHPs in mind should use composition, not inheritance.
### 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.
An implementation could also have unitful numbers, quarternions, etc.
In order to support the numeric tower, SAHPs define portable sets of
types arranged in a hierarchy of subsets. They are
all-exact-integers
⊆ all-exact-rational
⊆ all-real
⊆ all-complex
⊆ all-number
Type sets are lists that contain other type sets or concrete
types. Defining an implementation against a type set explicitly
defines the type set against all implementations, overriding previous
implementations: hence the prefix `all`. These sets are static.
### What Types are dispatched against?
All fundamental types (pairs, fixnums, vectors, defined record types).
Predicates are not dispatched against because that would make the type
system inefficient. One could force this by putting predicates into the
default implementation of a SAHP.
## 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. In order, the SAHP will
dispatch on (in order of precedence):
* local scope
* dynamic scope
* global scope
* the default implementation.
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, dynamic scope, and default
implementations.
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`, or `vector`, or
* The values of `all-exact-integers`, `all-exact-rationals`,
`all-real`, `all-complex`, and `all-number`, or
* Lists of type expressions, 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-expr procedure procedure)
Set `SAHP` to resolve to `procedure` given `type-expr` in global scope.
(define-global-SAHP (name (type-expr argument) . arg-rest) body ...)
Creates a procedure with the given arguments and body. The SAHP will
resolve to this procedure given `type-expr` in global scope.
### The Default Implementation
(set-default-SAHP! SAHP procedure)
Set `SAHP` to call `procedure`, if called with a type `T` that the SAHP
does not resolve to any procedure in any scope.
(define-default-SAHP (name arguments . arg-rest) body ...)
Creates a procedure with the given arguments and body. The SAHP will
use it as the default implementation.
### Dynamic Scope
(parameterize-SAHP ((SAHP (type-expr value) ...) ...) body ...)
Each `SAHP` must resolve to an SAHP.
Each SAHP will have each `type-expr` 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?`.
### Local Scope
(letrec-SAHP ((SAHP (type-expr value) ...) ...) body ...)
Each `SAHP` must be an identifier that resolves to a SAHP.
Each SAHP will have each `type-expr` 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.
## TODO
* Standard SAHP library.
|
