Design Problems in ThiNG (eighty-twenty news)

At the moment, I’ve three main problems in the work I’m doing designing ThiNG: syntax, semantics, and macros. (Doesn’t leave much, does it?) I’ll cover the syntactic and semantic problems tonight — my thinking on macros is much too fuzzy to write down at the moment.

Syntax

I’m leaning toward a concrete syntax that, like Smalltalk and Slate, makes message-sending the only concise operation, leaving application in particular as almost second-class. Since I expect message sending to make up a much larger fraction of code than raw application, it seems sensible to optimise for that case. Arranging things this way means we can avoid a lot of #quoting.

Message sends through the dynamic-dispatcher (arrows, ==>, read more-or-less as “desugars to”):

exp1, exp2            ==>   (0: exp1 1: exp2)
exp1 + exp2           ==>   (0: exp1 #(+): exp2)
exp1 selector         ==>   (#selector: exp1)
selector: exp1        ==>   (selector: exp1)            "a problem case"
exp1 selector: exp2   ==>   (0: exp1 selector: exp2)    "the same case"

In-place literal object construction:

[exp1, exp2]          ==>   [0: exp1 1: exp2]
[exp1 + exp2]         ==>   [0: exp1 #(+): exp2]
[exp1 selector]       ==>   [#selector: exp1]
[selector: exp1]      ==>   [selector: exp1]            "NOT a problem case"
[exp1 selector: exp2] ==>   [0: exp1 selector: exp2]    "illegal because ambiguous"

Quoting (since quotation could be implemented as a macro, this will need to become more scheme-like in terms of tying in with macro (and perhaps regular application) syntax):
```
# stx
```

Application:

exp1 $ exp2           ==>   (exp1 $ exp2)

The “data” equivalent of application (see also the “semantics” section below):
```
[exp1 $ exp2]         ==>   [exp1 $ exp2]
```

The “problem case” above is interesting: in Smalltalk and Slate, selectors, for instance #foo:bar:, are written foo: 1 bar: 2 when they’re used to send a message. The quoting of foo and bar is implicit — those tokens can’t be interpreted as variable references or variable bindings. In ThiNG, on the other hand, the identity function is [x:x], with the x on the left-hand-side of the colon a variable binding rather than a literal symbol to be used in pattern matching. If I wanted to instead produce an object that responded with some value when sent a literal message #x, I’d have to quote the x in the pattern thus: [#x:x].

When I’m sending a message through the dynamic-dispatcher, for instance (foo: 1 bar: 2), what happens under the hood is something like

currentContext $ [foo: 1 bar: 2]

at which point the problem becomes apparent. Both foo and bar occur as variable bindings - not as literal symbols! What’s intended is

currentContext $ [#foo: 1 #bar: 2]

On the other hand, if a user wrote [zot: 3] instead of (zot: 3), then I’d expect no such implicit quoting to happen.

Thinking about what Scheme might be like if it had more than the limited notion of pattern matching it has (see these two threads), we end up in a similar situation:

(lambda (x y) (+ x y))    ;; bind two variables
(lambda ('x y) ...)       ;; require first argument to be symbol x,
                          ;; and bind second argument

I think the solution of having implicit quoting in the syntactic context of message dispatch (round parens, rather than square brackets) is acceptable, because it is very seldom that one will want to send a message to the current context where the message needs to bind a variable, and should one want to do that, it is still possible using the explicit currentContext $ myMessage syntax above. (Caveat: I’m still uncertain about the best way of getting hold of the current context.)

Semantics

At present, matching the value [#x: 1 #y: 2] against the pattern [] will succeed, since the empty pattern places no requirements on its value. This is fine, except that it makes it impossible to introduce pattern-matching based branching!

The problem is this: Assume the existence of the empty object, and objects constructed from other objects, and nothing else. No symbols, integers, or other literals. With these ingredients, we can produce values such as

[]
[ []      : []      ]
[ []      : [[]:[]] ]
[ [[]:[]] : []      ]
[ [[]:[]] : [[]:[]] ]

etc. The problem is that because there is no ordering between clauses within an object/pattern definition, and because patterns within an object must be nonoverlapping, and because [] matches anything (it’s actually equivalent to discard!), we cannot use pattern-matching to distinguish reliably between any two of the values above.

Take, for instance, the pattern

[           []: a     [[]: []]: b ]

This can be equivalently written

[     [[]: []]: b           []: a ]

Now, when applied to a value [], obviously only the clause resulting in a will match, since the guard on the b clause places requirements on the value that it cannot satisfy. When applied to [[]: []], however, we have a problem, since both guards match — [], as a pattern, places no requirements on its argument at all!

When all we have is the empty object and objects constructed from it, we cannot define non-overlapping patterns. We can fix this in (at least) two ways: we can let clauses within an object be ordered, trying to match the leftmost first, for instance, or we can introduce some other kind of distinction that pattern-matching can get a grip on. I want to keep clauses unordered, for reasons involving method dispatch that I’ve not fully worked out yet, which leaves the introduction of a further distinction.

Fortunately, there is one piece of aggregate syntax that we need for other purposes, which can be used here without confusion: the syntax for application (more generally, without interpretation, simply syntax for pairs, analogous to Scheme’s (x . y)). When interpreted as code, it means application; when interpreted as data, I’m experimenting with the idea of making it mean extension. Assume, for the moment, that infix $ is the concrete syntax for application. Then a $ b means, if interpreted as code, “send the contents of variable b as a message to the receiver denoted by variable a”; and if interpreted as data, (loosely) “extend a with the clauses from b, searching a only if a search within b fails”.

We can then use pattern-matching to distinguish between

([] $  []) $ []          "left-heavy, a.k.a. left"
 [] $ ([]  $ [])         "right-heavy, a.k.a. right"

Now that we have a distinction we can make, we can define structures akin to booleans, natural numbers, characters, and symbols: all the literals we need for working with program representations.

(Pseudocode - I still need to work out how to integrate proper macros)

Define F = ([]$[])$[]
Define T = []$([]$[])

Define Nil = F
Define Cons(a, b) = [ T: a F: b ]

Define Zero = Nil (= F)
Define X * 2 + Y = Cons(Y, X), where X is a number and Y is either
  T for a one-bit, or F for a zero-bit

thus 5 = Cons(T, Cons(F, Cons(T, Nil)))
 and 2 = Cons(F, Cons(T, Nil))
       = [ T:F F:[ T:T F:F ] ]
       = [ ([]$([]$[])):(([]$[])$[])
           (([]$[])$[]):[ ([]$([]$[])):([]$([]$[]))
                          (([]$[])$[]):(([]$[])$[]) ] ]

Define a unicode character to be its codepoint as a number
Define a symbol to be a list of characters

Thus: #x = Cons('x', Nil)
         = Cons(120, Nil)
         = Cons(Cons(F, Cons(F, Cons(F, Cons(T,
                     Cons(T, Cons(T, Cons(T, Nil))))))),
                Nil)
           (etc.)

The naive encoding given above isn’t one that would be useful in a real implementation. For a start, it’d be very inefficient, so meta-level objects would probably be used directly instead; and also, even if that weren’t the case, a more realistic encoding would involve higher-level constructs, and wouldn’t be built so directly on primitive patterns of $. For instance, symbols might be represented as a stream of characters, with [#first: 'x' #rest: #nil], instead of the very low-level markers used above. (Although that particular choice of encoding opens up another can of worms: recursive data-structures!)

Note that I’m still working out the precise meaning of $ when interpreted as extension: for instance, when should the extension be visible as an extension, and when should it fade into the background, acting as if the compound object it produces is a simple object?