Action Items

PS2 is due Monday, September 30. You should be at least up to Problem 4 by now.

Before Thursday's class, read either the paper or slides for MapReduce: Simplified Data Processing on Large Clusters (Jeffrey Dean and Sanjay Ghemawat, Symposium on Operating System Design and Implementation, December, 2004).

Links

Linux Foundation Annual Linux Development Report (16 September 2013) (To download the full PDF, you need to survive an intrusive web form, which seems odd from an organization who's goal is to promote openness on the web.)

Linux Kernel Swear Counts

Github is your resume
Github is my resume
StackOverflow: Top Rust Users; Top Java Users (Which list is easier to make?)

Lists in Rust

For this exercise, we'll implement a linked list data structure using Rust. (Note that the Rust library provides a vector type, so it is unlikely you would want to use this linked list code, but it is a worthwhile exercise to explore some issues in programming in Rust.)

Version 1: Automatically Managed

list.rs code

struct Node {
    head : int,
    tail : Option<@Node>
}

type List = Option<@Node> ;

impl ToStr for List {
    fn to_str(&self) -> ~str { 
        fn elements_to_str(n: @Node) -> ~str {
            match (n.tail) {
                None => fmt!("%?", n.head),
                Some(tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
            }
        }

        match(*self) {
            None => ~"Null",
            Some(n) => fmt!("[%s]", elements_to_str(n))
        }
    }
}

fn main() {
    let lst : List = Some(@Node{head: 1, tail: Some(@Node{head : 2, tail: Some(@Node{head: 3, tail: None})})});
    println(fmt!("%s", lst.to_str()));
}

Version 2: Mutable List with Mapping

listmap.rs code

struct Node {
    head : int,
    tail : Option<@mut Node>
}

type List = Option<@mut Node> ;

trait Map {
    fn mapr(&self, &fn(int) -> int);
}

trait Filter {
    fn filtr(&self, &fn(int) -> bool);
}

impl Map for List {
    fn mapr(&self, f: &fn(int) -> int) { // Thanks to dbaupp for figuring out why this breaks when called "map"!
        let mut current = *self;
        loop {
            match(current) {
                None => break,
                Some(node) => { node.head = f(node.head); current = node.tail },
            }
        }
    }
}

impl ToStr for List {
    fn to_str(&self) -> ~str { 
        fn elements_to_str(n: @mut Node) -> ~str {
            match (n.tail) {
                None => fmt!("%?", n.head),
                Some(tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
            }
        }

        match(*self) {
            None => ~"Null",
            Some(n) => fmt!("[%s]", elements_to_str(n))
        }
    }
}

fn main() {
    let lst : List = Some(@mut Node{head: 1, tail: Some(@mut Node{head : 2, tail: Some(@mut Node{head: 3, tail: None})})});
    println(lst.to_str());
    lst.mapr(|x: int| { x + 1 });
    println(lst.to_str());
    lst.mapr(|x: int| { x * x });
    println(lst.to_str());
    lst.mapr(|x: int| { if x % 2 == 0 { x } else { -x }});
    println(lst.to_str());
}

Exercise 1. Add an append(&self, List) method that appends two lists. (You should think carefully about what semantics append should have before implementing it.)

Exercise 2. Add an filtr(&self, &fn(int) -> bool) method that removes elements for which a predicate is not true from a list.

Version 3: Owned Nodes

listo.rs code

// listo.rs - Owned List

struct Node {
    head : int,
    tail : Option<~Node>
}

type List = Option<~Node> ;

trait Map {
    fn mapr(&self, &fn(int) -> int) -> List;
}

impl Map for List {
    fn mapr(&self, f: &fn(int) -> int) -> List { 
         match(*self) {
            None => None,
            // need the ref here to keep the matched variable type borrowed
            Some(ref node) => { Some(~Node{ head: f(node.head), tail: node.tail.mapr(f) }) },
        }
    }
}

impl ToStr for List {
    fn to_str(&self) -> ~str { 
        fn elements_to_str(n: &~Node) -> ~str {
            match (n.tail) {
                None => fmt!("%?", n.head),
                Some(ref tail) => fmt!("%?, %s", n.head, elements_to_str(tail))
            }
        }

        match(*self) {
            None => ~"Null",
            Some(ref n) => fmt!("[%s]", elements_to_str(n)) 
        }
    }
}

fn main() {
    let lst0 : List = Some(~Node{head: 1, tail: Some(~Node{head : 2, tail: Some(~Node{head: 3, tail: None})})});
    println(lst0.to_str());
    let lst1 = lst0.mapr(|x: int| { x + 1 });
    println(lst1.to_str());
    let lst2 = lst1.mapr(|x: int| { x * x });
    println(lst2.to_str());
    let lst3 = lst2.mapr(|x: int| { if x % 2 == 0 { x } else { -x }});
    println(lst3.to_str());
    println(lst0.to_str());
}

Exercise 3. Make a generic List where the element type is a type parameter and can be any type that implements ToStr.

Exercise 4. Evaluate the performance and usability tradeoffs for the different list implementations.