2-2-closure.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">

<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />

<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
  set_interpreter_path("web-worker-interpreter/");
  set_language("scheme");
</script>
<script src="js/footnotes.js"></script>

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>


<title> iSICP 2.2 - Hierarchical Data and the Closure Property </title>
<script type="text/javascript">

  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-36868476-1']);
  _gaq.push(['_trackPageview']);

  (function() {
    var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
    ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
  })();

</script>
</head>
<body>

<div id="sidebox">
  <div class="tab"></div>
  <div class="content">
    
    <p> 
    
    <a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
    <span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
    <span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
    
    <script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
    new JotformFeedback({
    formId:'40222623177447',
    base:'http://jotform.me/',
    windowTitle:'Notify Me',
    background:'#FFA500',
    fontColor:'#FFFFFF',
    type:false,
    height:500,
    width:700
    });
    </script>
    <a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>

    <p>
    
    <div id="currently-editing"> </div>


    <script>
    
    function hideAll() {
      $("#currently-editing").hide();
      $("#toc").hide();
    }
    
    $("#currently-editing-link").click(function() {
      hideAll();
      $("#currently-editing").show();
    });
    
    $("#toc-link").click(function() {
      hideAll();
      $("#toc").show();
    });
    
    </script>
    
    <div id="toc"> </div>
    
    <p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
    
    <script>
    hideAll();
    $("#toc").show();
    </script>
  
  </div>
</div>

<script> 
$('#sidebox .tab').toggle(function(){
    $('#sidebox').animate({'right':'0%'});
}, function(){
    $('#sidebox').animate({'right':'-30%'});
});

$(document).ready(createTOC);

</script>

<div id="main">

<a href='index.html' style="float:left"> <img src='images/chevron-up.svg' height=64 width=64> </a>
<span style="float:right">
<a href='2-1-data.html'> <img src='images/chevron-left.svg' height=64 width=64> </a>
<a href='2-3-symbolic.html'> <img src='images/chevron-right.svg' height=64 width=64> </a>
</span>

<br> <br>

<div id="scheme-define-square">
(define (square x)
  (* x x))
</div>
<script>
hidden_prompt("scheme-define-square");
</script>

<h2> Hierarchical Data and the Closure Property </h2> 

<p> As we have seen, pairs provide a primitive ``glue'' that we can use to construct compound data objects. Figure 2-2 shows a standard way to visualize a pair---in this case, the pair formed by <tt>(cons 1 2)</tt>. In this representation, which is called <tt>box-and-pointer notation</tt>  , each object is shown as a <tt>pointer</tt>  to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a numeral. The box for a pair is actually a double box, the left part containing (a pointer to) the <tt>car</tt> of the pair and the right part containing the <tt>cdr</tt>.

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-11.gif'>

<p style="text-align:center"> <b> Figure 2.2: </b> Box-and-pointer representation of <tt>(cons 1 2)</tt>.

<p> We have already seen that <tt>cons</tt> can be used to combine not only numbers but pairs as well. (You made use of this fact, or should have, in doing Exercise 2-2 and Exercise 2-3.)  As a consequence, pairs provide a universal building block from which we can construct all sorts of data structures. Figure 2-3 shows two ways to use pairs to combine the numbers 1, 2, 3, and 4.

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-12.gif'>

<p style="text-align:center"> <b>Figure 2.3:</b> Two ways to combine 1, 2, 3, and 4 using pairs.

<p> The ability to create pairs whose elements are pairs is the essence of list structure's importance as a representational tool. We refer to this ability as the <tt>closure property</tt>  of <tt>cons</tt>. In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation.<a name="footnote_link_2-6" class="footnote_link" href="#footnote_2-6">6</a> Closure is the key to power in any means of combination because it permits us to create <tt>hierarchical</tt>  structures---structures made up of parts, which themselves are made up of parts, and so on.

<p> From the outset of Chapter 1, we've made essential use of closure in dealing with procedures, because all but the very simplest programs rely on the fact that the elements of a combination can themselves be combinations. In this section, we take up the consequences of closure for compound data. We describe some conventional techniques for using pairs to represent sequences and trees, and we exhibit a graphics language that illustrates closure in a vivid way.<a name="footnote_link_2-7" class="footnote_link" href="#footnote_2-7">7</a>

<h3> Representing Sequences </h3> 

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-13.gif'>

<p style="text-align:center"> <b>Figure 2.4:</b> The sequence 1, 2, 3, 4 represented as a chain of pairs.

<p> One of the useful structures we can build with pairs is a <tt>sequence</tt>  ---an ordered collection of data objects. There are, of course, many ways to represent sequences in terms of pairs. One particularly straightforward representation is illustrated in Figure 2-4, where the sequence 1, 2, 3, 4 is represented as a chain of pairs. The <tt>car</tt> of each pair is the corresponding item in the chain, and the <tt>cdr</tt> of the pair is the next pair in the chain. The <tt>cdr</tt> of the final pair signals the end of the sequence by pointing to a distinguished value that is not a pair, represented in box-and-pointer diagrams as a diagonal line and in programs as the value of the variable <tt>nil</tt>. The entire sequence is constructed by nested <tt>cons</tt> operations: 

<div id="scheme-cons-1-2-3-4">
(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))
</div>
<script>
prompt("scheme-cons-1-2-3-4");
</script>

<p> Such a sequence of pairs, formed by nested <tt>cons</tt>es, is called a <em> list </em>  , and Scheme provides a primitive called <tt>list</tt> to help in constructing lists.<a name="footnote_link_2-8" class="footnote_link" href="#footnote_2-8">8</a> The above sequence could be produced by <tt>(list 1 2 3 4)</tt>. In general,

<div id="scheme-list-syntax">
(list &lt;a_1&gt; &lt;a_2&gt; ... &lt;a_n&gt;)
</div>
<script>
makeStatic("scheme-list-syntax");
</script>

<p> is equivalent to

<div id="scheme-list-syntax-expand">
(cons &lt;a_1&gt;
      (cons &lt;a_2&gt;
            (cons ...
                  (cons &lt;a_n&gt;
                        nil)
...)))
</div>
<script>
makeStatic("scheme-list-syntax-expand");
</script>

<p> Lisp systems conventionally print lists by printing the sequence of elements, enclosed in parentheses. Thus, the data object in Figure 2-4 is printed as <tt>(1 2 3 4)</tt>:

<div id="scheme-define-one-through-four">
(define one-through-four (list 1 2 3 4))
</div>
<script>
prompt("scheme-define-one-through-four");
</script>

<p>

<div id="scheme-test-one-through-four">
one-through-four
</div>
<script>
promptDep("scheme-test-one-through-four", ["scheme-define-one-through-four"]);
</script>

<p> Be careful not to confuse the expression <tt>(list 1 2 3 4)</tt> with the list <tt>(1 2 3 4)</tt>, which is the result obtained when the expression is evaluated. Attempting to evaluate the expression <tt>(1 2 3 4)</tt> will signal an error when the interpreter tries to apply the procedure <tt>1</tt> to arguments <tt>2</tt>, <tt>3</tt>, and <tt>4</tt>.

<p> We can think of <tt>car</tt> as selecting the first item in the list, and of <tt>cdr</tt> as selecting the sublist consisting of all but the first item. Nested applications of <tt>car</tt> and <tt>cdr</tt> can be used to extract the second, third, and subsequent items in the list.<a name="footnote_link_2-9" class="footnote_link" href="#footnote_2-9">9</a> The constructor <tt>cons</tt> makes a list like the original one, but with an additional item at the beginning.

<div id="scheme-car-one-through-four">
(car one-through-four)
</div>
<script>
promptDep("scheme-car-one-through-four", ["scheme-define-one-through-four"]);
</script>

<p>

<div id="scheme-cdr-one-through-four">
(cdr one-through-four)
</div>
<script>
promptDep("scheme-cdr-one-through-four", ["scheme-define-one-through-four"]);
</script>

<p>

<div id="scheme-car-cdr-one-through-four">
(car (cdr one-through-four))
</div>
<script>
promptDep("scheme-car-cdr-one-through-four", ["scheme-define-one-through-four"]);
</script>

<p>

<div id="scheme-cons-10-one-through-four">
(cons 10 one-through-four)
</div>
<script>
promptDep("scheme-cons-10-one-through-four", ["scheme-define-one-through-four"]);
</script>

<p>

<div id="scheme-cons-5-one-through-four">
(cons 5 one-through-four)
</div>
<script>
promptDep("scheme-cons-5-one-through-four", ["scheme-define-one-through-four"]);
</script>

<p> The value of <tt>nil</tt>, used to terminate the chain of pairs, can be thought of as a sequence of no elements, the <tt>empty list</tt>  . The word <tt>nil</tt>  is a contraction of the Latin word <em>nihil</em>, which means ``nothing.''<a name="footnote_link_2-10" class="footnote_link" href="#footnote_2-10">10</a>

<h4> List operations </h4> 

<p> The use of pairs to represent sequences of elements as lists is accompanied by conventional programming techniques for manipulating lists by successively ``<tt>cdr</tt>ing down'' the lists. For example, the procedure <tt>list-ref</tt> takes as arguments a list and a number n and returns the nth item of the list. It is customary to number the elements of the list beginning with 0. The method for computing <tt>list-ref</tt> is the following:

<ul>

<li>
<p> For n = 0, <tt>list-ref</tt> should return the <tt>car</tt> of the list.
</li>

<li>
<p> Otherwise, <tt>list-ref</tt> should return  the (n - 1)st item of the <tt>cdr</tt> of the list.
</li>
</ul>

<div id="scheme-define-list-ref">
(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))
</div>
<script>
prompt("scheme-define-list-ref");
</script>

<div id="scheme-define-squares">
(define squares (list 1 4 9 16 25))
</div>
<script>
prompt("scheme-define-squares");
</script>

<div id="scheme-list-ref-squares-3">
(list-ref squares 3)
</div>
<script>
promptDep("scheme-list-ref-squares-3", ["scheme-define-list-ref", "scheme-define-squares"]);
</script>

<p> Often we <tt>cdr</tt> down the whole list. To aid in this, Scheme includes a primitive predicate <tt>null?</tt>, which tests whether its argument is the empty list. The procedure <tt>length</tt>, which returns the number of items in a list, illustrates this typical pattern of use:

<div id="scheme-define-length">
(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
</div>
<script>
prompt("scheme-define-length");
</script>


<div id="scheme-define-odds">
(define odds (list 1 3 5 7))
</div>
<script>
prompt("scheme-define-odds");
</script>


<div id="scheme-length-odds">
(length odds)
</div>
<script>
promptDep("scheme-length-odds", ["scheme-define-length", "scheme-define-odds"]);
</script>
<p> The <tt>length</tt> procedure implements a simple recursive plan. The reduction step is:

<ul>

<li>
<p> The <tt>length</tt> of any list is 1 plus the <tt>length</tt> of the <tt>cdr</tt> of the list.
</li>

</ul>

<p> This is applied successively until we reach the base case:

<ul>

<li>
<p> The <tt>length</tt> of the empty list is 0.
</li>

</ul>

<p> We could also compute <tt>length</tt> in an iterative style:

<div id="scheme-define-length-iterative">
(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0))
</div>
<script>
prompt("scheme-define-length-iterative");
</script>

<p> Another conventional programming technique is to ``<tt>cons</tt> up'' an answer list while <tt>cdr</tt>ing down a list, as in the procedure <tt>append</tt>, which takes two lists as arguments and combines their elements to make a new list:

<div id="scheme-append-squares-odds">
(append squares odds)
</div>
<script>
promptDep("scheme-append-squares-odds", ["scheme-define-squares", "scheme-define-odds"]);
</script>

<p>

<div id="scheme-append-odds-squares">
(append odds squares)
</div>
<script>
promptDep("scheme-append-odds-squares", ["scheme-define-squares", "scheme-define-odds"]);
</script>

<p> <tt>append</tt> is also implemented using a recursive plan. To <tt>append</tt> lists <tt>list1</tt> and <tt>list2</tt>, do the following:

<ul>
<li>
<p> If <tt>list1</tt> is the empty list, then the result is just <tt>list2</tt>.
</li>

<li>
<p> Otherwise, <tt>append</tt> the <tt>cdr</tt> of <tt>list1</tt> and <tt>list2</tt>, and <tt>cons</tt> the <tt>car</tt> of <tt>list1</tt> onto the result:
</li>
</ul>

<p>

<div id="scheme-define-append">
(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))
</div>
<script>
prompt("scheme-define-append");
</script>

<p>

<div class="exercise">
<p> <b>Exercise 2.17:</b> Define a procedure <tt>last-pair</tt> that returns the list that contains only the last element of a given (nonempty) list:

