Functional Programming

Appearance

Interpreter of SVGen ​

This homework assignment aims to implement an interpreter of a simple programming language which I call SVGen. This language allows writing programs generating SVG images. Thus the interpreter evaluates a given program and returns a string whose content is a valid SVG image. SVG is a XML-based vector image format. Our SVGen programs support only a fragment of the SVG specification to keep the assignment simple.

Important!

  1. The interpreter should be implemented in Racket, but you are not allowed to use Racket built-in function eval.

  2. All your code is required to be in a single file called hw2.rkt.

SVGen is a LISP-like language. Thus your interpreter does not have to parse the source file, but you will be given an abstract syntax tree (AST) directly represented as a nested list consisting of the language primitives. An example of a simple SVGen program is shown below:

scheme
'((define STYLE "fill:pink;opacity:0.5;stroke:black;stroke-width:2")
  (define END 15)
  (define (recur-circ x y r)
     (circle x y r STYLE)
       (when (> r END)
         (recur-circ (+ x r) y (floor (/ r 2)))
         (recur-circ (- x r) y (floor (/ r 2)))
         (recur-circ x (+ y r) (floor (/ r 2)))
         (recur-circ x (- y r) (floor (/ r 2))))))

This program recursively generates circles with smaller and smaller radii. Once the radius is smaller than the constant END, the program stops. Evaluating the expression '(recur-circ 200 200 100) returns a string containing an SVG image:

Interpreter specification ​

Your task is to implement a function

(execute width height prg expr)

where width and height is a width and height of the SVG image respectively. The argument prg is an SVGen program consisting of function and constant definitions, and expr is an expression to be evaluated (typically, it is a function call of a function defined in prg). For example, if and , the execute function returns a string

xml
<svg width="500" height="400">...content...</svg>

where the ...content... is the result of the interpreter by evaluating expr using the definitions in prg. To simplify the task, we split the function definitions part in prg from the expression expr whose evaluation gives the content of the SVG-tag. So you can process the function definitions prg in advance and create a global environment in which the expression expr is evaluated afterward. For example the result of the program prg in the recur-circ code snippet depicted in the circle figure was returned by the call

