eighty-twenty

(Update: Shortly after I posted this, I contacted the working-group chair, and he quickly replied to let me know that the group’s settings have been changed. It’s now possible to subscribe to group activity as a spectator. Posting is still restricted to group members, of course, but now others can follow along, which makes me happy.)

It’s almost impossible to follow the scheme-reports-wg1 Google Group, because

• you can’t join the google-group unless you’re part of the working group itself (no joining as a spectator)
• the interfaces available to non-google-group members are insufficient:
  • the RSS/Atom feeds truncate posts, meaning you have to click through to the google-group webpage for reading threads
  • the thread-reading pages themselves are not easy to catch up on (compare Thunderbird, an NNTP client, or even Google Reader here)
• the volume of the list is very high at the moment.

I’d be happy if there were

• a full-content RSS/Atom feed somewhere (for some reason I don’t trust that the existing feed (or perhaps Google Reader) is doing well in keeping posts in chronological order, either); or,
• an NNTP feed of the group (!); or,
• a regular mailman-style mailing list for the group.

The current setup really doesn’t work well for me at all, which is disappointing, as lots of the discussions I’ve overcome the awkwardness of the interface to read are really very interesting.

I’ve just finished reading “Xoc, an Extension-Oriented Compiler for Systems Programming”, by Russ Cox, Tom Bergany, Austin T. Clements, Frans Kaashoek, and Eddie Kohlery. It’s a description of an interesting approach to extensible compilation, for C in this case, that refines a lot of ideas that have been explored previously, bringing them together in a more compositional style than previous extensible compilers have managed to achieve.

One of the key themes in the paper is how to control extension visibility. They describe a couple of approaches they take: one, a type system used to ensure that extensions to abstract syntax are only visible to other extensions when those extensions explicitly declare knowledge of them; and two, an approach from Warth et al.’s “Statically scoped object adaptation with expanders” paper for controlling visibility of extensions to core data structures. I wonder if the latter is used to underpin the former at all.

Regarding the type system approach they take, it’s interesting how it lets the extension writer provide analyses directly in terms of extension abstract syntax, rather than forcing translation to a core language before performing any analysis. We did the latter in Highwire, and the error messages referred to core-language constructs which didn’t map well to source-language syntax: the user was forced to unexpand the macro in their heads to make sense of the output of the compiler. The paper refers to this problem in section 5.2, where the authors write “Since macros cannot access compiler internals, they typically do not even type check their arguments, producing cryptic errors when invoked incorrectly.”

Their compiler, xoc, is a source-to-source translator at the moment, which means it’s not integrated with code generation and backend optimisations and rewrites. It’d be fascinating to build a complete compiler in this style. It’d also be neat to relate this approach to extensible semantics. At the moment the extensions look quite ad-hoc. How could this framework be used, for example, to extend Scheme or ML, where there’s a real semantics underneath it?

One nice feature of xoc is that it tries to preserve hygiene during rewriting. I’m curious as to whether it preserves hygiene to the degree that, say, syntax-case does; their description of the feature was a bit terse for me to be able to tell. In particular I’m interested in how it treats keywords, and where “fresh names” come in to the picture; the paper speaks simply of the code emitter renaming variables “when two distinct variables share a name”.

They use a GLR parser for converting concrete syntax to abstract syntax. One of the benefits of this is its ability to deal with ambiguity, which they exploit in a couple of ways, most ingeniously in their approach to type inference (if you like) for syntax pattern variables. I’d like to learn more about how xoc computes the type of a syntax pattern variable; I wonder if a similar system could be ginned up for use with OMeta?

The laziness of most of xoc’s attribute computations is rather nifty. Code generated relatively late in a compilation, when earlier passes are complete for the rest of the code, can have necessary information filled in lazily on demand, running just those parts of the previous analyses that are required.

I’d like to see some of the pattern-matching and reconstruction features of xoc employed in the context of general purpose computing. It seems to me that using a GLR parser the way they do could effectively provide concrete domain-specific syntax for algebraic data types, not just abstract syntax trees. (The question arises: when is an AST an ADT? Always?) Being able to cons up syntax for new types as easily as Haskell and ML cons up the types themselves seems like a win it’s worth experimenting with. OMeta goes a step in this direction; I hope to explore it myself sometime soon.

