Blog Archives

Array Support – Meh

So it turns out array support is harder than I thought. I made a poor assumption in my VM that “setting a variable” was always going to look something like:

varname = value

… where these are surprisingly different at the VM level:

varname[index] = value        # "set index"
varname.member = value        # "set member"
value = varname[index]        # "get index"
value = varname.member        # "get member"
varname[index].member = value # "get index, then set member? or set index, then set member"

I am positive there is a parser/VM out there that has solved this in a really obvious and elegant way, but it hasn’t hit me yet. My guess is that I need to make a “reference” not just point at a yapVariable* all the time, but additionally keep track of an index or member name.

Long story short: Hurrrrrrrrrrrrrrrr

Posted in Blog

Short Circuits

I put in short circuits tonight, perhaps better known as “and” and “or”. The basic idea is that if you have if(a and b) and a is false, b never evaluates, and the same idea with if(a or b), except if a is true. This is more than just an optimization; programmers depend on it. It doesn’t mean I didn’t have to do some sad things in my compiler to make this play nice. Still looks good at the syntax tree and opcode level, so I’m happy enough.

My test script:

func first()
    print("first\n")
    return 1

func second()
    print("second\n")
    return 0

if first() or second()
    print("either\n")
else
    print("neither\n")

Graph:

My Syntax Tree!

Output:

first
either

Disassembly:

.kstr   0    "first
"

.kstr   1    "print"
.kstr   2    "first"
.kstr   3    "second
"

.kstr   4    "second"
.kstr   5    "neither
"

.kstr   6    "either
"

.kint   0    1
.kint   1    0

.block 0
     push_ks  0
   varref_ks  1
        call  1
        keep  0
     push_ki  0
         ret  1
         ret  0

.block 1
     push_ks  3
   varref_ks  1
        call  1
        keep  0
     push_ki  1
         ret  1
         ret  0

.block 2
     push_ks  5
   varref_ks  1
        call  1
        keep  0
       leave  0

.block 3
     push_ks  6
   varref_ks  1
        call  1
        keep  0
       leave  0

.main
  pushlblock  0
   varreg_ks  2
      setvar  0
  pushlblock  1
   varreg_ks  4
      setvar  0
  pushlblock  2
  pushlblock  3
   varref_ks  2
        call  0
        keep  1
          or  3
   varref_ks  4
        call  0
        keep  1
          if  1
         ret  0
Posted in Blog

Fun With Graphs

GraphViz is pretty sweet. Now that I have my fancy syntax tree to play with, I decided to drop in some basic dot output into my test program and see what I could get. The results are pretty awesome. This code from a previous post:

var i_am_true = 1

if i_am_true
    print("true!\n")
else
    print("false!\n")

var foo

foo = (2+3)*4
print("With parens   : ", foo, "\n")

foo = 2+3*4
print("Without parens: ", foo, "\n")

func annoying(text)
    var lots = 5
    while lots
        print(text)
        print("\n")
        lots = lots - 1

annoying("SPAM")

…produces:

My Syntax Tree!

Being able to see the tree made a few dumb things obvious. One of the things I’ve already fixed is the “empty expression” problem. With normal C style constructs, this would be represented in code with a lone semi-colon. For example:

int a = func(3+5);;;

… would actually produce two empty expressions at the end. I’m not sure if modern C compilers actually care about empty expression “cruft” in their syntax trees, but I suspect not as it doesn’t ultimately produce additional output, and RAM is cheap.

However, I have two problems with it in Yap, as I’m trying to keep RAM usage sane, and when PYTHON_SCOPING is enabled, empty statements are represented with blank lines! Without any StatementExpr pruning during tree creation, my earlier example would have looked like (stubs colored in red):

My Syntax Tree!

I haven’t decided if things like the StatementExpr are actually useful to the assembler in the future, so I’ve left them alone for now, but it does make the tree look cruftier than it needs to be.

One neat thing about seeing the tree is how obvious certain optimizations become. For example, take this code:

var x = (1+2+3+4+5) * 2

It produces this syntax tree, which would do all of this math every time the code executed:

My Syntax Tree!

However, if you put in a really simple optimization step that simply collapses (depth-first) any basic arithmetic nodes whose children are constants, you end up with:

My Syntax Tree!

This pattern can easily spill onto other operations, such as type conversions, which raises the question of “optimize for speed” vs “optimize for size”. For example, it is probably always worth collapsing a string->int conversion for both considerations, but optimizing out int->string might not be worth it, depending on your goal (I think).

I think proper comparison operators are up next.

Posted in Blog

Copy-on-Write, Assignment Expressions, and Memory Tracing

Copy-on-write was harder than I thought it’d be.

My first implementation was just going to CoW raw string data, and just duplicate the actual yapValue structures over and over, which (in retrospect) was dumb. The yapValue structure had two bools on it: “used” and “shared”, which was a very verbose way of marking a value up to twice (shared is marked if you try to mark a used value). I figured if I cleared all used/shared bools and did a marking pass, that I could safely do whatever I wanted to anything not marked as shared. This is bad.

