proper datatypes for bool and symbol

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

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

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'

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

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

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

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>"