You are standing in an open field west of a white house, with a boarded front door. You could circle the house to the north or south. There is a small mailbox here.
> open the mailbox
Opening the small mailbox reveals a leaflet.
> read the leaflet
[Taken]
“WELCOME TO ZORK, a game of adventure, danger, and low cunning. No computer should be without one!”
Thus begins Zork, perhaps the most famous of the classic Infocom text adventures of the 1980s. I grew up playing all the Infocom games. The puzzles, the sense of humour, the cleverness in a computer program that appears to understand English commands, all enchanted me in my youth, and still do.
As a child who could write programs that animated rocket ships flying around the screen, I was mystified as to how anyone could write a program that could understand English. What I only came to appreciate much later in life was that this was not the major technical achievement of the geniuses at Infocom. The real deal was that they solved in a stroke two major problems in the video game industry of the late 1970s and early 1980s:
- How do we write games once that can run on multiple platforms?
- How can we write games with code larger than the limited memory size of 1980’s era 8 bit computers? 64KB of memory is not much to work with.
The solution they came up with anticipated the Java VM and the CLR by decades:
- Solve the portability problem by compiling the games to a virtual machine bytecode language, not to any particular architecture. Then write an interpreter for every target machine. Now you can write n games and m interpreters at a cost of n + m instead of writing n games m times each for a cost of n * m.
- Solve the memory problem by implementing a virtual memory system in the virtual machine. Unused code or resources can stay on disk and be paged in when needed; code that hasn’t been used for a while can be abandoned and read back in later.
Genius! And this is what they did. The VM is now known as the Z-machine, Z for Zork, of course. This solution is ideal for text adventures which have huge-for-the-time code and text resources but do not have down-to-the-tenth-of-a-second timing requirements that most video games have.
Long after that, more super smart people reverse-engineered the six different versions of the Z-machine that Infocom created over the years and published a specification. So now anyone can write an interpreter for the Z-machine and run the old Infocom games.
Anyone, including me!
I have been meaning for some time now to implement a Z-machine, just for fun. My goal is certainly not to compete with any existing Z-machine implementations; there are plenty that do a better job than mine will at providing a pleasant gaming environment with beautiful text rendering, that support all of the later Infocom games with their graphics and sound effects and whatnot. Rather, my goals for this project are:
- Learn about the Z-machine
- Have fun writing some code and blogging about it
But there’s more. I’ve talked for years about functional programming in this blog, and large parts of Roslyn were written in a manner inspired by functional programming, but I have never written a largish program entirely in functional style. So:
Principle #1: The entire program will, as much as possible, be written in a purely functional, side-effect-free style…
Here’s the bit that I really decided to grit my teeth over:
…in OCaml
Now I know what you are thinking. Why on earth would the C# guy start writing code in OCaml, of all possible languages?! If someone like me, with long experience in the .NET stack wants to learn a functional language in the ML family then surely the natural choice is F#, with its beautiful debugger support in Visual Studio and interoperability with C#.
I have my reasons! I will go into them in a future post. But for now, just accept the fact that this blog is going to be about OCaml for a while. I’m hoping that it will be an interesting learning experience for everyone. We’ll get back to C# eventually.
As we go I’ll try to deduce some highfalutin moral principles for working in functional languages, or any languages for that matter.
And besides, the title of this blog will be more accurate than usual: we’ll literally be coding up some fabulous adventures. Join me!
If you want to follow along, you’ll need an installation of OCaml. Windows users can download OCaml 4.02 from OCamlPro at
https://www.ocamlpro.com/pub/ocpwin/ocpwin-builds/ocpwin64/20160113/
I used the Windows installer “ocpwin64-20160113-4.02.1+ocp1-full-mingw64.exe”
An alternate site, which I have not yet tried, is
http://protz.github.io/ocaml-installer/
which links to installer
http://gallium.inria.fr/~protzenk/caml-installer/ocaml-4.02.3-x86_64-mingw64-installer4-opam.exe
If you’re using a unix-based operating system, or Cygwin, or whatever, I leave it to you to figure out how to install OCaml 4.02.
And hey, for all I know, this could all be legal F#. It couldn’t hurt to try, though I have not taken the time to do so myself.
OCaml has both an interactive “REPL” mode and a traditional compiler mode. I’ll be using the latter, but I encourage you to try out the REPL, look at some online tutorials, and see how you like it. We’ll start looking at some code next time.
Next time on FAIC: How do you twiddle a bit in OCaml?
Fabulous adventures in coding 
> I have my reasons! I will go into them in a future post.
I’m curious about your reasons, and looking forward to your next posts.
Isn’t the F# syntax almost identical to the OCaml syntax anyway?
It is, but I have reasons for wanting to use the OCaml tool set and syntax. A nice side benefit of this project is that I will learn a lot about F#, I’m sure. Though really almost everything I do could be done in a much older version of ML still; I’m going to be using a pretty basic core of the language.
Should be a pretty straightforward port to Haskell, too. I might just follow along doing that, I could probably use some OCaml/F# familiarity!
Awesome! Can’t wait to see where this goes.
I wrote my own Z-machine interpreter in C# a few years ago: it’s called ZLR, and it translates Z-code to IL so the CLR can compile it to machine code. At the time, this made complex Inform 7 games noticeably more responsive. These days, I still use it for its debugger and as part of the test suite for ZILF, which is a compiler for the baroque Lisp-like language Infocom used to write Zork in the first place. (Both are open source available on Bitbucket.)
Nice! If I make mistakes along the way in my interpretation of the Z-machine specification please do be sure to point them out.
It does make a strange kind of sense to go with OCaml if the goal is to learn/demonstrate more about functional programming. While F# is designed for the .NET framework which is more familiar to someone who’s worked with C#, it also allows you to drop from functional style to OOP when required.
Generally that’s not a bad thing, but if you are trying to force yourself into a functional style the lack of temptation to break out of it back into OOP is probably helpful
Actually, that’s what the O in OCaml stands for: Object. For more “untainted by OOP” functional programming/style you’d likely head towards Caml or an older ML, one of the Lisp/Scheme family (again trending towards older versions as there are plenty of Lisp and Scheme object systems, but in Lisp/Scheme those are still likely to be bolt-on libraries/DSLs rather than actual “language core”), or something truly fun and mind-breaking like Haskell.
Oh. I’d forgotten that (not an (O)Caml user myself) but I do remember reading it.
I guess that blows my theory out the water, then.
I suppose you still get more of a sense about where F# came from by using OCaml, though.
It doesn’t matter that much to me since I only know the very basic of F# so learning some OCaml doesn’t hurt:). Look forward to seeing some code soon and I will try to follow along.
It is interesting (to me) to point that the “byte code/VM” approach is hardly unique, even before Java/.NET.
Zork certainly is one of the (if not *the*) earliest examples on personal computers. But the technique’s also been used in a variety of other projects, including Microsoft’s Multiplan/Excel spreadsheet programs, from the early 80’s well into the 90’s. The Microsoft “p-code” interpreter supported paging, and a form of code compression called “quoting” (i.e. if the compiler found multiple sections of code that compiled to the same p-code, it just put the compiled result in once, and that section of code was executed from whatever context the duplicate was found). The bulk of the program ran from p-code, but there was a thin native layer to support the platform-dependent API (similar to how Java and .NET wrap the underlying platform APIs now).
Wikipedia says the basic concept has existed since the 60’s: https://en.wikipedia.org/wiki/P-code_machine
And AFAIK, the web version of the Office apps are written in JavaScript, carrying on the tradition. 🙂
Indeed, my first job at Microsoft was working on the Mac implementation of the Visual Basic p-code interpreter, back in 1993. Good times!
The thing that is bugging me the most (maybe because I don’t like OCaml that much):
Why not Haskell?
I HAVE MY REASONS, he said mysteriously.
All will be made clear next week!
Closeness to F# is a good enough reason on its own for the purpose of this blog, I think. Also, if Eric’s really as fresh to functional programming as he implies, strict-by-default may seem less daunting; it’s one less new thing to stuff in your head at once, at least.
I’m not really disappointed; as I commented above, we can just port it as he goes. 🙂
Reminds me of the days spent hacking on a WD9000 Pascal Microengine whose _native_ language was p-code
It’s nice to see that Infocom is still remembered by people. I have fond (but see below) memories of their games. I was so frustrated that I couldn’t open the egg in Zork I, and I was driven to disassemble the interpreter to figure out the Z-Machine architecture. I then wrote a number of programs (under CP/M in that shiny new language “C”) that dumped the vocabulary table, dumped the action routines, figured out the compression algorithm for text, and eventually even wrote a disassembler and later decompiler for all the games (and yes, finally figured out how to wind up with an opened egg).
I assume you know about http://inform-fiction.org/zmachine/index.html, especially the Standards section that has a guide to the Z-Machine architecture. See also http://www.xlisp.org/zil.pdf
Finally, you and Dustin Campbell should team up.
It was Dustin’s offhand comment about implementing Z-machines the last time we had lunch that reminded me that I’d been meaning to do this!
Heh, we came to the same solution at Sifteo, for distributing games to ARM Cortex SoCs: https://blog.adafruit.com/2012/12/05/how-we-built-a-super-nintendo-out-of-a-wireless-keyboard-sifteo-sifteo/
The cubes aren’t on the market anymore, but the virtual machine, “thundercracker,” is open-source: https://github.com/sifteo/thundercracker
Pingback: Zork vs. Haskell, part 1. | Squandered Genius
Pingback: Visual Studio – Developer Top Ten for Feb 8th, 2016 - Dmitry Lyalin
Pingback: Old Teacher Trick: Artificial Constraints Beget Creativity | willmurphyscode
Pingback: Know the Words: State Machine – willmurphyscode
Pingback: Coding Machine – Reviewing Purathrive
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – Golden News
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – Hckr News
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – Outside The Know
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – Latest news
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – protipsss
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – World Best News
Pingback: New top story on Hacker News: A Z-Machine in OCaml (2016) – News about world
Pingback: A Z-Machine in OCaml (2016) – INDIA NEWS
To be fair, the last 80% of the work of implementing a Z-machine is pretty tedious, consisting mostly of troubleshooting edge cases and consulting the source code of other interpreters to clear up ambiguities in the spec.
So … you mean the very things that it would have been helpful to continue working on so that others understood it? If you have to consult other interpreters to understand the spec, that’s pretty odd. The spec is the basis for those interpreters. How would I know whether those other interpreters got it right? The series actually ends at one of the points that the author himself said was very confusing to implement.
I totally get it if interest is lost or whatever but it doesn’t hurt to tell people that they’re embarking on something that was never finished.
“If you have to consult other interpreters to understand the spec, that’s pretty odd. The spec is the basis for those interpreters. How would I know whether those other interpreters got it right?”
Yes, the spec has some problems. The Z-machine was reverse engineered by people who wrote their own interpreters, and the spec wasn’t written until later. In practice, what the most popular interpreters (mainly Frotz) do is what really matters, because all the other tools are tested against them, and if the spec disagrees then the spec is wrong.
Old school games.