DSSL2:   Data Structures Student Language
1 Syntax introduction
1.1 Compound statements and blocks
1.2 Formal grammar
2 Lexical syntax
2.1 Identifiers
2.2 Numeric literals
2.3 String literals
2.4 Comments
3 Statement forms
3.1 Definition and assignment forms
let
=
def
3.2 Loop and control forms
pass
if
elif
else
for
while
break
continue
return
3.3 Data and program structuring forms
struct
class
interface
import
3.4 Testing and timing forms
assert
assert_  eq
assert_  error
test
time
4 Expression forms
4.1 Variable expressions
4.2 Literal expressions
True
False
4.3 Functions and application expressions
lambda
4.4 Vectors and indexing expressions
4.5 Structs and projection expressions
4.6 Operator expressions
**
not
~
*
/
%
+
-
<<
>>
&
^
\|
==
!=
is
|is not|
<
<=
>
>=
and
or
5 Built-in functions, classes, methods, and constants
5.1 Primitive classes
5.1.1 Class bool
bool
5.1.2 Class char
char
5.1.3 Class int
int
«int».abs
«int».ceiling
«int».floor
«int».sqrt
5.1.4 Class float
float
«float».abs
«float».ceiling
«float».floor
«float».sqrt
5.1.5 Class proc
proc
«proc».compose
«proc».vec_  apply
5.1.6 Class str
str
«str».explode
«str».format
«str».len
5.1.7 Class vec
vec
«vec».filter
«vec».implode
«vec».len
«vec».map
5.2 Predicates
5.2.1 Basic type predicates
bool?
char?
contract?
flat_  contract?
int?
float?
proc?
str?
vec?
5.2.2 Numeric predicates
num?
nat?
zero?
pos?
neg?
even?
odd?
nan?
5.3 Comparision operations
cmp
max
min
5.4 Randomness operations
random
RAND_  MAX
random_  bits
5.5 I/  O Functions
print
println
5.6 Other functions
error
dir
6 Contracts
6.1 Contract syntax
6.2 Contract combinators
Any  C
Void  C
Vec  C
Fun  C
Not  C
Or  C
And  C
Int  In  C
apply_  contract
7.1

DSSL2: Data Structures Student Language

Jesse A. Tov <[email protected]>

 #lang dssl2 package: dssl2

1 Syntax introduction

1.1 Compound statements and blocks

DSSL2 uses alignment and indentation to delimit blocks. In particular, compound statements such as if-elif-else take ⟨block⟩s for each condition, where a ⟨block⟩ can be either one simple statement followed by a newline, or a sequence of statements on subsequent lines that are all indented by four additional spaces. Here is an example of a tree insertion function written using indentation:

#lang dssl2
 
def insert!(t, k):
    if empty?(t): new_node(k)
    elif zero?(random(size(t) + 1)):
        root_insert!(t, k)
    elif k < t.key:
        t.left = insert!(t.left, k)
        fix_size!(t)
        t
    elif k > t.key:
        t.right = insert!(t.right, k)
        fix_size!(t)
        t
    else: t

Each block follows a colon and newline, and is indented 4 spaces more than the previous line. In particular, the block started by def is indented by 4 spaces, and the elif blocks by 8. When a block is a simple statement, it can be placed on the same line, as in the if and else cases.

Extraneous indentation is an error.

1.2 Formal grammar

The DSSL2 language has a number of statement and expression forms, which are described in more depth below. Here they are summarized in Extended Backus-Naur Form.

Non-terminal symbols are written in ⟨italic_with_pointies⟩, whereas terminal symbols are in colored typewriter. Conventions include:

The grammar begins by saying that a program is a sequence of zero or more statements, where a statement is either a simple statement followed by a newline, or a compound statement.

program

 

=

 

{ statement }*

 

 

statement

 

=

 

simple NEWLINE

 

|

 

compound

 

 

simple

 

=

 

assert expr

 

|

 

assert_eq expr , expr

 

|

 

assert_error expr [ , expr ]

 

|

 

break

 

|

 

continue

 

|

 

lvalue = expr

 

|

 

expr

 

|

 

import mod_spec

 

|

 

let name opt_ctc [ = expr ]

 

|

 

pass

 

|

 

return [ expr ]

 

|

 

simple ; simple

 

 

lvalue

 

=

 

name

 

|

 

expr . name

 

|

 

expr [ expr ]

 

 

mod_spec

 

=

 

mod_name

 

|

 

mod_string

 

 

compound

 

=

 

class name opt_ctc_params opt_implements : class_block

 

|

 

def name opt_ctc_params ( { name opt_ctc },* ) opt_res_ctc : block

 

|

 

if expr : block { elif expr : block }* [ else : block ]

 

|

 

interface name opt_ctc_params : interface_block

 

|

 

for [ name , ] name in expr : block

 

|

 

struct name : struct_block

 

|

 

test [ expr ] : block

 

|

 

time [ expr ] : block

 

|

 

while expr : block

 

 

block

 

=

 

simple NEWLINE

 

|

 

NEWLINE INDENT { statement }+ DEDENT

 

 

class_block

 

=

 

NEWLINE INDENT class_fields class_methods DEDENT

 

 

class_fields

 

=

 

{ field_def NEWLINE }*

 

 

class_methods

 

=

 

{ method_proto : block }+

 

 

interface_block

 

=

 

pass

 

|

 

NEWLINE INDENT { method_proto NEWLINE }+ DEDENT

 

 

method_proto

 

=

 

def name opt_ctc_params ( name { , name opt_ctc }* ) opt_res_ctc

 

 

struct_block

 

=

 

pass

 

|

 

NEWLINE INDENT { field_def NEWLINE }+ DEDENT

 

 

field_def

 

=

 

let name opt_ctc

 

 

opt_implements

 

=

 

[ ( { name },* ) ]

 

 

opt_ctc

 

=

 

[ : ctc ]

 

 

opt_res_ctc

 

=

 

[ -> ctc ]

 

 

opt_ctc_params

 

=

 

[ [ { name },* ] ]

 

 

ctc

 

=

 

expr

 

 

expr

 

=

 

number

 

|

 

string

 

|

 

True

 

|

 

False

 

|

 

lvalue

 

|

 

expr if expr else expr

 

|

 

expr ( { expr },* )

 

|

 

lambda { name },* : simple

 

|

 

λ { name },* : simple

 

|

 

struct_name { { name : expr },* }

 

|

 

[ { expr },* ]

 

|

 

[ expr ; expr ]

 

|

 

[ expr for [ name , ] name in expr [ if expr ] ]

 

|

 

expr binop expr

 

|

 

unop expr

 

 

binops are, from tightest to loosest precedence:

unops are ~, +, -, and not.

2 Lexical syntax

2.1 Identifiers

Names, used for variables, functions, structs, classes, interfaces, fields, and methods, must start with a letter, followed by 0 or more letters or digits. The last character also may be ? or !.