I can’t assume that I will be doing a garbage collection pass on every op. I’m not sure what the “recommended” op count per GC will be, but doing it for each op is incredibly slow, and the only way the “shared” bool would ever be useful. Also, knowing if YOU are the reason a yapValue is flagged as “used” is impossible in certain contexts, so deciding to continue to manipulate a non-shared object would have been a big mistake.

It turns out the answer was in yapValue’s exposed interface. I changed all of the yapValueSet*() calls to return a yapValue* (instead of void), and added a new function which each calls as the function begins, like this:

yapValue * yapValueSetInt(struct yapVM *vm, yapValue *p, int v)
{
    p = yapValuePersonalize(vm, p);
    // ...
}

I needed to come up with a word that meant “clone the value if it is used”, and kept picturing words like “mine”, “solo”, “privatize”, and ultimately “personalize”. The trick here is that a fresh yapValue structure will not have the used bool set on it, so allocating one and immediately setting its value has the obvious effect. However, once a yapValue is set, it is set in stone until it is released (and returned back to the yapValue free list). I removed the shared bool and audited my code for any bad usages of yapValue. I had to add a couple more yapValueSet*() functions for completeness, but it worked on the first try, if you count “after watching the original version a few days earlier fail and rewriting it” the first try.

So yeah, copy-on-write is annoying, but can be made fairly painless with a strong interface. It might be worth prepopulating my yapValue free list with some “spares” on VM initialization to help out with the potential yapValue thrashing that could happen on a heavily modified value.

I also reworked my grammar to properly support “assignment expressions”. My first pass of my grammar had assignments as statements, which means you can’t use them as an rvalue (the overall statement doesn’t offer a value). Now that this is done, these all work:

var a, var b, var c
a = b = c = 10

var a = var b = var c = 10

var a = 10, var b = 20, var c = 30

The biggest trick with chaining assignments was avoiding the recalculation of the value. Much like C macro argument side effects when passing in x++ on a macro that references the argument multiple times, I couldn’t just reassemble the child expression a second time to offer it to the parent expression, as it might be calling a function, changing some global state, etc. Instead, I mangled my setvar opcode to optionally not pop the value it used. Since the compiler is aware that the owner of this expression is requesting a value, it can set the setvar’s operand appropriately and you end up with some simple assembly output:

var a, var b, var c
a = b = c = 10

produces:

.kstr   0    "a"
.kstr   1    "b"
.kstr   2    "c"
.kint   0    10

.main
   varreg_ks  0
         pop  1
   varreg_ks  1
         pop  1
   varreg_ks  2
         pop  1
     push_ki  0
   varref_ks  2
      setvar  1
   varref_ks  1
      setvar  1
   varref_ks  0
      setvar  0
         ret  0

The operand of 1 on the setvar statements indicates to the VM to leave that value on the stack after setting the variable reference. I should feel lucky that I had a spare operand to abuse! This grammar shake-up has prepared the code for list and dict (syntax like foo[3] = 10).

Finally, I put in a boatload of operation and memory tracing in order to verify all of my copy-on-write shenanigans. I got really tired of stepping through the VM ops over and over, when all I really wanted was a log / blow-by-blow account of what the stack count was and when allocs/frees/acquires/releases happened.

Here’s the script from above with basic tracing on.
… and with value op tracing on.
… and with memory op tracing on.

The output can get a little ridiculous, but it was incredibly useful to make sure I was doing things correctly.

Now I just need to let myself sleep more.

Posted in Blog

Show Your Work

I bet most programmers out there had to be scolded at least one time by a math teacher who was upset that they did all of the work in their head, or skipped a seemingly unimportant step. It isn’t until higher level math that you realize how useful it is to show your work.

I thought about this last night as I struggled with my linking code. I had convinced myself early in the project that I could get away with a somewhat half-assed syntax tree. I’d compile the bits I needed as I parsed, and then would link it all together at the end and everything is great. For the record, this works for most things!

I imagined how much easier it’d be to fix some of the problems I was running into if I just had a proper syntax tree, and then thought about all of the sweet optimizations I could easily detect with one. I have burnt the midnight oil yet again and effectively rewrote yapCompiler.c entirely to build a tree first, and then evaluate it. The new code is infinitely easier to follow and there is a lot less code duplication. It also allowed me to clean out a bunch of ugly cruft in yapCode and yapCompiler, which made me very happy.

Posted in Blog

String Formatting

String formatting is more obnoxious than I thought it’d be. Each language decides to do it in a slightly different way. You have Perl’s dot operator for concatenation, Lua’s dot-dot, and then you have Python and Javascript’s overloading of plus. You also have the printf varieties (string.format(), sprintf(), Python’s % usage). Every programmer out there has a million reasons their favorite language’s string formatting is the best.

I guess that means I should just pick my faves.