<div id="scheme-ex-define-last-pair">
(define (last-pair l)
  'your-code-here)
(last-pair (list 23 72 149 34))
</div>
<script>
makeEditable("scheme-ex-define-last-pair");
addOutput("scheme-ex-define-last-pair");
editorOf["scheme-ex-define-last-pair"].setOption("onBlur", function(){

  var code = "{0} \n (equal? (last-pair '(1 2 3 4)) '(4))".format(
    editorOf["scheme-ex-define-last-pair"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-last-pair-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-last-pair-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-last-pair-output").append(res.slice(0,-1));
  });
});
/*
(define (last-pair l)
  (if (null? (cdr l))
      l
      (last-pair (cdr l))))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.18:</b> Define a procedure <tt>reverse</tt> that takes a list as argument and returns a list of the same elements in reverse order:

<div id="scheme-ex-define-reverse">
(define (reverse l)
  'your-code-here)
(reverse (list 1 4 9 16 25))
</div>
<script>
makeEditable("scheme-ex-define-reverse");
addOutput("scheme-ex-define-reverse");
editorOf["scheme-ex-define-reverse"].setOption("onBlur", function(){

  var code = "{0} \n (equal? (reverse '(1 2 3 4)) '(4 3 2 1))".format(
    editorOf["scheme-ex-define-reverse"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-reverse-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-reverse-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-reverse-output").append(res.slice(0,-1));
  });
});
/*
(define (append-to-end l x)
  (if (null? l)
      (list x)
      (cons (car l)
            (append-to-end (cdr l) x))))

(define (reverse l)
  (if (null? l)
      l
      (append-to-end (reverse (cdr l))
                     (car l))))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.19:</b> Consider the change-counting program of section 1-2-2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure <tt>first-denomination</tt> and partly into the procedure <tt>count-change</tt> (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

<p> We want to rewrite the procedure <tt>cc</tt> so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:

<div id="scheme-define-coins">
(define us-coins (list 50 25 10 5 1))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))
</div>
<script>
prompt("scheme-define-coins");
</script>

<p> We could then call <tt>cc</tt> as follows:

<div id="scheme-cc-us-coins">
(cc 100 us-coins) ;292
</div>
<script>
prompt("scheme-cc-us-coins", ["scheme-define-coins", "scheme-ex-define-cc"]);
</script>

<p> To do this will require changing the program <tt>cc</tt> somewhat. It will still have the same form, but it will access its second argument differently, as follows:

<div id="scheme-ex-define-cc">
(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (&lt; amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))
</div>
<script>
makeEditable("scheme-ex-define-cc");
addOutput("scheme-ex-define-cc");
editorOf["scheme-ex-define-cc"].setOption("onBlur", function(){

  var code = "{0} \n (equal? (cc 100 '(50 25 10 5 1)) 292)".format(
    editorOf["scheme-ex-define-cc"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-cc-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-cc-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-cc-output").append(res.slice(0,-1));
    compute("scheme-cc-us-coins")
  });
});

/*
(define no-more? null?)
(define except-first-denomination cdr)
(define first-denomination car)
*/
</script>

<p> Define the procedures <tt>first-denomination</tt>, <tt>except-first-denomination</tt>, and <tt>no-more?</tt> in terms of primitive operations on list structures. Does the order of the list <tt>coin-values</tt> affect the answer produced by <tt>cc</tt>?  Why or why not?
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.20:</b> The procedures <tt>+</tt>, <tt>*</tt>, and <tt>list</tt> take arbitrary numbers of arguments. One way to define such procedures is to use <tt>define</tt> with <em>dotted-tail notation</em>  . In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a <tt>list</tt>  of any remaining arguments. For instance, given the definition

<div id="scheme-dotted-tail-syntax">
(define (f x y . z) &lt;body&gt;)
</div>
<script>
no_output_frozen_prompt("scheme-dotted-tail-syntax");
</script>

<p> the procedure <tt>f</tt> can be called with two or more arguments. If we evaluate

<div id="scheme-dotted-tail-application">
(f 1 2 3 4 5 6)
</div>
<script>
makeStatic("scheme-dotted-tail-application");
</script>

<p> then in the body of <tt>f</tt>, <tt>x</tt> will be 1, <tt>y</tt> will be 2, and <tt>z</tt> will be the list <tt>(3 4 5 6)</tt>. Given the definition

<div id="scheme-define-dotted-tail-syntax-one">
(define (g . w) &lt;body&gt;)
</div>
<script>
makeStatic("scheme-define-dotted-tail-syntax-one");
</script>

<p> the procedure <tt>g</tt> can be called with zero or more arguments. If we evaluate

<div id="scheme-g">
(g 1 2 3 4 5 6)
</div>
<script>
no_output_frozen_prompt("scheme-g");
</script>

<p> then in the body of <tt>g</tt>, <tt>w</tt> will be the list <tt>(1 2 3 4 5 6)</tt>.<a name="footnote_link_2-11" class="footnote_link" href="#footnote_2-11">11</a>

<p> Use this notation to write a procedure <tt>same-parity</tt> that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,

<div id="scheme-ex-define-same-parity">
(define (same-parity x . y)
  'your-code-here)

(same-parity 1 2 3 4 5 6 7)
(same-parity 2 3 4 5 6 7)
</div>
<script>
makeEditable("scheme-ex-define-same-parity");
addOutput("scheme-ex-define-same-parity");
editorOf["scheme-ex-define-same-parity"].setOption("onBlur", function(){

  var code = "{0} \n (equal? (same-parity '1 2 3 4 5 6 7) '(1 3 5 7))".format(
    editorOf["scheme-ex-define-same-parity"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-same-parity-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-same-parity-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-same-parity-output").append(res.slice(0,-1));
  });
});
/*
(define (filter l p)
  (cond ((null? l) l)
        ((p (car l)) (cons (car l)
                           (filter (cdr l) p)))
        (else (filter (cdr l) p))))

(define (same-parity x . y)
  (cons x (filter y (lambda (t) (= (modulo t 2)
                                   (modulo x 2))))))
*/
</script>
</div>

<h4> Mapping over lists </h4> 

<p> One extremely useful operation is to apply some transformation to each element in a list and generate the list of results. For instance, the following procedure scales each number in a list by a given factor:

<div id="scheme-define-scale-list">
(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))

(scale-list (list 1 2 3 4 5) 10)
</div>
<script>
prompt("scheme-define-scale-list");
</script>

<p> We can abstract this general idea and capture it as a common pattern expressed as a higher-order procedure, just as in section 1-3. The higher-order procedure here is called <tt>map</tt>. <tt>map</tt> takes as arguments a procedure of one argument and a list, and returns a list of the results produced by applying the procedure to each element in the list:<a name="footnote_link_2-12" class="footnote_link" href="#footnote_2-12">12</a>

<div id="scheme-define-map">
(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))
</div>
<script>
prompt("scheme-define-map");
</script>

<p>

<div id="scheme-test-map">
(map abs (list -10 2.5 -11.6 17))

(map (lambda (x) (* x x))
     (list 1 2 3 4))
</div>
<script>
prompt("scheme-test-map", ["scheme-define-map"]);
</script>

<p> Now we can give a new definition of <tt>scale-list</tt> in terms of <tt>map</tt>:

<div id="scheme-define-scale-list-with-map">
(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))
</div>
<script>
prompt("scheme-define-scale-list-with-map");
</script>

<p> <tt>map</tt> is an important construct, not only because it captures a common pattern, but because it establishes a higher level of abstraction in dealing with lists. In the original definition of <tt>scale-list</tt>, the recursive structure of the program draws attention to the element-by-element processing of the list. Defining <tt>scale-list</tt> in terms of <tt>map</tt> suppresses that level of detail and emphasizes that scaling transforms a list of elements to a list of results. The difference between the two definitions is not that the computer is performing a different process (it isn't) but that we think about the process differently. In effect, <tt>map</tt> helps establish an abstraction barrier that isolates the implementation of procedures that transform lists from the details of how the elements of the list are extracted and combined. Like the barriers shown in Figure 2-1, this abstraction gives us the flexibility to change the low-level details of how sequences are implemented, while preserving the conceptual framework of operations that transform sequences to sequences. Section 2-2-3 expands on this use of sequences as a framework for organizing programs.

<div class="exercise">
<p> <b>Exercise 2.21:</b> The procedure <tt>square-list</tt> takes a list of numbers as argument and returns a list of the squares of those numbers.

<div id="scheme-hidden-define-square-list">
(define (square-list items)
  (map (lambda (x) (* x x))
       items))
</div>
<script>
hidden_prompt("scheme-hidden-define-square-list", ["scheme-define-map"]);
</script>

<div id="scheme-test-square-list">
(square-list (list 1 2 3 4))
</div>
<script>
prompt("scheme-test-square-list", ["scheme-hidden-define-square-list"]);
</script>

<p> Here are two different definitions of <tt>square-list</tt>. Complete both of them by filling in the missing expressions:

<div id="scheme-ex-define-square-list">
(define (square-list items)
  (if (null? items)
      nil
      (cons &lt;??&gt; &lt;??&gt;)))

(define (square-list-map items)
  (map &lt;??&gt; &lt;??&gt;))
</div>
<script>
makeEditable("scheme-ex-define-square-list");
addOutput("scheme-ex-define-square-list");
editorOf["scheme-ex-define-square-list"].setOption("onBlur", function(){

  var code = "{0} \n {1} \n (and (equal? (square-list '(1 2 3 4)) '(1 4 9 16)) (equal? (square-list-map '(1 2 3 4)) '(1 4 9 16)))".format(
    editorOf["scheme-define-map"].getValue(),
    editorOf["scheme-ex-define-square-list"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-square-list-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-square-list-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-square-list-output").append(res.slice(0,-1));
  });
});
/*
(define (square-list items)
  (if (null? items)
      nil
      (cons (* (car items) (car items))
            (square-list (cdr items)))))

(define (square-list-map items)
  (map (lambda (x) (* x x))
       items))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.22:</b> Louis Reasoner tries to rewrite the first <tt>square-list</tt> procedure of Exercise 2-21 so that it evolves an iterative process:

<div id="scheme-define-louise-square-list">
(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))
</div>
<script>
prompt("scheme-define-louise-square-list", ["scheme-define-square"]);
</script>

<p> Unfortunately, defining <tt>square-list</tt> this way produces the answer list in the reverse order of the one desired. Why?

<p> Louis then tries to fix his bug by interchanging the arguments to <tt>cons</tt>:

<div id="scheme-define-louise-square-list-2">
(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))
</div>
<script>
prompt("scheme-define-louise-square-list-2", ["scheme-define-square"]);
</script>

<p> This doesn't work either. Explain.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.23:</b> The procedure <tt>for-each</tt> is similar to <tt>map</tt>. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, <tt>for-each</tt> just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all &ndash; <tt>for-each</tt> is used with procedures that perform an action, such as printing. For example,

<div id="scheme-test-for-each">
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
</div>
<script>
prompt("scheme-test-for-each", ["scheme-ex-define-for-each"]);
</script>

<p> should print <tt>57</tt>, <tt>321</tt> and <tt>88</tt>. The value returned by the call to <tt>for-each</tt> should be <tt>true</tt>. Give an implementation of <tt>for-each</tt>.

<div id="scheme-ex-define-for-each">
(define (for-each proc lst)
  'your-code-here)
</div>
<script>
makeEditable("scheme-ex-define-for-each");
addOutput("scheme-ex-define-for-each");
editorOf["scheme-ex-define-for-each"].setOption("onBlur", function(){

  var code = "{0} \n (for-each (lambda (x) (newline) (display x)) '(57 321 88))".format( 
    editorOf["scheme-ex-define-for-each"].getValue());

  eval_scheme(code).then(function(res){
    console.log(res);

    var $output = $_("scheme-ex-define-for-each-output")
    
    if (res.length >= 7 && res[res.length - 1] === "true\n" && res[res.length - 2].value === "88") {
      $output.empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $output.empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $output.append(res.slice(0,-1));
    compute("scheme-test-for-each");
  });
});

/*
TODO: why does a map-style definition throw exceptions?

(define (for-each proc items)
  (if (null? items)
      nil
      (begin (proc (car items))
             (for-each proc (cdr items))
             #t)))
*/
</script>

</div>

<h3> Hierarchical Structures </h3> 

<p> The representation of sequences in terms of lists generalizes naturally to represent sequences whose elements may themselves be sequences. For example, we can regard the object <tt>((1 2) 3 4)</tt> constructed by

<div id="scheme-show-1-2-pair-3-4">
(cons (list 1 2) (list 3 4))
</div>
<script>
prompt("scheme-show-1-2-pair-3-4");
</script>

<p> as a list of three items, the first of which is itself a list, <tt>(1 2)</tt>. Indeed, this is suggested by the form in which the result is printed by the interpreter. Figure 2-5 shows the representation of this structure in terms of pairs.

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-15.gif'>

<p style="text-align:center"> <b>Figure 2.5:</b> Structure formed by <tt>(cons (list 1 2) (list 3 4))</tt>.

<p> Another way to think of sequences whose elements are sequences is as <tt>trees</tt> . The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees. Figure 2-6 shows the structure in Figure 2-5 viewed as a tree.

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-16.gif'>

<p style="text-align:center"> <b>Figure 2.6:</b> The list structure in Figure 2-5 viewed as a tree.

<p> Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, which reduce in turn to operations on the branches of the branches, and so on, until we reach the leaves of the tree. As an example, compare the <tt>length</tt> procedure of section 2-2-1 with the <tt>count-leaves</tt> procedure, which returns the total number of leaves of a tree:

<div id="scheme-define-x">
(define x (cons (list 1 2) (list 3 4)))
</div>
<script>
prompt("scheme-define-x");
</script>

<p>

<div id="scheme-length-x">
(length x)
</div>
<script>
prompt("scheme-length-x", ["scheme-define-x"]);
</script>

<p>

<div id="scheme-count-leaves-x">
(count-leaves x)
</div>
<script>
prompt("scheme-count-leaves-x", ["scheme-define-x", "scheme-define-count-leaves"]);
</script>

<p>

<div id="scheme-list-x-x">
(list x x)
</div>
<script>
prompt("scheme-list-x-x", ["scheme-define-x"]);
</script>

<p>

<div id="scheme-length-list-x-x">
(length (list x x))
</div>
<script>
prompt("scheme-length-list-x-x", ["scheme-define-x"]);
</script>

<p>

<div id="scheme-count-leaves-list-x-x">
(count-leaves (list x x))
</div>
<script>
prompt("scheme-count-leaves-list-x-x", ["scheme-define-count-leaves", "scheme-define-x"]);
</script>

<p> To implement <tt>count-leaves</tt>, recall the recursive plan for computing <tt>length</tt>:

<ul>

<li>
<tt>length</tt> of a list <tt>x</tt> is 1 plus <tt>length</tt> of the <tt>cdr</tt> of <tt>x</tt>.
</li>

<li>
<tt>length</tt> of the empty list is 0.
</li>
</ul>

<p> <tt>count-leaves</tt> is similar. The value for the empty list is the same:

<ul>

<li>
<tt>count-leaves</tt> of the empty list is 0.
</li>
</ul>

<p> But in the reduction step, where we strip off the <tt>car</tt> of the list, we must take into account that the <tt>car</tt> may itself be a tree whose leaves we need to count. Thus, the appropriate reduction step is

<ul>

<li>
<tt>count-leaves</tt> of a tree <tt>x</tt> is <tt>count-leaves</tt> of the <tt>car</tt> of <tt>x</tt> plus <tt>count-leaves</tt> of the <tt>cdr</tt> of <tt>x</tt>.
</li>
</ul>

<p> Finally, by taking <tt>car</tt>s we reach actual leaves, so we need another base case:

<ul>
<li>
<tt>count-leaves</tt> of a leaf is 1.
</li>
</ul>

<p> To aid in writing recursive procedures on trees, Scheme provides the primitive predicate <tt>pair?</tt>, which tests whether its argument is a pair. Here is the complete procedure:<a name="footnote_link_2-13" class="footnote_link" href="#footnote_2-13">13</a>

<div id="scheme-define-count-leaves">
(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))
</div>
<script>
prompt("scheme-define-count-leaves");
</script>

