Assignment 2

Feb 7: fixed typo (in two places) where (+ 2 3) was written instead of the correct infix expression (2 + 3). Your code will not be tested on invalid input such as (+ 2 3). The typo was only in this spec, the testcases were correct.

Complete version Feb 1.

Main changes from the draft version:

• Renamed question 1 function toeuclidto avoid conflict with the built-ingcdfunction


• Slightly changed marks for questions 4 and 6 based on the length of my sample solutions. Question 4 is now worth 4 marks (was 3) and Question 6 is now worth 3 marks (was 4).


• Added missing ERROR HANDLING details and simplifying assumptions


• Added examples


• Added public tests ina2-public-tests.lisp
  


• Added more details on questions 6+7


• General proofreading and improving the formulations

This assignment is dueFeb 24at 23:55pm. Submit through the button on eClass.NO LATE SUBMISSIONS.

This assignment should be submitted as asingletext file namedassignment2.lisp.

All our examples, and more public test cases, are in filea2-public-tests.lisp. Also see the comments in that file.

Overview

In this assignment, yousimplify "math-like" arithmetic expressions in infix form. In infix form as used in mathematics, operators are written between the arguments, e.g.(3 + 5)instead of the Lisp-style(+ 3 5).

Main Goal of this Assignment

Your task is to simplify a given arithmetic expression as much as possible, and return the simplest expression as the function result. That simplest expression will either be an integer, or a fraction represented as a dotted pair. As part of this assignment, you first develop some helper functions. Then you solve different versions of the simplification problem. The details are stated below.

The main restriction is that we only deal with the operations +, -, *, and /, and that all arguments evaluate to integers or fractions represented in dotted pair notation. Therefore, all expressions eventually simplify to an integer or a dotted pair representing a fraction.

TYPES OF EXPRESSIONS IN THIS ASSIGNMENT

There are two types of numbers in this assignment:

• integers are represented in the usual way, e.g. 5, -13, 0


• A fraction p/q is represented by a dotted pair(p . q)
  

Other than numbers, there are three main types of expressions in this assignment:binaryexpr,infixexprandvarexpr. Avarexprcan contain other atoms that are the names of variables. However, all variables will be bound so you can evaluate them. See details below.

Details ofbinaryexpr

In a binary infix expression or
binaryexpr
, each operatorophas exactly two arguments,(arg1 op arg2). The arguments can be numbers, as defined above, or otherbinaryexpr. A more formal definition is:

• An integer is abinaryexpr
  


• Ifpandqare integer, then(p . q)is abinaryexpr
  


• IfE1andE2arebinaryexpr, then(E1 + E2), (E1 - E2), (E1 * E2)and(E1 / E2)arebinaryexpr
  


• Nothing else is abinaryexpr
  

Details ofinfixexpr

A general infix expression or
infixexpr
can contain an arbitrary number of arguments, with an operator between every two arguments:

(arg0 op1 arg1 op2 arg2 .... opn argn)

Formally:

• Anybinaryexpris aninfixexpr
  


• Ifn ≥ 2,arg0 ... argnareinfixexpr, andop1 ... opnare valid operators (see above), then(arg0 op1 arg1 op2 arg2 .... opn argn)is aninfixexpr.


• Nothing else is ainfixexpr
  

Rules for evaluatinginfixexpr

Forinfixexprwith multiple operators, such as(2 + 3 * 5 - 7 / 4), the usual rules of mathematics apply:

• Multiplication and division have the same precedence


• Addition and subtraction have the same precedence


• Multiplication and division have higher precedence than addition and subtraction


• Operators of the same precedence are left-associative. For example,(2 / 3 * 4) = ((2 / 3) * 4)
  

For example, the following terms are all equivalent:(2 + 3 * 5 - 7 / 4) = (2 + (3 * 5) - (7 / 4)) = ((2 + (3 * 5)) - (7 / 4))

Details ofvarexpr

Avarexpris like aninfixexpr, but with one more base case:

• A single letter atoma,...,zis avarexpr
  

For brevity, I do not write out the full specification. Let me know if you need it.

#1 (1 mark)

Write a Lisp function:

(euclid x y)

x and y are nonnegative integers. Compute the greatest common divisor of x and y usingEuclid's algorithm.

Hint: thebuilt in mod functionwill be handy.

