1-3-hop.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 1.3 - Higher-Order Procedures</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='1-2-procedures.html'> <img src='images/chevron-left.svg' height=64 width=64> </a>
<a href='2-1-data.html'> <img src='images/chevron-right.svg' height=64 width=64> </a>
</span>

<br> <br>

<h2> Formulating Abstractions with Higher-Order Procedures </h2>

<hr>

<p> We have seen that procedures are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers. For example, when we

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

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

<p> we are not talking about the cube of a particular number, but rather about a method for obtaining the cube of any number. Of course we could get along without ever defining this procedure, by always writing expressions such as

<div id="scheme-cube-ex">
(* 3 3 3)
(* x x x)
(* y y y)
</div>
<script>
no_output_prompt("scheme-cube-ex");
</script>

<p> and never mentioning cube explicitly. This would place us at a serious disadvantage, forcing us to work always at the level of the particular operations that happen to be primitives in the language (multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able to compute cubes, but our language would lack the ability to express the concept of cubing. One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. Procedures provide this ability. This is why all but the most primitive programming languages include mechanisms for defining procedures.

<p> Yet even in numerical processing we will be severely limited in our ability to create abstractions if we are restricted to procedures whose parameters must be numbers. Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called higher-order procedures. This section shows how higher-order procedures can serve as powerful abstraction mechanisms, vastly increasing the expressive power of our language.

<h3> Procedures as Arguments </h3>

<p> Consider the following three procedures. The first computes the sum of the integers from a through b:

<div id="scheme-define-sum-integers">
(define (sum-integers a b)
  (if (&gt; a b)
      0
      (+ a (sum-integers (+ a 1) b))))
</div>
<script>
prompt("scheme-define-sum-integers");
</script>

<p> The second computes the sum of the cubes of the integers in the given range:

<div id="scheme-define-sum-cubes">
(define (sum-cubes a b)
  (if (&gt; a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))
</div>
<script>
promptDep("scheme-define-sum-cubes", ["scheme-define-cube"]);
</script>

<p> The third computes the sum of a sequence of terms in the series

$$
\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + \cdots
$$

<p> which converges to $\pi/8$ (very slowly):<a name="footnote_link_1-49" class="footnote_link" href="#footnote_1-49">49</a>

<div id="scheme-define-pi-sum">
(define (pi-sum a b)
  (if (&gt; a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))
</div>
<script>
prompt("scheme-define-pi-sum");
</script>

<p> These three procedures clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the procedure, the function of a used to compute the term to be added, and the function that provides the next value of a. We could generate each of the procedures by filling in slots in the same template:

<div id="scheme-sum-template">
(define (&lt;name&gt; a b)
  (if (&gt; a b)
      0
      (+ (&lt;term&gt; a)
         (&lt;name&gt; (&lt;next&gt; a) b))))
</div>
<script>
prompt("scheme-sum-template");
</script>

<p> The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be brought to the surface. Indeed, mathematicians long ago identified the abstraction of summation of a series and invented &ldquo;sigma notation,&rdquo; for example

$$
\sum_{n=a}^b f(n) = f(a) + \cdots + f(b)
$$

<p> to express this concept. The power of sigma notation is that it allows mathematicians to deal with the concept of summation itself rather than only with particular sums &mdash; for example, to formulate general results about sums that are independent of the particular series being summed.

<p> Similarly, as program designers, we would like our language to be powerful enough so that we can write a procedure that expresses the concept of summation itself rather than only procedures that compute particular sums. We can do so readily in our procedural language by taking the common template shown above and transforming the &ldquo;slots&rdquo; into formal parameters:

<div id="scheme-define-sum">
(define (sum term a next b)
  (if (&gt; a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
</div>
<script>
prompt("scheme-define-sum");
</script>

<p> Notice that sum takes as its arguments the lower and upper bounds a and b together with the procedures term and next. We can use sum just as we would any procedure. For example, we can use it (along with a procedure inc that increments its argument by 1) to define sum-cubes:

<div id="scheme-define-inc">
(define (inc n) (+ n 1))
</div>
<script>
prompt("scheme-define-inc");
</script>

<div id="scheme-define-sum-cubes-sum">

(define (sum-cubes a b)
  (sum cube a inc b))
</div>
<script>
prompt("scheme-define-sum-cubes-sum");
depsOf["scheme-define-sum-cubes-sum"] = ["scheme-define-cube", "scheme-define-inc", "scheme-define-sum"];
</script>

<p> Using this, we can compute the sum of the cubes of the integers from 1 to 10:

<div id="scheme-sum-cubes-1-10">
(sum-cubes 1 10)
</div>
<script>
prompt("scheme-sum-cubes-1-10");
depsOf["scheme-sum-cubes-1-10"] = ["scheme-define-sum-cubes-sum"];
</script>

<p> With the aid of an identity procedure to compute the term, we can define sum-integers in terms of sum:

<div id="scheme-define-sum-integers-sum">
(define (identity x) x)

(define (sum-integers a b)
  (sum identity a inc b))
</div>
<script>
prompt("scheme-define-sum-integers-sum");
depsOf["scheme-define-sum-integers-sum"] = ["scheme-define-inc", "scheme-define-sum"];
</script>

<p> Then we can add up the integers from 1 to 10:

<div id="scheme-sum-integers-1-10">
(sum-integers 1 10)
</div>
<script>
prompt("scheme-sum-integers-1-10");
depsOf["scheme-sum-integers-1-10"] = ["scheme-define-sum-integers-sum"];
</script>

<p> We can also define pi-sum in the same way:<a name="footnote_link_1-50" class="footnote_link" href="#footnote_1-50">50</a>

<div id="scheme-define-pi-sum-sum">
(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))
</div>
<script>
prompt("scheme-define-pi-sum-sum");
depsOf["scheme-define-pi-sum-sum"] = ["scheme-define-sum"];
</script>

<p> Using these procedures, we can compute an approximation to  :

<div id="scheme-pi-sum-pi">
(* 8 (pi-sum 1 1000))
</div>
<script>
prompt("scheme-pi-sum-pi");
depsOf["scheme-pi-sum-pi"] = ["scheme-define-pi-sum-sum"];
</script>

<p> Once we have sum, we can use it as a building block in formulating further concepts. For instance, the definite integral of a function f between the limits a and b can be approximated numerically using the formula

$$
\int_a^b = \left[f(a + \frac{dx}{2}) + f(a + dx + \frac{dx}{2}) + f(a + 2dx + \frac{dx}{2}) + \cdots\right] dx
$$

<p> for small values of dx. We can express this directly as a procedure:

<div id="scheme-define-integral">
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))
</div>
<script>
prompt("scheme-define-integral");
depsOf["scheme-define-integral"] = ["scheme-define-sum"];
</script>

<p>

<div id="scheme-integral-cube">
(integral cube 0 1 0.01)
</div>

<p>

<div id="scheme-integral-cube-finer">
(integral cube 0 1 0.001)
</div>
<script>
prompt("scheme-integral-cube");
depsOf["scheme-integral-cube"] = ["scheme-define-cube", "scheme-define-integral"];
prompt("scheme-integral-cube-finer");
depsOf["scheme-integral-cube-finer"] = ["scheme-define-cube", "scheme-define-integral"];
</script>

<p> (The exact value of the integral of cube between $0$ and $1$ is $1/4$.)

<div class="exercise">
<p> <b> Exercise 1.29. </b> Simpson's Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson's Rule, the integral of a function f between a and b is approximated as

$$
\frac{h}{3} \left[ y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \cdots + 2y_{n-2} + 4y_{n-1} + y_n\right]
$$

<p> where $h = \frac{b - a}{n}$, for some even integer $n$, and $y_k = f(a + kh)$. (Increasing n increases the accuracy of the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000), and compare the results to those of the integral procedure shown above.

<div id="scheme-define-feq">
(define (feq a b)
  (&lt; (abs (- a b))
        0.000001))
</div>
<script>
hidden_prompt("scheme-define-feq")
</script>      

<div id="scheme-ex-simpson-input">
(define (simpson f a b n)
  'your-code-here)
</div>

<script>
/*
(define (simpson f a b n)
  (define h (/ (- b a) n))
  (define (inc x) (+ x 1))
  (define (y k)
    (f (+ a (* k h))))
  (define (term k)
    (* (cond ((odd? k) 4)
             ((or (= k 0) (= k n)) 1)
             ((even? k) 2))
       (y k)))
  (/ (* h (sum term 0 inc n)) 3))
*/

function simpson(f, a, b, n) {
  var h = (b - a) / n;
  function y(k) {
    return f(a + k*h);
  }
  function coeff(i) {
    if (i == 0 || i == n) {
      return 1;
    }
    return [2,4][i % 2];
  }

  var sum = 0;
  for (i = 0; i <= n; i++) {
    sum += coeff(i) * y(i);
  }
  return sum * h / 3;
}

addOutput("scheme-ex-simpson-input");
makeEditable("scheme-ex-simpson-input").setOption("onBlur", function() {

  function ss(f, fl, a, b, n) {
    return "(feq (simpson {0} {1} {2} {3}) {4}) ".format(fl, a, b, n, simpson(f, a, b, n));
  }

  function poly(x) {
    return 2 * x
  }

  polyl = "(lambda (x) (* 2 x))"

  var code = editorOf["scheme-ex-simpson-input"].getValue() + "\n" + editorOf["scheme-define-feq"].getValue() + "\n" + editorOf["scheme-define-sum"].getValue() +
             "(and " + ss(poly,polyl,2,3,10) + 
                       ss(poly,polyl,4,5,8) + 
                       ss(poly,polyl,2,10,12) + ") "

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

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.30. </b> The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

<div id="scheme-ex-sum-iter">
(define (sum term a next b)
  (define (iter a result)
    (if &lt;??&gt;
        &lt;??&gt;
        (iter &lt;??&gt; &lt;??&gt;)))
  (iter &lt;??&gt; &lt;??&gt;))  
</div>
<script>
addOutput("scheme-ex-sum-iter");

makeEditable("scheme-ex-sum-iter").setOption("onBlur", function() {
  var code = editorOf["scheme-ex-sum-iter"].getValue() + "\n" +
             "(= (sum (lambda (x) (* x x x)) 1 (lambda (n) (+ n 1)) 10) 3025)";

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

<p>

<div class="exercise">
<p> <b> Exercise 1.31. </b>

<p> The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.<a name="footnote_link_1-51" class="footnote_link" href="#footnote_1-51">51</a> Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Try both a recursive and an iterative approach. Show how to define factorial in terms of product. Also use product to compute approximations to  using the formula<a name="footnote_link_1-52" class="footnote_link" href="#footnote_1-52">52</a>

$$
\frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdots}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdots}
$$

<div id="scheme-ex-define-product">
(define (product term a next b)
  'your-code-here)
</div>
<script>
addOutput("scheme-ex-define-product");
makeEditable("scheme-ex-define-product").setOption("onBlur", function() {
  var code = editorOf["scheme-ex-define-product"].getValue() + "\n" +
             "(= (product (lambda (x) (* x x)) 1 (lambda (n) (+ n 1)) 5) 14400)"

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true") {
      $_("scheme-ex-define-product-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-product-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
      $_("scheme-ex-define-product-output").append(res);
    }
  });
});
/*
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.32. </b>

<p> Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:


<div id="scheme-accumulate-signature">
(accumulate combiner null-value term a next b)
</div>
<script>
no_output_frozen_prompt("scheme-accumulate-signature");
</script>

<p> Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate. Write two procedures, one that generates a recursive process and one iterative.

<div id="scheme-ex-define-accumulate">
(define (accumulate combiner null-value term a next b)
  'your-code-here)
</div>
<script>
addOutput("scheme-ex-define-accumulate");
makeEditable("scheme-ex-define-accumulate").setOption("onBlur", function() {
  var code = editorOf["scheme-ex-define-accumulate"].getValue() + "\n" +
             "(= (accumulate + 0 (lambda (x) (* x x)) 1 (lambda (n) (+ n 1)) 5) 55)"

  eval_scheme(code).then(function(res){
    if (res[res.length - 1] === "true") {
      $_("scheme-ex-define-accumulate-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
    } else {
      $_("scheme-ex-define-accumulate-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
      $_("scheme-ex-define-accumulate-output").append(res);
    }
  });
});
/*
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.33. </b> You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. 

<div id="scheme-ex-define-filtered-accumulate">
(define (filtered-accumulate combiner null-value term a next b filter?)
  'your-code-here)
</div>
<script>
addOutput("scheme-ex-define-filtered-accumulate");
makeEditable("scheme-ex-define-filtered-accumulate").setOption("onBlur", function() {
  var code = editorOf["scheme-ex-define-filtered-accumulate"].getValue() + "\n" +
             "(= (filtered-accumulate + 0 (lambda (x) (* x x)) 1 (lambda (n) (+ n 1)) 5 (lambda (x) #t)) 55)"

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

/*
(define (filtered-accumulate combiner null-value term a next b filter?)
  (cond ((> a b) null-value)
         ((filter? a) (combiner (term a)
                                (filtered-accumulate combiner null-value term (next a) next b filter?)))
         (else (filtered-accumulate combiner null-value term (next a) next b filter?))))
*/
</script>


<p> Show how to express the following using filtered-accumulate:

<ol style="list-style-type: lower-alpha">
<li>
<p> the sum of the squares of the prime numbers in the interval a to b (assuming that you have a <tt>prime?</tt> predicate already written)
</li>

<li>
<p> the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers $ &lt; n$ such that $\text{GCD}(i,n) = 1$).
</li>
</ol>

</div>

<h3> Constructing Procedures Using Lambda </h3>

<p> In using sum as in section 1.3.1, it seems terribly awkward to have to define trivial procedures such as pi-term and pi-next just so we can use them as arguments to our higher-order procedure. Rather than define pi-next and pi-term, it would be more convenient to have a way to directly specify &ldquo;the procedure that returns its input incremented by 4&rdquo; and &ldquo;the procedure that returns the reciprocal of its input times its input plus 2.&rdquo; We can do this by introducing the special form lambda, which creates procedures. Using lambda we can describe what we want as

<div id="scheme-lambda-plus-4">
(lambda (x) (+ x 4))
</div>
<script>
prompt("scheme-lambda-plus-4");
</script>

<p> and

<div id="scheme-lambda-inv-poly">
(lambda (x) (/ 1.0 (* x (+ x 2))))
</div>
<script>
prompt("scheme-lambda-inv-poly");
</script>

<p> Then our pi-sum procedure can be expressed without defining any auxiliary procedures as

<div id="scheme-define-pi-sum-lambda">
(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))
</div>
<script>
prompt("scheme-define-pi-sum-lambda");
depsOf["scheme-define-pi-sum-lambda"] = ["scheme-define-sum"];
</script>

<p> Again using lambda, we can write the integral procedure without having to define the auxiliary procedure add-dx:

<div id="scheme-define-integral-lambda">
(define (integral f a b dx)
  (* (sum f
          (+ a (/ dx 2.0))
          (lambda (x) (+ x dx))
          b)
     dx))
</div>
<script>
prompt("scheme-define-integral-lambda");
depsOf["scheme-define-integral-lambda"] = ["scheme-define-sum"];
</script>

<p> In general, lambda is used to create procedures in the same way as define, except that no name is specified for the procedure:

<div id="scheme-lambda-syntax">
(lambda (&lt;formal-parameters&gt;) &lt;body&gt;)
</div>
<script>
makeStatic("scheme-lambda-syntax");
</script>

<p> The resulting procedure is just as much a procedure as one that is created using define. The only difference is that it has not been associated with any name in the environment. In fact,

<div id="scheme-define-plus4">
(define (plus4 x) (+ x 4))
</div>
<script>
prompt("scheme-define-plus4");
</script>

<p> is equivalent to

<div id="scheme-define-plus4-lambda">
(define plus4 (lambda (x) (+ x 4)))
</div>
<script>
prompt("scheme-define-plus4-lambda");
</script>

<p> We can read a lambda expression as follows:

<p><p><tt>&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(x)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://mitpress.mit.edu/sicp/full-text/book/book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://mitpress.mit.edu/sicp/full-text/book/book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://mitpress.mit.edu/sicp/full-text/book/book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://mitpress.mit.edu/sicp/full-text/book/book-Z-G-D-16.gif" border="0">&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://mitpress.mit.edu/sicp/full-text/book/book-Z-G-D-16.gif" border="0"><br>
&nbsp;the&nbsp;procedure&nbsp;&nbsp;&nbsp;of&nbsp;an&nbsp;argument&nbsp;<tt>x</tt>&nbsp;&nbsp;that&nbsp;adds&nbsp;&nbsp;<tt>x</tt>&nbsp;and&nbsp;4<br>
</tt><p><p>

<p> Like any expression that has a procedure as its value, a lambda expression can be used as the operator in a combination such as

<div id="scheme-apply-lambda">
((lambda (x y z) (+ x y (square z))) 1 2 3)
</div>
<script>
prompt("scheme-apply-lambda");
depsOf["scheme-apply-lambda"] = ["scheme-define-square"];
</script>

<p> or, more generally, in any context where we would normally use a procedure name.<a name="footnote_link_1-53" class="footnote_link" href="#footnote_1-53">53</a>

<h4> Using let to create local variables </h4>

<p> Another use of <tt>lambda</tt> is in creating local variables. We often need local variables in our procedures other than those that have been bound as formal parameters. For example, suppose we wish to compute the function

$$
f(x,y) = x (1 + xy)^2 + y(1-y) + (1 + xy)(1 - y)
$$

<p> which we could also express as

\begin{align} 
a &amp;= 1 + xy \\
b &amp;= 1 - y \\
f(x,y) &amp;= xa^2 + yb + ab
\end{align}

<p> In writing a procedure to compute $f$ we would like to include as local variables not only $x$ and $y$ but also the names of intermediate quantities like $a$ and $b$. One way to accomplish this is to use an auxiliary procedure to bind the local variables:

<div id="scheme-define-f-helpers">
(define (f x y)
  (define (f-helper a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (f-helper (+ 1 (* x y))
            (- 1 y)))
</div>
<script>
prompt("scheme-define-f-helpers");
depsOf["scheme-define-f-helpers"] = ["scheme-define-square"];
</script>

<p> Of course, we could use a <tt>lambda</tt> expression to specify an anonymous procedure for binding our local variables. The body of <tt>f</tt> then becomes a single call to that procedure:

<div id="scheme-define-f-lambda">
(define (f x y)
  ((lambda (a b)
     (+ (* x (square a))
        (* y b)
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))
</div>
<script>
prompt("scheme-define-f-lambda");
depsOf["scheme-define-f-lambda"] = ["scheme-define-square"];
</script>

<p> This construct is so useful that there is a special form called <tt>let</tt> to make its use more convenient. Using <tt>let</tt>, the <tt>f</tt> procedure could be written as

<div id="scheme-define-f-let">
(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))
</div>
<script>
prompt("scheme-define-f-let");
depsOf["scheme-define-f-let"] = ["scheme-define-square"];
</script>

<p> The general form of a <tt>let</tt> expression is

<div id="scheme-let-syntax">
(let ((&lt;var1&gt; &lt;exp1&gt;)
      (&lt;var2&gt; &lt;exp2&gt;)
      ...
      (&lt;varN&gt; &lt;varN&gt;))
   &lt;body&gt;)
</div>
<script>
makeStatic("scheme-let-syntax");
</script>

<p> which can be thought of as saying

<pre>
let &lt;var_1&gt; have the value &lt;exp_1&gt; and
    &lt;var_2&gt; have the value &lt;exp_2&gt; and
    ...
    &lt;var_n&gt; have the value &lt;exp_n&gt;
in  &lt;body&gt;
</pre>

<p> The first part of the <tt>let</tt> expression is a list of name-expression pairs. When the <tt>let</tt> is evaluated, each name is associated with the value of the corresponding expression. The body of the <tt>let</tt> is evaluated with these names bound as local variables. The way this happens is that the <tt>let</tt> expression is interpreted as an alternate syntax for

<div id="scheme-let-expanded-syntax">
((lambda (&lt;var_1&gt; ... &lt;var_n&gt;) 
    &lt;body&gt;)
  &lt;exp_1&gt;
  ...
  &lt;exp_n&gt;)
</div>
<script>
makeStatic("scheme-let-expanded-syntax");
</script>

<p> No new mechanism is required in the interpreter in order to provide local variables. A <tt>let</tt> expression is simply syntactic sugar for the underlying <tt>lambda</tt> application.

<p> We can see from this equivalence that the scope of a variable specified by a <tt>let</tt> expression is the body of the <tt>let</tt>. This implies that:

<ul>

<li>
<tt>let</tt> allows one to bind variables as locally as possible to where they are to be used. For example, if the value of <tt>x</tt> is 5, the value of the expression

<div id="scheme-let-close-prelude">
(define x 5)
</div>

<div id="scheme-let-close">
(+ (let ((x 3))
     (+ x (* x 10)))
   x)
</div>


<p> is  <span id="scheme-let-close-output" class="output"> </span>

<script>
hidden_prompt("scheme-let-close-prelude");

no_output_prompt("scheme-let-close", ["scheme-let-close-prelude"]);
editorOf["scheme-let-close"].setOption("onBlur", function(){
  eval_editor("scheme-let-close").then(function(res){
    $_("scheme-let-close-output").empty().append($("<span>" + res + "</span>"));    
  });
});
</script>

<p> Here, the <tt>x</tt> in the body of the <tt>let</tt> is 3, so the value of the <tt>let</tt> expression is 33. On the other hand, the <tt>x</tt> that is the second argument to the outermost <tt>+</tt> is still 5.
</li>

<li>
<p> The variables' values are computed outside the <tt>let.</tt> This matters when the expressions that provide the values for the local variables depend upon variables having the same names as the local variables themselves. For example, if the value of <tt>x</tt> is 2, the expression

<div id="scheme-let-shadow-prelude">
(define x 2)
</div>
<script>
hidden_prompt("scheme-let-shadow-prelude");
</script>

<div id="scheme-let-shadow">
(let ((x 3)
      (y (+ x 2)))
  (* x y))
</div>

<script>
no_output_prompt("scheme-let-shadow", ["scheme-let-shadow-prelude"]);
editorOf["scheme-let-shadow"].setOption("onBlur", function(){
  eval_editor("scheme-let-shadow").then(function(res){
    $_("scheme-let-shadow-output").empty().append($("<span>" + res + "</span>"));    
  });
});
</script>

<p> will have the value <span id="scheme-let-shadow-output" class="output"></span> because, inside the body of the <tt>let, x</tt> will be 3 and <tt>y</tt> will be 4 (which is the outer <tt>x</tt> plus 2).
</li>
</ul>

<p> Sometimes we can use internal definitions to get the same effect as with <tt>let.</tt>  For example, we could have defined the procedure <tt>f</tt> above as

<div id="scheme-define-f-close-define">
(define (f x y)
  (define a (+ 1 (* x y)))
  (define b (- 1 y))
  (+ (* x (square a))
     (* y b)
     (* a b)))
</div>
<script>
prompt("scheme-define-f-close-define");
depsOf["scheme-define-f-close-define"] = ["scheme-define-square"];
</script>

<p> We prefer, however, to use <tt>let</tt> in situations like this and to use internal <tt>define</tt> only for internal procedures.<a name="footnote_link_1-54" class="footnote_link" href="#footnote_1-54">54</a>

<div class="exercise">
<p> <b> Exercise 1.34: </b> Suppose we define the procedure

<div id="scheme-define-f-g2">
(define (f g)
  (g 2))
</div>
<script>
prompt("scheme-define-f-g2");
</script>

<p> Then we have

<div id="scheme-f-square">
(f square)
</div>
<script>
prompt("scheme-f-square", ["scheme-define-f-g2", "scheme-define-square"]);
</script>

<div id="scheme-f-lambda-poly">
(f (lambda (z) (* z (+ z 1))))
</div>
<script>
prompt("scheme-f-lambda-poly", ["scheme-define-f-g2"]);
</script>

<p> What happens if we (perversely) ask the interpreter to evaluate the combination
<tt>(f f)?</tt>  Explain.

<div id="scheme-ex-f-f-mcq"></div>
<script>
makeMCQ("scheme-ex-f-f-mcq", 
    ["An error occurs, because <tt>2</tt> is not a procedure."],
    ["It evaluates to <tt>(2 2)</tt>, which is <tt>4</tt>.",
     "The interpreter enters an infinite loop.",
     "The result is <tt>2</tt>."
     ]);
</script>

</div>

<h3> Procedures as General Methods </h3>

<p> We introduced compound procedures in section @ref{1-1-4} as a mechanism for abstracting patterns of numerical operations so as to make them independent of the particular numbers involved. With higher-order procedures, such as the <tt>integral</tt> procedure of section @ref{1-3-1}, we began to see a more powerful kind of abstraction: procedures used to express general methods of computation, independent of the particular functions involved. In this section we discuss two more elaborate examples &mdash; general methods for finding zeros and fixed points of functions &mdash; and show how these methods can be expressed directly as procedures.

<h4> Finding roots of equations by the half-interval method </h4>

<p> The <em> half-interval method </em> is a simple but powerful technique for finding roots of an equation <em> f(x) = 0 </em>, where <em> f </em> is a continuous function. The idea is that, if we are given points $ a $ and $ b $ such that $ f(a) &lt; 0 &lt; f (b) $, then $ f $ must have at least one zero between $ a $ and $ b $. To locate a zero, let $ x $ be the average of $ a $ and $ b $ and compute $ f(x) $. If $ f(x) &gt; 0  $, then $ f $ must have a zero between $ a $ and $ x $. If $ f(x) &lt; 0$, then $ f $ must have a zero between $ x $ and $ b $. Continuing in this way, we can identify smaller and smaller intervals on which $ f $ must have a zero. When we reach a point where the interval is small enough, the process stops. Since the interval of uncertainty is reduced by half at each step of the process, the number of steps required grows as $\Theta(\log(L/T))$, where $L$ is the length of the original interval and $T$ is the error tolerance (that is, the size of the interval we will consider &ldquo;small enough&rdquo;). Here is a procedure that implements this strategy:

<div id="scheme-define-average">
(define (average x y)
  (/ (+ x y)
     2))
</div>
<script>
hidden_prompt("scheme-define-average");
</script>

<div id="scheme-define-search">
(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))
</div>
<script>
prompt("scheme-define-search");
depsOf["scheme-define-search"] = ["scheme-define-average", "scheme-define-close-enough"];
</script>

<p> We assume that we are initially given the function <em> f </em> together with points at which its values are negative and positive. We first compute the midpoint of the two given points. Next we check to see if the given interval is small enough, and if so we simply return the midpoint as our answer. Otherwise, we compute as a test value the value of <em> f </em> at the midpoint. If the test value is positive, then we continue the process with a new interval running from the original negative point to the midpoint. If the test value is negative, we continue with the interval from the midpoint to the positive point. Finally, there is the possibility that the test value is 0, in which case the midpoint is itself the root we are searching for.

<p> To test whether the endpoints are &ldquo;close enough&rdquo; we can use a procedure similar to the one used in section 1-1-7 for computing square roots:<a name="footnote_link_1-55" class="footnote_link" href="#footnote_1-55">55</a>

<div id="scheme-define-close-enough">
(define (close-enough? x y)
  (&lt; (abs (- x y)) 0.001))
</div>
<script>
prompt("scheme-define-close-enough");
</script>

<p> <tt>search</tt> is awkward to use directly, because we can accidentally give it points at which <em> f </em>'s values do not have the required sign, in which case we get a wrong answer. Instead we will use <tt>search</tt> via the following procedure, which checks to see which of the endpoints has a negative function value and which has a positive value, and calls the <tt>search</tt> procedure accordingly. If the function has the same sign on the two given points, the half-interval method cannot be used, in which case the procedure signals an error.<a name="footnote_link_1-56" class="footnote_link" href="#footnote_1-56">56</a>

<div id="scheme-define-negative-positive">
(define (negative? x)
  (< x 0))

(define (positive? x)
  (> x 0))
</div>
<script>
hidden_prompt("scheme-define-negative-positive")
</script>

<div id="scheme-define-half-interval-method">
(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))
</div>
<script>
prompt("scheme-define-half-interval-method");
depsOf["scheme-define-half-interval-method"] = ["scheme-define-search", "scheme-define-negative-positive"];
</script>

<p> The following example uses the half-interval method to approximate pi as the root between 2 and 4 of sin(x) = 0:

<div id="scheme-half-interval-method-sine">
(half-interval-method sin 2.0 4.0)
</div>
<script>
prompt("scheme-half-interval-method-sine");
depsOf["scheme-half-interval-method-sine"] = ["scheme-define-half-interval-method"];
</script>

<p> Here is another example, using the half-interval method to search for a root of the equation x<sup>3</sup> - 2x - 3 = 0 between 1 and 2:

<div id="scheme-half-interval-method-poly">
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
                      1.0
                      2.0)
</div>
<script>
prompt("scheme-half-interval-method-poly");
depsOf["scheme-half-interval-method-poly"] = ["scheme-define-half-interval-method"];
</script>

<h4> Finding fixed points of functions </h4>

<p> A number $x$ is called a $fixed point$ of a function $f$ if $x$ satisfies the equation $f(x) = x$. For some functions $f$ we can locate a fixed point by beginning with an initial guess and applying $f$ repeatedly,

$$
f(x), f(f(x), (f(f(f(x))))
$$

<p> until the value does not change very much. Using this idea, we can devise a procedure <tt>fixed-point</tt> that takes as inputs a function and an initial guess and produces an approximation to a fixed point of the function. We apply the function repeatedly until we find two successive values whose difference is less than some prescribed tolerance:

<div id="scheme-define-fixed-point">
(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (&lt; (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
</div>
<script>
prompt("scheme-define-fixed-point", ["scheme-define-close-enough"]);
</script>

<p> For example, we can use this method to approximate the fixed point of the cosine function, starting with 1 as an initial approximation:<a name="footnote_link_1-57" class="footnote_link" href="#footnote_1-57">57</a>

<div id="scheme-fixed-point-cos">
(fixed-point cos 1.0)
</div>
<script>
prompt("scheme-fixed-point-cos", ["scheme-define-fixed-point"]);
</script>

<p> Similarly, we can find a solution to the equation $y = sin(y) + cos(y)$:

<div id="scheme-fixed-point-sin-cos">
(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)
</div>
<script>
prompt("scheme-fixed-point-sin-cos", ["scheme-define-fixed-point"]);
</script>

<p> The fixed-point process is reminiscent of the process we used for finding square roots in section 1.1.7. Both are based on the idea of repeatedly improving a guess until the result satisfies some criterion. In fact, we can readily formulate the square-root computation as a fixed-point search. Computing the square root of some number $x$ requires finding a $y$ such that $y^2 = x$. Putting this equation into the equivalent form $y = x/y$, we recognize that we are looking for a fixed point of the function<a name="footnote_link_1-58" class="footnote_link" href="#footnote_1-58">58</a> $y \mapsto x/y$, and we can therefore try to compute square roots as

<div id="scheme-define-sqrt">
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))
</div>
<script>
prompt("scheme-define-sqrt", ["scheme-define-fixed-point"]);
</script>

<p> Unfortunately, this fixed-point search does not converge. Consider an initial guess $y_1$. The next guess is $y_2 = x/y_1$ and the next guess is $y_3 = x/y_2 = x/(x/y_1) = y_1$. This results in an infinite loop in which the two guesses $y_1$ and $y_2$ repeat over and over, oscillating about the answer.

<p> One way to control such oscillations is to prevent the guesses from changing so much. Since the answer is always between our guess $y$ and $\frac{x}{y}$, we can make a new guess that is not as far from $y$ as $\frac{x}{y}$ by averaging $y$ with $\frac{x}{y}$, so that the next guess after $y$ is $\frac{1}{2}(y + \frac{x}{y})$ instead of $\frac{x}{y}$. The process of making such a sequence of guesses is simply the process of looking for a fixed point of $y \mapsto \frac{1}{2}(y + \frac{x}{y})$:

<div id="scheme-define-sqrt-average">
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))
</div>
<script>
prompt("scheme-define-sqrt-average");
depsOf["scheme-define-sqrt-average"] = ["scheme-define-fixed-point", "scheme-define-average"];
</script>

<p> (Note that $y = \frac{1}{2}(y + \frac{x}{y})$ is a simple transformation of the equation $y = \frac{x}{y}$; to derive it, add $y$ to both sides of the equation and divide by $2$.)

<p> With this modification, the square-root procedure works. In fact, if we unravel the definitions, we can see that the sequence of approximations to the square root generated here is precisely the same as the one generated by our original square-root procedure of section 1.1.7. This approach of averaging successive approximations to a solution, a technique we that we call average damping, often aids the convergence of fixed-point searches.

<div class="exercise">
<p> <b> Exercise 1.35. </b> Show that the golden ratio  (section 1.2.2) is a fixed point of the transformation $x \mapsto 1 + \frac{1}{x}$, and use this fact to compute $\phi$ by means of the fixed-point procedure.

<div id="scheme-define-phi-fixed-point">
(define phi
  (fixed-point 'your-answer-here))
</div>
<script>
prompt("scheme-define-phi-fixed-point", ["scheme-define-fixed-point"]); //todo: mark this?
</script>

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.36. </b> Modify fixed-point so that it prints the sequence of approximations it generates, using the <tt>newline</tt> and <tt>display</tt> primitives shown in exercise 1.22. Then find a solution to $x^x = 1000$ by finding a fixed point of $x \mapsto \frac{\log(1000)}{\log(x)}$. (Use Scheme's primitive <tt>log</tt> procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by $\log(1) = 0.$)

<div id="scheme-ex-define-printing-fixed-point">
(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (&lt; (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
</div>
<script>
prompt("scheme-ex-define-printing-fixed-point", ["scheme-define-close-enough"]);
/*
(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) 
               (/ (+ x (/ (log 1000) (log x))) 
                  2))
               1.1)
*/
</script>

</div> 

<p>

<div class="exercise">
<p> <b> Exercise 1.37. </b> An infinite continued fraction is an expression of the form
 
$$
f = \cfrac{N_1}{D_1 + \cfrac{N_2}{D_2 + \cfrac{N_3}{D_3 + \cdots}}} 
$$

<p> As an example, one can show that the infinite continued fraction expansion with the $N_i$ and the $D_i$ all equal to $1$ produces $\frac{1}{\phi}$, where $\phi$ is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation &mdash; a so-called <em> k-term finite continued fraction </em> &mdash; has the form

$$
f = \cfrac{N_1}{D_1 + \cfrac{N_2}{\ddots + \cfrac{N_k}{D_k}}} 
$$

<p> Suppose that <tt>n</tt> and <tt>d</tt> are procedures of one argument (the term index $i$ that return the $N_i$ and $D_i$ of the terms of the continued fraction. Define a procedure <tt>cont-frac</tt> such that evaluating <tt>(cont-frac n d k)</tt> computes the value of the $k$-term finite continued fraction. 

<div id="scheme-ex-define-cont-frac">
(define (cont-frac n d k)
  'your-code-here)
</div>
<script>
prompt("scheme-ex-define-cont-frac");
/*
(define (cont-frac n d k)
  (define (frac i)
     (if (< i k)
         (/ (n i) (+ (d i) (frac (+ i 1))))
         (/ (n i) (d i))))
  (frac 1))
*/
</script>


<p> Check your procedure by approximating $\frac{1}{\phi}$ using

<div id="scheme-test-cont-frac">
(define k 10)
(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)
</div>
<script>
prompt("scheme-test-cont-frac", ["scheme-ex-define-cont-frac"]);
</script>

<p> for successive values of <tt>k</tt>. How large must you make <tt>k</tt> in order to get an approximation that is accurate to 4 decimal places?

<p> Try to write both an iterative and a recursive version of <tt>cont-frac</tt>.

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.38. </b> In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for $e - 2$, where $e$ is the base of the natural logarithms. In this fraction, the $N_i$ are all $1$, and the $D_i$ are successively $1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots$ Write a program that uses your <tt>cont-frac</tt> procedure from exercise 1.37 to approximate $e$, based on Euler's expansion.

<div id="scheme-ex-euler">
(cont-frac n d 10)
</div>
<script>
prompt("scheme-ex-euler", ["scheme-ex-define-cont-frac"]);
/*
(cont-frac (lambda (i) 1)
           (lambda (i)
             (if (= (modulo i 3) 2)
                 (* 2 (/ (+ 1 i) 3))
                 1))
*/
</script>
</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.39. </b> A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:

$$
\tan x = \cfrac{x}{1 - \cfrac{x^2}{3 - \cfrac{x^2}{5 - \ddots}}}
$$

<p> where <em> x </em> is in radians. Define a procedure <tt>(tan-cf x k)</tt> that computes an approximation to the tangent function based on Lambert's formula. <tt>k</tt> specifies the number of terms to compute, as in Exercise 1-37.

<div id="scheme-ex-define-tan-cf">
(define (tan-cf x k)
  'your-code-here)
</div>
<script>
prompt("scheme-ex-define-tan-cf", ["scheme-ex-define-cont-frac"]);
/*
(define (square x) (* x x))

(define (tan-cf x k)
   (define (n k)
       (if (= k 1)
           x
           (- (square x))))
   (define (d k)
       (- (* 2 k) 1))
   (cont-frac n d k))
*/
</script>
</div>

<h3> Procedures as Returned Values </h3>

<p> The above examples demonstrate how the ability to pass procedures as arguments significantly enhances the expressive power of our programming language. We can achieve even more expressive power by creating procedures whose returned values are themselves procedures.

<p> We can illustrate this idea by looking again at the fixed-point example described at the end of section 1.3.3. We formulated a new version of the square-root procedure as a fixed-point search, starting with the observation that x is a fixed-point of the function y -&gt; x/y. Then we used average damping to make the approximations converge. Average damping is a useful general technique in itself. Namely, given a function f, we consider the function whose value at x is equal to the average of x and f(x).

<p> Average damping is a useful general technique in itself. Namely, given a
function $f$, we consider the function whose value at $x$ is equal to the
average of $x$ and $f(x)$.

<p> We can express the idea of average damping by means of the following procedure:

<div id="scheme-define-average-damp">
(define (average-damp f)
  (lambda (x) (average x (f x))))
</div>
<script>
prompt("scheme-define-average-damp", ["scheme-define-average"]);
</script>

<p> <tt>average-damp</tt> is a procedure that takes as its argument a procedure f and returns as its value a procedure (produced by the lambda) that, when applied to a number <tt>x</tt>, produces the average of <tt>x</tt> and <tt>(f x)</tt>. For example, applying average-damp to the square procedure produces a procedure whose value at some number $x$ is the average of $x$ and $x^2$. Applying this resulting procedure to $10$ returns the average of $10$ and $100$, or $55$:<a name="footnote_link_1-59" class="footnote_link" href="#footnote_1-59">59</a>

<div id="scheme-average-damp-square-10">
((average-damp square) 10)
</div>
<script>
prompt("scheme-average-damp-square-10", ["scheme-define-average-damp", "scheme-define-square"]);
</script>

<p> Using <tt>average-damp</tt>, we can reformulate the square-root procedure as follows:

<div id="scheme-define-sqrt-average-damp">
(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y)))
               1.0))
</div>
<script>
prompt("scheme-define-sqrt-average-damp");
addDep("scheme-define-sqrt-average-damp", ["scheme-define-fixed-point", "scheme-define-average-damp"]);
</script>

<p> Notice how this formulation makes explicit the three ideas in the method: fixed-point search, average damping, and the function $y \mapsto \frac{x}{y}$. It is instructive to compare this formulation of the square-root method with the original version given in section 1.1.7. Bear in mind that these procedures express the same process, and notice how much clearer the idea becomes when we express the process in terms of these abstractions. In general, there are many ways to formulate a process as a procedure. Experienced programmers know how to choose procedural formulations that are particularly perspicuous, and where useful elements of the process are exposed as separate entities that can be reused in other applications. As a simple example of reuse, notice that the cube root of $x$ is a fixed point of the function $y \mapsto $\frac{}{y^2}$, so we can immediately generalize our square-root procedure to one that extracts cube roots:<a name="footnote_link_1-60" class="footnote_link" href="#footnote_1-60">60</a>

<div id="scheme-define-cube-root-average-damp">
(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y))))
               1.0))
</div>
<script>
prompt("scheme-define-cube-root-average-damp");
addDep("scheme-define-cube-root-average-damp", ["scheme-define-fixed-point", "scheme-define-average-damp", "scheme-define-square"]);
</script>

<h4> Newton's method </h4>

<p> When we first introduced the square-root procedure, in section 1.1.7, we mentioned that this was a special case of Newton's method. If x  g(x) is a differentiable function, then a solution of the equation g(x) = 0 is a fixed point of the function x  f(x) where

$$
f(x) = x - \frac{g(x)}{Dg(x)}
$$

<p> and $Dg(x)$ is the derivative of $g$ evaluated at $x$. Newton's method is the use of the fixed-point method we saw above to approximate a solution of the equation by finding a fixed point of the function $f$.<a name="footnote_link_1-61" class="footnote_link" href="#footnote_1-61">61</a> For many functions $g$ and for sufficiently good initial guesses for $x$, Newton's method converges very rapidly to a solution of g(x) = 0.<a name="footnote_link_1-62" class="footnote_link" href="#footnote_1-62">62</a>

<p> In order to implement Newton's method as a procedure, we must first express the idea of derivative. Note that &ldquo;derivative&rdquo;, like average damping, is something that transforms a function into another function. For instance, the derivative of the function $x \mapsto x^3$ is the function $x \mapsto 3x^2$. In general, if $g$ is a function and $dx$ is a small number, then the derivative $Dg$ of $g$ is the function whose value at any number $x$ is given (in the limit of small $dx$) by

$$
Dg(x) = \frac{g(x+dx) - g(x)}{dx}
$$

<p> Thus, we can express the idea of derivative (taking $dx$ to be, say, $0.00001$) as the procedure

<div id="scheme-define-deriv">
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))
</div>
<script>
prompt("scheme-define-deriv");
</script>

<p> along with the definition

<div id="scheme-define-dx">
(define dx 0.00001)
</div>
<script>
prompt("scheme-define-dx");
</script>

<p> Like average-damp, deriv is a procedure that takes a procedure as argument and returns a procedure as value. For example, to approximate the derivative of $f(x) = x^3$ at $5$ (whose exact value is $75$) we can evaluate

<div id="scheme-deriv-cube">
(define (cube x) (* x x x))

((deriv cube) 5)
</div>
<script>
prompt("scheme-deriv-cube", ["scheme-define-deriv", "scheme-define-dx"]);
</script>

<p> With the aid of <tt>deriv</tt>, we can express Newton's method as a fixed-point process:

<div id="scheme-define-newton-transform">
(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))
</div>
<script>
prompt("scheme-define-newton-transform", ["scheme-define-deriv", "scheme-define-dx", "scheme-define-fixed-point"]);
</script>