2.2 Numeric literals

Numeric literals include:

2.3 String literals

String literals are delimited by either single or double quotes:

def does_not_matter(double):
    if double:
        return "This is the same string."
    else:
        return 'This is the same string.'

The contents of each kind of string is treated the same, except that each kind of quotation mark can contain the other kind unescaped:

def does_matter(double):
    if double:
        return "This isn't the same string."
    else:
        return '"This is not the same string" isn\'t the same string.'

Strings cannot contain newlines directly, but can contain newline characters via the escape code \n. Other escape codes include:

Any other character following a backslash stands for itself.

An alternative form for string literals uses three quotation marks of either kind. The contents of such a string are treated literally, rather than interpreting escapes, and they may contain any characters except the terminating quotation mark sequence.

let a_long_string = '''This string can contain ' and " and
even """ and newlines. Just not '' and one more.'''

2.4 Comments

A comment in DSSL2 starts with the # character and continues to the end of the line.

Long string literals can also be used to comment out long blocks of code.

3 Statement forms

3.1 Definition and assignment forms

simple

let var_name = ⟨expr

Declares and defines a local variable. Local variables may be declared in any scope and last for that scope. A local variable may be re-assigned with the assignment form (=), as in the third line here:

def sum(v):
    let result = 0
    for elem in v: result = result + elem
    return result

simple

let var_name

Declares a local variable, which will be undefined until it is assigned:

let x
 
if y:
    x = f()
else:
    x = g()
 
println(x)

Accessing an undefined variable is an error.

simple

lvalue=exprrhs

Assigns the value of ⟨exprrhs⟩ to an ⟨lvalue⟩. The assigned ⟨lvalue⟩ can be in one of three forms:

This method assigns all three kinds of l-value:

def insert!(self, key, value):
    let index = self._bucket_index_(key)
    let current = self._buckets[index]
    while cons?(current):
        if key == current.first.key:
            # struct assignment:
            current.first.value = value
            return
        # variable assignment:
        current = current.rest
    # vector assignment:
    self._buckets[index] = cons(sc_entry(key, value), self._buckets[index])

compound

def fun_name(var_name1, ... var_namek): ⟨block

Defines fun_name to be a function with formal parameters var_name1, ..., var_namek and with body ⟨block⟩.

For example,

def fact(n):
    if n < 2:
        return 1
    else:
        return n * fact(n - 1)

A function may have zero arguments, as in greet:

def greet(): println("Hello, world!")

The body of a function is defined to be a ⟨block⟩, which means it can be an indented sequence of ⟨statement⟩s, or a single ⟨simple⟩ statement on the same line as the def.

Note that defs can be nested:

# rbt_insert! : X RbTreeOf[X] -> Void
def rbt_insert!(key, tree):
    # parent : RbLinkOf[X] -> RbLinkOf[X]
    def parent(link):
        link.parent if rbn?(link) else False
 
    # grandparent : RbLinkOf[X] -> RbLinkOf[X]
    def grandparent(link):
        parent(parent(link))
 
    # sibling : RbLinkOf[X] -> RbLinkOf[X]
    def sibling(link):
        let p = parent(link)
        if rbn?(p):
            if link is p.left: p.right
            else: p.left
        else: False
 
    # aunt : RbLinkOf[X] -> RbLinkOf[X]
    def aunt(link):
        sibling(parent(link))
 
    # . . .
 
    def set_root!(new_node): tree.root = new_node
    search!(tree.root, set_root!)

3.2 Loop and control forms

simple

pass

Does nothing.

# account_credit! : num? account? -> VoidC
# Adds the given amount to the given account’s balance.
def account_credit!(amount, account):
    pass
#   ^ FILL IN YOUR CODE HERE

compound

ifexprif⟩: ⟨blockif

{ elif exprelif⟩: blockelif }*

[ else: blockelse ]

The DSSL2 conditional statement contains an if, 0 or more elifs, and optionally an else for if none of the conditions holds.

First it evaluates the if condition ⟨exprif⟩. If non-false, it then evaluates block ⟨blockif⟩ and finishes. Otherwise, it evaluates each elif condition ⟨exprelif⟩ in turn; if each is false, it goes on to the next, but when one is non-false then it finishes with the corresponding ⟨blockelif⟩. Otherwise, if all of the conditions were false and the optional ⟨blockelse⟩ is included, it evaluates that.

For example, we can have an if with no elif or else parts:

if should_greet:
    greet()

The function greet() will be called if variable should_greet is non-false, and otherwise it will not.

Or we can have several elif parts:

def rebalance_left_(key, balance, left0, right):
    let left = left0.node
    if not left0.grew?:
        insert_result(node(key, balance, left, right), False)
    elif balance == 1:
        insert_result(node(key, 0, left, right), False)
    elif balance == 0:
        insert_result(node(key, -1, left, right), True)
    elif left.balance == -1:
        insert_result(node(left.key, 0, left.left,
                           node(key, 0, left,right, right)),
                      False)
    elif left.balance == 1:
        insert_result(node(left.right.key, 0,
                           node(left.key,
                                -1 if left.right.balance == 1 else 0,
                                left.left,
                                left.right.left),
                           node(key,
                                1 if left.right.balance == -1 else 0,
                                left.right.right,
                                right)),
                      False)
    else: error('Cannot happen')

compound

for var_name in ⟨expr⟩: ⟨block

Loops over the values of the given ⟨expr⟩, evaluating the ⟨block⟩ for each. The ⟨expr⟩ can evaluate to a vector, a string, or a natural number. If a vector, then this form iterates over the element values (not the indices) of the vector; if a string, this iterates over the characters; if a natural number n then it counts from 0 to n - 1.

for person in people_to_greet:
    println("Hello, %s!", person)

In this example hash function producer, the for loops over the characters in a string:

# make_sbox_hash : -> [str? -> nat?]
# Returns a new n-bit string hash function.
def make_sbox_hash(n):
    let sbox = [ random_bits(n) for _ in 256 ]
    def hash(input_string):
        let result = 0
        for c in input_string:
            let svalue = sbox[int(c) % 256]
            result = result ^ svalue
            result = (3 * result) % (2 ** n)
        return result
    hash

compound

for var_name1, var_name2 in ⟨expr⟩: ⟨block

Loops over the indices and values of the given ⟨expr⟩, evaluating the ⟨block⟩ for each. The ⟨expr⟩ can evaluate to a vector, a string, or a natural number. If a vector, then var_name1 takes on the indices of the vector while var_name2 takes on the values; if a string, then var_name1 takes on the indices of the characters while var_name2 takes on the characters; if a natural number then both variables count together.

for ix, person in people_to_greet:
    println("%p: Hello, %s!", ix, person)

compound

whileexpr⟩: ⟨block

Iterates the ⟨block⟩ while the ⟨expr⟩ evaluates to non-false. For example:

