Arcadian Visions

Haskell type classes are a very nice take on ad hoc polymorphism. Much like overloading in object oriented languages, type classes provide a mechanism for different implementations of the same conceptual operation to go by the same name.

A main difference is the total separation of interface from state representation. With class-based object orientation, programmers are often encouraged to define some thing, a class, that is a bit of state along with operations for manipulating that state in various ways. At some point, the programmer may want variations of those manipulations, and so can delve into inheritance. If more flexibility is needed (namely, the state representation shouldn’t be inherited), the programmer can turn to interfaces in languages like C#, Java, etc.

Now the programmer can program to the interface, and have wildly different state representations implement that interface. Type classes support that style of development in Haskell, but one can gain some of the same operational benefits by working with Units in PLT Scheme. Since I’ve talked about Units before, let’s just get right into this example of their usage.

Suppose I want to overload arithmetic operators in a very ad hoc way. More specifically, when I define a new data structure I want the freedom to define addition over that data structure such that I can write another function that uses the + operator without worrying about having to call a different + for different data structures. There are many ways of solving this kind of problem, this is but one.

#lang scheme
(require (prefix-in base: (only-in scheme + /)))
(require "typeclass-units.ss")
 
;; A class of things for which addition is defined.
(define-signature addable^ (zero +))
 
;; A class of things for which division is defined.
(define-signature divisible^ (/))
 
;; Standard arithmetic on numbers.
(define-instance (addable^ divisible^) num@
  (define zero 0)
  (define + base:+)
  (define / base:/))
 
;; Addition over strings is defined as string-append.
(define-instance addable^ string@
  (define zero "")
  (define + string-append))
 
;; The "+" function is a generic addition operation.
(define-constrained (+ (addable^) => x y)
  (+ x y))
 
((+ num@) 3 4)              ; Adding numbers
((+ string@) "hi " "there") ; Adding strings
 
;; A helper combinator.
(define (flip f) (λ(x y) (f y x)))
 
;; The definition of the "mean" function requires both addition and division.
(define-constrained (mean (addable^ divisible^) => items)
  (/ (foldl (flip +) zero items) (length items)))
 
