eighty-twenty

I’ve finally gotten around to moving many of our TLA archives over to Darcs. I simply sealed the TLA versions and imported the sealed snapshot into Darcs, without transferring the history.

The main public projects I’ve darcsified are chicken-sdl and gyre (which is the tool we use to publish this site).

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?

I started this afternoon wanting to get some hacking done on our Jukebox code, which is written using MzScheme’s web-server, but I’ve been pretty thoroughly distracted: first by the notion of using postgresql instead of flat-files for the Jukebox database, leading to my earlier scheme-pg post, and then by the desire to move the 8020 site over to darcs from tla, which led to exploring a chain of recursive dependencies. The arch2darcs program requires the missingh library, which in turn needs Cabal; so I decided the path of least resistance was upgrading to ghc 6.4.1, which seems to involve building from source when working on MacOS X. The build somehow caused make to spin endlessly (or at least it was giving no visible signs of progress), and I’ve given up on the whole line of investigation and am going back to the relative safety of working on the Jukebox itself.

So back to the Jukebox: over the last three weeks I’ve had an opportunity to teach myself basic JavaScript and AJAX techniques. Paul’s new Jukebox code uses nevow’s “livepage.py” features, which make a great substrate for a good Jukebox user-interface, with queue- and volume-updates broadcast to connected clients, and I’m thinking of adapting the existing Jukebox to do something similar using my new JavaScript skills.

I’ve just finished taking scheme-pg version 0.4.0, which is intended for MzScheme version 299.30, and updating it (1) so that it builds on MacOS X, thanks to Geoffrey Knauth’s patches (slightly edited to undo some kind of whitespace mangling probably introduced by the HTML mailing-list archiver); and (2) so that it builds with MzScheme v299.400. The only change to the Scheme code is in sql.ss — MzScheme v299.400 seems to have sprouted versions of string-upcase, string-titlecase, and string-downcase that conflict with SRFI-13’s versions of the same procedures.

My revised scheme-pg package is available at http://www.eighty-twenty.org/~tonyg/Darcs/scheme-pg/. That’s both a browseable snapshot, and a darcs repository that you can retrieve with

darcs get http://www.eighty-twenty.org/~tonyg/Darcs/scheme-pg/

After an appallingly long delay (longer than two months!), during which I fretted about the difficulty of fixing my broken laptop (but also learned to ride a motorcycle in my vastly expanded free time), I finally caved in and found a local repair shop (warning: link will resize your window) who would take the case. They did a great job of soldering a new (ad-hoc) connector to the motherboard for me. The power button worked fine when the machine was returned to me.

Unfortunately, I’d broken the keyboard’s ribbon-connector when I’d been taking the thing to pieces and putting it back together again, and the repair outfit had done the best they could with the broken cable I’d left them. Only about a third of the keys were working, so I called up the repair shop and ordered a new keyboard, which arrived the next business day. After all my experience taking the damned thing to pieces, I now rate myself at such a basic job as PowerBook keyboard replacement, so I opted to do it myself, and after an embarrassing false start, having forgotten to remove the remnants of the old broken connector from the socket on the motherboard, the new keyboard is installed and working perfectly.

Um, we now return you to your regularly scheduled 8020.

We’ve just set up a page for StoJ at lshift.net, subsuming the previous two stories about StoJ and providing a link to a running implementation that can be tried out over the web.

On Sunday I replaced the hard disk in my powerbook, according to the instructions here. Everything went well up to

Pull them out very carefully, as there are very thin cables on the connectors.

It turns out that there are very thin cables on the connectors. Now, I had the good fortune not to break any of these thin cables. What I did end up doing was accidentally removing the entire power connector socket from the motherboard. This was far, far easier than it should have been:

1. The solder holding the socket to the motherboard was bad, and the socket was very loose to begin with; and

2. The plug inserted into the socket was jammed tight. No force on Earth was going to separate that plug from its socket. (After it was thoroughly removed from the mainboard, I figured there was no point in being delicate, so took a couple of pairs of pliers to it to try to get the plug and socket separated. No luck. It may as well be glued shut!)

In desperation I googled around trying to find something to avoid consigning the whole machine to the tip. I found this, a more professional (and slightly more accurate) version of the same hard-disk replacement instructions. Note particularly the warning on this page,

The cables you’re about to remove are very fragile - do not pull directly on the wires. Instead, try to pry up the connector directly, using your fingernails or a small flathead screwdriver if necessary.

Yeah, no kidding.

So, now I have a Powerbook, with a brand-new working disk, that I can’t switch on — at least not while the keyboard is connected. Shorting the traces on the motherboard with a screwdriver caused it to power up, boot correctly, and happily wait for a login from the non-connected keyboard, but I don’t really want to try my luck by turning it on and then reconnecting the keyboard while it’s running (and never switching it off again). Neither are my soldering skills good enough to attempt soldering a new connector onto the (very small) traces on the circuitboard. I guess my options are either find a soldering expert, or discover some way of switching the machine on without using the power button.