Restrictions: there is a built-in gcd function in Lisp - do not use it or any other such shortcuts. Program out Euclid's algorithm yourself. There are tons of Lisp gcd examples out there on the internet, but of course you program this function yourself without looking.

Error handling: if either x or y are 0, return the atom GCD-ERROR. Note that this is different from the built-in gcd.

Examples:

(euclid 5 1) 1  (euclid 15 3) 3  (euclid 100 4) 4  (euclid 0 2) GCD-ERROR

See moreeuclidexamples in public tests.

#2 (1 mark)

Write a Lisp function:

(simplifyfraction F)

Given a fraction p/q represented by a dotted pair F = (p . q) with integers p, q, return the simplest fraction equal to p/q, in the same dotted-pair format. This simplest fraction is uniquely defined as x/y with y>0, gcd(x,y) = 1, and x/y = p/q.

Special case: if the result of simplifying (p . q) is an integer, then just return that integer instead of the dotted pair.

Error handling: if q is 0, return the atom ZERODIVIDE-ERROR.

Examples:

(simplifyfraction '(5 . 1)) 5  (simplifyfraction '(15 . 5)) 3  (simplifyfraction '(-100 . -4)) 25  (simplifyfraction '(0 . 2)) 0  (simplifyfraction '(105 . 6)) (35 . 2)  (simplifyfraction '(4 . -8)) (-1 . 2)  (simplifyfraction '(10 . 0)) ZERODIVIDE-ERROR

Moresimplifyfractionexamples are in public tests.

#3 (4 marks)

Write a Lisp function:

(simplifybinary E)

Given abinaryexprE, evaluate E according to the rules of arithmetic (as stated above) and return the simplest result as follows:

• Anything that can be further evaluated should be


• An integer is simpler than a fraction, i.e. return 5 not (5 . 1)


• Fractions must be in simplest form as computed bysimplifyfractionabove

Error handling: if at any step division by zero occurs, return the atom ZERODIVIDE-ERROR.

Examples:

(simplifybinary 5) 5  (simplifybinary '(50 . -10)) -5  (simplifybinary '(60 . 8)) (15 . 2)  (simplifybinary '(3 + 5)) 8  (simplifybinary '(((1 + 1) * (1 + 1)) * ((1 + 1) * (1 + 1)))) 16  (simplifybinary '(1 + (1 + ((1 / 2) + ((1 / (2 * 3)) + ((1 / ((2 * 3) * 4)) + (1 / (((2 * 3) * 4) * 5))))))))  (163 . 60)

See many moresimplifybinaryExamples in public tests.

#4 (4 marks)

Write a Lisp function:

(binarize E)

Given aninfixexprE, return the equivalentbinaryexprWITHOUT ANY SIMPLIFICATION and without error checking.

Examples:

(binarize 2) 2  (binarize '(2 + 3)) (2 + 3)  (binarize '(2 / 3 * 4)) ((2 / 3) * 4)  (binarize '(2 + 3 + 5 - 7 + 4)) ((((2 + 3) + 5) - 7) + 4)  (binarize '(2 + 3 * 5 - 7 / 4)) ((2 + (3 * 5)) - (7 / 4))  (binarize '(2 + 3 * 5 / 7 / 4)) (2 + (((3 * 5) / 7) / 4))  (binarize '((1 . 2) + (3 . 5) + (7 . 4))) (((1 . 2) + (3 . 5)) + (7 . 4))  (binarize '((2 + 3 + 5 - 7 + 4) * (2 + 3 + 5 - 7 + 4))) (((((2 + 3) + 5) - 7) + 4) * ((((2 + 3) + 5) - 7) + 4))  (binarize '(0 / 0 / 0 / 0 / 0)) ((((0 / 0) / 0) / 0) / 0) Note - no division by zero checking.

See morebinarizeExamples in public tests.

#5 (1 mark)

Write a Lisp function:

(simplify E)

Given aninfixexprE, evaluate E according to the rules of arithmetic (as stated above) and return the simplest result.

Error handling: if at any step division by zero occurs, return the atom ZERODIVIDE-ERROR.

Examples:

(simplify '(2 + 3 * 5 - 7 / 4)) (61 . 4)  (simplify '(1 + 1 + 1 / 2 + 1 / (2 * 3) + 1 / (2 * 3 * 4) + 1 / (2 * 3 * 4 * 5))) (163 . 60)

See many moresimplifyExamples in public tests.

#6 (3 marks)

Write a Lisp function:

(substitutevar Bindings E)

Here,Bindingsis a list of pairs(Name InfixE), whereNameis a single letter name andInfixEis aninfixexpr. E is avarexpr.

Return aninfixexprE' as follows: First, simplify all theInfixEinBindings, then substitute all variables in E with their (simplified) values, and return the equivalentinfixexpr, WITHOUT ANY FURTHER SIMPLIFICATION of E. So, the only change from input E to output E' is to substitute variables by their values.

Restrictions and simplifications: All variables that occur in E will be defined inBindings. So your result E' is a validinfixexprthat will not contain any variables. Theinfixexprused withinBindingswill not lead to any ZERODIVIDE-ERROR.

Error handling: no error handling is required. All inputs will be valid.

Basic examples:

(substitutevar '((x 1)) '(2 + x)) (2 + 1)  (substitutevar '((x 1) (y (2 + 3))) '(x + x + y)) (1 + 1 + 5)

See many moresubstitutevarExamples in public tests.

#7 (1 mark)

Write a Lisp function:

(simplifyvar Bindings E)

GivenBindingsas in question #6 and avarexprE, evaluate E according to the rules of arithmetic (as stated above) and return the simplest result.

Error handling and simplifications: if at any step of evaluating E, division by zero occurs, return the atom ZERODIVIDE-ERROR. As in question #6, theinfixexprwithinBindingswill not lead to any ZERODIVIDE-ERROR. However, evaluating E itself may lead to such errors.

Basic examples:

(simplifyvar '((x 1)) '(2 + x)) 3  (simplifyvar '((x 1) (y (2 + 3))) '(x + x + y)) 7

See many moresimplifyvarExamples in public tests.

MARKING

Your solutions have to be general to get any marks, i.e. you cannot just hardcode the public test cases and their answers.

There is a total of 15 marks. The assignment counts for 7.5% of your course total.

LEARNING OUTCOMES

These are some of the learning outcomes from working on this assignment:

• Gain practical experience in programming with Lisp from solving a medium-size problem


• Practice breaking down a problem into a set of functions, which together solve the problem


• Systematically build a solution to a more complex problem by rephrasing it using a set of simpler subproblems


• Study the problem of evaluation of nested expressions


• Structure given data according to given rules about precedence and evaluation order


• Build your own datatypes for computing with fractions and arithmetic expressions


• Work with substitution in a simple let-like environment


• Work with testcases to develop a solution incrementally

HINTS AND DETAILS - READ THEM ALL

• Before submitting,make sure your program runs correctly on our lab machines.


• For commenting and organizing your code, follow theprogramming style and marking guidelineand also the detailed explanations at the start ofAssignment 1.


• Restrictions: There are no restrictions on the use of built-in Lisp functions and special forms in this assignment, other than the ones explicitly stated. That said, there are still style marks, so do your comments properly, and stay true to the spirit of pure functional programming: avoid non-pure idioms such as destructive assignments, global variables, explicit loop constructs etc.


• While in general, your code should load without warnings in sbcl, due to the nature of this assignment you may want to have a small number of mutually recursive functions, where a calls b and b calls a. We will accept a modest number of warnings about such cases without deduction. (For example, in my sample solution there is one such case.)


• To test whether a s-expr is an integer, useintegerp.
  Examples:
  
  (integerp 22)and(integerp (+ 3 4))return T
  
  (integerp 23.5), (integerp 'a), (integerp '(+ 3 4)), (integerp nil)all return NIL.


• We donotuse shortcut evaluation in this assignment, in order to guarantee a definitive result when there is an error somewhere in an expression. So we do not simplify terms such as (0 * REST) to 0 without evaluating REST. For example, evaluating(0 * (1 / 0))gives a ZERODIVIDE-ERROR. See the testcases for more such examples.


• Dealing with fractions represented by dotted pairs: all our dotted pairs will be fully instantiated with integers, i.e. expressions such as (45 . 3). We will not have dotted pairs with variables, such as (P . Q), or dotted pairs with other expressions inside, such as ((1 + 2) . 3). Those are not validbinaryexpr,infixexprorvarexprby the rules above. If you see them appear in your tests, we strongly recommend that you figure out why, and change your code.

End of Assignment 2.