;; Computing the mean of a list of numbers.
((mean num@ num@) '(4 5 6))
 
;; Try giving an incompatible instance of divisible^... doesn't work.
((mean string@ num@) '("what " "is " "an average " "string?"))

What’s going on here? Let’s start from near the bottom with the mean function that computes the arithmetic mean (average) of a list of items. In order to write this function the way I have chosen to write it, I require definitions of addition and division for the items in the list. My function is not just,

(define (mean items) ...)

as that implies that the function is defined for any type of items. Instead, I want to let the caller of this function supply me with suitable definitions of addition and division for the items in question. To this end, I define mean to be constrained to the cases where the caller can supply such definitions.

This is all tied together through the Units system. In fact, this usage of Units is quite a bit restricted, but I think the syntax for this simpler usage is commensurately simpler, so perhaps of some use.

To define our interface, we use stock Unit signatures such as,

(define-signature addable^ (zero +))

that says that an addable thing has definitions for an additive identity, zero, and a definition of the + operator. To implement this interface, or define an instance of the type class, we can use a form like,

(define-instance addable^ string@
  (define zero "")
  (define + string-append))

that defines a + operator and a zero for strings which I can use in expressions like,

((+ string@) "hi " "there")

to yield the string "hi there".

Definitions of + and / for numbers are straightforward, but I’m not sure what I would want division over strings to mean, so I haven’t defined it. If I wanted to try computing a mean of a string, I would need to supply an instance definition of divisible^, so I tried giving it one for numbers at the end of that code listing… which didn’t work because the / from num@ doesn’t work for strings.

Let’s say that we’re in a punchy mood and define a “shape” to be anything that has an area,

(define-signature shape^ (area))

We then find ourselves dealing with some joker who gave us an instance like this,

(define-instance shape^ bad@
  (define (area b) "I'm not an area!"))

Clearly, this is not an area.

To stop this sort of thing before it catches on, we can tighten our interface with a contract,

;; Shapes have area
(define-signature shape^
  ((contracted [area (-> any/c number?)])))

Now, when we call the bad@ implementation of area, we get this error before the return value gets back into our code,
(unit bad@) broke the contract (-> any/c number?) on area; expected <number?>, given: "I'm not an area!"

• Instance passing is explicit, putting a burden on the caller of a constrained function.
• The simplified Unit syntax hides the lexical binding of the instance definitions supplied to constrained functions.
• There is no mechanism to implicitly pass supplied instance definitions to constrained functions called by other constrained functions.

This means that the functions that have constraints are, with this implementation, treated as terminal. Dynamic dispatch, as with multi-methods, can offer nicer call-site syntax, but the approach to dynamically binding implementations to identifiers shown here allows for a single resolution of that dispatch to be captured in a closure. If I have a large block of code dependent on some set of signatures, I can provide the relevant implementations and get a specialized closure back. For instance, the expression,

(+ string@)

results in a function for which references to the + function are bound to the implementation defined for strings. This is just the kind of thing that Units excel at, and I hope that the uses shown here can, if nothing else, encourage others to explore specific applications of the power of Units.

The simplest example is one that implements a funny head function for both lists and vectors. The arithmetic example is next up, followed by the much more object oriented shapes example.

The little macros that provide this syntax are defined in the typeclass-units module.

Anthony Programming, Scheme Programming, Scheme, tutorial

After working with modules in a language like Standard ML, modular abstraction in other programming languages can feel somewhat primitive. One sometimes wishes to abstract an inter-module dependency, or, put another way, parameterize a module by the implementation of an interface. In object-oriented terms, this is a functional analogy of programming to an interface. To this end, PLT Scheme provides a mechanism called Units. Unfortunately, I found working through the Guide and Reference (standard documentation) rather hard going as usage is somewhat complicated by the availability of syntax-directed static analysis in some situations but not others. What I really missed in the documentation was a simple, generic example of working with different implementations of one signature. What follows is an example program that demonstrates several variations of just that technique with PLT Scheme 4.1.5. This is by no means a replacement for the Guide or Reference, but instead a supplementary example. One additional note: I am deliberately using several variations of the syntax for working with Units in order to provide examples of a few different styles.

The program we are writing is one that asks the user for his or her name, and then displays a greeting. However, the interface logic doesn’t specify the implementation for either of those actions. In this toy example, the idea is to provide implementations in different human languages. Note that the entire implementation is abstract, not just the string data. So, for example, the action of asking for a name could involve very different dialogues in different implementations (e.g. one question, or a series of questions warming up to asking for a name), or even a network transport layer for interacting with a remote user. The key feature is that the interface logic is entirely parameterized by the two actions I am calling ask-for-name and greet.

Let’s make that parameterization concrete with the file service-sig.ss

;;; The service we are abstracting over is one that provides functions for 
;;; basic user interaction.
#lang scheme
 
(provide service^)
 
(define-signature service^
  (ask-for-name
   greet))

With that signature defined, we can define our user interaction logic. Here is the file interaction.ss.

;;; The interaction logic is dependent on a service for directly interfacing
;;; with the user. In this example, the functions ask-for-name and greet will
;;; be supplied by some unit implementing the service^ signature.
#lang scheme
 
(require "service-sig.ss")
 
(provide user-interface^ interaction@)
 
(define-signature user-interface^
  (prompt-user))
 
(define-unit interaction@
  (import service^)
  (export user-interface^)
  (define (prompt-user)
    (let ((name (ask-for-name)))
      (greet name))))

We’re going to need an implementation of our “service,” so let’s start with an English language version, service-impl1.ss

;;; An English language implementation of the service^ signature.
#lang scheme/unit
 
(require "service-sig.ss")
 
(import)
(export service^)
 
(define (ask-for-name) (printf "What is your name? ") (read-line))
(define (greet name) (printf "Well, hello there, ~a!~n" name))

That’s a lot of foundational work; let’s see how it comes together before going any further. The first version of our program, service-program1.ss

;;; Basic usage of the interaction unit. We supply interaction@ with an 
;;; implemenation of the service^ signature so that we can use it.
#lang scheme
 
(require "service-impl1.ss")
(require "service-impl2.ss")
(require "interaction.ss")
 
;; If we don't want programatic linking, then we can really lean on inference.
;; Change service-impl1@ to service-impl2@ for a different language.
(define-compound-unit/infer my-program
  (import)
  (export user-interface^)
  (link service-impl1@ interaction@)) 
 
;; Brings an implementation of the user-interface^ signature into scope.
(define-values/invoke-unit/infer my-program)
 
;; Kick off the interactive program
(prompt-user)

I’ve snuck in another implementation of our service^ signature. Here is the Spanish language version, service-impl2.ss,

;;; An Spanish language implementation of the service^ signature.
#lang scheme/unit
 
(require "service-sig.ss")
 
(import)
(export service^)
 
(define (ask-for-name) (printf "¿Cómo te llamas? ") (read-line))
(define (greet name) (printf "¡Bueno! ¿Cómo estás, ~a?~n" name))

One can play around with service-program1.ss as indicated in the comments. We have now achieved our goal of writing our program in such a way that we do not need to touch the interaction logic in order to supply different implementations of our service^ signature.

But Units can be taken further! Units are first class in PLT Scheme, so we can work with them at runtime. The requirement that we modify the source of service-program1.ss to change language front-ends feels a bit clumsy, so let’s write a program that will select which implementation to use for itself, service-program2.ss

;;; Units are first class in PLT Scheme, so we can programatically control 
;;; how they are linked together. In this variation, we bind an identifier 
;;; to a particular Unit depending on the user's choice of language. We 
;;; then link the interaction Unit with that new binding in order to 
;;; execute our program.
#lang scheme
 
(require "service-impl1.ss")
(require "service-impl2.ss")
(require "interaction.ss")
(require "service-sig.ss")
 
(printf "Choose your language: (1) English or (2) for Spanish")
(define language (if (regexp-match #px"2" (read-line))
                     'spanish
                     'english))
 
;; If we are willing to bind a temporary at the top-level, then we can 
;; use a define-unit form which will let us take advantage of /infer 
;; forms when using the unit. 
(define-unit-binding impl@ 
  (cond 
    ((eq? language 'english) service-impl1@)
    ((eq? language 'spanish) service-impl2@))
  (import)
  (export service^))
 
(define-compound-unit/infer my-program
  (import)
  (export user-interface^)
  (link impl@ interaction@))
 
;; Brings an implementation of the user-interface^ signature into scope.
(define-values/invoke-unit/infer my-program)
 
;; Kick off the interactive program
(prompt-user)

For one final variation, the top-level binding of impl@ bothers me a bit since it is purely a detail of my-program’s implementation. In service-program3.ss, we move impl@ into my-program’s definition.

;;; We can achieve programatic linking without binding a new identifier at the 
;;; top-level, but this strategy reduces the degree to which the Unit 
;;; system is able to infer imports and exports.
#lang scheme
 
(require "service-impl1.ss")
(require "service-impl2.ss")
(require "interaction.ss")
(require "service-sig.ss")
 
(printf "Choose your language: (1) English or (2) for Spanish")
(define language (if (regexp-match #px"2" (read-line))
                     'spanish
                     'english))
 
;; An example of using first class units. We have to make imports
;; and exports much more explicit since we are not using a top-level 
;; form for binding impl@, our temporary unit.
(define my-program
  (let ((impl@ (cond
                 ((eq? language 'english) service-impl1@)
                 ((eq? language 'spanish) service-impl2@))))
    (compound-unit
     (import)
     (export UI)
     (link (((UI : user-interface^)) interaction@ Lang)
           (((Lang : service^)) impl@)))))
 
;; Brings an implementation of the user-interface^ signature into scope.
(define-values/invoke-unit my-program (import) (export user-interface^))
 
;; Kick off the interactive program
(prompt-user)

All the source files may be found in this archive.

Anthony Programming, Scheme Programming, Scheme, tutorial