dispatch on types with multiple scopes

1 files changed, 147 insertions, 0 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..bb413fd
--- /dev/null
+++ b/README.md
@@ -0,0 +1,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.