recent changes

1. 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;
   }}

   
   


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


3. Register bindings for variables in leaf positions. This will cut down on lots of heap allocation


4. Verify the output of tests.


5. 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

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

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

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

Polymorphic Variants

Pros:

1. Outrageously polymorphic - use them any way you like, anywhere
2. No declarations needed.
3. 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:

1. 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.
2. Lots of work for the type solver, because of the overly detailed types...
3. ...thus the compiler runs slower

'Normal' Variants.

Pros:

1. Cleanly declared datatypes. If we're really planning on doing systems programming with this, then declared datatypes are probably non-negotiable.
2. 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:

1. 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}...
2. 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

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

1. 'datatype' syntax and 'normal' variants (though I've left in polymorphic variants as a 'stealth' feature)
2. more tests, and run_tests.py now verifies their output
3. '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

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.

1. The types are too expressive (see previous post)
2. 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.
3. 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

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?