Notch is Gonna Outdo Himself!


[Note: I/O has now been added]

My son is completely obsessed with Minecraft. It’s an amazing game and the way he plays it, it really nurtures extreme creativity. I honestly haven’t been able to get into it myself but I was pretty intrigued by the ComputerCraft mod which allows you to script the game in Lua. I thought it might be a good way to introduce my son to programming.

Even better, just today Notch announced his latest game and it looks like it will revolve around programming a 1980’s style 16-bit computer! Based on the spec at the site, I just couldn’t resist implementing the DCPU-16 in F# 🙂 I can’t wait for the game to come out!

let memory = Array.create 0x10000 0us
let registers = Array.create 11 0us

let rec cycle () =
    let mem i = (fun () -> memory.[i] |> int), (fun v -> memory.[i] <- uint16 v)
    let reg i = (fun () -> registers.[i] |> int), (fun v -> registers.[i] <- uint16 v)
    let lit v = (fun () -> v), (fun _ -> ())
    let pc, sp, o = reg 8, reg 9, reg 10
    let get v = (fst v) ()
    let set v i = (snd v) i
    let next () = let p = get pc in let n = mem p |> get in set pc (p + 1); n
    let decode () = let i = next () in i, (i &&& 0x3f0) >>> 4 |> int, (i &&& 0xfc00) >>> 10 |> int
    let skip () =
        let skip' i = if (i > 0xf && i < 0x18) || i = 0x1e || i = 0x1f then get pc + 1 |> set pc else ()
        let _, a, b = decode ()
        skip' a; skip' b
    let value = function
        | x when x <= 0x07 -> reg x // reg
        | x when x <= 0x0f -> (x &&& 0b111 |> reg |> fst) () |> mem // [reg]
        | x when x <= 0x17 -> (x &&& 0b111 |> reg |> fst) () + next () |> mem // [next + reg]
        | 0x18 -> let s = get sp in let x = mem s in set sp (s + 1); x // POP / [SP++]
        | 0x19 -> get sp |> mem // PEEK / [SP]
        | 0x1a -> get sp - 1 |> set sp; get sp |> mem // PUSH / [--SP]
        | 0x1b -> sp // SP
        | 0x1c -> pc // PC
        | 0x1d -> o // O
        | 0x1e -> next () |> mem // [next]
        | 0x1f -> next () |> lit // next (literal)
        | x -> x - 0x20 |> lit // literal 0x00-0x1f
    let instruction, a', b' = decode ()
    let a, b = value a', value b'
    let fxy f = f (get a) (get b)
    let fop op = fxy (fun x y -> op x y |> set a)
    let fif op = fxy (fun x y -> if op x y then skip ())
    match instruction &&& 0xf |> int with
    | 0x0 -> if a' = 0x01 then get pc |> set (value 0x1a (* PUSH *)); get b |> set pc // JSR
    | 0x1 -> get b |> set a // SET
    | 0x2 -> fxy (fun x y -> x + y |> set a; set o (if x + y > 0xffff then 1 else 0)) // ADD
    | 0x3 -> fxy (fun x y -> x - y |> set a; set o (if x - y < 0 then 0xffff else 0)) // SUB
    | 0x4 -> fxy (fun x y -> x * y |> set a; ((x * y) >>> 16) |> set o) // MUL
    | 0x5 -> fxy (fun x y -> if y = 0 then set a 0; set o 0 else x / y |> set a; (x <<< 16) / y |> set o) // DIV
    | 0x6 -> fxy (fun x y -> set a (if y = 0 then 0 else x % y)) // MOD
    | 0x7 -> fxy (fun x y -> let z = x <<< y in set a z; z >>> 16 |> set o) // SHL
    | 0x8 -> fxy (fun x y -> x >>> y |> set a; (x <<< 16) >>> y |> set o) // SHR
    | 0x9 -> fop (&&&) // AND
    | 0xa -> fop (|||) // BOR
    | 0xb -> fop (^^^) // XOR
    | 0xc -> fif (<>) // IFE
    | 0xd -> fif (=) // IFN
    | 0xe -> fif (<=) // IFG
    | 0xf -> fif (fun x y -> x &&& y = 0) // IFB
    cycle ()
