2-1-data.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.1 - Introduction to Data Abstraction </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-3-hop.html'> <img src='images/chevron-left.svg' height=64 width=64> </a>
<a href='2-2-closure.html'> <img src='images/chevron-right.svg' height=64 width=64> </a>
</span>
<br> <br>
<h2> Introduction to Data Abstraction </h2>

<hr>

<p> In section 1.1.8, we noted that a procedure used as an element in creating a more complex procedure could be regarded not only as a collection of particular operations but also as a procedural abstraction. That is, the details of how the procedure was implemented could be suppressed, and the particular procedure itself could be replaced by any other procedure with the same overall behavior. In other words, we could make an abstraction that would separate the way the procedure would be used from the details of how the procedure would be implemented in terms of more primitive procedures. The analogous notion for compound data is called <em>data abstraction</em>. Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed from more primitive data objects.

<p> The basic idea of data abstraction is to structure the programs that are to use compound data objects so that they operate on "abstract data." That is, our programs should use data in such a way as to make no assumptions about the data that are not strictly necessary for performing the task at hand. At the same time, a "concrete" data representation is defined independent of the programs that use the data. The interface between these two parts of our system will be a set of procedures, called <em>selectors</em> and <em>constructors</em>, that implement the abstract data in terms of the concrete representation. To illustrate this technique, we will consider how to design a set of procedures for manipulating rational numbers.

<h3> Example: Arithmetic Operations for Rational Numbers </h3> 

<p> Suppose we want to do arithmetic with rational numbers. We want to be able to add, subtract, multiply, and divide them and to test whether two rational numbers are equal.

<p> Let us begin by assuming that we already have a way of constructing a rational number from a numerator and a denominator. We also assume that, given a rational number, we have a way of extracting (or selecting) its numerator and its denominator. Let us further assume that the constructor and selectors are available as procedures:

<ul>

<li> 
<tt>(make-rat n d)</tt> returns therational number whose
numerator is the integer <tt>n</tt> and whose denominator is the integer <tt>d</tt>.
</li>

<li>
<tt>(numer x)</tt> returns the numerator of the rational number <tt>x</tt>.
</li>

<li>
<tt>(denom x)</tt> returns the denominator of the rational number <tt>x.</tt>
</li>
</ul>

<p> We are using here a powerful strategy of synthesis: <em>wishful thinking</em>. We haven't yet said how a rational number is represented, or how the procedures <tt>numer</tt>, <tt>denom</tt>, and <tt>make-rat</tt> should be implemented. Even so, if we did have these three procedures, we could then add, subtract, multiply, divide, and test equality by using the following relations:

$$
\frac{n_1}{d_1} - \frac{n_2}{d_2} = \frac{n_1 d_2 - n_2 d_1}{d_1 d_2}
$$

<p> We can express these rules as procedures:

<div id="scheme-define-arith-rat">
(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))
</div>
<script>
promptDep("scheme-define-arith-rat", ["scheme-define-rat"]);
</script>

<p> Now we have the operations on rational numbers defined in terms of the selector and constructor procedures <tt>numer, denom,</tt> and <tt>make-rat</tt>. But we haven't yet defined these. What we need is some way to glue together a numerator and a denominator to form a rational number.

<h4> Pairs </h4> 

<p> To enable us to implement the concrete level of our data abstraction, our language provides a compound structure called a <em>pair</em>, which can be constructed with the primitive procedure <tt>cons</tt>. This procedure takes two arguments and returns a compound data object that contains the two arguments as parts. Given a pair, we can extract the parts using the primitive procedures <tt>car</tt> and <tt>cdr</tt>. <a name="footnote_link_2-2" class="footnote_link" href="#footnote_2-2">2</a> Thus, we can use <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> as follows:

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

<div id="scheme-car-x">
(car x)
</div>
<script>
promptDep("scheme-car-x", ["scheme-define-x-cons-1-2"]);
</script>

<div id="scheme-cdr-x">
(cdr x)
</div>
<script>
promptDep("scheme-cdr-x", ["scheme-define-x-cons-1-2"]);
</script>

<p> Notice that a pair is a data object that can be given a name and manipulated, just like a primitive data object. Moreover, <tt>cons</tt> can be used to form pairs whose elements are pairs, and so on:

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

<p>