while not queue.empty?():
    explore(queue.dequeue())

Here’s a hash table lookup method that uses while, which it breaks out of using break:

def lookup(self, key):
    let bucket = self._find_bucket(key)
    let result = False
    while cons?(bucket):
        if key == bucket.first.key:
            result = bucket.first.value
            break
        bucket = bucket.rest
    return result

simple

break

When in a for or while loop, ends the (inner-most) loop immediately.

simple

continue

When in a for or while loop, ends the current iteration of the (inner-most) loop and begins the next iteration.

simple

expr

An expression, evaluated for both side effect and, if at the tail end of a function, its value.

For example, this function returns the size field of parameter tree if tree is a Node, and 0 otherwise:

# size : RndBstOf[X] -> nat?
def size(tree):
    if Node?(tree): tree.size
    else: 0

simple

returnexpr

Returns the value of the given ⟨expr⟩ from the inner-most function. Note that this is often optional, since the last expression in a function will be used as its return value.

That is, these are equivalent:

def inc(x): x + 1
def inc(x): return x + 1

In this method, the first return is necessary because it breaks out of the loop and exits the function; the second return is optional and could be omitted.

# : bloom-filter? str? -> bool?
def bloom_check?(self, s):
    for hash in self._hashes:
        let index = hash(s) % self._bv.len()
        if not self._bv[index]: return False
    return True

simple

return

Returns void from the current function.

3.3 Data and program structuring forms

compound

struct name:

    let field_name1

    ...

    let field_namek

Defines a new structure type struct_name with fields given by field_name1, ..., field_namek. For example, to define a struct posn with fields x and y, we write:

struct posn:
    let x
    let y

Then we can create a posn using struct construction syntax and select out the fields using dotted selection syntax:

let p = posn { x: 3, y: 4 }
def magnitude(q):
    sqrt(q.x * q.x + q.y * q.y)

It also possible to construct the struct by giving the fields in order using function syntax:

assert_eq magnitude(posn(3, 4)), 5

Another example:

# A RndBstOf[X] is one of:
# - False
# - Node(X, nat?, RndBstOf[X], RndBstOf[X])
struct Node:
    let key
    let size
    let left
    let right
 
# singleton : X -> RndBstOf[X]
def singleton(key):
    Node(key, 1, False, False)
 
# size : RndBstOf[X] -> nat?
def size(tree):
    tree.size if Node?(tree) else 0
 
# fix_size! : Node? -> Void
def fix_size!(node):
    node.size = 1 + size(node.left) + size(node.right)

compound

class name [ ( { interface_name },* ) ]

    let field_name1

    ...

    let field_namek

    def meth_name0(self0 { , param_name0 }*): ⟨block0

    ...

    def meth_namen(selfn { , param_namen }*): ⟨blockn

Defines a class named name with private fields field_name1 through field_namek, and methods meth_name0 through meth_namen. Defining a class defines both a constructor function name and a type predicate name?.

If optional interface_names are given, this form checks that the class implements those interfaces. See interface for more information on how interfaces work.

A class has zero or more fields, which cannot be accessed from outside the class. Fields may be accessed from methods via the “self” parameter, as explained below.

A class has one or more methods. Methods are public and can be accessed from outside the class, except for methods whose names begin with a single underscore, which are private. Each method takes a distinguished first parameter to refer to the instance of the object on which it was called (the “self” parameter, also known as the receiver), and zero or more other parameters. Inside a method, a field field_name may be accessed as self.field_name, where self is the name of that method’s self parameter. Other methods may also be called via the self parameter, and the self may be returned or passed to other functions or methods.

To call a method from either inside or outside the class, we use dot notation, writing the receiver, then the method name, and then the non-self parameters: object.meth_name(arg, ...).

Every class must have an “internal” constructor method named __init__, which takes a self parameter and any other values needed to initialize the class. The internal constructor method must initialize all the fields before it returns. Instances of a class may be constructed via the “external” constructor function, whose name is the same as the name of the class. It takes one fewer parameter than __init__, because it is not passed a self parameter. DSSL2 arranges to create the new object and pass it to __init__ for initialization.

Here is an example of a simple class with one field and four methods:

import cons
 
class Stack:
    let head
 
    def __init__(self):
        self.head = nil()
 
    def push(self, value):
        self.head = cons(value, self.head)
 
    def pop(self):
        self._check_non_empty()
        let result = self.head.car
        self.head = self.head.cdr
        result
 
    # Private helper method for emptiness check:
    def _check_non_empty(self):
        if nil?(self.head): error('Stack.pop: empty')

Note that the internal constructor method __init__ takes only a self parameter, which means that the external constructor function Stack takes none. Thus, we can use the constructor to create a new, empty stack, and then we can access the stack via its push and pop methods:

let stack = Stack()
stack.push(4)
stack.push(5)
assert_eq stack.pop(), 5
assert_eq stack.pop(), 4
assert_error stack.pop()

As an example of a class with a non-trivial constructor, here is a 2-D position class that can change only in the y dimension:

class VerticalMovingPosn:
    let x
    let y
 
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def get_x(self): self.x
 
    def get_y(self): self.y
 
    def set_y!(self, y): self.y = y

We can create a VerticalMovingPosn as follows:

let posn = VerticalMovingPosn(3, 4)
assert_eq posn.get_x(), 3
assert_eq posn.get_y(), 4
posn.set_y!(10)
assert_eq posn.get_x(), 3
assert_eq posn.get_y(), 10

Note that VerticalMovingPosn takes two parameters because __init__ takes three: the self parameter and two more.

compound