<p> The newton-transform procedure expresses the formula at the beginning of this section, and newtons-method is readily defined in terms of this. It takes as arguments a procedure that computes the function for which we want to find a zero, together with an initial guess. For instance, to find the square root of x, we can use Newton's method to find a zero of the function y  y2 - x starting with an initial guess of 1.<a name="footnote_link_1-63" class="footnote_link" href="#footnote_1-63">63</a> This provides yet another form of the square-root procedure:

<div id="scheme-define-sqrt-newton">
(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))
</div>
<script>
prompt("scheme-define-sqrt-newton", ["scheme-define-newton-transform", "scheme-define-square"]);
</script>

<h4> Abstractions and first-class procedures </h4>

<p> We've seen two ways to express the square-root computation as an instance of a more general method, once as a fixed-point search and once using Newton's method. Since Newton's method was itself expressed as a fixed-point process, we actually saw two ways to compute square roots as fixed points. Each method begins with a function and finds a fixed point of some transformation of the function. We can express this general idea itself as a procedure:

<div id="scheme-define-fixed-point-of-transform">
(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))
</div>
<script>
prompt("scheme-define-fixed-point-of-transform");
addDep("scheme-define-fixed-point-of-transform", ["scheme-define-fixed-point"]);
</script>

<p> This very general procedure takes as its arguments a procedure $g$ that computes some function, a procedure that transforms $g$, and an initial guess. The returned result is a fixed point of the transformed function.

