Ranked Programming

1 Introduction

The ranked-programming package implements ranked programming functionality for the Racket programming language. For background and general introduction on ranked programming please read this paper (presented at IJCAI 2019).

This document contains a complete reference of the functionality provided by this package. A quick-start guide for this package can be found here.

Before using this reference, the reader should be familiar with the paper linked to above. There are a few minor differences between the language described in the paper and the language implemented here, as well as a number of additional features not discussed in the paper. We list the differences and additions here:

Ranked Choice

The syntax of the ranked choice expression discussed in the paper is

The ranked choice expression implemented by this library uses a different syntax:

(nrm/exc K1 K2 R).

Either/Or

The syntax of the either/or expression discussed in the paper is

The either/or expression implemented by this library uses a different syntax:

(either/or K1 K2).

Truth expressions

The truth expression !x described in the paper is implemented by the procedure !. This means that we must enclose these expressions in parantheses. Thus, instead of writing

like in the paper, we have to write

(nrm/exc (! "foo") (! "bar") 1)

However, all expressions with parameters of type ranking are implemented so that these parameters also accept values of any other type. Such values are implicitly converted to rankings using !. Therefore, the ! procedure is actually redundant, because instead of (nrm/exc (! "foo") (! "bar") 1) we can simply write

(nrm/exc "foo" "bar" 1)

where "foo" and "bar" are implicitly converted to (! "foo") and (! "bar"), since they appear as arguments to parameters of type ranking.

Displaying Ranking Functions

In this text, ranking functions returned by expressions are referred to simply as rankings. They encode sets of possible return values of an expression, associated with degrees of surprise: 0 for not surprising, 1 for surprising, 2 for even more surprising, and so on. These rankings are represented by lazily-linked list data structures, as discussed in section 4 in the paper. In order to display a ranking, we need to provide it as an argument to one of the print functions implemented by this library. The standard print function is pr. Thus, instead of evaluating an expression like (nrm/exc "foo" "bar" 1) directly, we must evaluate it as follows.

> (pr (nrm/exc "foo" "bar" 1))

Rank  Value ------------ 0     foo 1     bar Done

Alternatives to pr are pr-all, pr-until and pr-first (see reference for details).

Doing other things with rankings

Apart from displaying a ranking, we can also convert it to some other, more manageable, representation. For this, we can use the rf->hash, rf->assoc and rf->stream functions, which convert a ranking to, respectively, a hash table, an association list, or a stream. The cut and limit procedures may also be of use in combination with these functions.

Additional functions and expression types

This library implements all functions and expression types discussed in the paper. These are the truth function (!), ranked choice expression (nrm/exc), the either/or syntactic shortcut (either/or), observation function (observe), ranked procedure call function ($), and ranked let* expression (rlet*).

This library also provides the following additional functions and expression types, which are not described in the paper:

• either-of Choose elements from a list (all equally surprising).

• construct-ranking Construct ranking from an association list.

• rank-of Return rank of a predicate according to a given ranking.

• failure Returns the empty ranking.

• rlet Generalises let, like rlet* generalises let*.

• rf-equal? Check if two rankings are equivalent.

• rf->hash/rf->assoc/rf->stream Convert ranking to other data structure.

• pr-all/pr-first/pr-until/pr Procedures for displaying a ranking.

• observe-r/observe-e Generalised observe variants.

• cut Restrict ranking up to a given rank.

• limit Restrict ranking up to a given number of values.

• rank?/ranking? Type checking for ranks and rankings.

• rank/c/ranking/c Type contracts for ranks and rankings.

These are all described in detail in this reference.

2 Reference

If k_1 and k_2 are rankings then (nrm/exc k_1 k_2 rank) returns a ranking according to which the rank of a value v is the minimum among the rank of v according to the ranking k_1, and the rank of v according to the ranking k_2 plus the value of rank.

> (pr (nrm/exc "foo" (nrm/exc "bar" "baz")))

Rank  Value ------------ 0     foo 1     bar 2     baz Done

Both k_1 and k_2 are evaluated on an as-needed basis. This means that k_1 is evaluated only after the ranking that is returned is consulted for the first time, and k_2 only after it is consulted beyond rank rank. This lazy evaluation scheme avoids needless calculations and provides the ability to define potentially infinite rankings.

Below is an example of an infinite ranking. The expression (recur x) normally returns x and exceptionally (recur (* x 2)). Even though recur is infinitely recursive, it does return a ranking, which is due to the lazy evaluation.

> (define (recur x) (nrm/exc x (recur (* x 2))))

> (pr (recur 1))

Rank  Value ------------ 0     1 1     2 2     4 3     8 4     16 5     32 6     64 7     128 8     256 9     512 ...

