[fexl]

The Fexl interpreter is simple, elegant, and fast. The core "reduce" routine runs about 43.5 million cycles per second on a simple infinite loop. If I set max_cycles to a billion it stops after about 23 seconds.

To test it with something more real, I wrote the "cat" program in Fexl as follows:

  \cat = (get_char \ch eq EOF ch I; put_char ch cat)

Then I pumped 30MB of data into it, which took about 42 seconds:

  time (head -c 30000000 /dev/zero | fexl_cat >/dev/null)

Of course that's a lot slower that pushing the data through the Unix cat program, which only takes about 0.14 seconds:

  time (head -c 30000000 /dev/zero | cat >/dev/null)

But think about all the gyrations happening here:

  \cat = (get_char \ch eq EOF ch I; put_char ch cat)

That is translated into the closed (variable-free) form:

  (Y (S (C get_char) (S (C (S (S (eq EOF) (C I))))
  (S (C (S put_char)) C))))

Then that runs like the wind, applying combinator rules such as these many millions of times:

  C x y = x
  S x y z = x z (y z)
  I x = x
  Y x = x (Y x)

Not to mention that get_char and put_char are handling and building characters one at a time, and the "eq" function runs as a combinator as well.

By the way it is quite trivial to add new combinators written in C. For example, the fabled Y combinator is defined in a single file "type_Y.c" as follows:

  #include "node.h"
  #include "type_Y.h"

  /*
  Fixpoint function (Y combinator):  (Y f) = (f (Y f))
  */
  static void step(void)
      { 
      int f1 = pop();
      if (!f1) return;

      set_pair(f1, R(f1), P(L(f1),R(f1)));
      } 

  int type_Y(void)
      { 
      static int node = 0;
      if (node == 0) node = new_combinator(step);
      return node;
      } 

The type_Y.h file just says:

  extern int type_Y(void);

[fexl]

The whole thing is about 800 lines of C code so far, and I aim to get that lower. :) For one thing, I'm busy bootstrapping the Fexl parser into Fexl itself. It's really neat to be able to express executable concepts simply and completely like this:

  # Parse a nested parenthesized expression.
  \parse_nested =
    (
    \yes
    \no
    skip_char ch_lparen
        (
        parse_expr
            (\expr skip_char ch_rparen (yes expr) no)
            no
        )
        no
    )

And it's simple to do either-or parsing like this:

  # Parse a factor:  either an id or a nested expression.
  \parse_factor =
      (
      \yes
      \no
      parse_id (\id yes (var id));
      parse_nested yes;
      no
      )

Even such mundane tasks as skipping white space and comments have a satisfying elegance about them:

  # Skip filler, including white space and comments.
  \skip_filler =
      (
      \done
      skip_space;
      skip_comment
          (skip_filler done)
          done
      )

[fexl]

OK, here's one more example of how to write a Fexl combinator. Back in 1924 the great Moses Schönfinkel demonstrated that all computable functions can be defined in terms of just two primitive functions: C (the constant function), and S (the fusion function). So here is the source code for S, the Mother of all functions:

  #include "node.h"
  #include "type_S.h"

  /*
  Fusion function (Verschmelzungfunktion)
  S x y z = ((x z) (y z))
  */
  static void step(void)
      {
      int f1 = pop();
      int f2 = pop();
      int f3 = pop();
      if (!f3) return;

      set_pair(f3, P(R(f1),R(f3)), P(R(f2),R(f3)));
      }

  int type_S(void)
      {
      static int node = 0;
      if (node == 0) node = new_combinator(step);
      return node;
      }

[Imbue]

Not sure if I am understanding this correctly. By bootstrapping, do you mean C does only the most basic syntax parsing, and then a fexl script (written in a basic fexl subset) does the more complete parsing?

All this stuff is really neat. Your C code interface looks quite nice and clean. I hope you release some source code soon.

And thanks for taking the time to write all this. Even though a lot of it is over my head, it's quite interesting. I'm really looking forward to playing around with it a bit and learning.

[fexl]

By the way, the initial release of Fexl will take a very simple form: A Universal Filter. The "fexl" executable will be nothing more than a program which maps standard input to standard output. So it's a filter. But it's universal because it is Turing-equivalent, capable of performing any conceivable function from stdin to stdout.

When Fexl runs, the first thing it does is read a Fexl function from standard input. The Fexl process then "becomes" that function, processing the tail of the input accordingly. Simple!

[fexl]

That was the general idea. But it's taken quite an interesting turn lately! Turns out I can parse Fexl one character at a time and build the closed executable form in a single pass as I go along -- thanks to a concept which I discovered several months ago but shelved as a mere curiosity at the time. But I'm sure using it now!

I started a proper blog here: http://fexl.com/blog , but we can still use ycombinator.com for discussion.

[fexl]

I created a Fexl discussion group at http://groups.google.com/group/fexl .

You can reach everything from http://fexl.com, including the Blog and Discussion group.