Social Contracts

8.12

Social Contracts🔗ℹ

Siddhartha Kasivajhula

High-level, composable syntax for describing contracts.

1 Introduction🔗ℹ

Racket’s built-in contract DSL is a flexible way to describe arbitrary data types. An essential property of data is that it exhibits hierarchical structure. Yet, the contract DSL does not provide corresponding syntactic abstractions with which to express this structure, necessitating that contract authors spell out the details of each contract in terms of primitives such as -> and or/c. In this sense, it is a low-level language for describing the contract, analogous to describing the operation of addition in terms of combinational logic.

The present module provides the missing abstractions, giving us a high level DSL for describing contracts in terms of their phrase structure. The forms provided correspond to commonly encountered high-level data abstractions whose definitions are collectively agreed upon. This agreement may take the form of collaborative development and discussion on the source repository, to agree on, for instance, the most useful form and variations of a predicate contract, or, at least, the agreement may simply be tacit in the sense that these contracts correspond to ideas that are common and widely known.

As an example, when you take two values of the same type and produce another value of the same type, this is an instance of composition. With the built-in contract DSL, the contract for this function may be specified as something like (-> integer? integer? integer?), which does not encode the idea of composition. Instead, here, we simply use the appropriate high-level contract, for instance (binary-composition/c integer?).

As the forms also compose, complex contracts exhibiting phrase structure have compact representations. For instance, (-> (-> integer? integer?) (-> integer? integer?) (-> integer? integer?)) may be expressed as (binary-composition/c (self-map/c integer?)).

2 What if I Don’t See the Contract I Need?🔗ℹ

If you believe that the data you are describing could be expressed more economically than the forms allow, or if an appropriate contract is missing altogether and seems relatively general or common (e.g. you’ve needed this contract more than once, and suspect that others might, as well), consider bringing it up for possible addition. With enough support or motivation, it will be added.

3 How Do I Migrate My Existing Contracts?🔗ℹ

In addition to the forms in contract/social, this collection also includes a racket-contract-to-social-contract "reverse compiler," which can help you migrate any existing contracts you’ve already written. You can use this either interactively, passing it one contract at a time to help you migrate your contracts manually, or you could also give it an entire provide form at once, to translate them all wholesale. See "C3PO": Social Protocol Assistant for more on how to use this. Note that although you might prefer to, it isn’t strictly necessary to migrate existing contracts, since the forms in this module can be used alongside them and even compose with them.

4 Contracts🔗ℹ

4.1 Basic and Arity-Based Forms🔗ℹ

syntax
function/c
syntax
(function/c source/c ... target/c)

A contract to recognize any function. This is the most general function contract and should be a last resort, to be employed only if a more specific contract is not available or appropriate. For instance, if the concerned function is a unary function and target/c is expecting a value of the same type as source/c, prefer using self-map/c instead. Likewise, each of the various function contracts in this module exploits some non-trivial relationship between the contracts specifying the function, and depending on the case, it may be appropriate to use a predicate contract, or an operation, or composition, and so on.

If used as an identifier macro, function/c means a unary function with input and output of type any/c.

function/c in general is equivalent to ->.

Examples:

> (define/contract (list-length lst)
    (function/c list? natural-number/c)
    (if (empty? lst)
      0
      (add1 (list-length (rest lst)))))
