I just have to say that it is an annual competition, which is held within ICFP Conference. The detailed information about the Contest can be found in Wikipedia. In general, each year there is a new 72-hour task to be completed.
The number of people on the team is not limited; there is no restriction on the programming language either. That is, it is possible for 72 hours to plunge into the world of problems that this year’s organizers have created and come back with a bunch of impressions.
Of course, if such things interest you. On my own behalf for people who first hear about it, I would recommend to read adept’s report(Russian language) on participation in 2006 ICFP Contest. This report is a kind of classic. Just so, after reading this report I had a great desire to take part in this competition.
Each year, all our colleagues think of the programming language to use for performing the task. And each time after ongoing arguments we choose Java. It just happened, so this year was not going to be an exception, and we definitely used Java application, but as it turned out later, not only it.
Day One (Friday) (The Contest Starts At 15:00)
In the office, just at that time all the competitors had a small rush job to do, that is why we started reading the task only at 18:00 and later. The task, by the way, turned out to be quite extensive, and was composed of 27 pages of A4. There were quite a bit of irrelevant information concerning manuals for different processors. We started reading the documentation. And, I need to say – after a busy working week – it goes too hard.
In order to win the contest this year, it was necessary to write a program for Lambda-Man, who has to run away from the ghosts through the field, where alongside with the ghosts there were pills, large pills, fruits … and I have to say, that’s it. After eating a large pill located on the map, LMan within a limited time gets a chance to make a feast of ghosts without any table-ware. For any positive actions LMan performs, he receives the corresponding number of points
- pill - 10 points - large pill - 50 points - ghost - 200-1600 points - fruits - 100-5000 points
If you are familiar with the old classic games, then you must have immediately realized that I am referring to Pac-Man.
That is, for the task to be completed it is supposed to create a sequence of actions for PacMan …. written in assembly language for Lambda-Man CPU. “Forget your favorite programming language for another 72 hours! You will write in assembler language during the next 3 days.”
Processor Lambda-Man turned out to be a little strange. It consisted of four registers, but we did not have direct access to them, 3 stacks, and 27 instruction statements. It wasn’t the first time I had heard of this type of processor, but I had never before programmed for it. Here is an example of a simple program that calls the function with one parameter for LMCPU
Minimal example of creating and using a local variable. LDC 21 LDF body ; load body AP 1 ; call body with 1 variable in a new frame RTN body: LD 0 0 ; var x LD 0 0 ; var x ADD RTN
19:56 (4 hours after the start)
We held the first general meeting of our team, and made the following decision
- We will write the program in a high level language which is compiled in LMCPU - One of us will be in charge of collecting the resulting task - High-level language we are going to use will be Clojure - We will not write their own processor implementation, because the organizers gave us a chance to test our programs/software in their implementation, written in JS
Why Clojure after all? Participating in this competition I have asked this question more than once. The basic idea was that assembler for LMCPU was specifically invented to make it easy to compile from the Lisp-like functional language. For compiler generation we use ANTLR, but we did not find proper grammar description for Lisp, that..can work with ANTL. The closest language appears to be Clojure.
21:18 (6 hours after the start)
We have a semi-automatic build of our task to be further sent for scoring. Rома is working at creating a compiler with Clojure * Pasha and I are looking into assembler and playing in HTML + JS, which the organizers provided.
What appeared to be an unpleasant surprise for us was that labels used in the examples on this site did not work, (So we had to tweak JS a little by introducing additional constants and labels)
LDC 0 LDF 4 CONS RTN LDC 0 LDC 1 CONS RTN
LDC 0 LDF step_function CONS RTN step_function: LDC 0 LDC DIRECTION_UP CONS RTN
In addition, Misha and all the others started learning Closure as quick as they could, so that by the time we have a compiler, we could write something in Clojure. We got all the information for our learning at the site Clojure Koans.
23:30 (8 hours after the start)
We have a parsed Clojure tree by Rоma.
01:00 (10 hours after the start)
02:34 (11,5 hours after the start)
Pasha is mastering the instruction of DBUG processor, and finally we see how the incoming data will look like.
(0, ((11, 16), (2, (3, 0))))
((0, ((11, 8), 2)), ((0, ((10, 10), 2)), ((0, ((11, 10), 2)), ((0, ((12, 10), 2)), 0))))
((0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, (0, 0))))))))))))))))))))))), ((0, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (0, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (0, 0))))))))))))))))))))))), ((0, (2, (0, (0, (0, (2, (0, (0, (0, (0, (2, (0, (2, (0, (0, (0, (0, (2, (0, (0, (0, (2, (0, 0))))))))))))))))))))))), ((0, (3, (0, (0, (0, (2, (0, (0, (0, (0, (2, (0, (2, (0, (0, (0, (0, (2, (0, (0, (0, (3, (0, 0))))))))))))))))))))))), ((0, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (2, (0, 0))))))))))))))))))))))), ((0, (2, (0, (0, ...
My compiler with ECMAScript has started giving the first sparks of life.
var f = 2; f++; var b = 5; var c = f + b;
And then I realized that a simple test “that it generates,” will not be enough for me. Of course, each time I could check the assembler that was generated directly in HTM from the organizers themselves, but it was not enough, and it was not fairly quickly either. Moreover, hacking something was very easy, and every time to test generation manually is not rational.
That is why I decided that in the process of testing I wouldn’t rather use assembler that has to be generalized but give preference to the state of the processor after the program completion.
Integration tests with the browser I also seemed not a very good idea, so I decided to write an emulator LMan CPU.
Most processor instructions were emulated, and when someone just started waking up I went to bed at last.
Day two (Saturday)
While I was still sleeping, Rома continues to write Clojure compiler. One by one, the instructions are added, and the tests for the compiler looks approximately as follows
test( "(+ 2 4)", "LDC 2\n", "LDC 4\n", "ADD" );
I wake up, join him and realize that I missed the point that in case of failure or improper format instructions or valueson stack registers, the processor will fall into catatonia. I quickly make the correction, gradually introducing checks for data types used.
While Міshа got sick, unable to bear sitting under the air conditioner in the fierce heat, Anastasia comes and helps me finish all the instructions of the processor with failed states. Meanwhile Pаshа is sitting and analyzing the data structures in assembler
Our processor is finally able to fully emulate all the necessary instructions and the first test clearly demonstrates it
//(> (+ (- 3 1) (* 2 2)) (== 2 2)) ArrayList instructions = LambdaManProcessor.parseAsmProgram( "LDC 3\n"+ "LDC 1\n"+ "SUB\n"+ "LDC 2\n"+ "LDC 2\n"+ "MUL\n"+ "ADD\n"+ "LDC 2\n"+ "LDC 2\n"+ "CEQ\n"+ "CGT"); processor = new LambdaManProcessor(instructions); processor.run(); assert(processor.topStackValue().equals(1)); // result of expression
We are chuckling at the work done, reports to Roma that now it’s possible to feed the results of program compilation with Clojure to the processor emulator, and verify the correctness of the processor status. It added confidence to our efforts. Now all the programs we are writing, on condition that checks are provided by our emulation processor, will normally run on the processor of the organizers.
Teamed with Pаsha, we check the programs that he had already written on our processor. It works!
Realizing that we did not have time to write anything on Clojure, quickly switch to assembler only and try with Pаsha to write anything that will be able to walk around the map. Anastasia is preparing everything for us to submit it by the end of Lighting Round (first 24 hours).
The first download of our LMan who just quietly goes one way.
We are loading LMan that is supposed to go by the rule of the right hand through the maze, no matter what.
It was a shame the error in calculating the next direction led to breaking the game. We were very upset that at 0 (top), 1 (right), 2 (down), 3 (left), the game did not understand such a direction as 4;) As a result our decision with Lighting was feeble, and could hardly score any points.
While the organizers are laying out an additional task for the ghosts management, we are having a lunch break.
In the task from the organizers that followed, a test condition is added – besides the LMan algorithm, additionally, we will have to be sending algorithms for ghosts (up to 4 algorithms). Those algorithms are also supposed be written in assembler.
Only with some restrictions; for example, the assembler for the processor on which the ghosts program are performed, is completely different. It is more like the x86 processor. In addition, the maximum number of instructions for the ghost algorithm should not exceed 256 instructions, that is, in general, very small, for assembler.
Function Environment Problem
The heart of the problem we faced was something like that: Variables that are transferred to function are always stored in the so-called environment (Environment, or ENV) It means that each function can get an access to their variables via ENV.
Something like this:
And compiler when encounters some variable has to convert the access to this variable to the access to ENV at the specific address. Note that, the first parameter – is the so-called depth environment – One’s own environment – always has the value 0, parental environment – 1, and so on. As follows:
That is, using x, y as a function of first, has to be translated in ENV [0,0], ENV [0,1]. But, using the same variables as a function of second, will look like ENV [1,0], ENV [1,1].
Basically, there is no problem in the generation of such a code. While compilation we can see the level of function, and replace the desired value. This code is generated quite easily.
Problems arise when we use a recursive call.
As you can see, the access to one and the same variables from the parent environment has to be translated into different instructions.
It was the problem we were hitting for a long time. For a very long time. Moreover, our lively “discussion” of what we primarily need made Rоmа flee to another room 🙂
Our first program in Clojure* that enabled LMan simply walk to the right
(defn step [state world] (tuple (0 1))) (defn main [world anything] (tuple (0 step)))
Others keep on thinking about the problem and additionally occasionally write tests for Clojure ‘.
Soon there appear if type operators and basic functions for working with lists first, last, nth.
Pаshа and Anastasia energetically create something like macro-assembler for assembler of ghosts. x86 assembler was not really like that. There are no full jump and labels. We immediately decided to use regexps and to replace labels for the number of line, and made our own “functions.”
We did lack functions, so we had to “reserve” the word FUNCTION and RETURN, which were replaced
mov h, pc add h, 3 mov pc," + labelName
mov pc, h
We read аlgorithms for ghosts in PacMan, it helped us understand what we want to do within the time given. Yes, our ghosts have to run to the LM by the shortest route, but sometimes – scattered in the corners of the map. The ghosts have different speed, so some may run directly on the box LM, and some – a few steps ahead of LM (proactively).
As soon as we started active creation of programs in Clojure, we had to tweak DBUG instruction, which produced the value in the grid on the screen. The main “problem” of this function was that it “took off” the value of the stack top, breaking up the logic of the program. However that problem was also solved. By the way, before that function had been completed, I watched the results of the algorithm work in the direction LMan followed 🙂
(defn dbg [fn] (first (tuple ( fn (DBG fn) ) )) )
We are actively practicing in writing functions in Clojure ‘
(defn nextCellByCurrentDirection2 [world direction location] (if (== direction 0) (decy location) (if (== direction 1) (incx location) (if (== direction 2) (incy location) (if (== direction 3) (decx location) (manLocation world) ) ) ) ) ) (defn nextCellByCurrentDirection [world] (nextCellByCurrentDirection2 (manDirection world) (manLocation world)) )
Quite a big problem was that for the calculation of the data. It was supposed to transfer additional parameters from the higher level to the lower one. It resulted in the situation where the variable world, appeared almost in all functions.
Finally we got the first algorithm for LMan that can move by right hand or left hand rule. It was not much, so Anastasia and Pasha’s ghosts quickly caught us, but that was at least something. The ghosts at that moment were able to run to LMan * the shortest way and scatter in different directions. The program for ghosts was the same for all 4, but the initial parameters (Where to run first, how long to run) differed, so our ghosts were running like living things.
Day three (Sunday)
That night I saw damn brackets in my dreams. I realized that Clojure is certainly the functional language, and so on. For us to create any more or less normal LMan, it is a must to just write the algorithm in that language. Especially since Roma added an additional function let, which greatly reduced the calls of some functions. Roma even started writing tests in Clojure 😉 and tackled the implementation of A-Star Besides, addition, many additional functions were added, like filter, map, find, needed for the implementation of A-Star algorithm.
However, the LMan algorithm did not come about.
My attempts to write the wave algorithm in Clojure failed and I gave up;)
At 17:30 on the last day I got myself busy with compiler for ECMAScript ‘
By Sunday evening our ghosts were able to:
- Run to LM for n steps
- Run proactively (in the area of LM square in the direction of its movement)
- Scatter into corners (allows to escape the traps of maze)
- Scatter if LM has eaten a large pill
- Stop doing anything and run to LM if it is nearby (but hasn’t eaten a large pill yet) – it is our co-called strategy EAT QUICK which we managed to achieve after our ghosts proudly ran passing an accessible LM
- Initiate primary parameters according to one’s own number (that is, the ghost strategy is common but all the parameters are set individually)
And it was all written in macro-assembler and in different files, then js replaced all labels, constants, processed functions, and created a huge blanket of 200+ lines.
Day four (Monday)
In the morning, Pasha teamed with Roma, and they continued to implement A * in Clojure ‘. Anastasia ran the decision on JS on several maps, and found that on some of them we can even win, but with a small number of points (as ghosts ate LM very well).
Waking up at 13:00 I rejoiced over our algorithm, and ran to fix our LMan’s brain, in order to prevent it from dying of ghosts under any suitable situation. First, we added a little bit of logic; in which case, we can count ghosts as a wall while calculating algorithm. It allowed LManu not to die so often. In addition, if LMan ate a large pill, he didn’t think of ghosts as an obstacle and ignored them at all. There was, of course, an idea of chasing ghosts, in case a large pill was eaten, but it turned out that in this case, LMan died more often 😉
Results and outcome
Lots of emotions 😉
A little bit upset, of course, that we failed to write more 🙂
It is unlikely that our LMan will take a winning prize 🙁
In contest like this, when a lot of things are changing and from time to time some people take over others to solve one and the same problem, it is tests that help understand the state of the code.
Concerning minuses – we have written 2 compilers instead of one;) and, in general, we split into groups with two approaches to the solution of the problem.
Pros of our work – ghost-team (Anastasia and Pasha) proved the viability of the pair-programming model (all Saturday afternoon and Sunday they wrote together).
All in all – it was fun though exhausting 😉
Next year – I will certainly participate again