Enigma Machine – Type Provider Edition

by Pezi 23. January 2015 07:28

Following up from @isaac_abraham’s awesome F# Enigma machine emulator, I decided it would be 10x cooler if it was in a type provider, because let’s face it, everything is 10x cooler once it’s in a type provider.

Here a some pictures of it in action!

enigma1 enigma2

As you can see, it uses an extensive property system that presents a menu along with the various controls to setup your enigma machine, and then finally to translate some text.  This TP is written with my InteractiveProvider as per usual.  On my first attempt at this during my lunch break today, I did succeed but I was growing increasingly frustrated with the somewhat contrived mechanism with which to process responses from properties, the text to display in intellisense, and the properties to show.

 

The Old System

The InteractiveProvider (henceforth known as IP) presents a very flexible yet slightly complicated interface with which to generate types.  Essentially, you implement IInteractiveState on some state object of your design, and IInteractiveServer on another type, which deals with processing responses.  The IP will display intellisense and options via the state, and when the user selects a property, the server decides what to do with it and returns some new state.

This is very cool as your state object can be whatever you like – record types, DU’s, or full classes.  Responses to property access can similar be of any type you like, and can be different on each property if you like.  The problems with this system are

  1. The creation of the text and properties is separate from the response handling of that property.  This can make it hard to read and reason about.
  2. It is a bit unsafe because everything gets boxed, unboxed, and each time the server has to deal with a response,  based on the current state you have to make sure you are dealing with the correct types coming back from the TP which can be a hit messy and detract from what you are really trying to do
  3. Although each state might require its own unique data, there is not any way to represent one thing without threading all the previous state through.  For example, if I want the user to enter a bunch of letters via properties until they press the [End] property, I can’t do this with just a string, Id have to carry the rest of whatever data I was using as well. This gets unwieldy quickly. There is no way to separate concerns.
  4. Again on with point 3, because of this it is not really possible to create re-usable chunks of state that perform common functions such as accepting input. 

 

 

The new system

In order to address this, I introduced another layer of abstraction, ‘cos you can never have too many layers of abstraction right? :)