This article is an excellent, excellent introduction to Git. It covers the low-level basics, which are much simpler and more elegant than you might be expecting¹, and then reaches up to the less elegant but very powerful world of the Git user interface. Highly recommended.

Most thinking about messaging seems to be framed in terms of process languages, like the π-calculus. In the π-calculus, processes evolve according to an internal clock, the ticks of which correspond to communication events between subprocesses. Many real programming languages based around messaging, like Erlang, are based around similar models, meaning that programmers write programs whose notion of time is implicit, rather than explicit. This can make it difficult to write programs which can reason about differing orders of events or cope with contradictory assertions about the state of the outside world.

An alternative way of dealing with messaging is to take an epistemic reasoning approach closely connected with Functional Reactive Programming (FRP): instead of writing programs that wait for the arrival of specific messages, one at a time, write programs that deal with a queryable monotonically increasing collection of all messages that have arrived or departed so far. Metadata about each message—the sender, the recipient, the time of receipt—are reified as queryable fields attached to each datum in the collection. The state of the program’s world is directly derivable from the program itself and the collection of messages that have been exchanged thus far.

By letting programs step back from the low-level detail of the exchange of messages and take a broader overview of the whole conversation thus far, we let programs behave much more flexibly in the face of such common distributed-systems challenges as lost messages, duplicated messages, out-of-order messages, inconsistent data, and timeouts.

I’ve been off-and-on thinking about these timeless ‘epistemic messaging’ systems for a couple of years now, since a customer project let us investigate their potential suitability for a particular style of long-lived database; while I could write more, and hope to in future, I want to record an observation that occurred to me a couple of days ago about a connection between modeless user interfaces and timeless messaging systems.

In the same way that modal user interfaces constrain the interaction between the user and program into a sequential, question-and-answer style, π-calculus-style programs constrain the interaction between programs in a distributed system into a similar one-thing-at-a-time sequential style, which can lead to programs having a sensitive dependence on message arrival order. Modeless user interfaces, by contrast, make possible a more open-ended, non-linear style of interaction with the user, and epistemic messaging does the same thing for program-to-program interaction: because the state of each program (and thereby its next action) is derived from the collection of messages that have been exchanged, the program can more easily be written to cope with messages arriving in an unusual order. Epistemic-messaging programs can even be written to be able to re-plan (and maybe even re-execute) their actions if received messages were to be permitted to be replaced mid-run.

(Aside: I wonder if there’s a connection here to the Curry-Howard isomorphism? A program operating epistemically over a collection of messages feels like a kind of type/formula, where a similar program in a π-calculus-like system feels like a program/proof.)

Another small thought on the topic of control in distributed systems: One of the first libraries people build on top of object-oriented languages is the observer/observable change-notification pattern. I think this is interesting. Object-oriented languages provide linguistic support for control-flow based on unicast message passing to a single receiver (glossing over the slight variation on the theme provided by multiple-dispatch-based languages), but I’m not aware of languages directly supporting message multicast, broadcast or anycast messaging.

Recently I’ve been teaching myself PowerPC assembly through porting JONESFORTH to PowerPC on Mac OS X. It struck me to run the same little fibonacci-sequence microbenchmark that I ran lo these many years past. The results were interesting:

The hand-coded assembly beats all the other entrants (perhaps unsurprisingly). The naive indirect-threaded FORTH is the fastest interpreted language, merely 5 times slower than fully optimised C.

Here’s the JONESFORTH code:

: FIB DUP 2 >= IF 1- DUP RECURSE SWAP 1- RECURSE + ELSE DROP 1 THEN ;

and here’s the PPC assembly (arg and result in r3):

_SFIB:  cmpwi   r3,2
        bge     1f
        li      r3,1
        blr
1:      mflr    r0
        stw     r0,-4(r1)
        addi    r3,r3,-1
        stwu    r3,-8(r1)
        bl      _SFIB
        lwz     r4,0(r1)
        stw     r3,0(r1)
        addi    r3,r4,-1
        bl      _SFIB
        lwz     r4,0(r1)
        add     r3,r3,r4
        lwz     r0,4(r1)
        addi    r1,r1,8
        mtlr    r0
        blr

Gordon Weakliem writes about literal hash-table syntax, and touches on some of the problems that programmers run in to with floating-point numbers. He writes:

12 years ago, I spent half a day in the debugger trying to figure out why the computer would not believe that 0.0 == 0.0 […]

