DSSL2: Data Structures Student Language

DSSL2 is a programming language for data structures students. It’s designed to be simple, providing only the basic elements needed to implement a variety of data structures.

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.