Expressions

An expression describes a stochastic experiment that generates values. The generated value may depend on the values of free variables inside the expression, and also on the value of parameters used in the expression; together, these are called the background knowledge. The meaning of an expression is a function from the background knowledge to probability distributions over its value, or alternatively, a conditional probability distrubion over the value of the expression given the background knowledge. The notation P_e(v|K) is used to denote the conditional probability distribution defined by expression e over values v given background knowledge K. If x is a free variable or parameter, K(x) denotes the value of x in the background knowldge. All values that are assigned positive probability by an expression must belong to the same type, which is the type of the expression.

Experiments produce a utility in addition to a value. The meaning of an expression is therefore the joint distribution over the the utility and the value, conditioned on the background knowledge. We will generally be interested in the expected utility produced by an expression. The notation U_e(K) will denote the conditional expected utility given the background knowledge K, while U_e(v,K) will denote the conditional expected utility given both the background knowledge and the fact that the expression produced the value v. These are related by U_e(K) = \sum_v P_e(v|K)U_e(v,K). In many cases the utility returned by an expression does not depend on the value, and these two are the same.

IBAL has the following expression forms:

• Constant expressions, consisting of a string, Boolean or integer literal, describe the experiment that always generates the corresponding value. I.e. P_e(v|K) = 1 if v is the value defined by the literal e, 0 otherwise. For constant expressions, U_e(v,K) = 0.

• Unary operator expressions have the form op e_1 where op is one of the unary operators defined in Section 1, and e_1 is an expression whose type is the same as the operator. This describes the experiment in which e_1 is generated and then the operator is applied to it to produce the result. The probability distribution and utility are given by:

  P_e(v|K) = Sum_{w:op w = v} P_e_1(w|K)
  U_e(v,K) = (1/P_e(v|K)) Sum_{w:op w = v} P_e_1(w|K) U_e_1(v,K)
  U_e(K) = U_e_1(K)
  

