[SOLVED] Programming Homework #2- BNFs, Parsing, and Higher-Order Functions-Q2

In this homework (and in all future homeworks) you should be working in the

“Module” language, and use the appropriate language using a #lang line. You should also click the “Show Details” button in the language selection dialog, and check the “Syntactic test suite coverage” option to see parts of your code that are not covered by tests: after you click “run”, parts of the code that were covered will be colored in green, parts that were not covered will be colored in red, and if you have complete coverage, then the colors will stay the same. Note that you can also set the default language that is inserted into new programs to #lang pl, to make things more convenient. There are some variants for the pl language for various purposes — in particular, #lang pl untyped will ignore all type declarations, and will essentially run your code in an untyped Racket.

The language for this homework is:

#lang pl 02

As in previous assignment, you need to use the special form for tests: test.

 

Reminders (this is more or less the same as the administrative instructions for the previous assignment):

Comments: Submitted code for each question should include at least two lines of comments with your personal description of the solution, the function and its type. In addition, you should comment on the process of solving this question – what were the main difficulties, how you solved them, how much time did you invest in solving it, did you need to consult others. A solution without proper comments may be graded 0. In general, comments should appear above the definition of each procedure (to keep the code readable).

Tests: For each question, you should have enough test cases for complete coverage (DrRacket indicates covered expressions with colors for covered and uncovered source code, unless your code is completely covered). See below on the way to create tests. Note that your tests should not only cover the code, but also all end-cases and possible pitfalls.

 

Important: Your tests should cover your whole code; otherwise the server will heavily penalize your submission. You should not have any uncovered expressions after you hit “Run” — it should stay at the same color, indicating complete coverage. Furthermore, the server will run its own tests over your code, which means that you will not be able to submit code that does not work.

General note: Code quality will be graded. Write clean and tidy code. Consult the Style Guide, and if something is unclear, ask questions on the course forum.

The test form can be used to test that an expression is true, that an expression evaluates to some given value, or that an expressions raises an error with some expected text message. For example, the three kinds of tests are used in this example:

#lang pl

(: smallest : (Listof Number) -> Number)

(define (smallest l)

(match l

[(list)      (error ‘smallest “got an empty list”)]

[(list n)    n]

[(cons n ns) (min n (smallest ns))]))

(test (smallest ‘(5 7 6 4 8 9)) => 4)

(test (zero? (smallest ‘(0 1 2 3 4))))

(test (smallest ‘()) =error> “got an empty list”)

In case of an expected error, the string specifies a pattern to match against the error message. (Most text stands for itself, “?” matches a single character and “*” matches any sequence of characters.)

Note that the =error> facility checks only errors that your code throws, not Racket errors. For example, the following test will not succeed:

(test (/ 4 0) =error> “division by zero”)

The code for all the following questions should appear in a single .rkt file named

<your ID>_2 (e.g., 333333333_2 for a student whose ID number is 333333333).

 

1.   BNF (SE)

1. In class we have seen the grammar for AE – a simple language for “Arithmetic Expressions”. Write a BNF for “SE”: a similarly simple language of “String Expressions”. Valid ‘programs’ (i.e., words in the SE language) should go along the lines of pl expressions for Strings, with two exceptions: 1. Only digits 0,…,9 are allowed as valid characters within strings; 2. We will have two types of expressions that are not available in the pl language (see below ‘stringinsert’ and ‘number->string’ type expressions). The valid operators that can be used in these expressions are string, string-length, and string-append, and also string-insert and number->string. It is also legal to have expressions of the form “<D>”, where <D> stands for a (finite) sequence of digits. Plain values in the language are characters (of digits) and natural numbers, thus the following are also valid expressions: a sequence of digits (such as, 347226) and an expression of the form #\v, where v is a digit.

Here, we do not care about implementing anything – neither the parser nor the evaluator. Thus, your code should be commented out. Still, it may be helpful to consider some future semantics that will help you understand the requirements. The operations ” “, string, string-append,

string-insert, and number->string are considered expressions

that represent a string (they would return a string). The operation string-length, and digit sequences are considered expressions that represent a natural number (they would return a natural number).

Expression of the form #\v represent a character.

Note the following requirements for the grammar:

string  is allowed with a sequence of any number of characters. string-append is allowed with a sequence of any number of expressions that represent strings. string-insert is allowed with an expression that represents a string, a character, and a natural number.   

number->string is allowed with a natural number.

