Second ThiNG spike
Mon 17 Oct 2005 11:08 BST
Over the weekend I built a second experimental implementation1 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?
-
The first experimental implementation was pretty much a pure-functional dialect of Slate, with ML-style reference cells (sparsely used). The system grew to the point where it could support an SDL interface and multiple socket-based tty consoles, and then I decided I’d learnt enough and it was time to start again. ↩
