wingolog

the good hack

26 July 2009 9:48 PM (hack | eisenstein | mumford | guile | scheme | closures | dybvig | time)

Good evening, internet!

I haven't written in a little while, and I suppose a hack-update is due. So first an overview, then a digression into nargery, then a discussion of what's really on my mind these days: Mumford and Eisenstein.

Hup hup, then!

guile

Guile is now on a monthly release schedule, in the runup to 2.0. We've already made two releases, 1.9.0 and 1.9.1.

The feedback has generally been that it works, that it is faster, but that in a few cases, some old macros have to change. The NEWS describe all the gory details, so I'll spare you them here.

Still though, I'm really proud for what we've been able to do: retrofit a compiler on top of a large base of informally defined interpreter semantics, expressed in code afloat on the internet. It's a pretty momentous refactoring effort.

I spoke at GUADEC briefly about Guile, in the impromptu lightning talk session. The story I really wanted to get out was not the details of Guile's compiler, but that Scheme is just one element of Guile. Elisp can exist there too, and Daniel Kraft's elisp branch seems to really be shaping up.

Of course, that's not to mention Daniel's brainfuck compiler, amusingly already merged as an example:

scheme@(guile-user)> ,L brainfuck
Guile Brainfuck interpreter 1.0 on Guile 1.9.0
Copyright (C) 2001-2008 Free Software Foundation, Inc.