This triggered two thoughts:

• floating-point numbers in GUIs should be represented differently depending on whether they are an exact representation or an inexact one - which might have saved Gordon’s 12 hours. For instance, inexact representations could be a slightly different shade from exact representations, making the hidden difference between the two zeros apparent at a glance; and

• programming languages must provide reflective access to the representation of floating point numbers, if they are used. As a programmer, I must be able to access the exact bit sequence used to represent the sign, mantissa and exponent of the float.

Regarding reflective access to floats, Java provides floatToIntBits and intBitsToFloat, and C provides (quasi-portable) pointer-based memory-aliasing type-punning to the same effect:

  float f = 1.23;
  int i = *((int *) &f);

Submatching in a pattern, +var@pattern, looks suspiciously similar to recursion in a value, var=value. In each case, we expect a value which is both named and processed, and in each case, a binding is introduced into code. The processing in the submatch case is a further pattern-match operation, and in the recursion case it is a nested evaluation.

The main difference, besides the overall context, between the two forms is the scope of the introduced binding: in the submatch, the pattern variable to the left of the @ sign is bound only in the right-hand-side of the overall pattern, at present, whereas in the recursive value the variable to the left of the = is bound in the right-hand-side of the recursion itself. Another important difference is that in the submatch context, the +var is clearly just a binding form, whereas in the recursion context, var can be seen as acting both as a binding form and a reference to the bound value. Another way of looking at it, though, has the var acting solely as a binding form, with the right-hand-side of the = being the actual result of the expression — the fact that the left and right-hand-sides are equivalent is not relevant, in this interpretation.

What if the two forms were unified, based on their similarities, using either var=pattern-or-value or +var=pattern-or-value for both pieces of syntax? The former seems out-of-place for submatches, since we want to clearly mark bindings that will propagate their bound value into the code on the right-hand-side of an object clause; and the latter seems out-of-place in a recursive value, since +var implies a binding object, which is a first-class datum in ThiNG.

Compare and contrast the following — a string-interleaving routine using the current syntax for both submatch and recursion:

sepList: [+s: loop=[(cons +x +more@(cons _ _)): (x ++ s ++ loop more)
                    (cons +x _): x
                    _: EmptyString]]

The same routine using +var=pattern-or-value for both:

sepList: [+s: +loop=[(cons +x +more=(cons _ _)): (x ++ s ++ loop more)
                     (cons +x _): x
                     _: EmptyString]]

Finally, the same routine using var=pattern-or-value for both:

sepList: [+s: loop=[(cons +x more=(cons _ _)): (x ++ s ++ loop more)
                    (cons +x _): x
                    _: EmptyString]]

Finally, there’s the question of scope: if the same syntax is used for both submatch and for recursion, what happens if we adjust the scoping rules to be as similar as possible? It doesn’t make sense for recursive-value’s scoping rule to be changed to be the same as submatch’s scoping rule — there’s no right-hand-side in a value for the binding to be visible in! — but the other way around might be worth considering: let the binding introduced as part of a submatch be visible as part of the right-hand-side of the submatch. What happens then? Do we end up with infinite patterns? Do we instead end up with a kind of unification-constraint in which an object matching a submatch that is referred to within that same submatch is constrained to have the same recursive topology as the pattern itself?

[Update: Something I forgot to mention — with the scope rule for submatches as it stands, it’s possible to evaluate and then compile patterns ahead of execution time. Changing the scope rule can make compilation of ThiNG code more difficult, forcing the system to be more late-bound than perhaps it needs to be.]

The other day, I noted that my generic-monad-in-Scheme implementation suffered from the flaw of not being able to type-check monad assemblies before any actions had been executed, and that in general such ahead-of-time checking is not possible without abstract interpretation of some kind, because the functional code in the right-hand-side of the bind operator can decide which action to splice into the monad next:

