[Go to previous, next page]

Numerical examples, really?

Here is a introduction to LFE, or Lisp-Flavored Erlang (lfe).¹

While trying to get up to speed on a new language, I’ve found it useful to try to program Monte-Carlo solutions to probability problems. Now learning programming using numerical computation is not very popular these days, but this is because calculating gcd’s, factorials, and Fibonacci numbers is not very motivating to folks. In contrast, Monte-Carlo simulations gamely manage to hold interest, because the solutions can be full of surprise and even charm, are either impossible or head-hurtingly difficult to find analytically, and of course the little gambler in everyone is eager to know or confirm a result. In one’s burning desire to get to the result, one quickly learns the rudiments of the language: basic arithmetic operations, conditionals, loops, procedures, scoping. For a collection of varied problems suitable for this venture, see 50cpp, idiots, dice.

Everybody doesn’t get a car

As a first example, let us solve the very famous but still twitchily surprising Monty Hall problem (idiots, p. 192). A game-show host shows a player three closed doors, behind one of which is the prize, a car. The player picks a door, whereupon the host opens one of the remaining two doors, with no car behind it. The player is now given the option to stick with his choice or pick the other unopened door. If the car is behind his final chosen door, it is his. The question is: Should he stick with his initial choice, or should he switch?

The analytical solution says he has 2/3 probability of winning if he switches. If you are not convinced, a Monte-Carlo simulation should help: We run the scenario a lot of times, say N times, and calculate the number of times, m, that a switch would win the car. m/N then gives the frequency-based probability that a switch wins.

First, we define a thunk (0-ary procedure) game representing each scenario (or experiment, or game, in this context):

(defun game ()
  (let ((actual-loc-of-car (random:uniform 3))
        (loc-picked-by-player (random:uniform 3)))
    (if (== actual-loc-of-car loc-picked-by-player)
        0
        1)))

This is pretty straightforward Lisp: defun defines a procedure, here named game, with no arguments. let introduces local variables, here: actual-loc-of-car, for the actual location of the car; and loc-picked-by-player, for the location initially chosen by the player. (random:uniform N) returns a random integer uniformly distributed between 1 and N, inclusive: The procedure called is uniform, from the standard module random.

When game is called, it randomly assigns values (from 1 through 3) to actual-loc-of-car and loc-picked-by-player. If these match, clearly the player should not switch. If they don’t, the door not opened by the host certainly does contain the car, and the player should switch. We have game return 1 if a switch is advisable, 0 if not. Why we use numbers rather than booleans should be obvious from the following.

We now define a thunk run that runs game a large number of times, returning the average return value:

(defun run ()
  (let ((num-trials 10000))
    (fletrec ((loop (i acc)
                (if (=< i num-trials)
                    (loop (+ i 1) (+ (game) acc))
                    (/ acc num-trials))))
      (loop 1 0))))

Here fletrec defines a local recursive procedure loop, which takes two arguments, i and acc. loop is called with 1, the (ordinal) number of the first trial; and 0, the accumulated sum so far. The if inside the loop ensures that loop is called (“looped”) exactly num-trials = 10000 times. Each loop call but the last adds to acc; the last call returns the average value.

This is how one does loops or iteration in properly tail-recursive languages such LFE: there is no dedicated loop primitive and no need for it either.

We’ll put the definitions of game and run in a file called montyhall.lfe, and add the following header to it:

(defmodule montyhall
  (export (run 0)))

The name of the module must match the basename of the file containing it. Compile the file as:

% lfec montyhall

where % is your OS prompt. This produces the compiled file montyhall.beam.

Now start LFE:

% lfe
Erlang <version> ...
LFE Shell <version> (abort with ^G)
>

At the LFE prompt (>), call the procedure run:

> (montyhall:run)

(montyhall:run) is how you call the exported procedure run in the module montyhall. The result should be close to 2/3.


¹ Those with a smattering of Scheme or Lisp should find a lot that is familiar. LFE is properly tail-recursive, like Scheme, but keeps the function-name space separate from the other variables, like Common Lisp. Furthermore, variables aren’t really “variable”, although it is possible to get the effect of assignment by using ETS (= Erlang Term Storage), whose usage is very roughly analogous to that of the property lists hanging off of symbols in Common Lisp. Of course, LFE has concurrency-related features that are usually not present in standard Scheme or Lisp.

[Go to previous, next page]