The Alien Tongue

Some notes on continuation-passing style

2012-01-21T01:18:00.000-08:00

I've been going over the CPS transform lately, and wrote some notes on how to use the transform to compile to C, stackless style.

dark.nightmare.com/rushing/factcps/

thinking about an llvm backend, again

2012-01-09T17:30:00.000-08:00

I've been very happy with my other project that uses LLVM as the backend for a compiler.
I've also learned a lot about LLVM's IR design.

I can't help but think that it might only take a week or two to write a back end for Irken.
However, there are a few issues.

My CPS output assumes that each insn has a result that is put into a register. This doesn't fit LLVM's model, which assumes that arguments to insns can be either an immediate or a register. In fact, they do not allow you to put an immediate into a register.
LLVM doesn't like gcc's goto-label feature. I think they implemented it reluctantly, because it doesn't fit the SSA model very well. The majority of funcalls by Irken are to known functions, which translate to a branch to a known label. However, whenever higher-level functions are called, this leads to something like "goto *r0;" in C, which turns into an indirectbr insn in LLVM. It implements this using a gigantic phi/indirectbr table at the very end of the function. Maybe this isn't really a problem - it just looks bad.
The extremely useful %cexp primitive would go away! There's something to be said for being able to refer to OS constants, OS functions, macros, etc... with such a simple mechanism. I'd probably just have to let it go, and force users to write stubs.

I think #1 can be dealt with by adding an extra pass that translates between the two representations. (maybe I should revisit the CPS==SSA paper?)

Another approach might be to use an annoying alloca/store/load sequence and hope that mem2reg does a good job?

Irken status, LLVM bitcode

2012-01-02T00:15:00.000-08:00

This is just a quick note that the Irken project has not died, only gone into a temporary hibernation.
When in the course of history it becomes necessary to earn a living...

Anyway, I have some tangentially related comments about LLVM.
My current employer is interested in maybe doing a little LLVM JIT work, wherein my experience with compilers may prove useful. A nice side effect for me is that I finally get to play around a bit with LLVM, something which I carefully avoided while working on Irken.

My first reaction was to pick up llvm-py, which looked like a fairly complete interface to the various libraries that make up the llvm system.

Big Mistake. It doesn't build any more. It's only a little over a year old. The last release of llvm-py was for LLVM 2.8rc2. I am now running 3.0.

Here's the problem: the LLVM API's are constantly changing. And that's a good thing, really. But since those C++ API's are the only well-supported interface to the system, it's a moving target.

There are three main options for a compiler writer who wants to target LLVM. The first is to use the C++ API. (or you could use the completely undocumented and incomplete C interface).

The second option is to write llvm assembly. This is not a bad option, but will be slower because of the need to parse the assembly.

The third is to write llvm 'bitcode'. I thought this was probably the right approach. Bitcode is a binary representation of the LLVM IR language, it seems that it would be likely to change much more slowly than the library interfaces.

The problem is that the person who designed the bitcode file format was on meth at the time. This has got to be one of the most evil formats I've ever seen. I think they were trying to make the resulting file as small as possible, but at the expense of counting every bit. (perhaps an early LLVM project flew on a space probe?) Just to give you an idea, 3 and 4-bit integers (not aligned on any boundary) are a common field type. And not just that, but some of the fields are variably sized, starting at 2 bits and going up. Symbols are represented using 6-bit characters. Also, the concept of 'bitstream' is taken very literally, the bits in a file are viewed as if it were one large integer, starting from the LSB. This is actually an elegant approach, but it is completely different from every other file format or network protocol. I had to continually resist using common parsing patterns with it. There's also a compression-like method of 'abbreviating' common record types. And after all that work to save bits, at the end of every block the bit stream is aligned to 32 bits!

Ok, got that off my chest.

My sense is that nobody uses the bitcode format because of this (the only other implementation I could find was in Haskell, and was also impenetrable because Everything Is A Monad, You Know). Most people just succumb to the pressure to write against the C++ API, and will then spend the rest of their lives reading the llvm-dev list to keep track of the changes.

I have mostly decoded the format, and I think I could actually output it for a compiler.
But I think I'll split the difference and start out by outputting llvm assembly to start with. If the day comes when I need to shave some of the 10MB off the resulting .so file, and maybe speed things up, I'll revisit the bitcode issue.

In the meanwhile I've had a whack at using Cython's C++ support to make a minimal interface to LLVM where I can feed either llvm assembly or bitcode to the JIT and run it.

git, github, clang

2011-05-23T17:15:00.000-07:00

I've imported my svn history into git, and published the whole thing on github:

https://github.com/samrushing/irken-compiler/

Still trying to grok git and github, there'll probably be a stall for a week or so.

In the meanwhile, I have interesting news: I was able to take out all the 'nested functions' which relied on a gcc extension. I resisted this for a long time because early testing had shown that declaring the 'registers' as local register variables in the main function was a huge win.

After a quick test the other day, I found that moving everything out to global variables has no visible impact on performance. I don't know if this is because of improvements in gcc & llvm, or if I just wasn't trying a large enough program.

That means I'm now able to compile the output with clang, rather than relying on llvm+dragonegg, which can be much more annoying to build, install, and use.

The good news continues: although the performance of the generated code is identical (maybe a tiny bit faster), the compilation time has been cut quite significantly. On my machine an LLVM -O2 compile dropped from 18m to 8m. The -O0 compile time is even sweeter, about 3s, which is actually faster than Irken itself, which hovers right around 5s to self-compile. So a roughly 10s edit-compile cycle will definitely speed the development of Irken up.

Now the bad news. The no-nested-funs version causes 'as' on snow leopard to take a lunch break. It actually nails the CPU for 10 or 15 minutes before finally emerging as if nothing was wrong. No problems on FreeBSD 7.3 with gcc-4.5.3, though. This could be a significant annoyance, since I expect many people trying out Irken would prefer to do so with a stock compiler.

More bad news: clang-2.9 crashes when fed Irken's self-compiled output. I was going to file a bug against it, but when I checked out the svn version and built it the problem was gone. Sigh.

This is why I'm trying to figure out how to make branches on github, since it'd be nice to maintain both versions for a while until these issues are ironed out. I have made a local branch called 'no-nested-funs', I just haven't figured out how to publish it on github.

nested datatypes, 2-3 trees, numerical encoding

2011-05-15T15:59:00.000-07:00

This paper by Hinze & Paterson discusses the use of 'nested datatypes' to implement 2-3 trees, but in a way that uses the type system to automatically handle the invariants. A blog post from Mark Chu-Carroll is a bit easier to follow. Here's his example of a sequence encoded as a 2-3 tree (in Haskell):

data Tree t = Zero t | Succ (Tree (Node t))
data Node s = Node2 s s | Node3 s s s

Each level of the tree contains sub-trees that are 'one less' via the numeric encoding scheme.

This sent me back to Okasaki's book, where I'm finally starting to grok those last two chapters.  This bizarre mingling of numerical encoding and data structures lights a fire in the parts of my brain dedicated to data structures.  If feel as if I could automatically see the relationship between red-black trees, 2-3 trees, and binary number representations.... if only I could double my IQ.

I have this cool puzzle called the 'Spin-Out', which is actually a physical demonstration of the properties of Gray Codes.  It seems to me that Gray Codes and balanced trees should be a natural fit.

Unfortunately, I can't experiment with any of these ideas in Irken (or OCaml, or SML) because the nested datatypes require polymorphic recursion.

Type inference with polymorphic recursion is undecidable.  Haskell allows it only if the user provides a manual type signature.  I'm guessing this is impossible (i.e., unsafe) with SML/OCaml because of the presence of assignment?  Could such a feature safely be used with functions that the compiler can verify are pure?

DOOM DOOM DOOM (a coro/thread kqueue-based scheduler)

2011-04-27T00:36:00.000-07:00

I've created a new sub-project, code-named 'doom', for the coroutine-based cooperative threading system. It uses kqueue(), of course. Because it's better. It wouldn't be too hard for someone from linux-land to make a version based on epoll.

In the doom directory, you'll find a simple http demo, and the obligatory echo server.

Exception handling certainly makes the code look a lot nicer.

I'm the best at space.

exception handling, take two

2011-04-22T15:55:00.000-07:00

A bit tricky, but I found a way to implement try/except almost completely with defmacro. I needed to add some extra typechecking around raise and try to ensure that all exception types are monomorphic. I achieved this by having the compiler keep a global map of exception-name => tvar. Seems to work...

While working on this I learned that the Scheme-style call/cc is not really type safe, and I need to use the SML version. The main difference is the protocol - SML's callcc requires the use of a throw procedure since the continuation needs to carry type information:

