hacker.org

Posted: **Sat Nov 15, 2008 3:29 pm**

Whoa, I got tired of recalculating all the jumps, so I wrote a tool which sort of adds support for labels to hvm. It isn't coded in hvm, though

Posted: **Sat Nov 15, 2008 5:18 pm**

There's talk of this kind of thing on the Challenges forum, quite a while ago - writing assemblers to calculate jump targets, etc.

I haven't gone that far though. I just implemented a kind of indirect subroutine system, so subroutines are numbered 0,1,2,etc, and they all have the same call site within the first 9 characters, so it's easy to call them. Then when the size of a subroutine changes, I only need to change the calculation for a single jump instruction, and potentially one other jump if the length of the first jump instruction changed.

It's nice because the knowledge about the length of each subroutine is localised near the subroutine itself, and it's easy to transplant subroutines from one program to another. I haven't used them in any other programs though - the only HVM challenges I can see at the moment either require writing very short programs, or programs that execute in very few cycles, and this system fails on both counts.

It was useful for calculator, though, because of the recursive nature of bracketed expressions, and the usefulness of having an easily-callable subroutine to parse a multi-digit number.

Posted: **Mon Nov 17, 2008 10:16 pm**

I even wrote a small compiler and assembler, to translate C-like code to
HVM.

The assembler is responsible for the calculation of jumps and numbers.

The compiler supports C-like syntax:

Code: Select all

int     printHello (void);
void    printWorld (void);

void    main (void)
{
        int a = printHello ();
        printc a; printc ' ';
        printWorld ();
        printc '!'; printc '\n';
}

int     printHello (void)
{
        printc 'H'; printc 'e'; printc 'l'; printc 'l'; printc 'o';
        return ',';
}

void    printWorld (void)
{
        printc 'W'; printc 'o'; printc 'r'; printc 'l'; printc 'd';
}

I think, I can use these programs with the labyrinth challenge.

And for Flash Flood it is probably helpful to test different algorithms with them,
although I will have to hand-optimize the HVM code.

Posted: **Sun Aug 23, 2009 4:16 pm**

yup, my code looks like:
(push 0) "/ position
(store 1000)

(call plusExpression)
(printInteger)
(halt)
...
(label plusExpression)
(call mulExpression)

...
(label mulExpression)
(call factor)
...
(label factor)
(call peek)
(sub $( )
(jmpEq0 parExpr)
(push 0) "/ current-val
(label digitLoop)
(call peek)
(dup)
(sub $0)
(jmpLt0 noDigit)
...
the code itself is an array constant in Smalltalk.
Most of the trouble lies in the variable branch-offset computation code, though.

Posted: **Sun Jan 17, 2010 11:22 pm**

one trick i use for the variable jumps... is to just way overestimate the length of it... ie #####**+- will handle any long distance jump up to the hundreds... i currently still write the code itself by hand but i leave the jumps in that form to easily adjust the numbers i havent writen a compiler yet because i have yet to see a language, besides lua and matlab, that can return more then one "object" (wrapping the pointers in an array doesnt count for me hehe, though im sure thats what those languages are actually doing)

Posted: **Sun Apr 18, 2010 4:47 pm**

At last, I solved this challenge, hours of debugging (by hand) and tricky jumped ("c"), etc.
What I want to know is how long your codes are?
I wrote about 430 Instructions.

Posted: **Sun Apr 18, 2010 10:02 pm**

Thanks for enjoying this challenge

My code is 370 instructions long.

Posted: **Sun Apr 18, 2010 11:42 pm**

My code is 317 instructions long but could easily be shortened. It was generated using a simple compiler to avoid calculating addresses by hand.

Posted: **Sun Apr 18, 2010 11:56 pm**

My original solution was 336 instructions long. I ran it through my assembler again and with improved jump calculations i'm now down to 296 instructions.

Posted: **Mon Apr 19, 2010 6:55 am**

After optimization, my code has become 189 instructions long.

Posted: **Mon Apr 19, 2010 7:09 am**

It seems to become a KOTH challenge here...

Posted: **Fri Mar 11, 2011 5:08 pm**

Mine is around 500 instructions long, mostly filled with whitespace between the subroutines. It could easily be made much shorter in size, but i got a bit tired of recalculating all those jump addresses.

I wrote the solution in a sort of pseudo code. When i was confident the algorithm would work, i manually translated it to HVM and debugged it untill it worked.

This challenge really taught me a lot, but for the next big HVM challenge i'll probably write myself some kind of compiler.

BTW, nice to see some of you got it with such small programs

Posted: **Sun Aug 21, 2011 12:37 pm**

I took 2 hours to solve this challenge, due to the lack of assembler or other tools whatsoever. But I think the lack of assembler was actually a pro, not a con, as the code size dramatically changes depending on how the jump/call target is calculated.

My code currently weighs 174 bytes (with six no-ops). I guess sub-160-byte solution is possible, but not seriously tried it.

Posted: **Tue Jul 31, 2012 2:32 pm**

my code is 603 lines. i first coded help subroutines, then a main loop
[help sub 1] [help sub 2] [main loop: call to parse goto main ] [parse: if is digit then dothis $ if ) then dothat $ ...]

for the algorithm:
first i thought about using some kind of unification algorithm similar to Prolog, then to write a parser which constructs a tree to be traversed, then i read in the dragon book about LR parsers.

in the end i used shunting yard made by http://en.wikipedia.org/wiki/Edsger_Dijkstra

great challenge!

Posted: **Wed Apr 03, 2013 12:27 pm**

Huh, my syntax is quite different from previously posted.
It's very similar to assembly and it's quite useful, because I have full control over generated code (it allows manual optimization for size/cycle count).
Interesting challenge

Screen from my IDE (C# + WPF):
http://wstaw.org/m/2013/04/03/Calculator.png
Now it's high time to solve "Labyrinth"