GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

No menu could be recovered. Follow the blue links in the page.

This view

  • Original page
  • New address

GeezerVison is showing sicp.sourceacademy.org — 2.5.3 Example: Symbolic Algebra - SICP Comparison Edition

SICP — Scheme/JS Structure and Interpretation of Computer Programs — Comparison Edition
 
Foreword
Foreword to Structure and Interpretation of Computer Programs, 1984
Preface
Prefaces to Structure and Interpretation of Computer Programs, 1996 & 1984
Acknowledgments
➤ ▼ 1 Building Abstractions with Procedures Functions
➤ ▼ 1.1 The Elements of Programming
1.1.1 Expressions
1.1.2 Naming and the Environment
1.1.3 Evaluating Combinations Operator Combinations
1.1.4 Compound Procedures Functions
1.1.5 The Substitution Model for Procedure Function Application
1.1.6 Conditional Expressions and Predicates
1.1.7 Example: Square Roots by Newton's Method
1.1.8 Procedures Functions as Black-Box Abstractions
➤ ▼ 1.2 Procedures Functions and the Processes They Generate
1.2.1 Linear Recursion and Iteration
1.2.2 Tree Recursion
1.2.3 Orders of Growth
1.2.4 Exponentiation
1.2.5 Greatest Common Divisors
1.2.6 Example: Testing for Primality
➤ ▼ 1.3 Formulating Abstractions with Higher-Order Procedures Functions
1.3.1 Procedures Functions as Arguments
1.3.2 Constructing Procedures using Lambda Constructing Functions using Lambda Expressions
1.3.3 Procedures Functions as General Methods
1.3.4 Procedures Functions as Returned Values
➤ ▼ 2 Building Abstractions with Data
➤ ▼ 2.1 Introduction to Data Abstraction
2.1.1 Example: Arithmetic Operations for Rational Numbers
2.1.2 Abstraction Barriers
2.1.3 What Is Meant by Data?
2.1.4 Extended Exercise: Interval Arithmetic
➤ ▼ 2.2 Hierarchical Data and the Closure Property
2.2.1 Representing Sequences
2.2.2 Hierarchical Structures
2.2.3 Sequences as Conventional Interfaces
2.2.4 Example: A Picture Language
➤ ▼ 2.3 Symbolic Data
2.3.1 Quotation Strings
2.3.2 Example: Symbolic Differentiation
2.3.3 Example: Representing Sets
2.3.4 Example: Huffman Encoding Trees
➤ ▼ 2.4 Multiple Representations for Abstract Data
2.4.1 Representations for Complex Numbers
2.4.2 Tagged data
2.4.3 Data-Directed Programming and Additivity
➤ ▼ 2.5 Systems with Generic Operations
2.5.1 Generic Arithmetic Operations
2.5.2 Combining Data of Different Types
2.5.3 Example: Symbolic Algebra
➤ ▼ 3 Modularity, Objects, and State
➤ ▼ 3.1 Assignment and Local State
3.1.1 Local State Variables
3.1.2 The Benefits of Introducing Assignment
3.1.3 The Costs of Introducing Assignment
➤ ▼ 3.2 The Environment Model of Evaluation
3.2.1 The Rules for Evaluation
3.2.2 Applying Simple Procedures Functions
3.2.3 Frames as the Repository of Local State
3.2.4 Internal Definitions Declarations
3.2.5 CSE Machine
➤ ▼ 3.3 Modeling with Mutable Data
3.3.1 Mutable List Structure
3.3.2 Representing Queues
3.3.3 Representing Tables
3.3.4 A Simulator for Digital Circuits
3.3.5 Propagation of Constraints
➤ ▼ 3.4 Concurrency: Time Is of the Essence
3.4.1 The Nature of Time in Concurrent Systems
3.4.2 Mechanisms for Controlling Concurrency
➤ ▼ 3.5 Streams
3.5.1 Streams Are Delayed Lists
3.5.2 Infinite Streams
3.5.3 Exploiting the Stream Paradigm
3.5.4 Streams and Delayed Evaluation
3.5.5 Modularity of Functional Programs and Modularity of Objects
➤ ▼ 4 Metalinguistic Abstraction
➤ ▼ 4.1 The Metacircular Evaluator
4.1.1 The Core of the Evaluator
4.1.2 Representing Expressions Components
4.1.3 Evaluator Data Structures
4.1.4 Running the Evaluator as a Program
4.1.5 Data as Programs
4.1.6 Internal Definitions Declarations
4.1.7 Separating Syntactic Analysis from Execution
➤ ▼ 4.2 Variations on a Scheme: Lazy Evaluation
4.2.1 Normal Order and Applicative Order
4.2.2 An Interpreter with Lazy Evaluation
4.2.3 Streams as Lazy Lists
➤ ▼ 4.3 Variations on a Scheme: Nondeterministic Computing
4.3.1 Amb and Search Search and amb
4.3.2 Examples of Nondeterministic Programs
4.3.3 Implementing the Amb amb Evaluator
➤ ▼ 4.4 Logic Programming
4.4.1 Deductive Information Retrieval
4.4.2 How the Query System Works
4.4.3 Is Logic Programming Mathematical Logic?
4.4.4 Implementing the Query System
➤ ▼ 5 Computing with Register Machines
➤ ▼ 5.1 Designing Register Machines
5.1.1 A Language for Describing Register Machines
5.1.2 Abstraction in Machine Design
5.1.3 Subroutines
5.1.4 Using a Stack to Implement Recursion
5.1.5 Instruction Summary
➤ ▼ 5.2 A Register-Machine Simulator
5.2.1 The Machine Model
5.2.2 The Assembler
5.2.3 Generating Execution Procedures for Instructions Instructions and Their Execution Functions
5.2.4 Monitoring Machine Performance
➤ ▼ 5.3 Storage Allocation and Garbage Collection
5.3.1 Memory as Vectors
5.3.2 Maintaining the Illusion of Infinite Memory
➤ ▼ 5.4 The Explicit-Control Evaluator
5.4.1 The Core of the Explicit-Control Evaluator The Dispatcher and Basic Evaluation
5.4.2 Sequence Evaluation and Tail Recursion Evaluating Function Applications
5.4.3 Conditionals, Assignments and Definitions Blocks, Assignments, and Declarations
5.4.4 Running the Evaluator
➤ ▼ 5.5 Compilation
5.5.1 Structure of the Compiler
5.5.2 Compiling Expressions Components
5.5.3 Compiling Combinations Applications and Return Statements
5.5.4 Combining Instruction Sequences
5.5.5 An Example of Compiled Code
5.5.6 Lexical Addressing
5.5.7 Interfacing Compiled Code to the Evaluator
References
About the SICP JS Project
Permalink copied!
2.5.3 Example: Symbolic Algebra