In hindsight, what I should have done (and this could be added as a hint to the two how-to pages I linked to above) is to cut the power wires to avoid having to pull out the plug in the first place. Once the hard-disk was replaced, it would have been a simple thing to solder the wires together again, or to add a simple in-line jumper to allow future removals of the top panel.

This afternoon I implemented a simple partial evaluator for a Scheme-like language, based on the paper “Partial Evaluator as a Compiler for Reflective Languages” (Asai, Masuhara, Matsuoka and Yonezawa, 1995). So far I’ve restricted myself to an IO-free, side-effect free language, but by using the notion of preactions I ought to easily be able to add support for IO. I’d like to explore extending the simple system I have now to cope with the Composable Memory Transactions of Harris et al instead of supporting Scheme’s destructive updates.

The addition of pattern-matching data-destructuring will help the partial evaluator out, too, in the same way it makes dealing with primitive data easier for the Spineless Tagless G-Machine (see section 4.7). For example, using the partial evaluator to specialize the expression

(fold + 0 a)

I currently get

(letrec ((g17 (lambda (x acc)
                (if (null? x)
                  acc
                  (GOTO g17
                        (if (pair? x)
                          (PRIMcdr x)
                          (error '"Not a pair in cdr" x))
                        (+ (if (pair? x)
                             (PRIMcar x)
                             (error '"Not a pair in car" x))
                           acc))))))
  (g17 a '0))

(Ignore the strange GOTO syntax — I’m also experimenting with identifying the places I can transform recursive procedures into iterative loops.) Note that the type test (pair? x) is repeated twice. If some kind of match clause were used instead, we would see the test lifted to wrap the (GOTO g17 ...) expression, leaving us with something more like

(letrec ((g17 (lambda (x acc)
                (if (null? x)
                  acc
                  (if (pair? x)
                      (GOTO g17 (PRIMcdr x) (+ (PRIMcar x) acc))
                      (error '"Not a pair in match" x))))))
  (g17 a '0))

which, when compiled, is about as efficient as you will get with a statically compiled Scheme. Lots of the optimizations developed in the Self system apply to dynamically compiled variants, of course, potentially leading to further efficiencies.

On this page about syntactic closures, we see the definition of an anaphoric-if macro that doesn’t transmit the “it” binding to the alternative clause — just to the consequent. This is pretty sophisticated. I immediately began to think about how you could do the same with syntax-case (as clearly others had before me) and it turns out to actually be easier. The only real downside is the introduction of another binding — but of course the mythical Sufficiently Smart Compiler will optimise that away immediately anyway.

"Release early, release often," they say. In this spirit, another release of Chicken Scheme bindings for Cairo is available in our 2005 archive.

The egg file is available in releases.

2005-01-06 18:15:03 GMT Michael Bridgen <mikeb@lshift.net>      patch-8

    Summary:
      Added text and font extents
    Revision:
      chicken-cairo--dev--0.1--patch-8

    - cairo_text_extents_t and cairo_font_extents_t types
      These are not returned from a function, so we have to allocate
      them as a (GC-able) byte vector and make C think it's a spot of
      memory.
    - Functions for determining the extents of text and fonts.
    - Updated example



2004-12-04 17:52:21 GMT Tony Garnock-Jones <tonyg@lshift.net>   patch-7

    Summary:
      Adapt to chicken-sdl's recent case changes, and upcase the cairo binding too
    Revision:
      chicken-cairo--dev--0.1--patch-7

    A few constants changed to UPPER_CASE, both references to SDL
    constants, and the flags defined in cairo.scm. Also removed test-cairo
    from the Makefile - it doesn't need to be compiled now that we have
    sdl-csi.


2004-11-30 00:40:37 GMT Michael Bridgen <mikeb@squaremobius.net>        patch-6

    Summary:
      Font and text rendering
    Revision:
      chicken-cairo--dev--0.1--patch-6

    Just a start on these -- enough to see something painted, which is exciting.


2004-11-17 19:40:06 GMT Tony Garnock-Jones <tonyg@kcbbs.gen.nz> patch-5

    Summary:
      cairo.setup file, to make 'make install' (and the egg) work
    Revision:
      chicken-cairo--dev--0.1--patch-5



2004-11-15 22:33:03 GMT Michael Bridgen <mikeb@squaremobius.net>        patch-4

    Summary:
      Query functions
    Revision:
      chicken-cairo--dev--0.1--patch-4

    Might come in handy ('specially alpha)


2004-11-15 14:02:26 GMT Michael Bridgen <mikeb@squaremobius.net>        patch-3

    Summary:
      Matrix operations (untested)
    Revision:
      chicken-cairo--dev--0.1--patch-3

    Added the cairo_matrix_* functions -- untested, except for the
    compilation unit test.

    Just a bunch of typing really.


2004-11-11 00:19:12 GMT Michael Bridgen <mikeb@squaremobius.net>        patch-2

    Summary:
      Some documentation and decorations
    Revision:
      chicken-cairo--dev--0.1--patch-2

    Added some documentation regarding obscure/non-obvious things;
    divided into sets of functions with headers for navigation.