<div id="scheme-car-car-z">
(car (car z))
</div>
<script>
promptDep("scheme-car-car-z", ["scheme-define-xyz"]);
</script>

<p>

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

<p> In section 2-2 we will see how this ability to combine pairs means that pairs can be used as general-purpose building blocks to create all sorts of complex data structures. The single compound-data primitive <em>pair</em>, implemented by the procedures <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>, is the only glue we need. Data objects constructed from pairs are called <em>list-structured</em> data.

<h4> Representing rational numbers </h4> 

<p> Pairs offer a natural way to complete the rational-number system. Simply represent a rational number as a pair of two integers: a numerator and a denominator. Then <tt>make-rat, numer,</tt> and <tt>denom</tt> are readily implemented as follows:<a name="footnote_link_2-3" class="footnote_link" href="#footnote_2-3">3</a>

<div id="scheme-define-rat">
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
</div>
<script>
prompt("scheme-define-rat");
</script>

<p> Also, in order to display the results of our computations, we can print rational numbers by printing the numerator, a slash, and the denominator:<a name="footnote_link_2-4" class="footnote_link" href="#footnote_2-4">4</a>

<div id="scheme-define-print-rat">
(define (print-rat x)
  (display (numer x))
  (display '/)
  (display (denom x))
  (newline))
</div>
<script>
promptDep("scheme-define-print-rat", ["scheme-define-rat"]);
</script>

<p> Now we can try our rational-number procedures:

<div id="scheme-define-one-half">
(define one-half (make-rat 1 2))
</div>
<script>
promptDep("scheme-define-one-half", ["scheme-define-rat"]);
</script>

<div id="scheme-print-one-half">
(print-rat one-half)
</div>
<script>
promptDep("scheme-print-one-half", ["scheme-define-print-rat", "scheme-define-one-half"]);
</script>

<p>

<div id="scheme-define-one-third">
(define one-third (make-rat 1 3))
</div>
<script>
promptDep("scheme-define-one-third", ["scheme-define-rat"]);
</script>

<p>

<div id="scheme-print-half-plus-third">
(print-rat (add-rat one-half one-third))
</div>
<script>
promptDep("scheme-print-half-plus-third", ["scheme-define-one-half", "scheme-define-one-third", "scheme-define-arith-rat", "scheme-define-print-rat"]);
</script>

<p>

<div id="scheme-print-half-times-third">
(print-rat (mul-rat one-half one-third))
</div>
<script>
promptDep("scheme-print-half-times-third", ["scheme-define-one-half", "scheme-define-one-third", "scheme-define-arith-rat", "scheme-define-print-rat"]);
</script>

<p>

<div id="scheme-print-third-plus-third">
(print-rat (add-rat one-third one-third))
</div>
<script>
promptDep("scheme-print-third-plus-third", ["scheme-define-one-half", "scheme-define-one-third", "scheme-define-arith-rat", "scheme-define-print-rat"]);
</script>

<p> As the final example shows, our rational-number implementation does not reduce rational numbers to lowest terms. We can remedy this by changing <tt>make-rat.</tt> If we have a <tt>gcd</tt> procedure like the one in section 1-2-5 that produces the greatest common divisor of two integers, we can use <tt>gcd</tt> to reduce the numerator and the denominator to lowest terms before constructing the pair:

<div id="scheme-define-gcd">
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
</div>
<script>
hidden_prompt("scheme-define-gcd");
</script>

<div id="scheme-define-make-rat-reduce">
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))
</div>
<script>
promptDep("scheme-define-make-rat-reduce", ["scheme-define-gcd"]);
</script>

<p> Now we have

<div id="scheme-test-rat-reduce">
(print-rat (add-rat one-third one-third))
</div>
<script>
promptDep("scheme-test-rat-reduce", ["scheme-define-arith-rat", "scheme-define-one-half", "scheme-define-one-third", "scheme-define-print-rat", "scheme-define-make-rat-reduce"]);
</script>

<p> as desired. This modification was accomplished by changing the constructor <tt>make-rat</tt> without changing any of the procedures (such as <tt>add-rat</tt> and <tt>mul-rat</tt>) that implement the actual operations.

<div class="exercise">
<p> <b> Exercise 2.1. </b> Define a better version of <tt>make-rat</tt> that handles both positive and negative arguments. <tt>Make-rat</tt> should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.
</div>

