Functional Rust: Cooking Beef

I caught the eye of Brainfuck-like language Cow . And I decided to write for him an interpreter on the newfangled Rust . And since Rust is a multi-paradigm language, the writing style of the program will be functional. To find out what happened - please under the cat.

I will try to keep the narration in the form of a tutorial, questions in the comments, valuable remarks about the lack of functionality - there too: we will fix it! In the meantime, let's go.

Preliminary design

Virtual state cows machines will be stored in an immutable state variable. All changes will be made using functions that have the following semantics:

 fn change(previousState: CowVM) -> CowVM // newState 

It looks like Elm , Redux , maybe something else that I myself do not know. Is not it?

In fact, exactly what is seen very well from the very beginning how to store data makes this task suitable for a functional approach.

Indeed, what is the Cow virtual machine?

• The command array is the most common integer array;
• Memory - the second is the same simple integer array;
• The current command cell is the index of the cell in the command array;
• The current memory cell is the index of the cell in the memory array;
• Register is almost a normal integer. Why almost? We learn further!
• ???
• PROFIT

Already at the very beginning of work on a task, I’m sure that all data at any stage of the program’s work will be stored that way. There will be no additional fields or views , the customer will not throw a couple of modifications of business logic ... A programmer's dream!

How are we going to maintain immunity?

In fact, it is possible to maintain immunity only in one way - every time you need to change something in the state of our program - we recreate an absolutely new state, save it and throw the old one into a landfill called out of the scope . The following magic features of the Rust language will help us with this:

• Treit Copy . If you come from the OOP, then the structures with the copy trait defined on them are not a reference type but a value type .
  
  You can play here , but if it is short, assignment does not take a variable, but copies it.
• Magic struct update syntax . This thing suddenly copies the fields from the old structure to the new one.
  
  IMPORTANT: Unfortunately, it does not copy the parameters at all, on which the Copy treit is not defined (in our case, this is Vec <i32> ). He just transfers them. And this is very important, because you can get caught up with all sorts of such errors. BUT just not in our case! After all, we don’t care about the old structure - what is transferred from it does not matter to us - we will never use it. This is a freebie !!

Model

The model, it’s a structure, will be one in our program - just the COW virtual machine:

 #[derive(Debug, Default, Clone)] pub struct CowVM { pub program: Vec<u32>, pub memory: Vec<i32>, pub program_position: usize, pub memory_position: usize, pub register: Option<i32> } 

Let's add some goodies to our structure - Debug, Default, Clone. What is it and why - you can read in my previous article .

Reducer

Here, in general, there is nothing complicated either. Following the semantic Zen defined at the preliminary design stage, we rivet to each opcode of the language its own separate command, which accepts the virtual machine and creates a new, already changed, which later returns.

For example, consider the function for the very important opcode mOo - the command shifts back one pointer to the memory cell:

 pub fn do_mOo(state: CowVM) ->CowVM { CowVM{ memory_position: state.memory_position-1, program_position: state.program_position+1, ..state } } 

The whole function does only two things - shifts the pointer to the memory cell 1 back and the pointer to the instruction cell 1 forward. Note that not all functions shift the pointer to the program cell forward, so it was decided not to allocate this functionality as a separate function. It takes a bit of space — a half line, and the function call would occupy approximately the same place, so in general it doesn't matter ...

Well, okay, let's move on to more interesting things. Remember, I said that our register is not quite normal? This is the best (and perhaps the only adequate) way to store a nullable value in Rust - the type of Option . The way, by the way, straight from the hell of functional programming. Perhaps we will not go into what it is; let us just note that such an approach is imposed by the language itself first, and secondly it is completely different from all your languages ​​in which there is nil , null and others like them. Such languages ​​are usually called classic OOP languages: Java , C # , Python , Ruby , Go ... There’s no point in continuing. Just get used to this state of affairs.

Let's return to our sheep. Since the register can be empty, and maybe not empty, you have to work with it as with Option . And here is the source code of our reducer:

 pub fn do_MMM(state: CowVM) -> CowVM { match state.register { Some(value) => { let mut memory = state.memory; memory[state.memory_position] = value; CowVM{ register: None, program_position: state.program_position+1, memory: memory, ..state } }, None => { CowVM{ register: Some(state.memory[state.memory_position]), program_position: state.program_position+1, ..state } }, } } 

See these 4 closing brackets in the end? Look scary. No wonder all the same, many functional languages ​​do not use brackets. Brrr ...

Note on the road is not a very elegant way to change the value in the memory of our virtual machine. Nothing better is thought out, can you tell me in the comments?