The manipulation of symbolic algebraic expressions is a complex process that illustrates many of the hardest problems that occur in the design of large-scale systems. An algebraic expression, in general, can be viewed as a hierarchical structure, a tree of operators applied to operands. We can construct algebraic expressions by starting with a set of primitive objects, such as constants and variables, and combining these by means of algebraic operators, such as addition and multiplication. As in other languages, we form abstractions that enable us to refer to compound objects in simple terms. Typical abstractions in symbolic algebra are ideas such as linear combination, polynomial, rational function, or trigonometric function. We can regard these as compound types, which are often useful for directing the processing of expressions. For example, we could describe the expression \[ x^{2}\, \sin (y^2+1)+x\, \cos 2y+\cos (y^3 -2y^2) \] as a polynomial in $x$ with coefficients that are trigonometric functions of polynomials in $y$ whose coefficients are integers.

We will not attempt to develop a complete algebraic-manipulation system here. Such systems are exceedingly complex programs, embodying deep algebraic knowledge and elegant algorithms. What we will do is look at a simple but important part of algebraic manipulation: the arithmetic of polynomials. We will illustrate the kinds of decisions the designer of such a system faces, and how to apply the ideas of abstract data and generic operations to help organize this effort.

Arithmetic on polynomials

Our first task in designing a system for performing arithmetic on polynomials is to decide just what a polynomial is. Polynomials are normally defined relative to certain variables (the indeterminates of the polynomial). For simplicity, we will restrict ourselves to polynomials having just one indeterminate (univariate polynomials).[1] We will define a polynomial to be a sum of terms, each of which is either a coefficient, a power of the indeterminate, or a product of a coefficient and a power of the indeterminate. A coefficient is defined as an algebraic expression that is not dependent upon the indeterminate of the polynomial. For example, \[ 5x^2 +3x +7 \] is a simple polynomial in $x$, and \[ (y^2 +1)x^3 +(2y)x+1 \] is a polynomial in $x$ whose coefficients are polynomials in $y$.

Already we are skirting some thorny issues. Is the first of these polynomials the same as the polynomial $5y^2 +3y +7$, or not? A reasonable answer might be yes, if we are considering a polynomial purely as a mathematical function, but no, if we are considering a polynomial to be a syntactic form. The second polynomial is algebraically equivalent to a polynomial in $y$ whose coefficients are polynomials in $x$. Should our system recognize this, or not? Furthermore, there are other ways to represent a polynomial—for example, as a product of factors, or (for a univariate polynomial) as the set of roots, or as a listing of the values of the polynomial at a specified set of points.[2] We can finesse these questions by deciding that in our algebraic-manipulation system a polynomial will be a particular syntactic form, not its underlying mathematical meaning.

Now we must consider how to go about doing arithmetic on polynomials. In this simple system, we will consider only addition and multiplication. Moreover, we will insist that two polynomials to be combined must have the same indeterminate.

We will approach the design of our system by following the familiar discipline of data abstraction. We will represent polynomials using a data structure called a poly, which consists of a variable and a collection of terms. We assume that we have selectors variable and term-list term_list that extract those parts from a poly and a constructor make-poly make_poly that assembles a poly from a given variable and a term list. A variable will be just a symbol, string, so we can use the same-variable? is_same_variable procedure function of section 2.3.2 to compare variables. The following procedures functions define addition and multiplication of polys:

