DSSL2: Data Structures Student Language

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:

• { x }* for repetition 0 or more times

• { x }+ for repetition 1 or more times

• { x },* for repetition 0 or more times with commas in between

• [ x ] for optional

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.

binops are, from tightest to loosest precedence:

• **,

• *, /, and %,

• + and -,

• >> and <<,

• &,

• ^,

• \| (not written with the backslash),

• ==, <, >, <=, >=, !=, is, and |is not| (not written with the vertical bars),

• and, and

• or.

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:

• Decimal integers: 0, 3, 18446744073709551617

• Hexadedecimal, octal, and binary integers: 0xFFFF00, 0o0177, 0b011010010

• Floating point: 3.5, 6.02E23, 1e-12, inf, nan

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:

• \a for ASCII alert (also \x07)

• \b for ASCII backspace (also \x08)

• \f for ASCII formfeed (also \x0C)

• \n for ASCII newline (also \x0A)

• \r for ASCII carriage return (also \x0D)

• \t for ASCII tab (also \x09)

• \v for ASCII vertical tab (also \x0B)

• \xhh in hex, for example \x0A is newline

• \ooo in octal, for example \011 is tab

• A backslash immediately followed by a newline causes both characters to be ignored, which provides a way to wrap long strings across lines.

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:

• 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] -> 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 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, 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 = 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 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 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:

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