type InteractiveState<'a> = 
    { displayOptions : 'a -> (string * obj) list 
      displayText : 'a -> string 
      processResponse : 'a * obj -> IInteractiveState 
      state : 'a } 
    member x.ProcessResponse o = x.processResponse (x.state, o) 
    interface IInteractiveState with 
        member x.DisplayOptions =  x.displayOptions x.state 
        member x.DisplayText = x.displayText x.state

This new record type is essentially a super-duper state object.  It brings together the creation of stuff and the processing of responses into the same place.  You can see it takes 3 functions and a bit of state, ‘a. 

  • displayOptions will be called with the current ‘a and is expected to generate a list of properties to display and a boxed version of some type that will be passed back to the server when the user selects that property.
  • displayText will be called with the current ‘a and used to generate what appears in intellisense when this type is currently selected (more on this later)
  • processResponse will be called with the current ‘a and is expected to return a new IInteractiveState

Because this is a generic type, it does mean when you start to use these together, they are going to need the same ‘a which is a bit of a pain, but it is readily solved by creating a DU of all the possible types that the various states in your system need.

type EnigmaTypes = 
    | Core of EnigmaCore.Enigma 
    | Strings of string 
    | Rotors of MachineRotor 
    with 
        member x.Enigma = match x with Core e -> e | _ -> failwith "" 
        member x.String = match x with Strings s -> s | _ -> failwith "" 
        member x.Rotor = match x with Rotors r -> r | _ -> failwith ""

This is not very nice but a very reasonable trade off for the power attained. Now the server object itself becomes very simple (infact this can be generalized as well)

type Enigma() = 
    interface IInteractiveServer with 
        member x.NewState: IInteractiveState = start() :> IInteractiveState        
        member x.ProcessResponse(state: IInteractiveState, response: obj): IInteractiveState =      
            let state = (state:?>InteractiveState<EnigmaTypes>) 
            state.ProcessResponse(response)

 

Start Your Engines!

Now the system is ready to rock!  You will notice when the server starts it calls start() to obtain its first state.  All the states are now just instances of record types.  start() looks like this

let start() = 
    { displayOptions = fun _ -> ["Begin!",box ()] 
      displayText = fun _ -> "Welcome to the type provider Enigma machine!" 
      processResponse = fun (e,_) -> mainMenu(e) :> _ 
      state = Core defaultEnigma }

this is as simple as it gets and not doing much interesting, you can see it returns one property “Begin!” along with a boxed unit type. I don’t care about the response type as there is only one property so I know it must be that being selected. 

processResponse simply creates the next state using the function mainMenu( .. ) which it passes the current state, in this case the default version of the enigma machine.

mainMenu(..) is much more interesting and too long to show here, so I will show some extracts / condensed versions

type MainMenuResponses = 
    | Nothing 
    | SelectLeftRotor 
    | SelectMiddleRotor 
    | SelectRightRotor 
    | SelectReflector 
    | SetWheelPosition 
    | SetRingPosition 
    | CreatePlugMapping 
    | Translate

let rec mainMenu(enigma:EnigmaTypes) =

{ displayOptions = fun _ -> ["# ",box Nothing; 
                             "Select a new left rotor",box SelectLeftRotor 
                             "Select a new middle rotor",box SelectMiddleRotor ….. ] 

  displayText = fun _ -> printMachine enigma.Enigma 
  processResponse = fun (e,r) -> 
    match unbox<MainMenuResponses> r with 
    | Nothing -> mainMenu(e) 
    | SelectLeftRotor -> 
        enterText("",[for i in 1..8-> sprintf "Rotor %i" i, box (string i)], 
            (fun s -> "Choose the rotor to place on the left"), 
            (fun s -> 
                let e = { e.Enigma with Left = getRotor s , WheelPosition 'A' } 
                mainMenu(Core e) :> IInteractiveState), 
            (fun _ -> false) )

 

The first bits are pretty straight forward, it shows the various menu options and boxes which one was selected using the DU defined above.  processResponse then unboxes the return value, matches on it,  then does something with the result.

In this case, it is calling another function called enterText – and this is where it gets really cool!  enterText is defined as follows

let rec enterText(state:string,options,genDisplayText,continuation,repeatCondition) = 
    { displayOptions = fun _ -> options 
      displayText = fun d -> genDisplayText d 
      processResponse = fun (current:EnigmaTypes,c) -> 
        let s =  current.String + string c 
        if repeatCondition s then enterText(s,options,genDisplayText,continuation,repeatCondition) :> _ 
        else continuation s 
      state = Strings state }

This function is designed based on the observation that when I want to accept an arbitrary amount of text from the user, the following is required

  1. A list of what inputs to be shown
  2. A way of knowing when to stop accepting more inputs (and recursively creating more types)
  3. A continuation function, that accepts the completed output and then generates some other state.

What is really awesome with is is that the enterText function simply takes a string – it doesn’t know or care about the Enigma object – this is made possible by the fact that we can now create a closure over the previous state’s data within the continuation lambda function, allowing us to decouple the recursive-text-entering portion of the type system.  Very nice!

Engage Turbo Mode!

Great!  now I can create re-usable state chunks and control stuff via closures.  However, there is one more usually contrived problem that this system solves very well.  Let’s take the menu function Adjust Wheel Position.  This one is a little bit of a pain because it requires several steps – first you must pick which wheel you want to manipulate, then you choose the letter you wish to set it to.  Usually you would have to model these as separate states, which would be confusing if you wanted to do the same thing somewhere else - but now you can actually compose these functions and closures together so that the whole intent and flow is clear within the same definition.  For example :

let selectMachineRotor(continutation) = 
    { displayOptions = fun _ -> 
        ["Left Wheel", box LeftRotor 
         "Middle Wheel", box MiddleRotor 
         "Right Wheel", box RightRotor] 
      displayText = fun d -> "Select a rotor." 
      processResponse = fun (current,c) -> 
        continutation (c:?>MachineRotor) 
      state = Rotors MachineRotor.LeftRotor }

This function accepts a continuation function and asks the user to select a wheel, and calls the continuation function with their choice

| SetRingPosition -> 
    let apply l  = function 
        | LeftRotor -> { e.Enigma with Left = { fst e.Enigma.Left with RingSetting = l }, snd e.Enigma.Left } 
        | MiddleRotor -> { e.Enigma with Middle = { fst e.Enigma.Middle with RingSetting = l }, snd e.Enigma.Middle} 
        | RightRotor -> { e.Enigma with Right = { fst e.Enigma.Right with RingSetting = l }, snd e.Enigma.Right }

    selectMachineRotor(fun rotor ->                  
        enterText("",[for i in 'A'..'Z' -> sprintf "%c" i, box (string i)], 
            (fun s -> "Choose a letter"), 
            (fun s -> 
                let e = apply (RingSetting s.[0]) rotor 
                mainMenu(Core e) :> IInteractiveState), 
            (fun _ -> false) ) :> IInteractiveState )

When the SetRingPosition menu item is selected, it returns the selectMachineRotor function, and the continuation function passed to uses the enterText function allowing the user to pick a letter, and finally the result is applied to the Enigma object and the whole thin is returned back to the main menu.  Very cool!

Straight away this is useful as the AdjustWheelPosition menu item has to do a very similar thing

| SetWheelPosition -> 
    let apply l  = function 
        | LeftRotor -> { e.Enigma with Left = (fst e.Enigma.Left, l)  } 
        | MiddleRotor -> { e.Enigma with Middle = (fst e.Enigma.Middle, l)  } 
        | RightRotor -> { e.Enigma with Right = (fst e.Enigma.Right, l)  }

    selectMachineRotor(fun rotor ->                  
        enterText("",[for i in 'A'..'Z' -> sprintf "%c" i, box (string i)], 
            (fun s -> "Choose a letter"), 
            (fun s -> 
                let e = apply (WheelPosition s.[0]) rotor 
                mainMenu(Core e) :> IInteractiveState ), 
            (fun _ -> false) ) :> IInteractiveState )

 

Conclusion

The IP has had a bit of a face-lift which makes it easier to write and read what is going on.  Plus you can have an Enigma machine in a type provider.  Who wouldn’t want that!  The code is a little bit of a mess at the moment, but I should clean it up soon and move the new super-state into the common interfaces project. 

Tags:

F# | type providers

The North Pole Type Provider: Escape from Santa’s Grotto!

by Pezi 24. December 2014 02:41

This post is part of the F# advent calendar, which is filled with all sorts of other cool blog posts, be sure to check it out.  Thanks to Sergey Tihon for organising!

It’s Christmas!

Happy Christmas everyone!  I have the honour of the Christmas Day F# advent calendar post (Thanks Tomas, ha!).  I had a whole bunch of different ideas, and typically, I decided to choose the largest, most complicated one.  Because of this, there is a lot of code written in just a couple of evenings. It is for the most part, badly designed, horribly written, nowhere near finished and should not be used as an example on how to write anything approaching nice F# code!  /disclaimer

Some Background

If you know me at all you will know that I tend to write lots of crazy type providers.  This will, of course, be no exception.  In fact, even though I wrote this in just a couple of evenings, it’s probably the most complex ridiculous TP to date.   To achieve this, I have used my Interactive Provider which is basically a type provider abstraction that lets you create crazy type providers without writing any provided types code at all!  Rejoice.

The TP is a game, which is based on the legendary circa 1980~ game Rogue. I realise that many people will not know about Rogue (although the term Roguelike is used a lot more these days) so I will explain a few bits that characterise a roguelike game

  • There are no graphics.  The character is typically thrown into a dungeon which is rendered using ASCII characters only.
  • They are procedurally generated.  Not just the dungeons themselves – a red potion in one game will be very different to your next.
  • They are hard. Although there is an end, usually you just see how far you can get before you die
  • They have permadeath. When you die, that’s it – start over from the beginning
  • They are typically very complex. Modern roguelikes are epic works of engineering with vast amounts of crazy stuff you can do, cause, and interact with, often in strange and fascinating ways.

Escape from Santa’s Grotto!

So, Christmas Eve is finally over and Santa plus crew have been celebrating a bit too much in the grotto / workshop.  One things leads to another, and everyone is smashed on all the sherry picked up from the previous night.  Santa wakes up at the bottom of the grotto, hungover, and unfortunately discovers that most the Reindeer and Elves are either still on the sherries or have fallen asleep drunk.  Now, everyone knows drunk Reindeer and Elves are incredibly violent, even to Santa.  Can you help him navigate his way up through 5 levels of the grotto?

image

Above shows a typical example of a starting position.  Important note! For this to work you MUST use a fixed-width font for your editor tooltips!  I recommend Consolas 10-12  (anyone would think type providers were not designed to run games!)

Here is a list of the possible characters and what they depict in the dungeon

  • This is Santa, the player
  • Horizontal wall
  • |   Vertical wall
  • #  Corridors that connect rooms
  • .   Floor
  • /  Open door
  • +  Closed door
  • *  Piles of presents
  • % Carrots of various types
  • !   Mince pies of various types
  • E  Elf
  • R  Reindeer
  • <  Stairs leading downwards
  • >  Stairs leading upwards

As the game progresses, you gain experience by killing hostile elves / reindeer and will level up, which increases your maximum hit points, makes you hit harder and more often.  Santa will heal over time, but he also gets hungry and must eat.  Perhaps you can find some other items that can heal you?

A typical full level map might look something like this

image

Notice you cannot see any items or monsters that are not in Santa’s field of view (FOV).  The FOV algorithm is different in corridors to when you are in rooms, and it is largely terrible due to time constraints, but it still works ok :)  Each turn, you are presented with a list of properties in intellisense that represent the available actions for you to perform.  Some of these require further input in the form of another list of properties.  The available actions are as follows.

  • Movement. Represented as N, NW, W, etc.  This will move you one tile in that direction, if possible
  • Pickup. This will take an item at your feet and put it in your inventory. Note: you will see in the status at the bottom of the screen when you are standing on something you can pick up
  • Use Item.  This will present you with a list of things in your inventory which you can use.  Only trial and error will tell you what a Blue mince pie does, be careful!
  • Drop Item.  You can drop things.  You might notice that Reindeer and Elves sometimes eat stuff they stand on.  Perhaps this could be useful?
  • Open / Close.  You will be asked to pick a direction, at which point the door (if it exists) will be opened / closed. Note that the monsters cannot open doors!
  • Wait .  Waste a turn doing nothing.  Santa gradually heals over time, be he also starves to death if you don’t keep him fed!
  • Climb.  This will take you to the next or previous level if you are standing on some stairs.

Strategy

  • Roguelikes are risk management games.  Often a lot of chance is involved.  Food should be a top priority as lack of that will kill you off given enough time, no matter what.  To this end you should try to make sure that the monsters do not eat any food lying around on the floor by ensuring they don't walk on those tiles.  
  • Similarly, eating mince pies is a game of chance, you could get lucky, or it might go horribly wrong.  In any case, once you know what a specific colour pie does, you will know all other pies of that colour do the same thing.  
  • Another way to identify mince pies is to drop them in the path of monsters and see what happens to them if they decide to eat it.  
  • Use doors to your advantage - monsters cannot open them.  
  • Sometimes you will be able to sneak past monsters without waking them - you must balance this with fighting and gaining experience, as the monsters will get tougher in each level.  
  • Monsters cannot follow you up and down stairs.
  • It is easy to cheat as this is a type provider, you can just undo your steps. Don’t do that, you are only cheating yourself!
  • There are (at time of writing!) 8(!!) different types of mince pie! be sure to experiment, there are some interesting ones such as this!

image 

In order to attack something, simply move in its direction.  At the end of your turn, any monsters that are awake will probably try and close in on, or attack you.  You will see the results of this at the bottom of the screen in the status messages.  If there are more than 2 status messages, you will be presented with a single property named “More” which will continue to cycle though the messages until they are exhausted.  I didn't have time to write anything except very rudimentary AI so they are pretty dumb and you should be able to get them stuck on each other, in corridors, and all sorts.  Actually!  I have changed my mind.  They are all still drunk, that is why their path finding is practically non-existent, and not because I had no time to do it!

Some final notes!

Well, I must admit I was furiously coding away just to get this to work at all.  There are still some bugs in it, and balance is way way off.  Roguelikes usually have an element of luck but this one more so than normal :)  I only managed to get a small portion of what I would have liked in, but it still is quite playable (albeit incredibly hard sometimes) and I am fairly sure it is the only roguelike type provider in existence!

To get it running

Head on over to my github, clone and build the Interactive Provider.  The IP works by scanning assemblies in a given location to find types that implement IInteractiveServer which it then uses to provide the types. Because of this you will need to point the Interactive Provider to the location of the XMAS_2014.dll file, like so

#r @"f:\git\InteractiveProvider\InteractiveProvider\bin\Debug\InteractiveProvider.dll"
type GamesType = PinkSquirrels.Interactive.InteractiveProvider< @"F:\git\InteractiveProvider\XMAS_2014\bin\Debug\">
let games = GamesType() 
games.``Start The North Pole``.

 

Please have a go, and let me know if you beat by tweeting @pezi_pink and / or #fsharp over on twitter!  If you manage to escape, be sure to let us know how many presents you managed to pick up on the way!

HO HO HO!

Tags:

F# | type providers