Original JavaScript
(define (add-poly p1 p2) (if (same-variable? (variable p1) (variable p2)) (make-poly (variable p1) (add-terms (term-list p1) (term-list p2))) (error "Polys not in same var - - ADD-POLY" (list p1 p2)))) (define (mul-poly p1 p2) (if (same-variable? (variable p1) (variable p2)) (make-poly (variable p1) (mul-terms (term-list p1) (term-list p2))) (error "Polys not in same var - - MUL-POLY" (list p1 p2)))) function add_poly(p1, p2) { return is_same_variable(variable(p1), variable(p2)) ? make_poly(variable(p1), add_terms(term_list(p1), term_list(p2))) : error(list(p1, p2), "polys not in same var -- add_poly"); } function mul_poly(p1, p2) { return is_same_variable(variable(p1), variable(p2)) ? make_poly(variable(p1), mul_terms(term_list(p1), term_list(p2))) : error(list(p1, p2), "polys not in same var -- mul_poly"); }

To incorporate polynomials into our generic arithmetic system, we need to supply them with type tags. We'll use the tag polynomial, "polynomial", and install appropriate operations on tagged polynomials in the operation table.

Original JavaScript
We'll embed all our code in an installation procedure for the polynomial package, similar to the ones in section 2.5.1: (define (install-polynomial-package) ;; internal procedures ;; representation of poly (define (make-poly variable term-list) (cons variable term-list)) (define (variable p) (car p)) (define (term-list p) (cdr p)) $langle$ procedures same-variable? and variable? from section 2.3.2 $\rangle$ ;; representation of terms and term lists $langle$ procedures adjoin-term $\ldots$ coeff from text below $langle$ (define (add-poly p1 p2) $\ldots$) $langle$ procedures used by add-poly $langle$ (define (mul-poly p1 p2) $\ldots$) $langle$procedures used by mul-poly $langle$ ;; interface to rest of the system (define (tag p) (attach-tag 'polynomial p)) (put 'add '(polynomial polynomial) (lambda (p1 p2) (tag (add-poly p1 p2)))) (put 'mul '(polynomial polynomial) (lambda (p1 p2) (tag (mul-poly p1 p2)))) (put 'make 'polynomial (lambda (var terms) (tag (make-poly var terms)))) 'done) We'll embed all our code in an installation function for the polynomial package, similar to the installation functions in section 2.5.1: function install_polynomial_package() { // internal functions // representation of poly function make_poly(variable, term_list) { return pair(variable, term_list); } function variable(p) { return head(p); } function term_list(p) { return tail(p); } $\langle{}$functions is_same_variable and is_variable from section 2.3.2$\rangle$ // representation of terms and term lists $\langle{}$functions adjoin_term...coeff from text below$\rangle$ function add_poly(p1, p2) { ... } $\langle{}$functions used by add_poly$\rangle$ function mul_poly(p1, p2) { ... } $\langle{}$functions used by mul_poly$\rangle$ // interface to rest of the system function tag(p) { return attach_tag("polynomial", p); } put("add", list("polynomial", "polynomial"), (p1, p2) => tag(add_poly(p1, p2))); put("mul", list("polynomial", "polynomial"), (p1, p2) => tag(mul_poly(p1, p2))); put("make", "polynomial", (variable, terms) => tag(make_poly(variable, terms))); return "done"; }

Polynomial addition is performed termwise. Terms of the same order (i.e., with the same power of the indeterminate) must be combined. This is done by forming a new term of the same order whose coefficient is the sum of the coefficients of the addends. Terms in one addend for which there are no terms of the same order in the other addend are simply accumulated into the sum polynomial being constructed.

In order to manipulate term lists, we will assume that we have a constructor the-empty-termlist the_empty_termlist that returns an empty term list and a constructor adjoin-term adjoin_term that adjoins a new term to a term list. We will also assume that we have a predicate empty-termlist? is_empty_termlist that tells if a given term list is empty, a selector first-term first_term that extracts the highest-order term from a term list, and a selector rest-terms rest_terms that returns all but the highest-order term. To manipulate terms, we will suppose that we have a constructor make-term make_term that constructs a term with given order and coefficient, and selectors order and coeff that return, respectively, the order and the coefficient of the term. These operations allow us to consider both terms and term lists as data abstractions, whose concrete representations we can worry about separately.

Here is the procedure function that constructs the term list for the sum of two polynomials:polynomials;[3]

Original JavaScript
note that we slightly extend the syntax of conditional statements described in section 1.3.2 by admitting another conditional statement in place of the block following else:
Original JavaScript
(define (add-terms L1 L2) (cond ((empty-termlist? L1) L2) ((empty-termlist? L2) L1) (else (let ((t1 (first-term L1)) (t2 (first-term L2))) (cond ((> (order t1) (order t2)) (adjoin-term t1 (add-terms (rest-terms L1) L2))) ((< (order t1) (order t2)) (adjoin-term t2 (add-terms L1 (rest-terms L2)))) (else (adjoin-term (make-term (order t1) (add (coeff t1) (coeff t2))) (add-terms (rest-terms L1) (rest-terms L2))))))))) function add_terms(L1, L2) { if (is_empty_termlist(L1)) { return L2; } else if (is_empty_termlist(L2)) { return L1; } else { const t1 = first_term(L1); const t2 = first_term(L2); return order(t1) > order(t2) ? adjoin_term(t1, add_terms(rest_terms(L1), L2)) : order(t1) < order(t2) ? adjoin_term(t2, add_terms(L1, rest_terms(L2))) : adjoin_term(make_term(order(t1), add(coeff(t1), coeff(t2))), add_terms(rest_terms(L1), rest_terms(L2))); } }
The most important point to note here is that we used the generic addition procedure function add to add together the coefficients of the terms being combined. This has powerful consequences, as we will see below.

In order to multiply two term lists, we multiply each term of the first list by all the terms of the other list, repeatedly using mul-term-by-all-terms, mul_term_by_all_terms, which multiplies a given term by all terms in a given term list. The resulting term lists (one for each term of the first list) are accumulated into a sum. Multiplying two terms forms a term whose order is the sum of the orders of the factors and whose coefficient is the product of the coefficients of the factors:

Original JavaScript
(define (mul-terms L1 L2) (if (empty-termlist? L1) (the-empty-termlist) (add-terms (mul-term-by-all-terms (first-term L1) L2) (mul-terms (rest-terms L1) L2)))) (define (mul-term-by-all-terms t1 L) (if (empty-termlist? L) (the-empty-termlist) (let ((t2 (first-term L))) (adjoin-term (make-term (+ (order t1) (order t2)) (mul (coeff t1) (coeff t2))) (mul-term-by-all-terms t1 (rest-terms L)))))) function mul_terms(L1, L2) { return is_empty_termlist(L1) ? the_empty_termlist : add_terms(mul_term_by_all_terms( first_term(L1), L2), mul_terms(rest_terms(L1), L2)); } function mul_term_by_all_terms(t1, L) { if (is_empty_termlist(L)) { return the_empty_termlist; } else { const t2 = first_term(L); return adjoin_term( make_term(order(t1) + order(t2), mul(coeff(t1), coeff(t2))), mul_term_by_all_terms(t1, rest_terms(L))); } }

This is really all there is to polynomial addition and multiplication. Notice that, since we operate on terms using the generic procedures functions add and mul, our polynomial package is automatically able to handle any type of coefficient that is known about by the generic arithmetic package. If we include a coercion mechanism such as one of those discussed in section 2.5.2, then we also are automatically able to handle operations on polynomials of different coefficient types, such as \[ \begin{array}{l} {\left[3x^2 +(2+3i)x+7\right] \cdot \left[x^4 +\frac{2}{3}x^2 +(5+3i)\right]} \end{array} \]

Because we installed the polynomial addition and multiplication procedures functions add-poly add_poly and mul-poly mul_poly in the generic arithmetic system as the add and mul operations for type polynomial, our system is also automatically able to handle polynomial operations such as \[ \begin{array}{l} {\left[ (y+1)x^2 +(y^2 +1)x+(y-1)\right]\cdot \left[(y-2)x+(y^3 +7)\right]} \end{array} \] The reason is that when the system tries to combine coefficients, it will dispatch through add and mul. Since the coefficients are themselves polynomials (in $y$), these will be combined using add-poly add_poly and mul-poly. mul_poly. The result is a kind of data-directed recursion in which, for example, a call to mul-poly mul_poly will result in recursive calls to mul-poly mul_poly in order to multiply the coefficients. If the coefficients of the coefficients were themselves polynomials (as might be used to represent polynomials in three variables), the data direction would ensure that the system would follow through another level of recursive calls, and so on through as many levels as the structure of the data dictates.[4]

Representing term lists

Finally, we must confront the job of implementing a good representation for term lists. A term list is, in effect, a set of coefficients keyed by the order of the term. Hence, any of the methods for representing sets, as discussed in section 2.3.3, can be applied to this task. On the other hand, our procedures functions add-terms add_terms and mul-terms mul_terms always access term lists sequentially from highest to lowest order. Thus, we will use some kind of ordered list representation.

How should we structure the list that represents a term list? One consideration is the density of the polynomials we intend to manipulate. A polynomial is said to be dense if it has nonzero coefficients in terms of most orders. If it has many zero terms it is said to be sparse. For example, \[ A:\quad x^5 +2x^4 +3x^2 -2x -5 \] is a dense polynomial, whereas \[ B:\quad x^{100} +2x^2 +1 \] is sparse.

The term lists of dense polynomials are most efficiently represented as lists of the coefficients. The term list of a dense polynomial is most efficiently represented as a list of the coefficients. For example, the polynomial $A$ above would be nicely represented as (1 2 0 3 -2 -5). list(1, 2, 0, 3, -2, -5). The order of a term in this representation is the length of the sublist beginning with that term's coefficient, decremented by 1.[5] This would be a terrible representation for a sparse polynomial such as $B$: There would be a giant list of zeros punctuated by a few lonely nonzero terms. A more reasonable representation of the term list of a sparse polynomial is as a list of the nonzero terms, where each term is a list containing the order of the term and the coefficient for that order. In such a scheme, polynomial $B$ is efficiently represented as ((100 1) (2 2) (0 1)). list(list(100, 1), list(2, 2), list(0, 1)). As most polynomial manipulations are performed on sparse polynomials, we will use this method. We will assume that term lists are represented as lists of terms, arranged from highest-order to lowest-order term. Once we have made this decision, implementing the selectors and constructors for terms and term lists is straightforward:[6]

Original JavaScript
(define (adjoin-term term term-list) (if (=zero? (coeff term)) term-list (cons term term-list))) (define (the-empty-termlist) '()) (define (first-term term-list) (car term-list)) (define (rest-terms term-list) (cdr term-list)) (define (empty-termlist? term-list) (null? term-list)) (define (make-term order coeff) (list order coeff)) (define (order term) (car term)) (define (coeff term) (cadr term)) function adjoin_term(term, term_list) { return is_equal_to_zero(coeff(term)) ? term_list : pair(term, term_list); } const the_empty_termlist = null; function first_term(term_list) { return head(term_list); } function rest_terms(term_list) { return tail(term_list); } function is_empty_termlist(term_list) { return is_null(term_list); } function make_term(order, coeff) { return list(order, coeff); } function order(term) { return head(term); } function coeff(term) { return head(tail(term)); }
where =zero? is_equal_to_zero is as defined in exercise 2.80. (See also exercise 2.87 below.)

Users of the polynomial package will create (tagged) polynomials by means of the procedure: function:

Original JavaScript
(define (make-polynomial var terms) ((get 'make 'polynomial) var terms)) function make_polynomial(variable, terms) { return get("make", "polynomial")(variable, terms); }

Exercise 2.87 Install =zero? is_equal_to_zero for polynomials in the generic arithmetic package. This will allow adjoin-term adjoin_term to work for polynomials with coefficients that are themselves polynomials.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 2.88 Extend the polynomial system to include subtraction of polynomials. (Hint: You may find it helpful to define a generic negation operation.)
function sub_terms(L1, L2) { if (is_empty_termlist(L1)) { return L2; } else if (is_empty_termlist(L2)) { return L1; } else { const t1 = first_term(L1); const t2 = first_term(L2); return order(t1) > order(t2) ? adjoin_term(t1, sub_terms(rest_terms(L1), L2)) : order(t1) < order(t2) ? adjoin_term(t2, sub_terms(L1, rest_terms(L2))) : adjoin_term(make_term(order(t1), sub(coeff(t1), coeff(t2))), sub_terms(rest_terms(L1), rest_terms(L2))); } } function sub_poly(p1, p2) { return is_same_variable(variable(p1), variable(p2)) ? make_poly(variable(p1), sub_terms(term_list(p1), term_list(p2))) : error(list(p1, p2), "polys not in same var -- sub_poly"); }
Exercise 2.89 Define procedures Declare functions that implement the term-list representation described above as appropriate for dense polynomials.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 2.90 Suppose we want to have a polynomial system that is efficient for both sparse and dense polynomials. One way to do this is to allow both kinds of term-list representations in our system. The situation is analogous to the complex-number example of section 2.4, where we allowed both rectangular and polar representations. To do this we must distinguish different types of term lists and make the operations on term lists generic. Redesign the polynomial system to implement this generalization. This is a major effort, not a local change.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 2.91 A univariate polynomial can be divided by another one to produce a polynomial quotient and a polynomial remainder. For example, \[ \begin{array}{lll} \dfrac{x^5-1}{x^2 -1} & = & x^3 +x,\ \text{remainder }x-1 \end{array} \] Division can be performed via long division. That is, divide the highest-order term of the dividend by the highest-order term of the divisor. The result is the first term of the quotient. Next, multiply the result by the divisor, subtract that from the dividend, and produce the rest of the answer by recursively dividing the difference by the divisor. Stop when the order of the divisor exceeds the order of the dividend and declare the dividend to be the remainder. Also, if the dividend ever becomes zero, return zero as both quotient and remainder.

We can design a div-poly div_poly procedure function on the model of add-poly add_poly and mul-poly. mul_poly. The procedure function checks to see if the two polys have the same variable. If so, div-poly div_poly strips off the variable and passes the problem to div-terms, div_terms, which performs the division operation on term lists. Div-poly The function div_poly finally reattaches the variable to the result supplied by div-terms. div_terms. It is convenient to design div-terms div_terms to compute both the quotient and the remainder of a division. div-terms The function div_terms can take two term lists as arguments and return a list of the quotient term list and the remainder term list.

Complete the following definition of div-terms div_terms by filling in the missing expressions. parts. Use this to implement div-poly, div_poly, which takes two polys as arguments and returns a list of the quotient and remainder polys.
Original JavaScript
(define (div-terms L1 L2) (if (empty-termlist? L1) (list (the-empty-termlist) (the-empty-termlist)) (let ((t1 (first-term L1)) (t2 (first-term L2))) (if (> (order t2) (order t1)) (list (the-empty-termlist) L1) (let ((new-c (div (coeff t1) (coeff t2))) (new-o (- (order t1) (order t2)))) (let ((rest-of-result compute rest of result recursively )) form complete result )))))) function div_terms(L1, L2) { if (is_empty_termlist(L1)) { return list(the_empty_termlist, the_empty_termlist); } else { const t1 = first_term(L1); const t2 = first_term(L2); if (order(t2) > order(t1)) { return list(the_empty_termlist, L1); } else { const new_c = div(coeff(t1), coeff(t2)); const new_o = order(t1) - order(t2); const rest_of_result = $\langle{}$compute rest of result recursively$\rangle$; $\langle{}$form and return complete result$\rangle$ } } }
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Hierarchies of types in symbolic algebra

Our polynomial system illustrates how objects of one type (polynomials) may in fact be complex objects that have objects of many different types as parts. This poses no real difficulty in defining generic operations. We need only install appropriate generic operations for performing the necessary manipulations of the parts of the compound types. In fact, we saw that polynomials form a kind of recursive data abstraction, in that parts of a polynomial may themselves be polynomials. Our generic operations and our data-directed programming style can handle this complication without much trouble.

On the other hand, polynomial algebra is a system for which the data types cannot be naturally arranged in a tower. For instance, it is possible to have polynomials in $x$ whose coefficients are polynomials in $y$. It is also possible to have polynomials in $y$ whose coefficients are polynomials in $x$. Neither of these types is above the other in any natural way, yet it is often necessary to add together elements from each set. There are several ways to do this. One possibility is to convert one polynomial to the type of the other by expanding and rearranging terms so that both polynomials have the same principal variable. One can impose a towerlike structure on this by ordering the variables and thus always converting any polynomial to a canonical form with the highest-priority variable dominant and the lower-priority variables buried in the coefficients. This strategy works fairly well, except that the conversion may expand a polynomial unnecessarily, making it hard to read and perhaps less efficient to work with. The tower strategy is certainly not natural for this domain or for any domain where the user can invent new types dynamically using old types in various combining forms, such as trigonometric functions, power series, and integrals.

It should not be surprising that controlling coercion is a serious problem in the design of large-scale algebraic-manipulation systems. Much of the complexity of such systems is concerned with relationships among diverse types. Indeed, it is fair to say that we do not yet completely understand coercion. In fact, we do not yet completely understand the concept of a data type. Nevertheless, what we know provides us with powerful structuring and modularity principles to support the design of large systems.

Exercise 2.92 By imposing an ordering on variables, extend the polynomial package so that addition and multiplication of polynomials works for polynomials in different variables. (This is not easy!)
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Extended exercise: Rational functions

We can extend our generic arithmetic system to include rational functions. These are fractions whose numerator and denominator are polynomials, such as \[ \begin{array}{l} \dfrac{x+1}{x^3 -1} \end{array} \] The system should be able to add, subtract, multiply, and divide rational functions, and to perform such computations as \[ \begin{array}{lll} \dfrac{x+1}{x^3 -1}+\dfrac{x}{x^2 -1} & = & \dfrac{x^3 +2x^2 +3x +1}{x^4 + x^3 -x-1} \end{array} \] (Here the sum has been simplified by removing common factors. Ordinary cross multiplication would have produced a fourth-degree polynomial over a fifth-degree polynomial.)

If we modify our rational-arithmetic package so that it uses generic operations, then it will do what we want, except for the problem of reducing fractions to lowest terms.

Exercise 2.93 Modify the rational-arithmetic package to use generic operations, but change make-rat make_rat so that it does not attempt to reduce fractions to lowest terms. Test your system by calling make-rational make_rational on two polynomials to produce a rational function
Original JavaScript
(define p1 (make-polynomial 'x '((2 1)(0 1)))) (define p2 (make-polynomial 'x '((3 1)(0 1)))) (define rf (make-rational p2 p1)) const p1 = make_polynomial("x", list(make_term(2, 1), make_term(0, 1))); const p2 = make_polynomial("x", list(make_term(3, 1), make_term(0, 1))); const rf = make_rational(p2, p1);
Now add rf to itself, using add. You will observe that this addition procedure function does not reduce fractions to lowest terms.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

We can reduce polynomial fractions to lowest terms using the same idea we used with integers: modifying make-rat make_rat to divide both the numerator and the denominator by their greatest common divisor. The notion of greatest common divisor makes sense for polynomials. In fact, we can compute the GCD of two polynomials using essentially the same Euclid's Algorithm that works for integers.[7] The integer version is

Original JavaScript
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
Using this, we could make the obvious modification to define a GCD operation that works on term lists:
Original JavaScript
(define (gcd-terms a b) (if (empty-termlist? b) a (gcd-terms b (remainder-terms a b)))) function gcd_terms(a, b) { return is_empty_termlist(b) ? a : gcd_terms(b, remainder_terms(a, b)); }
where remainder-terms remainder_terms picks out the remainder component of the list returned by the term-list division operation div-terms div_terms that was implemented in exercise 2.91.

Exercise 2.94 Using div-terms, div_terms, implement the procedure function remainder-terms remainder_terms and use this to define gcd-terms gcd_terms as above. Now write a procedure function gcd-poly gcd_poly that computes the polynomial GCD of two polys. (The procedure function should signal an error if the two polys are not in the same variable.) Install in the system a generic operation greatest-common-divisor greatest_common_divisor that reduces to gcd-poly gcd_poly for polynomials and to ordinary gcd for ordinary numbers. As a test, try
Original JavaScript
(define p1 (make-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2)))) (define p2 (make-polynomial 'x '((3 1) (1 -1)))) (greatest-common-divisor p1 p2) const p1 = make_polynomial("x", list(make_term(4, 1), make_term(3, -1), make_term(2, -2), make_term(1, 2))); const p2 = make_polynomial("x", list(make_term(3, 1), make_term(1, -1))); greatest_common_divisor(p1, p2);
and check your result by hand.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 2.95 Define $P_{1}$, $P_{2}$, and $P_{3}$ to be the polynomials
$P_{1}$: $x^2 - 2x + 1$
$P_{2}$: $11x^2 + 7$
$P_{3}$: $13x + 5$
Now define $Q_1$ to be the product of $P_1$ and $P_2$ and $Q_2$ to be the product of $P_1$ and $P_3$, and use greatest-common-divisor greatest_common_divisor (exercise 2.94) to compute the GCD of $Q_1$ and $Q_2$. Note that the answer is not the same as $P_1$. This example introduces noninteger operations into the computation, causing difficulties with the GCD algorithm.[8] algorithm.[9] To understand what is happening, try tracing gcd-terms gcd_terms while computing the GCD or try performing the division by hand.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

