APL's iota

So it's trivial to implement an APL-like iota combinator.

>> def iota = [ 0 -> 0 | N -> (iota (N-1)) N ]
>> iota 5
(0 1 2 3 4 5)

I subsequently set out to see if I could define factorial in an APL manner. The definition should be something like below.

>> def fac = mult @ map [X -> X + 1] @ iota

But the problem is Egel can't really pattern match readily against a variadic sized array. Take a variadic number of arguments, no problem; match against an n-adic construct, if n is known - sure; match against variadic array, no can do.

So, I either implement car/cdr like deconstruction combinators or I extend the pattern matching features. Where the new snag is that my bytecode doesn't support variadic pattern matching..

Log 082717

I took a small break. Most stuff works now but I hit a small snag which developed after changing the operational semantics of constant application.

>> def f = 1 2
>> f
(1 2)
>> def g = 1
>> def f = g 2
>> f
1

The first definition of f works according to the change in semantics but the second one still optimises constant applications away. I can easily change this but also at a potentially huge performance cost.  *I fixed this.*

I got the dual of variadic application working though, which is nice.

>> def app = [ 0 -> nil |  N -> (app (N-1)) N ]
>> app 3
(System.nil 1 2 3)

Conway's Life in Egel

I implemented some Rosetta Code examples, one is Conway's life which I am quite pleased with.

import "prelude.eg"

using System
using List
using IO

def boardsize = 5

def empty = [ X, Y -> 0 ]

def insert =
    [ X, Y, BOARD -> 
        [ X0, Y0 -> if and (X0 == X) (Y0 == Y) then 1
                    else BOARD X0 Y0 ] ]

def coords =
    let R = fromto 0 (boardsize-1) in
        [ XX, YY -> map (\X -> map (\Y -> X Y) YY) XX ] R R

def printcell =
    [ 0 -> print ". "
    | _ -> print "* " ]

def printboard =
    [ BOARD ->
        let M  = map [XX -> let _ = map [X Y -> printcell (BOARD X Y)] XX in print "\n" ] 
                     coords in
            nop ]

def count =
    [ BOARD, X, Y ->
        (BOARD (X-1) (Y-1)) + (BOARD (X) (Y-1)) + (BOARD (X+1) (Y-1)) +
        (BOARD (X-1) Y) + (BOARD (X+1) Y) +
        (BOARD (X-1) (Y+1)) + (BOARD (X) (Y+1)) + (BOARD (X+1) (Y+1)) ]

def next =
    [ 0, N -> if N == 3 then 1 else 0
    | _, N -> if or (N == 2) (N == 3) then 1 else 0 ]

def updateboard =
    [ BOARD ->
        let XX = map (\X Y -> X Y (BOARD X Y) (count BOARD X Y)) 
                     (flatten coords) in
        let YY = map (\X Y C N -> X Y (next C N)) XX in
            foldr [X Y 0, BOARD -> BOARD | X Y _, BOARD -> insert X Y BOARD ]
                  empty YY ]

def blinker =
    (insert 1 2) @ (insert 2 2) @ (insert 3 2)

def main = 
    let GEN0 = blinker empty in
    let GEN1 = updateboard GEN0 in
    let GEN2 = updateboard GEN1 in
    let _ = map [ G -> let _ = print "generation:\n" in printboard G ] 
                {GEN0, GEN1, GEN2} in
        nop

Cutting Guards

I wrote a small example program, found that the source-to-source transform for getting rid of guards was faulty, and found that since I allow for a variadic number of arguments, a trivial transform doesn't exist.

Below, an example:

     def f = [ X ? X == 0 -> 1 | -> 15 ]

The problem with a variadic number of arguments is that in the above example you would need code for the case where an argument is consumed, but the match failed, and for the case where an argument isn't consumed. Thus, in a trivial solution, you'd copy code for every guard.

There is no trivial solution without copying code - a potential exponential blow-up -, moreover guarded matches add little in expressiveness over just using an if-then-else. I decided to cut guarded commands.

Duals

Well, in Egel you can trivially write down variadic functions, like sum shown below.

>> def sum = [ X, Y -> sum (X+Y) | X -> X ]
>> sum 1 2 3 4
10