For example, some valid expressions in this language are:

“12344”

12

( string #\1 #\2 #\4 )

( string-append ( string #\1 #\2 #\4 ) “12” )

( string-insert “1357” #\4 66 )

( number->string 156879 )

( number->string ( string-length “0033344” ) )

( string-append “45” ( number->string ( string-length

“0033344” ) ))

( string-append )

( string-append “” ( string-insert “1357” #\4 66 ) “” )

#\3

but the following are invalid expressions:

“a2b” 12 13 4 67 ( string 124 ) ( string-append ( string-length “44” ) “12” ) ( string-insert “1357” 4 66 ) ( number->string “156879” ) ( string-append 33 44 66) #\3 #\4 #\32 #\q

 

NOTE: The use of ellipsis (‘…’) or ‘*’ is not allowed here (find ways within the BNF framework to specify zero-or-more occurrences of a previous piece of syntax). Use 𝜆 to specify the empty string.  

Important remark:  Your solution should only be a BNF and not a code in Racket (or in any other language). You cannot test your code!!! Indeed, your answer should appear inside a comment block (write the grammar in a #|—|# comment).  

1. Add to your BNF a derivation process for 3 different SE expressions, such that every operator (e.g., string-append, string-length, and

number->string) appears in at least one of these expressions. You may either provide a derivation tree or a series of replacements starting with <SE> and

(𝑖)

ending with your string. Mark each derivation rule by an index (use “       ” to state

=> that in a certain step, you have used rule number 𝑖 of your BNF).

 

2.   Higher Order Functions

As you already know, lists are a fundamental part of Racket. They are often used as a generic container for compound data of any kind. It is therefore not surprising that Racket comes with plenty of useful functions that operate on lists. One of the most useful list functions is foldl: it consumes a combiner function, an initial value, and an input list. It returns a value that is created in the following way:

• For the empty list, the initial value is returned,
• For a list with one item, it uses the combiner function with this item and the initial value,
• For two items, it uses the combiner function with the first and the result of folding the rest (a one-item list),

In the general case, the value of foldl is:

(foldl f init (list x1 x2 x3 … xn))

= (f xn (… (f x3 (f x2 (f x1 init)))))

Note that foldl is a higher-order function, like map. Its type is:

(: foldl : (All (A B) (A B -> B) B (Listof A) -> B))

Use foldl together with (or without) map to define a sum-of-squares function which takes a list of numbers as input, and produces a number which is the sum of the squares of all of the numbers in the list. A correct solution should be a oneliner. Remember to write a proper description and contract line, and to provide sufficient tests (using the test form). You will need to do this for a definition of square too, which you would need to write for your implementation of sum-ofsquares.

A more detailed explanation on both functions can be found at the bottom of the assignment or here.

 

Here is an example of a test that you might want to perform:

 

 

(test (sum-of-squares ‘(1 2 3)) => 14)

 

 

 

3.   PAE (and more H.O. functions)

1. In this question, you are asked to write a function _{createPolynomial} that takes as arguments a list of 𝑘 numbers 𝑎₀, … , 𝑎_𝑘−1 and returns as output a function. The returned function takes a number 𝑥₀ and return the value of the polynomial 𝑎₀ ⋅ 𝑥⁰ + ⋯ + 𝑎_𝑘−1 ⋅ 𝑥^𝑛−1 at 𝑥₀. To this end, you can use the built-in pl _expt function taking two numbers 𝑎 and 𝑏, and returning 𝑎^𝑏.

The following should help you understand the task at hand:

> (createPolynomial ‘(1 2 4 2))

– : (Number -> Number)

#<procedure:polyX>

 

(define p2345 (createPolynomial ‘(2 3 4 5)))

(test (p2345 0) =>

(+ (* 2 (expt 0 0)) (* 3 (expt 0 1)) (* 4 (expt 0 2)) (* 5

(expt 0 3))))

(test (p2345 4) =>

(+ (* 2 (expt 4 0)) (* 3 (expt 4 1)) (* 4 (expt 4 2)) (* 5 (expt 4 3))))

(test (p2345 11) => (+ (* 2 (expt 11 0)) (* 3 (expt 11 1)) (* 4 (expt 11 2)) (* 5 (expt 11 3))))

 

 

(define p536 (createPolynomial ‘(5 3 6)))

(test (p536 11) => (+ (* 5 (expt 11 0)) (* 3 (expt 11 1)) (* 6

(expt 11 2))))

 

(define p_0 (createPolynomial ‘()))

(test (p_0 4) => 0)

Remark: all recursive calls should be in tail recursion.

You are given the following partial code. Use it as a basis for your full code. Don’t forget to add comments and tests.

(: createPolynomial : (Listof Number) -> <-fill in->)

(define (createPolynomial coeffs)

  (: poly : (Listof Number) Number Integer Number ->

Number)

  (define (poly argsL x power accum)

     (if <-fill in->

        <-fill in->

        <-fill in-> ) 

  (: polyX : Number -> Number)

  (define (polyX x)

     ßfill in→)   ßfill in→)

 

 

 

1. We now move on to define a language PLANG that supports evaluating a polynomial on a sequence of points (numbers). You should base your solution on the interpreter we have written for the AE language. Specifically, your code should keep most of the definitions therein. The changes you do need to make are described next.

 

1. Write the BNF for the new language to allow for expressions of the

form {{ 𝒑𝒐𝒍𝒚 𝑪_𝟏 𝑪_𝟐 … 𝑪_𝒌} {𝑷_𝟏 𝑷_𝟐 … 𝑷_𝓵}} where all 𝐶_𝑖 and all 𝑃_𝑗 are valid AE expressions (and both 𝑘 ≥ 1 and ℓ ≥ 1).

See examples for valid expressions:

 

“{{poly 1 2 3} {1 2 3}}”

“{{poly 4/5 } {1/2 2/3 3}}”

“{{poly 2 3} {4}}”

“{{poly 1 1 0} {-1 3 3}}”

     “{{poly {/ 4 2}  {- 4 1}} {{- 8 4}}}”

     “{{poly {+ 0 1} 1 {* 0 9}} {{- 4 5} 3 {/ 27 9}}}”

 

Also see examples for invalid expressions:

 

“{{poly } {1 2 3} }”

“{{poly 4/5 } {1/2 2/3 3} {poly 1 2 4} {1 2}}”

“{{poly 2 3} {}}”

“{{poly 1 1 3} }”

 

 

 

 

You may use the following skeleton for your BNF:

#|

  The grammar:

    <PLANG> ::= 

    <AEs>   ::= 

    <AE>    ::= 

  |#

 

1. Write the parser for the new language. Use the following partial code as well the test examples provided below.

 

(define-type PLANG

    [Poly (Listof AE) <-fill in->])

 

  (define-type AE

    [Num  Number]

    [Add  AE AE]

    [Sub  AE AE]

    [Mul  AE AE]

    [Div  AE AE])

 

  (: parse-sexpr : Sexpr -> AE)

  ;; to convert s-expressions into AEs

  (define (parse-sexpr sexpr)

    (match sexpr

      [(number: n)    (Num n)]

      [(list ‘+ lhs rhs) (Add (parse-sexpr lhs) 

                             (parse-sexpr rhs))]

      [(list ‘- lhs rhs) (Sub (parse-sexpr lhs)                       (parse-sexpr rhs))]

      [(list ‘* lhs rhs) (Mul (parse-sexpr lhs) 

                             (parse-sexpr rhs))]

      [(list ‘/ lhs rhs) (Div (parse-sexpr lhs) 

                             (parse-sexpr rhs))]

 [else (error ‘parse-sexpr “bad syntax in ~s”            sexpr)]))

  

  (: parse : String -> PLANG)

  ;; parses a string containing a PLANG expression         to a PLANG AST   (define (parse str)

    (let ([code (string->sexpr str)])

      <-fill in->))

 

(test (parse “{{poly 1 2 3} {1 2 3}}”) 

     => (Poly (list (Num 1) (Num 2) (Num 3)) 

              (list (Num 1) (Num 2) (Num 3))))

(test (parse “{{poly } {1 2} }”) 

     =error> “parse: at least one coefficient is                        required in ((poly) (1 2))”)

(test (parse “{{poly 1 2} {} }”)       =error> “parse: at least one point is 

                       required in ((poly 1 2) ())”)

 

 

iii.      Write the evaluation process. In order to leave the AE eval unchanged (for the sake of keeping your work as simple as possible), we wrap it with an eval-poly function (which will be the core of the evaluator). We start with presenting the formal specification of the semantics:

 

eval-poly({{ 𝒑𝒐𝒍𝒚 𝑪_𝟏 𝑪_𝟐 … 𝑪_𝒌} {𝑷_𝟏 𝑷_𝟐 … 𝑷_𝓵}}) =

′(𝑝(𝑒𝑣𝑎𝑙(𝑃₁), … , 𝑒𝑣𝑎𝑙(𝑃_ℓ))) where 𝑝 is the polynomial defined by coefficients

(𝑒𝑣𝑎𝑙(𝐶₁), … , 𝑒𝑣𝑎𝑙(𝐶_𝑘). That is, the expressions 𝑪_𝟏 𝑪_𝟐 … 𝑪_𝒌   are evaluated to coefficients and the  expressions 𝑷_𝟏 𝑷_𝟐 … 𝑷_𝒌 are evaluated to numbers on which we evaluate the polynomial.

Here are some possible tests:

 

(test (run “{{poly 1 2 3} {1 2 3}}”) 

=> ‘(6 17 34))

(test (run “{{poly 4 2 7} {1 4 9}}”)  => ‘(13 124 589))

(test (run “{{poly 1 2 3} {1 2 3}}”)   => ‘(6 17 34))

(test (run “{{poly 4/5 } {1/2 2/3 3}}”) 

=> ‘(4/5 4/5 4/5))

(test (run “{{poly 2 3} {4}}”)  => ‘(14))

(test (run “{{poly 1 1 0} {-1 3 3}}”)  => ‘(0 4 4))) 

(test (run “{{poly {/ 4 2} {- 4 1}} {{- 8 4}}}”)

=> ‘(14))

(test (run “{{poly {+ 0 1} 1 {* 0 9}} {{- 4 5} 3

{/ 27 9}}}”)

=> ‘(0 4 4))

 

Use the following partial code as a basis for your code.

;; evaluates AE expressions to numbers

  (define (eval expr)

    (cases expr

      [(Num n)  n]

      [(Add l r) (+ (eval l) (eval r))]

      [(Sub l r) (- (eval l) (eval r))]

      [(Mul l r) (* (eval l) (eval r))]

      [(Div l r) (/ (eval l) (eval r))])) 

  (: eval-poly : PLANG ->   <-fill in-> )

  (define (eval-poly p-expr)

    <-fill in-> )

 

  (: run : String -> (Listof Number))

  ;; evaluate a FLANG program contained in a string

  (define (run str)

    (eval-poly (parse str)))

 

HINT: You may want to use the procedure map (twice).  See more about map below.

 

On the procedures map and fold-l

הפונקציה map:

קלט: פרוצדורה proc ורשימה lst פלט: רשימה שמכילה אותו מספר איברים כמו ב- lst – שנוצרה ע”י הפעלת הפרוצדורה proc על כל אחד מאיברי הרשימה lst. )ההסבר הבא הוא כללי יותר – כי למעשה הפונקציה map יכולה

לטפל במספר רשימות – לצורך השאלה הנתונה לא תזדקקו לשימוש כזה(  map proc lst …+) → list?) proc : procedure?   lst : list?

Applies proc to the elements of the lsts from the first elements to the last. The proc argument must accept the same number of arguments as the number of supplied lsts, and all lsts must have the same number of elements. The result is a list containing each result of proc in order.  :דוגמאות > (map add1 (list 1 2 3 4))

‘(2 3 4 5)

> (map (lambda (x) (list x))

‘(sym1 sym2 33)) ‘((sym1) (sym2) (33))  :foldl הפונקציה

קלט: פרוצדורה proc, ערך התחלתי init ורשימה lst פלט: ערך סופי )מאותו טיפוס שמחזירה הפרוצדורה proc( שנוצר ע”י הפעלת הפרוצדורה proc על כל אחד מאיברי הרשימה lst תוך שימוש במשתנה ששומר את הערך שחושב עד כה – משתנה זה מקבל כערך התחלתי את הערך של init. )ההסבר הבא הוא כללי יותר – כי למעשה הפונקציה foldl יכולה לטפל במספר רשימות – לצורך השאלה הנתונה לא תזדקקו לשימוש כזה(

 

(foldl

proc init lst …+) → any/c   proc : procedure?

init : any/c   lst : list?

Like map, foldl applies a procedure to the elements of one or more lists. Whereas map combines the return values into a list, foldl combines the return values in an arbitrary way that is determined by proc.  :דוגמאות > (foldl + 0 ‘(1 2 3 4))

10

> (foldl cons ‘() ‘(1 2 3 4))

‘(4 3 2 1)