2012-10-16

Scheming

MIT 6.001 is a classic, now-retired computer science class: Structure and Interpretation of Computer Programs (also the name of the textbook). It leveraged Scheme for much of the class.

I’m not remotely qualified to compare Scheme, Lisp and Erlang, except to say they’re all functional programming languages, and that Scheme is visually much closer to Lisp than Erlang is, and that despite some feeble efforts I’ve never gotten comfortable with true list-based languages like Scheme or Lisp, where everything, even function definitions, are (as I understand it) pure lists. Erlang fits my sysadmin background much better.

Regardless, assignments written to leverage Scheme should be fairly straightforward to solve with Erlang, and MITs The Game of Twenty-one is one such assignment.

tl;dr

The Game of Twenty-one (or 21” as I’ll refer to it) is a simplified version of blackjack. Cards are represented as random numbers between 1 and 10 (inclusive), and none of the complications of betting are involved. The player (or the player’s strategy function) tries to beat the house (or the house’s strategy function).

edoc and types

I decided that now would be a good time to tackle edoc, Erlang’s answer to Javadoc; while I was at it, I threw in type specifications and Dialyzer for good measure.

Show me the code

You can find the code at GitHub. Some snippets…

edoc + a blackjack strategy function

The basic interface for this module is to invoke either start/2 or test_strategy/3 with anonymous strategy functions for the player and the house; test_strategy/3 takes a 3rd argument representing the number of times the simulation should be run.

The strategy functions take a tally of the player’s (or house’s) current hand and a number representing the card that the player (or house) can see face up in front of the opponent.

Louis, one of the figments of this problem set’s imagination, wants to try a complex strategy involving both the tally and the face up card. You can see the @doc comment that will be used by edoc, the -spec specification that Dialyzer uses to discern whether the function adheres to its contract, and the logic itself.

The logic is convoluted, but easy to glean from the code.

%% @doc Louis' 21 strategy: draw if the current hand is < 12, hold if
%% > 16, and otherwise decide what to do based on the house's up card.
-spec louis(hand(), card()) -> action().
louis(Tally, _OpponentUp) when Tally < 12 ->
    draw;
louis(Tally, _OpponentUp) when Tally > 16 ->
    done;
louis(Tally, OpponentUp) when Tally =:= 12, OpponentUp < 4 ->
    draw;
louis(Tally, _OpponentUp) when Tally =:= 12 ->
    done;
louis(Tally, OpponentUp) when Tally =:= 16, OpponentUp =:= 10 ->
    done;
louis(Tally, _OpponentUp) when Tally =:= 16 ->
    draw;
louis(_Tally, OpponentUp) when OpponentUp > 6 ->
    draw;
louis(_, _) ->
    done.

Type declarations

Even without reading about Dialyzer and types, this should be fairly easy to interpret. The one notable oddity: types are represented with (), making them look like functions. Atoms are typically quoted (I forgot to quote ok) so that it’s clear that the developer wanted an atom (vs. accidentally leaving the parentheses off a type).

-type card() :: non_neg_integer().
-type action() :: 'draw' | 'done' | 'quit' | 'retry'.
-type hand() :: non_neg_integer().
-type actionresult() :: { ok, card() } | action().
-type endresult() :: 'user_quit' | 'user_busted' | 'house_busted' | 'house_won' | 'user_won'.

%% A strategy function takes a hand, a face up card for the opponent,
%% and decides what to do by returning an action.
-type strategyfun() :: fun((hand(), card()) -> action()).

So, an actionresult type is defined as one of two possible values: a tuple with ok and a card value, or an action value.

The action type is defined as one of 4 atoms: draw, done, quit, retry.

My specification isn’t quite as precise as it could be, because draw is not a valid atom for actionresult; any time a strategy function returns draw, that value is converted to the {ok, Card} tuple.

The distinction between an action type (the return value from a strategy function) and an actionresult type (the strategy action converted to a random card if draw was the result, otherwise just the action itself for controlling the flow of control) wasn’t obvious as I was writing the code, and would have been nearly impossible (for me) to define up front. It was only apparent in retrospect.

It’s also the type of distinction that I likely wouldn’t make very clear if I were writing Perl, and if I were creating OO types in Java I’d probably waste significant time trying to figure out how to represent the concepts.

Conclusions

edoc

I found edoc surprisingly difficult to apply; I felt the documentation was a bit too reference manual instead of user guide. But I’m generally a slow learner, so most programmers likely wouldn’t have a problem with it.

An example of the type of (admittedly self-imposed) problem I had with the docs: I wanted to include commentary about the types I defined, but I couldn’t figure out how to do it. I don’t think it’s possible, but nowhere does the documentation explicitly say so, unless I’m simply dense.

(It doesn’t help that I often skim instead of read.)

Dialyzer and types

In contrast, I fell in love with Erlang’s type system. It may have helped that Learn You Some Erlang For Great Good documented Dialyzer and not edoc; Fred’s documentation is superb.

Setting aside documentation, however, I think Erlang’s approach to type is quite attractive. It may be the first dynamic strongly-typed language I’ve enjoyed using (Python leaves me cold).

One key advantage to Erlang’s approach is that the developer can be fluid and lazy with types up front; get the code written without worrying much about long-term maintenance needs1. Later, once the initial brain dump is complete and you start slowing down, then you can start formalizing the implicit type specifications that have been making themselves apparent as you write the code2.

My sequence (more or less) for this project, which I’m guessing will be similar in the future:

  1. Start developing code.
  2. Once it’s clear what I need for passing state between functions, create a record type to make that process easier and replace all of the individual state values with aggregate records.
  3. Continue code development without types until one of two points is reached:
    • The code is becoming too long and/or hairy to easily follow.
    • I’m ready to start writing unit tests.
  4. Overlay type specifications. This will likely result in some rewriting as commonalities (or logic errors) are revealed; it may also lead to renaming function and variable names to be more consistent with the underlying data.
  5. Run dialyzer.
  6. Write unit tests.
    • Admittedly, I didn’t write unit tests for this one. It should be possible to create a non-random random value that would always give the same results, thus allowing unit tests to work, but I haven’t looked into it.

  1. One of my complaints with traditional OO programming is that I spend way too much time creating, and then rewriting, and then throwing away, types. Erlang makes it possible to just solve problems and worry about type later.

  2. See the above footnote. Note, too, that creating a type of a tuple incorporating an atom, an integer, and a string is one optional line of Erlang, and how many lines of Java?

erlang
Previous post
Noughts and Crosses When at chess you can't succeed, fall back to something simpler
Next post
FizzBuzz Yes, I can code