Not only have I done foreign function interface to C, the entire system depends on it.
Every atomic item begins with a pointer to its "type". Following the type pointer is an arbitrary vector of 0 or more machine words which constitute the data for that atomic item.
The type consists of a pair of C routine pointers: a "step" routine and a "show" routine. To write a new type X, you create two C files "type_X.h" and "type_X.c". The .h file typically contains a single "extern" declaration making the type structure visible to the rest of the system. As it stands right now, you must statically link your new type into the Fexl executable. I suppose eventually I or someone else can create a type which allows access to dynamic libraries, but I'm not messing with that right now.
The step routine is called when the atomic item is used as a Fexl function. Typically it should do a small and quick bit of surgery on the stack and return fairly quickly. It should never loop or fail to terminate in a predictable time. I believe this can eventually form the basis for "threading" multiple function reductions in a single process, but for now I'm sticking with a single reduction.
The show routine is used only for introspection, allowing the display of structures for tracing purposes during development and debugging. It returns a string representation of the atomic item, in the form of a valid Fexl token which can be parsed and easily distinguished from other types of atomic items.
With this feature, one can write a Fexl function which lazily converts a raw memory structure into a functional binary tree with tokens at the leaves. Then it is easy to write a Fexl function which lazily converts that binary binary tree into a functional string, or simply prints it directly.
That way even when you're debugging you never have to write a recursive C routine to traverse the memory structures aggressively, or worry about buffering large string representations.
All that is required for general purpose computation is the core "reduce" routine, which handles function application, along with the atomic types for the S and C combinators. To enhance efficiency, I also provide atomic types for the I and Y combinators, which could otherwise be defined in terms of S and C.
The reduce routine itself is under 10 lines of C code, consisting of a "while (1)" loop with some simple logic in the middle. It terminates when the reduction reaches a normal form, or when it loops beyond a maximum number of cycles, or when the memory arena is exhausted -- whichever comes first. So it is guaranteed to terminate.
Regarding the web demo, I have to be very careful with that. I'll be exposing a universal Turing machine to the World Wide Web. Certainly I'll be sand-boxing it, embedding the client's Fexl function inside an environment which does not allow arbitrary operating system calls. Nevertheless, because this is a very new product, I'll need to do extensive verification and testing on it to make sure it's properly sealed off.
Until now I've been fairly cavalier about it, because I've just been using a half-assed Perl interpreter which only calls a few safe routines, and was only exposed to a few trusted users. This new thing is a far more powerful beast, but it's code I can be proud of.
As for the schedule, I'll have to shoot for end of September. Typically I must devote the first half of every month to getting the hedge fund accounting done. After that I have more time for side projects.
One thing that has slipped my schedule is the need to do my own memory allocation inside the arena (the master array of ints). I can't trust any outside memory allocators. I call calloc once to create that arena, but after that it's all my own code. I'm doing the trick where a node begins and ends with a length, and I have a doubly-linked free list, so I can easily coalesce adjacent small free nodes into larger ones.
All my function application nodes are the same size, but there is no such constraint on Atomic! So I have to allow for variably sized data.
Thanks for your interest! Now that I have an audience of at least one, it's fun "blogging" about it here at HN. Thanks Paul Graham!
Every atomic item begins with a pointer to its "type". Following the type pointer is an arbitrary vector of 0 or more machine words which constitute the data for that atomic item.
The type consists of a pair of C routine pointers: a "step" routine and a "show" routine. To write a new type X, you create two C files "type_X.h" and "type_X.c". The .h file typically contains a single "extern" declaration making the type structure visible to the rest of the system. As it stands right now, you must statically link your new type into the Fexl executable. I suppose eventually I or someone else can create a type which allows access to dynamic libraries, but I'm not messing with that right now.
The step routine is called when the atomic item is used as a Fexl function. Typically it should do a small and quick bit of surgery on the stack and return fairly quickly. It should never loop or fail to terminate in a predictable time. I believe this can eventually form the basis for "threading" multiple function reductions in a single process, but for now I'm sticking with a single reduction.
The show routine is used only for introspection, allowing the display of structures for tracing purposes during development and debugging. It returns a string representation of the atomic item, in the form of a valid Fexl token which can be parsed and easily distinguished from other types of atomic items.
With this feature, one can write a Fexl function which lazily converts a raw memory structure into a functional binary tree with tokens at the leaves. Then it is easy to write a Fexl function which lazily converts that binary binary tree into a functional string, or simply prints it directly.
That way even when you're debugging you never have to write a recursive C routine to traverse the memory structures aggressively, or worry about buffering large string representations.
All that is required for general purpose computation is the core "reduce" routine, which handles function application, along with the atomic types for the S and C combinators. To enhance efficiency, I also provide atomic types for the I and Y combinators, which could otherwise be defined in terms of S and C.
The reduce routine itself is under 10 lines of C code, consisting of a "while (1)" loop with some simple logic in the middle. It terminates when the reduction reaches a normal form, or when it loops beyond a maximum number of cycles, or when the memory arena is exhausted -- whichever comes first. So it is guaranteed to terminate.
Regarding the web demo, I have to be very careful with that. I'll be exposing a universal Turing machine to the World Wide Web. Certainly I'll be sand-boxing it, embedding the client's Fexl function inside an environment which does not allow arbitrary operating system calls. Nevertheless, because this is a very new product, I'll need to do extensive verification and testing on it to make sure it's properly sealed off.
Until now I've been fairly cavalier about it, because I've just been using a half-assed Perl interpreter which only calls a few safe routines, and was only exposed to a few trusted users. This new thing is a far more powerful beast, but it's code I can be proud of.
As for the schedule, I'll have to shoot for end of September. Typically I must devote the first half of every month to getting the hedge fund accounting done. After that I have more time for side projects.
One thing that has slipped my schedule is the need to do my own memory allocation inside the arena (the master array of ints). I can't trust any outside memory allocators. I call calloc once to create that arena, but after that it's all my own code. I'm doing the trick where a node begins and ends with a length, and I have a doubly-linked free list, so I can easily coalesce adjacent small free nodes into larger ones.
All my function application nodes are the same size, but there is no such constraint on Atomic! So I have to allow for variably sized data.
Thanks for your interest! Now that I have an audience of at least one, it's fun "blogging" about it here at HN. Thanks Paul Graham!