<h3> Abstraction Barriers </h3> 

<p> Before continuing with more examples of compound data and data abstraction, let us consider some of the issues raised by the rational-number example. We defined the rational-number operations in terms of a constructor <tt>make-rat</tt> and selectors <tt>numer</tt> and <tt>denom</tt>. In general, the underlying idea of data abstraction is to identify for each type of data object a basic set of operations in terms of which all manipulations of data objects of that type will be expressed, and then to use only those operations in manipulating the data.

<p> We can envision the structure of the rational-number system as shown in Figure 2-1. The horizontal lines represent <em>abstraction barriers</em> that isolate different "levels" of the system. At each level, the barrier separates the programs (above) that use the data abstraction from the programs (below) that implement the data abstraction. Programs that use rational numbers manipulate them solely in terms of the procedures supplied "for public use" by the rational-number package: <tt>add-rat</tt>, <tt>sub-rat</tt>, <tt>mul-rat</tt>, <tt>div-rat</tt>, and <tt>equal-rat?</tt>. These, in turn, are implemented solely in terms of the constructor and selectors <tt>make-rat</tt>, <tt>numer</tt>, and <tt>denom</tt>, which themselves are implemented in terms of pairs. The details of how pairs are implemented are irrelevant to the rest of the rational-number package so long as pairs can be manipulated by the use of <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>. In effect, procedures at each level are the interfaces that define the abstraction barriers and connect the different levels.

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

<p style="text-align:center"> Figure 2.1:  Data-abstraction barriers in the rational-number package.

<p> This simple idea has many advantages. One advantage is that it makes programs much easier to maintain and to modify. Any complex data structure can be represented in a variety of ways with the primitive data structures provided by a programming language. Of course, the choice of representation influences the programs that operate on it; thus, if the representation were to be changed at some later time, all such programs might have to be modified accordingly. This task could be time-consuming and expensive in the case of large programs unless the dependence on the representation were to be confined by design to a very few program modules.

<p> For example, an alternate way to address the problem of reducing rational numbers to lowest terms is to perform the reduction whenever we access the parts of a rational number, rather than when we construct it. This leads to different constructor and selector procedures:

<div id="scheme-define-rat-reduce-in-constructor">
(define (make-rat n d)
  (cons n d))

(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))

(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))
</div>
<script>
promptDep("scheme-define-rat-reduce-in-constructor", ["scheme-define-gcd"]);
</script>

<p> The difference between this implementation and the previous one lies in when we compute the <tt>gcd</tt>. If in our typical use of rational numbers we access the numerators and denominators of the same rational numbers many times, it would be preferable to compute the <tt>gcd</tt> when the rational numbers are constructed. If not, we may be better off waiting until access time to compute the <tt>gcd</tt>. In any case, when we change from one representation to the other, the procedures <tt>add-rat</tt>, <tt>sub-rat</tt>, and so on do not have to be modified at all.

<p> Constraining the dependence on the representation to a few interface procedures helps us design programs as well as modify them, because it allows us to maintain the flexibility to consider alternate implementations. To continue with our simple example, suppose we are designing a rational-number package and we can't decide initially whether to perform the <tt>gcd</tt> at construction time or at selection time. The data-abstraction methodology gives us a way to defer that decision without losing the ability to make progress on the rest of the system.

<div class="exercise">
<p> <b> Exercise 2.2. </b> Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor <tt>make-segment</tt> and selectors <tt>start-segment</tt> and <tt>end-segment</tt> that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor <tt>make-point</tt> and selectors <tt>x-point</tt> and <tt>y-point</tt> that define this representation. Finally, using your selectors and constructors, define a procedure <tt>midpoint-segment</tt> that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:

<div id="scheme-define-print-point">
(define (print-point p)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")")
  (newline))
</div>
<script>
prompt("scheme-define-print-point");
</script>
</div>

<p>

