Design Problems in ThiNG
Thu 24 Nov 2005 21:20 GMT
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?
