# Comp200 Project 2 solution

\$24.99

Original Work ?

## Description

Introduction
Please submit your project and required image ﬁles electronically as described in the “Project Submissions” handout.
Code for this project:
• code ﬁles to read: curve-utils.scm, curves.scm, points segs.scm, curves setup.scm (For MitScheme) or curves setup racket.scm (For Racket) • code ﬁle simply to load: drawing.scm (For Mit-Scheme) or drawing racket (For Racket) • If you are going to do this assignment in Racket, please use DrRacket with R5RS language. In order to use R5RS language, click Languages on the top menu, click on Choose Language and then select R5RS language from Other Languages section. After that, click on Show Details, uncheck Disallow redeﬁnition of initial bindings and you will be ﬁnally able to complete this assignment in DrRacket environment.
One of the things that makes Scheme diﬀerent from other common programming languages is the ability to operate with higher-order procedures, namely, procedures that manipulate and generate other procedures. This project will give you extensive practice with higher-order procedures, in the context of a language for graphing two-dimensional curves and other shapes. The project comes in three parts. The ﬁrst gives you some experience in writing procedures and manipulating simple data structures. We recommend that you get started on this part as soon as you can. The second part deals with types of procedures, and is intended to help you understand diﬀerent kinds of higher order procedures. This leads directly to the third part, where you will write some higher order procedures to graph interesting curves.
Part 1: Simple Procedures for Planar Geometry
Let’s get some practice in writing procedures and manipulating data structures by considering some simple procedures for dealing with polygons in the plane. A polygon is an ordered sequence of line segments, where each line segment is represented by a start and end point (and implicitly all the points along the line between these two points). Of course, it is not just a random set of line segments, but rather a continuous one, in which the end point of one segment becomes the start point for the next, and in which the end point of the last segment is the start point of the ﬁrst one.
The ﬁle points segs.scm contains some simple deﬁnitions for constructing points (with an x and y coordinate) and segments, using Scheme’s basic constructor list. You should load this ﬁle into your Scheme so you can use these deﬁnitions and read it before attempting the exercises below.
1
Exercise 1:
Given a segment, we might want to know its length. Write a procedure segment-length that computes the length of a segment. Be sure to use the correct selectors for the data abstractions for segments and for points. Show some examples of your procedure in operation.
Exercise 2:
Now suppose you have a set of segments representing a polygon, and you want to compute the perimeter of the polygon. Write a recursive procedure called perimeter, using segment-length as a component, that takes as input a list of segments, and returns the sum of the lengths of the segments. Demonstrate this procedure working on test-segments.
Exercise 3:
In the previous exercise, we provided you with a pre-made list of segments. More generally, however, you will want to create a polygon as a list of segments, by connecting points together. Suppose you are given an ordered list of points, e.g., test-points, and you want to convert this to an ordered list of segments. To do so, you want to make a segment out of the ﬁrst and second point, a segment out of the second and third point and so on. But you also need to make a segment out of the last and ﬁrst point, to completely connect the polygon. One easy way to do this is to create a new list, in which the ﬁrst point of the original list is added at the end of the list (think about using append), and then recursively creating segments out of pairs of points. Write a procedure to do this. Compare its performance when applied to test-points, to the predeﬁned test-segments.
Exercise 4:
A useful characteristic of a polygon is its centroid, which is deﬁned as the average of the points of the polygon. We can compute this in a variety of ways. First, let’s think about adding two points together (that is, treating them as vectors). Write a procedure add-two-points that takes as input two points, and returns a new point, whose coordinates are the sums of the coordinates of the input points. Be sure to use appropriate constructors and selectors. Show your procedure working on some test cases.
Next, generalize this to add up a list of points, by writing a procedure add-all-points that uses add-two-points recursively to add up all the points.
Finally, use this procedure to write a procedure for computing the centroid of a list of points. Be sure to use the right constructor in generating the return value. Demonstrate this procedure applied to test-points.
Exercise 5:
An alternative way of computing the centroid is to ﬁrst construct a list of all the x-coordinates, then add them up and scale by the length of the list; do the same for the y-coordinates; and then construct the centroid. Implement this variation on computing the centroid, and demonstrate that it ﬁnds the same answer as the previous version.
2
Part 2. Procedure Types and Procedure Constructors
In this assignment we use many procedures which may be applied to many diﬀerent types of arguments and may return diﬀerent types of values. To keep track of this, it will be helpful to have some simple notation to describe types of Scheme values.
Two basic types of values are Number, the Scheme numbers such as 3, -4.2, 6.931479453e89, and Boolean, the truth values #t, #f. The procedure square may be applied to a Number and will return another Number. We indicate this with the type notation:
square: Number → Number
(define (square x) (* x x))
In trigonometry it is common to talk about the function cos2 which is the square of the cosine function. In Scheme, the corresponding procedure would be
(define (cos-square x) (square (cos x)))
Exercise 6:
Explain why the following Scheme deﬁnition does not work. (How would Scheme respond if we evaluated this deﬁnition?)
(define cos-square (square cos))
Of course it really does make sense to square a numerical function, if we get the types right
(define square-a-procedure (lambda (f) (lambda (x) (square (f x)))))
Now the procedure square-a-procedure may be applied to a procedure of type Number→Number and returns another procedure of that type:
square-a-procedure: (Number→Number) → (Number→Number) or, abbreviating Number→Number as F: square-a-procedure: F → F
and now we can say correctly
(define cos-square (square-a-procedure cos))
3
There are many other operations like squaring which can usefully be made into operations on procedures. The method for making such operations is captured by
(define (make-procedure-op number-op) (lambda (f) (lambda (x) (number-op (f x)))))
Note the syntactic sugar being used here. This is equivalent to
(define make-procedure-op (lambda (number-op) (lambda (f) (lambda (x) (number-op (f x))))))
so that there is a hidden lambda that is creating a procedure to associate with the name “makeprocedure-op” (see the textbook for more discussion on this).
Thus, we now can say
(define cos-square ((make-procedure-op square) cos))
That is, make-procedure-op may be applied to an “operator” of type F and returns the corresponding operator on procedures of type F:
make-procedure-op: F → (F → F)
We can also look at operations which can take two arguments, for example, subtraction. The procedure − may be applied to two Number’s and will return a Number. We indicate this with the notation:
− : Number, Number → Number
We can also make binary operations on numbers into operations on procedures:
(define (make-procedure-binop binop) (lambda (f g) (lambda (x) (binop (f x) (g x)))))
(define subtract-procedures (make-procedure-binop -))
We can use this to deﬁne the square-diﬀerence procedure
(define (square-difference f g) (subtract-procedures (square-a-procedure f) (square-a-procedure g)))
square-diﬀerence: F, F → F
4
Exercise 7:
What is the type of make-procedure-binop as it was used in the expression
(make-procedure-binop -)
So far we have made operations on numbers into operations on procedures, but it is actually common to make them into operations on operations on procedures! For example, the procedure deriv of SICP, Section 1.3.4, has type F → F. With it, we can deﬁne another procedure derivsquared of the same type:
(define (deriv-squared f) (square-a-procedure (deriv f)))
Exercise 8:
Explain why the following Scheme deﬁnition does not work. (How would Scheme respond if we evaluated this deﬁnition?)
(define deriv-squared (square-a-procedure deriv))
How about a “squaring” operation which applies to an operation like deriv? No problem:
(define (square-an-operator-on-proc op-on-proc) (lambda (f) (square-a-procedure (op-on-proc f))))
(define deriv-squared (square-an-operator-on-proc deriv))
Exercise 9:
What is the type of square-an-operator-on-proc?
Of course, we can generalize these ideas in other ways. For example, if f and g are procedures of type: Number→ Number, we can compose them:
(define (compose f g) (lambda (x) (f (g x))))
Thus, for example, (compose square log) is the procedure of type Number→Number that returns the square of the logarithm of its argument, while (compose log square) returns the logarithm of the square of its argument:
5
(log 2) ;Value: .693147805599453
((compose square log) 2) ;Value: .4804530139182014
((compose log square) 2) ;Value: 1.3862943611198906
As we have used it above, the procedure compose takes as arguments two procedures of type F=Number→Number, and returns another such procedure. We indicate this with the notation: compose:(F,F)→F
Just as square a number multiplies the number by itself, thrice of a function composes the function three times. That is, ((thrice f) n) will return the same number as (f(f(f n))):
(define (thrice f) (compose (compose f f) f))
((thrice square) 3) ;Value: 6561
(square (square (square 3))) ;Value: 6561
As used above, thrice is of type (F→F). That is, it takes as input a function from numbers to numbers and returns the same kind of function. But thrice will actually work for other kinds of input functions. It is enough for the input function to have a type of the form T→T, where T may be any type. So more generally, we can write
thrice: (T→T) → (T→T)
Composition, like multiplication, may be iterated. Consider the following:
(define (identity x) x)
(define (repeated f n) (if (= n 0) identity (compose f (repeated f (- n 1)))))
((repeated sin 5) 3.1) ;Value: 4.1532801333692235e-2
(sin(sin(sin(sin(sin 3.1))))) ;Value: 4.1532801333692235e-2
6
Exercise 10:
For what value of n will (((thrice thrice) f) 0) return the same value as ((repeated f n) 0) (ignore issues of equality by assuming that f has a value of type F so that the whole expression will return a number)?
Part 3. Curves as Procedures and Data
We’re going to develop a language for deﬁning and drawing planar curves. We’d like to plot points, construct graphs of functions, transform curves by scaling and rotating, and so on. One of the key ideas that we’ll stress throughout this course is that a well-designed language has parts that combine to make new parts that themselves can be combined. This property is called closure.
A planar curve in “parametric form” can be described mathematically as a function from parameter values to points in the plane. For example, we could describe the unit-circle as the function taking t to the point (sin2πt,cos2πt) where t ranges over the unit interval [0,1]. To visualize this representation, you can think of a runner going around the unit-circle in one hour, and our function returns his position when we specify the time t between 0 and 1.
In Scheme, we let Unit-Interval be the type of Scheme-numbers between 0 and 1, and we represent curves by procedures of Scheme type Curve, where
Curve = Unit-Interval → Point
and Point is some representation of pairs of Scheme-Numbers.
To work with Point, we need a constructor, make-point, which constructs Point’s from Number’s, and selectors, x-of and y-of, for getting the x and y coordinates of a Point. We require only that the constructors and selectors obey the rules for all Number’s m,n. In this problem set, we’ll use:
(define (make-point x y) (list x y))
(define (x-of point) (car point))
For example, we can deﬁne the Curve unit-circle and the Curve unit-line (along the x-axis):
(define (unit-circle t) (make-point (sin (* 2pi t)) (cos (* 2pi t))))
7
(define (unit-line-at y) (lambda (t) (make-point t y)))
(define unit-line (unit-line-at 0))
Note that we are already making a conceptual shift in our thinking. Here, a curve is not a geometric set of points, rather it is a procedure for taking number values in the unit interval, and generating the corresponding point. The key is that a curve is a procedure!
Exercise 11:
1. What is the type of unit-line-at?
2. Deﬁne a procedure diagonal-line with two arguments, a point and a length, and returns a line of that length beginning at the point and with tangent (that is, pointing upward at a 45 degree angle). By what we have discussed above, diagonal-line should return a curve (hence a procedure) that takes as input a parameter along the unit line (as do all curves) and returns the appropriate point along the line.
3. What is the type of diagonal-line?
4. Show some examples that test your procedure, and that show it returns the correct value.
In addition to the direct construction of Curve’s such as unit-circle or unit-line, we can use elementary Cartesian geometry in designing Scheme procedures which operate on Curve’s. For example, the mapping (x,y) → (-y, x) rotates the plane by 90 degrees, so
(define (rotate-pi/2 curve) (lambda (t) (let ((ct (curve t))) (make-point (- (y-of ct)) (x-of ct)))))
deﬁnes a procedure which takes a curve and transforms it into another, rotated, curve. The type of rotate-pi/2 is
Curve-Transform = Curve → Curve where Curve = Unit-Interval → Point. Thus, a curve transform is a procedure that converts an input procedure to a new procedure, i.e., a curve transform is a higher order procedure. Note in general that having a framework for describing types enables us to reason about procedures, e.g., knowing the type of an argument and the desired type of the output provides guidance on what must be done within a procedure to execute the desired transformation.
8
Exercise 12:
Write a deﬁnition of a Curve-Transform upside-down, which ﬂips a curve over a horizontal line through its start point. We have provided a variety of other procedure Curve-Transform’s and procedures which construct Curve-Transform’s in the ﬁle curves.scm. For example, • translate returns a Curve-Transform which rigidly moves a curve given distances along the x and y axes, • scale-x-y returns a Curve-Transform which stretches a curve along the x and y coordinates by given scale factors, and • rotate-around-origin returns a Curve-Transform which rotates a curve by a given number of radians.
A convenient, if somewhat more complicated, Curve-Transform is put-in-standard-position. We’ll say a curve is in standard position if its start and end points are the same as the unit-line, namely it starts at the origin, (0,0), and ends at the point (1,0). We can put any curve whose start and endpoints are not the same into standard position by (1) rigidly translating it so its starting point is at the origin, then (2) rotating it about the origin to put its endpoint on the x axis, and (3) ﬁnally scaling it to put the endpoint at (1,0):
(define (put-in-standard-position curve) (let* ((start-point (curve 0)) (curve-started-at-origin ((translate (- (x-of start-point)) (- (y-of start-point))) curve)) (new-end-point (curve-started-at-origin 1)) (theta (atan (y-of new-end-point) (x-of new-end-point))) (curve-ended-at-x-axis ((rotate-around-origin (- theta)) curve-started-at-origin)) (end-point-on-x-axis (x-of (curve-ended-at-x-axis 1)))) ((scale (/ 1 end-point-on-x-axis)) curve-ended-at-x-axis)))
It is useful to have operations which combine curves into new ones. We let Binary-Transform be the type of binary operations on curves, Binary-Transform = (Curve, Curve) → Curve The procedure connect-rigidly is a simple Binary-Transform. Evaluation of (connect-rigidly curve1 curve2) returns a curve consisting of curve1 followed by curve2; the starting point of the curve returned by (connect-rigidly curve1 curve2) is the same as that of curve1 and the end point is the same as that of curve2.