<div class="exercise">
<p> <b> Exercise 2.3. </b> Implement a representation for rectangles in a plane. (Hint: You may want to make use of Exercise 2-2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?
</div>

<h3> What Is Meant by Data? </h3> 

<p> We began the rational-number implementation in section 2-1-1 by implementing the rational-number operations <tt>add-rat</tt>, <tt>sub-rat</tt>, and so on in terms of three unspecified procedures: <tt>make-rat</tt>, <tt>numer</tt>, and <tt>denom</tt>. At that point, we could think of the operations as being defined in terms of data objects---numerators, denominators, and rational numbers---whose behavior was specified by the latter three procedures. 

<p> But exactly what is meant by <em>data</em>  ?  It is not enough to say "whatever is implemented by the given selectors and constructors."  Clearly, not every arbitrary set of three procedures can serve as an appropriate basis for the rational-number implementation. We need to guarantee that, if we construct a rational number <tt>x</tt> from a pair of integers <tt>n</tt> and <tt>d</tt>, then extracting the <tt>numer</tt> and the <tt>denom</tt> of <tt>x</tt> and dividing them should yield the same result as dividing <tt>n</tt> by <tt>d</tt>. In other words, <tt>make-rat</tt>, <tt>numer</tt>, and <tt>denom</tt> must satisfy the condition that, for any integer <tt>n</tt> and any non-zero integer <tt>d</tt>, if <tt>x</tt> is (<tt>make-rat n d</tt>), then

$$
\frac{\text{(numer x)}}{\text{(denom x)}} = \frac{n}{d}
$$

<p> In fact, this is the only condition <tt>make-rat</tt>, <tt>numer</tt>, and <tt>denom</tt> must fulfill in order to form a suitable basis for a rational-number representation. In general, we can think of data as defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfill in order to be a valid representation. <a name="footnote_link_2-5" class="footnote_link" href="#footnote_2-5">5</a>

<p> This point of view can serve to define not only "high-level" data objects, such as rational numbers, but lower-level objects as well. Consider the notion of a pair, which we used in order to define our rational numbers. We never actually said what a pair was, only that the language supplied procedures <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> for operating on pairs. But the only thing we need to know about these three operations is that if we glue two objects together using <tt>cons</tt> we can retrieve the objects using <tt>car</tt> and <tt>cdr</tt>. That is, the operations satisfy the condition that, for any objects <tt>x</tt> and <tt>y</tt>, if <tt>z</tt> is <tt>(cons x y)</tt> then <tt>(car z)</tt> is <tt>x</tt> and <tt>(cdr z)</tt> is <tt>y</tt>. Indeed, we mentioned that these three procedures are included as primitives in our language. However, any triple of procedures that satisfies the above condition can be used as the basis for implementing pairs. This point is illustrated strikingly by the fact that we could implement <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> without using any data structures at all but only using procedures. Here are the definitions:

<div id="scheme-define-cons">
(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))
</div>
<script>
prompt("scheme-define-cons");
</script>

<p> This use of procedures corresponds to nothing like our intuitive notion of what data should be. Nevertheless, all we need to do to show that this is a valid way to represent pairs is to verify that these procedures satisfy the condition given above. 

<p> The subtle point to notice is that the value returned by <tt>(cons x y)</tt> is a procedure---namely the internally defined procedure <tt>dispatch</tt>, which takes one argument and returns either <tt>x</tt> or <tt>y</tt> depending on whether the argument is 0 or 1. Correspondingly, <tt>(car z)</tt> is defined to apply <tt>z</tt> to 0. Hence, if <tt>z</tt> is the procedure formed by <tt>(cons x y)</tt>, then <tt>z</tt> applied to 0 will yield <tt>x</tt>. Thus, we have shown that <tt>(car (cons x y))</tt> yields <tt>x</tt>, as desired. Similarly, <tt>(cdr (cons x y))</tt> applies the procedure returned by <tt>(cons x y)</tt> to 1, which returns <tt>y</tt>. Therefore, this procedural implementation of pairs is a valid implementation, and if we access pairs using only <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> we cannot distinguish this implementation from one that uses "real" data structures.

<p> The point of exhibiting the procedural representation of pairs is not that our language works this way (Scheme, and Lisp systems in general, implement pairs directly, for efficiency reasons) but that it could work this way. The procedural representation, although obscure, is a perfectly adequate way to represent pairs, since it fulfills the only conditions that pairs need to fulfill. This example also demonstrates that the ability to manipulate procedures as objects automatically provides the ability to represent compound data. This may seem a curiosity now, but procedural representations of data will play a central role in our programming repertoire. This style of programming is often called <em>message passing</em>  , and we will be using it as a basic tool in Chapter 3 when we address the issues of modeling and simulation.

