Zork vs. Haskell, part 2.

From here on out, a code link will be provided at the top of each segment. These repositories contain a bit more than Eric’s because we’re using more heavyweight tooling, but everything outside of src/ can safely be ignored. Since we’re not changing any defaults, we’ll still need a Main.hs which doesn’t match any of Eric’s files; it will just import and re-export the main function from Flathead.hs.

Since we’re breaking the code apart into modules now, let’s also briefly touch on how we’re running it. The “stack runhaskell” command launches an interpreter, and if it needs to search for other modules, it does so relative to the directory it’s run from:

D:\flathask>stack runhaskell src/Flathead.hs
11
11

D:\flathask>stack runhaskell src/Main.hs
src\main.hs:3:8:
    Could not find module `Flathead'
    Use -v to see a list of the files searched for.

D:\flathask>cd src
D:\flathask\src>stack runhaskell Main.hs
11
11

This isn’t too inconvenient as long as you’re aware of it, but as an alternative, the project can be built to and run from a project-specific sandbox. This works from anywhere within the source tree:

D:\flathask>stack build
<a bunch of stuff happens>
Installing executable(s) in D:\flathask\.stack-work\install\8851aa27\bin

D:\flathask>stack exec flathask
11
11

Now, back to the…

Forest path

(code)

Other than breaking up the code modules, this episode’s main focus is the use of wrapper types. Conceptually, everything works exactly the same in Haskell; and the only new syntactic difference is in the declaration:

newtype Bit_number = Bit_number Int
newtype Bit_size = Bit_size Int

newtype behaves like OCaml’s type. Haskell does have a type keyword, but it creates a simple type alias which can be used interchangeably with the original. This is handy for giving short names to compound types, but doesn’t bring any extra safety. There’s one other subtle difference here that should be underscored: in Haskell, the names of types and type constructors must begin with a capital letter. However, they live in different namespaces, so we can use the exact same name for both; we did that here, which looks redundant but won’t always be the case.

That’s it for this episode’s main content, but do I have a stylistic comment. The big repetitive blocks for bit# and size# in the Utility module are unpleasant, and not just due to redundancy: they don’t provide any safety against, for example, directly invoking fetch_bits with Bit_number 97, which is exactly the sort of bug we don’t want to have to track down later, and could exploit the type system to avoid — with less repetitive code as a bonus! Eric says we’ll work with enumerations later, so perhaps he plans to revisit this then.


Oof, I’m falling behind but the next episode promises to be something of a beast. We’re getting into territory where the differences between OCaml and Haskell aren’t just superficial syntax: OCaml’s module system vs. Haskell’s parametric types and typeclasses, different behavior from the standard Map implementation, etc. I’ll catch up as soon as I can!

Zork vs. Haskell, part 1.

On a much more exciting blog, Fabulous Adventures in Coding, Eric Lippert is running a series in which he intends to write a Z-Engine (Infocom text adventure) interpreter in a purely-functional subset of OCaml. He’s normally a C# guy, what with having designed much of that language; and though he’s a big proponent of functional techniques, he says he’s never written a significant program that’s functional end-to-end.

Eric has reasons for picking OCaml. He’s hinted that some will be revealed later in the series; an obvious one is that it’s the most similar language to F#, which runs on the CLR and can interact directly with C#, but I’m sure there are more. Regardless, I was not the only one to post a comment about trying it in Haskell. Well… talk is cheap, let’s do this!

I’m going to attempt to mirror Eric’s structure in terms of what steps are taken and in which order. Rather than duplicate all his commentary and explanation, I’ll assume you’ve already read it and only remark on Haskell’s differences. I probably won’t post as frequently, but I’ll try to keep up at least at the weekly level; when my posts cover several of Eric’s, I’ll split them into sections matching his Zork-room episode titles. Like so:

West of house

Happily, in the past year Haskell’s ecosystem has advanced by leaps and bounds. My commandline examples will be for Windows (to match Eric’s) but other than the prompt and pathnames everything should work on other platforms without modification, including this link to the installer for stack.

http://docs.haskellstack.org/en/stable/README.html#how-to-install

stack is a recent Haskell tool which… well, let’s just call it sufficiently advanced technology and move on. Windows users will find a warning about work-arounds and a link a page filled with opaque references to things a new user probably hasn’t heard of; fret not, for our purposes none of that is necessary.

If you want to be safe about it anyway, for a fresh install there’s only one important thing to do: create a directory in the root of a drive for stack to use as a data store (mine is D:\.stack), and set the environment variable STACK_ROOT to that path. The reason for this is that Windows has limitations on the length of a pathname which other OSes don’t share; hitting that limit while installing Haskell modules is not unheard of. Having stack‘s working directory structure start at a drive’s root rather than buried in a user’s AppData directory gives a lot more characters to work with; it’s technically still possible to hit the limit, but in practice this solves the problem for all known modules.

After installing stack, it’s convenient to have it immediately download a default compiler version, since we won’t be customizing that. This would happen automatically the first time you try to run something, but to avoid any surprises when following the examples below, let’s do it up front.

D:\stack setup

Once that’s done, run the following (changing directories first if you want) to create a new project using the “simple” template:

D:\>stack new flathask simple

It may spit out a fairly big message complaining about missing parameters (author’s name and email, etc.) but that’s safe to ignore here, since we don’t plan on uploading this to a package repository. The final lines should read:

Writing configuration to file: flathask\stack.yaml
All done.

You should now have a flathask directory containing a few files and a src subdirectory, which in turn contains Main.hs. Verify success with the following:

D:\>cd flathask\src

D:\flathask\src>stack runhaskell Main.hs
hello world

Assuming I haven’t given terrible instructions, everything should be ready to go! Aim your favorite text editor at Main.hs.

North of house

Eric’s first line of code simply defines a constant. Haskell’s compiler doesn’t care what order your definitions are given in, so let’s just add it to the end of Main.hs:

word = 0xBEEF

No “let” is needed at the top level in Haskell, so it’s even simpler than the OCaml version. Of course, as in any pure functional language, it doesn’t have to be declared constant, because by default everything is constant.

Next step, make the program do something. Here, we need to take a quick detour into Haskell’s module system: unlike OCaml, a module is not available (even by a fully qualified name) unless it’s explicitly imported at the top of the file. This can occasionally lead to some pretty crazy import lists, but it also helps keep namespaces clean and simple. (Incidentally, you may have noticed “module Main where” at the top of Main.hs: each Haskell source file is one module, and vice versa.)

Funnily enough, the situation is reversed from OCaml: console output is in the Prelude (i.e. available with no import), but bitwise operations are not. Unlike definitions, imports are location-sensitive; insert this after the module declaration, but before any code:

import Data.Bits

Okay… because this project was initialized from a template, there’s a pre-supplied main function, which is the program entry point just like OCaml’s ().

main :: IO ()
main = do
 putStrLn "hello world"

The first line is a type declaration, which is considered good style at the top level, but it’s optional. Since Eric’s not using them, let’s just delete it. (Especially since the alternative is a long explanation of what “IO ()“ really means.)

The second line… hmm, I don’t really want to fully explain “do” right now either. For now just think of it as what would be an opening curly brace in a C-style language, with the closing brace supplied implicitly.

Finally, the meat of it: putStrLn doesn’t use the same formatting conventions as printf, but it does the same job. Now, we just need to make it stop greeting the globe, and get it to show us some of those sexy bitshifts. Eric’s first attempt translates like so:

main = do
  putStrLn (show ((shiftR word 12) .&. (complement (shiftL (-1) 4))))

Some of those parentheses are unnecessary (and some more could be gotten rid of with operators I don’t want to explain yet) but this format should highlight the equivalencies with Eric’s OCaml. A few things worth noting:

  • Indentation is significant, but not rigid: Haskell blocks must be consistently aligned, and a child block must be more indented than its parent. Here, it doesn’t matter how many spaces you put in front of line 2 as long as it’s more than zero.
  • putStrLn takes a string, adds a newline, and displays it. That’s it. No other formatting, no tokens or optional arguments, not even implicit casting; it does one job, and you deal with the rest before calling it. Here, we want to print an integer, so we need to turn it into a string first; elsewhere you might find .ToString(), here it’s show. (There’s also a print function which does the implicit conversion… okay, we’ll use that next time. But keep in mind that putStrLn is more generic, and thus more flexible.)
  • The number (-1) requires those parentheses. It’s a long story and nobody’s super happy with it, but in a nutshell the desired behavior of syntax elsewhere necessitates an explicit way to differentiate “negate” from “subtract” and that’s what they picked.

Following along, the next step is to split that bit-masking operation into a helper function, and use that in main. Only one new thing here: apparently OCaml lets you define infix functions with the same naming rules as any other binding. In Haskell the name of an infix function (operator) must be composed entirely of symbols, and a regularly-named function is always prefix. However, you can invert that behavior by placing an operator alone in parentheses to make it prefix, or by wrapping a named function in `backquotes` to make it infix. I didn’t do this last time, but let’s match this function as closely as possible to the structure of Eric’s:

fetch_bits high length word =
  let mask = complement ((-1) `shiftL` length) in
  (word `shiftR` (high - length + 1)) .&. mask

And here’s the amended main, using print as promised:

main = do
  putStrLn (show ((shiftR word 12) .&. (complement (shiftL (-1) 4))))
  print (fetch_bits 15 4 word)

And… whoops, it fails to compile with a quartet of errors about “No instance…” Reading through a few lines reveals that in fact, it’s not that there’s no instance; it’s that there are too many and the compiler can’t figure out which one pick. (Aside: what “instance” means here is not the same as what it means in an object-oriented language. Adding to the confusion, it is an instance of a class. But what class means… yeah, anyway.)

What’s going on here is, Haskell has polymorphism baked in so deep that even literals can have multiple types, and once in a while the type checker can’t nail down what’s intended. The culprit is our word constant: we bind it to 0xBEEF, and there are a few different types that literal could represent which also satisfy all of the known constraints of our functions. Normally this would be avoided with better function constraints, but I’m going to stick to Eric’s “no top-level type signatures” rule by putting an in-line signature on the literal itself:

word = 0xBEEF :: Int

Now that everything’s kosher:

D:\flathask\src>stack runhaskell Main.hs
11
11

Eric’s Github repository doesn’t start until the following episode, and mine will match. But to ensure we’re all on the same page, here’s my Main.hs so far.

module Main where

import Data.Bits

main = do
  putStrLn (show ((shiftR word 12) .&. (complement (shiftL (-1) 4))))
  print (fetch_bits 15 4 word)

word = 0xBEEF :: Int

fetch_bits high length word =
  let mask = complement ((-1) `shiftL` length) in
  (word `shiftR` (high - length + 1)) .&. mask

The singing, happy drunk.

Welcome back my friends, to the show that never ends; we’re so glad you could attend. Come inside! Come inside!

Anyone still listening? Well really, that’s a stupid question. Caring about whether I’m heard has been one of my constant blockades. I really ought to express myself regardless of any audience.

Tonight saw me going out with a bang: last karaoke night on the east coast, followed by a few rounds of shots with a DJ (and friends) who I met at a local Friday’s. The bang itself belongs to my marriage, which is over except the paperwork. But that’s a different story.

Right before your eyes, we pull laughter from the skies; and he laughs until he cries, then he dies, then he dies.

Oh my, I appear to be forcing an awkward juxtaposition. These italic interludes, particularly this latest, are at best tangential to my mood and circumstance. Much as one might expect my emotions to be flowing down that path, my current situation is more long-postponed inevitability than sudden upset. I was ready in advance.

The lines are from a song a few seasoned readers might recognize. On that same note, the title of this episode is also rather dated. I really can’t say which of the two will have a higher rate of recognition among those few, those lucky few, who peruse this disjointed (and long-silent) journal of mine.

But hey, let’s go digging. “The singing, happy drunk” is a character who has appeared in numerous MUDs and text-based roguelikes.

This creature moves somewhat erratically.
He can pick up objects, bash down doors, and open doors.
He is ever vigilant for intruders, which he may notice from 100 feet.
He will carry a object or treasure. He can beg.

Though he’s never been more than casual data to me, I’ve always felt a sort of kinship. Tonight it came to the fore: walking home post-revelry, I found myself singing to the stars themselves, and loving every second — right up until I hit the residential zone, and quit for fear of offending anyone.

Soon the gypsy queen, in a glaze of Vaseline, will perform her guillotine. What a scene! What a scene!

Once upon a time, I wouldn’t have hesitated. The very concept of “making a scene” is something I had to learn via harsh enforcement; and though it’s become near-instinct for me to avoid it, I have frequent doubts whether that was a good habit to pick up.

Certainly it’s more convenient. Without question, it results in fewer negative interactions with folk who don’t want to hear me serenading the sky at 2am.

But is that really worth the sacrifice? The song is lost now, given up for the momentary comfort of those who aren’t singing.

Why aren’t they?

Vague hand-waving.

My wife has chastised me for letting two more weeks slip by; and, though not completely silent, this will be another by my own standards of content.

It’s not that nothing interesting is happening. Several things are, in fact; all positive, too. It’s just that they’re also all in tenuous states where they could still fall through, and then I’d be sore embarrassed for having announced them.

Give it another week or two. Meanwhile, blow the time you would have spent perusing my voluminous diatribe on a cute little puzzle game instead.

Discombobulation persists.

Missed the last two weeks entirely, whoosh, zoom. I feel upside-down and underwater, but that doesn’t make for lively internet rambling. There have been two big new things in the interim which feel worth writing about: I’m learning Haskell, and doing contract work for a new website (Slant.co) involving research and writing.

Haskell is everything I loved in Smalltalk, plus everything that terrified me in Lisp, plus all the joy of trying to pretend Windows is Unix. That last item isn’t an endorsement, but the first two are.

Slant is like if Amazon’s “people also bought…” were merged with their review system, and the whole thing hybridized with Stack Exchange (or I guess Ask.com or something, if you swing that way), but instead of coming out some kind of derivative clusterfuck, it’s elegant and useful and has features you didn’t know you had missed.

Righto, conscience slaked for another quarter-moon. Arrivaderci.

Because math is fun, that’s why.

Find a 9 letter string of characters that contains only letters from

acdegilmnoprstuw

such that the hash(the_string) is

910897038977002

if hash is defined by the following pseudo-code:

Int64 hash (String s) {
    Int64 h = 7
    String letters = "acdegilmnoprstuw"
    for(Int32 i = 0; i < s.length; i++) {
        h = (h * 37 + letters.indexOf(s[i]))
    }
    return h
}

Random browsing brought me to a job listing with this puzzle. The instructions were to send an email with the solution as the topic, and attach the code you used to solve it. Sadly, I couldn’t follow those instructions: I didn’t write any code. I solved it with Calc and Notepad, because writing and compiling a program would have taken longer.

I’m honestly curious about the purpose of this test. Being a test question in the first place means that there must be a simple algorithmic solution, and there’s only one place where an algorithm can be applied: finding the solution process was trivial, and finding the actual answer by hand took only a couple of minutes. Granted, you need to know basic C syntax; but how many people, who might apply for the position in the first place, fail this test? It’s almost scary to think about! Are there applicants who just generate answers sequentially or randomly until one meets the criteria?

Admittedly I did something like that once, plotting a Sierpinski triangle by shotgunning random screen points (in Logo!) because I just didn’t think of nesting two FOR loops; but in my defense I was completely self-taught and also 12.

Louis C.K.: The Miracle of Flight

Long ago I came to the conclusion that people have a comfortable level of discomfort, which they maintain subconsciously. This sounds oxymoronic, but consider how commonly you’ll hear a sentiment along the lines of: “things are going too well, what disaster is headed this way?” Objectivity really can’t conquer human nature here; no matter how much we know better, there’s a sense that fortune must level out. (One version of this is a weekly occurrence in my household: “The cat is extremely well-behaved today, where did she pee?”)

Without conscious effort to the contrary, this sense that there must always be a certain level of badness in one’s life causes an odd effect: nearly everyone, regardless of life station or actual hardship, filters their subjective experience in a way that produces their personal sweet-spot of discomfort. The destitute play up positives to be happy with what they have; the affluent rage at the loss of things 90% of the world has never seen. While it’s easy to frame one as noble and the other as arrogant, they’re really the same thing, and equally delusional at either extreme.

Framing things as arrogant is fun, though. Ladies and gentlemen, Mr. Louis Székely!