<p>

<div class="exercise">
<p> <b>Exercise 2.24:</b> Suppose we evaluate the expression <tt>(list 1 (list 2 (list 3 4)))</tt>. Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2-6).
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.25:</b> Give combinations of <tt>car</tt>s and <tt>cdr</tt>s that will pick 7 from each of the following lists. Represent the list as <tt>l</tt>.

<div id="scheme-ex-pick-7-medium">
(1 3 (5 7) 9)
</div>
<script>
equalp_answer("scheme-ex-pick-7-medium", "(car (cdr (car (cdr (cdr l)))))");
</script>

<div id="scheme-ex-pick-7-easy">
((7))
</div>
<script>
equalp_answer("scheme-ex-pick-7-easy", "(car (car l))");
</script>

<div id="scheme-ex-pick-7-hard">
(1 (2 (3 (4 (5 (6 7))))))
</div>
<script>
equalp_answer("scheme-ex-pick-7-hard", "(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr l))))))))))))");
</script>

</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.26:</b> Suppose we define <tt>x</tt> and <tt>y</tt> to be two lists:

<div id="scheme-ex-append-cons-list">
(define x (list 1 2 3))

(define y (list 4 5 6))
</div>
<script>
prompt("scheme-ex-append-cons-list");
</script>

<p> What result is printed by the interpreter in response to evaluating each of the following expressions?

<div id="scheme-ex-append">
(append x y)
</div>
<script>
answer("scheme-ex-append", "(1 2 3 4 5 6)");
</script>

<div id="scheme-ex-cons">
(cons x y)
</div>
<script>
answer("scheme-ex-cons", "((1 2 3) 4 5 6)");
</script>

<div id="scheme-ex-list">
(list x y)
</div>
<script>
answer("scheme-ex-list", "((1 2 3) (4 5 6))");
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.27:</b> Modify your <tt>reverse</tt> procedure of Exercise 2-18 to produce a <tt>deep-reverse</tt> procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

<div id="scheme-hidden-answer-define-deep-reverse">
(define (append-to-end l x)
  (if (null? l)
      (list x)
      (cons (car l)
            (append-to-end (cdr l) x))))

;todo: maybe reverse should get an answer section too?
(define (reverse l)
  (if (null? l)
      l
      (append-to-end (reverse (cdr l))
                     (car l))))

(define (deep-reverse l)
  (if (null? l)
      '()
      (append-to-end (deep-reverse (cdr l))
                     (if (pair? (car l))
                         (deep-reverse (car l))
                         (car l)))))
</div>
<script>
hidden_prompt("scheme-hidden-answer-define-deep-reverse");
</script>

<div id="scheme-demonstrate-deep-reverse-define-x">
(define x (list (list 1 2) (list 3 4)))
</div>
<script>
prompt("scheme-demonstrate-deep-reverse-define-x", ["scheme-hidden-answer-define-deep-reverse"]);
</script>

<div id="scheme-demonstrate-deep-reverse-x">
x
</div>
<script>
prompt("scheme-demonstrate-deep-reverse-x", ["scheme-demonstrate-deep-reverse-define-x"]);
</script>

<p>

<div id="scheme-demonstrate-deep-reverse-reverse-x">
(reverse x)
</div>
<script>
prompt("scheme-demonstrate-deep-reverse-reverse-x", ["scheme-demonstrate-deep-reverse-define-x"]);
</script>

<p>

<div id="scheme-demonstrate-deep-reverse-deep-reverse-x">
(deep-reverse x)
</div>
<script>
prompt("scheme-demonstrate-deep-reverse-deep-reverse-x", ["scheme-demonstrate-deep-reverse-define-x"]);
</script>

<p>

<div id="scheme-ex-define-deep-reverse">
(define (deep-reverse lst)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-deep-reverse");
addOutput("scheme-ex-define-deep-reverse");
editorOf["scheme-ex-define-deep-reverse"].setOption("onBlur", function(){

  var code = "{0} \n (equal? '((4 3) (2 1)) (deep-reverse '((1 2) (3 4))))".format(
    editorOf["scheme-ex-define-deep-reverse"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-deep-reverse-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-deep-reverse-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-deep-reverse-output").append(res.slice(0,-1));
  });
});
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.28:</b> Write a procedure <tt>fringe</tt> that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,


<div id="scheme-hidden-answer-define-fringe">
(define (fringe l)
  (cond ((null? l) '())
        ((pair? l) (append (fringe (car l))
                           (fringe (cdr l))))
        (else (list l))))
</div>
<script>
hidden_prompt("scheme-hidden-answer-define-fringe");
</script>

<div id="scheme-demonstrate-fringe-define-x">
(define x (list (list 1 2) (list 3 4)))
</div>
<script>
prompt("scheme-demonstrate-fringe-define-x", ["scheme-hidden-answer-define-fringe"]);
</script>

<p>

<div id="scheme-demonstrate-fringe-fringe-x">
(fringe x)
</div>
<script>
prompt("scheme-demonstrate-fringe-fringe-x", ["scheme-demonstrate-fringe-define-x"]);
</script>

<p>

<div id="scheme-demonstrate-fringe-fringe-x-x">
(fringe (list x x))
</div>
<script>
prompt("scheme-demonstrate-fringe-fringe-x-x", ["scheme-demonstrate-fringe-define-x"]);
</script>

<p>


<div id="scheme-ex-define-fringe">
(define (fringe lst)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-fringe");
addOutput("scheme-ex-define-fringe");
editorOf["scheme-ex-define-fringe"].setOption("onBlur", function(){

  var code = "{0} \n (equal? '(1 2 3 4) (fringe '((1 2) (3 4))))".format(
    editorOf["scheme-ex-define-fringe"].getValue());

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-fringe-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-fringe-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-fringe-output").append(res.slice(0,-1));
  });
});
/*
(define (fringe l)
  (cond ((null? l) '())
        ((pair? l) (append (fringe (car l))
                           (fringe (cdr l))))
        (else (list l))))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.29:</b> A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using <tt>list</tt>):

<div id="scheme-define-make-mobile">
(define (make-mobile left right)
  (list left right))
</div>
<script>
prompt("scheme-define-make-mobile");
</script>

<p> A branch is constructed from a <tt>length</tt> (which must be a number) together with a <tt>structure</tt>, which may be either a number (representing a simple weight) or another mobile:

<div id="scheme-define-make-branch">
(define (make-branch length structure)
  (list length structure))
</div>
<script>
prompt("scheme-define-make-branch");
</script>

<ul>
<li>
<p> Write the corresponding selectors <tt>left-branch</tt> and <tt>right-branch</tt>, which return the branches of a mobile, and <tt>branch-length</tt> and <tt>branch-structure</tt>, which return the components of a branch.

<div id="scheme-ex-define-left-right-branch-length-structure">
(define (left-branch mobile)
  'your-code-here)

(define (right-branch mobile)
  'your-code-here)

(define (branch-length branch)
  'your-code-here)

(define (branch-structure branch)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-left-right-branch-length-structure");
addOutput("scheme-ex-define-left-right-branch-length-structure");
editorOf["scheme-ex-define-left-right-branch-length-structure"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2} {3} {4})".format(
    editorOf["scheme-ex-define-left-right-branch-length-structure"].getValue(),
    "(equal? 1 (left-branch '(1 2)))",
    "(equal? 2 (right-branch '(1 2)))",
    "(equal? 1 (branch-length '(1 2)))",
    "(equal? 2 (branch-structure '(1 2)))");

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-left-right-branch-length-structure-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-left-right-branch-length-structure-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-left-right-branch-length-structure-output").append(res.slice(0,-1));
  });
});
/*
(define left-branch car)
(define right-branch cadr)
(define branch-length car)
(define branch-structure cadr)
*/
</script>
<p>
</li>

<li>
<p> Using your selectors, define a procedure <tt>total-weight</tt> that returns the total weight of a mobile.

<div id="scheme-ex-define-total-weight">
(define (total-weight mobile)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-total-weight");
addDep("scheme-ex-define-total-weight", ["scheme-define-make-mobile", "scheme-define-make-branch", "scheme-ex-define-left-right-branch-length-structure"]);

addOutput("scheme-ex-define-total-weight");
editorOf["scheme-ex-define-total-weight"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-total-weight"),
    "#t",
    "(= (total-weight '((1 2) (1 2))) 4)"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-total-weight-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-total-weight-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-total-weight-output").append(res.slice(0,-1));
  });
});
/*
(define (total-weight mobile)
  (+ (total-weight-branch (left-branch mobile))
     (total-weight-branch (right-branch mobile))))

(define (total-weight-branch branch)
  (if (number? (branch-structure branch))
      (branch-structure branch)
      (total-weight branch-structure)))
*/
</script>
<p>
</li>

<li>
<p> A mobile is said to be <tt>balanced</tt> if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

<div id="scheme-ex-define-balancedp">
(define (balanced? mobile)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-balancedp");
addDep("scheme-ex-define-balancedp", ["scheme-define-make-mobile", "scheme-define-make-branch", "scheme-ex-define-left-right-branch-length-structure", "scheme-ex-define-total-weight"]);

addOutput("scheme-ex-define-balancedp");
editorOf["scheme-ex-define-balancedp"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-balancedp"),
    "#t",
    "(equal? (balanced? '((1 2) (1 2))) #t)"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-balancedp-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-balancedp-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-balancedp-output").append(res.slice(0,-1));
  });
});
/*
(define (balanced? mobile)
  (and (this-balanced mobile)
       (balanced-branch? (left-branch mobile))
       (balanced-branch? (right-branch mobile))))

(define (this-balanced mobile)
  (= (* (branch-length (left-branch mobile))
        (total-weight-branch (left-branch mobile)))
     (* (branch-length (right-branch mobile))
        (total-weight-branch (right-branch mobile)))))

(define (balanced-branch? branch)
  (or (number? (branch-structure branch))
      (balanced? (branch-structure branch))))
*/
</script>
<p>
</li>

<li>
<p> Suppose we change the representation of mobiles so that the constructors are
</li>

<div id="scheme-define-make-mobile-branch-cons">
(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))
</div>
<script>
prompt("scheme-define-make-mobile-branch-cons");
</script>

<p> How much do you need to change your programs to convert to the new representation?

</ul>
</div>

<h4> Mapping over trees </h4> 

<p> Just as <tt>map</tt> is a powerful abstraction for dealing with sequences, <tt>map</tt> together with recursion is a powerful abstraction for dealing with trees. For instance, the <tt>scale-tree</tt> procedure, analogous to <tt>scale-list</tt> of section 2-2-1, takes as arguments a numeric factor and a tree whose leaves are numbers. It returns a tree of the same shape, where each number is multiplied by the factor. The recursive plan for <tt>scale-tree</tt> is similar to the one for <tt>count-leaves</tt>:

<div id="scheme-define-scale-tree">
(define (scale-tree tree factor)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (* tree factor))
        (else (cons (scale-tree (car tree) factor)
                    (scale-tree (cdr tree) factor)))))
</div>
<script>
prompt("scheme-define-scale-tree");
</script>

<p>

<div id="scheme-test-scale-tree">
(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))
            10)
</div>
<script>
prompt("scheme-test-scale-tree", ["scheme-define-scale-tree"]);
</script>

<p> Another way to implement <tt>scale-tree</tt> is to regard the tree as a sequence of sub-trees and use <tt>map</tt>. We map over the sequence, scaling each sub-tree in turn, and return the list of results. In the base case, where the tree is a leaf, we simply multiply by the factor:

<div id="scheme-define-scale-tree-map">
(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))
</div>
<script>
prompt("scheme-define-scale-tree-map", ["scheme-define-map"]);
</script>

<p> Many tree operations can be implemented by similar combinations of sequence operations and recursion.

<div class="exercise">
<p> <b>Exercise 2.30:</b> Define a procedure <tt>square-tree</tt> analogous to the <tt>square-list</tt> procedure of Exercise 2-21. That is, <tt>square-list</tt> should behave as follows:

