DSSL2:   Data Structures Student Language
1 Syntax of DSSL2
1.1 Compound statements and blocks
1.2 Formal Grammar
1.3 Lexical Syntax
1.3.1 Identifiers
1.3.2 Numeric Literals
1.3.3 String Literals
1.3.4 Comments
1.4 Statement Forms
assert
assert_  eq
assert_  error
break
continue
def
defstruct
=
if
elif
else
let
for
pass
return
test
time
while
1.5 Expression Forms
True
False
lambda
object
1.5.1 Operators
**
!
~
*
/
%
+
-
<<
>>
&
^
\|
==
!=
===
!==
<
<=
>
>=
and
or
2 Built-in functions and values
2.1 Type predicates
proc?
str?
char?
num?
int?
float?
vec?
bool?
contract?
2.2 Numeric operations
floor
ceiling
int
float
random
max
min
quotient
RAND_  MAX
random_  bits
remainder
sqrt
2.2.1 Predicates
zero?
positive?
negative?
even?
odd?
nan?
2.3 String operations
chr
explode
format
implode
ord
strlen
2.4 Vector operations
build_  vector
filter
len
map
2.5 I/  O Functions
print
println
2.6 Other functions
error
identity
3 Contracts
3.1 Contract syntax
3.2 Contract combinators
Any  C
Void  C
Or  C
And  C
Fun  C
New  Forall  C
New  Exists  C
Int  In  C
apply_  contract
6.12

DSSL2: Data Structures Student Language

Jesse A. Tov <[email protected]>

 #lang dssl2 package: dssl2

1 Syntax of DSSL2

1.1 Compound statements and blocks

DSSL2 uses alignment and indentation to delimit blocks. In particular, compound statements such as if-elif-else take blocks 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 typewriter, 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 [ , string_expr ]
  | break
  | continue
  | defstruct struct_name ( { field_name [ : contract_expr ] },* )
  | lvalue = expr
  | expr
  | let var_name [ : contract_expr ] [ = expr ]
  | pass
  | return [ expr ]
  | simple ; simple
     
  lvalue = var_name
  | struct_expr . field_name
  | vec_expr [ index_expr ]
     
  compound = def name ( name [ : ctc_expr ] , ... ) [ -> ctc_expr ] : block
  | if expr : block { elif expr : block }* [ else : block ]
  | for [ var_name , ] var_name in expr : block
  | test [ expr ] : block
  | time [ expr ] : block
  | while expr : block
     
  block = simple NEWLINE
  | NEWLINE INDENT { statement }⁺ DEDENT
     
  expr = lvalue
  | number
  | string
  | True
  | False
  | expr ( { expr },* )
  | lambda { var_name },* : simple
  | λ { var_name },* : simple
  | expr if expr else expr
  | struct_name { { field_name : expr },*  }
  | object struct_name { { field_name : expr },*  }
  | [ { expr },* ]
  | [ expr ; expr ]
  | [ expr for [ var_name , ] var_name in expr [ if expr ] ]
  | expr BINOP expr
  | UNOP expr

BINOPs are, from tightest to loosest precedence:

UNOPs are !, ~, +, -.

1.3 Lexical Syntax

1.3.1 Identifiers

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

1.3.2 Numeric Literals

Numeric literals include:

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

1.3.4 Comments

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

1.4 Statement Forms

simple

assert expr

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

test "sch_member? finds 'hello'":
    let h = sch_new_sbox(10)
    assert !sch_member?(h, 'hello')
    sch_insert!(h, 'hello', 5)
    assert sch_member?(h, 'hello')

simple

assert_eq expr₁, expr

Asserts that the given exprs evaluates to structurally equal values. 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_error expr, string_expr

Asserts that the given expr errors, and that the error message contains the substring that results from evaluating string_expr.

simple

assert_error expr

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

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.

compound

def fun_name(var_name₁, ... var_namek): block

Defines fun_name to be a function with formal parameters var_name₁, ..., 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 statements, 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 === 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!)

simple

defstruct struct_name(field_name₁, ..., field_namek)

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

defstruct posn(x, 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])
defstruct Node(key, size, left, 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)

