pnkfif

Middle Squares and Big Nums

2011-11-06T17:33:00.000-08:00

No screen shots tonight. But on the semi-bright side, at least this time I am posting something that has to do with TAOCP.

For my second quick experiment to play with the Flash tools, I decided to make a swf that would illustrate the "middle-square" method for pseudo-random sequences of numbers (aka a pseudo-random number generator, or PRNG).

The technique is simple, and aptly named at least if you are used to reading your function compositions as (f ○ g) rather than as the categorical style of (g ; f). Every time you want a new "random" number of let's say 10 digits, you take the previous number N (or the initial seed if you're just starting out), square it (which will yield of number of at most 20 digits, and in fact we'll pad N² out with zeroes so that it is always 20 digits), and then extract the middle 10 digits from that 20 digit N².

It shouldn't take very much code to implement something like this. Except (a ha), a lot of "modern" languages like ActionScript do not have built-in support for arbitrary precision arithmetic. In the particular case of the ECMAscript family, as soon as you get above a certain threshold (usually around 2³⁰ or so, they fall into floating-point mode. That might suffice for a lot of the scripts out there, but it falls down miserably in this case because the majority of the ten digit numbers are obviously larger than 5⋅10⁹ = 5,000,000,000 which is itself larger than 4,294,967,296 = 2³².

So as soon as you want to actually show off Knuth's first example: 5,772,156,649, you discover that you can't use the language's built-in arithmetic to do it.

(And for those of you saying "but it is safe to use floating point to store those ten digit numbers; you get 53 bits of precision in the significand in IEEE 754 floating point": I recommend you go back up and re-read the very first step (or second-word in our ○-composed name). And/or double-check what 2⁵³ is in base-10.

Anyway, that was just a long explanation for why I had to make a quick BigNum class in order to do this task. I wasn't expecting to have to get into BigNum work until I hit Chapter 4 of TAOCP, and I plan to keep the class as minimal as possible (in both performance and features) until I get there.

(I used Emacs htmlize.el to format this code. If I knew how to integrate the CSS it generates into blogspot, I'd have font colors too. But that will have to be a project for another day.)

`BigNum.as` code


package  {
    public class BigNum {
        internal static const bigitLen = 16;
        internal static const base = 10; // Math.pow(2, bigitLen);

        // a base of 10 is *incredibly* inefficient, but it does allow
        // for a very simple toString implementation (and parse as well
        // but lets only put that in if I need to debug)

        public function toString():String {
            // This code *definitely* only works for base == 10

            if (base == 10) {
                var i;
                var r = "";
                var maxNonZeroIdx = 0;
                for (i=0; i < bigits.length; i++) {
                    if (bigits[i] > 0) {
                        maxNonZeroIdx = i;
                    }
                }
                for (i=0; i <= maxNonZeroIdx; i++) {
                    r = bigits[i] + r;
                }
                return r;
            } else {
                throw "unimplemented";
            }
        }

        // AF(this) = (nonNeg?1:-1) * Sum_i{ bigits[i] * base^i }
        private var nonNeg:Boolean;
        private var bigits:Vector.<uint>;

        public function BigNum(num:*=0) {
            nonNeg = true;
            bigits = new Vector.<uint>(1);
            if (num is uint && num < base) {
                bigits[0] = num;
            } else {
                this.parse(String(num));
            }
        }

        // modifies: this
        // effect: sets up this to match input (base 10).
        private function parse(input:String):void
        {
            if (false && base == 10) {
                parse_base10(input);
            } else {
                parse_general(input);
            }
        }

        // modifies: this
        // effect: same as parse(input)
        private function parse_base10(input:String):void
        {
            // This code *definitely* only works for base == 10

            bigits.length = input.length;
            for (var i=0; i < input.length; i++) {
                bigits[input.length - i - 1] = uint(input.charAt(i));
            }
        }

        // modifies: this
        // effect: same as parse(input)
        private function parse_general(input:String):void
        {
            // This code probably works for bases other than 10

            for (var i=0; i < input.length; i++) {
                var amount = uint(input.charAt(i));
                this.mulAndAddInPlace(10, amount);
            }
        }

        // modifies: this
        // effect: this := this*'scalar' + 'carry'
        private function mulAndAddInPlace(scalar:int, carry:int):void
        {
            for (var i=0; i < bigits.length; i++) {
                var a = bigits[i];
                a *= scalar;
                a += carry;
                bigits[i] = a % base;
                carry = (a - (a % base)) / base;
            }
            if (carry > 0) {
                bigits[bigits.length] = carry;
            }
        }

        // modifies: this
        // effect: this := this * 'base'
        private function leftShiftInPlace(amt:uint):void
        {
            for (var i=0; i<amt; i++) {
                bigits.unshift(0);
            }
        }

        private function bigit(idx:uint):uint
        {
            return (idx < bigits.length) ? bigits[idx] : 0;
        }

        public function add(that:BigNum):BigNum {
            // This code may or may not work for bases other than 10

            var r:BigNum = new BigNum;
            var len = Math.max(this.bigits.length, that.bigits.length);
            var carry = 0;
            for (var i=0; i<len; i++) {
                var b = this.bigit(i) + that.bigit(i) + carry;
                r.bigits[i] = b % base;
                carry = (b - (b % base)) / base;
            }
            if (carry > 0) {
                r.bigits[len] = carry;
            }
            return r;
        }

        private function clone():BigNum
        {
            return this.add(new BigNum);
        }

        public function mul(that:BigNum):BigNum {
            // This code may or may not work for bases other than 10

            // for now, multiply the same way you'd do it by hand:
            // by repeated multiply-by-scalar, shift, and sum.
            var accum:BigNum = new BigNum;
            for (var i=0; i<that.bigits.length; i++) {
                var scaled:BigNum = this.clone();
                scaled.mulAndAddInPlace(that.bigits[i], 0);
                scaled.leftShiftInPlace(i);
                accum = accum.add(scaled);
            }
            return accum;
        }
    }

}

Anyway, after the BigNum class done, I whipped up a Flash program that let me interactively input new seeds for such sequences. The first version was somewhat embarrassing, because I insisted on doing everything within the Actions block for the single frame of the SWF movie, rather than using any of the Flash Pro GUI to drag around UI elements.

But at least I had the good sense to factor out the middle square generation code. And then after I had that working acceptably, I was able to go back and experiment with using the Flash Pro GUI to use the built-in UI components more effectively (e.g. so that I could create a scrollable list for the output sequence rather than a non-scrollable label, and so that I could control the number of elements created in the sequence).

It is still not perfect; e.g. it would be better if the sequence were created on the fly in response to the user scrolling down the list. Then there would be no need to impose an a priori limit on the sequence length. But that would require a little bit more revision to the design than I want to undertake at the moment.

Anyway, here are the two versions, presented in three parts: first the middle square generation routine on its own, then the first ugly UI code, and then the better code that presumes that one has used Flash Pro to set up UI components in a sane manner.

Middle Square Generation


function middleSquareSequence(input:String, iters:uint):Vector.<String>
{
    var r:Vector.<String> = new Vector.<String>();
    if (isNaN(Number(input))) {
        r.push(input);
    } else {
        // Illustrate middle-square method for (bad) PRNG
        var digits:uint = input.length;

        // Make digit count even, to simplify definitionn of "middle digits"
        if ((digits % 2) == 1)
            digits = digits + 1;
        var dig2 = uint(digits/2);

        var bn:BigNum = new BigNum(input);
        var s:String = bn.toString();
        while (s.length < digits) {
            s = "0" + s;
        }
        r.push(s);

        for (var i=0; i < iters; i++) {
            var nsqr = bn.mul(bn); // this is <= 2*digits;
            // want the middle digits.
            // Ideally I'd do this via arithmetic, but I don't feel like
            // adding support for such to my hacked up BigNum class at the
            // moment.
            s = nsqr.toString();
            while (s.length < 2*digits) {
                s = "0"+s;
            }
            var sub:String = s.substring(dig2,2*digits-dig2);
            r.push(sub);
            bn = new BigNum(sub);
        }
    }
    return r;
}

Ugly Hacked Up UI Code


import fl.controls.Button;
import fl.controls.TextInput;
import fl.controls.List;
import fl.controls.Label;
import flash.events.MouseEvent;
import fl.controls.NumericStepper;

// ***************************************************************************
// Old hand written code below that did everything without using Flash Pro GUI
// (except for importing components into the SWF).  I.E., this code manually
// creates and positions the UI elements.  Its not really worth the pain for
// one-off scripts like this, especially now that I know how to get
// code-hinting for UI componets by explicitly redeclaring the variables.
// ***************************************************************************

if (true) {
    var b:Button;
    b = new Button;

    // Mutating b/textField doesn't seem to have
    // desirable effects.  The documentation just
    // says its a reference to the Button's internal
    // textfield, which makes me think that this never
    // should have been provided as a mutable property.
    // b.textField = t;

    b.label = "Click"
    // b.setStyle("textFormat", tf);
    // b.width = 400;
    // b.height = 300;
    b.x = 120;
    b.y = 10;
    addChild(b);

    var inp:TextInput;
    inp = new TextInput;
    inp.x = 120;
    inp.y = 40;
    inp.text = "5772156649";
    addChild(inp);

    b.addEventListener(MouseEvent.CLICK,
                       function() {
                           var seq:Vector.<String>;
                           seq = middleSquareSequence(inp.text, 400);
                           l.text = "";
                           for (var i=0; i<seq.length; i++) {
                               l.text += seq[i] + "\n";
                           }
                       });

    var l:Label;
    l = new Label;
    l.x = 220;
    l.y = 10;
    l.height = 400;
    if (true) {
        l.text = "Hi\nworld";
    } else if (false) {
        // (These are some tests of BigNum functionality
        //  I put in as I was getting this going.)
        l.text = (""+new BigNum("1234567890")
                  +"\n" + new BigNum("1234").add(new BigNum("1234"))
                  +"\n" + new BigNum("1234").add(new BigNum("1766"))
                  +"\n" + new BigNum("9999").add(new BigNum("1001"))
                  +"\n" + new BigNum("1000").mul(new BigNum("1000"))
                 );
    }
    l.selectable = true;
    addChild(l);
}

Nicer looking (and shorter) UI code presuming Flash Pro


import fl.controls.Button;
import fl.controls.TextInput;
import fl.controls.List;
import fl.controls.Label;
import flash.events.MouseEvent;
import fl.controls.NumericStepper;

// These are local variable declarations for the UI elements that I added
// manually in Flash Pro.  Apparently the tool is too stupid to know to provide
// code hinting unless I add these declarations (along with the above imports)
// myself.  (Or maybe this is a "feature" rather than a "bug")
var reseedButton:Button;
var seedInput:TextInput;
var outputList:List;
var numItersStepper:NumericStepper;

reseedButton.addEventListener(MouseEvent.CLICK,
  function () {
      outputList.removeAll();
      var seq : Vector.<String>;
      seq = middleSquareSequence(seedInput.text, numItersStepper.value);
      var seen = {};
      var seenRepeat:Boolean = false;
      for (var i=0; i<seq.length; i++) {
          if (seenRepeat || seq[i] in seen) {
              seenRepeat = true;
              outputList.addItem({label:(seq[i]+
                                         " (repeat)")});
          } else {
              outputList.addItem({label:seq[i]});
              seen[seq[i]] = true;
          }
      }
  });

A Bit of Trignometry

2011-11-05T13:31:00.000-07:00

So I wanted to aim small for my initial foray into using Flash Professional to make a small bit of example code for this blog.

(I have done some small proof of concept stuff in Flash Pro and in Flash Builder before, mainly to explore the runtime garbage collector or illustrate short-comings in our ActionScript API's. But none of that has translated over to blog content here before.)

I figure that in general I'll need to be able to render animated text and shapes. Other functionality (mouse event handling, UI elements like buttons or text boxes) can wait for later.

So okay, how about "Hello World," where the text does something interesting. Like rotate 360 degrees in a tight circle around its mid-point; that's the kind of thing that is really easy to show off in DrRacket.

It was easy to get started: a few mouse clicks to select the text tool, create a "Hello World" text object, and make it rotate continuously.

Choose the menu item "File → New..." and choose "ActionScript 3.0" in the New Document dialog window.
Now that you have a fresh blank slate to work with, select the Text tool in the toolbar on the right hand side of the screen:
Create a fresh text object by clicking the Text tool on the white space (the "stage") on the left hand side of the screen:
Create a fresh text object by clicking the Text tool on the white space (the "stage") on the left hand side of the screen:
If you like, you can automatically align the text to sit in the center of the stage, in four clicks: the first to open up the alignment controls, by clicking the "Align" button in the menu bar at the center of the screen, the second to turn on the "Align to stage" option in the alignment controls, and the third and fourth to turn on the "Align vertical center" and "Align horizontal center" options. The latter three steps are illustrated below:
Finally, to make the selected text actually act in a dynamic fashion, double-click one of the premade ActionScript snippets, found in the "Code Snippets" that you can select from that middle menu bar again. For this experiment, I selected the "Rotate Continously" code snippet:
You will probably get a pop-up dialog box saying that this code snippet requires an instance name; just click okay and Flash Pro makes up a name for the text object. And voila:

Except when I tested this (menu item "Control→Test Movie→Test"), I did not get what I expected:

Yes, this text is rotating in a circle... but not around a point in the middle of the text.

The reason is simple: the text object's position is determined relative to the (x,y) coordinate at the upper-left hand corner of the text. When you rotate the text, it rotates around that origin at its upper-left corner, so that corner is what it rotates around.

This discovery turned a somewhat silly test of Flash into a slightly more meaty (though mechanical) puzzle: how do I get the effect I wanted originally.

The answer: Trigonometry! As the rectangle rotates, we also adjust the position of its upper-left corner, moving it in a circle in synchronization with the rotation of the rectange.

(The above picture has flaws; in particular, the line segment r is supposed to end at the center point of the rectangle, but it clearly does not, since the horizontal line going through it is vertically above both the lower-left and the upper-right corners. This should not be possible if that line were truly going through the center of the rectangle. In my defense, this was my first foray into using Adobe Illustrator. I will probably try again later using TikZ/PGF.)

This derivation leads to the following change to the ActionScript code that Flash Pro inserted for us:


textField_1.addEventListener(Event.ENTER_FRAME, fl_RotateContinuously);

var w = this.width;
var h = this.height;
var r = Math.sqrt(w*w/4+h*h/4);
var theta = Math.asin(h/(2*r));
var origin = {x:stage.width/2, y:stage.height/2};

function fl_RotateContinuously(event:Event)
{
   alpha += 0.1;
   var psi = alpha + theta;
   var dx = r * Math.cos(psi);
   var dy = r * Math.sin(psi);
   // trace(w,h,dx,dy);
   textField_1.x = origin.x - dx;
   textField_1.y = origin.y - dy;
   textField_1.rotation = 360*alpha/(2*Math.PI);
}

And, voila, for real this time:

Bonjour de Paris

2011-10-29T11:27:00.001-07:00

I have arrived in Paris! It is great. Stephanie has been posting pictures on her blog.

I had to leave the majority of my library at home, but I did take a special set of textbooks with me: my old editions of TAOCP, all three volumes. I am hoping to work through volumes 2 and 3, and post the results of my experimental implementations here, the same way I posted the code for algorithm 7.2.1.1-W earlier. I have many more languages available at my fingertips now: in addition to the old-standbys, Java, C, and Scheme, I now also have ActionScript, Javascript, and C++. Imight also dabble in a bit of assembly code in x86_64 or ARM from time to time.

At the same time, I am experimenting with alternative tools for authoring blog content. I'm trying to be a good little Adobe employee and try to use our own tools (Dreamweaver in this case) to interface with Blogger. My end goal is to post active Javascript and Flash content on the web, in addtion to the transcripts I post. But that might require I shift over to my personal web server, rather than work through Blogger. We shall see.

from 90sec to 9sec.

2009-08-27T18:37:00.000-07:00

I have been reading Knuth's pre-fascicles from Chapter 7 of TAOCP.

Last night when I transcribed one of the algorithms (7.2.1.1-W) to Scheme code, I got caught up in Knuth's claim that the iterative process described should take "at most a few seconds", yet my first version was taking 90 seconds to run in Larceny. So I started the human iterative process of revising the code, inspecting the compiler output, and doing more runs to figure out where the time was going.

At the end of it, I got the running time down to 9 seconds (from 90; that's a 10x speed-up!) You can shave off a few more seconds by switching to unsafe mode via compiler switches, but it seems like the really important thing was understanding which operations were going to turn into native machine instructions, which ones would turn into millicode invocations in the C runtime, and which ones would turn into Scheme procedure invocations.

(I think 9 qualifies as "a few seconds", especially for a dynamic language like Scheme.)

So here, for your viewing pleasure, is both the first and last versions of the code, along with the log in the comments of the changes I made and what effect they seemed to have.


;; ----------------------------------------------------------------------
;; What is largest set of five letter words connected via single letter 
;; swaps?  To find out, we use specialized representation of sgb-words,
;; where each word is mapped to an index in a bit-table with 2^25 entries
;; (I would represent each bit by a byte for ease of coding, but Larceny
;;  cannot construct objects >= 16 MB, so my hand is forced.)

(define bytevector-bit-ref 
  (lambda (bv k)
    (let ((q (quotient k 8))
          (r (remainder k 8)))
      (fxarithmetic-shift-right
       (fxand (bytevector-u8-ref bv q)
              (fxarithmetic-shift-left 1 r)) r))))

(define bytevector-bit-ref? 
  (lambda (bv k)
    (not (zero? (bytevector-bit-ref bv k)))))

(define bytevector-bit-set! 
  (lambda (bv k bit)
    (let ((q (quotient k 8))
          (r (remainder k 8)))
      (bytevector-u8-set! 
       bv q 
       (fxior (fxand (bytevector-u8-ref bv q)
                     (fxxor #b11111111 (fxarithmetic-shift-left 1 r)))
              (fxarithmetic-shift-left bit r))))))

(define (word->index w)
  (let ((char->num (lambda (c) (- (char->integer c) (char->integer #\a))))
        (offsets (map (lambda (e) (expt 2 e)) '(20 15 10 5 0))))
    (apply + (map * (map char->num (string->list w)) 
                  offsets))))

(define (index->word i)
  (let ((num->char (lambda (n) (integer->char (+ n (char->integer #\a)))))
        (offsets (map (lambda (e) (expt 2 e)) '(20 15 10 5 0))))
    (list->string (map num->char (map (lambda (o) (remainder (quotient i o) (expt 2 5)))
                                      offsets)))))

(define (read-sgb-words file)
  (call-with-input-file file
    (lambda (p)
      (let loop ((words '()))
        (let ((x (read-line p)))
          (cond 
           ((eof-object? x)
            (reverse words))
           (else 
            (loop (cons x words)))))))))

(define (make-sgb-words-table words)
  (let ((table (make-bytevector (quotient (+ (expt 2 25) 7) 8))))
    (for-each (lambda (x) (bytevector-bit-set! table (word->index x) 1))
              words)
    table))

(define words (read-sgb-words "sgb-words.txt"))
(define t (make-sgb-words-table words))

;; This procedure takes 96sec on Chimaera.
;; Knuth says this process should finish in "at most a few seconds"; see below.
(define (find-max-intermix t words)
  (let ((A-best '())
        (l-best 0)
        (wiz (map word->index words))
        (two^25 (expt 2 25))
        (two^20 (expt 2 20))
        (two^15 (expt 2 15))
        (two^10 (expt 2 10))
        (two^5  (expt 2  5)))
    (let loop1 ((w1 wiz))
      (cond 
       ((not (null? w1))
        (let loop2 ((w2 (cdr w1)))
          (cond 
           ((null? w2)
            (loop1 (cdr w1)))
           (else 
            (let* ((w (car w1))
                   (w* (car w2))
                   (z (fxxor w w*))
                   (m (+ two^20 two^15 two^10 two^5 1))
                   (m* (* two^5 m)))
              (cond
               ((not (zero? (fxand (fxxor (fx- z m) z m) m*)))
                (loop2 (cdr w2)))
               (else 
                (let ((m (vector (fxand z (fx- two^5  1))      ; m_0 
                                 (fxand z (fx- two^10 two^5))  ; m_1
                                 (fxand z (fx- two^15 two^10)) ; m_2
                                 (fxand z (fx- two^20 two^15)) ; m_3
                                 (fxand z (fx- two^25 two^20)) ; m_4
                                 )))
                  (let ((l 1) (A (list w)))
                    (let* ((sw (lambda (j) 
                                 (set! w (fxxor w (vector-ref m j)))
                                 (cond ((bytevector-bit-ref? t w)
                                        (set! l (+ l 1))
                                        (set! A (cons w A))))))
                           (swap-0 (lambda () (sw 0)))
                           (swap-1 (lambda () (swap-0) (sw 1) (swap-0)))
                           (swap-2 (lambda () (swap-1) (sw 2) (swap-1)))
                           (swap-3 (lambda () (swap-2) (sw 3) (swap-2)))
                           (swap-4 (lambda () (swap-3) (sw 4) (swap-3))))
                      (swap-4)
                      (cond ((> l l-best)
                             (display A) (newline)
                             (set! l-best l)
                             (set! A-best A))))))
                (loop2 (cdr w2)))))))))))))


;; Knuth says this process should finish in "at most a few seconds" but its 
;; taking Chimaera 96.4sec; lets see if allowing more inlining helps matters...
;; - Using internal define for bytevector-bit-ref and bytevector-bit-ref?
;;   shaved off 6 seconds to 90.1sec
;; - Using macros to define { sw, swap-0, swap-1, swap-2, swap-3, swap-4 }
;;   brings time down to 77.7sec
;; - Using macros to define bytevector-bit-ref and bytevector-bit-ref? 
;;   did not improve the time at all... (but I did not do it properly the first time!)
;; - Lifting the definitions of m and m* did not improve the time.
;; - Replacing the encoding of m_i via a 5-elem vector with explicit
;;   variables { m_0 .. m_4 } may have shaved a fraction of a second off
;;   the time...
;; - Fixing the macro for bytevector-bit-ref and bytevector-bit-ref? did not help.
;; - Replacing fxarithmetic-shift-left and fxarithmetic-shift-right with fxlsh and fxrsh
;;   was huge; brought time down to 40.5sec
;; - Changing encoding of 2^k to thunks rather than let-bound constants did not help anything.
;; - Changing encoding of 2^k to macros rather than thunks did not help anything [[ but I may have been timing the wrong code here ]]
;; - Changing encoding of m and m' to macros rather than let-bound constants did not help anything.
;; 
;;   [[ note on last three items: it looks strongly like Twobit is
;;      reintroducing the let-bindings for temporaries rather than
;;      inline their values in the code, which is interesting.]]
;;   [[ (are fxlsh and friends not interpreted at compile time?) ]]

;; - Manually constant folding fxlsh and friends got down to 39.8sec (maybe not statistically sig delta).
;; - Adding check for bytevector? of t at outset got down to 39.1sec (again maybe not stat sig on own).
;; - Switching to multi-valued fxdiv-and-mod was a terrible idea (x2.5 slowdown)
;; - And even using fxdiv fxmod separately was a terrible idea (x2 slowdown)

;;   [[ We apparently do not have any compiler optimizations for fxquotient and similar; hmm. ]]

;; - Changing the code to use fxrhsl and fxand instead of quotient and remainder
;;   brings running time down to 9sec (from between 37 and 39 seconds; another huge leap!).
 
(define (find-max-intermix.v16 t words)

  (let*-syntax ((bytevector-bit-ref 
                 (syntax-rules () 
                   ((_ bv k)
                    (let ((q (fxrshl k 3))
                          (r (fxand  k #b111)))
                      (fxrsha
                       (fxand (bytevector-u8-ref bv q)
                              (fxlsh 1 r)) r)))))

               (bytevector-bit-ref? 
                (syntax-rules () 
                  ((_ bv k)
                   (not (zero? (bytevector-bit-ref bv k))))))

               (two^25 (syntax-rules () ((_) 33554432)))
               (two^20 (syntax-rules () ((_) 1048576)))
               (two^15 (syntax-rules () ((_) 32768)))
               (two^10 (syntax-rules () ((_) 1024)))
               (two^5  (syntax-rules () ((_) 32)))
               (m      (syntax-rules () ((_) 1082401 )))   ;; (+ (two^20) (two^15) (two^10) (two^5) 1) 
               (m*     (syntax-rules () ((_) 34636832 ))) ;; (* (two^5) (m)))))
               )

 (let* ((A-best '())
        (l-best 0)
        (wiz (map word->index words)))
   (cond 
    ((not (bytevector? t)) (error))
    (else 
    (let loop1 ((w1 wiz))
      (cond 
       ((not (null? w1))
        (let loop2 ((w2 (cdr w1)))
          (cond 
           ((null? w2)
            (loop1 (cdr w1)))
           (else 
            (let* ((w (car w1))
                   (w* (car w2))
                   (z (fxxor w w*)))
              (cond
               ((not (fxzero? (fxand (fxxor (fx- z (m)) z (m)) (m*))))
                (loop2 (cdr w2)))
               (else 
                (let ((m_0 (fxand z (fx- (two^5)  1)))
                      (m_1 (fxand z (fx- (two^10) (two^5))))
                      (m_2 (fxand z (fx- (two^15) (two^10))))
                      (m_3 (fxand z (fx- (two^20) (two^15))))
                      (m_4 (fxand z (fx- (two^25) (two^20)))))
                  (let ((l 1) (A (list w)))
                    (let*-syntax ((upd (syntax-rules ()
                                         ((upd) (cond ((bytevector-bit-ref? t w)
                                                       (set! l (+ l 1))
                                                       (set! A (cons w A)))))))
                                  (sw (syntax-rules ()
                                        ((sw 0) (begin (set! w (fxxor w m_0)) (upd)))
                                        ((sw 1) (begin (set! w (fxxor w m_1)) (upd)))
                                        ((sw 2) (begin (set! w (fxxor w m_2)) (upd)))
                                        ((sw 3) (begin (set! w (fxxor w m_3)) (upd)))
                                        ((sw 4) (begin (set! w (fxxor w m_4)) (upd)))))
                                  (swap-0 (syntax-rules () 
                                            ((_) (sw 0))))
                                  (swap-1 (syntax-rules ()
                                            ((_) (begin (swap-0) (sw 1) (swap-0)))))
                                  (swap-2 (syntax-rules () 
                                            ((_) (begin (swap-1) (sw 2) (swap-1)))))
                                  (swap-3 (syntax-rules () 
                                            ((_) (begin (swap-2) (sw 3) (swap-2)))))
                                  (swap-4 (syntax-rules () 
                                            ((_) (begin (swap-3) (sw 4) (swap-3))))))
                     (begin
                       (swap-4)
                       (cond ((> l l-best)
                              (display A) (newline)
                              (set! l-best l)
                              (set! A-best A)))))))
                (loop2 (cdr w2))))))))))))))))

UPDATE: I realized it might be worthwhile to identify how much speed-up would have resulted if I had just applied the most important steps to the original version at the outset.

The answer is that just:

Turning the bit-referencing operations into internal defines within the procedure, and

Using the fxlsh, fxrshl, and fxand operations for the definitions of the bit-referencing operations

brings the running time down to 18 seconds. So somewhere around 70 seconds of the time was spent on inefficiencies due to using general purpose arithmetic operations when fixnum operations (that the compiler specializes) would probably suffice for most people; no need to use macros to force an inlined swap(4) operation (which is what Knuth recommends in his text).

Here is the 18 second version. Note that its code bytevector after being compiled by Twobit is 4.0 kilobytes, while the more heavily optimized find-max-intermix.v16 is 17.8 kilobytes; that is a 4x space regression for a 2x speed improvement.


(define (find-max-intermix t words)

  (define bytevector-bit-ref 
    (lambda (bv k)
      (let ((q (fxrshl k 3))
            (r (fxand k #b111)))
        (fxrshl
         (fxand (bytevector-u8-ref bv q)
                (fxlsh 1 r)) r))))

  (define bytevector-bit-ref? 
    (lambda (bv k)
      (not (zero? (bytevector-bit-ref bv k)))))

  (let ((A-best '())
        (l-best 0)
        (wiz (map word->index words))
        (two^25 (expt 2 25))
        (two^20 (expt 2 20))
        (two^15 (expt 2 15))
        (two^10 (expt 2 10))
        (two^5  (expt 2  5)))
    (let loop1 ((w1 wiz))
      (cond 
       ((not (null? w1))
        (let loop2 ((w2 (cdr w1)))
          (cond 
           ((null? w2)
            (loop1 (cdr w1)))
           (else 
            (let* ((w (car w1))
                   (w* (car w2))
                   (z (fxxor w w*))
                   (m (+ two^20 two^15 two^10 two^5 1))
                   (m* (* two^5 m)))
              (cond
               ((not (zero? (fxand (fxxor (fx- z m) z m) m*)))
                (loop2 (cdr w2)))
               (else 
                (let ((m (vector (fxand z (fx- two^5  1))      ; m_0 
                                 (fxand z (fx- two^10 two^5))  ; m_1
                                 (fxand z (fx- two^15 two^10)) ; m_2
                                 (fxand z (fx- two^20 two^15)) ; m_3
                                 (fxand z (fx- two^25 two^20)) ; m_4
                                 )))
                  (let ((l 1) (A (list w)))
                    (let* ((sw (lambda (j) 
                                 (set! w (fxxor w (vector-ref m j)))
                                 (cond ((bytevector-bit-ref? t w)
                                        (set! l (+ l 1))
                                        (set! A (cons w A))))))
                           (swap-0 (lambda () (sw 0)))
                           (swap-1 (lambda () (swap-0) (sw 1) (swap-0)))
                           (swap-2 (lambda () (swap-1) (sw 2) (swap-1)))
                           (swap-3 (lambda () (swap-2) (sw 3) (swap-2)))
                           (swap-4 (lambda () (swap-3) (sw 4) (swap-3))))
                      (swap-4)
                      (cond ((> l l-best)
                             (display A) (newline)
                             (set! l-best l)
                             (set! A-best A))))))
                (loop2 (cdr w2)))))))))))))

mismatch twixt formals and invocation forms

2009-08-27T08:52:00.000-07:00

As a follow up to my yet-another-generator macro post:

yesterday at lunch I was trying to describe my problems generalizing my generator macro to handle arbitrary lambda formals lists. Ryan was the one who summed the problem up best; I think he said "there is a asymmetry between the format of the formals list and the format of invocation"

The problem in essence is that there are two distinct cases that are easy.
If you want to match a proper list of formals and generate a corresponding invocation, you do something like:


(define-syntax adder 
  (syntax-rules () 
    ((_ (args ...) k ...) 
     (lambda (args ...) (+ k ... args ...)))))

And, if you want to do variable arity, you can do it by matching an identifier representing the whole list of arguments


(define-syntax adder 
  (syntax-rules () 
    ((_ argl k ...) 
     (lambda argl (apply + k ... argl)))))

But notice the difference between the bottom and the top. If some users of the adder macro want to be able to specify that they are generating a procedure of arity 2, with appropriate error detection, they can use the first but not the second. And of course, the first does not do variable arity procedures.

To deal with this problem in the context of my generator macro, I introduced a helper macro that builds up an application expression based on the form of the formals list.


(define-syntax build-apply 
  (syntax-rules ()
    ((build-apply (rator rands ...) (args ...)) ;; usual case
     (rator rands ... args ...))
    ((build-apply (rator rands ...) (x . y))    ;; improper list, inductive case
     (build-apply (rator rands ...   x)  y))
    ((build-apply (rator rands ...) rest-args)  ;; improper list, base case
     (apply rator rands ... rest-args))))

The order of all three clauses above is very significant.

With that in place, here is the new form of my generator macro(s):


;; (generator ARGS BODY ...) => procedure 
;;   in whose body yield is bound to coroutine with caller
(define-syntax generator
  (transformer 
   (lambda (exp ren cmp)
     `(,(ren 'generator-via) yield ,(cadr exp) ,@(cddr exp)))))

(define-syntax generator-via
  (syntax-rules ()
    ((generator-via yield-id args body ...)
       (let ((get-next #f))
         (lambda args
           (call-with-current-continuation
            (lambda (exit)
              (cond 
               (get-next (build-apply (get-next exit) args))
               (else (let ((yield-id 
                            (lambda results 
                              (call-with-current-continuation
                               (lambda (next)
                                 (set! get-next (lambda (new-exit . args)
                                                  (set! exit new-exit)
                                                  (build-apply (next) args)))
                                 (apply exit results))))))
                       (call-with-values (lambda () body ...)
                         ;; below could also use build-apply with
                         ;; args, but then the "done-value"(s)
                         ;; returned from a generator would be forced
                         ;; to have value-count = length args
                         (lambda argl 
                           (set! get-next (lambda (new-exit . args)
                                            (apply new-exit argl)))
                           (apply exit argl)))))))))))))

yet another yield Scheme macro

2009-08-25T21:40:00.000-07:00

I have seen yield done plenty of times before, but I managed to reinvent it again tonight.

A lot of the time when I've played with call/cc, I have approached it trying to recreate a form in a statement-oriented language, and so I would end up not caring about the argument I would pass to the invocation of the captured continuation (because all I cared about was reestablishing the control flow of the prior context; the prior context itself would just discard any value I passed to it). I think the usual interpretation of yield is an instance of this in statement oriented languages.

However, when I was playing with some code tonight, I saw that dummy value and said, "ugly! why is that there?" And I decided to see what would happen if I got rid of it.

This macro is the result. (Obviously you want a bit of sugar around it to non-hygenically bind yield, although there are cases where it is nice to bind a different name like visit instead of yield, depending on the domain.)


(define-syntax generator-via
  (syntax-rules ()
    ;; puzzle 4 U: what role(s) does arg-list serve?  (all occurrences matter)
    ((generator-via yield-id arg-list body ...)
     (let ((yield-id #f) (get-next #f))
       (lambda arg-list
         (call-with-current-continuation
          (lambda (exit)
            (cond (get-next (get-next exit . arg-list))
                  (else (set! yield-id (lambda results 
                                         (call-with-current-continuation
                                          (lambda (next)
                                            (set! get-next 
                                                  (lambda (new-exit . arg-list)
                                                    (set! exit new-exit)
                                                    (next . arg-list)))
                                            (apply exit results)))))
                        (call-with-values (lambda () body ...)
                          ;; puzzle 4 U: why below eta-expansion required?
                          (lambda args (apply exit args))))))))))))

Its got some fun behaviors. Consider:


> (define grows 
    (generator-via yield (x) 
      (let loop ((i 0)) 
        (loop (+ i x (yield i))))))

> (grows 1)
0

> (grows 0)
1

> (grows 0)
2

> (grows 0)
3

> (grows 1)
5

> (grows 0)
6

(yes I just realized I could/should have let-bound the yield-id itself. The other set! invocations are believed to be necessary, barring tricks mixing letrec and call/cc.)

(no) interpreters on iphone

2009-07-29T12:13:00.000-07:00

I'm collecting blog posts and web pages discussing clause 3.3.2 of the iPhone SDK EULA and semi-related restrictions on iPhone apps.

mobilephonedevelopment article

rhomobile's interpretation of no interpreters rule

story of how a Basic interpreter got downgraded to a calculator (and how to bring the interpreter back if you're willing to jailbreak).

PhoneGap Discussion of arbitrariness of rejection

MacNN coverage of the PhoneGap issue.

Commodore 64 emulator rejection article

FrotZ got through the filter; I asked the developer about that in this discussion

git-svn argh!

2009-07-21T18:56:00.000-07:00

CCIS decommissioned a number of its Solaris machines recently.

I was using one of them as the point of access for the Larceny SVN repository, via the svn+ssh protocol.

More recently I have been playing with git-svn, using that as my way to interact with the repository. I made a local git-svn clone of the Larceny SVN repository, and then I would clone the clone and make branches in the cloned clones as part of my experimentation with new ideas. Fun fun fun.

Except that CCIS decommissioned a number of its Solaris machines recently, and I was using one of them as the point of access, which mean that the repository url looked something like svn+ssh://zulu.ccs.neu.edu/path-to-repos/, and git-svn (somewhat reasonably) assumes that these URLS would remain valid forever, and puts a copy of that URL into every log message of the clone.

Now, its easy to update those log messages; that's what git-filter-branch is for. (See also this related blog entry.)

But what's not so easy is dealing with the sudden split in the tree structure of the development on my cloned clones; all of my local deltas seem to point to the old changesets with the old bad URL. And "git rebase" does not seem to be magically able to handle this case.

Thus: git-svn argh!

If the SVN folks though that a "svn switch --relocate" command was important, maybe the git-svn developer(s) should also consider their design decisions...

Zecreasing Zerived Zvariables

2009-01-12T19:57:00.000-08:00

This is a great little story. And probably something I could explain to my Mom.

http://www.freedom-to-tinker.com/blog/felten/debugging-zune-blackout

(plus I've had this obsession with date-oriented code lately...)

(p.s. can one even pronounce "Zvariables"?)

5 or 6 forced restarts later...

2009-01-09T16:25:00.001-08:00

I wasted some time this evening trying to use gprof to profile Larceny.

Eventually I discovered that the -pg option simply does not work with gcc on Intel Macs. (Why on earth doesn't the man page for gprof say something about this?)

Apple instead recommends that one use Shark or Saturn, both provided when you install the CHUD Tools (Computer Hardware Understanding Developer Tools)

So I did that. I downloaded a copy of the CHUD Tools (and as far as I can remember, I did it by searching on ADC for them, and got a copy of chud.dmg). I was a little surprised by the file times (they said something like 2007) but I pressed on, eager to start seeing some profiler output, especially since all of my searches to read about Shark sounded very positive about it.

And then when I attempted to compile with -finstrument-functions, so I could use Saturn in the same way that I might have used gprof, I got a link error:


Undefined symbols:
  "___cyg_profile_func_exit", referenced from:
      _consolemsg in larceny.o
      _consolemsg in larceny.o
     ...
  "___cyg_profile_func_enter", referenced from:
      _panic_abort in larceny.o
      _panic_exit in larceny.o
    ...

I abandoned further attempts to use Saturn pretty quickly.

So then I tried Shark. And that was, if anything, worse. Because every time I tried to stop a profiling session, it would restart my machine!

Eventually I discovered (though not easily) this discussion post.

Hmm. CHUD 4.4.4 panics. I look at my version. Yep, its 4.4.4.

So I did a more careful search for a more recent version of CHUD (4.6.1, specifically). We'll see how that works out for me in a bit.

(I'm mostly posting this so that other people who run into a similar problem know that they need to get a newer version of CHUD. Maybe later I'll try to retrace my steps that led me to thinking that CHUD 4.4.4 was the version I needed to use...)

I do not know who linked to it, but some page (that I believe was on the Apple site) sent me to the follow ftp link, which has the version of CHUD that is incompatible with newer versions of OS X: ftp://ftp.apple.com/developer/Tool_Chest/Testing_-_Debugging/Performance_tools/CHUD_4.4.4.dmg

CFER : "suitable for blogs"

2008-12-15T09:55:00.000-08:00

ICFP 2009 has a "Call For Experience Reports", and specifically mentions that its suitable for posting on blogs.

So here goes. :)

ICFP 2009: CFER

data structures, network outages, and php

2008-07-02T15:41:00.000-07:00

The most "productive" portion of my day was spent prototyping the interface to summary set matrix that I will be putting into the regional collector RSN. I have the header file worked out and started working on the representation itself. I got part way through writing a constructor function before deciding that I wanted to think a bit more about how I want to handle allocation and deallocation of the entries in the sparse matrix.

(Some of that time was spent reviewing the existing source for the Larceny runtime, especially the different attribute bits one can put on pages of memory in Larceny, and the history of when they were introduced and/or shifted around by Lars...)

I also had a back-and-forth with the Systems staff since artichoke and poblano became inaccessible from the outside world at some point yesterday evening.

I finished off the day trying to figure out why my GC benchmarking script is still failing on the dynregion/ branch. I have more of a clue about it now, but am pretty unhappy about how much of a kludge this supposedly simpler script is becoming. (Maybe I should give up doing these things in shell script and just do them as Larceny scripts.)

hi after hiatus

2008-06-30T14:31:00.001-07:00

This weekend I mentioned that I had a blog to my family, and then showed the url to Stephanie.

I proceeded to become engrossed in reading over my old posts; I had forgotten some of the interesting software experiments I had been posting online.

Of course, I have not made a post in almost two years. I have since switched to keeping an internal work diary, so that I would not worry about giving away the farm (or embarrassing outcomes of my day to day research), and also posting any interesting links that I wanted to see later to my del.icio.us account

But I realized after looking at the old entries that I liked broadcasting my progress.

So I am going to try to maintain this blog again, and see if I can figure out how to distill my daily work diary into something small (and publicly distributable) each day (or perhaps every other day or so... who knows).

So, today:

Rasputin's disk was full; I had to wrestle with that for a little while. It seems like each disk fills up on such a regular basis that I really should consider fixing the autobuild scripts to clean up after themselves or to compress their generated directories or both...

I finally checked in a fix to Larceny's simplistic stopcopy collector on the IAssassin backend so that when allocation fills up a chunk in a semispace, the runtime first attempts to switch the allocation pointer to a free chunk within the semispace rather than attempt a whole heap collection. This is a crucial fix, because the stopcopy collector's performance had asymptotically terrible performance before, which affected both our benchmark results and some of our users who wanted to load a lot of code before performing a heap dump.

I spent some time trying to double-check the runtime source code's make dependencies, because I thought I saw evidence that not everything was being rebuilt properly in response to changes I made for fixing the stopcopy collector. Unfortunately I was unable to pin down any particular missing dependency.

I tried generalizing the nightly GC benchmarking script so that it could also benchmark my dynregion development branch. But then my attempts to just double-check the behavior of the GC benchmarking script itself failed, and my investigations there led me to file Ticket #547 in Larceny's trac database.

I also spent some time browsing the web/google groups/etc. I added some links to my aforementioned del.icio.us account. I don't think I'll be explicitly mentioning such activity on my part in the future.

Oh hdiutil, what can't you do?

2006-09-10T20:34:00.000-07:00

(orig article)

The punchline:

hdiutil convert image.dmg -format UDTO -o image.iso

Although this makes a file with the extension .cdr, the article claims that it is an iso file and can be renamed as such.

This allows me to use the OS X Disk Utility to create .iso images that can then be mounted from Parallels desktop or VMware.

UPDATE:
The above article seems to be a complete lie, but at least it pointed me at hdiutil... the above approach makes iso images that Mac OS X can mount, but do not work within Parallels.

However, the following command seems like it does the job:

hdiutil makehybrid -o image image.dmg

stupid LEA tricks

2006-08-08T11:37:00.000-07:00

LEA is the "load effective address" instruction on x86 processors.

Despite the "L" in the name, this is solely an arithmetic instruction. Which means there are some nasty little games you can play with it. Like this one I got courtesy of Frank Kotler from:

http://groups.google.com/group/alt.lang.asm/msg/27d6ed6183448057?hl=en&


global _start 

section .data 
     number_string db '123', 10 

section .text 
_start: 
     nop 

     push number_string 
     call atoi 
     add esp, byte 4 

     mov ebx, eax 
     mov eax, 1 
     int 80h 

atoi: 
     mov edx, [esp + 4]  ; pointer to string 
     xor eax, eax        ; clear "result" 
.top: 
     movzx ecx, byte [edx] 
     inc edx 
     cmp ecx, byte '0' 
     jb .done 
     cmp ecx, byte '9' 
     ja .done 

     ; we have a valid character - multiply 
     ; result-so-far by 10, subtract '0' 
     ; from the character to convert it to 
     ; a number, and add it to result. 

     lea eax, [eax + eax * 4] 
     lea eax, [eax * 2 + ecx - 48] 

     jmp short .top 
.done 
     ret

free smalltalk! (books, that is)

2006-07-18T13:26:00.000-07:00

Just discovered this page today:

20 smalltalk books, all available for free viewing online.

On a related note, here are some other free books online that I wasn't aware of until recently:

"Programming Ruby: The Pragmatic Programmer's Guide"
"Thinking Forth"; the PDFs there didn't work for me, but the LaTeX source is supposedly up there as well...

321 contact!

2006-05-03T09:38:00.000-07:00

Larceny's just ran x86 code in heap for the first time!

The initial scheme code:

(define seg (assemble (compile 321)))
(define env (environment-copy (interaction-environment)))
(define cseg (sassy-postpass-segment seg))
(define linked (link-lop-segment cseg env))

Note that the "program" we're compiling here is just evaluating the literal 321. Not very exciting to interpret, but to run off the heap, marvelous!

The (insane) hack on the x86 implementation of MacScheme's invoke:

 dec dword [GLOBALS+G_TIMER]
 jnz short %%L1
%%L0: mcall M_INVOKE_EX
 jmp short %%L1
%%L2:   storer 0, RESULT
 const2regf RESULT, fixnum(%1)
 int3 ;; debugging interrupt 
 ;;; (the lack of space is significant; gdb ignores "int 3")
 add     TEMP,-BVEC_TAG+BVEC_HEADER_BYTES
 jmp     TEMP
%%L1: lea TEMP, [RESULT+(8-PROC_TAG)]
 test TEMP_LOW, tag_mask
 jnz short %%L0
 ;; Felix inserted checks if we actually have a
 ;; fixnum here...
 mov TEMP, [TEMP-8+PROC_CODEVECTOR_NATIVE]
 test    TEMP_LOW, fixtag_mask
 jnz short %%L2
 storer 0, RESULT
 const2regf RESULT, fixnum(%1)
 jmp     TEMP

The heart of the hack is that invoke is now dispatching based on the kind of code pointer it got. This should allow me to keep using Petit for the heart of the system, but still test the code in the heap directly.

For fixnums (which are actually addresses into the text segment, but don't tell the garbage collector), we do the old invocation routine.

For bytevector pointers (which should point at codevectors in the heap), strip the tag off the pointer, then add the offset to skip over the bytevector header (on the heap object itself). Finally, JUMP!

And, at long last, the actual result:

(gdb) r -heap sassy.heap
Starting program: /home/pnkfelix/larcenydev/trunk/larceny_src/twobit.bin -heap sassy.heap
(no debugging symbols found)...(no debugging symbols found)...(no debugging symbols found)...(no debugging symbols found)...LARCENY_ROOT not set; using current directory
Larceny v0.91 "Children's Ice Cream" (May  2 2006 10:41:54, precise:Linux:unified)


> (load "testsass.scm") 

> (linked)

Program received signal SIGTRAP, Trace/breakpoint trap.
0x08342d49 in ..@6866.L2 ()
(gdb) stepi
0x08342d4c in ..@6866.L2 ()
(gdb) stepi
0x00767454 in ?? ()
(gdb) c
Continuing.
321

Did you see it??? Did you??? That 321 at the end, that was produced by code in the heap. (Well, the value was; the actual action of printing the value is still happening from code in the text segment).

Woo hoo!!!

on parallelizing a garbage collector

2006-02-01T18:25:00.000-08:00

So here are the lessons I learned from attempting to parallelize a stop-and-copy garbage collector, as implemented in the Larceny runtime, using Cilk's primitives as the basis for the parallelization.

At a high level, based on Flood's paper on parallel collection on SMP machines, I decided to start with a naive recursive stop-and-copy collection algorithm, and parallelize that using Cilk's spawn and sync primitives. (The Flood paper points out the utility of a work-stealing approach to load-balancing, which the Cilk runtime gives you "for free.")

Of course, the devil is in the details. First of all, all I had to start with was an kernel collector that uses Cheney's algorithm, which is not trivial to parallelize (as far as I can tell). So I had to develop a recursive algorithm that behaved in a manner compatible with the behavior of the Cheney collector (this is not as trivial as it sounds; the devil's in the details).

Even after I developed the recursive algorithm, I discovered a new set back: the Cilk language, as currently documented, has a restriction that you can only call Cilk functions from other Cilk functions. That is, Cilk functions can call out to C functions, but not vice versa.

This immediately leads to a huge problem for Larceny, because the Scheme code is meant to be able to call into the garbage collector. So that means that the Scheme code needs to be output as Cilk code, not C code. And in fact, the entire runtime and compiler system needs to be shifted to use Cilk instead of C. ACK!

Luckily, the very newest version of Cilk has a beta interface for calling Cilk functions from C code. Unluckily, the interface is indeed beta, and there were some bugs that were showstoppers for me (in hindsight, there were workarounds for the bugs, but that's neither here nor there).

So, here's the important lessons from the project:

Reverse engineering is hard. Even when you're going from a complex algorithm to a simple one, there's always details in "real systems" that get overlooked. (For me, it was particular invariants in terms of the Cheney algorithm deliberately not traversing certain structures at certain times, and it was overloading the generation bits to control this, even though it was still relevant even for non-generational collection.

If you want your language extension/variant A to interoperate with language B, it needs to go in both directions. You may think it will suffice to have one layered on top of the other, but in the end, you will be wrong, and your users will hate you. You're better off designing that interoperability in from the beginning. (This is relevant for languages that seek to interoperate with the CLR or the JVM, in that your extension language should define classes that themselves can be invoked or extended by terms in C# or Java, respectively.

They ID'ed me 100%

2006-01-03T10:19:00.000-08:00

Bourbon
Congratulations! You're 118 proof, with specific scores in beer (20) , wine (100), and liquor (78).

Screw all that namby-pamby chick stuff, you're going straight for the bottle and a shot glass! It'll take more than a few shots of Wild Turkey or 99 Bananas before you start seeing pink elephants. You know how to handle your alcohol, and yourself at parties.

My test tracked 4 variables How you compared to other people your age and gender:

You scored higher than 30% on proof
You scored higher than 50% on beer index
You scored higher than 84% on wine index
You scored higher than 66% on liquor index

Link: The Alcohol Knowledge Test written by hoppersplit on Ok Cupid, home of the 32-Type Dating Test

Swapping Ctrl/CapsLock (PCs or Macs!)

2005-11-13T20:07:00.000-08:00

Someone else cares about this, and he cares enough to catalogue how to do it on all sorts of machines!
Just go here.

(hmm. Actually, that was a total lie; the link above only treats windows and linux machines. Well, this guys says how to do it on 10.4 machines.)

some windows stuff worth knowing.

2005-11-03T20:57:00.000-08:00

This page tells you how to get free copies of the command line development tools that are including in Visual Studio. That's right, get yourself the C/C++ compiler and header files (as well as some batch scripts to set up your environment properly), all direct from Microsoft.

.NET Framework SDK (for the compiler and linker).

Platform SDK (for the header files).

As a side note to this, I had to learn about the call statement for DOS Batch scripts in order to learn how to make a batch file that would call each of the batch files in sequence, because each of the above SDK has a different batch file to set up the environment.

This page tells you how to edit the Windows Registry to change the behavior of the Caps Lock key. For a Emacs user like me, this was a crucial thing to learn, since the control key is really hard to get at on modern Windows laptops. Speaking of which . . .

This page tells you how to install Emacs on a Windows machine. It works well enough.

Cygwin. Nuff said.

GC'ing classes

2005-08-31T10:41:00.000-07:00

.NET as far as I can tell, does not garbage collect unreachable code. At best, you can try to manually manage the memory associated with dynamically loaded code by loading into separate AppDomains that you unload by hand. I have not really experimented with this option.

I was discussing this problem with a friend, who asserted that Java has the same problem.

To prove him wrong, I wrote the following class. You run it on the command line, passing an numeric argument that indicates the number of distinct classes you want to load. Try it out with and without the -Xnoclassgc option in Java!

import java.lang.Integer;
import java.lang.ClassLoader;
import java.lang.Class;
import java.lang.ClassNotFoundException;

public class ClassSFS {

    public static void println(String s) {
        System.out.println(s);
    }
    public static void println() {
        System.out.println();
    }
    public static void print(String s) {
        System.out.print(s);
    }
    public static void main(String[] args) {
        println("Hello World");
        int num_classes = Integer.parseInt(args[0]);
        initbytes();
        for(int i = 0; i < num_classes; i++) {
            
            Tbytes[ 48 + 5 ] = (byte) (0x61 + (i/100) % 26);
            Tbytes[ 48 + 6 ] = (byte) (0x61 + (i/10)  % 26);
            Tbytes[ 48 + 7 ] = (byte) (0x61 + (i/1)   % 26);
            
            CLoader cl = new CLoader();
            try {
                Class c = cl.findClass("T");
                Object x = c.newInstance();
                System.out.println("ClassLoader "+i+", x:"+x);
            } catch (ClassNotFoundException e) {
                System.out.println("ClassLoader "+i+", ClassNotFound e:"+e);
            } catch (InstantiationException e) {
                System.out.println("ClassLoader "+i+", InstantiationException e:"+e);
            } catch (IllegalAccessException e) {
                System.out.println("ClassLoader "+i+", IllegalAccessException e:"+e);
            } 
        }
    }

    static class CLoader extends ClassLoader {
        CLoader() { super(); }
        public Class findClass(String name) throws ClassNotFoundException {
            return 
                super.defineClass(name, 
                                  Tbytes,
                                  0,
                                  Tbytes.length);
        }
    }
    
    
    private static int[] iTbytes = {

        0xca, 0xfe, 0xba, 0xbe, 0x00, 0x00, 0x00, 0x2e, 0x00, 0x20, 0x0a, 0x00, 0x0a, 0x00, 0x16, 0x07,
        0x00, 0x17, 0x0a, 0x00, 0x02, 0x00, 0x16, 0x08, 0x00, 0x18, 0x0a, 0x00, 0x02, 0x00, 0x19, 0x09,
        0x00, 0x09, 0x00, 0x1a, 0x0a, 0x00, 0x02, 0x00, 0x1b, 0x08, 0x00, 0x0b, 0x07, 0x00, 0x1c, 0x07,
        /*                               f     e     e                                              */
        0x00, 0x1d, 0x01, 0x00, 0x03, 0x66, 0x65, 0x65, 0x01, 0x00, 0x12, 0x4c, 0x6a, 0x61, 0x76, 0x61,
        0x2f, 0x6c, 0x61, 0x6e, 0x67, 0x2f, 0x53, 0x74, 0x72, 0x69, 0x6e, 0x67, 0x3b, 0x01, 0x00, 0x06,
        0x3c, 0x69, 0x6e, 0x69, 0x74, 0x3e, 0x01, 0x00, 0x03, 0x28, 0x29, 0x56, 0x01, 0x00, 0x04, 0x43,
        0x6f, 0x64, 0x65, 0x01, 0x00, 0x0f, 0x4c, 0x69, 0x6e, 0x65, 0x4e, 0x75, 0x6d, 0x62, 0x65, 0x72,
        0x54, 0x61, 0x62, 0x6c, 0x65, 0x01, 0x00, 0x08, 0x74, 0x6f, 0x53, 0x74, 0x72, 0x69, 0x6e, 0x67,
        0x01, 0x00, 0x14, 0x28, 0x29, 0x4c, 0x6a, 0x61, 0x76, 0x61, 0x2f, 0x6c, 0x61, 0x6e, 0x67, 0x2f,
        0x53, 0x74, 0x72, 0x69, 0x6e, 0x67, 0x3b, 0x01, 0x00, 0x08, 0x3c, 0x63, 0x6c, 0x69, 0x6e, 0x69,
        0x74, 0x3e, 0x01, 0x00, 0x0a, 0x53, 0x6f, 0x75, 0x72, 0x63, 0x65, 0x46, 0x69, 0x6c, 0x65, 0x01,
        0x00, 0x06, 0x54, 0x2e, 0x6a, 0x61, 0x76, 0x61, 0x0c, 0x00, 0x0d, 0x00, 0x0e, 0x01, 0x00, 0x16,
        0x6a, 0x61, 0x76, 0x61, 0x2f, 0x6c, 0x61, 0x6e, 0x67, 0x2f, 0x53, 0x74, 0x72, 0x69, 0x6e, 0x67,
        0x42, 0x75, 0x66, 0x66, 0x65, 0x72, 0x01, 0x00, 0x03, 0x54, 0x3c, 0x3e, 0x0c, 0x00, 0x1e, 0x00,
        0x1f, 0x0c, 0x00, 0x0b, 0x00, 0x0c, 0x0c, 0x00, 0x11, 0x00, 0x12, 0x01, 0x00, 0x01, 0x54, 0x01,
        0x00, 0x10, 0x6a, 0x61, 0x76, 0x61, 0x2f, 0x6c, 0x61, 0x6e, 0x67, 0x2f, 0x4f, 0x62, 0x6a, 0x65,
        0x63, 0x74, 0x01, 0x00, 0x06, 0x61, 0x70, 0x70, 0x65, 0x6e, 0x64, 0x01, 0x00, 0x2c, 0x28, 0x4c,
        0x6a, 0x61, 0x76, 0x61, 0x2f, 0x6c, 0x61, 0x6e, 0x67, 0x2f, 0x53, 0x74, 0x72, 0x69, 0x6e, 0x67,
        0x3b, 0x29, 0x4c, 0x6a, 0x61, 0x76, 0x61, 0x2f, 0x6c, 0x61, 0x6e, 0x67, 0x2f, 0x53, 0x74, 0x72,
        0x69, 0x6e, 0x67, 0x42, 0x75, 0x66, 0x66, 0x65, 0x72, 0x3b, 0x00, 0x21, 0x00, 0x09, 0x00, 0x0a,
        0x00, 0x00, 0x00, 0x01, 0x00, 0x0a, 0x00, 0x0b, 0x00, 0x0c, 0x00, 0x00, 0x00, 0x03, 0x00, 0x01,
        0x00, 0x0d, 0x00, 0x0e, 0x00, 0x01, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x1d, 0x00, 0x01, 0x00, 0x01,
        0x00, 0x00, 0x00, 0x05, 0x2a, 0xb7, 0x00, 0x01, 0xb1, 0x00, 0x00, 0x00, 0x01, 0x00, 0x10, 0x00,
        0x00, 0x00, 0x06, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x11, 0x00, 0x12, 0x00,
        0x01, 0x00, 0x0f, 0x00, 0x00, 0x00, 0x2e, 0x00, 0x02, 0x00, 0x01, 0x00, 0x00, 0x00, 0x16, 0xbb,
        0x00, 0x02, 0x59, 0xb7, 0x00, 0x03, 0x12, 0x04, 0xb6, 0x00, 0x05, 0xb2, 0x00, 0x06, 0xb6, 0x00,
        0x05, 0xb6, 0x00, 0x07, 0xb0, 0x00, 0x00, 0x00, 0x01, 0x00, 0x10, 0x00, 0x00, 0x00, 0x06, 0x00,
        0x01, 0x00, 0x00, 0x00, 0x04, 0x00, 0x08, 0x00, 0x13, 0x00, 0x0e, 0x00, 0x01, 0x00, 0x0f, 0x00,
        0x00, 0x00, 0x1e, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x12, 0x08, 0xb3, 0x00, 0x06,
        0xb1, 0x00, 0x00, 0x00, 0x01, 0x00, 0x10, 0x00, 0x00, 0x00, 0x06, 0x00, 0x01, 0x00, 0x00, 0x00,
        0x02, 0x00, 0x01, 0x00, 0x14, 0x00, 0x00, 0x00, 0x02, 0x00, 0x15

    };

    private static byte[] Tbytes;

    public static void initbytes()
    { 
        Tbytes = new byte[ iTbytes.length  ];
        for(int i = 0; i < iTbytes.length; i++) {
            Tbytes[i] = (byte)(iTbytes[i]);
        }

        print(""+nybble2char((Tbytes[0]>>4) & 0xF));
        print(""+nybble2char((Tbytes[0]>>0) & 0xF));
        print(""+nybble2char((Tbytes[1]>>4) & 0xF));
        print(""+nybble2char((Tbytes[1]>>0) & 0xF));
        print(""+nybble2char((Tbytes[2]>>4) & 0xF));
        print(""+nybble2char((Tbytes[2]>>0) & 0xF));
        print(""+nybble2char((Tbytes[3]>>4) & 0xF));
        print(""+nybble2char((Tbytes[3]>>0) & 0xF));
        println();
    }
    
    private static char nybble2char(int b) {
        switch (b) {
        case 0xf: return 'f';
        case 0xe: return 'e';
        case 0xd: return 'd';
        case 0xc: return 'c';
        case 0xb: return 'b';
        case 0xa: return 'a';
        default: return (char) (b+'a');
        }
    }

    public static int Tcounter = 0;
}

The iTbytes array was generated by compiling public class T { private static String fee = "fee"; public String toString() { return "T<>"+fee; }}, then loading the resulting class file into emacs, switching to hexl-mode, and doing some keyboard-macrology to convert it to something javac would accept.

C#, pass-by-value, pass-by-reference

2005-08-25T11:49:00.000-07:00

Here's a nice little snippet of C# for you.

using System;

namespace InterfaceSample {
  public delegate void Changed();
  interface IPoint {
    int X { get; set; }
    int Y { get; set; }
  }
  
  struct Point: IPoint {
    private int xValue, yValue;
    public int X { get { return xValue; } set { xValue = value; } }
    public int Y { get { return yValue; } set { yValue = value; } }
  }
  
  public class EntryPoint {
    public static int Main() {
      String formatstr = "  p1.X: {0}, p1.Y: {1}, p2.X: {2}, p2.Y: {3} ip1.X: {4}, ip1.Y: {5}, ip2.X: {6}, ip2.Y: {7}";

      Point p1 = new Point();
      p1.X = p1.Y = 42;
      IPoint ip1 = p1;
      Point p2 = (Point) ip1;
      IPoint ip2 = ip1;

      Console.WriteLine(formatstr, p1.X, p1.Y, p2.X, p2.Y, ip1.X, ip1.Y, ip2.X, ip2.Y);
      p1.X = p1.Y = 21; Console.WriteLine("p1.X = p1.Y = 21;");
      Console.WriteLine(formatstr, p1.X, p1.Y, p2.X, p2.Y, ip1.X, ip1.Y, ip2.X, ip2.Y);
      ip1.X = ip1.Y = 84; Console.WriteLine("ip1.X = ip1.Y = 84;");
      Console.WriteLine(formatstr, p1.X, p1.Y, p2.X, p2.Y, ip1.X, ip1.Y, ip2.X, ip2.Y);
      return 0;
    }
  }
}

In C#, classes and interfaces can have properties, which have usage syntax similar to fields but semantics similar to methods. In the interface, you just declare the property name and whether it has getters/setters; in the class, you then define the behavior you want for the property.

In C#, you can declare struct types, which are value types in the language. This means that they are passed by value. However, they are not immutable.

In C#, a struct type can implement an interface. Ah, what fun.

Here's the output of the above program:

  p1.X: 42, p1.Y: 42, p2.X: 42, p2.Y: 42 ip1.X: 42, ip1.Y: 42, ip2.X: 42, ip2.Y: 42
p1.X = p1.Y = 21;
  p1.X: 21, p1.Y: 21, p2.X: 42, p2.Y: 42 ip1.X: 42, ip1.Y: 42, ip2.X: 42, ip2.Y: 42
ip1.X = ip1.Y = 84;
  p1.X: 21, p1.Y: 21, p2.X: 42, p2.Y: 42 ip1.X: 84, ip1.Y: 84, ip2.X: 84, ip2.Y: 84

The mutation to p's properties is not propagated over to ip, which looks odd to a Java programmer like me. This is because the assignment ip1 = p1 makes a copy of p1 when it "boxes" it into ip1.

And even odder, given the previous paragraph, the mutations to ip1 are carried over to ip2. Actually, this isn't so odd, since ip1 is an interface after all, that might ("must", considering boxing?) be implemented by an object, and therefore the assignment must copy a reference to the object.

Finally, you can copy from the interface back to a Point, but this requires a cast. This makes sense (see previous paragraph).

In the end, I don't think I have a big problem with value types. Its just the mutable value types that I get nervous about, because then you actually need to start thinking about the copy/reference semantics.

old stack based languages

2005-08-10T07:08:00.000-07:00

We all know that I've been looking at Forth to digest its approach to allowing powerful compile-time constructions.

Fare, an LL-discuss member, mentioned POP-11 as an alternative to Forth (that might be even older). It seems to also have the ability to define compile-time programs; it remains to be seen how it compares to Forth (or Lisp/Scheme, for that matter).

heh

I just realized that my use of "We all know" up above is completely unfounded, because I didn't bother to blog during the month of July, which was when I was investigating Forth so heavily. I suppose I should finish the investigation (or at least both the books from the library) and write something up.

rules for intermediate representations

2005-08-10T00:02:00.000-07:00

And the muse of compiler development did rise from her murky swamp, and did say unto the Larceny developers, "Thou shalt not convert your aye-arrh into object form, be it string, bytecode, or otherwise, until the last possible moment."

The Larceny developers did take exception to this rule, pleading "but we have chosen an invertible object form, from which the most exhalted client developer may extract the original structured aye-arrh. Its strings are formatted thusly, isomorphic to the structure of the input, and thus less painful for my mortal eyes to gaze upon than the radiance of the aye-arrh structure itself."

To this, the muse of compiler development rules responds, "verily, you might take such a path; but then you must also provide such inversion functions, and not place the onus of developing such functions upon the shoulders of the most exhalted client developer, who is already fed up with trying to make sense of your underspecified and confusingly named interfaces.

Here endeth the lesson.

On Macros and JavaDot

2005-08-04T16:01:00.000-07:00

Tonight I made a fun macro that tries to cut down on the verbosity when you refer to classes using Javadot; normally you have to explicit write out the full name with all the package prefixes. What I want is to introduce a nice shorthand, similar to the shorthand introduced by the import statement in Java.

Here is the macro:

;; (let/import ((X Y Z1 Z2 ...)) BODY ...) binds Y.Z1, Y.Z2, ... to
;; the expressions X.Y.Z1, X.Y.Z2, ..., and naturally generalizes to
;; more than one prefix X.
;; As one special case, if Zn is (), then that means import the constructor
;; X.Y. as the name Y. (note the period on the end).
(define-syntax let/import
  (transformer (lambda (stx ren cmp)
   (let ((bindings (cadr stx))
         (body (cddr stx))
         (construct-new-bindings 
   (lambda (binding)
     (let* ((->s (lambda (x)
     (if (null? x)
         ""
         (symbol->string x))))
     (prefix (->s (car binding)))
     (middle (->s (cadr binding)))
     (suffixes (map ->s (cddr binding)))
     (s->/append (lambda l 
            (string->symbol (apply string-append l))))
     (make-binding (lambda l
       (list (apply s->/append l)
             (symbol->javadot-symbol
       (apply s->/append prefix "." l))))))
       (map (lambda (suffix) (make-binding middle "." suffix))
     suffixes)))))
     `(,(ren 'let) (,@(apply append (map construct-new-bindings bindings))) 
       ,@body)))))

This pretty much works.

However, using it seems to have exposed what I'd call a bug in how Common Larceny's macro expander interacts with Javadot.

Watch this:

> (let () System.Reflection.Emit.AssemblyBuilderAccess.RunAndSave$)
#<procedure of 0 arguments>

> (let () System.Reflection.Emit.AssemblyBuilderAccess.Run$)
#<procedure of 0 arguments>

> (let/import ((System.Reflection.Emit AssemblyBuilderAccess RunAndSave$)) AssemblyBuilderAccess.RunAndSave$)
#<procedure of 0 arguments>

> (let/import ((System.Reflection.Emit AssemblyBuilderAccess RunAndSave$)) System.Reflection.Emit.AssemblyBuilderAccess.Run$)
#<procedure of 0 arguments>

> (let/import ((System.Reflection.Emit AssemblyBuilderAccess RunAndSave$)) System.Reflection.Emit.AssemblyBuilderAccess.RunAndSave$)

Error: Reference to undefined global variable "system.reflection.emit.assemblybuilderaccess.runandsave$".

>

What huppen!?!

I dunno, but Ryan and I tried looking at the expanded output:

> (macro-expand '(let/import ((System.Reflection.Emit AssemblyBuilderAccess RunAndSave$)) System.Reflection.Emit.AssemblyBuilderAccess.Run$))
((lambda () ((lambda (.assemblybuilderaccess.runandsave$|4) (clr/find-static-field-getter '#f 'system.reflection.emit.assemblybuilderaccess.run)) (clr/find-static-field-getter '#f 'system.reflection.emit.assemblybuilderaccess.runandsave))))

> (macro-expand '(let/import ((System.Reflection.Emit AssemblyBuilderAccess RunAndSave$)) AssemblyBuilderAccess.RunAndSave$))
((lambda () ((lambda (.assemblybuilderaccess.runandsave$|4) .assemblybuilderaccess.runandsave$|4) (clr/find-static-field-getter '#f 'system.reflection.emit.assemblybuilderaccess.runandsave))))

> (macro-expand '(let/import ((System.Reflection.Emit AssemblyBuilderAccess RunAndSave$)) System.Reflection.Emit.AssemblyBuilderAccess.RunAndSave$))
((lambda () ((lambda (.assemblybuilderaccess.runandsave$|4) (clr/find-static-field-getter '#f 'system.reflection.emit.assemblybuilderaccess.runandsave)) system.reflection.emit.assemblybuilderaccess.runandsave$)))

>

Update

It turns out this isn't even a problem with Macros; it looks like its just a bug in our JavaDot implementation when you refer to the same identifier more than once. E.g.:

> (begin (display System.String.class) (display System.String.class))
#<System.RuntimeType System.String>
Error: Reference to undefined global variable "system.string.class".

So much for getting excited about some strange new bug...

Tales from the Larceny source: Eta the Ultimate

2005-08-03T12:41:00.000-07:00

; Note: the idiom that is seen in this file,
; (emit-fixup-proc! as (lambda (b l) (fixup b l)))
; when `fixup' is a local procedure, avoids allocation of the closure
; except in the cases where the fixup is in fact needed, for gains in
; speed and reduction in allocation. (Ask me if you want numbers.)

I didn't understand this note in sparcasm.sch when I read it a week or so ago, so I asked Will to explain it to me. Here is what I got out of the explanation.

The code is something like:

(define (foo as x)
   (define (fixup bv loc) --omitted--)
   (if (usually-true)
       (bar)
       (emit-fixup-proc! as (lambda (b l) (fixup b l)))))

The idea here is that we know all the points where fixup is used, and it is being invoked at each one. Thus, fixup qualifies as a "known local procedure.", and we can compile it directly to a sequence of machine code instructions in the current text segment, and make it just another label in the compiled machine code for foo that we can jump to.

If we hadn't eta-expanded the reference to fixup, a la:

(define (foo as x)
   (define (fixup bv loc) --omitted--)
   (if (usually-true)
       (bar)
       (emit-fixup-proc! as fixup)))

then fixup is no longer a "known local procedure", because we cannot tell what emit-fixup-proc! will do with it (e.g. it may store it into a global variable which will later be invoked), and therefore in this latter case, we will conservatively generate a closure object and bind that to fixup.

In the former case, we also generate a closure object for the whole lambda expression, but we only generate this object on the uncommon control flow path; fixup itself is a free variable referenced by the closure, and therefore remains a simple label in the machine code text of foo.

This leads to a few questions, none of which I thought of in time to ask Will about them:

Couldn't we have acheived the same effect (but without eta-expanding) by pushing the definition of fixup down closer to its use?
- Quesswork answer: yes, but in the real source tree, fixup is actually referenced multiple times. Even then, one might be able to get away with cloning the definition and pushing the seperate clones down, but now you have to trade off the blow up in static code size versus the cost of allocating the closure at runtime.
What about an optimization pass to automatically introduce eta expansions on references like these to otherwise known local procedures?
- Quesswork answer: well, note here we rely on a human provided assurance as to what the common code path is. If it were more common to take the other route, then I don't think eta-expansion would be a win anymore. What kind of performance hit could such a transformation introduce then?
What about optimizing whatever is introducing the code for the allocation of the closure for fixup, so that the introduced code doesn't allocate until it absolutely must (due to data-dependency requirements, either by a use of fixup or a mutation of some data that the construction of fixup requires)?
- I dunno. Sounds tricky. Also note that this is pretty similar to (1.) above, except applied at a lower level than Scheme source.

I am . . .

2005-06-30T05:19:00.000-07:00

bonus (dfw) !

2005-06-29T03:29:00.000-07:00

And as an added bonus, here is pretty good commencement speech by David Foster Wallace. Its no "Wear Sunscreen", in that I don't see it being put to music and put on VH1 anytime soon, but its probably bettter than "No Sex in the Champagne Room."

David Foster Wallace, in case you didn't know, is the author of Infinite Jest, a book which I'm still not sure whether was worth finishing (other than to be able to say at dinner, "I finished Infinite Jest.", which is a great test of the people you're talking to, because the right response to this statement really is "Why?").

He has other books as well ("Interviews with hideous men") but those didn't grab me (and drop me) in the same way that Infinite Jest did.

self and virtual types

2005-06-29T03:18:00.000-07:00

I've been listening on discussions in the lab lately on handling self types. Sam mentioned something called virtual types. I know nothing about them.

However, I happened to run into an article by Remy and Vouillon arguing that virtual types (or at least common uses of virtual types) do not need special treatment in O'Caml, and gives some example code.

So I want to go back over the article later and really digest what is going on. I followed the argument as presented when I read it directly, but I'm feeling I may have missed the point when they were talking about camels at the end.

larceny unleashed

2005-06-20T16:45:00.000-07:00

Last week, Will finally decided it was time to "release" Petit Larceny (as well as the latest build for Native Larceny).

I don't have much else to add to the subject. (other than its not really what anyone is willing to call a formal release; Will calls it a "Developer's Alpha", and I call it "Potentially Unembarressing")

However, it is nice that we've hit this stage.

Next items on my agenda:

Finish term paper on "Computability and Complexity of Type Inference" (this mostly consists of poking Carl with progressively larger sticks).
Finish getting NASM support working for Larceny on win32 platforms (so that we can release for windows as well as the current Mac OS X and Sparc).
Merge the Common Larceny and Petit Larceny (aka release_2) source branches in the CVS repository.
Start planning out how to implement the Garbage First collector in Larceny's runtime.

garbage collection in cylone

2005-06-16T15:13:00.000-07:00

I just read a nice lil' paper that gives me hope for my own research.

It sounds like they put a region system to good use in developing a simple two-space garbage collector.

However, this blog entry indicates that they haven't figured out how to do a generational collector yet, and that they think it might require dependent types. Yowza. I've been thinking about the problem as well, but I never got to the point where it seemed like something that sophisticated would be required. . .

before you die, i'd like to. . .

2005-06-09T08:08:00.000-07:00

Here is a page of links on PowerPC assembly programming.

Yeah, I've taken my sweet time getting around to learning ppc asm, so now one must wonder, "why bother?"

No answer.

apple, suicide, and analogies

2005-06-09T07:09:00.000-07:00

This is a "fun" posting from 2001.

No, the analogy doesn't entirely stand up on its own. But its still worth considering.

The other issue that some people are talking about is DRM. Is that a driving issue? Its certainly not one that Steve Jobs was willing to mention on stage. Maybe its just paranoia.

"i for one welcome our new intel overlords"

2005-06-06T11:23:00.000-07:00

. . . but not really.

Yep, Apple is going to be a Switcher. And I'm somewhat pissed about it.

I really had bought into the argument that RISC processors were the right solution for the long term, and that PowerPC was more scalable than Intel, etc etc. If nothing else, Intel processors meager register set really sucks.

Perhaps the worst thing is that it is going to be very hard to convince anyone to buy a new mac for the next year, at least. Sigh.

The power set axiom and the specification schema

2005-05-26T08:37:00.000-07:00

Some people at the lab know that I occasionally (half-jokingly) question the existence of the real numbers and the (informal) validity of a set of axioms that imply that the reals exist.

Most recently I had pinned this down to the powerset axiom in Zermelo set theory. The powerset axiom is: "For any set z, there is a set whose members are just the subsets of z." [ forall z exists y forall x (x in y iff forall w ( w in x implies w in z )) ].

Let me be clear here: I have no problem with the powerset operator being applied to finite sets. I definitely see that for any finite set z, the powerset of z is easily constructed. The questionable part is: why should I believe that the powerset operator is applicable to infinite sets? Given the set of natural numbers N, if we allow the existance of its powerset, 2^N, then there are elements of 2^N that cannot be described by a finite piece of text. Why should we assume that such sets exist?

I recently picked up Boolos' book, "Logic, Logic, and Logic", again, and started looking there for answers to questions I've been having recently about Linear Logic. The first chapter presents "The Iterative Conception of Set", where Boolos describes a staged model for constructing the sets described by Zermelo's axioms (which include the powerset axiom above).

There are a lot of rules for building up these stages, but most of them are straightforward and believable. I skimmed them over, said "okay", and moved on to the next section, which argues that the axioms of Zermelo Set theory follow from the rules given for building the stages. This includes the Powerset axiom; so I was naturally interested in reading this more carefully.

The derivation of the Powerset axiom hinges on the truth of the "specification axioms" of the staged model. When I saw that, I said, "okay, I missed the details of the specification axioms, lets revisit it. . ." It is actually a schema describing an infinite set of formulas that we take as axioms. It is phrased as follows:

"forall s exists y forall x (x in y iff [X] and exists t (t earlierThan s and x formedAt t)))"
where [X] is a formula of in which no occurrence of "y" is free.

As Boolos puts it, "any such axiom will say that for any stage there is a set of just those sets to which [X] applies that are formed before that stage. Let us call these axioms specification axioms."

To derive the powerset axiom, one starts with the specification axiom:
"forall s exists y forall x (x in y iff (forall w (w in x implies w in z) and exists t (t earlierThan s and x formedAt t)))"
which is the same as the above with [X] := "forall w (w in x implies w in z)". This specification axiom says "for any stage, there is a set of all subsets of z formed at earlier stages." (the argument continues from there, but I don't want to relay the remainder of it at this point.)

z is free in the above specification axioms. So it seems that we're actually going to be employing an infinite number of the specification axioms to argue that the powerset axiom is true, since the powerset axiom is quantified over all z; is this okay? Plus, I'm no longer so sure that it is sensible to put no constraints on [X] other than that no occurrence of "y" be free in [X].

But these are pretty flimsy questions; and that's a good thing for me, because it means that I'm narrowing down my uneasiness about the powerset axiom into more bite-size chunks that I can process.

Linear Logic (with urls!)

2005-05-23T22:13:00.001-07:00

Girard, 1987. Very hard to read. Found on
Girard's pubs page. Girard, 1995 has a significantly lower barrier to entry.

Lafont's collection. The only one I've skimmed is a Linear Abstract Machine, which isn't even downloadable there.

Another collection

Wadler's collection.

mailman, the return

2005-05-21T10:19:00.000-07:00

As the subject indicates, I had a brief reencounter with a prior post today.

Short version of story (which is all I have time for today): when in doubt, check that the qrunner daemon has actually been started.

dlopen on win32 ?

2005-05-17T22:57:00.000-07:00

I spent today getting Larceny to build on Cygwin. After I finished getting something that seemd to evaluate simple Scheme expressions, I tried dynamic loading. And it didn't work.

So at last I realized that I had been misinterpreting many of Lars' statements: dynamic loading doesn't work at all on Windows (even under Cygwin, which was the key bit I was missing).

Thus began a huge quest to figure out how dynamic loading works on Windows. Ha. Ha. Ha.

Here are some links I've found trying to explain it to Unix-heads like myself (or just looked interesting as I browsed over the Google output).

I think I need to pay special attention to the "Gimp" solution documented on the EDLL page; I don't mind writing a .def file that has all the millicode routines listed in it.

linear objects

2005-05-12T15:52:00.000-07:00

This is just a note to myself to revisit the
following article by Henry Baker:
'Use-Once' Variables and Linear Objects

I really should start making a big list for Stevie and I to go through in preparation for our PL Jr talk.

See also:

publication pressure

2005-04-29T09:05:00.000-07:00

I have to say, I need to try to publish my work more often. (For other than
the obvious reason that I need to publish work, period.)

It really forces you to make everything concrete. To the max.

Almost as much as actually implementing it would.

System F and semi-unification

2005-04-19T15:26:00.000-07:00

This is somewhat of a note to myself to revist the responses posted.

I'm not 100% percent sure the original author (Mike) really had a grasp on what he was saying. On the one hand, he wanted to get an intuition as to which programs would be problematic to infer types for. But then he started talking about reducing inference for those problems to semi-unification; that's not the right idea! The idea is that you take a bog-standard undecidable problem (e.g. the halting problem), reduce that to semi-unification, and then reduce the reduction to a sample term in System F.

Of course, this would probably yield a term so complex that it would boggle the mind, and not provide the intuition that he was hoping for.

If, on the other hand, he was just interested in the idea of using a (partial) semi-unifier to (partially) perform type inference for System F, then that's a different story. Hard to tell. But lots of interesting points and links in the responses.

subtextual response

2005-04-19T08:39:00.000-07:00

I've been looking at Jonathan Edwards' experimental programming
environment/language, Subtextual

I am semi-underwhelmed. But there are some interesting connections with spreadsheet programming here.

I later read this post from the related Alarming Development blog, and there was one thing there that irk'ed me: the idea that we should embraced copy-and-paste programming.

cut-and-paste programming, I have learned to accept. That's when, if you are tempted to copy-and-paste a snippet of code, you instead cut it out entirely, and then turn it into a seperate subroutine/superclass/unit/module. Then you parameterize accordingly (and of course you are expected to add documentation about the mental model you have in your head about what this piece of code does).

But copy-and-paste is very dangerous. And in fact, in Subtextual, it seems like Edwards has embraced a sort of hybrid between cut and copy, because when you copy subtrees, you don't get a fresh copy immediately; instead you get a tree that is linked back to the original tree, and changes to either will propogate to both. You have a seperate operation, "introduce variant", to actually do the copying in place.

mailman, postfix, and pain

2005-04-12T10:54:00.000-07:00

Was up late last night trying to set up a mailman-based mailing list to demonstrate such things to my cousin.

I made much use of this page to figure out how to get the whole thing going. But when I went to bed, the damn thing still wasn't working.

Eventually I figured out that I never actually started the mailman daemon that is in charge of processing information as it comes in. I just figured that apache and postfix would know that they needed to call out to these command line procedures when they got certain inputs (e.g. mail to a particular address). Silly me.

So I was dumped into the sewer of systems administration once again. But I've pulled myself out now; I'm so happy I'm a PL researcher.

Observing Finalizers and References on the JVM

2005-04-11T22:10:00.000-07:00

As a followup to clarify my previous comment on this post (since Dave and I discussed this question personally):

Here is an experimental revision of the code that Dave posted; it is meant to demonstrate a number of things. The most important are:

If you want to really observe a space leak, it is helpful to actually use objects which are large (new int[X] is your friend here).
If you want to really observe a space leak, it (unfortunately) seems like you may have to employ the (non-standard) -Xms and -Xmx options to the JVM.
There are more reliable/sensible alternatives for monitoring whether an object has been collected than attempting to maintain a hashtable of object identifiers. Namely, use of classes in java.lang.ref.*.
- Having said this, I admit that I do not fully understand the semantics of weak references, because I was not able to naively replace all of Dave's uses of kill(int) with my killAlt(int) procedure.
Finalizers really are run only once. However, that doesn't always mean that you can't collect an object just because the call to its finalizer makes it live again.

I had to backport the code to JDK 1.4 since that's all I have on my poor little Mac OS X box. Sorry. I tried to make the backport clean by using trampoline instantiation of the generic collections rather than cluttering up the code with casts everywhere.

Sample command line invocations of this class:

% java -Xmx1mb -Xms1mb Immortal -dummysize 100000 -num 10

% java -Xmx1mb -Xms1mb Immortal -dummysize 100000 -blowup 10

(Note that due to the braindead way I'm doing argument parsing, the order of the options above is VERY significant).


import java.util.Hashtable;
import java.util.Vector;
import java.lang.ref.Reference;
import java.lang.ref.WeakReference;
import java.lang.ref.ReferenceQueue;

public class Immortal {

    static class HashtableFromIntegerToInteger {
 Hashtable me = new Hashtable();
 public int get(int k) { return ((Integer)me.get(new Integer(k))).intValue(); }
 public void put(int k, int v) { me.put(new Integer(k), new Integer(v)); }
 public void remove(int k) { me.remove(new Integer(k)); }
    }

    static class HashtableFromIntegerToImmortal {
 Hashtable me = new Hashtable();
 public Immortal get(int k) { return ((Immortal)me.get(new Integer(k))); }
 public void put(int k, Immortal v) { me.put(new Integer(k), v); }
 public void remove(int k) { me.remove(new Integer(k)); }
    }

    static class HashtableFromIntegerToRef {
 Hashtable me = new Hashtable();
 public Reference get(int k) { return ((Reference)me.get(new Integer(k))); }
 public void put(int k, Reference v) { me.put(new Integer(k), v); }
 public void remove(int k) { me.remove(new Integer(k)); }
    }

    /** tracks the number of times each finalizer is run */
    // private static Hashtable finalizeCounts = new Hashtable();
    private static HashtableFromIntegerToInteger finalizeCounts = new HashtableFromIntegerToInteger();

    /** used to control object lifetimes */
    private static HashtableFromIntegerToImmortal pointers = new HashtableFromIntegerToImmortal();

    private static HashtableFromIntegerToRef  phantoms = new HashtableFromIntegerToRef();
    
    private static ReferenceQueue refqueue = new ReferenceQueue();

    private static boolean nomesg = false;

    private static void mesg(String s) {
 if (! nomesg) {
     System.out.println(s);
 }
    }

    /** used to generate unique identifier codes */
    private static int unique = 0;

    /** some "large" state so that we can observe blowup */
    public int[] dummydata;
    private static int dummysize = 100;

    public static void killAlt(int id) {
        int finalizeCount = finalizeCounts.get(id);
        pointers.remove(id);
        while ( ! phantoms.get(id).isEnqueued())
        {
            mesg("(alt) trying to kill " + id + "...");
            System.gc();
        }
    }

    /** deletes the object with the given id. */
    public static void kill(int id)
    {
        int finalizeCount = finalizeCounts.get(id);
        pointers.remove(id);
        while (finalizeCounts.get(id) == finalizeCount)
        {
            mesg("trying to kill " + id + "...");
            System.gc();
        }
    }

    // The code from these two methods can't be inlined, because
    // we rely on their stack frame disappearing to prevent the
    // link to the tracked object from persisting.

    public static int makeTemporaryObject()
    {
        Immortal temp = new Immortal();
        return temp.id;
    }

    public static void doSomethingWith(int id)
    {
        Immortal temp = pointers.get(id);
        temp.sayHello();
    }

    /** identifier code */
    private int id;

    private Immortal()
    {
        id = unique++;
        mesg("creating instance " + id);
        finalizeCounts.put(id, 0);
        pointers.put(id, this);
 phantoms.put(id, new WeakReference(this, refqueue));
 int last = dummysize;
 dummydata = new int[last + 1];
 dummydata[0] = 1;
 dummydata[last] = 1;
    }

    public void sayHello()
    {
        System.out.println("hi, I'm number " + id);
    }

    public void finalize()
    {
        mesg("finalizing " + id + "...");
        finalizeCounts.put(id, finalizeCounts.get(id) + 1);
        // clear! *khzh-thump*
        pointers.put(id, this);
    }

    public static void main(String[] args) {

 if (args.length == 0) {
     int id = Immortal.makeTemporaryObject();
     
     // This causes the finalizer to run (in the GC thread.)
     Immortal.kill(id);
     
     // And yet, the object is still alive!
     Immortal.doSomethingWith(id);
     
     // This will now loop infinitely, since the finalizer
     // will never be run a second time.
     Immortal.kill(id); 
 } else { 
     for(int i = 0; i < args.length; i++) {
  if (false) {
      // dummy case for uniform syntax
  } else if (args[i].equals("-nomesg")) {
      nomesg = true;
  } else if (args[i].equals("-dummysize")) {
      int num = Integer.parseInt(args[++i]);
      dummysize = num;
  } else if (args[i].equals("-num")) {
      int num = Integer.parseInt(args[++i]);
      
      for(int j = 0; j < num; j++) {
   int id = Immortal.makeTemporaryObject();
   
   // This causes the finalizer to run (in the GC thread.)
   Immortal.kill(id);
   
   // And yet, the object is still alive!
   Immortal.doSomethingWith(id);
   
   // FSK: alternative variant of kill which uses weak references
   Immortal.killAlt(id); 
      }
  } else if (args[i].equals("-blowup")) {
      int num = Integer.parseInt(args[++i]);
      
      for(int j = 0; j < num; j++) {
   int id = Immortal.makeTemporaryObject();
   
   // This causes the finalizer to run (in the GC thread.)
   Immortal.kill(id);
   
   // And yet, the object is still alive!
   Immortal.doSomethingWith(id);
   
      }
  }
     }
 }
    }
}

"Well-going programs can be typed"

2005-03-26T17:18:00.000-08:00

Here is one of the stranger papers I've seen since the Forsythe one:

Well-going programs can be typed

The abstract:

Our idiomatically objectionable title is a pun on Milner's ``well-typed programs do not go wrong' --- because we provide a completeness result for type-checking rather than a soundness result.

We show that the well-behaved functions of untyped PCF are already expressible in typed PCF: any equivalence class of the partial logical equivalence generated from the flat natural numbers in the model given by PCF's operational semantics is inhabited by a well-typed term.

Its got Scott's $D_{\infty}$, PCF, Retractions, PERs, Logical Relations, . . .

And yet the paper itself is 50% tricks with Haskell type classes and GHC extensions.

I think the title is extremely misleading, at least based on my interpretation of the abstract. I thought the title meant: "if your untyped PCF program is well-behaved, then there is some way to add type annotations to yield a well-typed program (presumably with the same behavior)." But abstract semes to really be saying that if you have a well-behaved function, then there is some well-typed function with extensionally equivalent behavior; note the lack of constraint on the form of the typed program text and its relation to the untyped text.

test

2005-03-26T17:15:00.000-08:00

My first post. Woot.

Catching up on West Wing. This one has Castro. Lots of Cuban-sounding music in the background. Its kind of like watching The Godfather Part II