(define (callcc p) : (((continuation 'a) -> 'a) -> 'a)
  (p (getcc)))

(define (throw k v)
  (putcc k v))

;; -*- Mode: Irken -*-

(include "lib/core.scm")
(include "lib/random.scm")

;; We use polymorphic variants for exceptions.
;; Since we're a whole-program compiler there's no need to declare
;; them - though I might could be convinced it's still a good idea.
;;
;; Exception data must be monomorphic to preserve type safety.
;;
;; <try> and <raise> are implemented as macros, with one extra hitch:
;;  two special compiler primitives are used to check that exception
;;  types are consistent: %exn-raise and %exn-handle

(define (base-exception-handler exn) : ((rsum 'a) -> 'b)
  (error1 "uncaught exception" exn))

(define *the-exception-handler* base-exception-handler)

(defmacro raise
  (raise exn) -> (*the-exception-handler* (%exn-raise #f exn))
  )

(defmacro try
  ;; done accumulating body parts, finish up.
  (try (begin body0 ...) <except> exn-match ...)
  -> (callcc
      (lambda ($exn-k0)
        (let (($old-hand *the-exception-handler*))
          (set!
           *the-exception-handler*
           (lambda ($exn-val)
             (set! *the-exception-handler* $old-hand)
             (throw $exn-k0
              (%exn-handle #f $exn-val
               (match $exn-val with
                 exn-match ...
                 _ -> (raise $exn-val))))))
          (let (($result (begin body0 ...)))
            (set! *the-exception-handler* $old-hand)
            $result))))
  ;; accumulating body parts...
  (try (begin body0 ...) body1 body2 ...) -> (try (begin body0 ... body1) body2 ...)
  ;; begin to accumulate...
  (try body0 body1 ...)                   -> (try (begin body0) body1 ...)
  )

(define (level0 x)
  (try
   (level1 x)
   except
   (:Level0 x) -> (:pair "level 0" x)
   ))

(define (level1 x)
  (try
   (level2 x)
   except
   (:Level1 x) -> (:pair "level 1" x)
   ))

(define (level2 x)
  (try
   (level3 x)
   except
   (:Level2 x) -> (:pair "level 2" x)
   ))

(define (level3 x)
  (try
   (match x with
     0 -> (raise (:Level0 x))
     1 -> (raise (:Level1 x))
     2 -> (raise (:Level2 x))
     3 -> (raise (:Level3 x))
     4 -> (:pair "no exception!" 99)
     _ -> (raise (:Bottom x))
     )
   except
   (:Level3 x) -> (:pair "level 3" x)
   ))


(printn (level0 0))
(printn (level0 1))
(printn (level0 2))
(printn (level0 3))
(printn (level0 4))
(printn (level0 5))

exception handling with defmacro

2011-04-06T17:15:00.000-07:00

I've started work on a coroutine/thread scheduler, code named "Doom". Doing some socket I/O has finally snapped my 'missing feature' threshold - I really need exception handling to do it right.

Here's my first attempt. The basic syntax is (try <body> except <exception-patterns>).

If this works, it'll be a great example of the huge advantages of the lisp syntax and macros - no changes made to the compiler to support it!

;; -*- Mode: Irken -*-

(include "lib/core.scm")
(include "lib/random.scm")

;; can we implement an exception system using the macro system?
;; XXX eventually we'll need to change call/cc to swap out exception
;;  handlers, which probably means making a 'modern' call/cc with
;;  dynamic-wind, etc.

(define (base-exception-handler exn)
  (error1 "uncaught exception" exn))

(define *the-exception-handler* base-exception-handler)

(define (raise exn)
  (*the-exception-handler* exn)
  )

;; what kind of values do we want for exceptions, and how they're caught/compared?
;; python: started with strings, went to objects of the Exception class.
;; scheme: SRFI-12 includes something that looks like property lists?
;; sml: string refs? (in sml/nj according to CwC)
;; ocaml: declared exception datatypes.
;; [alternate for ocaml: http://dutherenverseauborddelatable.wordpress.com/downloads/exception-monads-for-ocaml/
;;  sounds a little like my 'fourth idea']

;; my first temptation is to just use symbols, and stay simple

;; second idea is to use a record, which theoretically gives you the
;;   ability to attach other kinds of data, which could be very
;;   convenient. Example: (raise BadFD) => {exception='BadFD ...}

;; third idea: hardcore - define a global exception type, force the user to
;;   extend it.  [could be made easier by compiler hacks that allow you to
;;   extend the type anywhere in the source?].  Code would have to wildcard
;;   exceptions it doesn't know about?  [or is that the definition of handing
;;   it upstream?]

;; fourth idea: use records (or polymorphic variants) to define unique
;;   exception names *and* types.  For example: (raise (BadFD
;;   current-fd)) would type as {BadFD=int ...}  this would make it
;;   more like the SRFI-12 property-list thing (unless I misunderstand
;;   what SRFI-12 is all about).  Hmmm... maybe we could extend the
;;   exception handler by extending the record?

;; It'd be nice if the type system can tell us what exceptions are possible
;;   at any given point in the code... is this maybe impossible due to the
;;   dynamic (vs static/lexical) nature of exception handling?

;; the more I think about the 'fourth idea' the less reason I see to
;;  restrict the type of exceptions.  Syntax-wise, the following macro
;;  does not enforce any restrictions.  It's possible though that only
;;  the polymorphic-variant-scheme will survive type checking.

;; this is the first time I've tried to 'accumulate' pieces in a macro.
;; it's possible that there's a better idiom that I just haven't discovered yet.
;; should really look to see how the scheme folks do this (or do they just avoid
;; it all by wrapping everything in verbose s-expressions).

(defmacro try
  ;; done accumulating body parts, finish up.
  (try (begin body0 ...) <except> exn-match ...)
  -> (let (($old-hand *the-exception-handler*))
       (set!
        *the-exception-handler*
        (lambda ($exn)
          (set! *the-exception-handler* $old-hand)
          (match $exn with
            exn-match ...
            _ -> (raise $exn))))
       (let (($result (begin body0 ...)))
         (set! *the-exception-handler* $old-hand)
         $result))
  ;; accumulating body parts...
  (try (begin body0 ...) body1 body2 ...) -> (try (begin body0 ... body1) body2 ...)
  ;; begin to accumulate...
  (try body0 body1 ...)                   -> (try (begin body0) body1 ...)
  )

(define (random-barf)
  (if (= (logand (random) 1) 1)
      (raise (:OtherException 99))
      7))

(define (thing)
  (try
   (let loop ((n 0))
     (if (= n 100)
         (raise (:MyException 12))
         (begin
           (random-barf)
           (loop (+ n 1)))))
   except
   (:MyException value) -> value
   (:OtherException _)  -> 9
   ))

(thing)

Here's what the macro expansion looks like for thing:

(define (thing)
  (let (($old-hand *the-exception-handler*))
    (begin
      (set!
       *the-exception-handler*
       (lambda ($exn)
         (begin
           (set! *the-exception-handler* $old-hand)
           (%fatbar
            #f
            (%nvcase
             nil
             $exn
             (MyException OtherException)
             (1 1)
             ((let-splat
               ((m9 (%nvget (:MyException 0 1) $exn)))
               (let_subst (value m9) value))
              9)
             (%match-error #f))
            (raise $exn)))))
      (let (($result
             (letrec
                 ((loop
                   (function loop (n) (if (= n 100) (raise (:MyException 12)) (loop (+ n 1))))))
               (loop 0))))
        (begin (set! *the-exception-handler* $old-hand) $result)))))

same-fringe demo

2011-03-23T17:55:00.000-07:00

This demonstrates how to use generators to solve the same-fringe problem.

Also, I found a minimalist way of building binary-tree literals using defmacro.

;; -*- Mode: Irken -*-

(include "lib/core.scm")

(datatype btree
  (:node (btree 'a) (btree 'a))
  (:leaf 'a))

(defmacro btree/make
  (btree/make (l r)) -> (btree:node (btree/make l) (btree/make r))
  (btree/make x)     -> (btree:leaf x))

(define t0 (literal (btree/make ((0 ((1 (2 (3 4))) 5)) (((6 7) ((8 (9 10)) 11)) ((12 (((13 14) 15) (16 17))) (18 19)))))))
(define t1 (literal (btree/make (((0 ((1 2) 3)) (((4 5) (((6 7) 8) (9 10))) ((11 ((12 13) 14)) ((15 (16 17)) 18)))) 19))))
(define t2 (literal (btree/make (((0 ((1 2) 3)) (((4 5) (((6 7) 8) (9 10))) ((88 ((12 13) 14)) ((15 (16 17)) 18)))) 19))))

(define btree/inorder
  p (btree:leaf x)   -> (begin (p x) #u)
  p (btree:node l r) -> (begin (btree/inorder p l) (btree/inorder p r) #u))

(define (btree/make-generator t)
  (make-generator
   (lambda (consumer)
     (btree/inorder
      (lambda (x) (consumer (maybe:yes x)))
      t)
     (forever (consumer (maybe:no))))))

(define (same-fringe t0 t1 =)
  (let ((g0 (btree/make-generator t0))
        (g1 (btree/make-generator t1)))
    (let loop ((m0 (g0)) (m1 (g1)))
      (match m0 m1 with
        (maybe:yes v0) (maybe:yes v1)
        -> (if (= v0 v1)
               (loop (g0) (g1))
               (print-string "NOT equal\n"))
        (maybe:no) (maybe:no)
        -> (print-string "equal\n")
        _ _ -> (print-string "unequal size\n")))))

(same-fringe t0 t1 =)
(same-fringe t0 t2 =)

win32 binary

2011-03-20T18:09:00.000-07:00

I've tried to make the bootstrapping script work on win32, and I think for the most part I've succeeded. There are issues with mac-specific flags making it into the bootstrap file that I still need to work out.

I used mingw, but I suspect other gcc binaries will work, too. A 32-bit executable is now available, which may ease the bootstrapping process for some.

description of the compiler and runtime

2011-03-17T18:58:00.000-07:00

I've started on a 'HACKING.txt' document describing the compiler and runtime.
It should be enough to get folks started on understanding the source.
Feedback appreciated!

-Sam

self-hosted distribution

2011-03-17T16:15:00.000-07:00

I've finally put together a 'real' self-hosted distribution.

The tarball is a little bigger - even though I removed all the python code. The reason is that I have to distribute a pre-compiled version of self/compile.c so that the compiler can be bootstrapped.

Enjoy, and feedback appreciated.

Here's the text of the README:

This is the initial release of the self-hosted compiler.

It's still in a very unpolished state, but you can use it to bootstrap itself.

Just run the script "util/bootstrap.py":

$ python util/bootstrap.py

Which does the following:
1) run gcc on the distributed version of self/compile.c
2) this binary will be used to recompile the compiler.
3) that binary will recompile the compiler again.
4) the output from steps 2 and 3 are compared, they should be identical.

If you're happy with the resulting compiler, you can compile an optimized
version of self/compile.c, but be warned - you'll need a lot of memory and
a lot of time.

I am using dragonegg for optimized builds, and that seems to take about a GB
of memory, and 18 minutes to build.  It's important to use '-O2', not '-O',
because '-O' takes 53GB of memory and hours to compile.

Very little documentation exists yet, try 'lang.html' for a brief tutorial.
The best way to get familiar with the language is to read the source code in
the 'self' directory, and browse over the files in "tests".

-Sam

C compiler issues

2011-03-09T15:03:00.000-08:00

As I came closer to completing the Irken implementation, I noticed that my edit-compile cycle was taking longer and longer. And by that, I don't mean a linear change. At some point a threshold was crossed, such that compiling an optimized binary could take nearly an hour with dragonegg, and much longer with gcc, consuming over 17G of memory while at it!

After doing some tests, I've identified at least one of the causes: my varref and varset functions.

A couple of years ago, the compiler output for a varref insn looked like this:

r0 = lenv[1][1][1][0];

Where the variable we are referencing is 3 levels up and at the 0 index. (i.e., a De Bruijn index of (3,0)).

I noticed that I could write an inline lexical function, varref(), that did this with a loop:

r0 = varref (3, 0);

... which is much cleaner. With -O, gcc, llvm, and dragonegg were all unrolling the constant loop and creating code that was identical to the first version.

I didn't notice the cost of this convenient feature until my program size got large enough... the compiler sources, when using the inline functions, take 5X as long to compile -O as the first version.

Also, a 'platform' note: I work on OS X, where the stock compiler is still /usr/bin/gcc. I did some timings for a non-optimized build and discovered that the stock gcc is over twice as fast as either my hand-built gcc-4.5.0, or dragonegg. So for quick edit-compile cycles, I switched back to the stock version. Though it'd be nice to know why the version from Apple is so much faster...

Self-hosted!

2011-03-09T14:50:00.000-08:00

[assumed skynet joke here]

A few days ago, after many weeks of frenetic work, the new self-hosted Irken compiled itself. There's still a lot of work to do, but this major milestone has been reached. The compiler passes the stage1==stage2 test, and I'm now concentrating on various features still missing compared to the python compiler. Also, the edit-compile cycle is still pretty slow, because both the compiler and gcc are slower than need be. Once I have these issues solved and some rudimentary error reporting (the current error reporting might be described as medieval) I'll make an official release.

I'm also thinking about how to best re-package the system, considering orphaning the python development branch, and starting a whole new repository for the self-hosted system.

In the meanwhile, if there's anyone out there that would just like to see it compile itself, I rolled a demo tarball up. Enjoy, and feedback is much appreciated!

progress on self-hosting

2011-02-14T17:20:00.000-08:00

Today the self-hosted Irken compiled its first complete program, all the way through substituting into the header template file, and compiling via gcc. A nice feeling.

;; -*- Mode: Irken -*-

(datatype list
  (:nil)
  (:cons 'a (list 'a))
  )

(defmacro list
  (list)         -> (list:nil)
  (list x y ...) -> (list:cons x (list y ...)))

(define (+ a b)
  (%%cexp (int int -> int) "%0+%1" a b))

(define length
  () -> 0
  (_ . tl) -> (+ 1 (length tl)))

(length (list 1 2 3))

I also finally got around to checking in the changes from the last couple of weeks, too much slacking off there.

Y combinator in Irken

2011-02-02T21:22:00.000-08:00

The second version requires recursive types.

;; -*- Mode: Irken -*-

;; See http://en.wikipedia.org/wiki/Fixed_point_combinator

(include "lib/core.scm")

(define (Y f)
  (lambda (x)
    ((f (Y f)) x)))

(define (factabs fact)
  (lambda (x)
    (if (= x 0)
        1
        (* x (fact (- x 1))))))

(printn ((Y factabs) 5))

;; and http://caml.inria.fr/pub/docs/u3-ocaml/ocaml-ml.html#toc5
;; let fix f' = let g f x = f' (f f) x in (g g);;
;; let fact = fix fact' in fact 5;;

(define (Y2 f1)
  ;; the '^' prefix tells the compiler not to inline this function
  ;;  which in this particular case would never terminate...
  (define (^g f)
    (lambda (x)
      (f1 (f f) x)))
  (^g ^g))

(define (fact1 fact x)
  (if (= x 0)
      1
      (* x (fact (- x 1)))))

(printn ((Y2 fact1) 5))

The function ^g has type

μ(A, (A->b))->(c->d)

recursive types, unification, sharing

2011-02-02T17:31:00.000-08:00

I'm having trouble with recursive types in my type reconstruction (type inference) algorithm, some kind of combinatorial explosion. I think there are multiple triggers for this: at each call to unify(), I'm running a complete apply-subst(), rather than a level at a time. For the massive types generated by my OO code, this means lots of wasted, repeated work.

But of course there's even more going on. I think my code that detects recursive types is not working as well as it should, and I think the cause is the lack of 'sharing'. Remy/Pottier use a different style of unification, that involves preserving shared elements of types, and I think this where I'm screwing up: because parts of types are being copied, I'm missing links between identical parts of the graph.

I found a nice presentation from Remy describing "Core ML", that explains this in (accented) English, rather than a relentless flurry of LaTeX: "Using, Understanding, and Unraveling The OCaml Language: From Practice to Theory and vice versa".

The constraint-oriented solver gave me recursive types for free, (because its output types are naturally graphs), but I'm really hoping to avoid going back to that code, because it's much slower and I frankly don't understand it as well as I'd like. Maybe I can pull out just the multi-equation unification stuff, and get back recursive types.

simple approach to OO and exploding equirecursive types

2011-01-31T15:54:00.000-08:00

While trying to port the graph algorithms (Kosaraju's algorithm / topological sort) I got to a point where I really wanted some imperative set/map objects, so I combined a 'class' using alists (for map) and lists (for set) with a few 'methods' put into records.

After playing with it for a while, I found a fairly neat way to do method calls and object layouts:

(define (set-class)

  (define (in self x)
    (let loop ((l self.list))
      (match l with
        () -> #f
        (hd . tl) -> (if (eq? hd x)
                         #t
                         (loop tl)))))
  (define (add self x)
    (if (self::in x)
        #u
        (set! self.list (list:cons x self.list))))
  
  (define (get self)
    self.list)

  (let ((methods {in=in add=add get=get}))
    (define (new l)
      {o=methods list=l})
    new
    ))

This leads to an efficient object layout very similar to Python's: one slot identifies the object type, the other slots hold instance variables. To support this, I added a reader hack that translates

(var::method arg0)

into

(var.o.method var arg0)

The result is something that I'm pretty sure will act just like Python's duck typing... for example a generic output function may call the 'write' method on an object, and its type will reflect that need: for a write method of a particular signature. Instead of 'o' I'd probably use a slot name like '__methods__'... this suggests standard repr/str interfaces, and the other duck-typed protocols that Python makes such good use of.

Pretty cool, huh?

Well, as soon as I tried actually using this code, the inferencer fell to its knees. I'm not kidding. It went from a 30 second compile to a 20 minute compile, eating up over a GB of memory. Hmmmm... looks like my quick-and-easy implementation of μ-types has problems, surprise. I think I was 'asking for it' by calling each method with a 'self' argument... each method call has to unify the object type twice. And storing objects inside of other objects doesn't help, either.

Back to the textbook. I'm hoping that reading this paper again will help.

self-hosting dilemma

2011-01-26T19:08:00.000-08:00

I have nearly the whole compiler rewritten in itself. I've saved one of the nastiest bits for last, the inliner. I've been planning on a new design for the inliner - rather than just copying the Python code. So of course, what happens in this late stage? A bug in the inliner!

The program types correctly if inlining is turned off, but fails if it's turned on. This is a great example of the gains to be had by typing both before and after phases of the compiler - but unfortunately in this case it means I have to fix a bug in some code that I intend to throw away as soon as it works!

Theoretically I could just turn off inlining until I'm done, and then write the new inliner in the self-hosted environment - but I can't be absolutely sure that it's not a more complex interaction between the typer and the inliner.

bloated C compilers

2011-01-20T23:15:00.000-08:00

I've been testing Irken out on my netbook (a Samsung NC10), and discovered a big problem with feeding Irken's output to gcc.

When I tried to compile the self-hosted Irken with -O, the netbook fell on its knees. After about 15 minutes, I decided to look into it... why hadn't the compile finished yet?

The input Irken source was about 60kB, which exploded into a 920kB C file. The C output is actually pretty low-level stuff, so it's probably comparable to a 300kB hand-written C file. But let's just call it 1MB and move on...

The gcc (version 4.4) process had eaten 1.4GB of virtual memory, so it was paging on the netbook.

That's 1600X the size of the C input file. It's nearly 25,000X the size of the Irken input. Wow.

So as a test I installed dragonegg and gcc-4.5. Quite a difference. The dragonegg compile held at 143MB for most of the compile, and peaked at around 200MB. Only 226X the size of the C input, and a mere 3400X the size of the Irken input.

But what's an order of magnitude between friends?

The datatype + record idiom

2011-01-20T15:27:00.000-08:00

One of the difficult decisions when working on a compiler is how to represent nodes. There's a strain between the pure-functional and object-oriented styles that can be really painful. I'm certainly not happy with the way I did it in Irken - a combination of pure-functional class with a bunch of attribute hacks.

While working to solve the same problem in self-hosted Irken, I've come across a pretty good idiom that captures the best of both worlds; giving me exactly the right combination of strong typing, mutability, and flexibility that I need.

The trick is to use a record as the node representation, but inside it put a slot that holds all the strongly-typed metadata that you need. Here's what it looks like so far:

;; node type holds metadata related to the node,
;;  but sub-nodes are held with the record.
(datatype node
  (:varref symbol)
  (:varset symbol)
  (:literal literal)
  (:cexp type string)
  (:nvcase symbol (list symbol))
  (:sequence)
  (:if)
  (:function symbol (list symbol)) ;; name formals
  (:call)
  )

(define node-counter (make-counter 0))

;; given a list of nodes, add up their sizes (+1)
(define (sum-size l)
  (fold (lambda (n acc) (+ n.s acc)) 1 l))

(define (node t subs)
  {t=t subs=subs s=(+ (sum-size subs) 1) id=(node-counter.inc) type=(type:base '?)}
  )

(define (node/varref name)
  (node (node:varref name) '()))

(define (node/varset name val)
  (node (node:varset name) (LIST val)))

(define (node/literal lit)
  (node (node:literal lit) '()))

(define (node/cexp type template args)
  (node (node:cexp type template) args))

(define (node/sequence subs)
  (node (node:sequence) subs))

Note how the node constructor initializes the other slots in the record. The interesting one for me today is the type field. This is later filled in by the typer, succinctly:

(define (type-of exp tenv)
  (let ((t (type-of* exp tenv)))
    (set! exp.type t)
    t))

(define (apply-subst-to-program n)
  (set! n.type (apply-subst-to-type n.type))
  (for-each apply-subst-to-program n.subs))

(define (type-program node)
  (let ((t (type-of node (alist/make))))
    (apply-subst-to-program node)
    t))

We've still preserved the strong typing of nodes, though: here's what a typical node-visiting function looks like:

(define (compile tail? exp lenv k)

  ;; override continuation when in tail position
  (if tail?
      (set! k (cont (k/free k) gen-return)))
  
  (match exp.t with
    (node:literal lit)           -> (c-literal lit k)
    (node:sequence)              -> (c-sequence tail? exp.subs lenv k)
    (node:if)                    -> (c-conditional tail? exp lenv k)
    (node:function name formals) -> (c-function name formals (car exp.subs) lenv k)
    (node:varref name)           -> (c-varref name lenv k)
    (node:varset name)           -> (c-varset name (car exp.subs) lenv k)
    (node:cexp sig template)     -> (c-cexp sig template exp.subs lenv k)
    (node:call)                  -> (c-call tail? exp lenv k)
    _ -> (begin (pp-node exp 0) (error1 "NYI" exp))
    )
  )

Note how metadata that's specific to each node type is stored in the datatype (exp.t), but generic info (like the list of sub-nodes, or the size) is stored in the record.

making the match compiler smarter

2011-01-18T17:34:00.001-08:00

The match compiler developed a little problem. It's amazing that it didn't show up earlier. As described in chapter 5 of Peyton-Jones' book, "The Implementation of Functional Programming Languages", certain 'obvious' or 'optimized' pattern matches actually compile to worse code.

The following function is from the book (pg 88), and is similar to an implementation of map2.

(define demo
  () ys -> (:A ys)
  xs () -> (:B xs)
  (x . xs) (y . ys) -> (:C x xs y ys)
  )

The second match clause will actually compile more efficiently if you use (x . xs) rather than a variable, because the match compiler knows in this case you're matching a cons cell. (it avoids the 'mixture rule' and uses only the 'constructor rule').

Regardless of this optimization, I ran into a more significant issue. If I use xs, I get an 'incomplete match' error, because the code generated for this match has to examine the first list twice - in the first test it covers only the nil case. In the second test, it covers the cons case, but has an 'else' clause that generates a match error.

Here's what the node tree looks like:

290 L    primapp [33] ('%%fatbar', None) ? 
262 L      nvcase [5] ('list', ['nil']) ? 
258 L        varref [1] m0_7_i0 ? 
260 L        primapp [2] ('%vcon/A/1', None) ? 
259 L          varref [1] m1_8_i1 ? 
261 L        primapp [1] ('%%fail', None) ? 
289 L      primapp [27] ('%%fatbar', None) ? 
267 L        nvcase [5] ('list', ['nil']) ? 
263 L          varref [1] m1_8_i1 ? 
265 L          primapp [2] ('%vcon/B/1', None) ? 
264 L            varref [1] m0_7_i0 ? 
266 L          primapp [1] ('%%fail', None) ? 
288 L        nvcase [21] ('list', ['cons']) ? 
268 L          varref [1] m0_7_i0 ? 
286 L          let_splat [18] [{m2_9_i0}, {m3_10_i0}] ? 
270 L            primapp [2] ('%nvget/list/cons/0', None) ? 
269 L              varref [1] m0_7_i0 ? 
272 L            primapp [2] ('%nvget/list/cons/1', None) ? 
271 L              varref [1] m0_7_i0 ? 
285 L            nvcase [13] ('list', ['cons']) ? 
273 L              varref [1] m1_8_i1 ? 
283 L              let_splat [10] [{m4_11_i0}, {m5_12_i0}] ? 
275 L                primapp [2] ('%nvget/list/cons/0', None) ? 
274 L                  varref [1] m1_8_i1 ? 
277 L                primapp [2] ('%nvget/list/cons/1', None) ? 
276 L                  varref [1] m1_8_i1 ? 
282 L                primapp [5] ('%vcon/C/4', None) ? 
278 L                  varref [1] m2_9_i0 ? 
279 L                  varref [1] m3_10_i0 ? 
280 L                  varref [1] m4_11_i0 ? 
281 L                  varref [1] m5_12_i0 ? 
284 L              primapp [1] ('%%match-error', None) ? 
287 L          primapp [1] ('%%match-error', None) ?

...and in a pseudo-python:

if nil(m0):
  A()
elif nil(m1):
  B()
else:
  if cons(m0):
    if cons(m1):
      C()
    else:
      raise Error
  else:
    raise Error

The problem is that the match is actually exhaustive, because the nil case was examined already. %%match-error in Irken is actually a kind of sentinel, the back end doesn't know how to compile it, so you can't actually compile code that's not exhaustive.

To fix this, I added an extra pass to the analysis phase that builds environments of 'already tested alternatives' for each nvcase variable. This actually killed two birds with one stone. In many cases, the innermost nvcase test is completely unnecessary - for this example, we've already tested for nil, and actually testing for a cons is redundant. In this case we simply remove the nvcase test (and the erroneous match-error), and return the body.

The code then generated for map is closer to what a human might write:

pseudo-python:

if nil(m0):
  A()
elif nil(m1):
  B()
else:
  C()

RTL:

0 = constructed [] 1
   1 = constructed [] 0
   2 = fatbar 'fatbar_0' []
       2 = move [0, None] 'm0_7_i0'
       2 = nvcase 'list' [2]
           2 = move [1, None] 'm1_8_i1'
           2 = primop [2] ('%make-tuple', 'A', 0)
               return [2] None
               fail [] ('fatbar_0', 0)
           return [2] None
       2 = fatbar 'fatbar_1' []
           2 = move [1, None] 'm1_8_i1'
           2 = nvcase 'list' [2]
               2 = move [0, None] 'm0_7_i0'
               2 = primop [2] ('%make-tuple', 'B', 1)
                   return [2] None
                   fail [] ('fatbar_1', 0)
               return [2] None
           2 = move [0, None] 'm0_7_i0'
           2 = primop [2] ('%vget', '0')
           3 = move [0, None] 'm0_7_i0'
           3 = primop [3] ('%vget', '1')
           4 = move [1, None] 'm1_8_i1'
           4 = primop [4] ('%vget', '0')
           5 = move [1, None] 'm1_8_i1'
           5 = primop [5] ('%vget', '1')
           6 = move [2, None] 'm2_9_i0'
           7 = move [3, None] 'm3_10_i0'
           8 = move [4, None] 'm4_11_i0'
           9 = move [5, None] 'm5_12_i0'
           6 = primop [6, 7, 8, 9] ('%make-tuple', 'C', 2)
               return [6] None
           return [2] None
       return [2] None

progress on self-hosting

2011-01-14T16:52:00.000-08:00

Making excellent progress on self-hosting. Today the baby irken compiler spat up its first real code:

beast:irken rushing$ self/backend

-- reader --
(((lambda (x y) x) 3 4))

-- macros --
((function lambda (x y) x) 3 4)

-- node tree --

5 call
  2 function lambda (x y)
    1 varref x
  1 literal {u1 3}
  1 literal {u1 4}

-- RTL --

0 env 2 
1 lit {u1 3}
- stor 1 1 0 0 
1 lit {u1 4}
0 stor 1 1 0 1 
1 close lambda
  0 ref 0 0 
  - ret 0
0 tail 1 0 
- ret 0

-- C output --
  r0 = allocate (TC_TUPLE, 3);
  r1 = (object *) 7;
  r0[2] = r1;
  r1 = (object *) 9;
  r0[3] = r1;
  // def lambda
  goto L0;
  FUN_lambda:
    r0 = varref (0, 0);
    PXLL_RETURN(0);
  L0:
  r1 = allocate (TC_CLOSURE, 2);
  r1[1] = &&FUN_lambda; r1 = lenv;
  r0[1] = r1[2]; lenv = r0; goto *r1;
  PXLL_RETURN(0);
#u
{total ticks: 1870544 gc ticks: 0}

format macro

2011-01-13T17:34:00.000-08:00

How cool is this?

;; -*- Mode: Irken -*-

(include "lib/core.scm")
(include "lib/pair.scm")
(include "lib/string.scm")

(defmacro format
  (format)                       -> (list:nil)
  (format (<int> n) item ...)    -> (list:cons (int->string n) (format item ...))
  (format (<char> ch) item ...)  -> (list:cons (char->string ch) (format item ...))
  (format (<bool> b) item ...)   -> (list:cons (bool->string b) (format item ...))
  (format (<string> s) item ...) -> (list:cons s (format item ...))
  (format x item ...)            -> (list:cons x (format item ...))
  )

(print-string (string-join (format "testing" (int 1) (bool #t) (char #\A) "\n") " "))

beast:irken rushing$ tests/t_format
testing 1 #t A 
#u
{total ticks: 154666 gc ticks: 0}

Let me explain what's going on here. First, this is a macro definition. Macros are specified using a pattern language. To the left of each arrow is an input pattern - on the right is how that input will be transformed; before the code gets to the compiler (in other words, textual substitution).

Symbols surrounded by angle brackets are keywords - i.e., constant symbols. This is to distinguish them from variables. Every other name in the input pattern is bound to a variable, which can be used in the output form.

So the final line is transformed into this expression:

(print-string
 (string-join
  (list:cons "testing"
             (list:cons (int->string 1)
                        (list:cons (bool->string #t)
                                   (list:cons (char->string #\A)
                                              (list:cons "\n" (list:nil))))))
  " "))

This is actually a very simple macro, the patterns could be much more sophisticated, with embedded list structures and other keywords. But it creates the illusion of a variable-arity, variably-typed format function in a language that is strictly, statically typed and does not support variable arity! And of course other macros may be invoked. I'm sure I'll be expanding it as I work more on Irken's self-hosted back end.

Usually string formatting is an ugly part of any language - one of the classic problems with C is that the format language is ill-specified and dangerous. Only recently have compilers become smart enough to even do rudimentary checking...

I'm only just beginning to see what's possible with this macro system. I think the pattern matching syntax combines very nicely with the general pattern matching in the language.

record type declarations

2011-01-08T16:47:00.000-08:00

I finally needed to declare record types in some complex data structures, so I spent about 10 minutes extending the type parser to support it. The syntax is IMHO obvious.

I was pleasantly surprised to see how easy it was to add this feature, and all the testing went quickly and as expected. I think this is all a 'side-effect' (pun intended) of a relatively complete and sane type system.

Here's what the syntax looks like:

;; -*- Mode: Irken -*-

(include "lib/core.scm")
(include "lib/pair.scm")
(include "lib/string.scm")

;; declare a new datatype <thing> with only one alternative <t>
;;   which consists of an open record type... i.e., a record that
;;   may contain other unknown fields.
(datatype thing
  (:t {x=int y=char ...})
  )

(define (test1)
  (thing:t {x=3 y=#\b z=9})
  )

(define (test2)
  (thing:t {x=4 y=#\c z=#\a a=#t b=#f}))

;; make sure it still works with *no* extra fields
(define (test3)
  (thing:t {x=4 y=#\a}))

(printn (test1))
(printn (test2))
(printn (test3))

self-hosting

2010-12-19T19:00:00.000-08:00

Just a quick note to explain the relative silence here recently. I've started rewriting Irken in itself, originally just as an exercise, but now with a little enthusiasm. Unfortunately there's the danger of second-system syndrome, which I'm trying to keep under control by focusing on eliminating design flaws, and not introducing new features.

Currently, I have the reader, the transformer, and the macro packages written. Next up are the pattern match compiler and the typing engine. Should be pretty smooth sailing after that.

how about a pattern-matching version of "let loop"?

2010-12-19T18:52:00.000-08:00

I tend to use the "named let" idiom a lot, to me it's the most general form of looping construct, and is more readable than artificial constructs like 'do'.

I've begun to pine for a pattern-matching version of that construct, though. Not sure how well it would fly, but it would nicely generalize pattern matching. The reason I like 'named let' is because it lets you compactly introduce a recursive function while keeping the initial arguments in a place that makes the whole construct easier to understand.

Here's what the 'length' function looks like right now:

(define (length l)
  (define fun
    acc ()        -> acc
    acc (hd . tl) -> (fun (+ 1 acc) tl)
  (fun 0 l)))

And here's what it might look like with a pattern-matching 'named let' variant:

(define (length l)
  (let loop (0 l)
    acc ()        -> acc
    acc (hd . tl) -> (loop (+ 1 acc) tl)))

Visually I think it should be easy to distinguish from a normal let by the lack of extra levels of parens in the 'binding' spot... and this is in addition to the obvious -> symbols.

One bad side-effect of this is that let could no longer be done with defmacro (as in lib/derived.scm), and would require a special hack in the parser...

proper datatypes for bool and symbol

2010-11-03T17:06:00.000-07:00

I had previously been tagging user-immediates in a way that wasted tag-space and didn't match up with the obvious implementation used for things like bools and chars.

This is now fixed. A nice side-effect of this change is that matches against bools are now detected as complete or incomplete.

Incomplete matches are now detected earlier in the compiler, in a way that makes it easier to figure out the code that actually triggered it.

I've also, for fun, started writing the lisp reader in irken itself.

equirecursive types

2010-10-26T16:04:00.000-07:00

Just a quick status update. As my 'user' program has become larger, the type solver has begun to slow down horribly. I'm on the wrong end of some horrible O(x) where x is probably n^4 or worse.

So I decided to try an experiment, going back to the classic algorithm W. This only took a couple of days! However. One thing I didn't realize I was getting for 'free' from the constraint-based solver was recursive types. Now I'm forced to actually understand the concept.

I see two potential outcomes: 1) I grok recursive types well enough to fix my unifier, and the compiler gets much much faster; or 2) I rewrite the constraint solver to be more efficient. It's possible that I understand things well enough now to be able to do so.

If anyone out there can explain how to do unification with equirecursive types, I'd love to have the help!

first draft of a language tutorial

2010-09-19T17:01:00.000-07:00

I've slapped together a tutorial/language document, I'd love to get some feedback on it. In order to save time and space, it is aimed at programmers that are already familiar with Lisp/Scheme; mostly it introduces the MLish concepts and unique quirks of Irken.

The Irken Language.

Feedback of any kind would be much appreciated!

new 'defmacro'

2010-07-26T13:52:00.000-07:00

Here's a taste of what the new macros look like. It's just like syntax-rules, but without the redundant 'define-syntax'/'syntax-rules' layers. I've also lost a layer of parens by using something closer to the Irken pattern-matching syntax.

;; -*- Mode: Irken -*-

;; derived expressions

(defmacro and
  (and)                 -> #t
  (and test)            -> test
  (and test1 test2 ...) -> (if test1 (and test2 ...) #f)
  )

;; *not* the same as a Scheme <or>, this returns a boolean.
(defmacro or
  (or) -> #f
  (or test) -> test
  (or test1 test2 ...) -> (if test1 #t (or test2 ...))
  )

(defmacro let
  ;; normal <let> here, we just rename it to our core
  ;; binding construct, <let_splat>
  (let ((name val) ...) body1 body2 ...)
  -> (let_splat ((name val) ...) body1 body2 ...)

  ;; named let
  (let tag ((name val) ...) body1 body2 ...)
  -> (letrec ((tag (lambda (name ...) body1 body2 ...)))
       (tag val ...))
  )

The Macro Wars

2010-07-21T13:21:00.000-07:00

Back in the 80's I worked mostly in Common Lisp, and therefore learned the relatively simple 'defmacro'. Over the years of exposure to Scheme, I was often curious about the more sophisticated macro systems (I think first described in R4RS, but rarely implemented). Most Scheme systems still used a backquote-style macro facility.

I never tried the 'hygienic' macro systems, partly because I didn't really care about the issue they're trying to solve, but mostly because they're just dauntingly complex. One reason is that people still seem to have not settled on one standard system. Maybe R6RS has?

If you want a taste, look over the PLT/Racket documentation here and here.

This discussion covers the strain between the two camps pretty well.

I've not completely decided yet whether I'm going to add macros to Irken. I'm coding something up now to try out. If it's a win, it stays in. But I'm leaning toward something like 'syntax-rules', with a simplified syntax. Pattern-matching will be a natural fit with the rest of Irken. [Why does scheme require both 'define-syntax' and 'syntax-rules' as two separate forms, repeating the name of the macro yet again?]

The Evil Value Restriction and Lisp Macros

2010-06-29T20:00:00.000-07:00

One of the more annoying features of the HM type system is how it interacts poorly with imperative features. Every few weeks I completely forget these limitations and try to do something that in any other language would be completely natural, and get bit again.

The heart of the problem is exposed by the idea of using a mutable list datatype. When you create an empty list ('nil'), it has type "list 'a" - in other words, 'nil' can take on any type you like.

In Irken, as long as you stick with the datatype constructors themselves, this works. You can create lists of different types right next to each other and have all the type safety you like.

But as soon as you try to wrap that up - for example, into a stack ADT - you hit the value restriction.

In OCaml, this problem manifests as 'weak' type variables - e.g., " list '_a ", which just records the fact that '_a is currently unknown, and will instantiate to only one type.

One reason this keeps biting me unexpectedly is that I've changed the compiler to (by default) only type the program after inlining. This make copies of smaller polymorphic functions/interfaces, thereby side-stepping the problem with the value restriction - instead of making one copy of a function that works at multiple types, inlining causes that code to be duplicated at each site. I only notice VR problems when I force it to type twice, or turn off inlining.

I'm wondering: as a practical matter, maybe I should just embrace this. I'm not qualified to invent a new type system that's going to fix all this. But a 'stupid' substitution system (like C++ templates or lisp macros) makes the problem go away, and that's good enough for me.

AFAIK none of the ML's have a macro system. Is this perhaps a side-effect of ML fans' universal hatred of Lisp?

How might macros interact with HM? For example, could we design a 'polymorphic class' that would essentially copy the code at each use site?

A possible approach to writing an LLVM backend

2010-05-21T00:23:00.000-07:00

Playing around with dragonegg, I've found that I can get pretty detailed llvm-ir/asm output, and I can even make sense of how the C output by Irken is getting translated. Seems like this could be a handy way of getting started on writing an llvm backend. Not that I'm thinking of doing that. Must... resist...

Here's the count-to-a-million test code in Scheme/Irken:

(let loop ((n 1000000))
  (if (zero? n)
      "done"
      (loop (- n 1))))

Here's the C output:

FUN_loop_8:
    r0 = varref (0,0);
    if PXLL_IS_TRUE(PXLL_TEST(unbox(r0)==0)) {
      r0 = (object*) &constructed_0;
      PXLL_RETURN(0);
    } else {
      r0 = varref (0,0);
      r1 = (object *) 3;
      r0 = box(unbox(r0)-unbox(r1));
      lenv[2] = r0;
      goto FUN_loop_8;
    }
    PXLL_RETURN(0);
  L1:
  r1 = allocate (TC_CLOSURE, 2);
  r1[1] = &&FUN_loop_8; r1[2] = lenv;
  r0[2] = r1;
  r0 = allocate (TC_TUPLE, 2);
  r1 = (object *) 2000001;
  r0[2] = r1;
  r1 = top[2];
  r0[1] = r1[2]; lenv = r0; goto FUN_loop_8;

And the relevant LLVM IR:

"<bb 12>":                                        ; preds = %"<bb 17>", %"<bb 13>", %"<bb 24>"
  %D.5560_160 = phi i8* [ inttoptr (i64 2000001 to i8*), %"<bb 24>" ], [ %D.5560_160, %"<bb 13>" ], [ %4, %"<bb 17>" ] ; <i8*> [#uses=3]
  %3 = icmp ult i8* %D.5560_160, inttoptr (i64 2 to i8*) ; <i1> [#uses=1]
  br i1 %3, label %"<bb 13>", label %"<bb 17>"

"<bb 13>":                                        ; preds = %"<bb 12>"
  %D.4871_48 = load i8** %2, align 8              ; <i8*> [#uses=1]
  indirectbr i8* %D.4871_48, [label %"<bb 12>", label %Lreturn]

"<bb 17>":                                        ; preds = %"<bb 12>"
  %n.85_162 = ptrtoint i8* %D.5560_160 to i64     ; <i64> [#uses=1]
  %D.5572_16323 = add i64 %n.85_162, -2           ; <i64> [#uses=1]
  %D.5579_167 = or i64 %D.5572_16323, 1           ; <i64> [#uses=1]
  %4 = inttoptr i64 %D.5579_167 to i8*            ; <i8*> [#uses=2]
  store i8* %4, i8** %11, align 8
  br label %"<bb 12>"

the pattern-matching parser, mostly done

2010-05-18T16:46:00.000-07:00

I have a nearly finished python-like-language parser, written using pattern matching.

The lexer is generated as a DFA by parse/lexer.py

The parser tables are generated by a set of tools (including Jason Evans' Parsing.py module) from a simplified version of the Python 1.5.2 Grammar.

The DFA engine is now in a separate file, lib/lexer.scm.

Here's the parser so far.

The lexer tokens are fed through a one-token buffer that generates INDENT and DEDENT tokens when necessary. This is done by the top-level 'parse' function.

Following that are the expr datatypes, print functions, and finally the parsing functions themselves.

Here's a typical parsing function:

(define p-while-stmt
  ;; while_stmt: 'while' test ':' suite ['else' ':' suite]
  (_ test _ (item:nt _ body) (item:nt _ else)) -> (expr:while (p-expr test) (p-suite body) (p-else else))
  x -> (perror "p-while-stmt" x))

Oh, and here's some sample output.

The Advantages of Tagged Immediates

2010-05-18T14:46:00.000-07:00

First, a definition. An 'immediate' is a value that can fit in a register. That is, a non-pointer value. In lisp, these are things like ints, bools, characters. Most lisp implementations use tag bits to identify these objects at runtime, and Irken has inherited this design.

The advantage is that the garbage collector and runtime can tell pointer from non-pointer, and can print out any type without consulting some table generated by the compiler.

The disadvantage is mostly with integers - Irken uses a one-bit tag, the lowest bit. Any value with the lowest bit set is an integer immediate. To get its value you merely shift right. This hurt a lot in the 16-bit world, a little in the 32-bit world, and I will venture to say not at all in a 64-bit world.

Bools, characters, unit types, etc... are represented by a value having the second bit set.

Pointer types are any value that has the lower two bits cleared; i.e., 32-bit aligned addresses. Very neat how that works out.

Now, the hardcore ML guys (like Mlton and OCaml) have pretty much eliminated all tagging, and use unboxed tuples whenever possible (i.e., a datatype containing three values will consist of exactly three words in the heap, no type+length word). They do this because they can, and I suppose to be more competitive with C.

My feeling is that the advantages of run-time tagging outweigh the disadvantages, especially when debugging a new compiler. I've had enough experience grepping through core dumps of python processes that I really appreciate having a heap image that can be combed through, analyzed by a coroner. [In fact, at IronPort we wrote an entire suite of tools for doing post-mortem analysis on python core files. Sadly they still haven't been open-sourced].

While hacking up the first test VM, I noticed another neat hack that claws back some of the disadvantage of boxes and tags.

Imagine you have a datatype like this:

(datatype key
  (:number int)
  (:letter char))

It would be rather inefficient to put 'keys' into one-tuples, only to have a tagged immediate inside. So Irken actually detects this case, and eliminates one-tuples like this whenever possible. At run-time, a 'key' will consist of either one or the other immediate type, distinguished by the tag that's already on these values.

The hack won't work for cases where you include more than one use of the same base type, for example:

(datatype key
  (:number int)
  (:funny int)
  (:letter char))

Since there's no way at runtime to distinguish the two integer alternatives. (But you'll still get it for the 'letter' alternative).

This hack works really well for a VM, where you need exactly this kind of datatype to represent the union of all possible types.

Getting Comfortable with Type Inference

2010-05-17T18:16:00.000-07:00

Now that I've had many months of experience working with a type-inferred language, I'm beginning to notice a change in the way I work.

Statically-typed functional languages have a well-deserved reputation for spitting out obtuse, nearly useless type errors. Irken is no exception. In fact, it's probably much worse than most languages because a type error dumps you into a Python traceback. Also, it doesn't bother to track source line number information, so you're really on your own.

Over the past month or two, especially since I added pattern matching, I've noticed that my 'type accuracy' is improving. The chances that something will be correctly typed the first time I try to compile it are higher than they were. As I become familiar with the type system, and pattern matching, Irken has been training me. It's as if a type error (and the resulting jaunt through pdb) is a slap on the nose. A clean compile is like a nice treat. Good human.

This has changed my edit-compile loop a little - I tend to compile more often. If I've only changed one or two lines since my last compile, I'm pretty sure I know where the typo is.

This makes me wonder if one of ML's problems is related to this. Old-timers don't need to spend all that effort making a "Microsoft Bob" type error reporter. They see "itypes.TypeError: ((()->wta), (wjx->vpq))" and they know they forgot to pass an argument to that function call they just added.

Newcomers, though. They get that same feeling they had the first time they struggled with a C or Ada compiler.

When/if I rewrite Irken in itself, I think I'll try to do a better job. In "HM(X) Type Inference is CLP(X) Solving", Sulzmann and Stuckey argue that a constraint-based solver can do a better job of error reporting; so here's hoping I can figure that out when the time comes.

(p.s. I have to admit that OCaml's reporting is pretty snazzy, though)

the temptations of LLVM

2010-05-11T13:38:00.000-07:00

I'm still plugging away at the parser and vm for the python-like-language.

But in another window I have the language reference for LLVM open, and as I browse through it I'm becoming increasingly distracted. There are many wonderful snacks - things like add with overflow detection, intrinsic functions like memmove, nice floating-point and vector insn support, atomic swap operations, etc...

An interesting aspect of LLVM is that it doesn't really support a register model. Instead, it uses SSA, which means that you just keep inventing names for each result. Now, this will either be a perfect fit for Irken's CPS-based compiler, or it will make it impossible to do. I haven't decided yet.

A long time ago, CPS and SSA were proven to be equivalent. From what I can tell, the compiler world has moved on and pretends that CPS never existed.

A statically typed VM?

2010-05-03T19:27:00.000-07:00

Trying to wrap my head around this idea... The VM I'm playing around with right now is dynamically typed - but its implementation is statically typed. I started thinking about making a bytecode implementation of Irken itself (rather than a Python-like language).

But I'm not sure it even makes sense to try to write a static VM in a static language, because you'd have to do the equivalent of 'void*' casting everywhere. (Of course, this is what you do when you write a VM in C, but it feels a much more natural thing to do in C 8^).

I was curious to see how OCaml dealt with this issue... and was quite surprised to find a VM written in C.

tak20 benchmark runs in the VM

2010-04-26T13:36:00.000-07:00

My favorite benchmark now runs in the VM, since I now have all three types of procedure invocation implemented: tail calls, tail recursive calls, and normal invocation. The last is the most complex, because it actually involves building a 'stack frame' and saving/restoring registers:

(datatype vmcont
  (:nil)
  (:k (vmcont) (lenv) int (vector (object)))
  )

Take a look at the current VM implementation, in Irken.

So a 'VM continuation' consists of the pointer to the next frame, the lexical environment, the PC, and a vector of saved registers.

The 'INVOKE' cps insn is turned into two VM insns, 'CALL' and 'POP'.

Even without any serious tweaking, the tak20 benchmark seems to run about the same speed as in python. But I plan to make specialized versions of CALL and POP for different numbers of saved registers. This will eliminate loops in the insns and thus get rid of allocation for the insn closures.

It's very rewarding to finally bring all this work together. Putting together a functioning VM is the very tip of an iceberg I've spent 2+ years building.

I'm even thinking about documenting the Irken language. Yeah, I know, crazy thoughts.

Next step: start building the python-like language. This would involve rewriting the byte-code compiler in Irken. OR, I could continue the nearly trivial task of supporting Irken as a byte-coded language, and start rewriting everything in Irken. As we all know, only the most fashionable and respectable languages are written in themselves. It's tempting!

dragon egg

2010-04-22T21:40:00.000-07:00

If you've ever tried to even read the instructions for building llvm-gcc (much less try to build it), you understand why this is good news.

http://dragonegg.llvm.org/

Sounds like gcc has gained a plugin architecture, and the llvm folks are putting together a plugin, 'DragonEgg', that uses LLVM as the back end.

Why do I care about this?

1) Clang still does not support lexical functions, which are critically important to Irken's performance.
2) The version of llvm-gcc distributed with Apple's XCode uses an older version of llvm that implements the address-of-label extension with a hack so horrible I would be embarrassed to describe it to you.

first loop in the vm!

2010-04-22T14:51:00.000-07:00

I've implemented enough instructions in the VM that I can now do a loop (a.k.a. a tail-recursive function call).

I still need to work on the VM insns, there's a lot of allocation taking place that shouldn't... also, there's range-checking on each and every vector access.. even including stuff like the register file. Given those caveats, it's only about 4X slower than a similar python loop. I'm pretty sure I should be able to make it faster than python, we'll see.

--- cps ---
   0 = new_env [] 1
   -   push_env [0] None
   1 = close [] 'loop_0'
       0 = lit [] 3
       1 = varref [] ((0, 0), False, {n_1})
       0 = primop [0, 1] ('%=',)
       0 = test [0] None
           0 = lit [] 1
               return [0] None
           0 = varref [] ((0, 0), False, {n_1})
           1 = lit [] 2
           0 = primop [0, 1] ('%-',)
               tr_call [0] (1, )
           return [0] None
   -   store_tuple [1, 0] (0, 1, 1)
   0 = new_env [] 1
   1 = lit [] 0
   0 = store_tuple [1, 0] (0, 1, 1)
   1 = varref [] ((0, 0), True, {loop_0})
       invoke_tail [1, 0]

stirrings of a vm

2010-04-05T12:56:00.000-07:00

I'm finally beginning to think seriously about a VM. It's been a long road.

My approach, as usual, is maximally lazy. For now, I've pushed the parser to the side while I figure out what the byte code compiler will put out. That of course depends on what the VM will look like.

To begin, I'll simply re-use the Irken compiler, which already compiles a lambda-calculus based language into a register-based CPS instruction stream.

Here's what it looks like so far.
This bytecode is consumed by the VM, which works in two phases. First, it loads the bytecode into two vectors, one holding instructions, one holding data. (Note: the insn vector is typed as "vector((->undefined))"). Then it simply invokes the first insn. See vm/vm.scm for details.

The vector of insns allows us to build a 'threaded' VM: each insn is implemented as a no-argument function. The last thing each insn does is fetch and execute the next insn.

(define (insn-literal)
  (set! regs[vm-data[pcd]] vm-data[(+ pcd 1)])
  (set! pcd (+ pcd 2))
  ((next-insn)))

"((next-insn))" compiles to a bit of C that looks like this:

lenv = r0[2]; goto *r0[1];

This has the potential to be very fast.

My current stumbling block is where/how to straddle the divide between the typed and untyped universe. The VM is written in a strongly typed language, but I want it to implement an untyped language. In order to do that I need to be able to store arbitrary objects into the VM registers. I'm thinking of a couple of different approaches right now.

1) Add an 'object' type to the Irken compiler - this will act like a normal declared datatype, but when you pattern match or vcase it, the compiler will emit code to detect our run-time tags instead. I'll probably need some way of casting things to the object type.

or

2) *Remove* run-time tagging from Irken. This would make Irken even more like OCaml. The advantages should be obvious. The disadvantage would be I would have to implement some kind of stack map and teach the garbage collector how to use it. Also, Irken would become much more difficult to debug. But I could then implement the VM using fully declared and 'normal' datatypes without adding an extra layer of type tagging.

pattern matching: red-black trees

2010-03-26T13:33:00.000-07:00

This is based on Okasaki's "Purely Functional Data Structures", Chapter 3.3.

(include "lib/core.scm")
(include "lib/random.scm")

(datatype T
  (:E)
  (:R (T 'a) 'a (T 'a))
  (:B (T 'a) 'a (T 'a))
  )

(define (T/insert root < k)

  (define lbalance
    (T:R (T:R a x b) y c) z d -> (T:R (T:B a x b) y (T:B c z d))
    (T:R a x (T:R b y c)) z d -> (T:R (T:B a x b) y (T:B c z d))
    a x b                     -> (T:B a x b)
    )

  (define rbalance
    a x (T:R (T:R b y c) z d) -> (T:R (T:B a x b) y (T:B c z d))
    a x (T:R b y (T:R c z d)) -> (T:R (T:B a x b) y (T:B c z d))
    a x b                     -> (T:B a x b)
    )

  (define (ins n)
    (match n with
      (T:E)
      -> (T:R (T:E) k (T:E))

      (T:R l k2 r)
      -> (cond ((< k k2)
                (T:R (ins l) k2 r))
               ((< k2 k)
                (T:R l k2 (ins r)))
               (else n))

      (T:B l k2 r)
      -> (cond ((< k k2)
                (lbalance (ins l) k2 r))
               ((< k2 k)
                (rbalance l k2 (ins r)))
               (else n))
      ))

  (let ((s (ins root)))
    (match s with
      (T:R l k r) -> (T:B l k r)
      (T:B _ _ _) -> s
      (T:E s)     -> (impossible)
      )))

(define (print-spaces n)
  (let loop ((n n))
    (cond ((> n 0)
           (print-string "  ")
           (loop (- n 1))))))

(define (print-item x d)
  (print-spaces d)
  (printn x))

(define T/print
  d (T:E)       -> #u
  d (T:R l x r) -> (begin (T/print (+ d 1) l) (print-item x d) (T/print (+ d 1) r))
  d (T:B l x r) -> (begin (T/print (+ d 1) l) (print-item x d) (T/print (+ d 1) r))
  )

(define (n-random n)
  (let loop ((n n)
             (t (T:E)))
    (if (= n 0)
        t
        (loop (- n 1) (T/insert t < (random))))))

(T/print 0 (n-random 20))

parsing with pattern matching

2010-03-26T13:09:00.000-07:00

Parsing with pattern matching is pretty sweet.

Here's a test grammar:

# test a simple predicate language
expr: predicate | atom
list: expr ("," expr)*
predicate: NAME "(" list ")"
atom: NAME | NUMBER | STRING

And the pattern-matching code to parse it into an AST:

(datatype atom
  (:name string)
  (:number int)
  (:string string)
  )

(datatype expr
  (:pred string (list (expr)))
  (:atom (atom))
  )

(define p-atom
  (item:t 'NAME x)   -> (atom:name x)
  (item:t 'NUMBER x) -> (atom:number (string->int x))
  (item:t 'STRING x) -> (atom:string x)
  _ -> (error "p-atom")
  )

(define p-list3
  (list:cons (item:t 'comma _) 
  (list:cons x 
  (list:nil))) -> (p-expr x)
  _ -> (error "p-list3")
  )

(define p-list2
  (item:nt 'list_c_1_s1 (list:cons x y)) -> (list:cons (p-list3 y) (p-list2 x))
  (item:nt 'list_c_1_s1 (list:nil))      -> (list:nil)
  _ -> (error "p-list2")
  )

(define p-list
  (item:nt 'list (list:cons expr 
                 (list:cons rest 
                 (list:nil)))) -> (list:cons (p-expr expr) (p-list2 rest))
  _ -> (error "p-list")
  )

(define p-expr2
  (item:nt 'predicate
           (list:cons (item:t 'NAME name)
           (list:cons _ ;; lparen
           (list:cons args
           (list:cons _ ;; rparen
           (list:nil))))))
  -> (expr:pred name (p-list args))

  (item:nt 'atom (list:cons x (list:nil))) -> (expr:atom (p-atom x))
  y -> (error y)
  )

(define p-expr
  (item:nt 'expr (list:cons x (list:nil))) -> (p-expr2 x)
  _ -> (error "p-expr")
  )

The patterns are a little noisy due to my lack of a special syntax for lists. I'm still on the fence about whether that's a good idea.

new release with pattern matching

2010-03-25T15:30:00.000-07:00

I've checked in the pattern matching code. There are 10 or so new tests for it, but none of them test it especially heavily. I'll probably rewrite lib/frb.scm (the red-black tree code) using it as the next 'test'.

http://www.nightmare.com/rushing/irken/irken.100325.tar.gz

impressed with llvm, again

2010-03-23T16:35:00.000-07:00

Testing out pattern matching against constants, I wrote the following silly function:

(define thing
  0 1 -> 2
  0 y -> 3
  1 0 -> 4
  1 x -> (+ x 5)
  y z -> (+ y z)
  )
(thing 10 20)

Which turned into a nice set of if statements, doing 4 tests in total. Not bad. But I was curious to see what kind of asm LLVM would generate for it.

_vm:
Leh_func_begin7:
        pushq   %rbp
Llabel13:
        movq    %rsp, %rbp
Llabel14:
        movq    _heap0(%rip), %rax
        movq    $772, (%rax)
        movq    $10, 8(%rax)
        movq    $10, 16(%rax)
        movq    $1, 24(%rax)
        movl    $61, %eax
        popq    %rbp
        ret
Leh_func_end7:

Huh. So that bit there at the very end, "movl $61, %eax". Yeah. That's the answer, "30". Even with all the tagging/untagging, registers, embedded if statements, etc... LLVM still optimized the entire program away to a constant. Nice.

pattern matching!

2010-03-22T13:01:00.000-07:00

I managed to ignore the subject of pattern matching for a loooong time. I wanted to see how reasonable it was to build a language using 'case'-type statements. I viewed my ability to code up something relatively complex like red-black trees as proof that they're not absolutely needed.

However, now that I've seen that it's relatively easy to add (given the existing vcase support), I'm beginning to warm up. Look over these alternate versions of 'reverse-onto'.

The problem that forced me to finally look into it was the parser. In order to walk over complex trees of tokens - keyed by symbols - I was writing some very hairy 5-levels-deep vcase code. And I remembered how much easier this kind of task is in a language like Erlang. If you look through the code for ejabberd, for example, you might be confused hunting for the xml/xmpp parser, until you realize that it's embedded in the definition of the functions themselves, using pattern matching.

As you might be able to tell from the example given, the constructor syntax is still pretty wordy. There's no easy fix for this problem, which is caused by the requirements of type inference. Most ML-like languages require that constructors are globally unique. I find this abhorrent, so instead I'm requiring the name of the datatype to be present, e.g. "list:cons".

There may be ways to make this less wordy. It would be perfectly reasonable to define the list constructors as 'C' and 'N'. (for 'cons' and 'nil', respectively). A tree datatype could use 'N' and 'E' (for 'node' and 'empty'). This would still be pretty readable.

SML seems to use its module system to make it possible to use single-letter abbreviations like this.

One other area of inequality that really bugs me: the way lists are treated specially in ML dialects. It would be really nice for the user to be able to define their own extensions in a lisp-macro-like way. Something to think about.

The Implementation of Functional Programming Languages

2010-03-20T16:06:00.000-07:00

I'm working on adding pattern matching to Irken. Digging through the OCaml source, I found a reference to this little gem:

"The Implementation of Functional Programming Languages" (Simon Peyton Jones, published by Prentice Hall, 1987.)

The book is available for free here: http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

Chapters 4 and 5 cover exactly what I need for pattern matching - in fact, it appears that their algorithm transforms a set of patterns into a tree of 'case' statements where their 'case' construct exactly matches my current 'vcase'. Nice!

How is it that after so many years of trudging through this space, I never knew about this book?

recent changes

2010-03-13T12:25:00.000-08:00

I've restored the ability to gc in the middle of a function. This required coming up with a bit of a trick to copy registers in and out of gc:
```
void gc_regs_in (int n) {
 switch (n) {
 case 4: heap1[6] = r3;
 case 3: heap1[5] = r2;
 case 2: heap1[4] = r1;
 case 1: heap1[3] = r0;
}}
```

Literal data built at compile-time. Big win for programs with lots of pre-initialized data (like lexer and parser tables).

Verify the output of tests.

Filled out the type declaration syntax (type variables, recursive types, etc...) and unified it with the cexp syntax. (Well, to the extent that they use a single parser now rather than two different ones).

syntax for literals

2010-03-12T14:57:00.000-08:00

In Scheme/Lisp, literal lists are expressed using the quote syntax: '(1 2 3), which is expanded by the reader to (QUOTE 1 2 3). In Lisp, quoted list structures are important, especially for macros (which I'm deliberately trying not to support in order to avoid becoming dependent on the lisp syntax).

I need a literal syntax for Irken, and until now I've used QUOTE, but it's causing me a lot of trouble now that I'm using algebraic datatypes.

To put this in terms that a C programmer can understand, this is a literal array of integers:

  int thing[] = {1, 2, 3, 4, 5};

Without a literal syntax, you'd have to do this:

  int * thing = malloc (sizeof(int) * 5);
  thing[0] = 1;
  ...

The 'list' datatype is declared like any other - it's not built in to the compiler (though I could certainly do that):

(datatype list
 (:nil)
 (:cons 'a (list 'a))
)

The compiler will translate '(1 2) into:
(QUOTE (list:cons 1 (list:cons 2 (list:nil)))).

But this leaves all the other datatypes with no convenient syntax - and worse - with no way to identify or express literals. This has turned into a big problem for the parser and lexer, where I really need to build the literals at compile-time (otherwise I get huge executables that do nothing but build data structures).

Right now I'm playing with this syntax:

(literal (tree:node (tree:leaf 1) (tree:node (tree:leaf 2) (tree:leaf 3))))

The grammar for 'constructed' literals is:

literal ::= (<constructor> <literal> ... ) | (vector <literal> ...) | immediate

The question is - should I retain QUOTE just for lists? I hate having two syntaxes for two very similar concepts. All the ML-like languages have a special syntax for lists, which is probably an indicator that it's important. On the other hand - the special syntax might encourage people to misuse the list datatype simply because it's more convenient - e.g., you might build a binary tree out of lists (which wastes a lot of heap) rather than declaring a proper datatype.

Parser's Working

2010-03-04T23:11:00.000-08:00

Ok, got the parser rewritten using the new datatypes.

If you're bored, and would like to know how small a lexer and parser engine can be, take a look at tests/t_parse.scm.

Note that both the lexer and the parser are bare-bones engines that are using tables generated by other tools written in Python. In this case, a DFA lexer written by me, and an LR(1) parser generator written by Jason Evans.

polymorphic vs normal variants

2010-03-03T17:54:00.001-08:00

Just a quick summary of the pros and cons of each alternative.

Polymorphic Variants

Pros:

Outrageously polymorphic - use them any way you like, anywhere
No declarations needed.
The runtime can associate certain meanings with the tags on polymorphic variants. This makes them act more like lisp type tags. For example, the runtime can identify a list and correctly print it out, rather than {u0 1 {u0 2 {u0 3 {u1}}}}. [This is probably addressed in ML by treating lists specially, rather than having the 'basis' declare the list type.]

Cons:

Each variant consumes precious tag space. Since type tags are stored in a byte, and in particular a byte with the lower two bits zeroed, there are only about 59 such tags left.
Lots of work for the type solver, because of the overly detailed types...
...thus the compiler runs slower

'Normal' Variants.

Pros:

Cleanly declared datatypes. If we're really planning on doing systems programming with this, then declared datatypes are probably non-negotiable.
Tag values are consumed only within a datatype - so rather than having 59 total different types, we can have an unlimited number of types, each of which can have up to 59 different variants. (To clarify this with an example, the list datatype uses the tags 0 and 1, because it has two variants, 'nil', and 'cons'). A tree datatype will also use tags starting at 0, since the type system guarantees that a tree will never be confused with a list at runtime.

Cons:

The runtime has no idea what it's printing out, so you can get impenetrable output like this: {u0 16 {u0 1 0} {u0 15 {u0 1 0} {u0 14 {u0 1 0}...

Datatype declarations are going to scare non-ML people off, which is a shame. Here's what the syntax currently looks like:

(datatype item
  (:nt symbol (list (item 'a)))
  (:t symbol)
  )

(datatype stack
  (:empty)
  (:elem (item 'a) int (stack 'a))
  )

Sadly, I've chosen the same solution as OCaml - to leave both kinds in. If I could collect up the nerve to remove a lot of hard-earned code, I'd probably remove polymorphic variants.

status update

2010-03-02T22:35:00.001-08:00

Finally posted a new tarball today. Lots of changes over the past few weeks:

'datatype' syntax and 'normal' variants (though I've left in polymorphic variants as a 'stealth' feature)
more tests, and run_tests.py now verifies their output
'let_reg' will store bindings into registers when certain conditions are met - this really cuts down on pointless allocation for local variables.

I feel like this is getting much closer to 'useful' status, and will hopefully begin work on a VM within the next couple of weeks.

Here's the tarball.

Temporarily Giving up on Polymorphic Variants

2010-02-12T14:36:00.001-08:00

Polymorphic Variants finally reached the point where they were causing more problems than they were worth. So I've temporarily put them aside... leaving support in the compiler, but I'm adding normal datatype/sum/union declarations back in.

The types are too expressive (see previous post)
Since the types are so complex, the solver gets hit with constraints leading to tens of thousands of type variables. This is mostly triggered by large initialization expressions like parser tables. Waiting 20 seconds to type a 40K file is not cool.
I need to get back to work, i.e. I need to make some progress.

So after plugging away for a week or so, I've now run into a new problem - the value restriction. Something I've put off dealing with for a long time. Turns out the problem is classically triggered by type constructors for things like empty lists. For example, this types without any problems:

(datatype list
  (nil)
  (cons 'a list)
)

(let ((l0 (list:nil)))
  (set! l0 (list:cons 34 l0))
  (list:cons #f l0)
)

[Note that the last line glues together a "list(bool)" onto a "list(int)"]

The solution is to restrict the polymorphism of assigned variables, hence the Value Restriction.

-Sam

restraining polymorphic variants

2010-02-05T13:50:00.000-08:00

Since I started playing with polymorphic variants, I've repeatedly stumbled into a strange problem with them. They're too expressive!

Polymorphic variants are the flip side of polymorphic records. This is a major feature of my type system that allows you to use any label anywhere, in any way, without having to declare it first. I really like this ability, especially in the context of Irken, because it has a very Pythonic, dynamic-language feel to it.

As an example, here's some code that creates a lisp-like list:


(:cons 1 (:cons 2 (:cons 3 (:nil)))

That's it. Symbols starting with colons are constructors. No datatype declaration. Completely type safe. You just use constructors however you like. OCaml has the same feature:


# `Cons (1, `Cons (2, `Cons 3, `Nil));;
- : [> `Cons of int * [> `Cons of int * [> `Cons of int ] * [> `Nil ] ] ] =
`Cons (1, `Cons (2, `Cons 3, `Nil))

But if you look at the type that OCaml assigns to the result you see the seed of the problem. Watch this:


# `Cons (1, `Cons ("hello", `Nil));;
- : [> `Cons of int * [> `Cons of string * [> `Nil ] ] ] =
`Cons (1, `Cons ("hello", `Nil))

See? You could call that the datatype of lists that start with an int followed by a string.

With a complex data structure like a red-black tree, you get types like this:


rsum(rlabel('purple', pre(product(rsum(rlabel('empty', pre(kb), rlabel('purple',
 pre(jw), rlabel('red', pre(gz), rdefault(abs()))))), rsum(rlabel('empty', pre(nq),
 rlabel('purple', pre(nl), rlabel('red', pre(ko), rdefault(abs()))))), jc, jd)), 
rlabel('empty', pre(product()), rlabel('red', pre(product(rsum(rlabel('purple', 
pre(product(hj, hk, hl, hm)), bgc)), rsum(rlabel('purple', pre(product(hn, ho, hp,
 hq)), bgp)), hh, hi)), rdefault(abs())))))

What the hell is that?? Well, it's a type built during the compilation of one of the tree-balancing functions; a reflection of the matching structure used to examine the tree a few levels deep. Think of it as a template that sits on top of a red-black tree.

Here, the compiler is building incredibly detailed, complex types and checking them for me. What I would prefer is for it to automatically recognize recursive datatypes when I use them - without have to declare them. Or, I would like the compiler to keep variants monomorphic within a single type.

This would involve a loss of some expressive power. But how often would you want to use variants polymorphically within the same object? And if you needed that, why wouldn't you use a different label?

Thinking about a new inliner...

2009-12-19T20:05:00.000-08:00

I recently found a problem with the inliner. After adding the code to unpack the data attached to variant types - I deliberately left the unpacker in a form like this:

((lambda (f0 f1 f2...) <body>) x.f0 x.f1 x.f2)

Something like that might be generated for a vcase expression like this:

      (define (pop)
        (vcase stack
          ((:nil) (error "stack underflow"))
          ((:elem item _ tail)
           (set! stack tail)
           item)))

I then made the inliner recognize ((lambda () ...) ...) applications and inline them when it could. This revealed a major problem with my inliner, most easily demonstrated like this:

(let ((n 10))
  ((lambda (x) (set! n 5) x) n))

This should return 10, not 5. In the stack example above, instead of returning the popped item, it returns the new top of the stack.

Some kind of assignment analysis is needed.

While digging around for a good reference on the subject, I found a really good paper on inlining that seems to cover this and several other issues. It looks pretty straightforward to implement, so there may be another pause-to-work-on-irken phase.

avoiding address range checks in the copying collector

2009-12-13T13:45:00.000-08:00

I added this hack years ago, in another project; so I don't remember if I came up with the idea myself or borrowed it from elsewhere.

The Cheney algorithm leaves a 'forwarding' pointer in fromspace to identify objects which have been evacuated to tospace. When looking at a pointer in fromspace, you need to do an address range check on it to figure out which space it points to. This is relatively expensive. What I do instead is store a sentinel in place of the object header, and store the forwarding address immediately after it. Then the scan can identify forwarded objects by just looking for the sentinel.

Unfortunately, this breaks for zero-element tuples - there's nowhere to store the forwarding pointer.

Normally, zero-element tuples shouldn't exist - it's more efficient to represent such an object by an immediate object (like 'nil'). This works for everything - except for vectors. Vectors are by their nature run-time beasts that must support zero length.

So I've added support for a new immediate type - TC_EMPTY_VECTOR, which will have to be checked for at runtime, for example in "vector-length".

More speedups for the solver

2009-12-12T17:11:00.000-08:00

When fed large chunks of pre-initialized data (in this case parser tables), the type solver fell over. It was taking on the order of minutes to solve about 1000 lines of parser table (which is nowhere near the size of the full parser).

The problem was that the split/unname phase of the solver doesn't kick in until the type of a particular node is completely solved - and this type was running to over 10,000 type variables. This was triggering a lot of nasty N² behavior in the solver, which shunts equations in and out of the unifier as it fuses/decomposes them.

The fix I found is to trigger an 'extra' unname phase whenever 1000 tvars have been added to an s_let() frame. This cut the time down from 1:20 to 8 seconds.

Another thing I'm considering - in order to avoid the 'overly specific type' problem - which really goes crazy when fed literal lists... I may try to type variant constructors as a funcall instead.

One last possibility - to add datatype declarations back, and just give up on the row-based variants. I don't want to do that, because I think they have a very pythonic feel to them.

p.s. I threw up a new tarball a few minutes ago.

Typed call-with-current-continuation?

2009-12-07T19:15:00.000-08:00

I ran into an interesting problem today. In certain use cases, make-generator fails to type correctly:


(define (make-generator producer)
 (let ((ready #f)
       ;; just holding useless continuations
       (caller (call/cc id))
       (saved-point (call/cc id)))

   (define (entry-point)
     (call/cc
      (lambda (k)
        (set! caller k)
        (if ready
            (saved-point #f)
            (producer yield)))))

   (define (yield v)
     (call/cc
      (lambda (k)
        (set! ready #t)
        (set! saved-point k)
        (caller v))))
   entry-point
   ))

Note the call (saved-point #f). This is returning #f to a normally-ignored continuation:


(define (make-int-generator n)
  (make-generator
   (lambda (consumer)
     (let loop ((n 0))
       (consumer n)
       (loop (+ n 1))))))

Depending on where you place a call to your consumer function, the continuation may or may not be ignored. I got different results depending on whether I called an external function to produce values, or an inline loop. I thought maybe by rewriting make-generator using lower-level prims putcc and getcc, I could make the problem go away.

Although it has simplified make-generator, the problem hasn't really gone away:


(define (make-generator producer)
  (let ((ready #f)
        ;; holding useless continuations
        (caller (getcc))
        (saved-point (getcc))
        )
    (define (entry-point)
      (set! caller (getcc))
      (if ready
          (putcc saved-point #u)
          (producer yield)))
    (define (yield v)
      (set! saved-point (getcc))
      (set! ready #t)
      (putcc caller v))
    entry-point
    ))

I made the problem go away by changing the type declaration for putcc:


(define (putcc k r)
  (%%cexp (continuation 'a -> 'b) "(k=%s, %s)" k r))

It used to read (continuation 'a -> 'a), and if you look at the tiny bit of C code there that's exactly what it does. However. We're talking about continuations here. It's very difficult to wrap my head around what it does 'in the real world'.

I'm sure that my getcc/putcc are not new, they're just the obvious way to save and store continuations. Have I typed this correctly, or have I waved my hand? How do the other typed languages deal with this problem?

One solution I tried was to pass make-generator an extra argument, of the generated type, and use that for the call to saved-point. It feels wrong, but ultimately may be the cleanest approach.

Status Update

2009-12-02T13:54:00.000-08:00

I've spent some time trying to speed up the type solver. My most complicated test is probably 't20.scm', which tests a generated lexer. Since it uses symbols it includes the entire library, including red-black trees.

I was able to trim the type reconstruction down from 50 seconds to about 7. I did this mainly by 'pruning' the set of equations making up a solved type scheme - keeping only those directly or indirectly referenced by the root type variables for the scheme. This seems to have lost me some of the outrageous type specificity, and seems similar to what Pottier's mini-prototype code does.

The 7 seconds for this is actually closer to 3.5s, since I run the typer twice. I think I can live with this speed for a while... that's to compile about 65KB of raw scheme code.

Next up: implement the LR(1) parse engine, then put the file I/O code, lexer, and parser all together for the first time.

Google's book search

2009-11-21T15:07:00.000-08:00

Google's book search just came in very handy... I came across a phrase in ATTPL using the term 'dominated', and I wasn't completely sure of its definition. And of course, I couldn't remember where in 100 pages it was defined.

Fine, I'll search the Postscript version of the chapter that I have on hand. Wait, no. That doesn't work. PS != PDF. Sigh.

So I typed in a unique phrase from the book: that found the book on Google Books. Then I simply searched for the term. Wow, it immediately told me exactly what I wanted to know.

Typing Twice

2009-11-18T20:33:00.000-08:00

I was having trouble propagating type information through the inlining pass. The source nodes have types attached to them, and you can carefully copy it when instantiating each function body... but in some cases the inlined types should be more accurate than they are.

Easy solution, run the type solver on the node tree again!

This should also help find bugs in the inliner... if something passes muster the first pass, it should definitely go through after inlining.

The Resurrected Lexer

2009-11-16T17:27:00.000-08:00

I have resurrected the lexer, after reworking lots of supportive library code, including vectors, symbols, the symbol table, lists, etc...

The new variant datatypes seem very comfortable to me. If you'd like to see the lexer working, compile and execute tests/t20.scm:

[rushing@dark ~/src/irken]$ tests/t20
{u8 newline ""}
{u8 keyword "def"}
{u8 whitespace " "}
{u8 ident "thing"}
{u8 whitespace " "}
{u8 lparen ""}
{u8 ident "x"}
{u8 rparen ""}
{u8 colon ""}
{u8 newline ""}
{u8 whitespace " "}
{u8 ident "return"}
{u8 whitespace " "}
{u8 ident "x"}
{u8 whitespace " "}
{u8 addop "+"}
{u8 whitespace " "}
{u8 number "5"}
{u8 newline ""}
#t
{total ticks: 28843224 gc ticks: 0}

Note that "{u8 ...}" is how the printer outputs the (:token kind value) constructor. Each variant constructor is assigned a unique integer tag. You'll see the same (somewhat confusing) output when playing with lists - I need to either pre-allocate (and thus reserve) certain constructor names - or quit using the builtin printer code (which is in C). I'm not sure that it's practical to teach the C printer how to print out variants, since the user can use them in different ways for different purposes.

Choosing a Parser

2009-11-15T17:07:00.000-08:00

Here's the problem. I need a parser for a python-like language, but written in Irken. Of course there are no parser generators for Irken, yet.

My first sneaky plan was to generate a set of parsing tables, and then implement the parser engine in Irken. [This is similar to my approach with the lexer - the lexer tables are generated by Python code, and emit Irken code]. I like dparser, but after looking at the parsing engine, it looked a bit intense for my purposes. I then started playing with Earley parsers. You can write an Earley parser in an amazingly small amount of code.

But Earley parsers aren't really table-driven, and it sounds like performance will be an issue.

Then I discovered Jason Evans' "Parsing.py" module. It's perfect. It generates a bog standard set of LR(1) tables. However, there was still a big gap between Python/Grammar/Grammar and the input needed by Parsing.py (which consists of a class for each terminal and non-terminal, and a method for each reduction - annotated with docstring-based reduction rules).

To fill that gap, I needed two things:

A parser for the python meta-grammar syntax.
A translator from that grammar into a Parsing.py parser.

You'll find both in my python/parsing subdirectory, enjoy!

[Thanks to John Plevyak for assistance with dparser]