<div id="scheme-test-square-tree">
(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
;(1 (4 (9 16) 25) (36 49))
</div>
<script>
prompt("scheme-test-square-tree");
</script>

<p> Define <tt>square-tree</tt> both directly (i.e., without using any higher-order procedures) and also by using <tt>map</tt> and recursion. 

<div id="scheme-ex-define-square-tree">
(define (square-tree tree)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-square-tree");
addDep("scheme-ex-define-square-tree", ["scheme-define-map"]);

addOutput("scheme-ex-define-square-tree");
editorOf["scheme-ex-define-square-tree"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-square-tree"),
    "#t",
    "(equal? (square-tree '(1 (2 (3 4) 5) (6 7))) '(1 (4 (9 16) 25) (36 49)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-square-tree-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-square-tree-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-square-tree-output").append(res.slice(0,-1));
  });
});
/*
(define (square-tree tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree sub-tree)
             (* sub-tree sub-tree)))
       tree))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.31:</b> Abstract your answer to Exercise 2-30 to produce a procedure <tt>tree-map</tt> with the property that <tt>square-tree</tt> could be defined as

<div id="scheme-demonstrate-tree-map-square-tree">
(define (square-tree tree) (tree-map square tree))
</div>
<script>
no_output_frozen_prompt("scheme-demonstrate-tree-map-square-tree", ["scheme-define-square"]);
</script>

<div id="scheme-ex-define-tree-map">
(define (tree-map f tree)
  'your-code-here)
</div>

<script>
makeEditable("scheme-ex-define-tree-map");
addDep("scheme-ex-define-tree-map", ["scheme-define-map"]);

addOutput("scheme-ex-define-tree-map");
editorOf["scheme-ex-define-tree-map"].setOption("onBlur", function(){

  var code = "{0} \n {1} \n (and {2} {3})".format(
    getDependedOnCode("scheme-ex-define-tree-map"),
    getDependedOnCode("scheme-demonstrate-tree-map-square-tree"),
    "#t",
    "(equal? (square-tree '(1 (2 (3 4) 5) (6 7))) '(1 (4 (9 16) 25) (36 49)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-tree-map-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-tree-map-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-tree-map-output").append(res.slice(0,-1));
  });
});
/*
(define (tree-map f tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree sub-tree)
             (f sub-tree)))
       tree))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.32:</b> We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is <tt>(1 2 3)</tt>, then the set of all subsets is <tt>(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))</tt>. Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

<div id="scheme-ex-define-subset">
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map 'your-answer-here rest)))))
</div>
<script>
makeEditable("scheme-ex-define-subset");
addDep("scheme-ex-define-subset", ["scheme-define-map"]);

addOutput("scheme-ex-define-subset");
editorOf["scheme-ex-define-subset"].setOption("onBlur", function(){

  var code = "{0} \n(and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-subset"),
    "#t",
    "(equal? (subsets '(1 2 3)) '(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-subset-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-subset-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-subset-output").append(res.slice(0,-1));
  });
});
/*
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (rest-ss)
                            (cons (car s)
                                  rest-ss))
                          rest)))))
*/
</script>
</div>

<h3> Sequences as Conventional Interfaces </h3> 

<p> In working with compound data, we've stressed how data abstraction permits us to design programs without becoming enmeshed in the details of data representations, and how abstraction preserves for us the flexibility to experiment with alternative representations. In this section, we introduce another powerful design principle for working with data structures &ndash; the use of <tt>conventional interfaces</tt> .

<p> In section 1-3 we saw how program abstractions, implemented as higher-order procedures, can capture common patterns in programs that deal with numerical data. Our ability to formulate analogous operations for working with compound data depends crucially on the style in which we manipulate our data structures. Consider, for example, the following procedure, analogous to the <tt>count-leaves</tt> procedure of section 2-2-2, which takes a tree as argument and computes the sum of the squares of the leaves that are odd:

<div id="scheme-define-sum-odd-squares">
(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))
</div>
<script>
prompt("scheme-define-sum-odd-squares");
</script>

<p> On the surface, this procedure is very different from the following one, which constructs a list of all the even Fibonacci numbers $\text{Fib}(k)$, where $k$ is less than or equal to a given integer $n$:

<div id="scheme-define-even-fibs">
(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))
</div>
<script>
prompt("scheme-define-even-fibs");
</script>

<p> Despite the fact that these two procedures are structurally very different, a more abstract description of the two computations reveals a great deal of similarity. The first program

<ul>
<li>
enumerates the leaves of a tree;
</li>

<li>
filters them, selecting the odd ones;
</li>

<li>
squares each of the selected ones; and
</li>

<li>
accumulates the results using <tt>+</tt>, starting with 0.
</li>
</ul>

<p> The second program

<ul>
<li>
enumerates the integers from 0 to n;
</li>

<li>
computes the Fibonacci number for each integer;
</li>

<li>
filters them, selecting the even ones; and
</li>

<li>
accumulates the results using <tt>cons</tt>,  starting with the
empty list.
</li>
</ul>

<p> A signal-processing engineer would find it natural to conceptualize these processes in terms of signals flowing through a cascade of stages, each of which implements part of the program plan, as shown in Figure 2-7. In <tt>sum-odd-squares</tt>, we begin with an <tt>enumerator</tt> , which generates a ``signal'' consisting of the leaves of a given tree. This signal is passed through a <tt>filter</tt> , which eliminates all but the odd elements. The resulting signal is in turn passed through a <tt>map</tt> , which is a ``transducer'' that applies the <tt>square</tt> procedure to each element. The output of the map is then fed to an <tt>accumulator</tt> , which combines the elements using <tt>+</tt>, starting from an initial 0. The plan for <tt>even-fibs</tt> is analogous.

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-17.gif'>

<p style="text-align:center"> <b>Figure 2.7:</b> The signal-flow plans for the procedures <tt>sum-odd-squares</tt> (top) and <tt>even-fibs</tt> (bottom) reveal the commonality between the two programs.

<p> Unfortunately, the two procedure definitions above fail to exhibit this signal-flow structure. For instance, if we examine the <tt>sum-odd-squares</tt>procedure, we find that the enumeration is implemented partly by the<tt>null?</tt> and <tt>pair?</tt> tests and partly by the tree-recursive structureof the procedure. Similarly, the accumulation is found partly in the tests and partly in the addition used in the recursion. In general, there are no distinct parts of either procedure that correspond to the elements in the signal-flow description. Our two procedures decompose the computations in a different way, spreading the enumeration over the program and mingling it with the <tt>map</tt>, the <tt>filter</tt>, and the <tt>accumulation</tt>. If we could organize our programs to make the signal-flow structure manifest in the procedures we write, this would increase the conceptual clarity of the resulting code.

<h4> Sequence Operations </h4> 

<p> The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate on the ``signals'' that flow from one stage in the process to the next. If we represent these signals as lists, then we can use list operations to implement the processing at each of the stages. For instance, we can implement the mapping stages of the signal-flow diagrams using the <tt>map</tt> procedure from section 2-2-1:

<div id="scheme-map-square-1-to-5">
(map square (list 1 2 3 4 5))
</div>
<script>
prompt("scheme-map-square-1-to-5", ["scheme-define-map", "scheme-define-square"]);
</script>

<p> Filtering a sequence to select only those elements that satisfy a given
predicate is accomplished by

<div id="scheme-define-filter">
(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
</div>
<script>
prompt("scheme-define-filter");
</script>

For example,

<div id="scheme-filter-odd-1-to-5">
(filter odd? (list 1 2 3 4 5))
</div>
<script>
prompt("scheme-filter-odd-1-to-5", ["scheme-define-filter"]);
</script>

<p> Accumulations can be implemented by

<div id="scheme-define-accumulate">
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
</div>
<script>
prompt("scheme-define-accumulate");
</script>

<p>

<div id="scheme-accumulate-sum-1-to-5">
(accumulate + 0 (list 1 2 3 4 5))
</div>
<script>
prompt("scheme-accumulate-sum-1-to-5", ["scheme-define-accumulate"]);
</script>

<p>

<div id="scheme-accumulate-product-1-to-5">
(accumulate * 1 (list 1 2 3 4 5))
</div>
<script>
prompt("scheme-accumulate-product-1-to-5", ["scheme-define-accumulate"]);
</script>

<p>

<div id="scheme-accumulate-cons-1-to-5">
(accumulate cons nil (list 1 2 3 4 5))
</div>
<script>
prompt("scheme-accumulate-cons-1-to-5", ["scheme-define-accumulate"]);
</script>

<p> All that remains to implement signal-flow diagrams is to enumerate the sequence of elements to be processed. For <tt>even-fibs</tt>, we need to generate the sequence of integers in a given range, which we can do as follows:
  
<div id="scheme-define-enumerate-interval">
(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))
</div>
<script>
prompt("scheme-define-enumerate-interval");
</script>

<p>

<div id="scheme-enumerate-interval-2-7">
(enumerate-interval 2 7)
</div>
<script>
prompt("scheme-enumerate-interval-2-7", ["scheme-define-enumerate-interval"]);
</script>

<p> To enumerate the leaves of a tree, we can use<a name="footnote_link_2-14" class="footnote_link" href="#footnote_2-14">14</a>

<div id="scheme-define-enumerate-tree">
(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

</div>
<script>
prompt("scheme-define-enumerate-tree");
</script>

<p>

<div id="scheme-enumerate-tree-nested-1-5">
(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
</div>
<script>
prompt("scheme-enumerate-tree-nested-1-5", ["scheme-define-enumerate-tree"]);
</script>

<p> Now we can reformulate <tt>sum-odd-squares</tt> and <tt>even-fibs</tt> as in the signal-flow diagrams. For <tt>sum-odd-squares</tt>, we enumerate the sequence of leaves of the tree, filter this to keep only the odd numbers in the sequence, square each element, and sum the results:

<div id="scheme-define-sum-odd-squares-with-accumulate">
(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))
</div>
<script>
prompt("scheme-define-sum-odd-squares-with-accumulate", ["scheme-define-accumulate", "scheme-define-map", "scheme-define-enumerate-tree"]);
</script>

<div id="scheme-hidden-define-fib">
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
</div>
<script>
hidden_prompt("scheme-hidden-define-fib");
</script>

<p> For <tt>even-fibs</tt>, we enumerate the integers from 0 to n, generate the Fibonacci number for each of these integers, filter the resulting sequence to keep only the even elements, and accumulate the results into a list:

<div id="scheme-define-even-fibs-with-accumulate">
(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))
</div>
<script>
prompt("scheme-define-even-fibs-with-accumulate", ["scheme-define-accumulate", "scheme-define-map", "scheme-define-enumerate-tree", "scheme-hidden-define-fib"]);
</script>

<p> The value of expressing programs as sequence operations is that this helps us make program designs that are modular, that is, designs that are constructed by combining relatively independent pieces. We can encourage modular design by providing a library of standard components together with a conventional interface for connecting the components in flexible ways.

<p> Modular construction is a powerful strategy for controlling complexity in engineering design. In real signal-processing applications, for example, designers regularly build systems by cascading elements selected from standardized families of filters and transducers. Similarly, sequence operations provide a library of standard program elements that we can mix and match. For instance, we can reuse pieces from the <tt>sum-odd-squares</tt> and <tt>even-fibs</tt> procedures in a program that constructs a list of the squares of the first $n + 1$ Fibonacci numbers:

<div id="scheme-define-list-fib-squares">
(define (list-fib-squares n)
  (accumulate cons
              nil
              (map square
                   (map fib
                        (enumerate-interval 0 n)))))
</div>
<script>
prompt("scheme-define-list-fib-squares", ["scheme-define-accumulate", "scheme-define-map", "scheme-define-enumerate-interval", "scheme-define-square", "scheme-hidden-define-fib"]);
</script>

<p>

<div id="scheme-list-fib-squares-10">
(list-fib-squares 10)
</div>
<script>
prompt("scheme-list-fib-squares-10", ["scheme-define-list-fib-squares"]);
</script>

<p> We can rearrange the pieces and use them in computing the product of the odd integers in a sequence:

<div id="scheme-define-product-of-squares-of-odd-elements">
(define (product-of-squares-of-odd-elements sequence)
  (accumulate *
              1
              (map square
                   (filter odd? sequence))))
</div>
<script>
prompt("scheme-define-product-of-squares-of-odd-elements", ["scheme-define-accumulate", "scheme-define-map", "scheme-define-square", "scheme-define-filter"]);
</script>

<p>

<div id="scheme-product-of-squares-of-odd-elements-1-to-5">
(product-of-squares-of-odd-elements (list 1 2 3 4 5))
</div>
<script>
prompt("scheme-product-of-squares-of-odd-elements-1-to-5", ["scheme-define-product-of-squares-of-odd-elements"]);
</script>

<p> We can also formulate conventional data-processing applications in terms of sequence operations. Suppose we have a sequence of personnel records and we want to find the salary of the highest-paid programmer. Assume that we have a selector <tt>salary</tt> that returns the salary of a record, and a predicate <tt>programmer?</tt> that tests if a record is for a programmer. Then we can write

<div id="scheme-define-salary-of-highest-paid-programmer">
(define (salary-of-highest-paid-programmer records)
  (accumulate max
              0
              (map salary
                   (filter programmer? records))))
</div>
<script>
prompt("scheme-define-salary-of-highest-paid-programmer");
</script>

<p> These examples give just a hint of the vast range of operations that can be expressed as sequence operations.<a name="footnote_link_2-15" class="footnote_link" href="#footnote_2-15">15</a>
  
<p> Sequences, implemented here as lists, serve as a conventional interface that permits us to combine processing modules. Additionally, when we uniformly represent structures as sequences, we have localized the data-structure dependencies in our programs to a small number of sequence operations. By changing these, we can experiment with alternative representations of sequences, while leaving the overall design of our programs intact. We will exploit this capability in section 3-5, when we generalize the sequence-processing paradigm to admit infinite sequences.