> (list-length '(h e l l o))
5
> (list-length "hello")
list-length: contract violation
  expected: list?
  given: "hello"
  in: the 1st argument of
      (-> (listof any/c) natural-number/c)
  contract from: (function list-length)
  blaming: program
   (assuming the contract is correct)
  at: eval:1:0

syntax
thunk/c
syntax
(thunk/c target/c)

A contract to recognize a "thunk", i.e. a function taking no arguments, which returns a value of type target/c. If no target contract is specified (i.e. when it is used in identifier form as thunk/c), the target defaults to any/c.

thunk/c in general is equivalent to (-> target/c).

Examples:

> (define/contract (hello-button)
    thunk/c
    "hello!")
> (hello-button)
"hello!"
> (hello-button "friend")
hello-button: arity mismatch;
the expected number of arguments does not match the given
number
  expected: 0
  given: 1
  arguments...:
   "friend"
> (define/contract (hello-button)
    (thunk/c number?)
    "hello!")
> (hello-button)
hello-button: broke its own contract
  promised: number?
  produced: "hello!"
  in: the range of
      (-> number?)
  contract from: (function hello-button)
  blaming: (function hello-button)
   (assuming the contract is correct)
  at: eval:7:0

syntax
binary-function/c
syntax
(binary-function/c a/c b/c target/c)

A contract to recognize a binary function, that is, a function taking two arguments. The arguments are expected to be of type a/c and b/c, respectively, and the return value is expected to be of type target/c. If the contract is used in identifier form simply as binary-function/c, then the inputs and outputs default to any/c.

binary-function/c in general is equivalent to (-> a/c b/c target/c).

Where applicable, prefer a more specific contract like binary-predicate/c, binary-operation/c, binary-composition/c, or binary-constructor/c.

Examples:

> (define/contract (my-add-as-string a b)
    (binary-function/c number? number? string?)
    (number->string (+ a b)))
> (my-add-as-string 3 5)
"8"
> (my-add-as-string 5)
my-add-as-string: arity mismatch;
the expected number of arguments does not match the given
number
  expected: 2
  given: 1
  arguments...:
   5

syntax
variadic-function/c
syntax
(variadic-function/c source/c)
syntax
(variadic-function/c source/c target/c)
syntax
(variadic-function/c paramspec)
syntax
(variadic-function/c source/c paramspec)
syntax
(variadic-function/c source/c target/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

A contract to recognize a variadic function, that is, a function taking an arbitrary number of arguments. The arguments in general are expected to all be of type source/c, and the return value is expected to be of type target/c. Any number of extra arguments may be indicated via the paramspec, which works the same as it does in self-map/c and operation/c. If no contract is specified for the return value, it defaults to any/c, and using the contract in identifier form simply as variadic-function/c assumes all contracts are any/c.

variadic-function/c in general is equivalent to (-> source/c ... target/c).

Where applicable, prefer a more specific contract like variadic-predicate/c, variadic-composition/c, or variadic-constructor/c.

Examples:

> (define/contract (my-add-as-string . vs)
(variadic-function/c number? string?)
(number->string (apply + vs)))
> (my-add-as-string 3 5 7)
"15"

4.2 Transformations🔗ℹ

syntax
(self-map/c type/c)
syntax
(self-map/c type/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

A contract to recognize a self-map, i.e. a function that maps a value of type type/c to a value of the same type. It could also optionally accept any (but a specific) number of additional arguments. The number and the types of these additional arguments are indicated by supplying a paramspec form, in which the signifier head means that these arguments appear before type/c in the function signature, while tail means that they appear after type/c.

self-map/c in general is equivalent to (-> type/c type/c), and for instance, (self-map/c list? (head number?)) is equivalent to (-> number? list? list?).

Examples:

> (define/contract (double n)
    (self-map/c natural-number/c)
    (* n 2))
> (double 5)
10
> (double "hello")
double: contract violation
  expected: natural-number/c
  given: "hello"
  in: the 1st argument of
      (-> natural-number/c natural-number/c)
  contract from: (function double)
  blaming: program
   (assuming the contract is correct)
  at: eval:14:0
> (define/contract (prefix str n)
    (self-map/c string? (tail natural-number/c))
    (substring str 0 n))
> (prefix "apple" 3)
"app"
> (prefix (list 1 2 3 4 5) 3)
prefix: contract violation
  expected: string?
  given: '(1 2 3 4 5)
  in: the 1st argument of
      (-> string? natural-number/c string?)
  contract from: (function prefix)
  blaming: program
   (assuming the contract is correct)
  at: eval:17:0

syntax
functional/c

A contract to recognize a function that accepts a function and returns another function. Not to be confused with function/c, "functional" is a term used to refer to higher-order functions.

Equivalent to (self-map/c procedure?) or (-> procedure? procedure?).

syntax
(binary-constructor/c primitive/c composite/c)
syntax
(binary-constructor/c #:order order primitive/c composite/c)
syntax
(variadic-constructor/c primitive/c composite/c)
syntax
(variadic-constructor/c #:order order primitive/c composite/c)

Similar to binary-function/c and variadic-function/c, but these contracts are specialized to recognize cons-style constructors that take primitive data and an instance of a rich data type and yield a fresh instance of the rich type incorporating the primitive data. order should be either 'abb or 'bab, reflecting the intended order of the primitive and composite inputs. Note that the order parameter controls the order in which the contracted function expects arguments, not the present forms. That is, regardless of the order specified using order, the first argument to these contract forms is always primitive/c, and the second argument is always composite/c.

This contract is equivalent to self-map/c when the latter expects a single additional argument, and in such cases the appropriate contract should be selected based on whether the function actually entails a notion of "construction" or not.

binary-constructor/c is equivalent to (-> primitive/c composite/c composite/c) or (-> composite/c primitive/c composite/c), depending on the indicated order, and variadic-constructor/c is equivalent to (-> primitive/c ... composite/c composite/c) or (-> composite/c primitive/c ... composite/c).

Examples:

> (define/contract (my-cons elem lst)
    (binary-constructor/c any/c list?)
    (cons elem lst))
> (my-cons "apple" (list "banana" "cherry"))
'("apple" "banana" "cherry")
> (my-cons "apple" "banana")
my-cons: contract violation
  expected: list?
  given: "banana"
  in: the 2nd argument of
      (-> any/c (listof any/c) (listof any/c))
  contract from: (function my-cons)
  blaming: program
   (assuming the contract is correct)
  at: eval:20:0

4.3 Operations🔗ℹ

syntax
(operation/c n source/c target/c)
syntax
(operation/c n source/c)
syntax
(operation/c n source/c target/c paramspec)
syntax
(operation/c n source/c paramspec)
syntax
(binary-operation/c source/c target/c)
syntax
(binary-operation/c source/c)
syntax
(binary-operation/c source/c target/c paramspec)
syntax
(binary-operation/c source/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

operation/c is a contract to recognize an n-ary homogeneous operation, that is, a function taking n arguments where each argument is of the same type. The inputs are expected to be of type source/c, and the return value is expected to be of type target/c. The contract can also accept a specific number of extra arguments which are specified using a paramspec form, which works the same way as in self-map/c. When the (operator/c n source/c) form is used, the output uses any/c. operation/c expects a specific number of inputs. To recognize an arbitrary number of inputs, use variadic-function/c instead.

binary-operation/c recognizes an operation of arity 2. Note that the term "binary operation" isn’t used consistently in mathematical literature, where it sometimes refers specifically to a closed binary operation where the output is of the same type as the input. For this more specific case, use binary-composition/c instead.

As an example, (operation/c 3 source/c target/c) is equivalent to (-> source/c source/c source/c target/c), while (binary-operation/c source/c target/c) is equivalent to (-> source/c source/c target/c).

Examples:

> (define/contract (my-add-as-string a b)
    (binary-operation/c number? string?)
    (number->string (+ a b)))
> (my-add-as-string 3 5)
"8"
> (my-add-as-string 5)
my-add-as-string: arity mismatch;
the expected number of arguments does not match the given
number
  expected: 2
  given: 1
  arguments...:
   5

syntax
(composition/c n type/c)
syntax
(composition/c n type/c paramspec)
syntax
(binary-composition/c type/c)
syntax
(binary-composition/c n type/c paramspec)
syntax
(variadic-composition/c type/c)
syntax
(variadic-composition/c type/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

Similar to operation/c, binary-function/c and variadic-function/c, but these contracts expect the input types and the output type to match, i.e. they recognize functions that compose values of some type.

binary-composition/c is equivalent to (-> type/c type/c type/c); variadic-composition/c is equivalent to (-> type/c ... type/c); and for instance, (composition/c 3 type/c) is equivalent to (-> type/c type/c type/c type/c).

4.4 Encoding🔗ℹ

syntax
predicate/c
syntax
(predicate/c source/c)
syntax
binary-predicate/c
syntax
(binary-predicate/c source/c)
syntax
(binary-predicate/c a/c b/c)
syntax
variadic-predicate/c
syntax
(variadic-predicate/c source/c)
syntax
(variadic-predicate/c source/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

Similar to function/c, binary-function/c, and variadic-function/c, but these contracts recognize predicates, meaning that the output is expected to be of type boolean?.

predicate/c is equivalent to (-> source/c boolean?), binary-predicate/c is equivalent to (-> a/c b/c boolean?), and variadic-predicate/c is equivalent to (-> source/c ... boolean?), with source/c, a/c and b/c defaulting to any/c if left unspecified.

syntax
(encoder/c as-type/c)
syntax
(decoder/c from-type/c)
syntax
hash-function/c

encoder/c recognizes functions that map inputs of any type (i.e. any/c) to a specific type, such as integer?. decoder/c recognizes functions that map inputs of a specific type, such as integer?, to an arbitrary output type (i.e. any/c). hash-function/c recognizes encoders that specifically map to the type fixnum?.

encoder/c is equivalent to (-> any/c as-type/c), decoder/c is equivalent to (-> from-type/c any/c), and hash-function/c is equivalent to (-> any/c fixnum?).

4.5 Data🔗ℹ

syntax
(maybe/c type/c)
syntax
(maybe/c type/c default/c)

A contract to recognize values that may or may not exist. This contract is intended to be used in cases where the value, if missing, is a sentinel value indicating absence, such as #f, undefined, or (void). In cases where the value may simply be one or another type, use or/c instead.

Equivalent to (or/c type/c default/c), with default/c defaulting to #f if left unspecified.

Examples:

> (define/contract v (maybe/c number?) 5)
> (define/contract v (maybe/c number?) #f)
> (define/contract v (maybe/c number? void?) (void))
> (define/contract v (maybe/c number?) "5")
v: broke its own contract
  promised: (or/c number? #f)
  produced: "5"
  in: (or/c number? #f)
  contract from: (definition v)
  blaming: (definition v)
   (assuming the contract is correct)
  at: eval:29:0

syntax
(nonempty/c type/c)

A contract to recognize nonempty sequences of type type/c. Equivalent to (and/c type/c (not/c empty?)).

Examples:

> (define/contract v (nonempty/c list?) (list 1 2 3))
> (define/contract v (nonempty/c string?) "hello")
> (define/contract v (nonempty/c sequence?) "hello")
> (define/contract v (nonempty/c string?) "")
v: broke its own contract
  promised: (not/c empty?)
  produced: ""
  in: an and/c case of
      (and/c string? (not/c empty?))
  contract from: (definition v)
  blaming: (definition v)
   (assuming the contract is correct)
  at: eval:33:0
> (define/contract v (nonempty/c list?) (list))
v: broke its own contract
  promised: (not/c empty?)
  produced: '()
  in: an and/c case of
      (and/c (listof any/c) (not/c empty?))
  contract from: (definition v)
  blaming: (definition v)
   (assuming the contract is correct)
  at: eval:34:0

4.6 Sequences🔗ℹ

syntax
lift/c
syntax
(lift/c pure/c)
syntax
(lift/c pure/c functor/c)
syntax
(lift/c paramspec)
syntax
(lift/c pure/c paramspec)
syntax
(lift/c pure/c functor/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

A contract to recognize a function that "lifts" a value of type pure/c into a container of type functor/c. Typically functor/c would be a parametric sequence type such as listof or sequenceof, and if left unspecified it is assumed to be the latter. Any number of extra arguments may be indicated by using a paramspec form, which works the same as in other contracts like self-map/c.

Equivalent in general to (-> pure/c (functor/c pure/c)).

Examples:

> (define/contract (my-range n)
    (lift/c number? listof)
    (range n))
> (my-range 5)
'(0 1 2 3 4)
> (my-range "5")
my-range: contract violation
  expected: number?
  given: "5"
  in: the 1st argument of
      (-> number? (listof number?))
  contract from: (function my-range)
  blaming: program
   (assuming the contract is correct)
  at: eval:35:0

syntax
map/c
syntax
(map/c source/c)
syntax
(map/c source/c paramspec)
syntax
(map/c source/c target/c)
syntax
(map/c source/c target/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

A contract to recognize a function that maps a sequence to another sequence. It is analogous to ->, except that the source/c and target/c contracts apply to the elements of the input and output sequences, respectively, rather than the inputs and outputs themselves. If left unspecified, target/c is assumed to be the same as source/c. If the contract is used in identifier form simply as map/c, both source/c and target/c are assumed to be any/c. Any number of extra arguments may be indicated by using a paramspec form, which works the same as in other contracts like self-map/c.

(map/c any/c sequence?) is equivalent to (lift/c sequence? sequenceof) but they indicate different things. The former should be used in cases where the sequences in the output are each derived from elements of the input (e.g. a function mapping nodes in a graph to a list of their neighbors), while the latter should be used where the sequences in the input are derived from the input sequence as a whole (e.g. permutations of the input sequence).

Equivalent in general to (-> (sequenceof source/c) (sequenceof target/c)).

Examples:

> (define/contract (rotate n lst)
    (map/c number? (head number?))
    (append (drop lst n) (take lst n)))
> (rotate 3 (list 1 2 3 4 5))
'(4 5 1 2 3)
> (rotate 3 (list "a" "p" "p" "l" "e"))
rotate: contract violation
  expected: number?
  given: "a"
  in: an element of
      the 2nd argument of
      (->
       number?
       (sequenceof number?)
       (sequenceof number?))
  contract from: (function rotate)
  blaming: program
   (assuming the contract is correct)
  at: eval:38:0

Changed in version 2.0 of package social-contract: The former map/c was renamed to mapper/c and this more versatile version was introduced as map/c.

syntax
mapper/c
syntax
(mapper/c source/c)
syntax
(mapper/c source/c target/c)

A contract to recognize a function that maps a function over a sequence of values. The input sequence is expected to contain values of type source/c and the mapping function is expected to be of type (-> source/c target/c), so that the result of the contractually bound function is expected to be of type (sequenceof target/c). source/c and target/c are assumed to be any/c if neither is specified (i.e. if the contract is used in identifier form), and the same if only one is specified.

Equivalent to (map/c source/c target/c (head (function/c source/c target/c))) or (-> (-> source/c target/c) (sequenceof source/c) (sequenceof target/c)).

Examples:

> (define/contract (stringify-numbers fn lst)
    (mapper/c number? string?)
    (map fn lst))
> (stringify-numbers number->string (list 1 2 3 4))
'("1" "2" "3" "4")
> (stringify-numbers number->string (list "1" "2" "3" "4"))
stringify-numbers: contract violation
  expected: number?
  given: "1"
  in: an element of
      the 2nd argument of
      (->
       (-> number? string?)
       (sequenceof number?)
       (sequenceof string?))
  contract from: (function stringify-numbers)
  blaming: program
   (assuming the contract is correct)
  at: eval:41:0

syntax
filter/c
syntax
(filter/c type/c)

A contract to recognize a function that filters a sequence using a predicate. The input sequence is expected to contain values of type type/c. The predicate is expected to be on type/c values as well, and the output is expected to be of the same type as the input. If the contract is used in identifier form, type/c is assumed to be any/c.

Equivalent to (map/c type/c (head (predicate/c type/c))) or (-> (-> type/c boolean?) (sequenceof type/c) (sequenceof type/c)).

Examples:

> (define/contract (take-while pred lst)
    (filter/c number?)
    (if (or (null? lst)
            (not (pred (car lst))))
        null
        (cons (car lst)
              (take-while pred (cdr lst)))))
> (take-while positive? (list 4 2 7 -1 2 3 -4 5))
'(4 2 7)
> (take-while positive? (list "1" "2" "3" "4"))
take-while: contract violation
  expected: number?
  given: "1"
  in: an element of
      the 2nd argument of
      (->
       (-> number? boolean?)
       (sequenceof number?)
       (sequenceof number?))
  contract from: (function take-while)
  blaming: program
   (assuming the contract is correct)
  at: eval:44:0

syntax
reducer/c
syntax
(reducer/c type/c)
syntax
(reducer/c type/c target/c)
syntax
(reducer/c paramspec)
syntax
(reducer/c type/c paramspec)
syntax
(reducer/c type/c target/c paramspec)

paramspec = (head arg/c ...)
| (tail arg/c ...)

A contract to recognize functions that consume a sequence and produce a value. The sequence is expected to contain values of type type/c, and the result is expected to be of type target/c. Any number of extra arguments may be indicated using a paramspec, just like in other forms such as self-map/c.

If target/c is not specified, it is assumed to be type/c. If type/c isn’t specified either, they are both assumed to be any/c.

reducer/c is in general equivalent to (function/c (sequenceof type/c) target/c) or (-> (sequenceof type/c) target/c).

Examples:

> (define/contract (my-sum lst)
    (reducer/c number?)
    (apply + lst))
> (my-sum (list 1 2 3 4))
10
> (my-sum (list "1" "2" "3" "4"))
my-sum: contract violation
  expected: number?
  given: "1"
  in: an element of
      the 1st argument of
      (-> (sequenceof number?) number?)
  contract from: (function my-sum)
  blaming: program
   (assuming the contract is correct)
  at: eval:47:0

syntax
classifier/c
syntax
(classifier/c by-type/c)

A contract to recognize a function that classifies the elements of the input sequence into distinct classes based on some key function. If the contract is used as an identifier, by-type/c defaults to any/c.

Equivalent to (map/c any/c sequence? (head (encoder/c by-type/c))) or (-> (-> any/c by-type/c) sequence? (sequenceof sequence?)).

Examples:

> (define/contract (alphabetize key lst)
    (classifier/c char?)
    (group-by key lst))
> (alphabetize (curryr string-ref 0) (list "apple" "banana" "apricot" "cherry" "blackberry"))
'(("apple" "apricot") ("banana" "blackberry") ("cherry"))
> (alphabetize string-upcase (list "apple" "banana" "apricot" "cherry" "blackberry"))
alphabetize: contract violation
  expected: char?
  given: "APPLE"
  in: the range of
      the 1st argument of
      (->
       (-> any/c char?)
       (sequenceof any/c)
       (sequenceof sequence?))
  contract from: (function alphabetize)
  blaming: program
   (assuming the contract is correct)
  at: eval:50:0

5 "C3PO": Social Protocol Assistant🔗ℹ

(require contract/social/c3po)

package: social-contract

C3PO is a "reverse compiler" that can help you migrate your contracts to social contracts. It accepts contracts, either individually or as an entire provide form, and translates the input so it is rephrased in terms of high-level social contracts. It can even accept social contracts you’ve already written and translate them into more minimal representations, so it could potentially be incorporated into a general-purpose linter for contracts.

To use it, simply translate a contract or provide specification (provided verbatim without quoting) in order to "reverse-compile" it into high-level social contracts.

syntax
(translate ctc)

"Reverse compile" the contract ctc as a social contract specification.

(translate (-> integer? integer? integer?))
(translate (-> any/c number?))
(translate (-> string? any/c))
(translate (-> (-> integer? integer? integer?) (-> integer? integer? integer?)))
(translate (provide address occupation (contract-out [name (-> any/c string?)])))

5.1 Limitations🔗ℹ

You should use C3PO as an assistant and not defer to it blindly, due to the following limitations.

5.1.1 Correct Vs Appropriate Contracts🔗ℹ

Low-level contract specifications cannot in general be uniquely mapped to high level contract representations, and in some cases a matching high-level contract may coincidentally have the same signature but not actually describe the data in question. For instance, a function that takes a number and a list and returns a list has the signature of a constructing function, yet, this particular function may be using the input number as an index of some kind to extract a sublist rather than incorporating it into the resulting list as a constructor typically would. We may prefer to think of this as a parametrized self-map or as a binary function rather than as a binary constructor. It all boils down to the question, "what is the idea behind this function?" – which can’t always be discerned from the function signature alone.

5.1.2 Not All Contract Forms Supported🔗ℹ

At the moment, C3PO supports the -> and ->* contract forms, but not ->i. If ->i is encountered during parsing, it would just leave this form unchanged in the output (while translating the rest of it). Note that this is a limitation of C3PO, not the forms in contract/social, which are fully compatible with the built-in forms.

1	Introduction
2	What if I Don’t See the Contract I Need?
3	How Do I Migrate My Existing Contracts?
4	Contracts
5	"C3PO": Social Protocol Assistant