Announcements See web page for talk schedule Dire consequences if I don’t hear from you by Monday Schedule next week: • Monday – class as usual • Wednesday – class as usual • immediately after class – I go to Chicago for data mining conference, return Sunday (will be checking email) • Friday – class as usual: Les LaCroix from ITS will talk about scripting languages Scheme Lists Lists are a special form of SExpressions () represents the empty list (A) represents list contains A • (A) is really (A . ()) (A B) is really (A . (B . () ) ) • (picture on blackboard) Function Calls Function calls represented as lists • (A B C) means • evaluate A to a function, evaluate B and C as parameters Use the value returned by the call as the "meaning" of (A B C) Why does (car (1 2)) fail? • (1 2) looks like a function call, but 1 isn't a function. quote function says "don't evaluate" • (car (quote (1 2))) • shorthand: (car '(1 2)) User-defined functions The list (lambda (args) (body)) creates an anonymous function (lambda (x y) (+ x y)) ((lambda (x y) (+ x y)) 5 6) => 11 User-defined functions The scheme command define binds values and functions to symbols • (define pi 3.14159265) • (define add-two-nums (lambda (x y) (+ x y))) Abbreviated as (define add-two-nums (x y) (+ x y)) Functions in Scheme are first-class objects – treated just like any other data type Recursion Breaks a problem down into simpler or smaller problems Mentality: If trivial case then supply answer else supply part of answer combined with solution of smaller problem Example: nth function Example: nth function (define (nth input n) (if (= n 0) (car input) (nth (cdr input) (- n 1)))) Example: copy-list Example: copy-list (define (copy-list input) (cond ((= (length input) 0) ()) ((= (length input) 1) (list (car input))) (else (cons (car input) (copy-list (cdr input)))))) Let and side effects let is used to create local variables • example in DrScheme let is good for preventing functions from affecting the outside world A side effect is when a function changes either one if its parameters or a global variable Scheme uses the ! as a convention to indicate that a function changes an argument Subsets How can we define a Scheme function to create a subset? (subsets ‘(1 2 3)) => ( () (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)) Number of subsets of n+1 values is twice as many as subsets of n values If we have subsets of (1 2), get subsets of (1 2 3) by duplicating all subsets of (1 2) and adding 3 Subsets Define distrib function to add a new element to a list of lists (distrib ‘(() (1) (2) (1 2)) 3) => ( (3) (3 1) (3 2) (3 1 2)) (define (distrib L E) (if (null? L) () (cons (cons E (car L)) (distrib (cdr L) E)))) Then define an extend function to attach these two together: Subsets (define (extend L E) (append L (distrib L E))) Then defining the subsets code is easy: (define (subsets L) (if (null? L) (list ()) (extend (subsets (cdr L)) (car L)))) Accessing elements of a list (list-tail L k) • returns tail of a list after removing first k elements (list-ref L k) • pulls off the k-th element Both of these can be slow since lists are linked lists Still have not heard from a handful of people No language or date, but paired • Language but no date: • Kevin DeRonne Shaun Reynolds Ryan Wakeham Chris Ghere Steve Fritzdixon Looking for partner • Scott O’Reilly / Thorin Tatge No contact at all • • • • • Robin Smogor / Jenny Cooper Paired? Language? Date? • Mark Peralta / Chris Middleton Akira Matoba If you have not contacted me at all by the end of the day today (via email), drop a letter grade on the talk If you do not have a language and date scheduled before class on Wednesday, same penalty Vectors Better to use vectors if accessing multiple elements of a list: • (define x #(1 2.0 “three”)) • (vector-ref x 2) vector->list and list->vector convert back and forth “->” is Scheme convention for a conversion function Lookup tables Scheme function assoc does lookup in a list • (define my-list ‘( (a 10) (b 20) (c 30)) (assoc ‘b my-list) Can do it with non-atomic keys too • (define price-list ‘( ( (subaru forester) 21000) ( (toyota rav4) 23000) ( (honda cr-v) 21200) )) (assoc ‘(toyota rav4) price-list) Nasty Scheme functions set-car! set-cdr! examples Scoping Scheme has lexical scoping. Any variables which are non-local are bound to containing lambda parameters, let values, or globally defined values. Example: (define (f x) (lambda (y) (+ x y))) f takes one parameter, x. It returns a function of y. (f 10) => (lambda (y) (+ 10 y)) Scoping Unbound symbols are assumed to be globals Let is a good way to encapsulate internal variables (define cnt (let ( (I 0) ) (lambda () (set! I (+ I 1)) I))) Try it by executing the function (cnt) repeatedly Let bindings can be subtle Notice the difference in behavior between these two programs: (define cnt (let ( (I 0) ) (lambda () (set! I (+ I 1)) I))) (define cnt (lambda () (let ( (I 0) ) (set! I (+ I 1)) I))) Sharing vs. Copying If there were no side effects, would never need to copy an object – just copy pointers If there are side effects, sometimes need to copy entire objects (define A ‘(1 2)) (define B (cons A A)) B = ( (1 2) 1 2) show picture (set-car! (car B) 10) Copying Scheme objects (define (copy obj) (if (pair? obj) (cons (copy (car obj)) (copy (cdr obj))) obj)) Shallow & Deep Copying Shallow copy – just copies a reference Deep copy – copies the entire object In Java (similar to C++): • Object O1 = new Object(); • Object O2; • O2 = O1; // shallow copy Java has a clone operation: • O2 = O1.clone(); ... but anything referenced by the object is shallow copied (unless you overload clone) Equality Checking Pointer equivalence – do the two operands point to the same address? Structural equivalence – do the two operands point to identical structures, even if in different locations? Pointer equivalence is faster but may not be what you want • eqv? and eq? are pointer equivalence • equal? is structural equivalence equal? is usually what you want (but slower) Loops Look like recursion (let loop ((x 1) (sum 0)) if (<= x 10) (loop (+ x 1) (+ sum x)) sum)) Sums the values from 1 to 10 and displays it Similar to for (x=1; x <= 10; sum += x, x++){}; cout << sum; Control Flow in Scheme Scheme’s control flow is normally simple and recursive: • First argument is evaluated to get a function • Remaining arguments are evaluated to get actual parameters • Actual parameters are bound to function’s formal parameters • Function body is evaluated to obtain function call value Leads to deeply nested expression evaluation. Example: Multiply a list of integers (define (mult-list L) (if (null? L) 1 (* (car L) (mult-list (cdr L))))) The call (mult-list ‘(1 2 3 4 5)) expands to (* 1 (* 2 (* 3 (* 4 (* 5 1))))) Get clever: if a 0 appears anywhere in the list, the product must be 0. Improved multiply (define (mult-list L) (cond ((null? L) 1) ((= 0 (car L)) 0) (else (* (car L) (mult-list (cdr L))))))) Better than above: but still do lots of unnecessary multiplications (until you hit zero) Can we escape from a sequence of nested calls once we know they’re unnecessary? Exceptions C++ handles this problem with exceptions struct Node { int val; Node *next; } C++ Exceptions int mult (Node *L) { try { return multNode(L); } catch (int returnCode) { return returnCode; } int multNode(Node *L) { if (L == NULL) return 1; else if (L->val == 0) throw 0; else return L->val * multNode(L->next); } Scheme Continuations A continuation is a Scheme mechanism for storing what you should do with a return value. Two different styles • Implement your own • Built in Scheme mechanisms Scheme continuations http://www.cs.utexas.edu/users/wilson/schintro/ schintro_127.html#SEC171 http://www.cs.utexas.edu/users/wilson/schintro/ schintro_141.html#SEC264 In most languages, calling a function creates a stack frame that holds return address for call and variable bindings In Scheme, everything is stored in garbage collected heap Whenever you call a function, you get a pointer to the calling function: partial continuation (draw picture) Scheme continuations Scheme actually lets you manipulate these continuations. This is weird! Scheme function: • call-with-current-continuation • can be abbreviated as call/cc Call/cc is used to call another function, but it passes along the current continuation as an argument. Continuations example (define (resumable-fun) (display 1) (display (call/cc abortable-fun)) (display 2)) (define (abortable-fun escape-fun) (display ‘a) (if (bad-thing-happens) (escape-fun 0)) (display ‘b)) (resumable-fun) Continuations with multiply Problem: how to use call/cc with an argument? (define (mult-list L) (call/cc mult-list-main L)) ;; this is bad code – can’t take ;; a list Trick: have call/cc call an anonymous function (define (mult-list L) (call/cc (lambda (escape) (mult-list L escape))) Multiply with continuations (define (mult-list-main L escape) (cond ((null? L) 1) ((=0 (car L)) escape 0) (else (* (car L) (mult-list-main (cdr L) escape)))) (define (mult-list L) (call/cc (lambda (escape) (mult-list-main L escape))) Implement your own continuation ;; con has “to be done” multiplications (define (mult-list L con) (cond ((null? L) (con 1)) ((= 0 (car L) 0) (else (mult-list (cdr L) (lambda (n) (* n (con (car L))))))) To actually call the function: (define (id x) x) (mult-list ‘(1 2 3) id)

Descargar
# Function Calls - Carleton College