<div class="exercise">
<p> <b>Exercise 2.33:</b> Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

<div id="scheme-ex-define-map-as-accumulate">
(define (map p sequence)
  (accumulate (lambda (x y) 'you-answer-here) nil sequence))
</div>
<script>
makeEditable("scheme-ex-define-map-as-accumulate");
addDep("scheme-ex-define-map-as-accumulate", ["scheme-define-accumulate"]);

addOutput("scheme-ex-define-map-as-accumulate");
editorOf["scheme-ex-define-map-as-accumulate"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-map-as-accumulate"),
    "#t",
    "(equal? '(1 2 3) (map (lambda (x) x) '(1 2 3)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-map-as-accumulate-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-map-as-accumulate-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-map-as-accumulate-output").append(res.slice(0,-1));
  });
});
/*
(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) nil sequence))
*/
</script>

<p>

<div id="scheme-ex-define-append-as-accumulate">
(define (append seq1 seq2)
  (accumulate cons 'your-answer-here 'your-answer-here))
</div>
<script>
makeEditable("scheme-ex-define-append-as-accumulate");
addDep("scheme-ex-define-append-as-accumulate", ["scheme-define-accumulate"]);

addOutput("scheme-ex-define-append-as-accumulate");
editorOf["scheme-ex-define-append-as-accumulate"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-append-as-accumulate"),
    "#t",
    "(equal? '(1 2 3 4 5) (append '(1 2 3) '(4 5)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-append-as-accumulate-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-append-as-accumulate-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-append-as-accumulate-output").append(res.slice(0,-1));
  });
});
/*
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
*/
</script>

<p>

<div id="scheme-ex-define-length-as-accumulate">
(define (length sequence)
  (accumulate 'your-answer-here 0 sequence))
</div>
<script>
makeEditable("scheme-ex-define-length-as-accumulate");
addDep("scheme-ex-define-length-as-accumulate", ["scheme-define-accumulate"]);

addOutput("scheme-ex-define-length-as-accumulate");
editorOf["scheme-ex-define-length-as-accumulate"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-length-as-accumulate"),
    "#t",
    "(equal? 3 (length '(1 2 3)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-length-as-accumulate-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-length-as-accumulate-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-length-as-accumulate-output").append(res.slice(0,-1));
  });
});
/*
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.34:</b> Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

$$
a_n r^n + a_{n-1} r^{n-1} + \cdots + a_1 r + a_0
$$


<p> using a well-known algorithm called <tt>Horner's rule</tt> , which structures the computation as

$$
(\cdots (a_n r + a_{n-1}) r + \cdots + a_1) r + a_0
$$


<p> In other words, we start with $a_n$, multiply by $x$, add $a_{n-1}$, multiply by $x$, and so on, until we reach $a_0$.<a name="footnote_link_2-16" class="footnote_link" href="#footnote_2-16">16</a>

<p> Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from $a_0$ through $a_n$.

<div id="scheme-ex-define-horner-eval">
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))
</div>
<script>
makeEditable("scheme-ex-define-horner-eval");
addDep("scheme-ex-define-horner-eval", ["scheme-define-accumulate"]);

addOutput("scheme-ex-define-horner-eval");
editorOf["scheme-ex-define-horner-eval"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-horner-eval"),
    "#t",
    "(equal? 79 (horner-eval 2 '(1 3 0 5 0 1)))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-horner-eval-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-horner-eval-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-horner-eval-output").append(res.slice(0,-1));
  });
});
/*
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) 
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))
*/
</script>

<p> For example, to compute $1 + 3x + 5x^3 + x^5$ at $x = 2$ you would evaluate

<div id="scheme-horner-eval-poly-at-2">
(horner-eval 2 (list 1 3 0 5 0 1))
</div>
<script>
no_output_frozen_prompt("scheme-horner-eval-poly-at-2");
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.35:</b> Redefine <tt>count-leaves</tt> from
section 2-2-2 as an accumulation:

<div id="scheme-ex-define-count-leaves-with-accumulate">
(define (count-leaves t)
  (accumulate 'your 'answer (map 'your 'answer)))
</div>
<script>
makeEditable("scheme-ex-define-count-leaves-with-accumulate");
addDep("scheme-ex-define-count-leaves-with-accumulate", ["scheme-define-accumulate", "scheme-define-map"]);

addOutput("scheme-ex-define-count-leaves-with-accumulate");
editorOf["scheme-ex-define-count-leaves-with-accumulate"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-count-leaves-with-accumulate"),
    "#t",
    "(equal? 4 (count-leaves '((1 2) (1 2))))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-count-leaves-with-accumulate-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-count-leaves-with-accumulate-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-count-leaves-with-accumulate-output").append(res.slice(0,-1));
  });
});
/*
(define (count-leaves t)
  (accumulate + 0 (map (lambda (x)
                         (if (pair? x)
                             (count-leaves x)
                             1))
                         t)))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.36:</b> The procedure <tt>accumulate-n</tt> is similar to <tt>accumulate</tt> except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if <tt>s</tt> is a sequence containing four sequences, <tt>((1 2 3) (4 5 6) (7 8 9) (10 11 12)),</tt> then the value of <tt>(accumulate-n + 0 s)</tt> should be the sequence <tt>(22 26 30)</tt>. Fill in the missing expressions in the following definition of <tt>accumulate-n</tt>:

<div id="scheme-ex-define-accumulate-n">
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init 'your-answer)
            (accumulate-n op init 'your-answer))))
</div>
<script>
makeEditable("scheme-ex-define-accumulate-n");
addDep("scheme-ex-define-accumulate-n", ["scheme-define-accumulate", "scheme-define-map"]);

addOutput("scheme-ex-define-accumulate-n");
editorOf["scheme-ex-define-accumulate-n"].setOption("onBlur", function(){

  var code = "{0} \n (and {1} {2})".format(
    getDependedOnCode("scheme-ex-define-accumulate-n"),
    "#t",
    "(equal? '(22 26 30) (accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12))))"
  );

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true\n") {
      $_("scheme-ex-define-accumulate-n-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-accumulate-n-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
    }
    $_("scheme-ex-define-accumulate-n-output").append(res.slice(0,-1));
  });
});
/*
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))
*/
</script>
</div>

<p>

<div class="exercise">
<b> Exercise 2.37 </b>.

<p> Suppose we represent vectors v = (v_i) as sequences of numbers, and matrices m = (m_(ij)) as sequences of vectors (the rows of the matrix). For example, the matrix


$$ 
\left[ \begin{array}{cccc}
1 &amp; 2 &amp; 3 &amp; 4 \\
4 &amp; 5 &amp; 6 &amp; 6 \\
6 &amp; 7 &amp; 8 &amp; 9 \end{array} \right]
$$


<p> is represented as the sequence <tt>((1 2 3 4) (4 5 6 6) (6 7 8 9))</tt>. With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

<ul>
<li>
<tt>(dot-product v w)</tt> returns the sum $\sum_i v_i w_i$
</li>
<li>
<tt>(matrix-*-vector m w)</tt> returns the vector $t$, where $t_i =  \sum_j m_{ij} v_j$
</li>
<li>
<tt>(matrix-*-matrix m n)</tt> returns the matrix $p$, where $p_{ij} = \sum_k m_{ik} n_{kj}$
</li>
<li>
<tt>(transpose m)</tt> returns the matrix $n$, where $n_{ij} = m_{ji}$
</li>
</ul>

<p> We can define the dot product as<a name="footnote_link_2-17" class="footnote_link" href="#footnote_2-17">17</a>

<div id="scheme-define-dot-product">
(define (dot-product v w)
  'sorry-map-is-not-implemented-yet
  (accumulate + 0 (map * v w)))
</div>
<script>
prompt("scheme-define-dot-product");
</script>

<p> Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure <tt>accumulate-n</tt> is defined in Exercise 2-36.)

<div id="scheme-ex-define-matrix-operations">
(define (matrix-*-vector m v)
  (map 'your-answer-here m))

(define (transpose mat)
  (accumulate-n 'your 'answer mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map 'your-answer-here m)))
</div>
<script>
prompt("scheme-ex-define-matrix-operations");
</script>
</div>

<div class="exercise">
<p> <b>Exercise 2.38:</b> The <tt>accumulate</tt> procedure is also known as <tt>fold-right</tt>, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a <tt>fold-left</tt>, which is similar to <tt>fold-right</tt>, except that it combines elements working in the opposite direction:

<div id="scheme-define-fold-left">
(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))
</div>
<script>
prompt("scheme-define-fold-left");
</script>

<p> What are the values of

<div id="scheme-ex-foldr-div" class='static'>
(fold-right / 1 (list 1 2 3))
</div>
<script> 
answer("scheme-ex-foldr-div", 1.5);
</script>

<div id="scheme-ex-foldl-div" class='static'>
(fold-left / 1 (list 1 2 3)) ;please give the inverse, we haven't implemented rational numbers yet!
</div>
<script> 
answer("scheme-ex-foldl-div", 6);
</script>

<div id="scheme-ex-foldr-list" class='static'>
(fold-right list nil (list 1 2 3))
</div>
<script> 
answer("scheme-ex-foldr-list", "(1 (2 (3 ())))");
</script>

<div id="scheme-ex-foldl-list" class='static'>
(fold-left list nil (list 1 2 3))
</div>
<script> 
answer("scheme-ex-foldl-list", "(((() 1) 2) 3)");
</script>

<p> Give a property that <tt>op</tt> should satisfy to guarantee that <tt>fold-right</tt> and <tt>fold-left</tt> will produce the same values for any sequence.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.39:</b> Complete the following definitions of <tt>reverse</tt> (Exercise 2-18) in terms of <tt>fold-right</tt> and <tt>fold-left</tt> from Exercise 2-38:

<div id="scheme-ex-define-reverse-with-foldr">
(define (reverse sequence)
  (fold-right (lambda (x y) <??>) nil sequence))

(define (reverse sequence)
  (fold-left (lambda (x y) <??>) nil sequence))
</div>
<script>
prompt("scheme-ex-define-reverse-with-foldr");
</script>
</div>

<h4> Nested Mappings </h4> 

<p> We can extend the sequence paradigm to include many computations that are commonly expressed using nested loops.<a name="footnote_link_2-18" class="footnote_link" href="#footnote_2-18">18</a> Consider this problem: Given a positive integer n, find all ordered pairs of distinct positive integers i and j, where 1 &lt;= j&lt; i&lt;= n, such that i + j is prime. For example, if n is 6, then the pairs are the following:

$$ 
\begin{array}{c|ccc}
i &amp; 2 &amp; 3 &amp; 4 &amp; 4 &amp; 5 &amp; 6 &amp; 6 \\
j &amp; 1 &amp; 2 &amp; 1 &amp; 3 &amp; 2 &amp; 1 &amp; 5 \\
\hline \\
i+j &amp; 3 &amp; 5 &amp; 5 &amp; 7 &amp; 7 &amp; 7 &amp; 11 \end{array}
$$


<p> A natural way to organize this computation is to generate the sequence of all ordered pairs of positive integers less than or equal to $n$, filter to select those pairs whose sum is prime, and then, for each pair $(i, j)$ that passes through the filter, produce the triple $(i,j,i+j)$.

<p> Here is a way to generate the sequence of pairs: For each integer $i &lt;= n$, enumerate the integers $j&lt;i$, and for each such $i$ and $j$ generate the pair $(i,j)$. In terms of sequence operations, we map along the sequence <tt>(enumerate-interval 1 n)</tt>. For each $i$ in this sequence, we map along the sequence <tt>(enumerate-interval 1 (- i 1))</tt>. For each $j$ in this latter sequence, we generate the pair <tt>(list i j)</tt>. This gives us a sequence of pairs for each $i$. Combining all the sequences for all the $i$ (by accumulating with <tt>append</tt>) produces the required sequence of pairs:<a name="footnote_link_2-19" class="footnote_link" href="#footnote_2-19">19</a>

<div id="scheme-define-pairs-sum-to-prime">
(define n 6)

(accumulate append
            nil
            (map (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))
</div>
<script>
prompt("scheme-define-pairs-sum-to-prime", ["scheme-define-accumulate", "scheme-define-map", "scheme-define-enumerate-interval"]);
</script>

<p> The combination of mapping and accumulating with <tt>append</tt> is so common in this sort of program that we will isolate it as a separate procedure:

<div id="scheme-define-flatmap">
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
</div>
<script>
prompt("scheme-define-flatmap", ["scheme-define-accumulate", "scheme-define-map"]);
</script>

<p> Now filter this sequence of pairs to find those whose sum is prime. The filter predicate is called for each element of the sequence; its argument is a pair and it must extract the integers from the pair. Thus, the predicate to apply to each element in the sequence is

<div id="scheme-define-prime?">
(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))
</div>
<script>
hidden_prompt("scheme-define-prime?");
</script>

<div id="scheme-define-prime-sum?">
(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))
</div>
<script>
prompt("scheme-define-prime-sum?", ["scheme-define-prime?"]);
</script>

<p> Finally, generate the sequence of results by mapping over the filtered pairs using the following procedure, which constructs a triple consisting of the two elements of the pair along with their sum:

<div id="scheme-define-make-pair-sum">
(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
</div>
<script>
prompt("scheme-define-make-pair-sum");
</script>

<p> Combining all these steps yields the complete procedure:

<div id="scheme-define-prime-sum-pairs">
(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))))
</div>
<script>
prompt("scheme-define-prime-sum-pairs", ["scheme-define-map", "scheme-define-filter", "scheme-define-flatmap", "scheme-define-enumerate-interval"]);
</script>

