calculator

Discussion of challenges you have already solved
paranoia
Posts: 1
Joined: Sat Nov 08, 2008 6:40 pm

calculator

Post by paranoia »

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 :)
gfoot
Posts: 269
Joined: Wed Sep 05, 2007 11:34 pm
Location: Brighton, UK

Post by gfoot »

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.
Mütze
Posts: 23
Joined: Sun Oct 26, 2008 2:39 pm

Post by Mütze »

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.
blablaSTX
Posts: 11
Joined: Mon Aug 17, 2009 8:12 pm
Contact:

Post by blablaSTX »

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.
nighthalk
Posts: 41
Joined: Fri Jul 31, 2009 8:22 pm

Post by nighthalk »

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)
outsider
Posts: 37
Joined: Wed Jan 07, 2009 12:15 pm

Post by outsider »

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.
tails
Posts: 191
Joined: Tue Jun 10, 2008 7:51 pm
Location: Tokyo

Post by tails »

Thanks for enjoying this challenge :)

My code is 370 instructions long.
User avatar
teebee
Posts: 89
Joined: Mon Nov 10, 2008 3:21 pm
Location: Germany

Post by teebee »

My code is 317 instructions long but could easily be shortened. It was generated using a simple compiler to avoid calculating addresses by hand.
Zeta
Posts: 62
Joined: Thu Apr 16, 2009 3:37 pm

Post by Zeta »

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.
tails
Posts: 191
Joined: Tue Jun 10, 2008 7:51 pm
Location: Tokyo

Post by tails »

After optimization, my code has become 189 instructions long. :)
User avatar
teebee
Posts: 89
Joined: Mon Nov 10, 2008 3:21 pm
Location: Germany

Post by teebee »

It seems to become a KOTH challenge here...
User avatar
zjorzzzey
Posts: 11
Joined: Fri Oct 30, 2009 7:31 pm
Location: NL

Post by zjorzzzey »

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 :)
lifthrasiir
Posts: 8
Joined: Tue Aug 16, 2011 12:35 pm

Post by lifthrasiir »

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.
User avatar
dangermouse
Posts: 89
Joined: Sun Jun 05, 2011 8:14 pm
Location: deep space computing AG
Contact:

Post by dangermouse »

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!
Redford
Posts: 41
Joined: Sat Jul 04, 2009 8:32 pm
Location: Poland
Contact:

Post by Redford »

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" :)
Image
Post Reply