[PLUGIN, WIP, 0.23] kRISC - kOS with a RISC heart

[marianoapp]

kRISC - kOS with a RISC heart

This is a fork of the kOS Autopilot v0.9.3 in which all the code execution is done in a RISC-like CPU.

I started this project as a proof of concept to see if I could write a formal grammar for the KerboScript language and ended up rewriting most of kOS itself. The parts that remains mostly unchanged are the ones in the "outer shell" or that deal directly with KSP, for example the Bindings, SpecialValues, SteeringHelper, TermWindow, etc.

Highlights

• The script code is parsed with a LL(1) parser using a formal grammar defined for the language
  
• The parsed code is then compiled into a stack-based program similar to a RPN calculator or the NET IL itself
  
• FAST (see the Benchmarks section)
  

Parsing and compilation

• The grammar was written with TinyPG which automatically generates the needed classes for the parsing with no additional dependencies. There's no need to modify these classes by hand except for removing the "Compiled" flag of the RegExs that is not supported by mono.
  
• The resulting AST from the parser is then compiled into a series of simple opcodes that the CPU can execute efficiently.
  

Differences for the user respect to Nivekk's kOS

• The grammar supports numbers in scientific notation
  
• The grammar supports negative numbers / expressions (no more 0-... ).
  
• The terminal window can be scrolled via PageUp/PageDown
  
• This version does NOT include an in-game editor
  
• Syntax errors highlighted with correct line number and position
  
  

Internal architecture overview

• A Program is simply a list of opcodes
  
• A Trigger is a function that is called on every update (commands like WAIT UNTIL, ON, WHEN are implemented this way).
  
• A ProgramContext is a class that contains a Program and related values, like the instruction pointer and its triggers.
  
• A CodePart contains tree code sections: InitializationCode, FunctionsCode and MainCode
  
• The Compiler returns a CodePart object
  
• The ProgramBuilder builds a Program from one or more CodeParts assembling the different sections in the correct order.
  
• The CPU continues the execution of the current program in every update until it finds a wait or has executed the maximum configured number of opcodes per update
  
• The BoundVariables were modified so that they query the value to KSP only once per update.
  
• There is a class called SharedObjects which contains a reference to every major piece of the mod, so instead of passing a reference to a CPU, a Vessel, etc. you pass an instance of this class. This has the advantage that when a reference changes (like the Vessel on docking) you don't need to update every reference that exists to it.
  
• Most of the classes have been designed to tolerate the lack of other pieces of the mod, and that is why the CPU can work without a binding manager or a terminal window.
  
• Locks are implemented as a call to method pointer, so when you "lock" a variable you are only updating its method pointer.
  