<p> Nested mappings are also useful for sequences other than those that enumerate intervals. Suppose we wish to generate all the permutations of a set $S$; that is, all the ways of ordering the items in the set. For instance, the permutations of $\{1,2,3\}$ are $\{1,2,3\}$, $\{1,3,2\}$, $\{2,1,3\}$, $\{2,3,1\}$, $\{3,1,2\}$, and $\{3,2,1\}$. Here is a plan for generating the permutations of $S$: For each item $x$ in $S$, recursively generate the sequence of permutations of $S - x$,<a name="footnote_link_2-20" class="footnote_link" href="#footnote_2-20">20</a> and adjoin $x$ to the front of each one. This yields, for each x in S, the sequence of permutations of S that begin with $x$. Combining these sequences for all $x$ gives all the permutations of $S$:<a name="footnote_link_2-21" class="footnote_link" href="#footnote_2-21">21</a>

<div id="scheme-define-permutations">
(define (permutations s)
  (if (null? s)                    ; empty set?
      (list nil)                   ; sequence containing empty set
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))
</div>
<script>
prompt("scheme-define-permutations", ["scheme-define-map", "scheme-define-flatmap", "scheme-define-remove"]);
</script>

<p> Notice how this strategy reduces the problem of generating permutations of S to the problem of generating the permutations of sets with fewer elements than S. In the terminal case, we work our way down to the empty list, which represents a set of no elements. For this, we generate <tt>(list nil)</tt>, which is a sequence with one item, namely the set with no elements. The <tt>remove</tt> procedure used in <tt>permutations</tt> returns all the items in a given sequence except for a given item. This can be expressed as a simple filter:

<div id="scheme-define-remove">
(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))
</div>
<script>
prompt("scheme-define-remove", ["scheme-define-filter"]);
</script>

<p>

<div class="exercise">
<p> <b>Exercise 2.40:</b> Define a procedure <tt>unique-pairs</tt> that, given an integer $n$, generates the sequence of pairs $(i,j)$ with $1 &le; j&lt; i &le; n$. Use <tt>unique-pairs</tt> to simplify the definition of <tt>prime-sum-pairs</tt> given above. 
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.41:</b> Write a procedure to find all ordered triples of distinct positive integers $i$, $j$, and $k$ less than or equal to a given integer $n$ that sum to a given integer $s$.
</div>

<p>

<div class="exercise">

<p> <b>Exercise 2.42:</b> The ``eight-queens puzzle'' asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). 

<p> <img class='center' src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-23.gif'>

<p style="text-align:center"> <b>Figure 2.8:</b> A solution to the eight-queens puzzle.

<p> One possible solution is shown in Figure 2-8. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed $k - 1$ queens, we must place the $k^{th}$ queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place $k - 1$ queens in the first $k - 1$ columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the $k^{th}$ column is safe with respect to the other queens. This produces the sequence of all ways to place $k$ queens in the first $k$ columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

<p> We implement this solution as a procedure <tt>queens</tt>, which returns a sequence of all solutions to the problem of placing n queens on an $n \times n$ chessboard. <tt>queens</tt> has an internal procedure <tt>queen-cols</tt> that returns the sequence of all ways to place queens in the first k columns of the board.

<div id="scheme-define-queens">
(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))
</div>
<script>
prompt("scheme-define-queens", ["scheme-define-filter", "scheme-define-map", "scheme-define-flatmap"]);
</script>

<p> In this procedure <tt>rest-of-queens</tt> is a way to place $k - 1$ queens in the first $k - 1$ columns, and <tt>new-row</tt> is a proposed row in which to place the queen for the $k^{th}$ column. Complete the program by implementing the representation for sets of board positions, including the procedure <tt>adjoin-position</tt>, which adjoins a new row-column position to a set of positions, and <tt>empty-board</tt>, which represents an empty set of positions. You must also write the procedure <tt>safe?</tt>, which determines for a set of positions, whether the queen in the kth column is safe with respect to the others. (Note that we need only check whether the new queen is safe---the other queens are already guaranteed safe with respect to each other.)
 </div>

<p>

<div class="exercise">
<p> <b>Exercise 2.43:</b> Louis Reasoner is having a terrible time doing Exercise 2-42. His <tt>queens</tt> procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the $6 \times 6$ case.)  When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the <tt>flatmap</tt>, writing it as

<div id="scheme-louise-queens-flatmap">
(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))
</div>
<script>
no_output_frozen_prompt("scheme-louise-queens-flatmap");
</script>

<p> Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's program to solve the eight-queens puzzle, assuming that the program in Exercise 2-42 solves the puzzle in time T.
</div>


<h3> Example: A Picture Language </h3> 

<p> This section presents a simple language for drawing pictures that illustrates the power of data abstraction and closure, and also exploits higher-order procedures in an essential way. The language is designed to make it easy to experiment with patterns such as the ones in Figure 2-9, which are composed of repeated elements that are shifted and scaled.<a name="footnote_link_2-22" class="footnote_link" href="#footnote_2-22">22</a> In this language, the data objects being combined are represented as procedures rather than as list structure. Just as <tt>cons</tt>, which satisfies the closure property, allowed us to easily build arbitrarily complicated list structure, the operations in this language, which also satisfy the closure property, allow us to easily build arbitrarily complicated patterns.

<p>

<div class="figure">
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-24.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-25.gif'>

<p> <b>Figure 2.9:</b> Designs generated with the picture language.
</div>

<h4> The picture language </h4> 

<p> When we began our study of programming in section 1-1, we emphasized the importance of describing a language by focusing on the language's primitives, its means of combination, and its means of abstraction. We'll follow that framework here.

<p> Part of the elegance of this picture language is that there is only one kind of element, called a <tt>painter</tt> . A painter draws an image that is shifted and scaled to fit within a designated parallelogram-shaped frame. For example, there's a primitive painter we'll call <tt>wave</tt> that makes a crude line drawing, as shown in Figure 2-10. The actual shape of the drawing depends on the frame---all four images in Figure 2-10 are produced by the same <tt>wave</tt> painter, but with respect to four different frames. Painters can be more elaborate than this: The primitive painter called <tt>rogers</tt> paints a picture of MIT's founder, William Barton Rogers, as shown in Figure 2-11.<a name="footnote_link_2-23" class="footnote_link" href="#footnote_2-23">23</a> The four images in Figure 2-11 are drawn with respect to the same four frames as the <tt>wave</tt> images in Figure 2-10.

<p> To combine images, we use various operations that construct new painters from given painters. For example, the <tt>beside</tt> operation takes two painters and produces a new, compound painter that draws the first painter's image in the left half of the frame and the second painter's image in the right half of the frame. Similarly, <tt>below</tt> takes two painters and produces a compound painter that draws the first painter's image below the second painter's image. Some operations transform a single painter to produce a new painter. For example, <tt>flip-vert</tt> takes a painter and produces a painter that draws its image upside-down, and <tt>flip-horiz</tt> produces a painter that draws the original painter's image left-to-right reversed.

<div class="figure">
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-26.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-27.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-28.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-29.gif'>

<p> <b>Figure 2.10:</b> Images produced by the <tt>wave</tt> painter, with respect to four different frames. The frames, shown with dotted lines, are not part of the images. 
</div>

<p>

<div class="figure">
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-30.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-31.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-32.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-33.gif'>

<p> <b>Figure 2.11:</b> Images of William Barton Rogers, founder and first president of MIT, painted with respect to the same four frames as in Figure 2-10 (original image reprinted with the permission of the MIT Museum). 
</div>

<p> Figure 2-12 shows the drawing of a painter called <tt>wave4</tt> that is built up in two stages starting from <tt>wave</tt>:

<div id="scheme-define-wave-2-4">
(define wave2 (beside wave (flip-vert wave)))
(define wave4 (below wave2 wave2))
</div>
<script>
prompt("scheme-define-wave-2-4");
</script>

<div class='figure'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-34.gif'>
<img src='http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-35.gif'>

<p> <b>Figure 2.12:</b> Creating a complex figure, starting from the <tt>wave</tt> painter of Figure 2-10.
</div>

<p> In building up a complex image in this manner we are exploiting the fact that painters are closed under the language's means of combination. The <tt>beside</tt> or <tt>below</tt> of two painters is itself a painter; therefore, we can use it as an element in making more complex painters. As with building up list structure using <tt>cons</tt>, the closure of our data under the means of combination is crucial to the ability to create complex structures while using only a few operations.

<p> Once we can combine painters, we would like to be able to abstract typical patterns of combining painters. We will implement the painter operations as Scheme procedures. This means that we don't need a special abstraction mechanism in the picture language: Since the means of combination are ordinary Scheme procedures, we automatically have the capability to do anything with painter operations that we can do with procedures. For example, we can abstract the pattern in <tt>wave4</tt> as

<div id="scheme-define-flipped-pairs">
(define (flipped-pairs painter)
  (let ((painter2 (beside painter (flip-vert painter))))
    (below painter2 painter2)))
</div>
<script>
prompt("scheme-define-flipped-pairs");
</script>

<p> and define <tt>wave4</tt> as an instance of this pattern:

<div id="scheme-define-wave4">
(define wave4 (flipped-pairs wave))
</div>
<script>
prompt("scheme-define-wave4");
</script>

<p> We can also define recursive operations. Here's one that makes painters split and branch towards the right as shown in figures Figure 2-13 and Figure 2-14:

<div id="scheme-define-right-split">
(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))
</div>
<script>
prompt("scheme-define-right-split");
</script>

<p>

<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-36.gif">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-37.gif">

<p> <b>Figure 2.13:</b> Recursive plans for <tt>right-split</tt> and <tt>corner-split</tt>.
</div>

<p> We can produce balanced patterns by branching upwards as well as towards the right (see Exercise 2-44 and figures Figure 2-13 and Figure 2-14):

<div id="scheme-ex-define-corner-split">
(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right right))
              (corner (corner-split painter (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right corner))))))
</div>
<script>
prompt("scheme-ex-define-corner-split");
</script>

<p>

<div id="scheme-right-split-wave-rogers-4">
(right-split wave 4)         
(right-split rogers 4)
</div>
<script>
prompt("scheme-right-split-wave-rogers-4");
</script>
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-38.gif">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-39.gif">

<div id="scheme-corner-split-wave-rogers-4">
(corner-split wave 4)        
(corner-split rogers 4)
</div>
<script>
prompt("scheme-corner-split-wave-rogers-4");
</script>
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-40.gif">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-41.gif">
<p> <b>Figure 2.14:</b> The recursive operations <tt>right-split</tt> and <tt>corner-split</tt> applied to the painters <tt>wave</tt> and <tt>rogers</tt>. Combining four <tt>corner-split</tt> figures produces symmetric <tt>square-limit</tt> designs as shown in Figure 2-9.

<p> By placing four copies of a <tt>corner-split</tt> appropriately, we obtain a pattern called <tt>square-limit</tt>, whose application to <tt>wave</tt> and <tt>rogers</tt> is shown in Figure 2-9:

<div id="scheme-define-square-limit">
(define (square-limit painter n)
  (let ((quarter (corner-split painter n)))
    (let ((half (beside (flip-horiz quarter) quarter)))
      (below (flip-vert half) half))))
</div>
<script>
prompt("scheme-define-square-limit");
</script>

<p>

<div class="exercise">
<p> <b>Exercise 2.44:</b> Define the procedure <tt>up-split</tt> used by <tt>corner-split</tt>. It is similar to <tt>right-split</tt>, except that it switches the roles of <tt>below</tt> and <tt>beside</tt>.
 </div>

<h4> Higher-order operations </h4> 

<p> In addition to abstracting patterns of combining painters, we can work at a higher level, abstracting patterns of combining painter operations. That is, we can view the painter operations as elements to manipulate and can write means of combination for these elements---procedures that take painter operations as arguments and create new painter operations.

<p> For example, <tt>flipped-pairs</tt> and <tt>square-limit</tt> each arrange four copies of a painter's image in a square pattern; they differ only in how they orient the copies. One way to abstract this pattern of painter combination is with the following procedure, which takes four one-argument painter operations and produces a painter operation that transforms a given painter with those four operations and arranges the results in a square. <tt>Tl</tt>, <tt>tr</tt>, <tt>bl</tt>, and <tt>br</tt> are the transformations to apply to the top left copy, the top right copy, the bottom left copy, and the bottom right copy, respectively.

<div id="scheme-define-square-of-four">
(define (square-of-four tl tr bl br)
  (lambda (painter)
    (let ((top (beside (tl painter) (tr painter)))
          (bottom (beside (bl painter) (br painter))))
      (below bottom top))))
</div>
<script>
prompt("scheme-define-square-of-four");
</script>

<p> Then <tt>flipped-pairs</tt> can be defined in terms of <tt>square-of-four</tt> as follows:<a name="footnote_link_2-24" class="footnote_link" href="#footnote_2-24">24</a>

<div id="scheme-define-flipped-pairs-with-square-of-four">
(define (flipped-pairs painter)
  (let ((combine4 (square-of-four identity flip-vert
                                  identity flip-vert)))
    (combine4 painter)))
</div>
<script>
prompt("scheme-define-flipped-pairs-with-square-of-four");
</script>


<p> and <tt>square-limit</tt> can be expressed as<a name="footnote_link_2-25" class="footnote_link" href="#footnote_2-25">25</a>

<div id="scheme-define-square-limit-with-square-of-four">
(define (square-limit painter n)
  (let ((combine4 (square-of-four flip-horiz identity
                                  rotate180 flip-vert)))
    (combine4 (corner-split painter n))))
</div>
<script>
prompt("scheme-define-square-limit-with-square-of-four");
</script>

<div class="exercise">
<p> <b>Exercise 2.45:</b> <tt>right-split</tt> and <tt>up-split</tt> can be expressed as instances of a general splitting operation. Define a procedure <tt>split</tt> with the property that evaluating