If k_1 ... k_n are rankings, then (either/or k_1 ... k_n) returns a ranking according to which the rank of a value v is the minimum among the ranks of v according to the rankings k_1 ... k_n.

This function (called the Truth function in the paper) is included for the sake of completeness but is actually redundant. This is because all expressions provided by this library with parameters of type ranking are implemented so that these parameters also accept values of any other type. Such values are implicitly converted to rankings using !. See discussion in the introduction.

The following example determines the degree of surprise that (recur 1) returns a value higher than 500.

> (define (recur x) (nrm/exc x (recur (* x 2)) 1))

> (rank-of (lambda (x) (> x 500)) (recur 1))

9

The ranking k is consulted as much as necessary but no more. More precisely, k is consulted until a value for which pred returns #t is encountered.

If pred does not return #t for some finitely-ranked value, and k is infinite (i.e., assigns finite ranks to infinitely many values) then rank-of does not terminate.

The predicate pred is only called for values that have a finite rank according to k. If pred does not terminate for one of these values then rank-of might also not terminate. If pred throws an error for one of these values then rank-of might also throw an error.

In the following example we determine the ranking returned by (recur 1) given that we observe that the value that is returned is higher than 500.

The predicate pred is only called for values that have a finite rank according to k. If pred does not terminate for one of these values then observe might also not terminate. If pred throws an error for one of these values then observe might also throw an error. }

The precise rule that is used to construct the ranking returned by the expression ($ k_1 ... k_n) is as follows: Suppose that the rankings k_1 ... k_n assign ranks r_1 ... r_n to the values v_1 ... v_n. Furthermore suppose that the standard procedure call (v_1 ... v_n) returns v. Then v is returned with rank r_1+...+r_n, unless there is another sequence of values that yields a lower rank for v using the same rule.

Consider the procedure call (+ 5 10). The ranked version of this is ($ + 5 10):

> (pr ($ + 5 10))

Rank  Value ------------ 0     15 Done

Now suppose we are uncertain about the argument 10: this value is normally 10 and exceptionally 20. To express this we replace 10 with (nrm/exc 10 20):

> (pr ($ + 5 (nrm/exc 10 20)))

Rank  Value ------------ 0     15 1     25 Done

Now we add uncertainty about the operation: we normally add but exceptionally multiply:

> (pr ($ (nrm/exc + *) 5 (nrm/exc 10 20)))

Rank  Value ------------ 0     15 1     25 1     50 2     100 Done

The precise rule that is used to construct the ranking returned by the expression (rlet ([var_1 k_1] ... [var_n k_n]) body) is as follows: Suppose that the rankings k_1 ... k_n assign ranks r_1 ... r_n to the values v_1 ... v_n. Furthermore, suppose that body, with occurrences of var_1 ... var_n replaced with v_1 ... v_n, returns v. Then v is returned with rank r_1+...+r_n, unless there is another sequence of values that yields a lower rank for v using the same rule.

The rlet expression provides a convenient way to construct a joint ranking over a set of independent variables. An example: let b and p be boolean variables standing for beer and peanuts. We only exceptionally drink beer, and thus b becomes (nrm/exc #f #t). Furthermore, we normally eat peanuts, and thus b becomes (nrm/exc #t #f).

> (pr (rlet        ((b (nrm/exc #f #t))         (p (nrm/exc #t #f)))        (string-append (if b "beer" "no beer") " and "                       (if p "peanuts" "no peanuts"))))

Rank  Value ------------ 0     no beer and peanuts 1     no beer and no peanuts 1     beer and peanuts 2     beer and no peanuts Done

One may wish to express dependencies between variables. In the example above, we might wish to express that our peanut consumption depends on whether we drink beer. However, this cannot be done, since the argument for p cannot refer to the value of b. The rlet* expression extends the rlet expression and provides a solution for such cases.

The rule used to determine the ranking that is returned is the same as that of rlet, except that the expressions used as arguments for k_1 ... k_n may refer to the preceding variables. This provides a convenient way to construct a joint ranking over a list of variables, where each variable may depend on the preceding variables.

An example: let b and p be boolean variables standing for "beer" and "peanuts". Like before, we only exceptionally drink beer, and thus b becomes (nrm/exc #f #t). However, this time our peanut consumption depends on whether we drink beer: if we do, we normally have peanuts, and otherwise we don’t. Thus, p becomes (if b (nrm/exc #t #f) #f). Note that this expression refers to b, which would not be allowed if we used rlet instead of rlet*.

> (pr (rlet*        ((b (nrm/exc #f #t))         (p (if b (nrm/exc #t #f) #f)))        (string-append (if b "beer" "no beer") " and "                       (if p "peanuts" "no peanuts"))))

Rank  Value ------------ 0     no beer and no peanuts 1     beer and peanuts 2     beer and no peanuts Done