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:

• var_name assigns to a variable, which can be a let-defined variable or a function parameter.

• ⟨exprstruct⟩.field_name assigns to a structure field, where expression ⟨exprstruct⟩ must evaluate to a structure that has a field named field_name.

• ⟨exprvec⟩[⟨exprindex⟩] assigns to a vector element, where ⟨exprvec⟩ evaluates to the vector and ⟨exprindex⟩ evaluates to the index of the element.

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] -> None

def rbt_insert(key, tree):

# parent : RbLinkOf[X] -> RbLinkOf[X]

def parent(link):

link.parent if rbn?(link) else None

# 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: None

# 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; produces None.

# account_credit : num? account? -> NoneC

# Adds the given amount to the given account’s balance.

def account_credit(amount, account):

pass

#   ^ FILL IN YOUR CODE HERE

compound if ⟨exprif⟩: ⟨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 (any value but False or None), 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 while ⟨expr⟩: ⟨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 = None

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 return ⟨expr⟩

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 None 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 magnitude(posn(3, 4)) == 5

Another example:

# A RndBstOf[X] is one of:

# - None

# - 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, None, None)

# 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 stack.pop() == 5

assert 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 posn.get_x() == 3

assert posn.get_y() == 4

posn.set_y(10)

assert posn.get_x() == 3

assert 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:

• The interface name itself, name, which can be mentioned in a class to check the class against that interface.

• The interface predicate, name?, which checks for objects whose classes are declared to implement the interface.

• The interface contract, name!, which modifies a protected object to disable methods not present in the interface. See Contracts for more information on contracts.

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:

• empty?, taking no non-self arguments,

• full?, taking no non-self arguments,

• add, taking one non-self argument, and

• remove, taking no non-self arguments.

(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 = None

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 = [None; 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 assert ⟨expr⟩

Asserts that the given ⟨expr⟩ evaluates to a truthy value. If the expression evaluates False or None, 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')

test 'first_char_hasher works':

assert first_char_hasher('')      == 0

assert first_char_hasher('A')     == 65

assert first_char_hasher('Apple') == 65

assert first_char_hasher('apple') == 97

simple assert ⟨exprtest⟩, time < ⟨exprsec⟩

Asserts that ⟨exprtest⟩ evaluates to a truthy value in less than ⟨exprsec⟩ seconds.

simple assert_error ⟨exprfail⟩

assert_error ⟨exprfail⟩, ⟨exprstr⟩

assert_error ⟨exprfail⟩, time < ⟨exprsec⟩

assert_error ⟨exprfail⟩, ⟨exprstr⟩, time < ⟨exprsec⟩

Asserts that evaluating ⟨exprfail⟩ results in an error. If ⟨exprfail⟩ evaluates without producing an error, the assertion fails. Allows specifying an expected error message or timeout duration.

In the 2nd and 4th forms, expression ⟨exprstr⟩ must evaluate to a string, which must be a substring of the resulting error message for the assertion to succeed. (The 1st and 3rd forms do not specify an error message, so any error will cause the assertions to succeed.)

The 3rd and 4rd forms allow giving a timeout, in seconds, for evaluating ⟨exprfail⟩. Thus, expression ⟨exprsec⟩ must evaluate to a positive number.

compound test ⟨expr⟩: ⟨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 1 + 1 == 2

assert 2 + 2 == 4

A test ⟨block⟩ 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 h.lookup('hello') == 5

assert not h.member?('goodbye')

assert not h.member?('helo')

h.insert('helo', 4)

assert h.lookup('hello') == 5

assert h.lookup('helo') == 4

assert not h.member?('hel')

h.insert('hello', 10)

assert h.lookup('hello') == 10

assert h.lookup('helo') == 4

assert not h.member?('hel')

assert h.keys(h) == cons('hello', cons('helo', nil()))

compound time ⟨expr⟩: ⟨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:

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.