<div id="scheme-define-right-up-split-with-split">
(define right-split (split beside below))
(define up-split (split below beside))
</div>
<script>
prompt("scheme-define-right-up-split-with-split");
</script>

<p> produces procedures <tt>right-split</tt> and <tt>up-split</tt> with the same behaviors as the ones already defined.
 </div>

<h4> Frames </h4> 

<p> Before we can show how to implement painters and their means of combination, we must first consider frames. A frame can be described by three vectors---an origin vector and two edge vectors. The origin vector specifies the offset of the frame's origin from some absolute origin in the plane, and the edge vectors specify the offsets of the frame's corners from its origin. If the edges are perpendicular, the frame will be rectangular. Otherwise the frame will be a more general parallelogram.

<p> Figure 2-15 shows a frame and its associated vectors. In accordance with data abstraction, we need not be specific yet about how frames are represented, other than to say that there is a constructor <tt>make-frame</tt>, which takes three vectors and produces a frame, and three corresponding selectors <tt>origin-frame</tt>, <tt>edge1-frame</tt>, and <tt>edge2-frame</tt> (see Exercise 2-47).

<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch2-Z-G-42.gif">
<p> <b>Figure 2.15:</b> A frame is described by three vectors -- an origin and two edges.
</div>

<p> We will use coordinates in the unit square $(0 &le; x,y &le; 1)$ to specify images. With each frame, we associate a <tt>frame coordinate map</tt> , which will be used to shift and scale images to fit the frame. The map transforms the unit square into the frame by mapping the vector v = (x,y) to the vector sum

$$
\text{Origin}(\text{Frame}) + x \cdot \text{Edge}_1(\text{Frame}) + y \cdot \text{Edge}_2(\text{Frame})
$$


<p> For example, (0,0) is mapped to the origin of the frame, (1,1) to the vertex diagonally opposite the origin, and (0.5,0.5) to the center of the frame. We can create a frame's coordinate map with the following procedure:<a name="footnote_link_2-26" class="footnote_link" href="#footnote_2-26">26</a>

<div id="scheme-define-frame-coord-map">
(define (frame-coord-map frame)
  (lambda (v)
    (add-vect
     (origin-frame frame)
     (add-vect (scale-vect (xcor-vect v)
                           (edge1-frame frame))
               (scale-vect (ycor-vect v)
                           (edge2-frame frame))))))
</div>
<script>
prompt("scheme-define-frame-coord-map");
</script>

<p> Observe that applying <tt>frame-coord-map</tt> to a frame returns a procedure that, given a vector, returns a vector. If the argument vector is in the unit square, the result vector will be in the frame. For example,

<div id="scheme-frame-coord-map-a-frame-0-0">
((frame-coord-map a-frame) (make-vect 0 0))
</div>
<script>
no_output_frozen_prompt("scheme-frame-coord-map-a-frame-0-0");
</script>

<p> returns the same vector as

<div id="scheme-origin-frame-a-frame">
(origin-frame a-frame)
</div>
<script>
prompt("scheme-origin-frame-a-frame");
</script>

<div class="exercise">
<p> <b>Exercise 2.46:</b> A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate. Implement a data abstraction for vectors by giving a constructor <tt>make-vect</tt> and corresponding selectors <tt>xcor-vect</tt> and <tt>ycor-vect</tt>. In terms of your selectors and constructor, implement procedures <tt>add-vect</tt>, <tt>sub-vect</tt>, and <tt>scale-vect</tt> that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar:

\begin{align} 
(x_1, y_1) + (x_2, y_2) &amp;= (x_1 + x_2, y_1 + y_2) \\
(x_1, y_1) - (x_2, y_2) &amp;= (x_1 - x_2, y_1 - y_2) \\
             s \cdot (x, y) &amp;= (sx, sy)
\end{align}
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.47:</b> Here are two possible constructors for frames:

<div id="scheme-ex-define-make-frame">
(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))
</div>
<script>
prompt("scheme-ex-define-make-frame");
</script>

<p> For each constructor supply the appropriate selectors to produce an implementation for frames.
</div>

<h4> Painters </h4> 

<p> A painter is represented as a procedure that, given a frame as argument, draws a particular image shifted and scaled to fit the frame. That is to say, if <tt>p</tt> is a painter and <tt>f</tt> is a frame, then we produce <tt>p</tt>'s image in <tt>f</tt> by calling <tt>p</tt> with <tt>f</tt> as argument.

<p> The details of how primitive painters are implemented depend on the particular characteristics of the graphics system and the type of image to be drawn. For instance, suppose we have a procedure <tt>draw-line</tt> that draws a line on the screen between two specified points. Then we can create painters for line drawings, such as the <tt>wave</tt> painter in Figure 2-10, from lists of line segments as follows:<a name="footnote_link_2-27" class="footnote_link" href="#footnote_2-27">27</a>

<div id="scheme-ex-define-segments-to-painter">
(define (segments->painter segment-list)
  (lambda (frame)
    (for-each
     (lambda (segment)
       (draw-line
        ((frame-coord-map frame) (start-segment segment))
        ((frame-coord-map frame) (end-segment segment))))
     segment-list)))
</div>
<script>
prompt("scheme-ex-define-segments-to-painter");
</script>

<p> The segments are given using coordinates with respect to the unit square. For each segment in the list, the painter transforms the segment endpoints with the frame coordinate map and draws a line between the transformed points.

<p> Representing painters as procedures erects a powerful abstraction barrier in the picture language. We can create and intermix all sorts of primitive painters, based on a variety of graphics capabilities. The details of their implementation do not matter. Any procedure can serve as a painter, provided that it takes a frame as argument and draws something scaled to fit the frame.<a name="footnote_link_2-28" class="footnote_link" href="#footnote_2-28">28</a>

<div class="exercise">
<p> <b>Exercise 2.48:</b> A directed line segment in the plane can be represented as a pair of vectors---the vector running from the origin to the start-point of the segment, and the vector running from the origin to the end-point of the segment. Use your vector representation from Exercise 2-46 to define a representation for segments with a constructor <tt>make-segment</tt> and selectors <tt>start-segment</tt> and <tt>end-segment</tt>.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.49:</b> Use <tt>segments->painter</tt> to define the following primitive painters:

<ul>
<li>
The painter that draws the outline of the designated frame.
</li>

<li>
The painter that draws an ``X'' by connecting opposite corners of the frame.
</li>

<li>
The painter that draws a diamond shape by connecting the midpoints of the sides
of the frame.
</li>

<li>
The <tt>wave</tt> painter.
</li>
</ul>
</div>

<h4> Transforming and combining painters </h4> 

<p> An operation on painters (such as <tt>flip-vert</tt> or <tt>beside</tt>) works by creating a painter that invokes the original painters with respect to frames derived from the argument frame. Thus, for example, <tt>flip-vert</tt> doesn't have to know how a painter works in order to flip it---it just has to know how to turn a frame upside down: The flipped painter just uses the original painter, but in the inverted frame.

<p> Painter operations are based on the procedure <tt>transform-painter</tt>, which takes as arguments a painter and information on how to transform a frame and produces a new painter. The transformed painter, when called on a frame, transforms the frame and calls the original painter on the transformed frame. The arguments to <tt>transform-painter</tt> are points (represented as vectors) that specify the corners of the new frame: When mapped into the frame, the first point specifies the new frame's origin and the other two specify the ends of its edge vectors. Thus, arguments within the unit square specify a frame contained within the original frame.

<div id="scheme-define-transform-painter">
(define (transform-painter painter origin corner1 corner2)
  (lambda (frame)
    (let ((m (frame-coord-map frame)))
      (let ((new-origin (m origin)))
        (painter
         (make-frame new-origin
                     (sub-vect (m corner1) new-origin)
                     (sub-vect (m corner2) new-origin)))))))
</div>
<script>
prompt("scheme-define-transform-painter");
</script>

<p> Here's how to flip painter images vertically:

<div id="scheme-define-flip-vert">
(define (flip-vert painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)   ; new <tt>origin</tt>
                     (make-vect 1.0 1.0)   ; new end of <tt>edge1</tt>
                     (make-vect 0.0 0.0))) ; new end of <tt>edge2</tt>
</div>
<script>
prompt("scheme-define-flip-vert");
</script>

<p> Using <tt>transform-painter</tt>, we can easily define new transformations. For example, we can define a painter that shrinks its image to the upper-right quarter of the frame it is given:

<div id="scheme-define-shrink-to-upper-right">
(define (shrink-to-upper-right painter)
  (transform-painter painter
                     (make-vect 0.5 0.5)
                     (make-vect 1.0 0.5)
                     (make-vect 0.5 1.0)))
</div>
<script>
prompt("scheme-define-shrink-to-upper-right");
</script>

<p> Other transformations rotate images counterclockwise by 90 degrees<a name="footnote_link_2-29" class="footnote_link" href="#footnote_2-29">29</a>

<div id="scheme-define-rotate90">
(define (rotate90 painter)
  (transform-painter painter
                     (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0)))
</div>
<script>
prompt("scheme-define-rotate90");
</script>

<p> or squash images towards the center of the frame:<a name="footnote_link_2-30" class="footnote_link" href="#footnote_2-30">30</a>

<div id="scheme-define-squash-inwards">
(define (squash-inwards painter)
  (transform-painter painter
                     (make-vect 0.0 0.0)
                     (make-vect 0.65 0.35)
                     (make-vect 0.35 0.65)))
</div>
<script>
prompt("scheme-define-squash-inwards");
</script>

<p> Frame transformation is also the key to defining means of combining two or more painters. The <tt>beside</tt> procedure, for example, takes two painters, transforms them to paint in the left and right halves of an argument frame respectively, and produces a new, compound painter. When the compound painter is given a frame, it calls the first transformed painter to paint in the left half of the frame and calls the second transformed painter to paint in the right half of the frame:

<div id="scheme-define-beside">
(define (beside painter1 painter2)
  (let ((split-point (make-vect 0.5 0.0)))
    (let ((paint-left
           (transform-painter painter1
                              (make-vect 0.0 0.0)
                              split-point
                              (make-vect 0.0 1.0)))
          (paint-right
           (transform-painter painter2
                              split-point
                              (make-vect 1.0 0.0)
                              (make-vect 0.5 1.0))))
      (lambda (frame)
        (paint-left frame)
        (paint-right frame)))))
</div>
<script>
prompt("scheme-define-beside");
</script>

<p> Observe how the painter data abstraction, and in particular the representation of painters as procedures, makes <tt>beside</tt> easy to implement. The <tt>beside</tt> procedure need not know anything about the details of the component painters other than that each painter will draw something in its designated frame.

<div class="exercise">
<p> <b>Exercise 2.50:</b> Define the transformation <tt>flip-horiz</tt>, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.51:</b> Define the <tt>below</tt> operation for painters. <tt>Below</tt> takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define <tt>below</tt> in two different ways---first by writing a procedure that is analogous to the <tt>beside</tt> procedure given above, and again in terms of <tt>beside</tt> and suitable rotation operations (from Exercise 2-50).
</div>

<h4> Levels of language for robust design </h4> 

<p> The picture language exercises some of the critical ideas we've introduced about abstraction with procedures and data. The fundamental data abstractions, painters, are implemented using procedural representations, which enables the language to handle different basic drawing capabilities in a uniform way. The means of combination satisfy the closure property, which permits us to easily build up complex designs. Finally, all the tools for abstracting procedures are available to us for abstracting means of combination for painters.

<p> We have also obtained a glimpse of another crucial idea about languages and program design. This is the approach of <tt>stratified design</tt> , the notion that a complex system should be structured as a sequence of levels that are described using a sequence of languages. Each level is constructed by combining parts that are regarded as primitive at that level, and the parts constructed at each level are used as primitives at the next level. The language used at each level of a stratified design has primitives, means of combination, and means of abstraction appropriate to that level of detail.

<p> Stratified design pervades the engineering of complex systems. For example, in computer engineering, resistors and transistors are combined (and described using a language of analog circuits) to produce parts such as and-gates and or-gates, which form the primitives of a language for digital-circuit design.<a name="footnote_link_2-31" class="footnote_link" href="#footnote_2-31">31</a> These parts are combined to build processors, bus structures, and memory systems, which are in turn combined to form computers, using languages appropriate to computer architecture. Computers are combined to form distributed systems, using languages appropriate for describing network interconnections, and so on.

<p> As a tiny example of stratification, our picture language uses primitive elements (primitive painters) that are created using a language that specifies points and lines to provide the lists of line segments for <tt>segments->painter</tt>, or the shading details for a painter like <tt>rogers</tt>. The bulk of our description of the picture language focused on combining these primitives, using geometric combiners such as <tt>beside</tt> and <tt>below</tt>. We also worked at a higher level, regarding <tt>beside</tt> and <tt>below</tt> as primitives to be manipulated in a language whose operations, such as <tt>square-of-four</tt>, capture common patterns of combining geometric combiners.

<p> Stratified design helps make programs <tt>robust</tt> , that is, it makes it likely that small changes in a specification will require correspondingly small changes in the program. For instance, suppose we wanted to change the image based on <tt>wave</tt> shown in Figure 2-9. We could work at the lowest level to change the detailed appearance of the <tt>wave</tt> element; we could work at the middle level to change the way <tt>corner-split</tt> replicates the <tt>wave</tt>; we could work at the highest level to change how <tt>square-limit</tt> arranges the four copies of the corner. In general, each level of a stratified design provides a different vocabulary for expressing the characteristics of the system, and a different kind of ability to change it.

<div class="exercise">
<p> <b>Exercise 2.52:</b> Make changes to the square limit of <tt>wave</tt> shown in Figure 2-9 by working at each of the levels described above. In particular:

