CS 61A -- Week 10 Solutions LAB ASSIGNMENT: 3.12 append vs. append! exp1 is (b); exp2 is (b c d). Append (without the !) makes copies of the two pairs that are part of the list x. (You can tell because it uses cons, which is the constructor function that generates a brand new pair.) Append! does not invoke cons; it mutates the existing pairs to combine the two argument lists. 2. Set! vs. set-cdr! There are two ways to think about this, and you should understand both of them: The syntactic explanation -- SET! is a special form; its first argument must be a symbol, not a compound expression. So anything of the form (set! (...) ...) must be an error. The semantic explanation -- SET! and SET-CDR! are about two completely different purposes. SET! is about the bindings of variables in an environment. SET-CDR! is about pointers within pairs. SET! has nothing to do with pairs; SET-CDR! has nothing to do with variables. There is no situation in which they are interchangeable. (Note: The book says, correctly, that the two are *equivalent* in the sense that you can use one to implement the other. But what that means is that, for example, if we didn't have pairs in our language we could use the oop techniques we've learned, including local state variables bound in an environment, to simulate pairs. Conversely, we'll see in Chapter 4 that we can write a Scheme interpreter, including environments as an abstract data type, building them out of pairs. But given that we are using the regular Scheme's built-in pairs and built-in environments, those have nothing to do with each other.) 3a. Fill in the blanks. > (define list1 (list (list 'a) 'b)) list1 > (define list2 (list (list 'x) 'y)) list2 > (set-cdr! ____________ ______________) okay > (set-cdr! ____________ ______________) okay > list1 ((a x b) b) > list2 ((x b) y) The key point here is that if we're only allowed these two SET-CDR!s then we'd better modify list2 first, because the new value for list1 uses the sublist (x b) that we'll create for list2. So it's (set-cdr! (car list2) (cdr list1)) (set-cdr! (car list1) (car list2)) 3b. Now do (set-car! (cdr list1) (cadr list2)). Everything that used to be "b" is now "y" instead: > list1 ((a x y) y) > list2 ((x y) y) The reason is that there was only one appearance of the symbol B in the diagram, namely as the cadr of list1; every appearance of B in the printed representation of list1 or list2 came from pointers to the pair (cdr list1). The SET-CAR! only makes one change to one pair, but three different things point (directly or indirectly) to it. 3.13 make-cycle The diagram is +----------------+ | | V | ---> XX--->XX--->XX---+ | | | V V V a b c (last-pair z) will never return, because there is always a non-empty cdr to look at next. 3.14 Mystery procedure. This procedure is REVERSE!, that is to say, it reverses the list by mutation. After (define v (list 'a 'b 'c 'd)) (define w (mystery v)) the value of w is the list (d c b a); the value of v is the list (a) because v is still bound to the pair whose car is a. (The procedure does not change the cars of any pairs.) 5a. We want Scheme-2 to accept both the ordinary form (define x 3) and the procedure-abbreviation form (define (square x) (* x x)) The latter should be treated as if the user had typed (define square (lambda (x) (* x x))) The hint says we can use data abstraction to achieve this. Here is the existing code that handles DEFINE: (define (eval-2 exp env) (cond ... ((define-exp? exp) (put (cadr exp) (eval-2 (caddr exp) env) env) 'okay) ...)) We're going to use selectors for the pieces of the DEFINE expression: (define (eval-2 exp env) (cond ... ((define-exp? exp) (put (DEFINE-VARIABLE exp) (eval-2 (DEFINE-VALUE exp) env) env) 'okay) ...)) To get the original behavior we would define the selectors this way: (define define-variable cadr) (define define-value caddr) But instead we'll check to see if the cadr of the expression is a symbol (so we use the ordinary notation) or a list (abbreviating a procedure definition): (define (define-variable exp) (if (pair? (cadr exp)) (caadr exp) ;(define (XXXX params) body) (cadr exp))) (define (define-value exp) (if (pair? (cadr exp)) (cons 'lambda (cons (cdadr exp) ;params (cddr exp))) ;body (caddr exp))) Writing selectors like this is the sort of situation in which the compositions like CAADR are helpful. That particular one is (car (cadr exp)), which is the first element of the second element of the expression. (You should recognize CADR, CADDR, and CADDDR as selectors for the second, third, and fourth elements of a list.) The second element of the expression is a list such as (SQUARE X), so the car of that list is the variable name. Since DEFINE-VALUE is supposed to return an expression, we have to construct a LAMBDA expression, making explicit what this notation abbreviates. 5c. In a procedure call, parameters are processed from left to right, and PUT adds each parameter to the front of the environment. So they end up in reverse order. Similarly, top-level DEFINEs add things to the global environment in reverse order. So the sequence of expressions should be Scheme-2: (define b 2) Scheme-2: (define a 1) Scheme-2: ((lambda (c b) 'foo) 4 3) It doesn't matter what's in the body of the procedure, since we're interested in the environments rather than in the values returned. HOMEWORK: 3.16 incorrect count-pairs This procedure would work fine for any list structure that can be expressed as (quote ). It fails when there are two pointers to the same pair. (define a '(1 2 3)) (count-pairs a) --> 3 (define b (list 1 2 3)) (set-car! (cdr b) (cddr b)) (count-pairs b) --> 4 (define x (list 1)) (define y (cons x x)) (define c (cons y y)) (count-pairs c) --> 7 (define d (make-cycle (list 1 2 3))) (count-pairs d) --> infinite loop Note from example c that it's not necessary to use mutators to create a list structure for which this count-pairs fails, but it is necessary to have a name for a substructure so that you can make two pointers to it. The name needn't be global, though; I could have said this: (define c (let ((x (list 1))) (let ((y (cons x x))) (cons y y) ))) 3.17 correct count-pairs (define (count-pairs lst) (let ((pairlist '()) (count 0)) (define (mark-pair pair) (set! pairlist (cons pair pairlist)) (set! count (+ count 1))) (define (subcount pair) (cond ((not (pair? pair)) 'done) ((memq pair pairlist) 'done) (else (mark-pair pair) (subcount (car pair)) (subcount (cdr pair))))) (subcount lst) count)) The list structure in pairlist can get very complicated, especially if the original structure is complicated, but it doesn't matter. The cdrs of pairlist form a straightforward, non-circular list; the cars may point to anything, but we don't follow down the deep structure of the cars. We use memq, which sees if PAIR (a pair) is eq? (NOT equal?) to the car of some sublist of pairlist. Eq? doesn't care about the contents of a pair; it just looks to see if the two arguments are the very same pair--the same location in the computer's memory. [Non-experts can stop here and go on to the next problem. The following optional material is just for experts, for a deeper understanding.] It's not necessary to use local state and mutation. That just makes the problem easier. The reason is that a general list structure isn't a sequence; it's essentially a binary tree of pairs (with non-pairs as the leaves). So you have to have some way to have the pairs you encounter in the left branch still remembered as you traverse the right branch. The easiest way to do this is to remember all the pairs in a variable that's declared outside the SUBCOUNT procedure, so it's not local to a particular subtree. But another way to do it is to have a more complicated helper procedure that takes PAIRLIST as an argument, but also sequentializes the traversal by keeping a list of yet-unvisited nodes, sort of like the breadth-first tree traversal procedure (although this goes depth-first because TODO is a stack, not a queue): (define (count-pairs lst) (define (helper pair pairlist count todo) (if (or (not (pair? pair)) (memq pair pairlist)) ; New pair? (if (null? todo) ; No. More pairs? count ; No. Finished. (helper (car todo) pairlist count (cdr todo))) ; Yes, pop one. (helper (car pair) (cons pair pairlist) (+ count 1) ; Yes, count it, (cons (cdr pair) todo)))) ; do car, push cdr (helper lst '() 0 '())) As you're reading this code, keep in mind that all the calls to HELPER are tail calls, so this is an iterative process, unlike the solution using mutation, in which the call (SUBCOUNT (CAR PAIR)) isn't a tail call and so that solution generates a recursive process. And after you understand that version, try this one: (define (count-pairs lst) (define (helper pair pairlist count todo) (if (or (not (pair? pair)) (memq pair pairlist)) ; New pair? (todo pairlist count) ; No. Continue. (helper (car pair) (cons pair pairlist) (+ count 1) ; Yes, count it, (lambda (pairlist count) ; do car, push cdr (helper (cdr pair) pairlist count todo))))) (helper lst '() 0 (lambda (pairlist count) count))) Here, instead of being a list of waiting pairs, TODO is a procedure tha
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: module ranger.gui.widgets.browsercolumn</title>
</head><body bgcolor="#f0f0f8">

<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial">&nbsp;<br><big><big><strong><a href="ranger.html"><font color="#ffffff">ranger</font></a>.<a href="ranger.gui.html"><font color="#ffffff">gui</font></a>.<a href="ranger.gui.widgets.html"><font color="#ffffff">widgets</font></a>.browsercolumn</strong></big></big></font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/home/hut/ranger/ranger/gui/widgets/browsercolumn.py">/home/hut/ranger/ranger/gui/widgets/browsercolumn.py</a></font></td></tr></table>
    <p><tt>The&nbsp;<a href="#BrowserColumn">BrowserColumn</a>&nbsp;widget&nbsp;displays&nbsp;the&nbsp;contents&nbsp;of&nbsp;a&nbsp;directory&nbsp;or&nbsp;file.</tt></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#aa55cc">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Modules</strong></big></font></td></tr>
    
<tr><td bgcolor="#aa55cc"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><table width="100%" summary="list"><tr><td width="25%" valign=top><a href="re.html">re</a><br>
</td><td width="25%" valign=top></td><td width="25%" valign=top></td><td width="25%" valign=top></td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ee77aa">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
    
<tr><td bgcolor="#ee77aa"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><dl>
<dt><font face="helvetica, arial"><a href="ranger.gui.widgets.pager.html#Pager">ranger.gui.widgets.pager.Pager</a>(<a href="ranger.gui.widgets.html#Widget">ranger.gui.widgets.Widget</a>)
</font></dt><dd>
<dl>
<dt><font face="helvetica, arial"><a href="ranger.gui.widgets.browsercolumn.html#BrowserColumn">BrowserColumn</a>
</font></dt></dl>
</dd>
</dl>
 <p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#000000" face="helvetica, arial"><a name="BrowserColumn">class <strong>BrowserColumn</strong></a>(<a href="ranger.gui.widgets.pager.html#Pager">ranger.gui.widgets.pager.Pager</a>)</font></td></tr>
    
<tr><td bgcolor="#ffc8d8"><tt>&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><dl><dt>Method resolution order:</dt>
<dd><a href="ranger.gui.widgets.browsercolumn.html#BrowserColumn">BrowserColumn</a></dd>
<dd><a href="ranger.gui.widgets.pager.html#Pager">ranger.gui.widgets.pager.Pager</a></dd>
<dd><a href="ranger.gui.widgets.html#Widget">ranger.gui.widgets.Widget</a></dd>
<dd><a href="ranger.gui.displayable.html#Displayable">ranger.gui.displayable.Displayable</a></dd>
<dd><a href="ranger.shared.html#EnvironmentAware">ranger.shared.EnvironmentAware</a></dd>
<dd><a href="ranger.shared.html#FileManagerAware">ranger.shared.FileManagerAware</a></dd>
<dd><a href="ranger.shared.html#Awareness">ranger.shared.Awareness</a></