CSC151.01 2015S, Class 37: Trees ================================ * Continue Partners! _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Debrief from yesterday. * The `listp?` predicate. * How Scheme prints lists. * Drawing trees vs. drawing lists. * Lab. Preliminaries ------------- ### Admin * Lab 35 returned. ### Upcoming Work * Lab writeup (optional): Exercises 2 and 4a. * Reading for Wednesday: [Vectors](../readings/vectors-reading.html) * HW7 due tonight at 10:30 p.m. * Exam 3 available now, officially distributed tomorrow. ### Extra Credit Opportunities #### Academic * Joe Palca talk Tuesday at 7:30 p.m. in Sebring-Lewis. * Scholars Convocation Wednesday at noon: Alison Bechdel. * CS Extras Thursday: ??? * CS Table Friday: Design for User Empowerment #### Peer Support (Morning Section) * KY's radio show, "We Think We're Funny", 9-10pm Mondays. * Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m. * How an admitted student this coming Sunday night (or the following Sunday night)! Contact JMU for info. * ISO Show, Saturday night 7-9 pm at Harris. Many live performances. * Salsa Showcase Seventeenth #### Miscellaneous _Nothing at present_ ### Other Good Things (no extra credit) * Student research seminar this week. ### Questions Debrief from yesterday ---------------------- What should we take from yesterday's lab? * We build things with pairs. * Lists * As well as some weird things that aren't lists. * These are somewhat "dynamic" - You can always add something at the front with cons. * There is a close relationship between lists and pairs. * All NON-EMPTY lists are pairs * null is not a pair. * Not all pairs are lists * (cons 'a 'b) * For a pair to be a list, the cdr has to be a list. * We can provide unambiguous drawings of pair structures using a simple process. * For any cons, draw this pair thing with two boxes * When a parameter to cons is null, draw a slash * When a parameter to cons is not null, draw an arrow to that element * We can turn these drawings back into code. * A list with N elements has a "spine" of N pairs. * One box for each element in a list, the boxes are spread out in a line. Why are we studying this? * There is some value in understanding what a program or langauge does "behind the scenes". * Understanding the underlying representation can help you better explain some phenomena. * We will start building some pair structures that aren't lists, so you should know more about those structures. * Linked structures are a fundamental idea in CS. How Scheme prints lists ----------------------- We see our first pair Print a single quotation mark and an open paren Print the car Look at the remaining pairs Print a space Print the car When you hit null, print a close paren When you hit something other than null, print the profanity symbol (.) and the cdr (define print-something (lambda (thing) (cond [(pair? thing) (display "'(") (print-something (car thing)) (let kernel ([remaining (cdr thing)]) (cond [(null? remaining) (display ")")] [(pair? remaining) (display " ") (print-something (car remaining)) (kernel (cdr remaining)] Writing `listp?` ---------------- A list is a collection of values. In Scheme, we can build lists with pair structures. * cons a value onto the front of a list * build the empty list with null "A list is either `null` or `(cons VALUE LIST)`". (define listp? (lambda (val) (or ; is it null? (null? val) ; is it a pair whose cdr is a list (and (pair? val) (listp? (cdr val)))))) "Structural recursion" -> Recurse over the parts of a structure (e.g., built with pairs) Lab --- Writeup is cancelled.