Byte Code Player/Recorder/Optimizer

 Right, so due to side-effecting code a range of optimizations is out of reach. For example, even beta reduction is unsafe under most circumstances. Like below.

  (\f -> f . f)  (print 'hello'; (\x -> x + 1)) 0

That gives one side effect strictly right-to-left reduced, but two when 'optimized' by first beta-reducing the term.

HOWEVER,

It should be safe to just observe what bytecode instructions were emitted during the normal evaluation and glue those together.

At some point, I am going to optimize with some kind of bytecode player/recorder.

Static Programming

 I thought about dynamic programming, ... and then decided against it. Though I want people (me) to be able to inspect the runtime, I don't want people to be able to modify it (except maybe through loading modules).

Simple reason: when the meaning of a symbol doesn't change that shaves off a lookup over a table, plus you enable optimizations, and that implies way faster code.

SectorLisp

 Yah, I love stuff like this. Sectorlisp, in less than 512 bytes.

Searching is calculating, parsing is searching

 I elaborated on the previous small theory and implemented search combinators which I used in a small example to write a parser/evaluator for a simple expression language.

Calculations

I added a small theory of calculations modulo a state and an example. A calculation consists of chained actions where an action is a function working on a state returning a result and a new state.

The gist is:

    ## Calculate:return a - calculate further with value a                                           

    def return =

        [ A S -> (A, S) ]                                                                            

    ## Calculate:chain f g - first do f, then g                                                      

    def chain =                                                                                      

        [ F G S -> [(A, S) -> G A S] (F S) ]                                                     

                                                                                                     

    ## Calculate:run f s - run calculation f on state s                                              

    def run =                                                                                        

        [ F S -> [(A, S) -> A] (F S) ]    

Which are, of course, a monad return and bind with a run function.

The calculation theory and the state game. The state game is straightforward, state and manipulation functions are defined, after which the game loop function results in a chain of actions, which are run on the state.

Pre-release v0.1.1: hotfixed critical regression

 So, a critical regression made the interpreter stall on large input. I followed a hunch that since the lexer became LL(n) instead of LL(1) the UnicodeString's charAt32 method kept resetting an internal pointer resulting in quadratic behavior. The fix worked.

Back at 50KLoc/sec parses on a synthetic example. It warranted a pre-release of v0.1.1 because this was a show-stopper for me.

Ah well. Neat, I guess.

FreeBSD 13.0 compile and install

The Egel interpreter now works on FreeBSD though you need to set the include environment variable. Took me a day to get FreeBSD+dwm running under Qemu on my Macbook Air M1, but felt worth it.

To do: Time & Date

So, time and date functions for Egel. Probably these should come in the form of built-in primitives since you want to be able to natively parse and format them. Following the rule: lift C++ to Egel I am looking at that but find it hard, there's some kind of impedance mismatch going on I find hard to place.

There's just too much going on. Conceptually, C++17 onwards has clocks, time points, and durations. The time points and durations are tied to any of the (five or something) clocks. There's also time_t which is the old unix epoch time I estimate - I gathered I would drop this. Then time points and durations can be expressed in types varying between years to nanoseconds.

A bit hard to disentangle and match to combinators. 

Optimal Reduction. Levy, you serious?

So. Egel is a term rewriter so I ended up discussing Levy-optimal reduction. I never trusted that result.

Optimal probably involves never performing the same reduction during the lifetime of a program.

Two intuitions:

1. Likely there's a result akin to halting that deciding whether two similar reductions might occur during the lifetime of a program is undecidable.
2. Optimal sharing probably can be viewed, or stated as, as an optimal search problem thus then no optimal reduction can exist unless P=NP; i.e., optimal reduction would be optimal search would be a polynomial reduction strategy for NP problems.

Something like that. Old thoughts in the back of my mind.