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

Units in PLT Scheme offer great promise in the area of parameterizing modular code. Rather than lean on require forms (or imports in other languages) for bringing identifier bindings into scope, Units offer programmatic parameterization. Instead of editing the source code of a module that depends on some other code, one can provide that parameter at, or close to, the ultimate use site of the fully realized Unit (perhaps in a module dedicated specifically to wiring together the components of an application). However, the reality isn’t always characterized by blue skies and smooth sailing. One area that has often bothered me is that if I create a Unit foo that depends on some unit exporting a signature setup^ (i.e. foo’s setup), the process of invoking foo can be somewhat cumbersome.

More specifically, I might have some unit g that exports the setup^ signature, so how do I go about invoking foo with g as a parameter? It sounds like I want something that looks like (foo g), but perhaps that’s not quite right since we often want the invocation of a Unit to add bindings to the caller’s lexical context. This explains why Unit invocation is actually done by forms such as define-values/invoke-unit or define-values/invoke-unit/infer. An emerging theme is that these are rather long names! To make matters worse, the /infer variants of Unit functions require that argument identifiers be bound by forms like define-unit. But that is a serious limitation, as illustrated in an earlier post.

If we set aside the /infer functionality, then define-values/invoke-unit itself leaves a bit to be desired since it requires explicit import and export annotations. But before we can even call define-values/invoke-unit we must link the Unit exporting setup^ to the Unit importing it, in our case, foo. This requires the creation of a compound-unit that specifies the necessary linking. Unfortunately, while that syntax is powerfully expressive, it is also somewhat scary compared to the initial hope for invocation syntax looking like (foo g).

To this end, I have written up several options for our example Unit invocation scenario. Each option may be uncommented (one at a time), and the entire module evaluated to see that bar is appropriately bound. The idea in these examples is that any helper functionality can be put into another module, while each Option represents a possible call-site syntax. The in-line unit expressions are also likely to be pulled in from elsewhere (e.g. one may have several back-end service providers expressed as Units that can be supplied to a client of any service exporting a particular signature).

#lang scheme
 
(define-signature setup^ (baz))
(define-signature foo^ (bar))
(define-unit foo@
  (import setup^)
  (export foo^)
  (define bar (baz 2)))
 
;; Option 1
;; Put the setup requirements into the current namespace so that the 
;; import binding can be inferred from context.
;(define (baz x) (+ x 40))
;(define-values/invoke-unit/infer foo@)
 
;; Option 2
;; Manually create a unit to provide setup^ and link it to foo@ before 
;; invoking the compound unit to get the desired bar binding.
;(define-values/invoke-unit 
;  (compound-unit
;    (import)
;    (export Foo)
;    (link (((Setup : setup^)) (unit (import) 
;                                    (export setup^)
;                                    (define (baz x) (+ x 40))))
;          (((Foo : foo^)) foo@ Setup)))
;  (import)
;  (export foo^))
 
 
;; Use a helper function to do the linking. The helper function can live in 
;; another module.
(define (init-setup setup)
  (compound-unit
    (import)
    (export Foo)
    (link (((Setup : setup^)) setup)
          (((Foo : foo^)) foo@ Setup))))
 
;; Option 3
;; Use the helper function with an explicit define-values/invoke-unit. 
;; This has the benefit of hiding the linking.
;(define-values/invoke-unit
;  (init-setup (unit (import) (export setup^) (define (baz x) (+ x 40))))
;  (import)
;  (export foo^))
 
;; A helper macro that can reduce the call site burden to knowing how to 
;; provide the necessary setup^ bindings, but requires neither an empty 
;; (import) nor a mention of the foo^ signature. Thanks to Jon Rafkind.
(define-syntax (mkfoo stx)
  (syntax-case stx ()
    [(_ setup) (syntax-local-introduce
                #'(define-values/invoke-unit 
                    (init-setup setup)
                    (import)
                    (export foo^)))]))
 
;; Option 4
;; Use a macro to completely hide the requirements of using the compound 
;; unit.
;(mkfoo (unit (import) (export setup^) (define (baz x) (+ x 40))))
 
;; Get the caller's lexical context for the generated bindings by using 
;; a provided export signature. Thanks to Matthew Flatt.
(define-syntax mkfoo2
  (syntax-rules ()
    [(_ setup sig) (define-values/invoke-unit
                     (init-setup setup)
                     (import)
                     (export sig))]))
 
;; Option 5
;; Provide the export signature from the caller's context so that bindings 
;; are made in the right context.
;(mkfoo2 (unit (import) (export setup^) (define (baz x) (+ x 40))) foo^)
 
; Make sure we have a binding for bar!
bar

Anthony Programming, Scheme

Apropos of nothing… here are two examples of empty LaTeX files suitable for everyday use (e.g. homework). These templates don’t necessarily conform to any particular standard, but I think they are reasonable.

\documentclass{article}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{float}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage[left=0.75in, top=1in, right=0.75in, bottom=1in]{geometry}
\pagestyle{plain}
\begin{document}
    \rhead{Student Name\\School 101: Homework 1}
    \thispagestyle{fancy}
 
    % The list environment is just to get some vertical spacing
    \list{} \item \endlist
 
    % Let the homework begin!
    \section*{Question 1}
    \subsection*{Part (a)}
    Yes
    \subsection*{Part (b)}
    No
 
    \section*{Question 2}
    Maybe
\end{document}

Looks like this,

A variation with a simpler header,

\documentclass{article}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{float}
\usepackage[left=1in, top=1in, right=1in, bottom=1in]{geometry}
\pagestyle{plain}
\newtheorem{theorem}{Theorem}%[section]
 
\begin{document}
    \begin{flushright}
    Student Name\\School 101
    \end{flushright}
 
    \section*{Exercise 42}
    Eureka!
 
    \begin{theorem}
        \textit{(A useful equivalence)}\\
        $P = NP$
    \end{theorem}
    \begin{proof}
        By inspection.
    \end{proof}
\end{document}

looks like this,

Enjoy!

Anthony Software LaTeX

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

A quick public service note for anyone else trying to install the Image package (1.0.8 was the version I downloaded) with Octave (3.0.3 was the version I had) installed as Octave.app from the Octave Forge page.

I had ImageMagick 6.4.1 installed via fink on OS 10.4.11, but installing the Octave Image package was failing on

mkoctfile __magick_read__.cc

Looking in image-1.0.8/src/Makefile, there is the line

$(MKOCTFILE) $< `Magick++-config --cppflags` `Magick++-config --ldflags`

which, it turns out, needed to be

$(MKOCTFILE) $< `Magick++-config --cppflags` `Magick++-config --ldflags` `Magick++-config --libs`

for me.

Since it took me several hours to sort this all out, I’m putting it here for anyone else having trouble getting the Image package installation to link with ImageMagick.

Anthony Octave, Programming, Software