Let’s consider an example of a language with a simple product structure derived
from the context of role-playing games, namely the language of dice rolls.
In most games that make more than a passing use of dice (i.e., where different kinds
and numbers of dice are used), dice rolls are indicated with a syntax like
“2D6” or perhaps “3d6”,
where a pair of numerals (representing natural numbers, i.e., non-negative integers)
is provided, usually with a bit of punctuation between to indicate the particular
interpretation as dice (here the letter “D”).
In games, the informal semantics of a dice roll specification is that one should
pick up a certain number (the first numeral) of dice with a certain number of sides
(the second numeral) and roll them together, adding up the pips on all the dice
to get a total. Many modern games use dice with 4, 6, 8, 12 or 20 sides, since these
correspond to the so-called
Platonic solids,
i.e., convex regular polyhedra (tetrahedron, cube, octahedron, dodecahedron and
icosahedron). By combining different numbers of dice (usually, but not always, with the
same number of sides) a variety of different “profiles” of results can
be obtained, allowing game designers the ability to tailor the specification to a desired
distribution of possible outcomes. In many role-playing games, certain dice roll
combinations have gained an almost iconic status, for example the
“3d6” often used to determine the defining physical and other
play characteristics of new characters in the game.
But can we construe the semantics of the “language” of dice rolls more formally?
We could try to capture randomness somehow, but there is a kind of non-determinism at play here,
one which begs us to find a more holistic story: just as the meaning of a function is more
than just the result of its call on a specific, individual value. When we roll those dice, we may
get one of several outcomes (albeit still a discrete set of “crisp” alternatives). Furthermore,
we also make a little “semantic abstraction”, in that we don't normally care about which die came up
with which value, but rather only about their collective sum. So, for example, a roll of "3d6"
will give us some (natural) number result between 3 and 18 inclusive; but it will also do
so with varying probabilities. We can capture the meaning “as a whole” by considering the result
to be a function ... and perhaps a little more. We can think of the results as a discrete
probability distribution, or DPD.
Specifically, we can capture all the relevant information as a combination of the range of possible totals and a function from numbers within that range to a number result (the latter, in essence, the number of distinct possible combinations which would produce that argument number as a result of the throw). This suggests that we define a new datatype with a pair of components, one a natural number range and the other a function from numbers (well, numbers in that range) to number results, representing the combinations which will get us a particular number in a throw of the dice.
Now, we can't (easily, as beginners) put the restriction about the range of the results into a constraint about the domain of the function, but this is one reason for working with the range as part of the pair: we can at least dynamically, if not statically (as a part of the type) compute things of interest having to do with the range, for example, its size. Let’s agree that the function itself should return a 0 result for values outside the intended domain of the function; in fact, we can't yet easily restrict to just natural number arguments, so let's agree to return a 0 result for negative number inputs as well.
Another very useful thing is to be able to print out the DPD in a compelling, stylized fashion, say as a histogram, like this:
3 *
4 ***
5 ******
6 **********
7 ***************
8 *********************
9 *************************
10 ***************************
11 ***************************
12 *************************
13 *********************
14 ***************
15 **********
16 ******
17 ***
18 *
In Haskell, we can make even have the system print such histograms as the “shown” results
of a DPD value given as the result of computation: we just make the DPD type an instance of the
Show class and provide a definition of a show (note: little “s”) function
which turns any DPD into a String for display (the display above uses tabs and newlines in particular
as pieces of the String result to this effect).
instance Show DPD where
show = ...
We will probably (heh) also want to compute various things from a DPD, not the least of
which might be a more standard probability (value between 0 and 1) for a result of a given magnitude.
In fact, Haskell supports an exact rational number type (if we import the Ratio
module at the top of our file) which we could use to express the sorts of exact rational
probabilities we expect here (no “1-over-pi“ for us!). You can write rational numbers
in Haskell (with the module loaded) in the form "n % m", where the percent sign was chosen
(as a bit of culture-contextual sub-symbolic orthographic goodness) because of its similarity
to the usual “slash” of fractions and computer-language division operators.
In fact, it's easy enough to generalize the idea of a (rational) probability away from the specifics
of a particular number result to a predicate on numbers, so that we'll be able to inquire of
a DPD:
“What is the chance that I will get a result in the range 1-10?” or
“What is the chance that I will roll an even number?” or
“What is the chance I will get a number less than 5?”
Each of these questions corresponds to a predicate, i.e., a function from numbers
(say, Integers)
to boolean results. Question: how do we determine how many possible roll results have the
property and how many don't? How can we then determine the rational number probability of a roll
meeting a given predicate?
Finally, you should also define an addition function on dice rolls (really: semantically
on DPDs) so that you can merge together rolls of dice of different sizes, such as
2d6 `plus` 3d4. These tools, in combination, would allow a user (say a game designer)
to explore the probability distributions associated with various combinations of dice of
different sizes, interactively viewing the distributions themselves or testing various predicates
to fit various game design goals.
In summary, you should write:
A(n algebraic) datatype for DPDs (“discrete probability distributions”) built from pairs of intervals and functions. Intervals in turn should be pairs of numbers representing a range of possible values: you can declare a data type for these as well, if you wish, so that you can distinguish a range from some other pair of integers being used for a different purpose (e.g., ratios, complex numbers, etc.).
A function which takes two integer values (a syntactic “dice roll”) and converts
them into a DPD (say as roll :: Int -> Int -> DPD).
For example, you should have:
DPD> roll 3 4
3 *
4 ***
5 ******
6 **********
7 ************
8 ************
9 **********
10 ******
11 ***
12 *
DPD> roll 7 2
7 *
8 *******
9 *********************
10 ***********************************
11 ***********************************
12 *********************
13 *******
14 *
A function which takes a predicate on integers and a DPD and computes the (discrete)
probability of getting a result matching that predicate from a roll, perhaps
sat :: (Int -> Bool) -> DPD -> Ratio Int (here "sat"
is intended to abbreviate “satisfies”).
For example:
DPD> sat even (roll 3 6)
1 % 2
DPD> sat (<10) (roll 2 4 `plus` roll 2 6)
29 % 144
A function which adds two discrete probability distributions together, so that dice rolls
can be combined (perhaps plus :: DPD -> DPD -> DPD).
For example, here’s a roll of two 4-sided dice and two 6-sided dice:
DPD> roll 2 4 `plus` roll 2 6
4 *
5 ****
6 **********
7 ********************
8 *********************************
9 ************************************************
10 **************************************************************
11 ************************************************************************
12 ****************************************************************************
13 ************************************************************************
14 **************************************************************
15 ************************************************
16 *********************************
17 ********************
18 **********
19 ****
20 *
A function and Show instance which converts a DPD into a histogram string
for output, as shown above.
(Basically, all the examples here that show a DPD as a histogram in
response to a Haskell calculation of type DPD demonstrate what
this should look like: in particular, if you call a function that results
in a DPD value, it should just print out like a histogram
(see for example the result of the plus of two rolls
immediately above).