CS471-Project 2 Solved

The aims of this project are as follows:

•    To become adept with recursive programming.

•    To expose you to functional programming.

•    To familiarize you with programming without using destructive assignment.

1.2          Project Speci cation
Project should contain de nitions for the following functions:

1.      (mul-list list x) which when given a proper list list of numbers returns the list formed by multiplying each element of list by x. 5-points

2.      (sum-lengths list) which when given a proper list list of proper lists returns the sum of the lengths of all the lists contained directly in list. This function should not be tail-recursive. 5-points

3.      (poly-eval coeffs x) which evaluates the polyomial speci ed by list coeffs at x. Speci cally, given a list of n + 1 numeric polynomial coe cients coeffs (c[n] c[n-1] ... c[0]) and a number x, return the value of c[n]×xn+c[n−1]×xn−1+...+c[1]×x+c[0]. Your computation should evaluate each term as written above; i.e. each c[i]×xi term should be explicitly evaluated and added together.. This function should not be tail-recursive. 10-points

4.      (poly-eval-horner coeffs x) which uses Horner’s method to evaluate the polynomial given by list coeffs at number x. The list coeffs is as speci ed in the previous exercise. 10-points

5.      (count-occurrences s-exp x) which given a Scheme s-expression s-exp returns the number of sub-expressions which are equal? to x. 10-points

6.      (arith-eval exp) which returns the result of evaluating arithmetic expression exp, where exp is either a Scheme number or one of ( op exp-1 exp-2 ) where op is one of ’add, ’sub, ’mul or ’div specifying respectively the binary arithmetic operators +, -, *, / and exp-1 and exp-2 are arithmetic expressions. 10-points

7.      (sum-lengths-tr list) with the same speci cation as sum-lengths but with the requirement that all recursive calls must be tail-recursive. 10points

8.      (poly-eval-horner-tr coeffs x) with the same speci cation as poly¬ -eval-horner but with the requirement that all recursive calls must be tail-recursive. 10-points

9.      (mul-list-2 list x) with the same speci cation as mul-list but which replaces all recursion with the use of one or more of map, foldl or foldr. 5-points

10.   Write a function (sum-lengths-2 list) with the same speci cation as sum-lengths but which replaces all recursion with the use of one or more of map‘, foldl or foldr. 5-points

The arith-parse.scm le should contain a de nition of a function (arith-¬ parse tokens) which should return an AST representing the structure of the proper list tokens as speci ed by the following EBNF grammar:

expr

: term ( ’+ term )*

; term

: factor ( ’* factor )*

; factor

: NUMBER

| ’< expr ’

;

Both the ’+ and ’* operators should be left-associative.

The proper list tokens should contain Scheme numbers, ’+, ’* and ’< and ’ (the latter two symbols are used as parentheses). The AST for ’+ and ’* should use tags ’add and ’mul repectively; i.e. the output of arith-parse should be suitable as input to arith-eval.

If tokens cannot be parsed according to the above grammar, then (arith-¬ parse tokens) should return #f. 20-points

The project is subject to the following additional restrictions:

•    You should not use any of Scheme’s mutation operators; i.e. no Scheme function with name ending in ! may be used.

•    The functions de ned in prj2-sol.scm should not de ne any top-level auxiliary functions; i.e. any auxiliary functions needed for the operation of a required function should be de ned within that function. This restriction does not apply to arith-parse.scm.

•    None of the functions may use map, foldl, or foldr unless explicitly speci ed.

•    Some of the function speci cations give implementation restrictions. Those must be followed.

1.3        Example Log
The following provides a log of interaction with the code submitted with this project:

$ racket

Welcome to Racket v7.2. (load "prj2-sol.scm")

(mul-list ’(3 4 5) 8)

’(24 32 40)

(mul-list ’() 8) ’()

(sum-lengths ’( (1 2 3) (()) (() 2 (3 4 5))))

7

(sum-lengths ’( )) 0

(poly-eval ’(5 4 3 2 1) 1)

15

(poly-eval ’(5 4 3 2 1) 2)

129

(poly-eval ’() 1) 0

(poly-eval-horner ’(5 4 3 2 1) 1)

15

(poly-eval-horner ’(5 4 3 2 1) 2)

129

(poly-eval-horner ’() 1)

0

(count-occurrences ’( (+ 1 2) (a (+ 1 2) 3) ) 1)

2

(count-occurrences ’( (+ 1 2) (a (+ 1 2) 3) ) 3)

1

(count-occurrences ’( (+ 1 2) (a (+ 1 2) 3) ) ’(+ 1 2))

2

(count-occurrences ’( (+ 1 2) (a (+ 1 2) 3) ) ’(+ 1 3))

0

(arith-eval ’(mul 3 (add 4 (mul 4 3))))

48

(arith-eval 45) 45

(sum-lengths-tr ’( (1 2 3) (()) (() 2 (3 4 5))))

7

(sum-lengths-tr ’()) 0

(poly-eval-horner-tr ’(5 4 3 2 1) 1)

15

(poly-eval-horner-tr ’(5 4 3 2 1) 2)

129

(poly-eval-horner-tr ’() 2) 0

(mul-list-2 ’(4 5 9) 4)

’(16 20 36)

(mul-list-2 ’() 4) ’()

(sum-lengths-2 ’( (1 2 3) (()) (() 2 (3 4 5))))

7

(sum-lengths-2 ’( )) 0

(load "arith-parse.scm") (arith-parse ’( 1 + 2 +       4 * 3 ))

’(add (add 1 2) (mul 4 3))

(arith-parse ’( 1 + < 2 +                          4 * 3 ))

’(add 1 (add 2 (mul 4 3)))

(arith-parse ’( 1 + < 2 + + 4 * 3 ))

#f

(arith-parse ’( 1 + 2 +                        4 * 3 ))

#f

(arith-parse ’( 1 + < 2 +                          4 * 3 ))

’(add 1 (mul (add 2 4) 3))

(arith-parse ’( @ 1 + < 2 +                          4 * 3 ))

#f

(arith-eval (arith-parse ’( 1 + < 2 +                                  4 * 3 )))

19

 

$