Enter `,help' for help.
brainfuck@(guile-user)> +++ +++ +++ +           initialize counter (cell #0) to 10
... [                       use loop to set the next four cells to 70/100/30/10
...     > +++ +++ +             add  7 to cell #1
...     > +++ +++ +++ +         add 10 to cell #2 
...     > +++                   add  3 to cell #3
...     > +                     add  1 to cell #4
...     <<< < -                 decrement counter (cell #0)
... ]                   
... >++ .                   print 'H'
... >+.                     print 'e'
... +++ +++ +.              print 'l'
... .                       print 'l'
... +++ .                   print 'o'
... >++ .                   print ' '
... <<+ +++ +++ +++ +++ ++. print 'W'
... >.                      print 'o'
... +++ .                   print 'r'
... --- --- .               print 'l'
... --- --- --.             print 'd'
... >+.                     print '!'
... >.                      print '\n'
... 
... ]
Hello World!
brainfuck@(guile-user)>

The example is from wikipedia. You can see that the brainfuck reader actually integrates with readline. Since brainfuck programs are normally terminated by end-of-file, we provide an alternate terminal: if ] (the loop terminator) is seen while not inside a loop, we stop reading the brainfuck expression.

Actually, I have to use a similar trick with the ECMAScript reader -- while the grammar does not require it in all situations, you have to terminate expressions entered at the REPL with a semicolon.

Anyway! Guile progresses apace. My favorite addition from the last release was a set of vector and bytevector instructions to the VM. Probably the biggest effect for existing users is that vector-ref and vector-set have their own VM operations now, and are thus much faster.

But the bit that I like is that there are now VM ops for bytevector refs and sets for packed values: everything from unsigned 8-bit values to 64-bit floats. It should make large-scale data processing feasible within Guile's VM, and it will make native compilation for those operations fairly direct and efficient.

Finally, hackwise, I implemented what Kent Dybvig calls "display closures" for Guile.

Before, all heap-allocated values (values that were captured by other procedures and values that were set!) were allocated in a linear list, and closure creation just mean consing together that list of heap variable state with your program code. You can think of this as a degenerate case of the ribcage strategy.

I guess I should be a little clearer. Consider this function, which should add a common prefix to all strings in a list:

(define (munge-strings list prefix)
  (map (lambda (x)
         (string-append prefix x))
       list))

Semantically, you could identify the variables with numbers and it would be the same:

(define (munge-strings <0,0> <0,1>)
  (map (lambda (<1,0>)
         (string-append <0,1> <1,0>))
       <0,0>))

Here the first index refers to the procedure in which the variable is bound, and the second is the nth variable in that procedure. Well this leads itself to a natural implementation of closures: in the function that is mapped, just capture the environment at that point -- then you can get to prefix just by looking back to the first variable in the 0th frame.

But you can do better than that. A variable that's not referenced in an enclosed lambda can just be allocated on the stack -- so list goes on the stack. prefix stays on the heap, though. And that's where Guile was...

...until I realized, via reading Dybvig's 20-year-old dissertation, that I didn't actually have to have environment structures on the heap at all. Closures could just capture the variables that they need into a vector for their own use.

Shared variables can be copied, there's no problem -- except if those variables are ever set!. So in that case, a condition you can determine lexically, you need to allocate those variables in "boxes". Getting and setting values is indirected through the boxes, but those boxes can live whereever -- on the stack in the function that binds the variables, or in the free variables vectors of closures.

This scheme has the advantage that more values can be allocated on the stack, free variable lookup is O(1), and you don't tie the garbage collector's anthropomorphic hands by holding onto parts of the environment that you don't need.

So that's the novelty for the upcoming 1.9.2 release, slated for 15 August. Then we'll have a 1.9.3 in the following month, and 2.0 in October. Like clockwork :)

like clockwork

Lyn Gerry continues her reading of The Ascent of Humanity on her radio show, Unwelcome Guests. It's fascinating, and challenging.

Charles Eisenstein, the author of The Ascent of Humanity, owes a large debt to Lewis Mumford, a historian of technology -- or "technics", as seems to be his preferred word. Eisenstein quotes Mumford liberally. It is by a happy coincidence that a friend of mine pushed Mumford's Technics and Civilization on me a couple months ago -- in exchange for Expect Resistance -- and it is shaping up to be a great, great work.

Regarding "clockwork", as a phenomenon and as a paradigm, Mumford has this to say:

The clock, moreover, is a piece of power-machinery whose "product" is seconds and minutes: by its essential nature it dissociated time from human events and helped create the belief in an independent world of mathematically measurable sequences: the special world of science. There is relatively little foundation for this belief in common human expreience: throughout the year the days are of uneven duration, and not merely does the relation between day and night steadily change but a slight journey from East to West alters astronomical time by a certain number of minutes. In terms of the human organism itself, mechanical time is even more foreign: while human life has regularities of its own, the beat of the pulse, the breathing of the lungs, these change from hour to hour with mood and action, and in the longer span of days, time is measured not by the calendar but by the events that occupy it. The shepherd measures from the time the ewes lambed; the farmer measures back to the day of sowing or forward to the harvest: if growth has its own duration and regularities, behind it are not simply matter and motion but the facts of development: in short, history.

In Reuleaux's definition, quoted by Mumford, a machine is "a combination of resistant bodies so arranged that by their means the mechanical forces of nature can be compelled to do work accompanied by certain derminant motions." But those bodies need not be mineral in nature; indeed, Mumford identifies the human industrialism necessary for the Great Works of the Pyramids as one of the first steps into the machine age: the reduction of man to the "resistant body" of the machine.

So it's interesting to think about the relationship of timekeeping to the mechanization of the human. The ringing of the bells, whether via water-clock or the dawn's early light on the crier's face, introduced discrete time to humanity, and so human activity began to be fit to those times -- cutting off the legs to to fit the bed, so to speak. Mumford continues:

Abstract time became the new medium of existence. Organic functions themselves were regulated by it: one ate, not upon feeling hungry but when prompted by the clock: one slept, not when one was tired, but when the clock sanctioned it. A generalized time-consciouesness accompanied the wider use of clocks: dissociating time from organic sequences, it became easier for the men of the Renascence to indulge the fantasy of reviving the classic past or of reliving the splendors of antique Roman civilization: the cult of history, appearing first in daily ritual, finally abstracted iself as a special discipline.

I've been having lots of dreams about Namibia recently. A common time reference where I lived there is etango peni: "sun where", literally. It's usually indicated with an outstretched arm pointing to where the sun should be, as in, we'll meet this afternoon when the sun is there.

I guess my concern is, to what extent is our obedience to the clock and to the calendar a life-affirming concern, and on the other hand, to what extent does it reduce us to "resistant bodies"? Do we exist in time, or do we exist in a use/used relationship -- to time, and to those that mark the time?

To tie it back to the more nargy concerns above, I think that time-based releases do have a positive effect on the Guile machine. And the Guile machine is a liberatory one -- in whatever trade, programming or otherwise, we should not grind our grist at the lord's mill.

But the greater questions that Mumford and Eisenstein raise make me wonder further about Guile work, not just relative to other systems, or relative to my desire to hack, but relative to the story of humanity -- Ascent or otherwise -- what does furthering this technology really do for life?

Unfortunately, I have no answers for that one. I'll let the tubes know if I find out. Until then, or likely sooner, happy hacking, for Life!

One response

  1. Aaron Bockover says:

    This is awesome. I love these posts and your passion for languages. Until next time! NC out.

Leave a Reply