3 ms·
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
by fexl 16y ago
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);
- deleted 16y ago[deleted]
- fexl 16y agoThe 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 )
- deleted 16y ago[deleted]
- fexl 16y agoOK, 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 16y agoNot 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 16y agoThat 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 http://fexl.com/blog , but we can still use ycombinator.com for discussion.
- fexl 16y agoBy 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!