<p> Using this abstraction, we can recast the first square-root computation from this section (where we look for a fixed point of the average-damped version of $y \mapsto \frac{x}{y}$) as an instance of this general method:


<div id="scheme-define-sqrt-fixed-point-of-transform">
(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y))
                            average-damp
                            1.0))
</div>
<script>
prompt("scheme-define-sqrt-fixed-point-of-transform", ["scheme-define-fixed-point-of-transform", "scheme-define-average-damp"]);
</script>

<p> Similarly, we can express the second square-root computation from this section (an instance of Newton's method that finds a fixed point of the Newton transform of $y \mapsto y^2 - x$) as

<div id="scheme-define-sqrt-fixed-point-of-newton-transform">
(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x))
                            newton-transform
                            1.0))
</div>
<script>
prompt("scheme-define-sqrt-fixed-point-of-newton-transform", ["scheme-define-fixed-point-of-transform", "scheme-define-square", "scheme-define-newton-transform"]);
</script>

<p> We began section 1.3 with the observation that compound procedures are a crucial abstraction mechanism, because they permit us to express general methods of computing as explicit elements in our programming language. Now we've seen how higher-order procedures permit us to manipulate these general methods to create further abstractions.

<p> As programmers, we should be alert to opportunities to identify the underlying abstractions in our programs and to build upon them and generalize them to create more powerful abstractions. This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task. But it is important to be able to think in terms of these abstractions, so that we can be ready to apply them in new contexts. The significance of higher-order procedures is that they enable us to represent these abstractions explicitly as elements in our programming language, so that they can be handled just like other computational elements.

