Recursion

Recursion is central to programming, and very important in stochastic modeling. Many modeling frameworks rely on it, implicitly or explicitly. For example, a Markov chain is a recursively defined process in which a system evolves from one state to the next via some specified transition model. Meanwhile, a stochastic context free grammar explicitly uses recursion to model how a sentence is generated.

As mentioned previously, recursive functions can naturally be defined in IBAL. When defining a function f in a declaration of the form f(x_1,...,x_n) = e, the name f is bound in e to the function itself. Thus f can be invoked within its own body to create a recursive call. Similarly, the fix notation can be used to define a recursive function within an expression. For example, here is a noisy version of a power function, in which a is multiplied by itself n times, except that some of the times the multiplication can ``fail'' to happen.

f(a,b) =
  if b == 0
  then 1
  else 
    let m = dist [0.7 : a, 0.3 : 1] in
    m * f(a,b-1)

f(2,3)

Using recursion along with structured data types, we can easily define a Markov chain. The following example, contained in markov1.ibl, defines a simple random walk:

type Chain = <state : Int, next : Chain>

trans(prev) = 
  let curr = prev + dist [ 0.5 : 1, 0.5 : -1 ] in      
  <state : curr, next : trans(curr)>

walk : Chain = <state : 0, next : trans(0)>

We first define the type of a Markov chain to be a linked list. Each element contains a state, which in our case is just an integer, and a link to the remainder of the chain. We define a transition function, which takes a previous state and returns a new chain. The Markov chain itself is constructed using an initial state and the transition function. Note that the value of the variable walk is infinite! Nevertheless, one can issue a query such as walk.next.next.state, and IBAL returns an answer.

To achieve this, IBAL uses the technique of lazy evaluation. When answering a query, it generates only the part of the model needed to answer the query. In our example, in order to know the value of walk.next.next.state, IBAL only needs to generate variables corresponding to walk.state, walk.next.state and walk.next.next.state. The remainder of the walk object is irrelevant to the query and is not generated.

In addition to lazy evaluation, IBAL also supports eager evaluation, in which the answer to a query is computed in the natural order in which an experiment is defined. So in the above example, the entire walk object will be generated before walk.next.state can be computed, and thus the computation will not terminate. Thus, eager evaluation is at a disadvantage with this example. However, eager evaluation is usually much more efficient on examples on which it does terminate, so it is often the better option. The default mode of evaluation is eager. Lazy evaluation can be turned on using the -l flag.

While tuples, as we have seen, do support recursion, IBAL provides algebraic data types (ADTs) as a general mechanism defining recursive data structures. ADTs provide support for recursion in two ways. First and foremost, the very definition of an ADT can be recursive. In addition, elements of an ADT can have different forms, some of which may recurse while others do not. This allows finite but arbitrarily structured recursive objects to be specified, such as lists and trees.

The different forms of an ADT are specified by different constructors. A constructor is an upper case identifier, and is associated with zero or more fields, each of which has some type. A value for the ADT will have a constructor, and also values for the fields associated with the constructor.

The canonical example of an ADT is the list. A list has two possible forms. It can either be empty, or it can consist of an element followed by a list. An ADT describing lists of integers can be defined using the following declaration:

data List = Nil | Cons (Int, List)

To construct an actual list, just use one of the constructors, and then specify values for each of the fields. For example, Nil and Cons (2, Cons (1, Nil)) are two lists. When you enter Nil at the IBAL prompt, you see that the name of the variable in the result, is *.!. The ! indicates that the variable represents the constructor of an ADT. Similarly, the value of the constructor shows up as !Nil. Variables representing constructors are special, because they determine which other variables show up in the result. For example, suppose you enter Cons (1, Nil). There are two new variables, *.Cons_0 and *.Cons_1 representing the two fields of the Cons form of list. Now, what happens if the two types of constructors can both appear in the result? Try

dist [0.5 : Nil, 0.5 : Cons (1, Nil)]

The result contains all possible variables that could show up for any constructor. If a variable is undefined in a particular row, because the constructor has the wrong type, - [] appears in place of the value. This is IBAL's way of saying that that variable can take on any value, in other words its value doesn't matter.

