December Adventure

The goal is to write a little piece of code every day in december. See here.

Mine is to experiment a way of representing trees that i learnt in this talk by Aaron Hsu : Dyalog '18: High-performance Tree Wrangling, the APL Way. The APL language is used in this video, but it is accessible even if you don't know it (which is my case, i only played a tiny little bit on tryapl.org). The key idea is to represent a tree as a 1-dimensional array of nodes, each node contains its data, and a reference to its parent (and eventually one to its left sibling).

At the end of the talk i was thinking "what about parsing ? it would be neat if we could do it the same say", and a couple of days ago, i've stumbled upon this talk, by Aaron Hsu again : Text Processing in APL // Aaron Hsu // Dyalog '22. It's very interesting and completely different from other parsing techniques. This section is my preferred part of the talk. He explains that no recursion is used : instead of a call stack, the AST being built is used as a "reified" stack, and it becomes also easy to do good error reporting. (mind blown). I've watched this section several times. Not sure i've understood everything yet.

I've tried a little bit in C, but for the December Adventure i'll give it a try with uxntal. I am not very good at uxntal, it will be an opportunity to get a little bit better. I really don't know what I am doing, but i think it will be fun.

The repository is here: https://github.com/max22-/dal

01/12 and 02/12

I've tried several times to write a little language inspired by Joy. I'll try to parse that :
[dup 0 = [1 drop] [dup 1 - fac *] ifte] ' fac def

So i've set up a uxntal skeleton. Hardcoded that line of code. The idea of the parsing technique of Aaron Hsu is that a string can be thought of a tree where each character is a tiny little branch (and then multiple passes refine the structure of the tree). Then i've implemented a function to add nodes to a tree, and another to transform a string into a tree. Tonight i've started writing another to display a node, which is not finished yet. Beetbug was very useful :)

03/12

Today i've implemented tree displaying (and corrected some bugs). I can now print a tree where the leaves can only be characters. Tomorrow i will maybe add other types like integers, etc. And i will generate a tree with a more complex structure to see if it displays correctly. I also have to find why there is a #02 remaining on the working stack at the end of the program...

04/12

Today I have hard-coded this to create an example tree: 

        
#0000 .type/LIST #0000 ;tree1 add-node
#00 LIT "a .type/CHARACTER #0000 ;tree1 add-node
#00 LIT "b .type/CHARACTER #0000 ;tree1 add-node
#00 LIT "c .type/CHARACTER #0000 ;tree1 add-node
#0000 .type/LIST #0000 ;tree1 add-node
#00 LIT "d .type/CHARACTER #0004 ;tree1 add-node
#00 LIT "e .type/CHARACTER #0004 ;tree1 add-node
#00 LIT "f .type/CHARACTER #0004 ;tree1 add-node
#04d2 .type/INTEGER #0004 ;tree1 add-node
#162e .type/INTEGER #0000 ;tree1 add-node
;tree1 print-tree

The prototype of the add-node function is this :

@add-node ( data* type parent* tree* -: )

And the output of print-tree is this :

        
        
00010 nodes
LIST
    a
    b
    c
    LIST
        d
        e
        f
        01234
    05678
It took me quite some time because i've found some bugs in the code.

08/12

The last 3 days i didn't have much time to work on the december adventure. And i've been distracted by another project...

Today i've corrected a tiny bug i mentioned earlier : now the working stack is empty at the end of the program. (one of the functions was not balanced properly). I have also started to write a lexer, but it is not working yet and i have nothing to show for the moment.

09/12

Today i've done a lot of debugging. Now the lexer sort of works, but isn't completely complete :) It only handles brackets and integers, I need to add words tomorrow. But at least today i can show something :

10/12

I've finished the lexer (i've added 'word' lexing), and debugged it. It looks like it works ! Here is the output :

        
[dup 0 = [1 drop] [dup 1 - fac *] ifte] ' fac def
00049 nodes
LIST
    LEFT_BRACKET
    WORD
        d
        u
        p
    00000
    WORD
        =
    LEFT_BRACKET
    00001
    WORD
        d
        r
        o
        p
    RIGHT_BRACKET
    LEFT_BRACKET
    WORD
        d
        u
        p
    00001
    WORD
        -
    WORD
        f
        a
        c
    WORD
        *
    RIGHT_BRACKET
    WORD
        i
        f
        t
        e
    RIGHT_BRACKET
    WORD
        '
    WORD
        f
        a
        c
    WORD
        d
        e
        f
    EOF
Goodbye.
wst  00  00  00  00 [00] 01  0e  00  02 
rst  00  00  00  00 [00] 01  28  16  da
Nothing left on the stack, cool !