scheme
(execute 400 400 prg '(recur-circ 200 200 100))`

Important

The function execute has to be exported from your file hw2.rkt! Thus your file must contain (provide execute).

SVGen syntax and semantics ​

Now we define the syntax and semantics of SVGen programs.

Syntax ​

The syntax of SVGen is specified by a grammar below. A grammar consists of rules of the form LHS -> RHS where LHS is a non-terminal symbol and RHS is either a sequence of symbols or several sequences separated by the pipe |. The rule states that the non-terminal symbol LHS can be rewritten into one of the sequences of symbols separated by |. To define arbitrarily long sequences, we use the formal language operators * and +. For a symbol <symbol> the notation <symbol>* (resp. <symbol>+) stands for any finite (resp. finite nonempty) sequence of <symbol>s separated by spaces.

<program> -> (<definition>*)

<definition> -> (define (<id> <id>*) <expression>+)
              | (define <cid> <val>)

<expression> -> <application>
              | (if <bool-exp> <expression> <expression>)
              | (when <bool-exp> <expression>+)

<application> -> (<svg-op> <arg>*)
               | (<id> <arg>*)

<bool-exp> -> (<bool-op> <num-exp>*)

<arg> -> <string>
       | <num-exp>
       | <cid>

<num-exp> -> <num>
           | <id>
           | <cid>
           | (<num-op> <num-exp>*)

<string> -> any Racket string, e.g. "fill:blue"
<num> -> any Racket number, e.g. 3.14
<cid> -> any Racket symbol starting with an uppercase character, e.g. STYLE
<val> -> <string> | <num>
<id> -> any Racket symbol starting with a lowercase character, e.g. x1
<num-op> -> + | - | * | / | floor | cos | sin
<svg-op> -> circle | rect | line
<bool-op> -> = | < | >

We will comment on its parts. An SVGen program is a list of definitions as specified by the rule <program> -> (<definition>*). Each definition is either a function definition of the form (define (<id> <id>*) <expression>+) or a constant definition of the form (define <cid> <val>).

The constant definitions consist of an identifier <cid> and a value <val>. To distiguish constants from other <id>s, <cid> is a Racket symbol starting with an uppercase letter. The value <val> is either a string (e.g., "fill:red") or a numerical value (e.g., 3.14).

The syntax of the function definitions is the same as in Racket. The first identifier <id> is the name of the function and the sequence <id>* represents its arguments. The body of the function definition consists of nonempty seqeuence of expressions. Moreover, the only variables occuring in the body are among the function arguments. For instance, the body of (define (f x y) <body>) may contain only variables x,y. The body expressions might also refer to defined constants. Note that there can be no nested definitions.

Each expression is either a function application or if-expression or when-expression. The if-expression (if <bool-exp> <expression> <expression>) has the same syntax as if-expressions in Racket, i.e., the condition <bool-exp> is followed by a then-expression which is followed by an else-expression. The when-expression (when <bool-exp> <expression>+) contains a condition <bool-exp> followed by a nonempty sequence of expressions. The conditions <bool-exp> are of the form (<bool-op> <num-exp>*), where <bool-op> is one of =, <, > followed by numeric expressions.

The function application <application> represents a function call. Either it is a call of an SVG-primitive function (i.e., one of circle, rect, line) or a defined function. Each argument <arg> of a function call can be a string or a numeric expression or a constant. The numeric expressions <num-exp> have the same syntax as in Racket. They are built up from variables, numbers, constants, and functions +, -, *, /, floor, cos, sin.

Semantics ​

The evaluation of an expression with respect to an SVGen program returns a string representing a valid SVG image. The output string is generated by the function calls of SVG-primitives which generate corresponding SVG-tags. The semantics of the SVG-primitives is defined as follows:

  • The (circle x y r style) is evaluated to the SVG-tag <circle>, where are coordinates of its origin, is its radius, and is a string of style options. For example,
scheme
> (circle 50 40 20 "fill:blue") 
<circle cx="50" cy="40" r="20" style="fill:blue"/>
  • The (rect x y width height style) is evaluated to the SVG-tag <rect>, where are coordinates of its origin, , is its width and height respectively, and is a string of style options. For example,
scheme
> (rect 10 20 30 40 "fill:blue")
<rect x="10" y="20" width="30" height="40" style="fill:blue"/>
  • The (line x1 y1 x2 y2 style) is evaluated to the SVG-tag <line>, where are coordinates of its origin, coordinates of the final point, and is a string of style options. For example,
scheme
> (line 10 20 30 40 "stroke:black;stroke-width:5")
<line x1="10" y1="20" x2="30" y2="40" style="stroke:black;stroke-width:5"/>

The rest of the SVGen semantics is quite straightforward following the Racket semantics. The interpretation of the conditional expression (when <bool-exp> <expression>+) evaluates the nonempty sequence of expressions only if the condition <bool-exp> is evaluated to true. If the condition <bool-exp> is evaluated to false, the when-expression returns the empty string "".

Further hints ​

Try to make your solution structured by splitting your code into several independent pieces and design covering test cases for all the pieces. For example, I split my solution into the following parts:

  • Functions generating SVG-tags
  • Environment functions
  • Evaluator functions

Functions generating SVG-tags ​

This part is quite straightforward. You can devise a clever solution using higher-order functions. It is convenient to use the Racket function format to create a particular string. For example,

scheme
> (format "<svg width=\"~a\" height=\"~a\">" 200 100) 
"<svg width=\"200\" height=\"100\">"

Note the escape backslash character allowing to enter double quotes. The format function also converts numerical values into a string automatically.

Environment functions ​

To evaluate an application of a defined function, the interpreter has to know all the function and constant definitions from prg, and all the values to be bound to the function arguments. You need to design a data structure capturing these data. I call it an environment. It has three parts. The first two consist of the function and constant definitions. They can be processed in advance because the interpreter gets them separately. Thus the first two parts remain constant during the evaluation of a given expression.

The last part of the environment is more dynamic. Once you need to evaluate a function call (f e1 e2 ...), you have to first evaluate the expressions e1 e2 ... obtaining some values , then you can create a new environment whose last part is created based on the values , and finally, you can evaluate the body of f in this new environment.

Note that SVGen has no bindings scopes. The only variables are just parameters in the function definitions (apart from the defined constants). Consequently, the second part of the environment is fully determined by a function call. Thus there is no need to extend the envinroment by bindings from the outer scope (unlike a Racket interpreter).

Evaluator functions ​

These functions form the core of the interpreter. They should follow the grammar of the language. Roughly speaking, for each rule of the grammar, there is a corresponding function recognizing which of the right-hand side applies. Once it is clear, the expression is decomposed into particular parts; to implement such a function, it is convenient to employ pattern matching. Each part is either a terminal symbol (like a number, a string, a primitive function) or corresponds to a rule in the grammar. If it is a terminal symbol, its evaluation is given by its semantics (e.g., the symbol '+ stands for the Racket function +). If it corresponds to a rule, it can be evaluated recursively by the corresponding evaluator function.

Test cases ​

This section presents a few test cases to show how the interpreter should behave. Similarly, as in the first homework assignment, your execute function returns a string. If you test it directly in DrRacket REPL, the REPL displays the string value full of the escape character \. To see the result without escape characters, one has to apply function display to the result. Such displayed string can then be copied into your clipboard and pasted into any SVG viewer (I use the online editors in \url{https://www.w3schools.com/graphics/svg_intro.asp}). In the following examples, we will display the resulting SVG format on several lines indented for better readability. However, to simplify your task, your output string does not need to contain any newline characters or whitespace between SVG tags.

Line

scheme
> (display (execute 400 400 '()
             '(line 10 20 30 40 "stroke:black;stroke-width:5")))
<svg width="400" height="400">
  <line x1="10" y1="20" x2="30" y2="40" style="stroke:black;stroke-width:5"/>
</svg>

Circle

scheme
> (display (execute 400 400 
             '((define STYLE "fill:red"))
             '(circle 200 200 (floor (/ 200 3)) STYLE)))
<svg width="400" height="400">
  <circle cx="200" cy="200" r="66" style="fill:red"/>
</svg>

Rectangles

scheme
> (define test1
    '((define (start)
        (rect 0 0 100 100 "fill:red")
        (rect 100 0 100 100 "fill:green")
        (rect 200 0 100 100 "fill:blue"))))

> (display (execute 400 400 test1 '(start)))

<svg width="400" height="400">
  <rect x="0" y="0" width="100" height="100" style="fill:red"/>
  <rect x="100" y="0" width="100" height="100" style="fill:green"/>
  <rect x="200" y="0" width="100" height="100" style="fill:blue"/>
</svg>

Circles

scheme
(define test2
  '((define STYLE "fill:red;opacity:0.2;stroke:red;stroke-width:3")
    (define START 195)
    (define END 10)
    (define (circles x r)
      (when (> r END)
        (circle x 200 r STYLE)
        (circles (+ x (floor (/ r 2))) (floor (/ r 2)))))))

> (display (execute 400 400 test2 '(circles 200 START)))  
<svg width="400" height="400">
  <circle cx="200" cy="200" r="195" style="fill:red;opacity:0.2;stroke:red;stroke-width:3"/>
  <circle cx="297" cy="200" r="97" style="fill:red;opacity:0.2;stroke:red;stroke-width:3"/>
  <circle cx="345" cy="200" r="48" style="fill:red;opacity:0.2;stroke:red;stroke-width:3"/>
  <circle cx="369" cy="200" r="24" style="fill:red;opacity:0.2;stroke:red;stroke-width:3"/>
  <circle cx="381" cy="200" r="12" style="fill:red;opacity:0.2;stroke:red;stroke-width:3"/>
</svg>

Recursive Tree

scheme
  (define tree-prg
    '((define STYLE1 "stroke:black;stroke-width:2;opacity:0.9")
      (define STYLE2 "stroke:green;stroke-width:3;opacity:0.9")
      (define FACTOR 0.7)
      (define PI 3.14)
      (define (draw x1 y1 x2 y2 len angle)
        (if (> len 30)
            (line x1 y1 x2 y2 STYLE1)
            (line x1 y1 x2 y2 STYLE2))
        (when (> len 20)
          (recur-tree x2 y2 (floor (* len FACTOR)) angle)
          (recur-tree x2 y2 (floor (* len FACTOR)) (+ angle 0.3))
          (recur-tree x2 y2 (floor (* len FACTOR)) (- angle 0.6))))
      (define (recur-tree x1 y1 len angle)
        (draw x1
              y1
              (+ x1 (* len (cos angle)))
              (+ y1 (* len (sin angle)))
              len
              angle))))

Evaluating this program by

scheme
(display (execute 400 300 tree-prg '(recur-tree 200 300 100 (* PI 1.5))))

generates the tree above.