To be honest, we note that there are no arrays in "purely functional" languages. There are lists or dictionaries. Replacing an item in the list is O (N) , in the dictionary O (logN) , and here at least O (1) . And it pleases. And the memory of the form:

 {"0": 0, "1": 4, .... "255": 0} 

shakes me to shiver. So let it be as it will be.

We do the rest of the commands by analogy - you can look at them in the source code.

The main cycle of the program

Everything is simple:

• We read mu-mu-th source,
• Create a new virtual machine with empty memory and a full array of commands,
• We execute all the commands sequentially until the work of the program is completed.

Since we have a functional approach, we need to do everything without cycles: recursively. So do.

Let's define the main recursive function - execute :

 fn execute(state: CowVM) -> CowVM { new_state = match state.program[state.program_position] { 0 => commands::do_moo(state), 1 => commands::do_mOo(state), 2 => commands::do_moO(state), 3 => commands::do_mOO(state), 4 => commands::do_Moo(state), 5 => commands::do_MOo(state), 6 => commands::do_MoO(state), 7 => commands::do_MOO(state), 8 => commands::do_OOO(state), 9 => commands::do_MMM(state), 10 => commands::do_OOM(state), 11 => commands::do_oom(state), _ => state, } execute(new_state) } 

The logic is simple - we look at a new command, execute it and repeat it all over again. And so on to the bitter end.

That's all. COW Interpreter - Ready!

This main program cycle

You ask me - "Is this a joke?" The same question I asked myself when it turned out that in the "multi-paradigm" (ha-ha!) Rust language there is no Tail Call Optimization . (What is it - read here .)

Without this entertaining thing, you will very quickly find out for yourself why stackoverflow is named that way .

Well, you have to redo the cycle.

To do this, remove the recursion from the execute function:

 fn execute(state: CowVM) -> CowVM { match state.program[state.program_position] { 0 => commands::do_moo(state), 1 => commands::do_mOo(state), 2 => commands::do_moO(state), 3 => commands::do_mOO(state), 4 => commands::do_Moo(state), 5 => commands::do_MOo(state), 6 => commands::do_MoO(state), 7 => commands::do_MOO(state), 8 => commands::do_OOO(state), 9 => commands::do_MMM(state), 10 => commands::do_OOM(state), 11 => commands::do_oom(state), _ => state, } } 

And we will run the loop directly in the main function:

 fn main() { let mut state = init_vm(); loop { if state.program_position == state.program.len() { break; } state = execute(state); } } 

Do you feel the pain of world functional programming? Not only did this language make us forget about the beauty of native recursions, it also made us make a mutable variable !!!

And in fact - unfortunately it will not work like that

 fn main() { let state = init_vm(); loop { if state.program_position == state.program.len() { break; } let state = execute(state); } } 

due to reasons that are hidden in the twilight ... In fact, due to the fact that the variables created inside the loop disappear when they go out of scope (on the next line in this case).

Reading mu-mu source

But in the work with IO in Rust there is nothing functional. Totally. So this part is beyond the scope of this article and can be found in the source code of this interpreter.

Conclusion

According to the subjective sensations, the Rust language had managed to rust without aging. And the PLO in it is not some PLO, and the OP is not quite the OP. But - "multi-paradigm". Although, maybe at the junction of these paradigms you get something WOW ! It remains to hope so - and pista on Rust .

However, there are obvious advantages in the functional approach. Having written the whole program succeeded:

• Do not enter never into the corridors of the PLO and create a single class.
• Never to have problems with delaying, reassigning, pointing, and God still knows what Rust has there when working with variables. Yes, we didn’t make any references at all, variable variables (well, almost), I almost forgot what borrow and ownership . Frankly, writing without thinking about what you can fail to compile because of all this is real pleasure.
• We have managed to never again enter into lifetime parameters - this is really the twilight side of the whole Rust . Frankly, they scare me (x: &'a mut i32) and I am very glad that I could have avoided all this.
• We have not implemented a single treyta. So-so is an achievement, but suddenly it turns out that in the AF, the traits are not so necessary / important.
• All these functions are inherently clean, and they are very easy to test (perhaps the next article will be about this, although the difference between testing in OOP and OP is known for a long time and it is easy to googling like that).

Afterword

Thanks to everyone who read it. I invite you to comment on the article, where we can discuss the different programming paradigms in Rust . Comments, suggestions - all the same.

Link to the source

Thanks

Thank you so much @minizinger for developing particularly difficult for me (because the most non- functional ) places in the program, inspiration and support.