# 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.