<ul>
<li>
Add some segments to the primitive <tt>wave</tt> painter of Exercise 2-49 (to add a smile, for example).
</li>

<li>
Change the pattern constructed by <tt>corner-split</tt> (for example, by using only one copy of the <tt>up-split</tt> and <tt>right-split</tt> images instead of two).
</li>

<li>
Modify the version of <tt>square-limit</tt> that uses <tt>square-of-four</tt> so as to assemble the corners in a different pattern. (For example, you might make the big Mr. Rogers look outward from each corner of the square.)
</li>
</ul>
</div>

<br>
<br>

<hr>

<div id="footnotes">
<h3 id='Notes'> Notes </h3>

<div id="footnote_2-6" class="footnote">  
<p> <a href="#footnote_link_2-6" class="footnote_backlink">6</a> The use of the word ``closure'' here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The Lisp community also (unfortunately) uses the word ``closure'' to describe a totally unrelated concept: A closure is an implementation technique for representing procedures with free variables. We do not use the word ``closure'' in this second sense in this book.
</div>

<div id="footnote_2-7" class="footnote">  
<p> <a href="#footnote_link_2-7" class="footnote_backlink">7</a> The notion that a means of combination should satisfy closure is a straightforward idea. Unfortunately, the data combiners provided in many popular programming languages do not satisfy closure, or make closure cumbersome to exploit. In Fortran or Basic, one typically combines data elements by assembling them into arrays---but one cannot form arrays whose elements are themselves arrays. Pascal and C admit structures whose elements are structures. However, this requires that the programmer manipulate pointers explicitly, and adhere to the restriction that each field of a structure can contain only elements of a prespecified form. Unlike Lisp with its pairs, these languages have no built-in general-purpose glue that makes it easy to manipulate compound data in a uniform way. This limitation lies behind Alan Perlis's comment in his foreword to this book: ``In Pascal the plethora of declarable data structures induces a specialization within functions that inhibits and penalizes casual cooperation. It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.''
</div>

<div id="footnote_2-8" class="footnote">  
<p> <a href="#footnote_link_2-8" class="footnote_backlink">8</a> In this book, we use list to mean a chain of pairs terminated by the end-of-list marker. In contrast, the term list structure refers to any data structure made out of pairs, not just to lists.
</div>

<div id="footnote_2-9" class="footnote">  
<p> <a href="#footnote_link_2-9" class="footnote_backlink">9</a> Since nested applications of car and cdr are cumbersome to write, Lisp dialects provide abbreviations for them -- for instance,

<pre>
(cadr &lt;arg&gt;) = (car (cdr &lt;arg&gt;))
</pre>

<p> The names of all such procedures start with c and end with r. Each a between them stands for a car operation and each d for a cdr operation, to be applied in the same order in which they appear in the name. The names car and cdr persist because simple combinations like cadr are pronounceable.
</div>

<div id="footnote_2-10" class="footnote">  
<p> <a href="#footnote_link_2-10" class="footnote_backlink">10</a> It's remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair? In Scheme, nil is an ordinary name, which we use in this section as a variable whose value is the end-of-list marker (just as true is an ordinary variable that has a true value). Other dialects of Lisp, including Common Lisp, treat nil as a special symbol. The authors of this book, who have endured too many language standardization brawls, would like to avoid the entire issue. Once we have introduced quotation in section 2.3, we will denote the empty list as '() and dispense with the variable nil entirely.
</div>

<div id="footnote_2-11" class="footnote">  
<p> <a href="#footnote_link_2-11" class="footnote_backlink">11</a> To define <tt>f</tt> and <tt>g</tt> using <tt>lambda</tt> we would write

<div id="scheme-lambda-dotted-tail-syntax">
(define f (lambda (x y . z) &lt;body&gt;))
(define g (lambda w &lt;body&gt;))
</div>
<script>
prompt("scheme-lambda-dotted-tail-syntax");
</script>
</div>

<div id="footnote_2-12" class='footnote'> 
<p> <a href="#footnote_link_2-12" class="footnote_backlink">12</a> Scheme standardly provides a <tt>map</tt> procedure that is more general than the one described here. This more general <tt>map</tt> takes a procedure of n arguments, together with n lists, and applies the procedure to all the first elements of the lists, all the second elements of the lists, and so on, returning a list of the results. For example:

<div id="scheme-demonstrate-map">
(map + (list 1 2 3) (list 40 50 60) (list 700 800 900))
'(741 852 963)

(map (lambda (x y) (+ x (* 2 y)))
     (list 1 2 3)
     (list 4 5 6))
'(9 12 15)
</div>
<script>
prompt("scheme-demonstrate-map");
</script>
</div>

<div id="footnote_2-13" class='footnote'> 
<p> <a href="#footnote_link_2-13" class="footnote_backlink">13</a> The order of the first two clauses in the <tt>cond</tt> matters, since the empty list satisfies <tt>null?</tt> and also is not a pair.</div>

<div id="footnote_2-14" class='footnote'> 
<p> <a href="#footnote_link_2-14" class="footnote_backlink">14</a> This is, in fact, precisely the fringe procedure from exercise 2.28. Here we've renamed it to emphasize that it is part of a family of general sequence-manipulation procedures.
</div>

<div id="footnote_2-15" class='footnote'> 
<p> <a href="#footnote_link_2-15" class="footnote_backlink">15</a> Richard Waters (1979) developed a program that automatically analyzes traditional Fortran programs, viewing them in terms of maps, filters, and accumulations. He found that fully 90 percent of the code in the Fortran Scientific Subroutine Package fits neatly into this paradigm. One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations. The programming language APL owes much of its power and appeal to a similar choice. In APL all data are represented as arrays, and there is a universal and convenient set of generic operators for all sorts of array operations.
</div>

<div id="footnote_2-16" class='footnote'> 
<p> <a href="#footnote_link_2-16" class="footnote_backlink">16</a> According to Knuth (1981), this rule was formulated by W. G. Horner early in the nineteenth century, but the method was actually used by Newton over a hundred years earlier. Horner's rule evaluates the polynomial using fewer additions and multiplications than does the straightforward method of first computing an xn, then adding an-1xn-1, and so on. In fact, it is possible to prove that any algorithm for evaluating arbitrary polynomials must use at least as many additions and multiplications as does Horner's rule, and thus Horner's rule is an optimal algorithm for polynomial evaluation. This was proved (for the number of additions) by A. M. Ostrowski in a 1954 paper that essentially founded the modern study of optimal algorithms. The analogous statement for multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro (1975) provides an overview of these and other results about optimal algorithms.
</div>

<div id="footnote_2-17" class='footnote'> 
<p> <a href="#footnote_link_2-17" class="footnote_backlink">17</a> This definition uses the extended version of map described in footnote 12.
</div>

<div id="footnote_2-18" class='footnote'> 
<p> <a href="#footnote_link_2-18" class="footnote_backlink">18</a> This approach to nested mappings was shown to us by David Turner, whose languages KRC and Miranda provide elegant formalisms for dealing with these constructs. The examples in this section (see also exercise 2.42) are adapted from Turner 1981. In section 3.5.3, we'll see how this approach generalizes to infinite sequences.
</div>

<div id="footnote_2-19" class='footnote'> 
<p> <a href="#footnote_link_2-19" class="footnote_backlink">19</a> We're representing a pair here as a list of two elements rather than as a Lisp pair. Thus, the ``pair'' (i,j) is represented as (list i j), not (cons i j).
</div>

<div id="footnote_2-20" class='footnote'> 
<p> <a href="#footnote_link_2-20" class="footnote_backlink">20</a> The set S - x is the set of all elements of S, excluding x.
</div>

<div id="footnote_2-21" class='footnote'> 
<p> <a href="#footnote_link_2-21" class="footnote_backlink">21</a> Semicolons in Scheme code are used to introduce comments. Everything from the semicolon to the end of the line is ignored by the interpreter. In this book we don't use many comments; we try to make our programs self-documenting by using descriptive names.
</div>

<div id="footnote_2-22" class='footnote'> 
<p> <a href="#footnote_link_2-22" class="footnote_backlink">22</a> The picture language is based on the language Peter Henderson created to construct images like M.C. Escher's ``Square Limit'' woodcut (see Henderson 1982). The woodcut incorporates a repeated scaled pattern, similar to the arrangements drawn using the square-limit procedure in this section.
</div>


<div id="footnote_2-23" class='footnote'> 
<p> <a href="#footnote_link_2-23" class="footnote_backlink">23</a> William Barton Rogers (1804-1882) was the founder and first president of MIT. A geologist and talented teacher, he taught at William and Mary College and at the University of Virginia. In 1859 he moved to Boston, where he had more time for research, worked on a plan for establishing a ``polytechnic institute,'' and served as Massachusetts's first State Inspector of Gas Meters.

<p> When MIT was established in 1861, Rogers was elected its first president. Rogers espoused an ideal of ``useful learning'' that was different from the university education of the time, with its overemphasis on the classics, which, as he wrote, ``stand in the way of the broader, higher and more practical instruction and discipline of the natural and social sciences.'' This education was likewise to be different from narrow trade-school education. In Rogers's words:

<p> The world-enforced distinction between the practical and the scientific worker is utterly futile, and the whole experience of modern times has demonstrated its utter worthlessness.

<p> Rogers served as president of MIT until 1870, when he resigned due to ill health. In 1878 the second president of MIT, John Runkle, resigned under the pressure of a financial crisis brought on by the Panic of 1873 and strain of fighting off attempts by Harvard to take over MIT. Rogers returned to hold the office of president until 1881.

<p> Rogers collapsed and died while addressing MIT's graduating class at the commencement exercises of 1882. Runkle quoted Rogers's last words in a memorial address delivered that same year:

<blockquote> ``As I stand here today and see what the Institute is, ... I call to mind the beginnings of science. I remember one hundred and fifty years ago Stephen Hales published a pamphlet on the subject of illuminating gas, in which he stated that his researches had demonstrated that 128 grains of bituminous coal -- ''

``Bituminous coal,'' these were his last words on earth. Here he bent forward, as if consulting some notes on the table before him, then slowly regaining an erect position, threw up his hands, and was translated from the scene of his earthly labors and triumphs to ``the tomorrow of death,'' where the mysteries of life are solved, and the disembodied spirit finds unending satisfaction in contemplating the new and still unfathomable mysteries of the infinite future.
</blockquote>

<p> In the words of Francis A. Walker (MIT's third president):

<blockquote> All his life he had borne himself most faithfully and heroically, and he died as so good a knight would surely have wished, in harness, at his post, and in the very part and act of public duty. </blockquote>

</div>

<div id="footnote_2-24" class='footnote'> 
<p> <a href="#footnote_link_2-24" class="footnote_backlink">24</a> Equivalently, we could write

<pre>
(define flipped-pairs
  (square-of-four identity flip-vert identity flip-vert))
</pre>
</div>

<div id="footnote_2-25" class='footnote'> 
<p> <a href="#footnote_link_2-25" class="footnote_backlink">25</a> Rotate180 rotates a painter by 180 degrees (see exercise 2.50). Instead of rotate180 we could say (compose flip-vert flip-horiz), using the compose procedure from exercise 1.42.
</div>

<div id="footnote_2-26" class='footnote'> 
<p> <a href="#footnote_link_2-26" class="footnote_backlink">26</a> Frame-coord-map uses the vector operations described in exercise 2.46 below, which we assume have been implemented using some representation for vectors. Because of data abstraction, it doesn't matter what this vector representation is, so long as the vector operations behave correctly.
</div>

<div id="footnote_2-27" class='footnote'> 
<p> <a href="#footnote_link_2-27" class="footnote_backlink">27</a> Segments->painter uses the representation for line segments described in exercise 2.48 below. It also uses the for-each procedure described in exercise 2.23.
</div>

<div id="footnote_2-28" class='footnote'> 
<p> <a href="#footnote_link_2-28" class="footnote_backlink">28</a> For example, the rogers painter of figure 2.11 was constructed from a gray-level image. For each point in a given frame, the rogers painter determines the point in the image that is mapped to it under the frame coordinate map, and shades it accordingly. By allowing different types of painters, we are capitalizing on the abstract data idea discussed in section 2.1.3, where we argued that a rational-number representation could be anything at all that satisfies an appropriate condition. Here we're using the fact that a painter can be implemented in any way at all, so long as it draws something in the designated frame. Section 2.1.3 also showed how pairs could be implemented as procedures. Painters are our second example of a procedural representation for data.
</div>

<div id="footnote_2-29" class='footnote'> 
<p> <a href="#footnote_link_2-29" class="footnote_backlink">29</a> Rotate90 is a pure rotation only for square frames, because it also stretches and shrinks the image to fit into the rotated frame.
</div>

<div id="footnote_2-30" class='footnote'> 
<p> <a href="#footnote_link_2-30" class="footnote_backlink">30</a> The diamond-shaped images in figures 2.10 and 2.11 were created with squash-inwards applied to wave and rogers.
</div>

<div id="footnote_2-31" class='footnote'> 
<p> <a href="#footnote_link_2-31" class="footnote_backlink">31</a> Section 3.3.4 describes one such language.
</div> </div>

<hr>

<p> <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_US" target="_blank"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" /></a><br /> Based on Structure and Interpretation of Computer Programs, a work at <a xmlns:dct="http://purl.org/dc/terms/" href="http://mitpress.mit.edu/sicp/" rel="dct:source" target="_blank">http://mitpress.mit.edu/sicp/</a>.

</div>

<a href="https://github.com/zodiac/isicp" target="_blank"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_green_007200.png" alt="Fork me on GitHub"></a>

</body>
</html>