<p> In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have <em> first-class </em> status. Some of the &ldquo;rights and privileges&rdquo; of first-class elements are:<a name="footnote_link_1-64" class="footnote_link" href="#footnote_1-64">64</a>

<ul>

<li> <p> They may be named by variables. </li>
<li> <p> They may be passed as arguments to procedures. </li>
<li> <p> They may be returned as the results of procedures. </li>
<li> <p> They may be included in data structures.<a name="footnote_link_1-65" class="footnote_link" href="#footnote_1-65">65</a> </li>

</ul>

<p> Lisp, unlike other common programming languages, awards procedures full first-class status. This poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.<a name="footnote_link_1-66" class="footnote_link" href="#footnote_1-66">66</a>

<div class="exercise">

<p> <b> Exercise 1.40. </b> Define a procedure <tt>cubic</tt>
that can be used together with the <tt>newtons-method</tt> procedure in
expressions of the form

<div id="scheme-newtons-method-cubic">
(define (cubic a b c)
  'your-answer-here)

(newtons-method (cubic a b c) 1)
</div>
<script>
prompt("scheme-newtons-method-cubic", ["scheme-define-newton-transform"]);
</script>

<p> to approximate zeros of the cubic $x^3 + ax^2 + bx + c$.

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.41. </b> Define a procedure <tt>double</tt> that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if <tt>inc</tt> is a procedure that adds 1 to its argument, then <tt>(double inc)</tt> should be a procedure that adds 2.

<div id="scheme-ex-define-double">
(define (double f)
  'your-answer-here)
</div>
<script>
makeEditable("scheme-ex-define-double");
addOutput("scheme-ex-define-double");
editorOf["scheme-ex-define-double"].setOption("onBlur", function(){
  
  var code = "{0} \n (= ((double (lambda (i) (+ 1 i))) 1) 3)".format(editorOf["scheme-ex-define-double"].getValue());

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

<p> What value is returned by the following? (Please do not use the interpreter for this.)

<div id="scheme-double-itered-inc">
(((double (double double)) inc) 5)
</div>
<script>
answer("scheme-double-itered-inc", 21);
</script>

<p>
</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.42. </b> Let f and g be two one-argument functions. The composition f after g is defined to be the function x f(g(x)). Define a procedure compose that implements composition. 

<div id="scheme-ex-define-compose">
(define (compose f g)
  'your-answer-here)
</div>
<script>
makeEditable("scheme-ex-define-compose");
addOutput("scheme-ex-define-compose");
editorOf["scheme-ex-define-compose"].setOption("onBlur", function(){

  var code = "{0} \n (define (square x) (* x x)) \n (= ((compose square square) 2) 16)".format(editorOf["scheme-ex-define-compose"].getValue());

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

/*
(define (compose f g)
  (lambda (x) (f (g x))))
*/
</script>

<p> For example, if inc is a procedure that adds 1 to its argument,

<div id="scheme-compose-square-inc">
((compose square inc) 6)
</div>
<script>
prompt("scheme-compose-square-inc", ["scheme-define-square", "scheme-define-inc", "scheme-ex-define-compose"]);
</script>

<p> should return 49.
</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.43. </b> If f is a numerical function and n is a positive integer, then we can form the $n^{th}$ repeated application of $f$, which is defined to be the function whose value at $x$ is $f(f(\cdots(f(x))\cdots))$. For example, if $f$ is the function $x \mapsto x + 1$, then the $n^{th}$ repeated application of $f$ is the function $x \mapsto x + n$. If $f$ is the operation of squaring a number, then the $n^{th}$ repeated application of $f$ is the function that raises its argument to the $2n^{th}$ power. Write a procedure that takes as inputs a procedure that computes $f$ and a positive integer $n$ and returns the procedure that computes the $n^{th}$ repeated application of $f$.

<div id="scheme-ex-define-repeated">
(define (repeated f n)
  'your-answer-here)
</div>
<script>
makeEditable("scheme-ex-define-repeated");
addOutput("scheme-ex-define-repeated");
editorOf["scheme-ex-define-repeated"].setOption("onBlur", function(){

  var code = "{0} \n (define (square x) (* x x)) \n (= ((repeated square 2) 5) 625)".format(editorOf["scheme-ex-define-repeated"].getValue());

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

/*
(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (if (= n 0)
      (lambda (x) x)
      (compose f (repeated f (- n 1)))))
*/
</script>

<p> Your procedure should be able to be used as follows:

<div id="scheme-repeated-square-2-5">
((repeated square 2) 5)
</div>
<script>
frozen_prompt("scheme-repeated-square-2-5", ["scheme-ex-define-repeated", "scheme-define-square"]);
</script>

<p> and should return 625. Hint: You may find it convenient to use <tt>compose</tt> from Exercise 1-42.

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.44. </b> The idea of smoothing a function is an important concept in signal processing. If $f$ is a function and $dx$ is some small number, then the smoothed version of f is the function whose value at a point $x$ is the average of $f(x - dx)$, $f(x)$, and $f(x + dx)$. Write a procedure <tt>smooth</tt> that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.

<div id="scheme-ex-define-smooth">
(define dx 0.1)

(define (smooth f)
  'your-answer-here)
</div>
<script>
makeEditable("scheme-ex-define-smooth");
addOutput("scheme-ex-define-smooth");
editorOf["scheme-ex-define-smooth"].setOption("onBlur", function(){

  var code = "{0} \n {1} \n (feq ((smooth cos) 0) 0.99666944)".format(editorOf["scheme-define-feq"].getValue(), editorOf["scheme-ex-define-smooth"].getValue());

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

/*
(define (smooth f)
  (lambda (x)
    (/ (+ (f (- x dx))
          (f x)
          (f (+ x dx)))
       3)))
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.45. </b> We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of $y \mapsto \frac{x}{y}$ does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped $y \mapsto \frac{x}{y^2}$. Unfortunately, the process does not work for fourth roots &mdash; a single average damp is not enough to make a fixed-point search for $y \mapsto \frac{x}{y^3}$ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of $y \mapsto \frac{x}{y^3}$) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute $n^{th}$ roots as a fixed-point search based upon repeated average damping of $y \mapsto \frac{x}{y^{n-1}}$. Use this to implement a simple procedure for computing $n^{th}$ roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

<div id="scheme-ex-define-nth-root">
(define (root n x)
  'your-answer-here)
</div>
<script>
prompt("scheme-ex-define-nth-root");
</script>

</div>

<p>

<div class="exercise">
<p> <b> Exercise 1.46. </b> Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure <tt>iterative-improve</tt> that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.

<div id="scheme-ex-define-iterative-improve">
(define (iterative-improve good-enough? improve)
  'your-answer-here)
</div>
<script>
prompt("scheme-ex-define-iterative-improve");
</script>

</div>


<br>
<br>

<hr>

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

<div id="footnote_1-49" class="footnote">
<p><a href="#footnote_link_1-49" class="footnote_backlink">49</a>
 This series, usually written in the equivalent form $\frac{\pi}{4}  =  1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots$, is due to Leibniz. We'll see how to use this as the basis for some fancy numerical tricks in section&nbsp;<a href="book-Z-H-24.html#%_sec_3.5.3">3.5.3</a>.
</p></div>

<div id="footnote_1-50" class="footnote">
<p><a href="#footnote_link_1-50" class="footnote_backlink">50</a>
 Notice that we have used block structure (section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.8">1.1.8</a>) to embed the definitions of <tt>pi-next</tt> and <tt>pi-term</tt> within <tt>pi-sum</tt>, since these procedures are unlikely to be useful for any other purpose. We will see how to get rid of them altogether in section&nbsp;<a href="book-Z-H-12.html#%_sec_1.3.2">1.3.2</a>.
</p></div>

<div id="footnote_1-51" class="footnote">
<p><a href="#footnote_link_1-51" class="footnote_backlink">51</a>
 The intent of exercises&nbsp;<a href="book-Z-H-12.html#%_thm_1.31">1.31</a>-<a href="book-Z-H-12.html#%_thm_1.33">1.33</a> is to demonstrate the expressive power that is attained by using an appropriate abstraction to consolidate many seemingly disparate operations. However, though accumulation and filtering are elegant ideas, our hands are somewhat tied in using them at this point since we do not yet have data structures to provide suitable means of combination for these abstractions. We will return to these ideas in section&nbsp;<a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a> when we show how to use <em>sequences</em> as interfaces for combining filters and accumulators to build even more powerful abstractions. We will see there how these methods really come into their own as a powerful and elegant approach to designing programs.
</p></div>

<div id="footnote_1-52" class="footnote">
<p><a href="#footnote_link_1-52" class="footnote_backlink">52</a>
 This formula was discovered by the seventeenth-century English mathematician John Wallis.
</p></div>

<div id="footnote_1-53" class="footnote">
<p><a href="#footnote_link_1-53" class="footnote_backlink">53</a>
 It would be clearer and less intimidating to people learning Lisp if a name more obvious than <tt>lambda</tt>, such as <tt>make-procedure</tt>, were used. But the convention is firmly entrenched. The notation is adopted from the $\lambda$ calculus, a mathematical formalism introduced by the mathematical logician Alonzo Church (1941). Church developed the $\lambda$ calculus to provide a rigorous foundation for studying the notions of function and function application. The $\lambda$ calculus has become a basic tool for mathematical investigations of the semantics of programming languages.
</p></div>

<div id="footnote_1-54" class="footnote">
<p><a href="#footnote_link_1-54" class="footnote_backlink">54</a>
 Understanding internal definitions well enough to be sure a program means what we intend it to mean requires a more elaborate model of the evaluation process than we have presented in this chapter. The subtleties do not arise with internal definitions of procedures, however. We will return to this issue in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a>, after we learn more about evaluation.
</p></div>

<div id="footnote_1-55" class="footnote">
<p><a href="#footnote_link_1-55" class="footnote_backlink">55</a>
 We have used 0.001 as a representative &ldquo;small&rdquo; number to indicate a tolerance for the acceptable error in a calculation. The appropriate tolerance for a real calculation depends upon the problem to be solved and the limitations of the computer and the algorithm. This is often a very subtle consideration, requiring help from a numerical analyst or some other kind of magician.
</p></div>

<div id="footnote_1-56" class="footnote">
<p><a href="#footnote_link_1-56" class="footnote_backlink">56</a>
 This can be accomplished using <tt>error</tt>, which takes as arguments a number of items that are printed as error messages.
</p></div>

<div id="footnote_1-57" class="footnote">
<p><a href="#footnote_link_1-57" class="footnote_backlink">57</a>
 Try this during a boring lecture: Set your calculator to radians mode and then repeatedly press the <tt>cos</tt> button until you obtain the fixed point.
</p></div>

<div id="footnote_1-58" class="footnote">
<p><a href="#footnote_link_1-58" class="footnote_backlink">58</a>
  $\mapsto$ (pronounced &ldquo;maps to&rdquo;) is the mathematician's way of writing <tt>lambda</tt>. $y \mapsto x/y$ means <tt>(lambda(y) (/ x y))</tt>, that is, the function whose value at $y$ is $x/y$.
</p></div>

<div id="footnote_1-59" class="footnote">
<p><a href="#footnote_link_1-59" class="footnote_backlink">59</a>
 Observe that this is a combination whose operator is itself a combination. Exercise&nbsp;<a href="book-Z-H-10.html#%_thm_1.4">1.4</a> already demonstrated the ability to form such combinations, but that was only a toy example. Here we begin to see the real need for such combinations &mdash; when applying a procedure that is obtained as the value returned by a higher-order procedure.
</p></div>

<div id="footnote_1-60" class="footnote">
<p><a href="#footnote_link_1-60" class="footnote_backlink">60</a>
 See exercise&nbsp;<a href="book-Z-H-12.html#%_thm_1.45">1.45</a> for a further generalization.
</p></div>

<div id="footnote_1-61" class="footnote">
<p><a href="#footnote_link_1-61" class="footnote_backlink">61</a>
 Elementary calculus books usually describe Newton's method in terms of the sequence of approximations <em>x</em><sub><em>n</em>+1</sub> = <em>x</em><sub><em>n</em></sub> - <em>g</em>(<em>x</em><sub><em>n</em></sub>)/<em>D</em><em>g</em>(<em>x</em><sub><em>n</em></sub>). Having language for talking about processes and using the idea of fixed points simplifies the description of the method.
</p></div>

<div id="footnote_1-62" class="footnote">
<p><a href="#footnote_link_1-62" class="footnote_backlink">62</a>
 Newton's method does not always converge to an answer, but it can be shown that in favorable cases each iteration doubles the number-of-digits accuracy of the approximation to the solution. In such cases, Newton's method will converge much more rapidly than the half-interval method.
</p></div>

<div id="footnote_1-63" class="footnote">
<p><a href="#footnote_link_1-63" class="footnote_backlink">63</a>
 For finding square roots, Newton's method converges rapidly to the correct solution from any starting point.
</p></div>

<div id="footnote_1-64" class="footnote">
<p><a href="#footnote_link_1-64" class="footnote_backlink">64</a>
 The notion of first-class status of programming-language elements is due to the British computer scientist Christopher Strachey (1916-1975).
</p></div>

<div id="footnote_1-65" class="footnote">
<p><a href="#footnote_link_1-65" class="footnote_backlink">65</a>
 We'll see examples of this after we introduce data structures in chapter&nbsp;2.
</p></div>

<div id="footnote_1-66" class="footnote">
<p><a href="#footnote_link_1-66" class="footnote_backlink">66</a>
 The major implementation cost of first-class procedures is that allowing procedures to be returned as values requires reserving storage for a procedure's free variables even while the procedure is not executing. In the Scheme implementation we will study in section&nbsp;<a href="book-Z-H-26.html#%_sec_4.1">4.1</a>, these variables are stored in the procedure's environment.
</p></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>