We can solve the problem exhibited in exercise 2.95 if we use the following modification of the GCD algorithm (which really works only in the case of polynomials with integer coefficients). Before performing any polynomial division in the GCD computation, we multiply the dividend by an integer constant factor, chosen to guarantee that no fractions will arise during the division process. Our answer will thus differ from the actual GCD by an integer constant factor, but this does not matter in the case of reducing rational functions to lowest terms; the GCD will be used to divide both the numerator and denominator, so the integer constant factor will cancel out.

More precisely, if $P$ and $Q$ are polynomials, let $O_1$ be the order of $P$ (i.e., the order of the largest term of $P$) and let $O_2$ be the order of $Q$. Let $c$ be the leading coefficient of $Q$. Then it can be shown that, if we multiply $P$ by the integerizing factor $c^{1+O_{1} -O_{2}}$, the resulting polynomial can be divided by $Q$ by using the div-terms div_terms algorithm without introducing any fractions. The operation of multiplying the dividend by this constant and then dividing is sometimes called the pseudodivision of $P$ by $Q$. The remainder of the division is called the pseudoremainder.

Exercise 2.96
  1. Implement the procedure function pseudoremainder-terms, pseudoremainder_terms, which is just like remainder-terms remainder_terms except that it multiplies the dividend by the integerizing factor described above before calling div-terms. div_terms. Modify gcd-terms gcd_terms to use pseudoremainder-terms, pseudoremainder_terms, and verify that greatest-common-divisor greatest_common_divisor now produces an answer with integer coefficients on the example in exercise 2.95.
  2. The GCD now has integer coefficients, but they are larger than those of $P_1$. Modify gcd-terms gcd_terms so that it removes common factors from the coefficients of the answer by dividing all the coefficients by their (integer) greatest common divisor.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Thus, here is how to reduce a rational function to lowest terms:

  • Compute the GCD of the numerator and denominator, using the version of gcd-terms gcd_terms from exercise 2.96.
  • When you obtain the GCD, multiply both numerator and denominator by the same integerizing factor before dividing through by the GCD, so that division by the GCD will not introduce any noninteger coefficients. As the factor you can use the leading coefficient of the GCD raised to the power $1+O_{1} -O_{2}$, where $O_{2}$ is the order of the GCD and $O_{1}$ is the maximum of the orders of the numerator and denominator. This will ensure that dividing the numerator and denominator by the GCD will not introduce any fractions.
  • The result of this operation will be a numerator and denominator with integer coefficients. The coefficients will normally be very large because of all of the integerizing factors, so the last step is to remove the redundant factors by computing the (integer) greatest common divisor of all the coefficients of the numerator and the denominator and dividing through by this factor.

