Foundations of Computer Science Fall 2007 For today you should have: 1) (at least) ordered Sipser's book 2) read Louden, Programming Languages, Chapter 1, Sections 1.1 through 1.3 3) installed Dr. Scheme in the environment of your choice 4) run the Scheme examples from notes01 and gcd from Louden For next time: 1) do the exercises near the end of notes02. Bring a neatly printed hard copy of your working code. 2) prepare for a Scheme quiz 3) read Louden, Programming Languages, Chapter 1, Sections 1.4 through 1.6 and prepare to answer the questions below Reading questions ----------------- Louden, Programming Languages, Chapter 1, Sections 1.1 through 1.3 1) The first sentence of the chapter is a statement of what famous hypothesis in linguistics? 2) What are the elements of the von Neumann model of a computer? 3) What is Church's thesis? You might want to read the Wikipedia page, too. 4) Louden claims that one of the necessary features of a programming language is that it be machine-readable. Can you think of some limitations this requirement puts on programming languages? [For questions 5 and 6, don't worry about remembering the differences between these different kinds of abstraction. It's not super important.] 5) In the context of data, give an example of a basic abstraction, a structured abstraction and a unit abstraction. 6) In the context of control flow, give an example of a basic abstraction, a stuctured abstration and a unit abstration. 7) In Louden's vocabulary, what's the difference between a procedure and a function? [The paragraph in the middle of page 1-9 is important.] 8) What are the 3.5 programming paradigms? 9) What is the lambda calculus? 10) What does it mean to say that a language is Turing complete? 11) What is a _very_ high level language? More scheme ----------- The subset of the language you have learned is Turing complete, but it is not easy to see that yet. But if we add cond (or if), it becomes clearer. (define (myabs x) (cond ((< x 0) (- x)) ((= x 0) 0) ((> x 0) x))) (myabs -3) Many computations that would be expressed using iteration in an imperative paradigm are expressed using recursion in a functional paradigm: (define (factorial n) (cond ((< n 0) 'oops) ((= n 0) 1) (else (* n (factorial (- n 1)))))) (factorial 6) This has the apparent drawback of using stack space in proportion to n. In some cases this drawback can be mitigated by writing a version of the function that is 'tail-recursive': (define (tail-factorial n) (define (iter product counter) (cond ((> counter n) product) (else (iter (* product counter) (+ counter 1))))) (iter 1 1)) (tail-factorial 6) What is the defining characteristic of tail recursion? What optimization does tail recursion admit? What is the difference between a bound and unbound variable? Write a procedure called fib that takes a parameter n and returns the nth element of the Fibonacci sequence that begins F0 = 1, F1 = 1. Rewrite your function in tail recursive form :) (don't try too hard; this is an example of a tree-recursive computation) List processing --------------- If all of the elements of a list are available at once, you can assemble them into a list with a function called (drum roll, please) list! > (list 1 2 3) (1 2 3) The output format for lists is not a valid input format: > (1 2 3) . procedure application: expected procedure, given: 1; arguments were: 2 3 But if you quote it, all is well: > '(1 2 3) (1 2 3) Accessing the elements of a list is a special treat: (car t) returns the first element of list t (cdr t) returns a list of all-but-the-first elements of t Examples: > (define t (list 1 2 3)) > (car t) 1 > (cdr t) (2 3) Empty lists: (list) creates an empty list () also an empty list '() the most idiomatic way to create an empty list (null? t) returns #t if t is the empty list, #f otherwise > '() () > (null? '()) #t > (null? t) #f mnemonics --------- Some dialects of scheme provide more mnemonic names. You can define your own: (define (first t) (car t)) (define (rest t) (cdr t)) > (define t (list 1 2 3)) > (first t) 1 > (rest t) (2 3) Write a function, using these names, that takes a list of numbers and returns their sum: Now write a tail-recursive version: cons ---- If all of the elements of a list are available at the same time, you can use 'list to assemble them. But often you want to assemble a list a little bit at a time. cons takes two arguments and returns a pair, sometimes called a 2-tuple > (cons 1 2) (1 . 2) Again, the output format is not a legal input format: > (1 . 2) application: bad syntax (illegal use of `.') in: (1 . 2) Unless you quote it: > '(1 . 2) (1 . 2) first and rest (and car and cdr) work with pairs: > (define pair (cons 1 2)) > (first pair) 1 > (rest pair) 2 For pairs, left and right would be better names. In (1 . 2), both elements are integers. In general, you can build any data structure out of pairs. Draw box and pointer diagrams for the following expressions: (cons 1 2) (cons (cons 1 2) (cons 3 4)) (cons (cons 1 (cons 2 3)) 4) Probably the most common data structure is a linked list: A list can be 1) the empty list, '() OR 2) a pair whose first element is "cargo" and whose second element is a list. Draw a box and pointer diagram for a list with the cargo 1 2 3 4. Write an expression that builds this structure using cons. cons up a list -------------- The function pair? returns #t if the argument is a pair, #f otherwise. Write a function that takes a list as an argument and that builds a copy of the list (different list with the same cargo) Question: does your function make a shallow or deep copy? (Do we care?) What would a deep copy look like? What does it mean in this context? map --- Write a function that takes a list of integers and returns a list that contains the squares of the integers. Generalize your function so that it takes a function as its first argument and applies it to each element of the list. This function is sometimes called map, or more specifically mapcar. How might you generalize this function even more? filter ------ even? returns #t if its argument is an even number, #f otherwise. Write a function called select-evens that takes a list and returns a list that contains only the even elements. Generalize your function so that it takes a function as its first argument, applies the function to each element in the list, and returns a list of the elements that yield #t. reduce ------ Write a function that takes a list of integers and computes their product (using only binary multiplications). How would you generalize this function? higher-order functions ---------------------- map, filter and reduce are examples of higher-order functions; that is, functions that take functions as arguments. This sort of thing is very common in languages like Lisp and Python. It is less common in the C family languages, but can be implemented fairly easily with function pointers. The other feature of higher-order functions is that they often return functions. Easy in Lisp, etc. Hard in C family. Here's a contrived example: (define (incrementor n) (lambda (x) (+ x n))) And here's how you would use it: > (incrementor 1) # > ((incrementor 1) 2) 3 Notice that the anonymous function created by the lambda has a reference to n, which is defined in the enclosing scope. When this function is applied later, it needs to be able to refer to n. How do you think that works? Hint: wikipedia closure. list-tree ambiguity ------------------- What is the value of (cons (list 1 2) (list 3 4)) Draw a box and pointer diagram and then interpret it. You can think of a list of lists as a tree, but not necessarily the other way around. Exercises --------- Write a function called 'append that takes two lists and returns a new list that contains all the elements from the first list followed by all the elements of the second. Write a function called 'reverse that takes a list and returns a new list that contains the elements from the original list in reverse order. Write a function called 'deep-reverse that takes a list and returns a new list that contains the elements from the original list in reverse order. If any of the elements are lists, they should also be reversed, and so on. Write a function called 'leaves that takes a tree and returns list of the leaves (that is, all the elements that are not pairs). Reading questions ----------------- Louden, Programming Languages, Chapter 1, Sections 1.4 through 1.6 1) What is the difference between syntax and semantics? [Helpful Note: a grammar is a set of rules that describes a language, which is a set of strings (in the case of a programming language, it's the set of syntactically legal programs).] 2) Why is it hard to write language semantics in a natural language? What is the alternative? 3) What's the difference between an interpreter and a compiler? 4) What is a pseudointerpreter? 5) What are the usual stages of language translation? 6) Give an example of a static property of a program. Give and example of a dynamic property. 7) What does it mean to say that a language is "an interpreted language"? 8) What are the different kinds of errors? 9) What is a pragma? 10) What are some of the characteristics of a good programming language?