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,
• bignums,
• flonums,
• 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. The search process is:

1. Set the current scope to local scope, and set the closest implementation I to nothing.
2. If there are no more scopes to visit, return I.
3. Find an implementation in the current scope.
4. If the implementation is not overridable, return it.
5. If the implementation is overridable, and it is more specific than I, set I to this implementation and continue at 2 with the next scope.
6. If there is no implementation, continue to the next scope.

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.

Flags

Flags are a list of symbols, which may be:

• overridable: See above.

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 number, 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)

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.

flag can be omitted.

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

flag can be omitted.

Local Scope

(letrec-SAHP ((SAHP (type flag 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.

flag can be omitted.

TODO

• Standard SAHP library.
• if-not-exists to provide default implementations for specific types.