• Binary operator expressions have the form e_1 op e_2 where op is one of the binary operators defined in Section 1, and e_1 and e_2 are expressions whose type is the same as the operator. This describes the experiment in which e_1 and e_2 are generated and then the operator is applied to them to produce the result. The values of e_1 and e_2 are conditionally independent given the background knowledge. The probability distribution and utility are given by:

  P_e(v|K) = Sum_{w_1,w_2: w_1 op w_2 = v} P_e_1(w_1|K) P_e_2(w_2|K)
  U_e(v,K) = (1/P_e(v|K) Sum_{w_1,w_2: w_1 op w_2 = v} P_e_1(w_1|K) P_e_2(w_2|K) (U_e_1(w_1,K) + U_e_2(w_1,K))
  U_e(K) = U_e_1(K) + U_e_2(K)
  

• The operator constants op, in which op is an operator not appearing in infix or prefix position as in the previous two cases, denote the experiment whose value is always the built-in function specified by the operator.

• The lambda expression fun (x_1,...,x_n) -> e_1 where the x_i are lidents is a function constant, that always produces the function with formal arguments x_1,...,x_n, body e_1 in context K.

  The notation fun x_1 -> e_1 is equivalent to fun (x_1) -> e_1.

  The fix expression fix f (x_1,...,x_n) -> e_1 where f and the x_i are lidents is also a function constant, that always produces the function with name f, formal arguments x_1,...,x_n, body e, in the context produced by extending K with the binding associating f with the function itself.

  The notation fix x_1 -> e_1 is equivalent to fix (x_1) -> e_1.

• The tuple expression <n_0 : e_0, ..., n_m : e_m> has the type <n_0 : t_0, ..., n_m : t_m>, where t_i is the type of expression e_i. It describes the experiment in which a value v_i is generated for each e_i, and the tuple <n_0 : v_0, ..., n_m : v_m> is returned. The different v_i are generated independently given the background knowledge, so the probability distribution and utility are given by

  P_e(<n_0 : v_0, ..., n_m : v_m>|K) = Prod_i P_e_i(v_i|K)
  U_e(<n_0 : v_0, ..., n_m : v_m>, K) = Sum_i U_e_i(v_i,K)
  U_e(K) = Sum_i U_e_i(K)
  

  The anonymous tuple expression <e_0, ..., e_m> is equivalent to the tuple <0 : e_0, ..., m : e_m>.

• The expressions U, U e_1 and U (e_1,...,e_n) where n>2 are constructor expressions. U is a longvar identifying a constructor of a previously defined ADT. The constructor has zero fields in the first case, one in the second case and n in the third case. The types of the expressions e_i are the same as those of the corresponding fields. A constructor expression is similar to a tuple expression. It describes the experiment in which the e_i are evaluated, and the results are bundled together in an ADT value.

• The variable x, where x is a longvar, is the experiment that always produces the value of the x according to the background knowledge. x must be defined in the background knowledge. The probability distribution is given by P_e(v|K) = 1 if K(x) = v, 0 otherwise. The utility is 0.

• The dot notation is extended to general component access. e_1.n, where e_1 is an expression of tuple type <n:t,...>, is an expression of type t. It denotes the experiment of evaluating e_1 and extracting the component named n from the resulting tuple. If w is a tuple, let <n:v,w> denote the tuple that associates n with v and otherwise is the same is w.

  P_e(v|K) = \sum_w P_e_1(<n:v,w>|K)
  U_e(v,K) = (1/P_e(v|K)) \sum_w P_e_1(<n:v,w>|K) U_e_1(<n:v,w>,K)
  U_e(K) = U_e_1(K)
  

• The conditional if e_1 then e_2 else e_3 in which e_1 is an expression of Bool type, while e_2 and e_3 are expressions of the same type, describes the following stochastic experiment: first a value of e_1 is generated, then if it is true a value of e_2 is returned, otherwise a value of e_3 is returned. Given the background knowledge, the outcomes of e_1, e_2 and e_3 are independent. Therefore the probability distribution over values is defined as follows.

  P_e(v|K) = P_e_1(\true|K)P_e_2(v|K) + P_e_1(\fls|K)P_e_3(v|K)
  

  For a given value v, by Bayes rule

  P(\true|v,K) = P_e_1(\true|K)P_e_2(v|K) / P_e(v|K)
  P(\fls|v,K) = P_e_1(\fls|K)P_e_3(v|K) / P_e(v|K)
  

  Then the conditional expected utility given that the value is v is

  U_e(v,K) = P(\true|v,K)(U_e_1(\true,K) + U_e_2(v,K)) + P(\fls|v,k)(U_e_1(\fls,K) + U_e_3(v,K))
  

  Note that in the description of the experiment, only one of the consequents is ever evaluated. In particular, if an observation in one of the consequents conditions the background knowledge, that conditioning will only take effect in those cases that the consequent is evaluated.

• The case expression has the form

  case e_0 of
  # p_1 : e_1
  ...
  # p_n : e_n
  

  where the p_i are exhaustive patterns of the same type as expression e_0, while the e_i are all expressions of the same type, which is also the type of the entire case expression. The first hash is optional. Such an expression describes the experiment in which the value of e_0 is generated, and if it is accepted by p_0 then the value of e_1 is generated, else if it is accepted by p_0 then the value of e_2 is generated, and so on. A p_i may contain a variable x, as described in Section 4. If so, a binding associating x with the value it accepted is added to the background knowledge before evaluating e_i. We write P_e_i(v|K,w) to indicate the extension of the background knowledge when value w is accepted by p_i.

  For any value w, let i(w) = 1 if w is accepted by p_1, 2 if it is accepted by p_2 but not p_1, and so on. Then the probability distribution over values of the case expression is given by:

  P_e(v|K) = \sum_w P_e_0(w|K)P_e_{i(w)}(v|K)
  

  One can immediately see that an ordinary conditional can be viewed as a special form of case expression. Alternatively, a case expression can be expressed as a sequence of nested conditionals. This is the approach taken in the IBAL implementation.

• The comparison e_1 == e_2, in which e_1 and e_2 are expressions of the same type, is an expression of type Bool. It describes the experiment in which values for e_1 and e_2 are generated, and the value trueis returned if the outcomes are equal, false otherwise. As usual, e_1 and e_2 are conditionally independent given the background knowledge. The probability distribution over values is

  P_e(\true|K) = \sum_w P_e_1(w|K) P_e_2(w|K)
  P_e(\fls|K) = 1 - P_e(\true|K)
  U_e(\true,K) = (1/P_e(\true|K) Sum_w (P_e_1(w|K) P_e_2(w|K) (U_e_1(w,K) + U_e_2(w,K))
  U_e(\fls,K) = (1/P_e(\fls|K)) Sum_{w_1,w_2:w_1<>w_2} (P_e_1(w_1|K) P_e_2(w_2|K) (U_e_1(w_1,K) + U_e_2(w_2,K))
  U_e(K) = U_e_1(K) + U_e_2(K)
  

• The expression dist [ f_1 : e_1, ..., f_n : e_n ] specifies stochastic choice over the values of e_1 to e_n. The f_i are posfloats; if they do not sum to 1, they are normalized, so we shall assume that they sum to 1. The e_i are expressions of the same type, which is also the type of the whole expression. The expression describes the experiment in which an integer between 1 and n is randomly chosen, with the probability of i being f_i. Then, if i is chosen, the value of e_i is returned. The probability distribution over values is P_e(v|K) = \sum_i f_i P_e_i(v|K). By Bayes rule, P(i|v,K) = f_i P_e_i(v|K). The utility is given by

  U_e(v,K) = Sum_i P(i|v,K) U_e_i(v,K)
  U_e(K) = Sum_i f_i U_e_i(K)
  

  flip f, where f is a float between 0 and 1, is equivalent to dist [ f : \true, 1-f : \fls ].

  uniform n, where n is a positive integer, is equivalent to dist [ 1/n : 0, ..., 1/n : n-1 ].

  pdist p [ e_1, ..., e_n ], where p is the name of a previously defined n dimensional parameter, specifies stochastic choice using a learnable parameter. Since the background knowledge specifies the parameter value, the conditional distribution over the value of the expression given the background knowledge can be specified: P_e(v|K) = Sum_i K(p)_i P_e_i(v|K).

• Applications have the general form e_0 (e_1, ..., e_n). e_0 is an expression of arrow type, taking n arguments of type t_1 to t_n and returning a result of type t. Each e_i has type t_i, and t is the type of the application. An application describes the experiment of generating a value for e_0, which is a function, and applying it to the values of e_1, ..., e_n.

  A function f taking formal arguments x_1,...,x_n describes a conditional distribution over values given values of the arguments. If the body of the function is g and its context is L, then the conditional distribution defined by f is

  P_f(v|v_1,...,v_n) = P_g(v|L,x_1=v_1,...,x_n=v_n)
  

  The meaning of the application is then defined by summing over all possible function and argument values:

  P_e(v|K) = Sum_{v_0,...,v_n} Prod_i P_e_i(v_i|K) P_v_0(v|v_1,...,v_n)
  

  The utility function is given by

  U_e(v,K) = (1/P_e(v,K)) Sum_{v_0,...,v_n} (Prod_i P_e_i(v_i|K)) (\sum_i U_e_i (v_i,K)) U_v_0(v|v_1,...,v_n)
  

• The various declarations also appear inline in expression form.
  • The let expressions generate values for new variables, adding them to the knowledge base. The form is let p = e_1 in e_2 where p is a pattern, e_1 is an expression of the same type as p, and e_2 is another expression whose type is the type of the entire let expression. The let expression describes the experiment in which a value is generated for e_1, and it is matched to p. If p contains variables, these are bound to the components they match, and the background knowledge is extended. The value of e_2 is then generated and returned. It is an error for e_1 to generate, with positive probability, a value that is rejected by p. We write P_e_2(v|K,w) for the probability distribution over values v given the extended background knowledge produced by matching w to p.

    P_e(v|K) = \sum_w P_e_1(w|K) P_e_2(v|K,w)
    U_e(v,K) = (1/P_e(v|K)) \sum_w P_e_1(w|K) P_e_2(v|K,w) (U_e_1(w,K) U_e_2(v,K|w))
    

    The form let p : t = e_1 in e_2 is the same, with the additional assertion that e_1 has type t.

    The form let f(x_1,...,x_n) = e_1 in e_2 is equivalent to let f = fix f(x_1,...,x_n) -> e_1 in e_2.

    The form let f(x_1,...,x_n) : t = e_1 in e_2 is the same, with the additional assertion that e_1 has type t.

    Values of variables are computed lazily in IBAL, so if a variable defined by a let expression is not needed its value will not be computed.

  • The observation expressions condition the probability distribution over values on certain events. The form obs x = p in e_1, where x is a longvar and p is a pattern can be understood as follows: let fail be a special value that is not generated by any normal expression. Then the observation expression returns the value of e_1 if x is accepted by p, and fail otherwise. The probability distribution is given by P_e(fail|K) is 1 if K(x) is rejected by p, otherwise P_e = P_e_1.

    From a global point of view, experiments that produce fail are rejected. This has the effect of conditioning the probability distribution on the observation having the required value.

    obs x in e_1 is equivalent to obs x = true in e_1. obs ~x in e_1 is equivalent to obs x = false in e_1.

  • A decision expression has the form decide x choices givens in e_1, where x is a name, choices is a specification of the options available to the decision maker, and givens specifies the information available to the decision maker. choices and givens have the same syntax as in Section 5. It describes a situation in which a decision maker chooses the value of x so as to maximize its future expected utility. For each value v of choices, let U_e_1(K,x=v) denote the expected utility of e_1 when the background knowledge is extended by binding x to v. Given information i, let P(K|i) be the probability of the background knowledge given the information. Then the expected utility of choosing v given the agent's information i is Sum_K P(K|i) U_e_1(K,x=v).

    Thus the decision expression defines an experiment as follows. Given the background knowledge K, compute the information known to the agent i, and determine the optimal decision

    v* = argmax_v Sum_K P(K|i) U_e_1(K,x=v)
    

    Then add the binding of x to v* to the background knowledge, and produce the result of evaluating e_1.

  • A parameters expression has the form params d_1 ; ... ; d_n in e_1 where each d_i is a parameter declaration of the form p = [ f_1, ..., f_n ]. The meaning is similar to a parameter declaration, except that multiple parameters can be generated by a single expression. Each of the names p is associated with a parameter with the given Dirichlet prior.

  • A simple reward expression has the form reward f in e_1 where f is a float. This is the same as e_1, except that f is added to the utility.

    A conditional reward expression has the form reward case e_1 of clauses in e_2 where clauses has the same syntax as in Section 5. This is the same as e_2, except that a reward whose value depends the value of e_1 is added, as described in Section 5.

    A discounted reward expression has the form discount f in e_1, where f is a posfloat. This is the same as e_1, except that the utility is multiplied by f.

  • A type synonym can be defined in an expression using the lettype defn in e_1, where defn has the same syntax as in Section 5. The defined type is available for use in e_1. The meaning of the expression is the same as e_1.

  • An ADT can be defined in an expression using the letdata defn in e_1, where defn has the same syntax as in Section 5. The defined type is available for use in e_1. The meaning of the expression is the same as e_1.

• The expression { b } where b is a block has type equal to the tuple type of b. We can understand a block to be equivalent to an expression made up of the declaration-expression forms described previously. Specifically, let e be the tuple expression <n_0 : n_0, ..., n_m : n_m> where the n_i are the non-private names defined in the block. Then, if the block consists of the declarations d_1,...,d_l, it is equivalent to the expression h_1 in ... in h_l in e, where each of the h_i is an expression form corresponding to the declaration d_i.

• (e) is an expression equivalent to e.

• e:t is equivalent to e, with the added assertion that its type agrees with type expression t.

• error s, where s is a string literal, evaluates to an error condition with the given error message s. This expression can have any type. It is useful for specifying the result of computation in cases that ordinarily should not be reached. The expression error is equivalent to error "".