CS3: Introduction to Symbolic ProgrammingFall 2006 Nate [email protected] 14:ListsScheme vs. other programming languagesScheduleLecture: Lists, and introduce the big projectLab: Lists; start on the projectNov 20-2413Final Exam (Saturday, 9am-11am) 100 Lewis (Lewis?)Dec 16thLecture: Guest Lecture: what is CS at UCB?Lab: Finish up the Project CHECKOFF #3 – Tue/Wed Project Due on Fri (at midnight)Dec 4 – Dec 815Lecture: Lists, other languages Lab: Big Project CHECKOFF #1 – Tue/Wed CHECKOFF #2 – Thur/FriNov 27–Dec 114Project Check-offs•There are 3 checkoffsYou need to do them on time in order to get credit for the project3. Tell your TA which project you will do and who you will do it with 4. Show your TA that you have accomplished something. S/he will comment. 5. Show that you have most of the work done: your TA will run your code.ListsSentences(words) vs lists: constructorssentenceTakes a bunch of words and sentences and puts "them" in order in a new sentence.listTakes any number of elementsReturns the list with those elementsappendTakes two listsReturns a list with the element of each list put togetherconsTakes an element and a listReturns a list with the element at the front, and the list contents trailingcons is closely tied to recursion(define (sent-square-all sent) (if (empty? sent) '() (se (square (first sent)) (sent-square-all (bf sent)))))(ssa '(1 2 3))  (se 1 (se 4 (se 9 '())))(define (list-square-all lst) (if (null? lst) '() (cons (square (car lst)) (list-square-all (cdr lst)))))(lsa '(1 2 3))  (cons 1 (cons 4 (cons 9 '())))Sentences(words) vs lists: selectorsbutlast…last…butfirstReturns a sentence of everything but the first word (but, works on lists)cdr Returns a list of everything but the first element of the listfirstReturns the first word (although, works on non-words)carReturns the first element of the listSentences(words) vs lists: HOFAccumulateReturns the value of applying a function to successive pairs of the input sentence or wordreduceReturns the value of applying a function to successive pairs of the (single) input listkeepReturns a sentence or word where every element satisfies a predicatefilter Returns a list where every element satisfies a predicate. Takes a single list as inputeveryReturns a sentence where a func is applied to every element of an input sentence or word.mapReturns a list where a func is applied to every element of the input list. Can take multiple input lists.What goes in a list?•Answer: anything!•So, (word? x) (not (list? x))are not the same thing!A few other important topics re: lists2. map can take multiple arguments4. apply6. Association lists8. Generalized listsmap can take multiple list arguments(map + '(1 2 3) '(100 200 300))(101 202 303)The argument lists have to be the same length(define (palindrome? lst) (all-true? (map equal? lst (reverse lst))))(palindrome? '(a m a n a p l a n a c a n a l p a n a m a))  #tapply (not the same as accumulate!)•apply takes a function and a list, and calls the function with the elements of the list as its arguments:(apply + '(1 2 3))(apply cons '(joe '(bob))(apply day-span '((january 1) (december 31)))Association lists•Used to associate key-valu e pairs((i 1) (v 5) (x 10) (l 50) (c 100) (d 500) (m 1000)) •assoc looks up a key and returns a pair(assoc 'c '((i 1) (v 5) (x 10) … ) ) (c 100);; Write sale-price, which takes a list of items and a;; table of item-price pairs, and returns a total price(define *price-list* '((bread 2.89) (milk 2.33) (cheese 5.21) (chocolate .50) (beer 6.99) (tofu 1.67) (pasta .69)))(sale-price '(bread tofu) *price-list*)Generalized lists•Elements of a list can be anything, including any list•Lab materials discuss-flatten (3 ways)-completely-reverse-processing a tree-structured directoryHow about this flatten?(define (flatten thing) (if (list? thing) (reduce _______ (map flatten thing)) (______ thing)))Scheme versus other languagesFunctional Programming•In CS3, we have focused on programming without side-ef fec ts.-All that can matter with a procedure is what it returns-In other languages, you typically:-Perform several actions in a sequence-Set the value of a variable – and it stays that way-All of this is possible in Scheme; Chapter 20 is a good place to startThe language Scheme•Scheme allows you to ignore tedium and focus on core concepts-The core concepts are what we are teaching!•Other languages:-Generally imperative, sequential-Lots and lots of syntactic structure (built in commands)-Object-oriented is very "popular" nowCS3 concepts out in the world•Scheme/lisp does show up: scripting languages inside applications (emacs, autocad, Flash, etc.)•Scheme/Lisp is used as a "prototyping" language-to quickly create working solutions for brainstorming, testing, to fine tune in other languages, etc. •Recursion isn't used directly (often), but recursive ideas show up everywhereJava•Java is a very popular programming language-Designed for LARGE programs-Very nice tools for development-Gobs of libraries (previous solutions) to help solve problems that you might want solvedPHP•PHP-Popular language for web development (combined with a web-server and database)-Lots of features, but little overall "sense"-Because programs in PHP execute behind a web-server and create, on the fly, programs in other languages, debugging can be onerous.SQL resembles HOFs•SQL if for database retrieval•query: “Tell me the names of all the lecturers who have been at UCB longer than I have.” select name from lecturers where date_of_hire < (select date_of_hire from lecturers where name = 'titterton'); •query: “Tell me the names of all the faculty who are older than the faculty member who has been here the longest.” select L1.name from lecturers as L1 where L1.age > (select L2.age from lecturers as L2 where L2.date_of_hire = (select min(date_of_hire) from lecturers) );ProblemsCS3: Introduction to Symbolic ProgrammingFall 2006 Nate [email protected] 14:ListsScheme vs. other programming languages2 Spring 2006 CS3: 2 ScheduleLecture: Lists, and introduce the big projectLab: Lists; start on the projectNov 20-2413Final Exam (Saturday, 9am-11am) 100 Lewis (Lewis?)Dec 16thLecture: Guest Lecture: what is CS at UCB?Lab: Finish up the