Effort

A student tried very hard to write a koan.

Quoting conundrum

I want to quote Gabriel: “A language should be small enough for a programmer to be able keep all of it in mind when programming.” Or maybe Gabriel and Steele: “A language should be small enough for an average programmer to keep in his head.” Really neither of these is quite right, and I want “A programming language should be small enough to keep in your head.” But how do I credit it?

“A programming language should be small enough ... to keep in [your] head” is clumsy. If I call it “after” someone it sounds like a picture, and “modified from” or “based on” like a program. And which of the authors should I credit?

I'll go with “after Gabriel” since it's close to what I want, and short. But citation was an obstacle, and to others as well. The second paper cited above is unfinished, and much of what remains to do is formal cites. How much communication does the rite of credit stop?

Composition without combinators

There is still far too much functional noise in the two-line combinator samefringe. Here's how I'd really like to write it:

samefringe = (composition (or eq (and (and* consp) ((and (eq car) (samefringe cdr)) rotate-right))))
rotate-right = (while (composition (consp car)) (composition (cons caar (cons cdar cdr))))

Something like this would do it:

(defmacro composition (body)
  (labels ((translate (term)
             (typecase term
               (symbol (if (fboundp term) `#',term term))
               (cons (case (car term)
                       (or `(hor ,@(mapcar #'translate (cdr term))))
                       (and `(hand ,@(mapcar #'translate (cdr term))))
                       (t (cons (if (cddr term) 'h '|.:|) (mapcar #'translate term)))))
               (t `(k ,term)))))
    (translate body)))

This is a language where composition, not application, is the Form Without A Name.

(Edit 6 January: fixed examples.)

Optimizing samefringe

The essence of McCarthy's samefringe is "Two trees have the same fringe if they are eq, or if, when rotated all the way right, they have the same car and their cdrs have the same fringe.". This is points-free, and translates nicely into combinator style.

samefringe = hor eq (hand (and* .: consp) ((hand (eq .: car) (samefringe .: cdr)) .: rotate-right))
rotate-right = while (consp . car) (h cons caar (h cons cdar cdr))

.: is like compose, but wraps the second function around each of the first's arguments. This is an operation I need a lot. h is similar, but wraps a different function around each argument. Both of these need better names. and* is and as a function, and hand and hor are h-like versions. while iterates.

f .: g = λ x y ... -> f (g x) (g y) ...
h e f g ... = λ x y ... -> e (f x) (g y) ...
and* a b ... = (and a b ...)
while test step = named-λ loop init ... -> if (test init ...) (loop (step init ...)) init

If the combinators work on arbitrary numbers of arguments, we get n-ary samefringe for free. Not bad for two lines.

McCarthy's samefringe

Richard Gabriel's article on random ideas vaguely related to parallelism includes McCarthy's clever samefringe, which runs in log space without coroutines. Am I the only person who didn't know about this?

(defun samefringe (tree1 tree2)
  (or (eq tree1 tree2)
      (and (not (atom tree1)) (not (atom tree2))
           (same (gopher tree1) (gopher tree2)))))

(defun same (x y)
  (and (eq (car x) (car y))
       (samefringe (cdr x) (cdr y))))

(defun gopher (tree)
  (cond ((atom (car tree)) tree)
        (t (gopher (cons (caar tree)
                         (cons (cdar tree) 
                               (cdr tree)))))))

Gabriel rightly says “this solution is difficult to understand”, but the problem is in the presentation, not the algorithm. Even McCarthy makes naming mistakes - gopher should be called skew-right. It rotates the tree all the way right, so the first element of the fringe is in the car, and the rest is easy.

What part of "type" don't you understand?

Type is one of the most overloaded words in computer science. It has at least six important senses:

1. The representation of a variable, in low-level languages.
2. The class or constructor of a value, in most dynamically typed languages.
3. Any set of values, in Lisp.
4. A protocol or interface an object implements, in Smalltalk.
5. An intended meaning of values, in static typing.
6. A theorem about a program, in type theory.

Each of these is the one true sense of “type” to some people, and absurd to others, even though the first five are obviously related.

A lot of misunderstandings come from confusion of different senses of “type”. For example, some static typists say “static typechecking eliminates runtime type errors”. If this means “static theorem checking eliminates runtime theorem errors”, it's trivially true. But “runtime type error” usually means a value of the wrong class, and with this interpretation it's blatantly wrong.

My advice is to avoid the word “type” when you want to be understood, unless you know how your audience will interpret it.