This is the archived Fall 2013 version of the course. For the most recent version, see http://rust-class.org.

Class 9: Multi-Tasking Map

PDF version of notes for printing

Action Items

PS2 is due Monday, September 30. The submission form for PS2 will be posted soon. As part of submitting PS2, you will schedule a short (10 minute) demo/review with one of the course staff. All team members are expected to participate in the demo, except in exceptional circumstances. At the demo, you should be prepared to show off your shell and will be asked to try some specific things in your shell and explain things about what happens, as well as answering questions about your design and implementation.

Submit your "guess" and justification to the how fast is my new MacBook poll in the Piazza forum before 11:59pm Monday.

Sequential Map

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,
            Some(ref node) => { Some(~Node{ head: f(node.head), tail: node.tail.mapr(f) }) },
        } 
    } 
}

You should understand everything in this code. If you don't feel comfortable with functions that take other functions as inputs or return new functions as results and recursive data structions and procedures on them, you should read John McCarthy's Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I) (Communications of the ACM, April 1960). If you prefer a more "colorful" presentation, I would recommend reading Chapter 4 and Chatper 5 from a highly-rated but lowly-ranked and rarely-used introductory computing textbook. You should be able to translate the program examples from the Scheme language used there into Rust.

Another interesting writing from John McCarthy is Progress and its Sustainability. Although, you might want to consider his predictive ability in light of this one also: Networks Considered Harmful for Electronic Mail (December 1989).

The reason why telefax will supplant email unless email is separated from special networks is that telefax works by using the existing telephone network directly. To become a telefax user, it is only necessary to buy a telefax machine for a price between $1,000 and $5,000 (depending on features) and to publicize one's fax number on stationery, on business cards and in telephone directories. Once this is done anyone in the world can communicate with you. No complicated network addresses and no politics to determine who is eligible to be on what network. Telefax is already much more widely used than email, and a Japanese industry estimate is that 5 percent of homes will have telefax by 1995 and 50 percent by 2010. This is with a $200 target price. ... More generally, suppose the same need can be met either by buying a product or subscribing to a service. If the costs are at all close, the people who sell the product win out over those selling the service. Why this is so I leave to psychologists, and experts in marketing, but I suppose it has to do with the fact that selling services requires continual selling to keep the customers, and this keeps the prices high. I hope my pessimism about institutions is unwarranted, but I remember a quotation from John von Neumann to some effect like expecting institutions to behave rationally is like expecting heat to flow from a cold place to a hot place.

Were institutions more rational than John McCarthy predicted, or is there some other reason why his prediction was so wrong?

Processes, Threads, and Tasks

What is difference between a process and thread?

Is a Rust task more like a process or a thread?

How can Rust tasks provide process-like memory isolation but without the expense of a traditional process?

Spawning Tasks

The spawn function takes in an owned function (which cannot capture any mutable, shared objects) and runs that function in a new thread:

    fn spawn(f: ~fn())

These two constructs are equivalent (the second is preferred for readability, but the first is better for understanding what you are doing):

spawn( | | {  
    println("Get back to work!"); 
});

do spawn {  
    println("Get back to work!”)");
}

Channels provide a way for spawned tasked to communicate back to their parent:

   let (port, chan) : (Port<int>, Chan<int>) = stream();
   let val = node.head;
   do spawn {
      chan.send(f(val));
   }
   let newval = port.recv();

The port.recv() call with block until a sent value (from chan.send(f.val)) arrives.

Multi-Tasked Mapping

listspawn.rs code

struct Node { head : int, tail : Option<~Node> }
type List = Option<~Node> ;

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

impl Map for List {
    fn mapr(&self, f: extern fn(int) -> int) -> List { 
         match(*self) {
            None => None,
            Some(ref node) => { 
                let (port, chan) : (Port<int>, Chan<int>) = stream();
                let val = node.head;
                do spawn {
                    let res = f(val);
                    chan.send(res);
                }
                let newtail = node.tail.mapr(f); // needs to move here!
                let newval = port.recv();
                Some(~Node{ head: newval, tail: newtail })
            }
        }
    }
}

fn collatz_steps(n: int) -> int {
    if n == 1 {
        0
    } else {
        1 + collatz_steps(if n % 2 == 0 { n / 2 } else { 3*n + 1 })
    }
}

fn find_collatz(k: int) -> int {
    // Returns the minimum value, n, with Collatz stopping time >= k.
    let mut n = 1;
    while collatz_steps(n) < k { n += 1; }
    n
}

Modern Processors

For a much more entertaining answer to the question of why the best laptop I could buy at Cavalier Computers yesterday only has four cores, read James Mickens' The Slow Winter (a hilarilous short essay, but with lots of big technical ideas in it)

Today, if a person uses a desktop or laptop, she is justifiably angry if she discovers that her machine is doing a non-trivial amount of work. If her hard disk is active for more than a second per hour, or if her CPU utilization goes above 4%, she either has a computer virus, or she made the disastrous decision to run a Java program. Either way, it's not your fault: you brought the fire down from Olympus, and the mortals do with it what they will. But now, all the easy giants were dead, and John was left to fight the ghosts that Schröinger had left behind. "John," you say as you pour some eggnog, "did I ever tell you how I implemented an out-of-order pipeline with David Hasselhoff and Hulk Hogan's moustache colorist?" You are suddenly aware that you left your poncho in the other room.


Class 8: Git Yer Pointers Here

PDF version of notes for printing

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.


Class 7: What the &~#@? (Pointers in Rust)


Pages

  • Challenges
  • Course Wrapup
  • Final Projects
  • Final Survey
  • Getting Started with Github
  • IRC
  • Problem Set 3 - Zhtta Server - Benchmarking
  • Project
  • Project Ideas
  • Problem Set 1 - zhttpto Web Server
  • Comments on PS1 Comments
  • Problem Set 1 Reference Solution
  • Problem Set 2 - The Good Auld Shell
  • Problem Set 3 - Zhtta Server
  • Page Removed
  • Schedule
  • Enrolling for Spring 2014
  • Syllabus
  • Using Materials
  • Using Rust for an Undergraduate OS Course
  • VirtualBox
  • Working on Github in cs4414