calculator
calculator
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
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.
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.
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:
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.
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';
}
And for Flash Flood it is probably helpful to test different algorithms with them,
although I will have to hand-optimize the HVM code.
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.
(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.
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)
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
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
-
- Posts: 8
- Joined: Tue Aug 16, 2011 12:35 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.
My code currently weighs 174 bytes (with six no-ops). I guess sub-160-byte solution is possible, but not seriously tried it.
- dangermouse
- Posts: 89
- Joined: Sun Jun 05, 2011 8:14 pm
- Location: deep space computing AG
- Contact:
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!
[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!
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"
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"