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
|
# 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.
SAHPs do handle single inheritance[^1], because it is an inherent part
of the numerical tower and R6RS records, and because method dispatch
can be implemented unambiguously. Multiple inheritance has many of
the same issues that multiple dispatch has and is also not included.
Single dispatch and single inheritance work for most other programming
languages, so why not use it in Scheme?
[^1]: SAHPs are based off of Rust traits, which do not allow for
inheritance at all. A more radical design would do away with single
inheritance and subtyping entirely.
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.
## API
A SAHP is a procedure object. There is no portable way to differentiate
between a SAHP and a regular procedure. A SAHP has a
* local scope,
* dynamic scope, and
* global scope
Multiple SAHPs can share global scope tables. 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.
When an implement for a type `T` is added to an SAHP, the implementation
will also be added to every supertype of `T` that does not have an
implementation already. This currently applies to the numerical tower
and can be easily extended to systems with single inheritance like R6RS.
SAHPs do not dispatch against procedures, because that would make dispatch
non-terminating and possibly non-deterministic.
### 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. These SAHPs are not necessarily `eqv?`.
### Global Scope
(set-global-SAHP! SAHP type procedure)
Set `SAHP` to resolve to `procedure` given `type` in global scope.
(define-global-SAHP (name (type 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.
### Dynamic Scope
(parameterize-SAHP ((SAHP (type 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?`.
### Local Scope
(letrec-SAHP ((SAHP (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.
## TODO
* Should there be a way to erase local/dynamic bindings? There would need
to be a way to mark default supertype bindings.
* Standard SAHP library.
|
