Geekly Articles each Day
📜 ⬆️ ⬇️

Nemerle and satellite, or OP for the little ones


Recently on Habré the mention of Nemerle is often mentioned. Do you want to know what it is and how it is eaten, or rather, how it is eaten with it (tasks)?

I will try to show you with a simple example, but for this you will have to

First of all


I will tell you at once what I won't tell you :)
')
I will not tell you in detail the features of syntax and so on. - Anyone can read this on http://www.nemerle.org/ and google it for details. In short, Nemerle is a hybrid programming language for the .net platform. Hybrid - means that it combines the properties of imperative OOP and procedural, C-like syntax and flexibility and abilities of a functional language.

I will not talk about the features of the paradigm, hygienic macros, and how to change its syntax in this fully compiled static-typed language.

I will not tell you that Nemerle "does not like" variables, and that many imperative things are not available in the language by default: if , cycles for , return , many more. In truth, they are not in the language itself - everything is implemented by special, street macros.

Finally, I will not tell you that Nemerle with phenomenal rigorous-ruleznost is able to deduce the types of objects - so much so that with # 4.0 it rests :)

In general, this will be a bad article, because I will just tell you how beautifully to solve the problem in the functional paradigm, using the Nemerle gadgets. Well, the problem we will have to match the language - with the recently passed contest icfp2009 . Rather, its part - we will write Orbital VM on Nemerle, in a functional style.

For those to whom the lines above said little or almost nothing, I cite a link to the contest specification, and also briefly explain below what the essence is.

The previous contest (for 2008) used the LiveCD Knoppix, equipped with various “batteries”, as a proving ground to prevent anyone from feeling offended - JRE, gcc, ghc (Haskell), CLOS (Lisp), Python. Practice has shown that, due to differences in floating-point operations, not all languages ​​produced the same results, which made it difficult, if not more. Therefore, in the current year (ie, in 2009), the organizers rolled out unambiguous specs on the VM, having made that, it would be possible to bring its solution to the problem.

There were 4 groups of tasks with 4 options (within the group, the tasks differed in initial conditions, between groups - goals), for each group of tasks a binary with bytecode and the initial state of the data memory for OVM were proposed. After the program was loaded into OVM, it was necessary to configure it by setting a number (1000 + N variants) on a special input port of the machine and drive off 1 execution cycle. And then - in flight.

I set forth in my own words - the task as a whole was to read the sensor readings and control the satellite's servomotors, to perform “aerobatics”: bring it to a given orbit; catch up and overtake the alien satellite rolling into the abyss of capitalism , etc. One run on all OVM instructions was equal to one second of simulation time (simsek).

Since only a solution log was required from the teams (namely, a sequence of commands on servomotors with time reference), then, in principle, the task could be solved exclusively “in mind”; but, as the harsh reality showed, all the winning teams used VMs to debug the results. (Moreover, it seems that all the teams, without exception, used VM; some, however, not their own :)).

Details about the misadventures of different teams, and who “dragged” the car from someone, if you do not know yet, you can see here

We will implement it.

For the cause


After reading the specs, you can imagine in general this very Orbital VM (OVM): a register machine with data memory space of 16K, as well as a separate 16K address space for I / O ports (I and O are separate).
Hands and itching to outline a cycle in which the program counter increases in a cycle, and the result read by it from the program file is parsed using bit operations and fed to a huge switch that updates the contents of memory and registers.

All right; so it is possible? Yes. But I suggest not to hurry and follow the path of OP-tao, designing from the top down :)

So, consider the state of the OVM at time T 0 . After executing one instruction, the state of the machine will change. Thus, one OVM instruction for our purposes can be viewed as a function: at the input, the state of the machine S, at the output S *.

S n + 1 = INSTR n (S n );

A small consequence - if each instruction returns a new state, it means that we can save it to a separate list with time stamps to keep the story. Trifle, but nice

Accordingly, the whole program for OVM is a stream of instructions, which is represented by a list of closure functions; To execute a program, it is necessary to call all functions in turn, starting with the very first of the list, transferring to each next state that the previous one returned. We transfer the initial state S 0 to the very first function. Mathematically speaking, we perform a left (literally) convolution (fold left).

So, closer to the code. On Nemerle, on him, darling. I will be brief (s), but with explanations.

Define alias types:
type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .
  1. type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .
  2. type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .
type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .

INSTR is a type that defines a function that takes an OVM state as input and returns an OVM.
PROGRAM - OVM software; a tuple consisting of: a list of instructions (this is a stream of commands) and an initial state. The syntax '*' just says that these two types need to be linked into a tuple.

Our Main function is simple to laugh:
  1. Main (): void {
  2. def (instructions, initialState) = load_program ( "bin1.obf" ); // exception
  4. // configure
  5. vmi_set_problem (1001, initialState);
  6. def state = exec_one_cycle (instructions, initialState); // exception
  7. vmi_set_problem (0000, state);
  9. // since that we can read all data
  10. Console .WriteLine ( "x = {0}, fuel = {1}" ,
  11. vmi_get_x (state), vmi_get_fuel (state));
  12. }