Exercise 2.97
  1. Implement this algorithm as a procedure function reduce-terms reduce_terms that takes two term lists n and d as arguments and returns a list nn, dd, which are n and d reduced to lowest terms via the algorithm given above. Also write a procedure function reduce-poly, reduce_poly, analogous to add-poly, add_poly, that checks to see if the two polys have the same variable. If so, reduce-poly reduce_poly strips off the variable and passes the problem to reduce-terms, reduce_terms, then reattaches the variable to the two term lists supplied by reduce-terms. reduce_terms.
  2. Define a procedure function analogous to reduce-terms reduce_terms that does what the original make-rat make_rat did for integers:
    Original JavaScript
    (define (reduce-integers n d) (let ((g (gcd n d))) (list (/ n g) (/ d g)))) function reduce_integers(n, d) { const g = gcd(n, d); return list(n / g, d / g); }
    and define reduce as a generic operation that calls apply-generic apply_generic to dispatch to either reduce-poly either to reduce_poly (for polynomial arguments) or reduce-integers to reduce_integers (for scheme-number javascript_number arguments). You can now easily make the rational-arithmetic package reduce fractions to lowest terms by having make-rat make_rat call reduce before combining the given numerator and denominator to form a rational number. The system now handles rational expressions in either integers or polynomials. To test your program, try the example at the beginning of this extended exercise:
    Original JavaScript
    (define p1 (make-polynomial 'x '((1 1)(0 1)))) (define p2 (make-polynomial 'x '((3 1)(0 -1)))) (define p3 (make-polynomial 'x '((1 1)))) (define p4 (make-polynomial 'x '((2 1)(0 -1)))) (define rf1 (make-rational p1 p2)) (define rf2 (make-rational p3 p4)) (add rf1 rf2) const p1 = make_polynomial("x", list(make_term(1, 1), make_term(0, 1))); const p2 = make_polynomial("x", list(make_term(3, 1), make_term(0, -1))); const p3 = make_polynomial("x", list(make_term(1, 1))); const p4 = make_polynomial("x", list(make_term(2, 1), make_term(0, -1))); const rf1 = make_rational(p1, p2); const rf2 = make_rational(p3, p4); add(rf1, rf2);
    See if you get the correct answer, correctly reduced to lowest terms.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