interface name:

    def meth_name1(self1 { , param_name1 }*

    ...

    def meth_namek(selfk { , param_namek }*)

Defines an interface named name with methods meth_name1 through meth_namek. Defining an interface binds three identifiers:

An interface specifies some number of methods, their names, and their arities (numbers of parameters). It can then be used to check that a class implements the interface, meaning that it provides methods with those names and arities.

For example, consider an interface for a simple container that supports adding and removing elements, and checking whether the container is empty or full:

interface CONTAINER:
    def empty?(self)
    def full?(self)
    def add(self, value)
    def remove(self)

The interface specifies a class with four methods:

(Note that the parameter names themselves don’t matter—all that matters is how many.)

We can implement the CONTAINER interface multiple ways. For example, here we consider two classes that do so.

First, the Cell class implements a container with room for one element, initially empty:

class Cell (CONTAINER):
    let _contents
    let _empty?
 
    def __init__(self):
        self._contents = False
        self._empty?   = True
 
    def empty?(self):
        self._empty?
 
    def full?(self):
        not self.empty?()
 
    def add(self, value):
        if self.full?(): error("Cell.add: full")
        self._contents = value
        self._empty? = False
 
    def remove(self):
        if self.empty?(): error("Cell.remove: empty")
        self._empty? = True
        self._contents

Second, the VecStack class implements a fixed-size stack using a vector:

class VecStack (CONTAINER):
    let _data
    let _len
 
    def __init__(self, capacity):
        self._data = [False; capacity]
        self._len  = 0
 
    def capacity(self):
        self._data.len()
 
    def len(self):
        self._len
 
    def empty?(self):
        self.len() == 0
 
    def full?(self):
        self.len() == self.capacity()
 
    def add(self, value):
        if self.full?(): error('VecStack.add: full')
        self._data[self._len] = value
        self._len = self._len + 1
 
    def remove(self):
        if self.empty?(): error('VecStack.remove: empty')
        size._len = self._len - 1
        self._data[self._len]

Both classes Cell and VecStack implement the methods of interface CONTAINER with the correct arities, so their definitions succeed. Notice that VecStack has additional methods not mentioned in the interface—this is okay! Because both classes Cell and VecStack implement CONTAINER, CONTAINER? will answer True for their instances.

Furthermore, instances of either class can be protected with the CONTAINER! interface contract, which disables methods that are not declared in CONTAINER.

If a class does not implement the methods of a declared interface, it is a static error. For example, consider this position class:

class Posn (CONTAINER):
    let _x
    let _y
 
    def __init__(self, x, y):
        self._x = x
        self._y = y
 
    def x(self): _x
    def y(self): _y

The definition of Posn is in error, because it does not implement the methods of CONTAINER.

simple

import mod_name

import mod_string

Imports the specified DSSL2 module. Modules may be from the standard library, in which case the unquoted mod_name is used, or from the current directory, in which case mod_string should be the name of the file as a string literal.

A DSSL2 module is a .rkt file starting with #lang dssl2 and consisting of a sequence of DSSL2 ⟨statement⟩s. All definitions not starting with a single underscore are public, and may be imported into another DSSL2 module. The import form may only be used at the top level of a module.

3.4 Testing and timing forms

simple

assertexpr

Asserts that the given ⟨expr⟩ evaluates to non-false. If the expression evaluates false, signals an error.

test "ScHash.member? finds 'hello'":
    let h = ScHash(10, make_sbox_hash())
    assert not h.member?('hello')
    h.insert!('hello', 5)
    assert h.member?('hello')

simple

assert_eqexpr1⟩, ⟨expr2

Asserts that the given ⟨expr⟩s evaluates to equal values, using == to perform the comparison. If they are not equal, signals an error.

test 'first_char_hasher':
    assert_eq first_char_hasher(''), 0
    assert_eq first_char_hasher('A'), 65
    assert_eq first_char_hasher('Apple'), 65
    assert_eq first_char_hasher('apple'), 97

simple

assert_errorexprfail⟩, ⟨exprstr

Asserts that the given ⟨exprfail⟩ errors, and that the error message contains the substring that results from evaluating ⟨exprstr⟩.

simple

assert_errorexpr

Asserts that the given ⟨expr⟩ errors without checking for a particular error.

compound

testexpr⟩: ⟨block

Runs the code in ⟨block⟩ as a test case named ⟨expr⟩ (which is optional). If an assertion fails or an error occurs in ⟨block⟩, the test case terminates, failure is reported, and the program continues after the block.

For example:

test "arithmetic":
    assert_eq 1 + 1, 2
    assert_eq 2 + 2, 4

A testblock⟩ can be used to perform just one check or a long sequence of preparation and checks:

test 'single-chaining hash table':
    let h = ScHash(10)
    assert not h.member?('hello')
 
    h.insert!('hello', 5)
    assert h.member?('hello')
    assert_eq h.lookup('hello'), 5
    assert not h.member?('goodbye')
    assert not h.member?('helo')
 
    h.insert!('helo', 4)
    assert_eq h.lookup('hello'), 5
    assert_eq h.lookup('helo'), 4
    assert not h.member?('hel')
 
    h.insert!('hello', 10)
    assert_eq h.lookup('hello'), 10
    assert_eq h.lookup('helo'), 4
    assert not h.member?('hel')
    assert_eq h.keys(h), cons('hello', cons('helo', nil()))

compound

timeexpr⟩: ⟨block

Times the execution of the ⟨block⟩, and then prints the results labeled with the result of ⟨expr⟩ (which isn’t timed, and which is optional).

For example, we can time how long it takes to create an array of 10,000,000 0s:

time '10,000,000 zeroes':
    [ 0; 10000000 ]

The result is printed as follows:

10,000,000 zeroes: cpu: 309 real: 792 gc: 238

This means it tooks 309 milliseconds of CPU time over 792 milliseconds of wall clock time, with 238 ms of CPU time spent on garbage collection.

4 Expression forms

4.1 Variable expressions

expr

var_name

The value of a variable, which must be a function parameter, bound with let, or defined with def. For example,

let x = 5
println('%p', x)

prints “5”.

Lexically, a variable is a letter or underscore, followed by zero or more letters, underscores, or digits, optionally ending in a question mark or exclamation point.

4.2 Literal expressions

expr

number

A numeric literal.

expr

string

A string literal.

expr

True

The true Boolean value.

expr

False

The false Boolean value, the only value that is not considered true.

4.3 Functions and application expressions

expr

expr0⟩(⟨expr1⟩, ..., ⟨exprk⟩)

Evaluates all the expressions; ⟨expr0⟩ must evaluate to a procedure. Then applies the result of ⟨expr0⟩ with the results of the other expressions as arguments.

For example,

fact(5)

calls the function fact with argument 5, and

ack(5 + 1, 5 + 2)

calls the function ack with arguments 6 and 7.

Note that method calls are just object method lookup combined with procedure applcation. That is, when you write

q.enqueue(5)

that means lookup the enqueue method in q, and then apply the result to 5.

expr

lambda var_name1, ..., var_namek: ⟨simple

λ var_name1, ..., var_namek: ⟨simple

Creates an anonymous function with parameters var_name1, ..., var_namek and body ⟨simple⟩. For example, the function to add twice its first argument to its second argument can be written

lambda x, y: 2 * x + y

4.4 Vectors and indexing expressions

expr

expr1⟩[⟨expr2⟩]

Expression ⟨expr1⟩ must evaluate to a vector or string o; ⟨expr2⟩ must evaluate to an integer n between 0 and o.len() - 1. Then this returns the nth element of vector o or the nth character of string o.

expr

[ ⟨expr1⟩, ..., ⟨exprk⟩ ]

Creates a new vector of length k whose values are the values of the expressions.

For example:

let v = [ 1, 2, 3, 4, 5 ]

expr

[ ⟨exprinit⟩; ⟨exprsize⟩ ]

Constructs a new vector whose length is the value of ⟨exprsize⟩, filled with the value of ⟨exprinit⟩. That is,

[ 0; 5 ]

means the same thing as

[ 0, 0, 0, 0, 0 ]

Note that ⟨exprinit⟩ is not re-evaluated to produce each element, so an expression like [[0; 5]; 5] produces a vector that contains the same vector five times, not five different subvectors.

expr

[ ⟨exprelem⟩ for var_name in ⟨expriter⟩ ]

[ ⟨exprelem⟩ for var_name1, var_name2 in ⟨expriter⟩ ]

Vector comprehensions: produces a vector of the values of ⟨exprelem⟩ while iterating the variable(s) over ⟨expriter⟩. In particular, ⟨expriter⟩ must be a vector v, a string s, or a natural number n; in which case the iterated-over values are the elements of v, the characters of s, or counting from 0 to n - 1, respectively. If one variable var_name is provided, it takes on those values. If two are provided, then var_name2 takes on those values, while var_name1 takes on the indices counting from 0 upward.

For example,

[ 10 * n for n in [ 5, 4, 3, 2, 1 ] ]

evaluates to

[ 50, 40, 30, 20, 10 ]

And

[ 10 * n + i for i, n in [ 5, 4, 3, 2, 1 ] ]

evaluates to

[ 50, 41, 32, 23, 14 ]

expr

[ ⟨exprelem⟩ for var_name in ⟨expriter⟩ if ⟨exprcond⟩ ]

[ ⟨exprelem⟩ for var_name1, var_name2 in ⟨expriter⟩ if ⟨exprcond⟩ ]

If the optional ⟨exprcond⟩ is provided, only elements for which ⟨exprcond⟩ is non-false are included. That is, the variable(s) take on each of their values, then ⟨exprcond⟩ is evaluated in the scope of the variable(s). If it’s non-false then ⟨exprelem⟩ is evaluated and included in the resulting vector.

For example,

[ 10 * n for n in [ 5, 4, 3, 2, 1 ] if odd?(n) ]

evaluates to

[ 50, 30, 10 ]

4.5 Structs and projection expressions

expr

expr⟩.prop_name

Expression ⟨expr⟩ must evaluate to struct value that has field prop_name or an object value that has method prop_name; then this expression evaluates to the value of that field of the struct or that method of the object.

expr

struct_name { field_name1: ⟨expr1⟩, ..., field_namek: ⟨exprk⟩ }

Constructs a struct with the given name and the values of the given expressions for its fields. The struct must have been declared with those fields using struct.

If a variable with the same name as a field is in scope, omitting the field value will use that variable:

struct Foo:
    let bar
    let baz
 
let bar = 4
let baz = 5
 
assert_eq Foo { bar, baz: 9 }, Foo(4, 9)

4.6 Operator expressions

Operators are described in order from tighest to loosest precedence.

expr

expr1**expr2

Raises the value of ⟨expr1⟩ to the power of the value of ⟨expr2⟩, both of which must be numbers.

The ** operator is right-associative.

expr

notexpr

~expr

-⟨expr

+⟨expr

Logical negation, bitwise negation, numerical negation, and numerical identity.

notexpr⟩ evaluates ⟨expr⟩, then returns True if the result was False, and False for any other result.

~expr⟩ requires that ⟨expr⟩ evalutes to an integer or Boolean; it flips every bit of the number, or negates the Boolean.

-expr⟩ and +expr⟩ require that ⟨expr⟩ evaluates to a number. Then - negates the number, and + returns it unchanged.

expr

expr1*expr2

expr1/expr2

expr1%expr2

Multiplies, divides, or modulos the values of the expressions, respectively.

expr

expr1+expr2

Addition:

Anything else is an error.

expr

expr1-expr2

Subtracts two numbers.

expr

expr1<<expr2

expr1>>expr2

Left and right bitwise shift.

expr

expr1&expr2

Bitwise and for integers; logical and for Booleans.

expr

expr1^expr2

Bitwise xor for integers; logical xor for Booleans.

expr

expr1\|expr2

Bitwise or for integers; logical or for Booleans. (Not written with the backslash.)

expr

expr1==expr2

expr1!=expr2

expr1isexpr2

expr1|is not|expr2

expr1<expr2

expr1<=expr2

expr1>expr2

expr1>=expr2

Operator == is structural equality (except for classes that override it), and != is its negation. Operator is is physical equality, and |is not| (not written with the vertical bars) is its negation. To understand the difference, suppose that we create two different vectors with the same contents. Those vectors are structurally equal but not physically equal.

Operators <, <=, >, and >= are the standard inequalities for numbers and characters, and compare strings in lexicographic order.

expr

expr1andexpr2

Short-circuiting logical and. First evaluates ⟨expr1⟩; if the result is False then the whole conjunction is False; otherwise, the result of the conjunction is the result of ⟨expr2⟩.

expr

expr1orexpr2

Short-circuiting logical or. First evaluates ⟨expr1⟩; if the result is non-false then the whole disjunction has that result; otherwise the result of the disjunction is the result of ⟨expr2⟩.

expr

exprthen⟩ if ⟨exprcond⟩ else ⟨exprelse

The ternary expression first evaluates the condition ⟨exprcond⟩. If non-false, evaluates ⟨exprthen⟩ for its value; otherwise, evaluates ⟨exprelse⟩ for its value.

For example:

def parent(link):
    link.parent if rbn?(link) else False

5 Built-in functions, classes, methods, and constants

5.1 Primitive classes

DSSL2 includes seven primitive classes for building up more complex data structures. The constructors and methods of these classes are documented in this subsection.

5.1.1 Class bool

The primitive class for Boolean values, True and False. The type predicate for class bool is bool?.

Booleans support logical binary operators & (and), \| (or, written without the backslash), and ^ (xor), and logical unary negation ~. They also support comparison with ==, <, <=, etc. False compares less than True.

procedure

bool(AnyC) -> bool?

bool() -> bool?

The constructor for class bool.

In its one-argument form, converts any type to bool. All values but False convert to True.

In its no-argument form, returns False.

5.1.2 Class char

The primitive class for representing a single character of text. The type predicate for class char is char?.

A character can be converted to its integer value with the int constructor. Characters can be compared with ==, <, <=, etc.

procedure

char(char) -> bool?

char(int?) -> bool?

char(str?) -> bool?

char() -> bool?

The constructor for class char.

Given a character, returns that character. Given an integer, returns the character corresponding to the Unicode code point, or errors if the integer is not a valid Unicode character. Given a one-character string, returns the character of the string; any longer or shorter string is an error.

5.1.3 Class int

The primitive class for representing integral quantities of unlimited size. The type predicate for class int is int?.

Integers support binary arithmethic operators + (addition), - (subtraction), * (multiplication), and / (integer division); when combined with an instance of class float, the result will also be a float. They also support unary + (identity) and - (negation).

They also support comparison with ==, <, <=, etc., and they can be compared against floats.

Integers support binary bitwise operators & (bitwise and), \| (bitwise or), and ^ (bitwise xor), and unary bitwise negation ~.

procedure

int(num?) -> int?

int(char?) -> int?

int(str?) -> int?

int(bool?) -> int?

int() -> int?

The constructor for class int.

method

«int».abs() -> int?

Returns the absolute value of the receiving integer.

method

«int».ceiling() -> int?

Returns the same integer.

method

«int».floor() -> int?

Returns the same integer.

method

«int».sqrt() -> float?

Returns the square root of the receiving integer, as a float.

5.1.4 Class float

The primitive class for representing approximations of real numbers (as 64-bit IEEE 754 numbers). The type predicate for class float is float?.

Floats support binary arithmethic operators + (addition), - (subtraction), * (multiplication), and / (division); when combined with an instance of class int, the result will also be a float. They also support unary + (identity) and - (negation).

They also support comparison with ==, <, <=, etc., and they can be compared against ints.

procedure

float(num?) -> float?

float(str?) -> float?

float(bool?) -> float?

float() -> float?

The constructor for class float.

Converts an exact integer to the nearest double-precision floating point value. If given a string, attempt to convert to a number, throwing an error if the conversion fails. Booleans True and False convert to 1.0 and 0.0, respectively.

Given no arguments, returns 0.0.

method

«float».abs() -> float?

Returns the absolute value of the receiving float.

method

«float».ceiling() -> int?

Returns smallest integer that is no less than the receiving float. That is, it rounds up to the nearest integer.

method

«float».floor() -> int?

Returns the largest integer that is no greater than the receiving float. That is, it rounds down to the nearest integer.

method

«float».sqrt() -> float?

Returns the square root of the receiving float.

5.1.5 Class proc

The primitive class for representing functions. The type predicate for class proc is proc?.

Procedures can be applied.

procedure

proc(proc?) -> proc?

proc() -> proc?

The constructor for class proc.

Given one procedure argument, returns it unchanged. Given no arguments, returns the identity function.

method

«proc».compose(proc?) -> proc?

Composes the receiving procedure with the parameter procedure. For example,

assert_eq (λ x: x + 1).compose(λ x: x * 2)(5), 11

method

«proc».vec_apply(vec?) -> AnyC

Applies the receiving procedure using the contents of the given vector as its arguments.

5.1.6 Class str

The primitive class for representing textual data. The type predicate for class str is str?.

A string can be indexed with square bracket notation, which returns an instance of class char. Strings may be concatenated with the + operator. Concatenating a string with a non-string using + converts the non-string to a string first.

procedure

str(str?) -> str?

str(AnyC) -> str?

str(len: nat?, c: char?) -> str?

str() -> str?

The constructor for class str.

method

«str».explode() -> VecC[char?]

Breaks the receiving string into a vector of its characters.

method

«str».format(AnyC, ...) -> str?

Formats the given arguments, treating the receiving string as a format string in the style of print.

For example,

assert_eq '%s or %p'.format('this', 'that'), "this or 'that'"

method

«str».len() -> nat?

Returns the length of the receiving string in characters.

5.1.7 Class vec

The primitive vector class, for representing sequence of values of fixed size. The type predicate for class vec is vec?.

A vector can be indexed and assigned with square bracket notation.

procedure

vec() -> vec?

vec(len: nat?) -> vec?

vec(len: nat?, init: FunC[nat?, AnyC]) -> vec?

The constructor for class vec.

method

«vec».filter(pred?: FunC[AnyC, AnyC]) -> vec?

Filters the given vector, by returning a vector of only the elements satisfying the given predicate pred?.

In particular, v.filter(pred?) is equivalent to [ x for x in v if pred?(x) ]

method

«vec».implode() -> vec?

If the receiver is a vector of characters, joins them into a string. (Otherwise, an error is reported.)

method

«vec».len() -> nat?

Returns the length of the vector.

method

«vec».map(f: FunC[AnyC, AnyC]) -> vec?

Maps a function over a vector, returning a new vector.

In particular, v.map(f) is equivalent to [ f(x) for x in v ]

5.2 Predicates

5.2.1 Basic type predicates

procedure

bool?(AnyC) -> bool?

Determines whether its argument is a Boolean, that is an instance of class bool.

procedure

char?(AnyC) -> bool?

Determines whether its argument is an instance of class char.

procedure

contract?(AnyC) -> bool?

Determines whether its argument is a contract. Contracts include many constants (numbers, strings, Booleans), single-argument functions (considered as predicates), and the results of contract combinators such as OrC and FunC.

See Contracts for more.

procedure

flat_contract?(AnyC) -> bool?

Determines whether its argument is a flat contract. Flat contracts are contracts that answer right away and return the protected value unchanged on success, rather than wrapping it. Flat contracts include constants (numbers, strings, Booleans), single-argument functions, and the results of contract combinators such as OrC and AndC applied to flat contracts. Non-flat contracts include the results of FunC and VecC.

See Contracts for more.

procedure

int?(AnyC) -> bool?

Determines whether its argument is an instance of class int.

procedure

float?(AnyC) -> bool?

Determines whether its argument is an instance of class float.

procedure

proc?(AnyC) -> bool?

Determines whether its argument is an instance of class proc.

procedure

str?(AnyC) -> bool?

Determines whether its argument is an instance of class str.

procedure

vec?(AnyC) -> bool?

Determines whether its argument is an instance of class vec.

5.2.2 Numeric predicates

procedure

num?(AnyC) -> bool?

Determines whether its argument is a number. This includes both class int and class float.

procedure

nat?(AnyC) -> bool?

Determines whether its argument is a non-negative integer.

procedure

zero?(AnyC) -> bool?

Determines whether its argument is a number equal to zero.

procedure

pos?(AnyC) -> bool?

Determines whether its argument is a number greater than zero.

procedure

neg?(AnyC) -> bool?

Determines whether its argument is a number less than zero.

procedure

even?(AnyC) -> bool?

Determines whether its argument is an even number.

procedure

odd?(AnyC) -> bool?

Determines whether its argument is an odd number.

procedure

nan?(AnyC) -> bool?

Determines whether its argument is the special class float not-a-number value. This is useful, since nan is not necessarily == to other instances of nan.

5.3 Comparision operations

procedure

cmp(AnyC, AnyC) -> OrC(int?, False)

Compares two values of any type. If the values are incomparable, returns False. Otherwise, returns an integer: less than 0 if the first argument is less, 0 if equal, or greater than 0 if the first argument is greater.

procedure

max(AnyC, AnyC, ...) -> AnyC

Returns the largest of the given arguments, using cmp to determine ordering. It is an error if the values are not comparable.

procedure

min(AnyC, AnyC, ...) -> AnyC

Returns the smallest of the given arguments, using cmp to determine ordering. It is an error if the values are not comparable.

5.4 Randomness operations

procedure

random() -> float?

random(limit: IntInC(1, 4294967087)) -> nat?

random(start: int?, limit: int?) -> nat?

When called with zero arguments, returns a random floating point number in the open interval (0.0, 1.0).

When called with one argument limit, returns a random integer from the closed interval [0, limit - 1].

When called with two arguments start and limit, returns a random integer from the closed interval [start, limit - 1]. The difference between the arguments can be no greater than 4294967087.

constant

RAND_MAX: nat?

Defined to be 4294967087, the largest parameter (or span) that can be passed to random.

procedure

random_bits(nat?) -> nat?

Returns a natural number consisting of the requested number of random bits. That is, given n, returns an integer in the closed interval [0, 2 ** n - 1]. This procedure may be slow, but it is not limited by RAND_MAX in the way that the random procedure is.

5.5 I/O Functions

procedure

print(str?, AnyC, ...) -> VoidC

The first argument is treated as a format string into which the remaining arguments are interpolated, and then the result is printed.

The format string is a string that contains a formatting code for each additional argument, as follows:

For example:

let a = 3
let b = 4
print("%p + %p = %p", a, b, a + b)

prints “3 + 4 = 7”.

procedure

println(str?, AnyC, ...) -> VoidC

println(AnyC, ...) -> VoidC

If the first argument is a string then println is like print, but adds a newline at the end.

If the first argument is a non-string or there are no arguments, then println prints all the arguments with commas in between and a newline after, as if formatted by "%p, …, %p\n".

If DSSL2 supported user-defined varargs functions, it might be defined as:

def println(*args):

    if args.len() == 0:

        print('\n')

    elif str?(args[0]):

        print(*args)

        print('\n')

    else:

        let fmt = ''

        for _ in args:

            fmt = '%p' if fmt == '' else fmt + ', %p'

        println(fmt, *args)

5.6 Other functions

procedure

error(str?, AnyC, ...) -> VoidC

error(AnyC, ...) -> VoidC

Terminates the program with an error message.

If a first argument is supplied and it is a string, then the error message will be produced by interpolating the remaining arguments into the string à la print.

If there are no arguments, or if the first argument is not a string, then it formats all the arguments with commas in between and a “call” to error around it. This ensure that all calls to error produce some kind of sensible output.

procedure

dir(AnyC) -> VecC[str?]

Given an object, returns a vector of the names of its methods. Given a struct, returns a vector of the names of its fields.

6 Contracts

The contract system helps guard parts of a program against each other by enforcing properties of function and method parameters and results, structure and class fields, and variables. In particular, contracts specify properties of values that are checked at various points in the program.

A contract may be flat, in which case it is checked immediately against a value. Or a contract may by higher-order, in which case it may have to wrap a value to perform further checking in the future.

A number of DSSL2 values may be used as contracts, including:

For example, to ensure that a function takes a string and returns a number or False, we could use the contract FunC[str?, OrC(num?, False)].

6.1 Contract syntax

compound

let var_name : ⟨ctc⟩ = ⟨expr

Binds variable var_name to the value of expression ⟨expr⟩, while applying the contract ⟨ctc⟩. Subsequent assignments to the variable also must satisfy the contract. For example:

let x : int? = 0

Note that the ⟨exprrhs⟩ is optional, and the contract will not be checked before the variable is assigned:

let x : int?
 
x = 5

compound

def namef(name1: ⟨ctc1⟩, ..., namek: ⟨ctck⟩) -> ⟨ctcres⟩: ⟨block

Defines function namef while specifying contract expressions ⟨ctc1⟩ through ⟨ctck⟩ for the parameters, and contract expression ⟨ctcres⟩ for the result. For example:

def pythag(x: num?, y: num?) -> num?:
    sqrt(x * x + y * y)

Each of the contract positions is optional, and if omitted defaults to AnyC.

Optionally, after namef and before the left parenthesis, ⟨opt_ctc_params⟩ may appear: one or more comma-separated names, enclosed in square brackets. These are optional contract parameters to the function, which can appear in the contracts on the rest of the parameters, the result, and anywhere in the body of the function.

For example, a vector mapping function might be defined with contract parameters and contracts on its parameters as follows:

def vec_map[T, U](f: FunC[T, U], v: VecC[T]) -> VecC[U]:
    [ f(e) for e in v ]

When calling vec_map, it’s possible to supply actual contracts for T and U in square brackets; or omitting the square brackets, the contracts both default to AnyC.

compound

struct name:

    let field_name1: ⟨ctc1

    ...

    let field_namek: ⟨ctck

Defines a structure name with the given contracts ⟨ctci⟩ applied to the fields field_namei. This means that the contracts will be applied both when constructing the structure and when mutating it. For example:

struct posn:
    let x: float?
    let y: float?

Now constructing a posn will require both parameters to satisfy the float? predicate, as will assigning to either field.

It’s possible to include contracts on some fields without including them on all, and the fields with omitted contracts default to AnyC.

compound

class name [ [ { ctc_param },* ] ] [ ( { interface_name },* ) ]:

    let field_name1: ⟨ctcfield_1

    ...

    let field_namek: ⟨ctcfield_k

    def meth_name0(self0 { , arg_name0: ctcarg_0 }*) -> ⟨ctcres_0⟩: ⟨block0

    ...

    def meth_namen(selfn { , arg_namen: ctcarg_n }*) -> ⟨ctcres_n⟩: ⟨blockn

Defines a class with contracts. See class for the basics of classes.

Contracts may be placed on:

Any contracts may be omitted, and default to AnyC. No contract may be placed on a method’s self parameter, as that parameter is already known to be an instance of the class.

If the class implements interfaces that have contracts, the interfaces’ contracts have no effect on the defined class.

A class may have some number of generic contract parameters, ctc_param. These can be used to parameterize a class over other contracts. When provided, they are in scope throughout the class. The external constructor receives the actual contracts for an instance of the class as optional, square bracket parameters, giving before the ordinary parameters that are passed to the internal constructor.

For example, we can define a generic position class:

class Posn[T]:
    let _x: T
    let _y: T
 
    def __init__(self, x: T, y: T):
        self._x = x
        self._y = y
 
    def x(self) -> T:
        self._x
 
    def y(self) -> T:
        self._y

Now it is possible to make a position with int? coordinates or a position with float? coordinates, by passing the coordinate contract in square brackets to the Posn constructor:

let p = Posn[int?](3, 4)
let q = Posn[float?](3.0, 4.0)

Specifying contract parameters is optional, and if omitted, they default to AnyC. So we can write

let r = Posn(3, 4.0)

to get a Posn[AnyC].

When a contract parameter is given, the Posn constructor and methods all check the given values against the given contract.

When a class has generic contract parameters, its predicate can also be instantiated with contracts, using square brackets:

assert Posn?[int?](p)
assert not Posn?[int?](q)
assert not Posn?[int?](r)
 
assert not Posn?[float?](p)
assert Posn?[float?](q)
assert not Posn?[float?](r)

If the predicate is not instantiated, it recognizes all objects of that class regardless of how their contract parameters are instantiated:

assert Posn?(p)
assert Posn?(q)
assert Posn?(r)

Note that a predicate not being instantated is different from instantiating it with AnyC:

assert not Posn?[AnyC](p)
assert not Posn?[AnyC](q)
assert Posn?[AnyC](r)

compound

interface name [ [ { ctc_param },* ] ]:

    def meth_name1(self1 { , arg_name1: ctcarg_1 }*) -> ⟨ctcres_1

    ...

    def meth_namek(selfn { , arg_namek: ctcarg_n }*) -> ⟨ctcres_k

Defines a interface with contracts. See interface for the basics of interfaces.

As with a class, contracts may be provided on method parameters (except for self) and results. The contracts have no effect when a class implements the interface, but do have an effect with the interface is used to protect an instance of a class that implements it.

Defining an interface name binds three identifiers: name, name?, and name!. The first of these is used in class definitions to refer to the interface; the second is the predicate, which recognizes instances of classes that implement the interface. The third is the interface contract, which can be used to protect instances of classes that implement the interface, to ensure that their usage is only via the interface.

When an interface contract protects an object, first it checks the class of the object. If the class is not declared to implement the interface, an error is signaled. If the class does implement the interface, then a protected object is created. The protected object is like the original object, except that only the methods of the interface are usable; all other methods will error, blaming the caller, if called. Furthermore, any contracts specified on methods in the interface are applied to those methods of the protected object. (Reprotecting a protected object with the same interface has no effect.)

Here is an example of an interface with one method and a class that implements it:

interface HAS_X:
    def get_x(self)
 
class Posn (HAS_X):
    let x
    let y
 
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def get_x(self): self.x
    def get_y(self): self.y

We might want to ensure that some client code uses an instance of Posn only according to the HAS_X interface, without accessing its other methods. We can use the HAS_X! interface contract to protect a Posn instance in exactly this way. First, we create an object and use it normally:

let original = Posn(3, 4)
 
assert_eq original.get_x(), 3
assert_eq original.get_y(), 4
 
assert HAS_X?(original)

Note that the interface predicate HAS_X? answers True for instances of classes that implement HAS_X.

We can protect the original object by applying the HAS_X! interface contract, as follows:

let protected: HAS_X! = original

Now, we can call protected.get_x() because interface HAS_X defines the get_x method. But we cannot call get_y on protected, because protecting it with HAS_X! makes all methods other than get_x raise an error:

assert_eq protected.get_x(), 3
assert_error protected.get_y()

We can still access get_y on original:

assert_eq original.get_x(), 3
assert_eq original.get_y(), 4

As another example of how interface contracts can protect objects against misuse, consider the following class Counter, which implements an interface STEPPABLE:

interface STEPPABLE:
    def step(self)
 
class Counter (STEPPABLE):
    let count
    def __init__(self, value: int?): self.count = value
    def get(self): self.count
    def step(self): self.count = self.count + 1

The STEPPABLE! interface contract can be placed on a parameter to a function to ensure that the function only uses the given object according to the STEPPABLE interface. For example, we know that this advance function can only use the step method to advance the Counter:

def advance(counter: STEPPABLE!, count: nat?):
    while count > 0:
        counter.step()
        count = count - 1

A version of the function that attempts to do addition will fail because the necessary methods aren’t usable when the object is protected:

def sneaky_advance(counter: STEPPABLE!, count: nat?):
    # Won't work because both .__init__ and .get are missing.
    counter.__init__(counter.get() + count)

Like classes, interfaces can have generic contract parameters ctc_param. When an interface has generic contract parameters, these parameters are available to the contracts in the body of the interface. The interface contract name! takes its contract parameters as optional square bracket parameters that default to AnyC.

For example, here is a generic interface for a queue:

interface QUEUE[T]:
    def empty(self) -> bool?
    def enqueue(self, value: T) -> VoidC
    def dequeue(self) -> OrC(False, T)

This interface definition binds three identifiers:

expr

expr0⟩[⟨expr1⟩, ..., ⟨exprk⟩]

Indexes or instantiates the result of ⟨expr0⟩.

If ⟨expr0⟩ evalutes to a vector or string, then k must equal 1, and this is an indexing expression.

If ⟨expr0⟩ is a generic function, class, or contract, then ⟨expr1⟩, ..., ⟨exprk⟩ are the parameters used to instantiate the generic function, class, or contract. For example, function contracts are created using FunC and square brackets:

FunC[int?, char?, str?]

Or here is an example of a generic pair class, which can be instantiated to particular contracts for its components using square brackets:

class Pair[T, U]:
    let _fst
    let _snd
 
    def __init__(self, fst: T, snd: U):
        self._fst = fst
        self._snd = snd
 
    def fst(self) -> T: self._fst
    def snd(self) -> U: self._snd
 
let p = Pair[int?, str?](5, 'six')

6.2 Contract combinators

constant

AnyC: contract?

A flat contract that accepts any value.

constant

VoidC: contract?

A flat contract that accepts the result of pass and other statements that return no value (such as assignment and loops). This is used as the result contract for functions and methods that do not return a value.

procedure

VecC[contract?]: contract?

Creates a contract that protects a vector to ensure that its elements satisfy the given contract.

For example:

let v: VecC[int?] = [2, 3, 4]

Note that vector contracts are checked lazily, when elements are indexed or assigned, rather than eagerly when first protected. So for example:

let v: VecC[int?] = [2, 3, 'four'] # okay, not checked yet
assert_eq v[1], 3                  # passes check
assert_error v[2]                  # fails check

Assigning a non-integer to an element of v is an error as well.

If the optional square bracket parameter is omitted, VecC just checks that the protected value is a vector.

procedure

FunC[contract?, ..., contract?]: contract?

Creates a function contract with the given arguments and result. The last argument is a contract applied to the result, and all the other arguments are contracts applied to the parameters.

If the optional square bracket parameters are omitted, the resulting contract checks for a procedure, but nothing further.

procedure

NotC(contract?) -> contract?

Creates a contract that inverts the sense of the given flat contract.

procedure

OrC(contract?, contract?, ...) -> contract?

Creates a contract that accepts a value if any of the arguments does. For the details of how this works for higher-order contracts, see racket:or/c.

procedure

AndC(contract?, contract?, ...) -> contract?

Creates a contract that accepts a value if all of the arguments do. For the details of how this works for higher-order contracts, see racket:and/c.

procedure

IntInC(low: OrC(int?, False), high: OrC(int?, False)) -> contract?

Constructs a contract that accepts integers in the closed interval [low, high]. If either end of the interval is False, that end of the interval is unchecked.

procedure

apply_contract(contract?, AnyC) -> AnyC

apply_contract(contract?, AnyC, pos: str?) -> AnyC

apply_contract(contract?, AnyC, pos: str?, neg: str?) -> AnyC

Applies a contract to a value, optionally specifying the parties.

You are unlikely to need to use this.