Ranked Programming
1 Introduction
2 Reference
nrm/  exc
either/  or
either-of
!
construct-ranking
rank-of
failure
observe
$
rlet
rlet*
rf-equal?
rf->hash
rf->assoc
rf->stream
pr-all
pr-first
pr-until
pr
observe-r
observe-e
cut
limit
set-global-dedup
rank?
ranking?
rank/  c
ranking/  c
8.12

Ranked Programming🔗ℹ

Tjitze Rienstra

 (require ranked-programming) package: 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

(nrm K1 exc R K2)

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

(either K1 or K2)

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

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

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.

Example:
> (rf->assoc (nrm/exc "foo" "bar"))

'(("foo" . 0) ("bar" . 1))

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:

These are all described in detail in this reference.

2 Reference🔗ℹ

syntax

(nrm/exc k_1 k_2 rank)

(nrm/exc k_1 k_2)
 
  k_1 : (any/c)
  k_2 : (any/c)
  rank : (rank?)
Normally returns the value captured by k_1 and exceptionally (with degree of surprise rank) the value captured by k_2. If rank is omitted, it defaults to 1.

Examples:
> (pr (nrm/exc "foo" "bar"))

Rank  Value

------------

0     foo

1     bar

Done

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

Rank  Value

------------

0     foo

2     bar

Done

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

...

syntax

(either/or k_1 ... k_n)

Returns a ranking according to which k_1 ... k_n all equally surprising.

Example:
> (pr (nrm/exc "peter" (either/or "ann" "bob" "charlie")))

Rank  Value

------------

0     peter

1     ann

1     bob

1     charlie

Done

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.

Example:
> (pr (either/or (nrm/exc "peter" "ann") (nrm/exc "bob" "charly")))

Rank  Value

------------

0     peter

0     bob

1     ann

1     charly

Done

procedure

(either-of lst)  ranking?

  lst : (list?)
Returns a ranking according to which all elements of the list lst are equally surprising.

Example:
> (define weekdays (list "mon" "tue" "wed" "thu" "fri"))
> (define weekend (list "sat" "sun"))
> (pr (nrm/exc (either-of weekdays) (either-of weekend)))

Rank  Value

------------

0     mon

0     tue

0     wed

0     thu

0     fri

1     sat

1     sun

Done

syntax

(! v)

Constructs a ranking according to which v is ranked 0 and anything else ranked infinity.

Example:
> (pr (! 5))

Rank  Value

------------

0     5

Done

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.

syntax

(construct-ranking (v_1 . r_1) ... (v_n . r_n))

Constructs a ranking from an association list. The values v_1 ... v_n are returned with ranks r_1 ... r_n. Rank r_1 must be 0, and r_1 ... r_n must be sorted in non-decreasing order.

Example:
> (pr (construct-ranking ("x" . 0) ("y" . 1) ("z" . 5)))

Rank  Value

------------

0     x

1     y

5     z

Done

procedure

(rank-of pred k)  rank?

  pred : (any/c -> boolean?)
  k : (ranking/c)
Returns the rank of the predicate pred according to the ranking k. This value represents the degree of surprise that pred holds according to k. It is the rank of the lowest-ranked value for which pred returns #t.

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.

procedure

(failure)  ranking?

Returns an empty ranking.

procedure

(observe pred k)  ranking?

  pred : (any/c -> boolean?)
  k : (ranking?)
Returns the ranking k conditionalized on the predicate pred. This is the ranking-theoretic conditionalization operation, which is the ranking-based analogue of the probabilistic contitionalization operation.

The ranking returned by the expression (observe pred k) is determined by the following rule: Suppose k assigns a finite rank r to the value v. Then:
  • if (pred v) returns #f then v is discarded (or returned with rank infinity).

  • if (pred v) returns #t then v is returned with rank r minus (rank-of pred k).

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.

Examples:
> (define (recur x) (nrm/exc x (recur (* x 2)) 1))
> (pr (observe (lambda (x) (> x 500)) (recur 1)))

Rank  Value

------------

0     512

1     1024

2     2048

3     4096

4     8192

5     16384

6     32768

7     65536

8     131072

9     262144

...

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. }

procedure

($ k_1 ... k_n)  ranking?

  k_1 : any/c
  k_n : any/c
Returns the result of applying the procedure k_1 to the arguments k_2 ... k_n.

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

syntax

(rlet ([var_1 k_1] ... [var_n k_n]) body)

