Assignment: references and the stack

Download this crate for the second homework assignment. It contains some tests, benchmarks, and function prototypes. Since we are still covering basic Rust concepts, we still focus on small and simple functions.

1 N-Grams

1.1 Extract n-grams

Implement the following function in src/ngrams.rs:

pub fn char_ngrams(seq: &[char], n_min: usize, n_max: usize) -> Vec<&[char]>

This function should return all character-ngrams from length n_min to length n_max from the sequence seq. For example, char_ngrams(&['h', 'e', 'l', 'l', 'o'], 2, 3) should extract all bigrams and trigrams from the character sequence hello.

In the implementation, use while loops for iteration and two slices to keep track of where you are in the sequence. You are not allowed:

let mut i = 0;
while i < seq.len() {
    // ...
    i += 1;
}

Hint: You can go throught an array element by element by repeatedly slicing using &seq[1..].

1.2 ngrams memory use

How much memory (in bytes) do you expect the Vec<[&char]> returned from char_ngrams to use given that m n-grams are returned? How much of this memory is allocated on the stack and how much on the heap (assuming that the returned Vec lives on the stack)?

2 Stack size

Write a small standalone program that prints (a close approximation of) the maximum stack size in kilobytes as its last output. Feel free to output junk before the last output 😀. The program should not rely on functions or commands that were designed to return the stack size (such as std::rt::util::min_stack or ulimit). Since this is a small program, you can compile it directly using the Rust compiler:

rustc -O stacksize.rs

Of course, you are free to create a binary crate as well with cargo new --bin stacksize.

Hint 1: If you are on a UNIX, you can compare the output of your program agains the maximum stack size reported by ulimit -s in the shell.

Hint 2: Use recursion to overflow the stack, keeping track of the depth of the recursion.

Hint 3: You can use an array to allocate a large amount of stack space. For example:

let x = [0u8; 1000];

allocates an array of 1000 u8s on the stack.

Hint 4: The compiler may optimize the array away if it is not used or only used in a trivial manner.

Submission

The tar.gz or zip file should be uploaded through this page. The deadline is May 8 at 13:00.