Comments (18)

  1. joe says:

    Looks great. How would I use it from within f# interactive?

  2. AshleyF says:

    @joe Well Notch has yet to publish any I/O specs. About all you can do with the above so far is to perhaps run the sample code at the bottom of the spec (0x10c.com/…/dcpu-16.txt).

    Define a loader with something like:

    let load = List.iteri (fun i c -> memory.[i] <- uint16 c)

    and then load the memory dump from the spec:

    load [0x7c01; 0x0030; 0x7de1; 0x1000; 0x0020; 0x7803; 0x1000; 0xc00d

         0x7dc1; 0x001a; 0xa861; 0x7c01; 0x2000; 0x2161; 0x2000; 0x8463

         0x806d; 0x7dc1; 0x000d; 0x9031; 0x7c10; 0x0018; 0x7dc1; 0x001a

         0x9037; 0x61c1; 0x7dc1; 0x001a; 0x0000; 0x0000; 0x0000; 0x0000]

    Finally kick it off with cycle () and step through 50 cycles in the debugger. Indeed, as the comment in the source in the spec says, "X should now be 0x40 if everything went right."

    Not a very thorough test, but at least this much works 🙂

  3. joe says:

    hmm – this is what I get when I try to run it:

     cycle();;

     ^^^^^^^

    stdin(186,1): error FS0030: Value restriction. The value 'it' has been inferred

    to have generic type

       val it : '_a

    Either define 'it' as a simple data term, make it a function with explicit argum

    ents or, if you do not intend for it to be generic, add a type annotation.

  4. TechNeilogy says:

    Someone should use quotations to build a complier for a subset of F#.

  5. AshleyF says:

    @joe If you're running at the interactive try ignoring the return value as in "cycle () |> ignore"

    That will run, though it will never return! 🙂 The sample code from the spec purposely goes into an infinite loop (labled "crash" even!) at the end.  You'd have to paste the code into a regular project and step through under a debugger if you want to see what's going on…

    This is just the beginning of course. Notch will define I/O and it will become more meaningful. In the eventual game, you'll be able to talk to sensors and actuators on the ship and will have networked communication with other CPUs and ships. In the mean time, I wanted the VM so I can prepare a Forth to run on it 🙂

  6. AshleyF says:

    @TechNeilogy Indeed, that would be awesome! Walk an F# quotation and translate to machine code for the DCPU. That would just be insane and crazy-cool!

  7. joe says:

    @Ashley – excellent, that solved it for me. Thank you. I've done rudimentary f# but this will certainly give me something to study. Well done

  8. Caleb says:

    Are you going to put this up on GitHub or something? https://github.com/dcpu16 has a collection of implementations in various languages.

  9. Pedro says:

    Nice one, the cutest I've seen so far. Most implementations have been pretty atrocious to be honest.

  10. This is great! Thanks for the implementation.

    Do you mind if I take it as starting point to a possible DCPU-16 GUI simulator?

  11. AshleyF says:

    @Caleb sure, I'll put it on github after a bit – especially once there's more to it (I/O, etc. and want to do a Forth on it 🙂

  12. AshleyF says:

    @Moondevil certainly, feel free to take it and do whatever with it 🙂

  13. AshleyF says:

    Just fixed a bug in which decoding the next instruction to skip it in an IF* instruction was affecting sp. Thanks much to MarkSweep in the HN thread (news.ycombinator.com/item) for pointing it out!

  14. Thanks, but it seems someone already implemented my IDE idea,

    badsector.github.com/…/index.html.

    It is actually quite good. Not sure if I'll still invest the time now.

  15. AshleyF says:

    @Moondevil, it's amazing how quickly a community around this sprung up and has implemented so much so quickly! There's several others out there doing Forth (which is what I want to do) as well, an LLVM backend, etc. It's just insane!

    That's IDE looks pretty good. I wouldn't be discouraged from doing your own though – always fun! Or even just join the existing project and add your unique bit to it. … I may do that with the Forth if someone else is far enough along by next weekend… 🙂