* This source code was highlighted with Source Code Highlighter .

In the first line (where def), a tuple of type PROGRAMM is broken into a stream and an initial state, which is returned by the procedure for loading a program from a binary file.
Next, we set the option number (1001), perform one clock cycle, clear the option register (this is necessary) and output the initial state to the screen (vmi_set_problem doesn’t cause problems for the program, but rather sets the desired value on the configuration port)

A function that performs 1 second of simulation time agreed to look like this:
  1. exec_one_cycle (program: list [INSTR], fromState: OVMState): OVMState {
  2. List .FoldLeft (
  3. program, // <- whom?
  4. fromState, // <- why? (from what?)
  5. fun (instruction: INSTR, currState: OVMState) { // the client executes each instruction
  6. instruction (currState)
  7. }
  8. )
  9. }
* This source code was highlighted with Source Code Highlighter .

As agreed, we do the convolution on the left. FoldLeft is the standard library method for working with lists in Nemerle.
Here, fun in the 5th line is not because I became particularly fun, but the construction of the Nemerle language, which defines an anonymous function “by place”. In principle, you can use the syntax of the delegate, but so clearer. Slightly.
Note that there is no return - the fact is that in Nemerle the last expression is what will be the value returned from the function.

By the way, fun is also a macro from the Nemerle library; it allows you to define a function and returns it immediately

Of the unlighted, but important, remains the structure of OVMState. We tear covers.
  1. class OVMState
  2. {
  3. public MEM: array [ double ] = array (16384);
  4. public OUTS: array [ double ] = array (16384);
  5. public INS: array [ double ] = array (16384);
  6. public mutable STATUS: bool = false ;
  7. }
* This source code was highlighted with Source Code Highlighter .

No magic. One moment - if you want to have a variable in Nemerle, then you need to specify this explicitly (mutable). By default, everything is readonly, out of harm's way.

What do we have left? The answer is loading the program, and converting bytecode to the list of functions (or rather, closures filled with the specific data of each instruction). I think you already understand what will happen next.
  1. load_program (file: string ): PROGRAMM
  3. // many bukaf are omitted well, almost without harm to the meaning
  5. // do
  6. using (stream = File .OpenRead (file)) {
  7. def frames = read_frames (stream);
  8. (load_instructions (frames), load_state (frames))
  9. }
  10. }
* This source code was highlighted with Source Code Highlighter .

The input file (the specs say that it is divided into frames) is read by the frames, and decoded. If you do not go into details about the presence of two types of bytecode (S and D) and so on. And so forth, the decoder for D, for example, will look like below:
  1. /// decodes d-type instruction
  2. def decode_d_type (addr: int , opcode: DOpCodes, r1: int , r2: int ): INSTR {
  3. match (opcode) {
  4. | DOpCodes. Add => make_add (addr, r1, r2);
  5. | DOpCodes.Sub => make_sub (addr, r1, r2);
  6. | DOpCodes.Mult => make_mult (addr, r1, r2);
  7. | DOpCodes.Div => make_div (addr, r1, r2);
  8. | DOpCodes.Phi => make_phi (addr, r1, r2);
  9. | DOpCodes.Output => make_out (r1, r2);
  10. | _ => throw InvalidOperationException (); // exception
  11. }
  12. }
* This source code was highlighted with Source Code Highlighter .

For S-instructions - the same. match is a pattern matching operation, a sort of advanced switch with powerful capabilities.

The final touch - in fact, the designers themselves closures - «make_bla_bla». For example, the “creator” of the add instruction is the multiplication:
  1. make_add (addr: int , r1: int , r2: int ): INSTR {
  2. fun (s) {
  3. s.MEM [addr] = s.MEM [r1] + s.MEM [r2];
  4. s
  5. }
  6. }
* This source code was highlighted with Source Code Highlighter .

Those. we create a closure that can add two operands, and return the newly appeared instruction. Please note that I have specified the types of the function, which is not necessary - Nemerle will display them on their own.

For a snack


I missed a certain amount of the service code, but I hope the thought was clear - we design it top-down, in a procedural manner, which is simpler and simpler in simple tasks than a garden with OOP. The hybrid OOP with the OP in Nemerle contributes to this, allowing you to focus on the task.

Those who wish to practice with this OVM and steer the satellite can use the following tips:
- smoke specs on icfp2009
- arrange OVM as a class, connect it to a project on CSharp, for example, and write a management strategy in it.

All the code from the article and the rest, which was not given, but will be needed, is available on pastebin.org here . The rate of fire on a regular laptop (Core2Duo 2GHz) is ~ 30,000 simulation seconds per second (sim / sec), i.e. it is possible to comfortably control the control algorithms.

PS Something like that. Enjoy your flight. Wire from orbit, if that :)

PPS I almost forgot. Interest for implemented direct VM (selection + decoding of instructions at each step) in C # - about 24000 sim / sec came out. Unfortunately, this does not mean that Nemerle is so fast (20% faster) - this means that in C # the operations on the bits used in the decoder are well optimized.

Source: https://habr.com/ru/post/66349/

More articles:


All Articles