<div class="exercise">
<p> <b> Exercise 2.4. </b> Here is an alternative procedural representation of pairs. For this representation, verify that <tt>(car (cons x y))</tt> yields <tt>x</tt> for any objects <tt>x</tt> and <tt>y</tt>. 

<div id="scheme-define-cons-lambda">
(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))
</div>
<script>
prompt("scheme-define-cons-lambda");
</script>

<p> What is the corresponding definition of <tt>cdr</tt>? 

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

  var code = "{0} \n {1} \n (= (cdr (cons 1 2)) 2)".format(editorOf["scheme-define-cons-lambda"].getValue(), editorOf["scheme-ex-define-cdr"].getValue());

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

/*
(define (cdr z)
  (z (lambda (p q) q)))
*/
</script>

<p> Hint: To verify that this works, make use of the substitution model of section 1-1-5.
</div>

<p>

<div class="exercise">
<p> <b> Exercise 2.5. </b> Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair $a$ and $b$ as the integer that is the product $2^a 3^b$. Give the corresponding definitions of the procedures <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>.

<div id="scheme-ex-define-cons-using-2-3">
(define (cons a b)
  'your-answer-here)
</div>
<script>
makeEditable("scheme-ex-define-cons-using-2-3");
addOutput("scheme-ex-define-cons-using-2-3");
editorOf["scheme-ex-define-cons-using-2-3"].setOption("onBlur", function(){

  var code = "{0} \n (= (cons 1 2) 18)".format(editorOf["scheme-ex-define-cons-using-2-3"].getValue());

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

/*
(define (cons a b)
  (* (expt 2 a)
     (expt 3 b)))
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b> Exercise 2.6. </b> In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing $0$ and the operation of adding $1$ as

<div id="scheme-define-church-numeral">
(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))
</div>
<script>
prompt("scheme-define-church-numeral");
/*
(define one (lambda (f)
              (lambda (x)
                (f x))))

(define two (lambda (f)
              (lambda (x)
                (f (f x)))))
*/
</script>

<p> This representation is known as <em>Church numerals</em>  , after its inventor, Alonzo Church, the logician who invented the lambda calculus. 

<p> Define <tt>one</tt> and <tt>two</tt> directly (not in terms of <tt>zero</tt> and <tt>add-1</tt>). (Hint: Use substitution to evaluate <tt>(add-1 zero)</tt>). Give a direct definition of the addition procedure <tt>+</tt> (not in terms of repeated application of <tt>add-1</tt>).
</div>

<h3> Extended Exercise: Interval Arithmetic </h3> 

<p> Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measured parameters of physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision.

<p> Electrical engineers will be using Alyssa's system to compute electrical quantities. It is sometimes necessary for them to compute the value of a parallel equivalent resistance R_p of two resistors $R_1$ and $R_2$ using the formula

$$
R_p = \frac{1}{\frac{1}{R_1} + \frac{1}{R_2}}
$$

<p> Resistance values are usually known only up to some tolerance guaranteed by the manufacturer of the resistor. For example, if you buy a resistor labeled "6.8 ohms with 10% tolerance" you can only be sure that the resistor has a resistance between 6.8 - 0.68 = 6.12 and 6.8 + 0.68 = 7.48 ohms. Thus, if you have a 6.8-ohm 10% resistor in parallel with a 4.7-ohm 5% resistor, the resistance of the combination can range from about 2.58 ohms (if the two resistors are at the lower bounds) to about 2.97 ohms (if the two resistors are at the upper bounds).

<p> Alyssa's idea is to implement "interval arithmetic" as a set of arithmetic operations for combining "intervals" (objects that represent the range of possible values of an inexact quantity). The result of adding, subtracting, multiplying, or dividing two intervals is itself an interval, representing the range of the result.

<p> Alyssa postulates the existence of an abstract object called an "interval" that has two endpoints: a lower bound and an upper bound. She also presumes that, given the endpoints of an interval, she can construct the interval using the data constructor <tt>make-interval</tt>. Alyssa first writes a procedure for adding two intervals. She reasons that the minimum value the sum could be is the sum of the two lower bounds and the maximum value it could be is the sum of the two upper bounds:

<div id="scheme-define-add-interval">
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
</div>
<script>
prompt("scheme-define-add-interval");
</script>

<p> Alyssa also works out the product of two intervals by finding the minimum and the maximum of the products of the bounds and using them as the bounds of the resulting interval. (<tt>Min</tt> and <tt>max</tt> are primitives that find the minimum or maximum of any number of arguments.)

<div id="scheme-define-mul-interval">
(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
</div>
<script>
prompt("scheme-define-mul-interval");
</script>

<p> To divide two intervals, Alyssa multiplies the first by the reciprocal of the second. Note that the bounds of the reciprocal interval are the reciprocal of the upper bound and the reciprocal of the lower bound, in that order.

<div id="scheme-define-div-interval">
(define (div-interval x y)
  (mul-interval x
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))
</div>
<script>
prompt("scheme-define-div-interval");
</script>

<p>

<div class="exercise">
<p> <b>Exercise 2.7:</b> Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:

<div id="scheme-define-make-interval">
(define (make-interval a b) (cons a b))
</div>
<script>
prompt("scheme-define-make-interval");
</script>

<p> Define selectors <tt>upper-bound</tt> and <tt>lower-bound</tt> to complete the implementation.

<div id="scheme-ex-define-upper-lower-bound">
(define (lower-bound interval)
  'your-answer-here)

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

  var code = "{0} \n (= (upper-bound (cons 1 2)) 2)".format(editorOf["scheme-ex-define-upper-lower-bound"].getValue());

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

/*
(define lower-bound car)
(define upper-bound cdr)
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.8:</b> Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called <tt>sub-interval</tt>.

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

  var code = "{0} \n {1} \n {2} \n (equal? (sub-interval (cons 3 4) (cons 1 2)) (cons 1 3))".format(editorOf["scheme-define-make-interval"].getValue(), editorOf["scheme-ex-define-upper-lower-bound"].getValue() ,editorOf["scheme-ex-define-sub-interval"].getValue());

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

/*
(define (sub-interval a b)
  (make-interval (- (lower-bound a) (upper-bound b))
                 (- (upper-bound a) (lower-bound b))))
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.9:</b> The <tt>width</tt>  of an interval is half of the difference between its upper and lower bounds. The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic operations the width of the result of combining two intervals is a function only of the widths of the argument intervals, whereas for others the width of the combination is not a function of the widths of the argument intervals. Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted). Give examples to show that this is not true for multiplication or division.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.10:</b> Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans (includes) zero. Modify Alyssa's code to check for this condition and to signal an error if it occurs.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.11:</b> In passing, Ben also cryptically comments: "By testing the signs of the endpoints of the intervals, it is possible to break <tt>mul-interval</tt> into nine cases, only one of which requires more than two multiplications."  Rewrite this procedure using Ben's suggestion.

<p> After debugging her program, Alyssa shows it to a potential user, who complains that her program solves the wrong problem. He wants a program that can deal with numbers represented as a center value and an additive tolerance; for example, he wants to work with intervals such as 3.5 +/- 0.15 rather than [3.35, 3.65]. Alyssa returns to her desk and fixes this problem by supplying an alternate constructor and alternate selectors: 

<div id="scheme-define-make-center-width">
(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))
</div>
<script>
prompt("scheme-define-make-center-width");
</script>

<p> Unfortunately, most of Alyssa's users are engineers. Real engineering situations usually involve measurements with only a small uncertainty, measured as the ratio of the width of the interval to the midpoint of the interval. Engineers usually specify percentage tolerances on the parameters of devices, as in the resistor specifications given earlier.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.12:</b> Define a constructor <tt>make-center-percent</tt> that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector <tt>percent</tt> that produces the percentage tolerance for a given interval. The <tt>center</tt> selector is the same as the one shown above.


<div id="scheme-ex-define-make-center-percent">
(define (make-center-percent center percent)
  'your-answer-here)

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

  var code = "{0} \n {1} \n {2} \n {3} \n (define i (make-center-percent 2 100)) \n (and (equal? i (cons 0 4)) (equal? (percent i) 100))".format(
    editorOf["scheme-define-make-interval"].getValue(), 
    editorOf["scheme-ex-define-upper-lower-bound"].getValue(), 
    editorOf["scheme-define-make-center-width"].getValue(), 
    editorOf["scheme-ex-define-make-center-percent"].getValue());

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

/*
(define (make-center-percent center percent)
  (make-center-width center (* 0.01 center percent)))

(define (percent interval)
  (* 100 (/ (width interval)
            (center interval)))) 
*/
</script>

</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.13:</b> Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

<p> After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

$$
\frac{R_1 R_2}{R_1 + R_2}
$$

<p> and

$$
\frac{1}{\frac{1}{R_1} + \frac{1}{R_2}}
$$

<p> He has written the following two programs, each of which computes the parallel-resistors formula differently:

<div id="scheme-define-par">
(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))

(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))
</div>
<script>
prompt("scheme-define-par");
</script>

<p> Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.14:</b> Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see Exercise 2-12).
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.15:</b> Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, <tt>par2</tt> is a "better" program for parallel resistances than <tt>par1</tt>. Is she right?  Why?
</div>

<p>

<div class="exercise">
<p> <b>Exercise 2.16:</b> Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible?  (Warning: This problem is very difficult.)
</div>


<br>
<br>

<hr>

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

<div id="footnote_2-2" class="footnote"> 
<p> <a href="#footnote_link_2-2" class="footnote_backlink">2</a> The name <tt>cons</tt> stands for "construct."  The names <tt>car</tt> and <tt>cdr</tt> derive from the original implementation of Lisp on the IBM 704. That machine had an addressing scheme that allowed one to reference the "address" and "decrement" parts of a memory location. <tt>Car</tt> stands for "Contents of Address part of Register" and <tt>cdr</tt> (pronounced "could-er") stands for "Contents of Decrement part of Register." 
</div>

<div id="footnote_2-3" class="footnote"> 
<p> <a href="#footnote_link_2-3" class="footnote_backlink">3</a> Another way to define the selectors and constructor is

<div id="scheme-define-rat-pointless">
(define make-rat cons)
(define numer car)
(define denom cdr)
</div>
<script>
prompt("scheme-define-rat-pointless");
</script>

<p> The first definition associates the name <tt>make-rat</tt> with the value of the expression <tt>cons</tt>, which is the primitive procedure that constructs pairs. Thus <tt>make-rat</tt> and <tt>cons</tt> are names for the same primitive constructor.

<p> Defining selectors and constructors in this way is efficient: Instead of <tt>make-rat</tt> <em>calling</em> <tt>cons</tt>, <tt>make-rat</tt> <em>is</em> <tt>cons</tt>, so there is only one procedure called, not two, when <tt>make-rat</tt> is called. On the other hand, doing this defeats debugging aids that trace procedure calls or put breakpoints on procedure calls: You may want to watch <tt>make-rat</tt> being called, but you certainly don't want to watch every call to <tt>cons</tt>.

We have chosen not to use this style of definition in this book.
</div>

<div id="footnote_2-4" class="footnote"> 
<p> <a href="#footnote_link_2-4" class="footnote_backlink">4</a> <tt>display</tt> is the Scheme primitive for printing data. The Scheme primitive <tt>newline</tt> starts a new line for printing. Neither of these procedures returns a useful value, so in the uses of <tt>print-rat</tt> below, we show only what <tt>print-rat</tt> prints, not what the interpreter prints as the value returned by <tt>print-rat</tt>. </div>

<div id="footnote_2-5" class="footnote">
<p> <a href="#footnote_link_2-5" class="footnote_backlink">5</a> Surprisingly, this idea is very difficult to formulate rigorously. There are two approaches to giving such a formulation. One, pioneered by C. A. R. Hoare (1972), is known as the method of <em>abstract models</em>. It formalizes the "procedures plus conditions" specification as outlined in the rational-number example above. Note that the condition on the rational-number representation was stated in terms of facts about integers (equality and division). In general, abstract models define new kinds of data objects in terms of previously defined types of data objects. Assertions about data objects can therefore be checked by reducing them to assertions about previously defined data objects. Another approach, introduced by Zilles at MIT, by Goguen, Thatcher, Wagner, and Wright at IBM (see Thatcher, Wagner, and Wright 1978), and by Guttag at Toronto (see Guttag 1977), is called <em>algebraic specification</em>. It regards the "procedures" as elements of an abstract algebraic system whose behavior is specified by axioms that correspond to our "conditions," and uses the techniques of abstract algebra to check assertions about data objects. Both methods are surveyed in the paper by Liskov and Zilles (1975).
</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>