Thursday, July 27, 2017

Log 072717

Observe the pretty date! I haphazardly moved some code around and implemented further functionality for primitive input/output and basic math libraries. Of course, there were -and still are- some small bugs but the scheme I use seems to work.

So what is left is to make both libraries conceptually neat, and move on and implement a 'prelude' for the interpreter.

Wednesday, July 26, 2017

Log 072617

Well, the interpreter prints. That is, the scheme I've got to implement primitive input/output and a math library compiles and the interpreter is able to run dynamically loadable libraries.

It's a bit rough around the edges and I need to move some code around still, but it works.

Saturday, July 22, 2017

Log 072217

So, Thursday I wrote an introduction to the evaluation strategy I employ in the Egel interpreter. I moved that to the main website and started shaving, rewriting, and removing. Lastly, I updated the pictures a few times which took some work because Inkscape isn't very good at keeping a similar layout for different pictures. Now, it's Sunday and I am reasonably content with the result, though it might be somewhat informal to some people. But, ah well, this is the first time I had the opportunity to get half-baked 'feelings' right while loosely relating what I designed to other approaches so I guess I was entitled to wasting some time on it.

Meanwhile, I didn't code. I decided upon a C++ implementation for primitive input/output because reasons -callback hell, the convenience of Unicode support, minimal dependencies, C++ is reasonably portable, etc.- but that also implies a lot of work I can't seem to find the energy for at the moment.

I need to:
  • Implement channels in C++, an abstraction over several iostreams which is going to be pretty verbose in that it needs to support a lot of operations.
  • Write IO combinators employing that abstraction in a dynamically loadable module.
  • Test all of that. The channel abstraction, the combinators, and module loading.
Too. Much. Work.

The Unreasonable Effectiveness of Dynamic Typing

The Unreasonable Effectiveness of Dynamic Typing for Practical Programs from JavaZone on Vimeo.

Thursday, July 20, 2017

Operational Semantics of Eager Combinator Rewriting


I got a question about the operational semantics of the eager combinator rewrite system I use. It's embarrassingly facile and trivial to explain with two pictures, so here goes.

Say, you have a term language where you want to rewrite an expression consisting of combinators. In Egel's case, each combinator knows how to rewrite itself, therefore, corresponds to a procedure or some code.

You could use a stack and push stackframes for F, G, and H. However, I wanted to experiment with another model, rewriting. Note that since we're rewriting eagerly we're rewriting the outermost expression first.

The operational semantics Egel uses is extremely simplistic: Start with the node which is to be rewritten first, store the result where necessary, and continue with the next node to rewrite.

That's it. Note that the resulting graph is still a directed acyclic graph. That's what enables me to implement Egel's interpreter with native C++ reference counted pointers.

This is, of course, a slow and restrictive manner of evaluation. For one, stack based evaluators are simply faster because pushing data to, or popping from, a stack is less computationally expensive than allocating, and deallocating, heap nodes. Second, it's a term rewrite system so you can't allow for assignment since that would usually allow you to create cyclic structures.

The benefits of this model are threefold. For one, you don't run out of stack space which is really important in a functional language as I have experienced, unfortunately. Second, it is still a tree rewrite system so you don't need to care about tail call optimization. Third, you can reference count.

I simply like this model of evaluation, there isn't much more to it.

Notes: Yes, these are thunks or heap allocated stack frames. No, this isn't done with CPS since CPS is a transformation, not an evaluation strategy. Bytecode is generated directly for this model.

More: Egel also supports exceptions which is a natural extension of this model. It is left as an exercise to the reader.

Wednesday, July 19, 2017

Log 071917

I took a break after running into a few snags. For one, the Ocaml input/output (IO) specification wasn't very good. It neatly describes channels and cleanly separates them into input and output; that looks nice at first glance but what if you want both? I.e., a naive database application usually consists of seek operations followed by reads and writes. It's an odd design decision.

Then there is C++'s manner of working with stdin, stdout and stderr as well as istreams, ostreams and fstreams. They made the standard IO streams uncopyable! Implying you can only pass references but never copy them. Of course, you might be tempted to pass pointers but you run into another whole set of problems. For one, expect lots of template type errors, and also, you're not supposed to call delete when a standard stream goes out of scope.

Then there is the class inheritance design of C++'s streams. It's over-engineered to meet the requirements of an OO type system; here you also see that the type system forces a solution which is simply not that neat though multiple inheritance helps.

Looking at both specifications I can only conclude that C's POSIX file handles specification simply wasn't that bad.

I also started looking at libuv as the basis of file IO, and later multithreading. And I hit another snag: Callbacks don't neatly fit into a mostly referential transparant system. (Well, so far. Unless I come up with a scheme to make it fit.) The problem: Sure you can define a callback, sure it will read values from a pipe, but it can't do anything with it. It simply cannot inform another thread easily to continue evaluation with a calculated value. (Imagine multiple reading threads and one thread who consumes and writes the result back. It's difficult to combine results from multiple threads with one callback.)

I am tempted to roll out my own temporary solution for primitive IO. I am also tempted to ignore libuv and write a PAR combinator using C++ primitives. But libuv is cross-platform, well-maintained, scalable, and popular...