(define (goes-wrong)
  (run-io (mlet* ((val mread))
            (if val ;; if the user entered #f, we break, otherwise we're fine
                (mlet* ((_ (mdisplay "Was true\n"))) (return 'apples))
                'bananas)))) ;; Note: missing "(return ...)"!

Perhaps a partial-evaluator can play the part of a Haskell-type-system-like abstract interpretation well enough to drive the type-safety checks through the code at PE time (loosely equivalent to static-analysis time) for most cases (leaving the remaining cases for runtime-detection, as in the present implementation, and perhaps warning the user)? In order to find out, my next experiment in this direction will be marrying the monad code to the partial-evaluator I implemented some months ago.

I don’t know what crack I was smoking the other day, but my implementation of general monads not only does not have the property I claimed for it, viz. that it provides the same level of type-checking as Haskell ahead of execution-time, but it cannot provide such a level of ahead-of-runtime checking, whether the hosting language is eager or lazy.

To see the first, try the following example:

> (run-io (mlet* ((_ (mdisplay "HERE\n"))
                  (_ sget))
            (return 232)))
HERE
wrong monad-class ((mclass #5(struct:<monad-class> io [...]))
      (m #3(struct:<monad> #5(struct:<monad-class> state [...]) [...]))) 

Note how an action is performed before the type error is detected. In general, it is not possible to detect the type-error ahead of time without abstract interpretation of the level of sophistication that Haskell’s type-checker provides, as the following example demonstrates:

> (define (goes-wrong)
    (run-io (mlet* ((val mread))
              (if val
                  (mlet* ((_ (mdisplay "Was true\n"))) (return 'apples))
                  'bananas)))) ;; Note: missing "(return ...)"!
> (goes-wrong)
#t
Was true
apples
> (goes-wrong)
#f
<monad>-ref: expects type <struct:<monad>> as 1st argument, given: bananas; other arguments were: 0
[...]

The problem is that the system can decide how to continue based on I/O performed at runtime, and so the composition performed by bind cannot be checked until after the left-hand-side has been fully evaluated. [Aside: the <monad>-ref error was a symptom of the unexpected problem described below — now that the code has been fixed, it instead complains “not a monad bananas”, as it should.]

This affects all my monad implementations, not just the IO monad:

> (run-st (mlet* ((a sget)
                  (b (mdisplay "OH NO\n"))
                  (_ (sput 4)))
            (return (+ a 1)))
          2)
OH NO
(3 . 4)

Actually, and this is unexpected ("OH NO" indeed!), here it’s even worse than just not catching the type-error before any actions have executed: it isn’t catching the error at all. Here’s what that mlet* expands into:

(>>= sget
     (lambda (a)
       (>>= (mdisplay "OH NO\n")
            (lambda (b)
              (>>= (sput 4)
                   (lambda (_)
                     (return (+ a 1))))))))

My implementation of >>= isn’t “reaching into the lambda” in the case of the IO monad. [Interlude; sounds of programming from behind the curtain.] The problem was my use of the (bad) “delayed monad” idea in implementing the IO monad — I’ve just replaced that idea with a more explicit representation of a delayed action, and the code now behaves as I expected. How embarrassing! Here’s the trace now that I’ve fixed that problem:

> (mlet* ((a sget)
          (b (mdisplay "OH NO\n"))
          (_ (sput 4)))
    (return (+ a 1)))
#3(struct:<monad> #5(struct:<monad-class> state [...]) [...])

This shows that before we run the monad, it appears to be a well-behaved state monad instance. Running it now causes the error to be detected:

> (run-st (mlet* ((a sget)
                  (b (mdisplay "OH NO\n"))
                  (_ (sput 4)))
            (return (+ a 1)))
          2)
wrong monad-class ((mclass #5(struct:<monad-class> state [...]))
      (m #3(struct:<monad> #5(struct:<monad-class> io [...]) [...]))) 

This demonstrates what I was hoping to show above, before I was derailed by the delayed-monad issue: that the impossibility of using this technique to type-check monad assemblies ahead of any actions being performed applies to all monad kinds, not just the IO monad. Of course, it’s less of a problem for non-side-effecting monads, such as the state monad, since performing an action (in the case immediately above, reading the hidden state variable) in such a monad has no effect on the outside world by the time the type-error is detected.

In conclusion, I was mistaken about Scheme’s ability to achieve the same level of ahead-of-execution type-checking as Haskell manages — I don’t believe it to be possible without essentially Haskell-equivalent abstract-interpretation machinery bolted on to the language. Nonetheless, the library I’ve developed does catch type errors eventually — so long as the faulty code is eventually run! This is no worse than regular dynamically-typed language code, and is still a useful system, so I’m not completely disappointed. I will still be able to use the idea to structure side-effects in ThiNG.