But is the reverse possible too? Best I got to was this:

>> def un = [ 0 -> 0 | N -> N (un (N-1)) ]
>> un 5
(5 (4 (3 (2 (1 0)))))

I think I need something like a reverse too though I am not sure. Also get the feeling I am reinventing Lisp. Which is a bad idea I guess, Lisp will always be better at being Lisp than Egel will ever be.

Changes in the Operational Semantics

I decided to make a fundamental change in the semantics. Egel is untyped, so you need to deal with the case where a constant is applied to another constant; i.e., what does "a" 1 reduce to?

I sidestepped the issue until now and went for a scheme where "a" 1 reduces to "a", thus every constant gobbles up any arguments supplied to it. Mostly I did that because it was convenient, the code is somewhat shorter.

But it seems more natural to simply not reduce; i.e., the result should simply be "a" 1. That seems like a little change but users might make small typos, like forget an operator, and find it too hard to debug a program where constants 'magically' disappear.

The trivial case is easy to implement but now all operators also need this behavior. I.e., (1+2) 3 now reduces to 3, whereas it should reduce to 3 3.

Log 081617

Well. I ticked off the items on my to-do list. So, the new one:

1. Switch over to the standard syntax for 'let'.
2. Allow for assignment in the REPL.
3. Maybe allow for object definitions in the REPL.
4. Support a time-out in the IRC bot.

Another four items. Great!

Log 081517

The byte code generation bug turned out to be insignificant but in order to debug it, I changed some code first to trivialize some invariants, then I found the snag.

I fixed some small stuff but didn't find the motivation yet to tick off other parts of the to-do list.

Log 081317

I implemented a quick-and-dirty IRC bot for Egel, a C++ application which allows for online evaluation. That gave me the opportunity to work on a somewhat neat manner of incorporating the Egel runtime in a C++ application.

It works but not to my satisfaction. I need to change and support two things: 1) Evaluation now works in a cumbersome manner with callbacks which need to go. 2) I need to think about a scheme to call Egel routines from the evaluator. I am not sure what I want here but some tighter integration seems in order.

I also found a not so nice bug in bytecode generation. Well, that's a show stopper. I am not worried since I trust the evaluation scheme I got but annoyed that a bug like that can pop up that late during development. I need to either test a lot or idiot proof it, and it turns out I am not idiotic enough to write down really strange programs which bring all bugs to the surface.

Then there is OO. I think I'll need syntactic sugar for an extend relation. That's not too hard but some work.

So, in order, my small todo list below:

1. Fix the byte generation bug.
2. Make calling the evaluator sane.
3. Add extend relation to objects.

The work is never done.

Log 081117

I implemented a scheme for creating objects but I didn't add a safe scheme yet for destructive assignment.

For the moment I see three different approaches:

1. Ignore, just let cycles be created. This what I have now.
2. Detect cycle creation, and fail if a cycle would be created.
3. Conservatively copy, that part of the tree which holds the cyclic reference is copied.

I am also working a bit on an IRC bot but didn't progress very far yet.

Log 080417

Well. I don't feel like doing much. I registered an account at readthedocs and started thinking a bit about performance. On a small test example, determine the length of a list of a million numbers, the interpreter runs in seventeen seconds whereas the Glasgow Haskell interpreter runs in around a second. 17x slower.

The hotspot is, of course, the bytecode interpreter.

There are a number of things I can do to gain some performance:

1. Change the register storage from a container to an array.
2. Fix the amount of copying. (The 'clone' method.)
3. Expand the bytecode a bit since it's minimal but not fast.
4. Use multiple inheritance to remove an indirection from arrays of objects.
5. Write my own reference counting object.

I changed a few lines of code and implemented the first two steps. Performance increased from seventeen to ten seconds on the example.

Quotation

I am thinking of adding a trivial quotation scheme. Nothing difficult, only for combinators. I.e., `x is nothing more than informing the interpreter not to evaluate the combinator x.

I guess I could do it. But is a construct like that useful? I can't get my head around it.

Mike Acton "Data-Oriented Design and C++"

Log 080117

Anyways, after fighting with a small template instantiation problem the 'par' construct works.

Now what?