News for hackers. Stuff that matters.
Re:Lisp is Sin (2006) by fexl on Tuesday September 28, 2010 @08:59PM (#1737931)
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);
Re:Lisp is Sin (2006) by fexl on Tuesday September 28, 2010 @10:03PM (#1738071)
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
      )
Re:Lisp is Sin (2006) by fexl on Tuesday September 28, 2010 @10:29PM (#1738133)
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;
      }
Re:Lisp is Sin (2006) by Imbue on Wednesday September 29, 2010 @03:43PM (#1740834)
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.

Re:Lisp is Sin (2006) by fexl on Friday October 01, 2010 @07:20PM (#1749167)
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!

Re:Lisp is Sin (2006) by fexl on Friday October 01, 2010 @07:10PM (#1749147)
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.

Re:Lisp is Sin (2006) by fexl on Saturday October 02, 2010 @05:21PM (#1751386)
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.