The GCD computation is at the heart of any system that does operations on rational functions. The algorithm used above, although mathematically straightforward, is extremely slow. The slowness is due partly to the large number of division operations and partly to the enormous size of the intermediate coefficients generated by the pseudodivisions. One of the active areas in the development of algebraic-manipulation systems is the design of better algorithms for computing polynomial GCDs.[10]


[1] On the other hand, we will allow polynomials whose coefficients are themselves polynomials in other variables. This will give us essentially the same representational power as a full multivariate system, although it does lead to coercion problems, as discussed below.
[2] For univariate polynomials, giving the value of a polynomial at a given set of points can be a particularly good representation. This makes polynomial arithmetic extremely simple. To obtain, for example, the sum of two polynomials represented in this way, we need only add the values of the polynomials at corresponding points. To transform back to a more familiar representation, we can use the Lagrange interpolation formula, which shows how to recover the coefficients of a polynomial of degree $n$ given the values of the polynomial at $n+1$ points.
[3] This operation is very much like the ordered union-set union_set operation we developed in exercise 2.62. In fact, if we think of the terms of the polynomial as a set ordered according to the power of the indeterminate, then the program that produces the term list for a sum is almost identical to union-set. union_set.
[4] To make this work completely smoothly, we should also add to our generic arithmetic system the ability to coerce a number to a polynomial by regarding it as a polynomial of degree zero whose coefficient is the number. This is necessary if we are going to perform operations such as \[ {\left[ x^2 +(y+1)x+5\right]+ \left[ x^2 +2x+1\right]} \] which requires adding the coefficient $y+1$ to the coefficient 2.
[5] In these polynomial examples, we assume that we have implemented the generic arithmetic system using the type mechanism suggested in exercise 2.78. Thus, coefficients that are ordinary numbers will be represented as the numbers themselves rather than as pairs whose car head is the symbol scheme-number. string "javascript_number".
[6] Although we are assuming that term lists are ordered, we have implemented adjoin-term adjoin_term to simply cons the new term onto the existing term list. adjoin the new term to the front of the existing term list. We can get away with this so long as we guarantee that the procedures functions (such as add-terms) add_terms) that use adjoin-term adjoin_term always call it with a higher-order term than appears in the list. If we did not want to make such a guarantee, we could have implemented adjoin-term adjoin_term to be similar to the adjoin-set adjoin_set constructor for the ordered-list representation of sets (exercise 2.61).
[7] The fact that Euclid's Algorithm works for polynomials is formalized in algebra by saying that polynomials form a kind of algebraic domain called a Euclidean ring. A Euclidean ring is a domain that admits addition, subtraction, and commutative multiplication, together with a way of assigning to each element $x$ of the ring a positive integer measure $m(x)$ with the properties that $m(xy)\geq m(x)$ for any nonzero $x$ and $y$ and that, given any $x$ and $y$, there exists a $q$ such that $y=qx+r$ and either $r=0$ or $m(r) < m(x)$. From an abstract point of view, this is what is needed to prove that Euclid's Algorithm works. For the domain of integers, the measure $m$ of an integer is the absolute value of the integer itself. For the domain of polynomials, the measure of a polynomial is its degree.
[8] In an implementation like MIT Scheme, this produces a polynomial that is indeed a divisor of $Q_1$ and $Q_2$, but with rational coefficients. In many other Scheme systems, in which division of integers can produce limited-precision decimal numbers, we may fail to get a valid divisor.
[9] In JavaScript, division of integers can produce limited-precision decimal numbers, and thus we may fail to get a valid divisor.
[10] One extremely efficient and elegant method for computing polynomial GCDs was discovered by Richard Zippel (1979). The method is a probabilistic algorithm, as is the fast test for primality that we discussed in chapter 1. Zippel's book (1993) describes this method, together with other ways to compute polynomial GCDs.
< Previous
Next >
2.5.3   Example: Symbolic Algebra
You are visitor 01402639 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.