• The ProgramFile class replaces the File class (didn't like the name collision with System.IO) and adds the possibility to save the files of the hard disk as a zip file encoded with Base64 for file sizes that are as low as 25% of the uncompressed file. Since mono doesn't provide an implementation of System.IO.Compression an external library (SharpZipLib) was necessary. This library is not needed if file compression is not enabled (by default is not).
  

Configuration

A new "Config" class was added that handles the mod configuration (through PluginConfiguration) and since its a SpecialValue is possible to make changes in the configuration directly from the terminal window.

Executing "list config" shows a list of all the (three for now) configuration options.

Benchmarks

• To measure if this version was really faster than the others I had to add some execution statistics to all versions (code below)
  
• The statistics show the total Update time (measured in CPU::Update) and the total Execution time (measured in CommandRunFile::Update)
  
• The time was measured using the System.Diagnostics.Stopwatch class and restricting the game to use only one core (this is VERY important, otherwise the times would be distorted)
  
• The number between brackets for kRISC is the configured maximum instructions per update.
  
• The methodology for the test was as follow:
  
  • Copy the corresponding version of the plugin dll to the GameData\Plugins folder
    
    
  • Start KSP and place the test rocket in the launchpad
    
    
  • Switch to archive, run the launch program and wait until it ends (about 2:11 in-game time)
    
    
  • Revert to launch and repeat
    
    
  • Close KSP and repeat from point 1 for another version
    
    

[table=width: 500]

[tr]

[td]kOS version[/td]

[td]Run 1[/td]

[td]Run 2[/td]

[/tr]

[tr]

[td]Nivekk's kOS v0.9.3*[/td]

[td]18.50s[/td]

[td]17.70s[/td]

[/tr]

[tr]

[td]Erendrake's kOS v0.11.0[/td]

[td]19.70s[/td]

[td]18.80s[/td]

[/tr]

[tr]

[td]kRISC (40) [/td]

[td]0.70s[/td]

[td]0.50s[/td]

[/tr]

[tr]

[td]kRISC (100)[/td]

[td]1.03s[/td]

[td]0.98s[/td]

[/tr]

[tr]

[td]kRISC (200)[/td]

[td]0.99s[/td]

[td]1.13s[/td]

[/tr]

[/table]

*Nivekk's kOS include the 0.23 fix and the until loop lag fix

These times will be different for everyone but the relation should be constant.

My computer is somewhat old so that explains why kOS lags so much, but even having a fast computer everyone can benefit from having a few extra CPU cycles

Versions used in the tests (include the source with the statistics modification and the matching compiled dll)

• Nivekk's kOS 0.9.3: link
  
• Erendrake's kOS v0.11.0: link
  
• kRISC: link
  

Repository

https://github.com/marianoapp/kRISC

To comply with the rules

• Name and version: kRISC v0.1 based off Nivekk's kOS 0.9.3
  
• Authors:
  

  
  

  • kRISC: Mariano (me)
    
    
  • kOS: Nivekk and everyone who collaborated in the project
    
    

  [*]License: Inherits kOS' GNU GPL

[Camacha]

O dear, another interesting alternative Can you explain the main benefits for end users for this way of handling things? And are you planning to maintain this, or is it merely an exercise?

Good job, by the way

Edited February 22, 2014 by Camacha

[Faark]

Interesting, kOS was ever about performance? Just wondering, since apparently no one ever converted kOS scripts into actual net byte code and let .NET jit compile it to simple native code. No simulated cpu could beat that in terms of performance.

But that's a huge step into that direction and thus definitively an improvement.

[marianoapp]

Can you explain the main benefits for end users for this way of handling things?

Performance. This is a test I just made of a craft that decouples nine different hovering crafts, each one with its own 3 PI controllers. As you can see the FPS barely moved from no script running to nine hovering crafts when using kRISC, but for kOS the performance quickly reduces for every additional craft to the point of being unplayable (note that after six crafts the game already grind to a halt).

Javascript is disabled. View full album

Interesting, kOS was ever about performance? Just wondering, since apparently no one ever converted kOS scripts into actual net byte code and let .NET jit compile it to simple native code. No simulated cpu could beat that in terms of performance.

But that's a huge step into that direction and thus definitively an improvement.

Convert to .NET byte code was my initial idea but after some thought I realized that the overhead of type checking and conversion (kerboscript being loosely typed) would probably compensate any gains in performance.

[rhoark]

Looks promising. Now it might be possible to have artificially slow units low in the tech tree.

[skykooler]

Looks promising. Now it might be possible to have artificially slow units low in the tech tree.

This would be awesome! Start with bulky, heavy, slow Apollo-specced computers near the beginning, and progress through to near-modern-day speeds when you've reached the end of the tech tree!

[Camacha]

Performance. This is a test I just made of a craft that decouples nine different hovering crafts, each one with its own 3 PI controllers. As you can see the FPS barely moved from no script running to nine hovering crafts when using kRISC, but for kOS the performance quickly reduces for every additional craft to the point of being unplayable (note that after six crafts the game already grind to a halt).

You had my curiosity. But now you have my attention.

Even though I think performance was artificially limited in kOS, there are also some definite unintentional problems. Can you provide any insights into how this version of kOS could or could not combine with the other initiatives currently under development? Would it, for instance, be possible to use the bones of this version with the extra syntax/commands of the other versions without all too much work? Or would that mean a complete rewrite?

[Dunbaratu]

I like this but the forking of kOS has me worried. At the moment I have to choose between whether I want the better underlying infrastructure that this mod would give, or if I want the extra features that erendrake's version has added after the point of code forking.

[erendrake]

This is really cool work! Enabling multi part missions is something scripting engines are great for and before now it has only been for those with newer machines. Thank you for sharing!

[erendrake]

I like this but the forking of kOS has me worried. At the moment I have to choose between whether I want the better underlying infrastructure that this mod would give, or if I want the extra features that erendrake's version has added after the point of code forking.

If marianoapp wants to, I'm sure we could merge our effort and make one really great scripting project. It's a lot of work to build something like this on your own, having a team to back you up can really help.

[Camacha]

If marianoapp wants to, I'm sure we could merge our effort and make one really great scripting project. It's a lot of work to build something like this on your own, having a team to back you up can really help.

Not to mention maintenance is more likely in the long run. I think fragmentation and branches dying because of lack of interest are the biggest threats to great ideas at the moment.

[marianoapp]

I'm all for collaboration, in fact right now I'm rearranging the project to make merging with erendrake's kOS easier. I'm going to keep adding the features that were included in kOS after my fork trying to keep both as compatible as possible. Once both projects are in sync feature-wise we can merge them into a single great one.

Talking about keeping projects compatible and I already deviate when I added the capability to run programs on other units of the same vessel. This wasn't into my plans but I really wanted to make a dropship that released drones.

[erendrake]

I'm all for collaboration, in fact right now I'm rearranging the project to make merging with erendrake's kOS easier.

[rhoark]

Is it decoupled enough to target another language at the simulated CPU?

[Camacha]

Talking about keeping projects compatible and I already deviate when I added the capability to run programs on other units of the same vessel. This wasn't into my plans but I really wanted to make a dropship that released drones.

Looks like air-to-air docking with multiple units might get a little easier. I did that with two (and maybe three) units, but KSP needed some convincing to do that. A small fleet should make it even more interesting.

Edited February 24, 2014 by Camacha

[Dunbaratu]

This wasn't into my plans but I really wanted to make a dropship that released drones.

That's an awesome demonstration of the capabilities. I like it.

It makes me want to design a Voltron that assembles itself....

[marianoapp]

Is it decoupled enough to target another language at the simulated CPU?

Yes it is, you just have to create a new class that inherits from kOS.Compilation.Script and override the Compile method.

[erendrake]

@marianoapp Just FYI, when you announced you really cool work on this we were about to release a new version of KOS that adds a few new features. The commits for this release are on the master kos branch as of a few hours ago. I wont be adding any more commits to the KOS master branch until we are done with the merge I just wanted to give you a heads up.

[marianoapp]

Great!

I just finished merging all the changes introduced in v0.11.0, so now only remains to merge v0.11.1

It's going to be a busy night...

Edited February 27, 2014 by marianoapp

[erendrake]

Great, and I just finished merging all the changes introduced in v0.11.0, so now only remains to merge v0.11.1

It's going to be a busy night...

Sorry about that. If we had not been so close i would have waited.

[Camacha]

So this is a question of sooner rather than later? Sweet. I was really loving the prospect of this, but assumed it would take some time.

This place has some great energy.

[marianoapp]

Sorry about that. If we had not been so close i would have waited.

Don't worry, I already did all the heavy lifting merging v0.11.0, this should be a little easier

[Boamere]

I'm all for collaboration, in fact right now I'm rearranging the project to make merging with erendrake's kOS easier. I'm going to keep adding the features that were included in kOS after my fork trying to keep both as compatible as possible. Once both projects are in sync feature-wise we can merge them into a single great one.

Talking about keeping projects compatible and I already deviate when I added the capability to run programs on other units of the same vessel. This wasn't into my plans but I really wanted to make a dropship that released drones.

http://youtu.be/58WwE4oGNUo

As a noob to KOS (yeah we all have to start somewhere )I don't understand how you got those little craft to do that without a controller on them, also is this addon just to make KOS easier to use including Fps? Or is it much bigger than that?

Thanks

[marianoapp]

I used module manager to add a kOS module to all of the stock command units just for aesthetics reasons. This project is a heavily modified version of kOS, but we are now in the process of merging it with the main version of kOS to have the best of both worlds

[Camacha]

I used module manager to add a kOS module to all of the stock command units just for aesthetics reasons. This project is a heavily modified version of kOS, but we are now in the process of merging it with the main version of kOS to have the best of both worlds

Now that we are talking about kOS units, I was thinking that we could use a bit more variety anyway. You could figure that pods might have computers included, but I think there is room for some seperate units too. The current one is a bit largish for some applications on smaller vehicles, even though I like the non assuming simplicity of the thing.

Edited March 1, 2014 by Camacha