For basic concatenation, I punted and went with the plus symbol. I’m currently making my decision to concatenate-versus-add by the current type of the left operand. We’ll see how much I hate it in a few weeks, but for now, I’m satisfied. I would have gone for Perl’s dot operator usage, if it wasn’t for my general fear of it ruining my parser with conflicts due to it being the same syntax someone would do for a member lookup.

For fancy sprintf style formatting, I stole Python’s, although I currently require that you parenthesize the arguments. I’ll probably change this in the future.

Sample script:

print(5+5, "\n")
print(5+"5", "\n")
print("5"+5, "\n")
print(string(5)+5, "\n")
print(int("5")+5, "\n")
print("my name is %s and I am %d years old.\n" % ("joe", 0x1f))

Output:

.kstr   0    "
"

.kstr   1    "print"
.kstr   2    "5"
.kstr   3    "my name is %s and I am %d years old.
"

.kstr   4    "joe"
.kint   0    5
.kint   1    31

.main
     push_ki  0
     push_ki  0
         add  0
     push_ks  0
   varref_ks  1
        call  2
        keep  0
     push_ki  0
     push_ks  2
         add  0
     push_ks  0
   varref_ks  1
        call  2
        keep  0
     push_ks  2
     push_ki  0
         add  0
     push_ks  0
   varref_ks  1
        call  2
        keep  0
     push_ki  0
    tostring  0
     push_ki  0
         add  0
     push_ks  0
   varref_ks  1
        call  2
        keep  0
     push_ks  2
       toint  0
     push_ki  0
         add  0
     push_ks  0
   varref_ks  1
        call  2
        keep  0
     push_ks  4
     push_ki  1
     push_ks  3
      format  2
   varref_ks  1
        call  1
        keep  0
         ret  0

10
10
55
55
10
my name is joe and I am 31 years old.
Press any key to continue . . .
Posted in Blog

Python Scoping

I got Python scoping working as an option. It turns out it is only like 20 or so lines of code of difference in the lexer.

Sample script (PYTHON_SCOPING #defined):

var i_am_true = 1

if i_am_true
    print("true!\n")
else
    print("false!\n")

var foo

foo = (2+3)*4
print("With parens   : ", foo, "\n")

foo = 2+3*4
print("Without parens: ", foo, "\n")

func annoying(text)
    var lots = 5
    while lots
        print(text)
        print("\n")
        lots = lots - 1

annoying("SPAM")

Sample script (PYTHON_SCOPING not #defined):

var i_am_true = 1;

if(i_am_true)
{
    print("true!\n");
}
else
{
    print("false!\n");
}

var foo;

foo = (2+3)*4;
print("With parens   : ", foo, "\n");

foo = 2+3*4;
print("Without parens: ", foo, "\n");

func annoying(text)
{
    var lots = 5;
    while(lots)
    {
        print(text);
        print("\n");
        lots = lots - 1;
    }
}

annoying("SPAM");

Both scripts output this:

.kstr   0    "i_am_true"
.kstr   1    "true!
"

.kstr   2    "print"
.kstr   3    "false!
"

.kstr   4    "foo"
.kstr   5    "With parens   : "
.kstr   6    "
"

.kstr   7    "Without parens: "
.kstr   8    "lots"
.kstr   9    "text"
.kstr  10    "annoying"
.kstr  11    "SPAM"
.kint   0    1
.kint   1    2
.kint   2    3
.kint   3    4
.kint   4    5

.block 0
     push_ks  3
   varref_ks  2
        call  1
        keep  0
       leave  0

.block 1
     push_ks  1
   varref_ks  2
        call  1
        keep  0
       leave  0

.block 2
       start  0
   varref_ks  8
      refval  0
       leave  1
   varref_ks  9
      refval  0
   varref_ks  2
        call  1
        keep  0
     push_ks  6
   varref_ks  2
        call  1
        keep  0
   varref_ks  8
      refval  0
     push_ki  0
         sub  0
   varref_ks  8
      setvar  0
       break  1

.block 3
   varreg_ks  9
      setvar  0
     push_ki  4
   varreg_ks  8
      setvar  0
  pushlblock  2
       enter  0
         ret  0

.main
     push_ki  0
   varreg_ks  0
      setvar  0
  pushlblock  0
  pushlblock  1
   varref_ks  0
      refval  0
          if  1
   varreg_ks  4
         pop  1
     push_ki  1
     push_ki  2
         add  0
     push_ki  3
         mul  0
   varref_ks  4
      setvar  0
     push_ks  5
   varref_ks  4
      refval  0
     push_ks  6
   varref_ks  2
        call  3
        keep  0
     push_ki  1
     push_ki  2
     push_ki  3
         mul  0
         add  0
   varref_ks  4
      setvar  0
     push_ks  7
   varref_ks  4
      refval  0
     push_ks  6
   varref_ks  2
        call  3
        keep  0
  pushlblock  3
   varreg_ks 10
      setvar  0
     push_ks 11
   varref_ks 10
        call  1
        keep  0
         ret  0

true!
With parens   : 20
Without parens: 14
SPAM
SPAM
SPAM
SPAM
SPAM
Posted in Blog