eighty-twenty

Over the weekend I built a second experimental implementation¹ of ThiNG (older articles: 1, 2), a simple normal-order pattern-matching-based evaluator with a parser built out of packrat parsing combinators and my hacked-on version of Dorai Sitaram’s pregexp library.

I’ve chosen to view functions and records/objects exactly the same way: as pattern-matching message-dispatchers. Here are a few expressions, to give some feel for the language:

"This is a comment, just as in Smalltalk."

[x: x]              "This is the identity function."
[x: x] 123          "This is the identity function applied to the literal integer 123."

"This function takes a 2-tuple, and returns the tuple with its elements swapped."
[[x, y]: [y, x]]

"This is a sketch of a mapping function."
define map [
  (f Nil)           : Nil
  (f [Hd: h Tl: t]) : [Hd: f h Tl: map f t]
]

Note that objects ([Key: value Key: value ...]) are the same as functions ([Pattern: expression Pattern: expression ...]) since (1) the language is lazy, and (2) atoms (keys) are just special-cases of patterns.

I noticed an interesting thing while I was implementing pattern matching. Consider the pattern [Hd: h Tl: t]. The idea is that it should match an object that can receive Hd or Tl as arguments, and bind the variables h and t respectively to the results of applying the object to those arguments. That means that when function/object syntax occurs in value context, it is interpreted as [pattern: value pattern: value ...], but (and this is the interesting bit) in pattern context, it is interpreted as [value: pattern value: pattern ...].

When a pattern [X: v] is being matched against some function, perhaps [X: 1 Y: 2], we see:

    [[X: v]: v] [X: 1 Y: 2]
--> let v = ([X: 1 Y: 2] X) in v
--> let v = 1 in v
--> 1

A slightly more complex example:

    [[[X: 123]: [v, w]]: v] [[X: n]: [n * 2, n * 3]]
--> let [v, w] = ([[X: n]: [n * 2, n * 3]] [X: 123]) in v
--> let [v, w] = [123 * 2, 123 * 3] in v
--> 123 * 2
--> 246

Variable references on the left-hand-side of a colon in value context are binding occurrences, and on the right-hand-side in value context are referencing occurrences; but in pattern context this is reversed, with variables on the left-hand-side of a colon being references and on the right-hand-side being binders. An interesting question about the scope of variable references inside patterns arises: what should their scope be, considering that functions/objects do not have a defined ordering on their pattern-matching clauses?