simple

lvalue = expr

Assignment. The assigned lvalue can be in one of three forms:

This function assigns all three kinds of l-value:

def sch_insert!(hash, key, value):
    let index = sch_bucket_index_(hash, key)
    let current = hash.buckets[index]
    while cons?(current):
        if key == current.first.key:
            # struct assignment:
            current.first.value = value
            return
        # variable assignment:
        current = current.rest
    # vector assignment:
    hash.buckets[index] = cons(sc_entry(key, value), hash.buckets[index])

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

compound

if exprif: blockif elif expri: blocki 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 expri in turn; if each is false, it goes on to the next, but when one is non-false then it finishes with the corresponding blocki. Otherwise, if all of the conditions were false and the optional blockelse is included, 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 true, and otherwise it will not.

Or we can have several elif parts:

def rebalance_left_(key, balance, left0, right):
    let left = left0.node
    if !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')

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.

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 values (not the indices) of the vector; if a string, this iterates over the characters as 1-character strings; if a natural number n then it counts from 0 to n - 1.

for person in people_to_greet:
    println("Hello, ~a!", 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[ord(c) % 256]
            result = result ^ svalue
            result = (3 * result) % (2 ** n)
        return result
    hash

compound

for var_name₁, var_namein 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₁ takes on the indices of the vector while var₂ takes on the values; if a string, then var₁ takes on the indices of the characters while var₂ takes on the characters; if a natural number then both variables count together.

for ix, person in people_to_greet:
    println("~e: Hello, ~a!", ix, person)

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

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 function, 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?(b, s):
    for hash in b.hashes:
        let index = hash(s) % b.bv.size
        if !bv_ref(b.bv, index): return False
    return True

simple

return

Returns void from the current function.

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_eq 1 + 1, 2
    assert_eq 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 = sch_new_1(10)
    assert !sch_member?(h, 'hello')
 
    sch_insert!(h, 'hello', 5)
    assert sch_member?(h, 'hello')
    assert_eq sch_lookup(h, 'hello'), 5
    assert !sch_member?(h, 'goodbye')
    assert !sch_member?(h, 'helo')
 
    sch_insert!(h, 'helo', 4)
    assert_eq sch_lookup(h, 'hello'), 5
    assert_eq sch_lookup(h, 'helo'), 4
    assert !sch_member?(h, 'hel')
 
    sch_insert!(h, 'hello', 10)
    assert_eq sch_lookup(h, 'hello'), 10
    assert_eq sch_lookup(h, 'helo'), 4
    assert !sch_member?(h, 'hel')
    assert_eq sch_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:

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.

compound

while expr: block

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

while !is_empty(queue):
    explore(dequeue(queue))

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

def sch_lookup(hash, key):
    let bucket = sch_bucket_(hash, key)
    let result = False
    while cons?(bucket):
        if key == bucket.first.key:
            result = bucket.first.value
            break
        bucket = bucket.rest
    return result

1.5 Expression Forms

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

expr

struct_expr.field_name

Expression expr must evaluate to struct value that has field fieldname; then this expression evaluates to the value of that field of the struct.

expr

vec_expr[index_expr]

Expression vec_expr must evaluate to a vector v; index_expr must evaluate to an integer n between 0 and len(v) - 1. Then this returns the nth element of vector v.

expr

True

The true Boolean value.

expr

False

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

expr

expr0(expr₁, ..., exprk)

Evaluates all the expressions; 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.

expr

lambda var_name₁, ..., var_namek: simple

λ var_name₁, ..., var_namek: simple

Creates an anonymous function with parameters var_name₁, ..., 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

expr

true_expr if cond_expr else false_expr

The ternary expression first evaluates the condition cond_expr. If non-false, evaluates true_expr for its value; otherwise, evaluates false_expr for its value.

For example:

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

expr

struct_name { field_name₁: expr₁, ..., 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 defstruct.

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

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

expr

object struct_name { field_name₁: expr₁, ..., field_namek: exprk }

Creates a struct value without declaring the struct type with defstruct. In particular, creates a struct with the given name struct_name and the given fields and values, regardless of what structs might be declared. The field names cannot have any repeats.

This is useful for one-off objects. For example, a simple 2-D point object might be defined as:

def Posn(x_, y_):
    def get_x(): x_
    def get_y(): y_
    def fmt(): format("(~e, ~e)", x_, y_)
    object Posn { get_x: get_x, get_y: get_y, fmt: fmt, }

expr

[ expr0, ..., exprk - 1 ]

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

[ init_expr; size_expr ]

Constructs a new vector whose length is the value of size_expr, filled with the value of init_expr. That is,

[ 0; 5 ]

means the same thing as

[ 0, 0, 0, 0, 0 ]

expr

[ elem_expr for var_name in iter_expr ]

[ elem_expr for var_name₁, var_namein iter_expr ]

Vector comprehensions: produces a vector of the values of elem_expr while iterating the variable(s) over iter_expr. In particular, iter_expr 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 1-character strings comprising 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_name₂ takes on those values, while var_name₁ 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

[ elem_expr for var_name in iter_expr if cond_expr ]

[ elem_expr for var_name₁, var_namein iter_expr if cond_expr ]

If the optional cond_expr is provided, only elements for which cond_expr is non-false are included. That is, the variable(s) take on each of their values, then cond_expr is evaluated in the scope of the variable(s). If it’s non-false then elem_expr 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 ]
1.5.1 Operators

Operators are described in order from tighest to loosest precedence.

expr

expr** expr

Raises the value of expr₁ to the power of the value of expr₂, both of which must be numbers.

The ** operator is right-associative.

expr

!expr

~expr

-expr

+expr

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

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

~expr, -expr, and +expr require that expr evaluate to a number. Then ~ flips every bit, - negates it, and + returns it unchanged.

expr

expr* expr

expr/ expr

expr% expr

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

expr

expr+ expr

Addition:

Anything else is an error.

expr

expr- expr

Subtracts two numbers.

expr

expr<< expr

expr>> expr

Left and right bitwise shift.

expr

expr& expr

Bitwise and.

expr

expr^ expr

Bitwise xor.

expr

expr\| expr

Bitwise or. (Not written with the backslash.)

expr

expr== expr

expr!= expr

expr=== expr

expr!== expr

expr< expr

expr<= expr

expr> expr

expr>= expr

Operator == is structural equality, and != is its negation. Operator === is physical equality, and !== 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 compare pairs of strings in lexicographic order.

expr

exprand expr

Short-circuiting logical and. First evaluates expr₁; if the result is False then the whole conjunction is False; otherwise, the result of the conjunction is the result of expr₂.

expr

expror expr

Short-circuiting logical or. First evaluates expr₁; if the result is non-false then the whole disjunction has that result; otherwise the result of the conjunction is the result of expr₂.

2 Built-in functions and values

2.1 Type predicates

procedure

proc?(AnyC) -> bool?

Determines whether its argument is a procedure (function).

procedure

str?(AnyC) -> bool?

Determines whether its argument is a string.

procedure

char?(AnyC) -> bool?

Determines whether its argument is a string of length 1.

procedure

num?(AnyC) -> bool?

Determines whether its argument is a number.

procedure

int?(AnyC) -> bool?

Determines whether its argument is an integer.

procedure

float?(AnyC) -> bool?

Determines whether its argument is a floating-point number.

procedure

vec?(AnyC) -> bool?

Determines whether its argument is a vector.

procedure

bool?(AnyC) -> bool?

Determines whether its argument is a bool?.

procedure

contract?(AnyC) -> bool?

Determines whether its value 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.

2.2 Numeric operations

procedure

floor(num?) -> int?

Rounds a number down to the largest integer that is no greater.

procedure

ceiling(num?) -> int?

Rounds a number up to the smallest integer that is no less.

procedure

int(num?) -> int?

int(str?) -> int?

int(bool?) -> int?

Returns the integer part of a number, by truncation. That is, the decimal point and everything after it is removed. If given a string, attempt to convert to a number before truncating, throwing an error if the conversion fails. Booleans True and False convert to 1 and 0, respectively.

procedure

float(num?) -> float?

float(str?) -> float?

float(bool?) -> 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.

procedure

random() -> float?

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

random(int?, 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 exact integer from the closed interval [0, limit - 1].

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

procedure

max(num?, num?, ...) -> num?

Returns the largest of the given numbers.

procedure

min(num?, num?, ...) -> num?

Returns the smallest of the given numbers.

procedure

quotient(nat?, nat?) -> nat?

Returns the truncated quotient.

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 number consisting of the requested number of random bits.

procedure

remainder(nat?, nat?) -> nat?

Returns the remainder of the truncated quotient.

procedure

sqrt(num?) -> float?

Computes the square root of a number.

2.2.1 Predicates

procedure

zero?(num?) -> bool?

Determines whether its argument is zero.

procedure

positive?(num?) -> bool?

Determines whether its argument is greater than zero.

procedure

negative?(num?) -> bool?

Determines whether its argument is less than zero.

procedure

even?(int?) -> bool?

Determines whether its argument is an even integer.

procedure

odd?(int?) -> bool?

Determines whether its argument is an odd integer.

procedure

nan?(num?) -> bool?

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

2.3 String operations

procedure

chr(nat?) -> str?

Converts the code point of a character to the character that it represents, as a one-character string. Inverse to ord.

assert_eq chr(97), 'a'

procedure

explode(str?) -> VectorOf[str?]

Breaks a string into a vector of 1-character strings.

procedure

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

Using its first argument as a template, interpolates the remaining arguments, producing a string. The main recognized escape codes are ~e and ~a. The former, ~e, displays values the same way that they are displayed in the interactions window, including quotation marks around strings. The latter, ~a, can be used to display strings without quotation marks.

Additionally, ~n can be used to insert a newline, and ~~ inserts a literal ~.

procedure

implode(VectorOf[str?]) -> str?

Concatenates a vector of strings into a single string.

procedure

ord(str?) -> nat?

Converts a character, represented as a one-character string, to its code point. Inverse to chr.

assert_eq ord('a'), 97

procedure

strlen(str?) -> nat?

Returns the length of a string in characters.

2.4 Vector operations

procedure

build_vector[X](n: nat?, f: FunC(nat?, X)) -> VectorOf[X]

Creates a vector of size n whose elements are f(0), f(1), ..., f(n - 1). Equivalent to

[ f(x) for x in n ]

procedure

filter[X](pred: FunC(X, bool?), v: VectorOf[X]) -> VectorOf[X]

Returns a vector containing the elements of v for which pred returns non-false. Equivalent to

[ x for x in v if pred(x) ]

procedure

len[X](VectorOf[X]) -> nat?

Returns the length of a vector.

procedure

map[X, Y](f: FunC(X, Y), v: VectorOf[X]) -> VectorOf[X]

Returns a vector consisting of f applied to each element of v. Equivalent to

[ f(x) for x in v ]

2.5 I/O Functions

procedure

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

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

procedure

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

Like print, but adds a newline at the end.

2.6 Other functions

procedure

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

Terminates the program with an error message. The error message must be supplied as a format string followed by values to interpolate, in the style of format.

procedure

identity[X](X) -> X

The identity function, which just returns its argument.

3 Contracts

The contract system helps guard parts of a program against each other by enforcing properties of function parameters, structure fields, and variables. A number of DSSL2 values may be used as contracts, including:

3.1 Contract syntax

compound

def namef(name₁: expr₁, ... namek: exprk) -> exprr: block

Defines function namef while specifying contracts expr1 through exprk for the parameters, and contract exprr 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.

compound

let var_name : contract_expr = expr

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

let x : int? = 0

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

let x : int?
 
x = 5

simple

defstruct name(name1: expr1, ..., namek: exprk)

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

defstruct posn(x: float?, 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.

3.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).

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

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

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

procedure

NewForallC(str?) -> contract?

Creates a new, universal contract variable, useful in constructing parametric contracts.

procedure

NewExistsC(str?) -> contract?

Creates a new, existential contract variable, useful in constructing parametric contracts.

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[X](contract?, X) -> X

apply_contract[X](contract?, X, pos: str?) -> X

apply_contract[X](contract?, X, pos: str?, neg: str?) -> X

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