Programming with ADTs is most easily done by pattern matching. For example, we can compute the length of a list with

length (l) =
  case l of
  # Nil : 0
  # _ :: xs : 1 + length (xs)

Of course, everything we have said about lists of integers applies to lists of any other type. In fact, we can define the list ADT to be polymorphic, as follows

data List [a] = Nil | Cons (a, List [a])

Here a is a type variable. The square brackets indicate that a is a parameter of the List type. A type may have zero or more type parameters. The square brackets are optional, but help clarify the syntax, and are necessary in some cases.

A list of a is either empty, or consists of an a followed by a list of a. Polymorphism is a powerful programming technique. Once we have polymorphic types, we can define polymorphic functions that work on many different types. In fact, the length function we defined above works just as well for lists of any type. If you check the type of length, you will see that it is List[a] -> Int, meaning that is a function from lists of a to integers. If you want to learn more about polymorphism, study a functional programming language such as Objective CAML or Haskell.

This List type is defined in the library list.ibl, which is automatically loaded when IBAL is run. Also, standard syntax for lists is available: [] denotes the empty list, $x \verb@::@ \ell$ denotes the list in which $x$ is consed onto $\ell$, and $\verb@[@ x_1 \verb@,@ ... \verb@,@ x_n \verb@]@$ denotes the list consisting of $x_1,...,x_n$. You can still use the Nil and Cons(x,xs) if you like. Useful functions such as head, tail and length have been defined. Remember that when using one of these functions, you have to prepend the name of the library, so for example you would call list.length.

Now that we have the polymorphic List type, let us define general Markov chains using the List ADT. The following code can be found in markov2.ibl. We will allow the state space to be any type a. A Markov chain is defined by an initial distribution and a transition model. We define Init and Trans types, each parameterized by a:

type Init [a] = () -> a
type Trans [a] = (a) -> a

The first declaration indicates that an Init a is a function that takes zero arguments and produces an a; the meaning of such a function is a probability distribution over values of type a. Meanwhile a Trans a takes a value of type a and stochastically produces another value of that type. We then define

type Markov [a] = < init : Init [a], trans : Trans [a] >

A realization of a Markov chain is a sequence of states, where the first state is generated from the initial distribution, and the k+1-the state is generated by applying the transition model to the k-th state.

realize (m) : (Markov [a]) -> List [a] = 
  let f(x) = x :: f(m.trans (x)) in
  f(m.init ())

Note the type assertion, which says that realize is a function that takes a Markov [a] and produces a List [a], i.e. a realization.

We then redefine our random walk example as a specialization of the Markov type, where type a is an integer.

random_walk : Markov [Int] = 
     < init : fun () -> 0, 
       trans : fun (n) -> dist [ 0.5 : n++, 0.5 : n-- ] >

walk = realize(random_walk)

To access individual states in the realization, we define the helper function nth, as follows:

nth (n,l) : (Int, List [a]) -> a =
  case l of
  # x :: xs : if n==0 then x else nth (n-1,xs)
  # [] : error "Too short";

Note the special error expression. It corresponds to an experiment that has no value, but instead results in an error condition with the associated error message. If the function nth is applied to a list that is too short for the first argument, the error condition results. In our case, the error is impossible because the list corresponding to the realization of a Markov chain is infinite.

To test the code, try entering nth(3,walk). Gradually increase the value of n. The time IBAL takes to return an answer should grow cubicly. Why is that? Well, IBAL needs to perform some work for each of the n time steps. At each step, IBAL has to compute a transition model from $n$ states to $n$ states. Thus the total amount of work is cubic in n.

We might have expected IBAL to take exponential time as n increases. After all, the number of possible random walks is exponential in n. However, IBAL uses dynamic programming to avoid having to consider all possible paths. This is achieved by memoizing all function applications. Whenever IBAL tries to answer a query on a function application, it checks to see whether the same query has been asked before, with the same possible set of values for its arguments. This has the general effect of reproducing a variety of dynamic programming algorithms, such as forwards-backwards for hidden Markov models and the inside algorithm for stochastic context free grammars.