Wednesday, February 20, 2019

Unfortunate

Zero-arity combinators often lead to weird behavior and I guess should, in general, be avoided. To boil it down to one example:


[ X Y -> Y X | -> 0 ] 1 2 ==> (2 1)

But

let F = [ X Y -> Y X | -> 0 ] in F 1 2 ==> (0 1 2)

The discrepancy is unfortunate but completely correct according to the operational semantics. In the first case, a lambda expression is applied to its arguments, then reduced; in the second case, the lambda expression is reduced, then applied.

It's unfortunate but I think I'll keep it.

Thursday, January 17, 2019

Log 011719

Right, so after some hacking, three things are now on my TODO list.

  1. Rewrite the Sudoku solver.
  2. Fix a renaming bug.
  3. Implement `eval` correctly.
The Sudoku solver is a hack. It is a rewrite of a solver I once wrote in OCaml. It has poor performance since inequalities aren't eliminated leading to way too much work and it also doesn't make use of Egel very well. It could all be done way more principled.

The renaming bug is due to that I tried to avoid renaming completely in the interpreter for performance reasons but, as it turns out, can't.

The two previous tasks are not too difficult. `eval`, however, will need the introduction of fine-grained locking on internal data structures and the implementation of a pure term evaluator.

Problems are that `eval` may at any point change the state of the interpreter, be called recursively, and be called from different threads.

I.e, `eval "eval \"[X->X\"" 1` are examples I am looking at. Guess I better start off with the first two tasks, though.

Tuesday, January 15, 2019

Log 011519

Right, so I am back after a long break to programming on Egel. Last I remembered, I got stuck on implementing basic input/output routines, decided I probably need to support the whole C Posix interface, which also meant having bytes as primitive types, and subsequently abandoned the whole project.

Not sure what I've been doing in the intermediate time. It involved a lot of Brexit posts and playing Magic Arena.

But I returned!

I decided that supporting Posix is overkill for now and just implemented basic reading and writing of Unicode strings to channels as primitives. Which isn't fine, all popular languages have byte IO as primitives too, but -ah well-, whatever.

I also implemented a small Unicode TCP transport for Egel. Combined with eval, that allowed me to write a small server which evaluates Egel expressions for anyone on port 5000.

# Testing Egel's Unicode TCP transport.
#
# The server spawns a listener for each incoming connection,
# evaluates input from there, and sends the result back.

import "io.ego"
using IO
using System

def listener =
    [ CHAN ->
        let IN = read_line CHAN in
        if eof CHAN then close CHAN
        else
            print "received: " IN "\n";
            let OUT = eval IN in
            print "sending: " OUT;
            write_line CHAN (blip OUT);
            listener CHAN ]

def spawn =
    [ SERVER ->
        let CHAN = accept SERVER in
        print "spawned a listener\n";
        let _ = par (spawn SERVER) (listener CHAN) in
            nop ]
     
def main =
    let SERVER = server 5000 5 in spawn SERVER


It works. Neat! I also wrote a small Sudoku solver and uncovered a small bug in Egel.

Tuesday, March 20, 2018

Dots to colons

I changed the dot in `System.nil` into a colon, so now it's `System:nil`. The good part, `.` is now function composition. The bad part, `:` might interfere with CVS, comma separated files, which, despite being called comma separated, often use a colon.

I might change it again. `#`? `$`? I am out of ideas.


Monday, March 19, 2018

Semicolon

What's a language without a semicolon? Since Egel has strict semantics but combinators may be side-effecting, it makes sense to add statements, a bit of a trivial extension, to at least give users the possibility to easily define input/output behavior. For example,

printLine "What's your name?"; let X = readLine in print "Hello, " X "!"

Which is a bit shorter than





let _ = printLine "What's your name?" in let X = readLine in print "Hello, " X "!"

But I guess that'll pay off for longer routines. The easiest manner of generating code for semicolons is therefor a let. But lijero on freenode pointed out that you can also employ a 'semicolon' combinator.

[ X _ -> X ] (let X = readLine in print "Hello, " X "!") (printLine "What's your name?")

So, there are some tradeoffs. The let sugar means I'll generate one combinator for each semicolon, the semicolon combinator needs to be added to the runtime -which I don't like- but you could, for instance, then fold that semicolon over a list.

Then, should the semicolon combinator be a built-in or generated on the fly? I don't know yet. If I had some kind of optimizing compiler, the compiler would need to know about its definition. A C++ defined combinator is a bit faster but also more a bit work.

Looks like I'll go the whole principled way of going for an explicit AST node for a statement, a transform do desugarize that, and built-in C++ combinator.

For a semicolon.

Sunday, March 18, 2018

Eight Reasons Egel is Slow

I checked the program `foldl (+) 0 {0,..,1000000}` against GHC and it's about 16 seconds for the Egel interpreter versus maybe at most 300ms for ghci. Because Egel is a term rewriter it turns out `foldl` and `foldr` have roughly the same performance. That in comparison to an old report on GHC behavior.

The odd thing is that it seems to take more time in the IRC bot, a dynamic library seems slower than the compiled interpreter. It's 16 seconds for the console application versus roughly a minute in the bot.

I am two or three orders off. That roughly corresponds to 2^8 to 2^10, so there are in the neighborhood of at least eight reasons why Egel is slower.
  1. The Egel interpreter is a vannila term rewriter.
  2. The interpreter doesn't optimize.
  3. The language is untyped.
  4. The interpreter uses idiomatic C++ and classes from the standard library.
  5. Thread safe reference counting.
  6. No standard arithmetic primitives.
  7. The bytecode generated is dumb.
  8. The overhead of exceptions.
But not bad for a simplistic robust interpreter. Not bad at all.

I love back-of-an-envelope reasoning.