The rlet expression generalises Racket’s standard let expression. Like in the standard let expression, var_1 ... var_n are variables, and body is an expression in which these variables may occur. The difference with the standard let expression is that the k_1 ... k_n parameters expect arguments of type ranking.

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.

syntax

(rlet* ([var_1 k_1] ... [var_n k_n]) body)

The rlet* expression generalises Racket’s standard let* expression in a way similar to how rlet generalises let.

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

procedure

(rf-equal? k_1 k_2)  boolean?

  k_1 : (ranking/c)
  k_2 : (ranking/c)
Returns #t if k_1 and k_2 are equivalent rankings, and #f otherwise. Two rankings are equivalent if they assign the same rank to each finitely-ranked value. This means that the order in which values with the same rank are returned is irrelevant. This procedure will not terminate if k_1 and k_2 are infinite rankings (i.e., assign finite ranks to infinitely many values).

procedure

(rf->hash k)  hash?

  k : (ranking/c)
Converts the ranking k to a hash table that maps each finitely ranked value to its rank. This procedure will not terminate if k is an infinite ranking (i.e., assigns finite ranks to infinitely many values).

procedure

(rf->assoc k)  list?

  k : (ranking/c)
Converts the ranking k to an association list, which is a list consisting of pairs (v . r) for each finitely ranked value v and rank r. These pairs appear in non-decreasing order with respect to rank. If k is an infinite ranking (i.e., assigns finite ranks to infinitely many values) this function will not terminate.

procedure

(rf->stream k)  stream?

  k : (ranking/c)
Converts the ranking k to a stream that generates pairs (value . rank) for each finitely ranked value and its rank (see racket/stream). These pairs are generated in non-decreasing order with respect to rank. The ranking k will be consulted one value at a time, as the stream is consumed. If k is an infinite ranking (i.e., assigns finite ranks to infinitely many values) then this function returns an infinite stream.

procedure

(pr-all k)  void?

  k : (ranking/c)
Displays the complete ranking k in tabular form and in non-decreasing order with respect to rank. If k is an infinite ranking (i.e., assigns finite ranks to infinitely many values) this function will not terminate.

procedure

(pr-first n k)  void?

  n : (natural-number/c)
  k : (ranking/c)
Like pr-all but only displays the n lowest-ranked values.

procedure

(pr-until rank k)  void?

  rank : (natural-number/c)
  k : (ranking/c)
Like pr-all but only displays values up to rank rank.

procedure

(pr k)  void?

  k : (ranking/c)
Displays the 10 lowest-ranked values of the ranking k. Short for (pr-first 10 k).

procedure

(observe-r x pred k)  ranking?

  x : (rank?)
  pred : (any/c -> boolean?)
  k : (ranking?)
Like observe but implements the more general result-oriented conditionalization operation, where x is the extra posterior belief strength parameter.

procedure

(observe-e x pred k)  ranking?

  x : (rank?)
  pred : (any/c -> boolean?)
  k : (ranking?)
Like observe but implements the more general evidence-oriented conditionalization operation, where x is the extra evidence strength parameter.

procedure

(cut rank k)  ranking?

  rank : (rank?)
  k : (ranking?)
Returns the ranking k restricted to values with a rank of at most rank.

procedure

(limit count k)  ranking?

  count : (rank?)
  k : (ranking?)
Returns the ranking k restricted to the count lowest-ranked values.

procedure

(set-global-dedup enabled)  void?

  enabled : (boolean?)
Sets the global deduplication setting. If enabled, duplicate higher-ranked values are filtered out of any ranking that is computed. If disabled, duplicates may occur (e.g. a ranking where some value x occurs more than once, where the higher-ranked occurrence is redundant). By default, this setting is enabled. Disabling it will lead to less memory consumption, since duplicate detection requires memorisation of values. In some cases, disabling deduplication can speed up inference. In other cases, disabling deduplication slows down inference, due to redundant computations. Which is better depends on the implementation.

Without deduplication:
> (set-global-dedup #f)
> (pr (nrm/exc "a" "a" 5))

Rank  Value

------------

0     a

5     a

Done

With deduplication:
> (set-global-dedup #t)
> (pr (nrm/exc "a" "a" 5))

Rank  Value

------------

0     a

Done

procedure

(rank? x)  boolean?

  x : (any/c)
Returns #t if x is a rank (a non-negative integer or infinity) and #f otherwise.

procedure

(ranking? x)  boolean?

  x : (any/c)
Returns #t if x is a ranking and #f otherwise.

A contract for ranks (non-negative integers or infinity).

A contract for rankings.