Basic Concepts

Enter ibal at the command line. This will bring you to an IBAL prompt:

IBAL>

At the IBAL prompt, enter "hello world" (including the quotation marks). You should see the following result.

       *       
 [hello world] 
---------------
 [hello world] | 1

What does this mean? IBAL always presents its results in the form of a table. The table contains a column for every variable in the result. The part of the table above the dashed line is called the schema -- it describes the variables and their possible values. The part of the table below the dashed line is the body. It describes a probability distribution over the values of the variables.

The schema consists of two lines. The top line shows the variables in the result. In this case we have a single variable, named * (pronounced ``star''), which is a special variable that always refers to the outcome of the program being computed. In our simple program this is the only variable. The second line of the schema shows, for each variable, the set of values that variable can take. In our case, it shows that * can take only the value hello world.

The body consists of a sequence of rows. Each row specifies an assignment of values to the variables, and the probability of that assignment. In our case there is just a single row, in which * takes on the value hello world. That row has probability 1. Thus, the table says that the program "hello world" has the outcome hello world with probability 1.

Why is this table obtained as the result of typing "hello world" at the IBAL prompt? "hello world" is a very simple example of an expression. The expression is the basic programming unit of IBAL, and all IBAL programs essentially reduce to expressions. Intuitively, an expression defines an experiment that stochastically produces an outcome. When you enter an expression at the IBAL prompt, IBAL evaluates the expression to compute the probability distribution over the outcome, and presents that result in the form of a table. (In this tutorial, I am careful to distinguish between the outcome of the experiment defined by an expression, and the result of IBAL's computation, which is a table showing a probability distribution over the outcome.)

"hello world" is a constant expression, an expression that always produces the same value -- in this case, the symbol hello world. In general, the expression "x" produces the symbol x. There are also the Boolean constants True and False. (Symbolic constants are case-sensitive, but the Boolean constants are not.) Then there are the integer constants such as 0, 1, and -286.

Aside: There is an alternative syntax for producing symbolic constants: 'x produces the symbol x, provided that x consists only of letters, digits or the underscore character (_). A symbol of this form is called an identifier. For example, 'hello_world produces the symbol hello_world. If the same symbol is created with the two different syntaxes, the two values are equal, e.g., "hello_world" and 'hello_world produce the same value.

Our example so far is boring, since it is deterministic. To introduce stochasticity into the language, we use the dist construct. For example, enter

dist [0.2 : 'hello, 0.8 : 'world]

at the IBAL prompt. The resulting table is

       *       
 [world; hello]
---------------
    [world]    | 0.8 
    [hello]    | 0.2

The table tells us that * can take on two values, world and hello, and that it takes value hello with probability 0.2, and world with probability 0.8. The rows in the result are listed in order of decreasing probability. In general, an expression of the form dist [p_1 : e_1, ..., p_n : e_n] where the p_i are probabilities and the e_i are expressions, defines the experiment that chooses one of the e_i with probability proportional to p_i, and then runs e_i. (If the p_i do not add up to 1, they are normalized.) There is a useful shorthand flip p, which is the same as dist [p : true, 1-p : false]. You can also use uniform n, where n is a positive integer, to specify a uniform distribution over the integers 0 through n-1.

Now enter the following at the IBAL prompt:

dist [0.2 : 'hello, 0.3 : 'world, 0.5 : 'world]

The result is the same as before. Even though there are three possible executions of the experiment, there are only two different possible results, and their distribution is the same as before. IBAL computes the distribution over outcomes, not over executions, and where necessary sums the probabilities of different executions that produce the same outcome.

One can compare two values for equality, producing a Boolean result. For example, try

'hello == 'world

(Note the ``equals-equals'' syntax for equality tests.) One can apply the standard Boolean operators ~ (not), & (and) and | (or) with the usual results. One can also use if-then-else constructs to create more complex expressions. E.g.

if flip 0.7 then 'hello else 'world

IBAL provides a rich case construct for branching based on the value of an expression. The general form is

case e of
# pat_1 : e_1
# pat_2 : e_2
...
# pat_n : e_n

where e, and the e_i are expressions, while each of the pat_i is a pattern. A pattern matches a set of values. The simplest kind of pattern is simply a value, which matches itself. Another pattern is _, which matches all values. We will see other kinds of pattern later. (The hash (#) before the first pattern is optional, but makes for better looking code.)

The case expression can be understood as defining the following experiment: First evaluate e, then if the outcome matches pattern pat_1, evaluate e_1; else if the outcome matches pattern pat_2, evaluate e_2; ...; else if the outcome matches pattern pat_n, evaluate e_n. Since _ matches all values, it can be used to indicate the default clause that holds if none of the previous patterns are satisfied. There does not have to be an explicit default clause. However, it is an error to write a case statement in which the outcome of e might match none of the patterns.

Here is an example of a case expression. It is too long to fit on a single line. To break it into multiple lines, end each line before the last with a backslash (\) as follows: (Make sure to leave a space before the backslash -- IBAL does not insert one for you.)

IBAL> case dist [ 0.3 : 'hello , 0.7 : 'world ] of \
    > # 'world : true \
    > # _ : false