On this page:
Preliminaries
1 Pretty Printing
1.1 Additional Preliminaries
1.2 Problem Description

Problem Set 07

Last updated: Tue, 3 Mar 2015 10:47:20 -0500

OUT: Monday 2/23/2015, 9pm EST
DUE: Monday 3/2/2015, 9pm EST

Preliminaries
1 Pretty Printing
1.1 Additional Preliminaries

Save your solutions for this problem to a file named pretty.rkt.
Run the following expression (you must have required extras.rkt) to check that your file is properly named and is in the proper directory:

(check-location "07" "pretty.rkt")

Add these additional provides at the top of your file (below the requires), so that we can test your solution:
(provide expr->strings)

1.2 Problem Description

Here is a data definition for numeric expressions.
; An Expr is one of:
; - Integer
;  - (make-add (cons Expr NEListOf<Expr>) Boolean)
;  - (make-mul (cons Expr NEListOf<Expr>) Boolean)
; Represents a numeric expression that is either an integer, or an addition
; or multiplication of two or more expressions.
; The Boolean flag indicates whether the expression uses infix or prefix notation.
(define-struct add (exprs infix?))
(define-struct mul (exprs infix?))
Complete the data definition with appropriate data examples and templates.
Note that there are two pre-defined alternative data definitions of NEListOf<X>, each with a different template. You may use either representation (or both).
Then implement the expr->strings function.
; expr->strings : Expr Natural -> ListOf<String>
; Returns a rendering of exp as a sequence of lines,
; where each line is a string not longer than width characters.
; EFFECT: errors if expr cannot fit width
(define (expr->strings expr width) ...)
Here are the rendering rules:
  • Numbers are rendered with number->string.

  • Compound expressions are rendered with surrounding parentheses.

  • There are no spaces immediately inside open and closing parentheses.

  • An expression is rendered as a single line if it fits within the specified width.

  • Infix expressions are rendered with an operator between each expression and a space between an operator and each subexpression.
    (check-equal? (expr->strings (make-add (list 1 2 3) true) 11)
                  (list "(1 + 2 + 3)")
                  "infix, single line")

  • Prefix expressions are rendered with only one operator at the beginning and a space separating each subexpression, like in Racket.
    (check-equal? (expr->strings (make-add (list 1 2 3) false) 100)
                  (list "(+ 1 2 3)")
                  "prefix, single line")

  • If an expression cannot be rendered on one line, it should be stacked across multiple lines.
    • There are no spaces before a new line.

    • Parentheses should never go on their own line.

    • Infix expressions are stacked with each operator on its own line and subexpressions and operators of that expression at the same left alignment. This may require indenting subexpressions with spaces, depending on how many surrounding parentheses there are.
      (check-equal? (expr->strings (make-add (list 10 20 30) true) 7)
                    (list "(10"
                          " +"
                          " 20"
                          " +"
                          " 30)")
                    "infix stacking")

    • Prefix expressions are stacked such that the first line has the operator and the first subexpression. All other subexpressions should be on their own line, indented with spaces to align with the first subexpression.
      (check-equal? (expr->strings (make-add (list 10 20 30) false) 7)
                    (list "(+ 10"
                          "   20"
                          "   30)")
                    "prefix stacking")

    • An expression may have mixed infix and prefix notation expressions.
      (define EXAMPLE
        (make-add (list (make-mul (list 1 2) true)
                        (make-add (list 3 4) false))
                  true))
      (begin-for-test
        (check-equal? (expr->strings EXAMPLE 100)
                      (list "((1 * 2) + (+ 3 4))")
                      "unstacked")
        (check-equal? (expr->strings EXAMPLE 9)
                      (list "((1 * 2)"
                            " +"
                            " (+ 3 4))")
                      "one level stacking")
        (check-equal? (expr->strings EXAMPLE 8)
                      (list "((1 * 2)"
                            " +"
                            " (+ 3"
                            "    4))")
                      "two level stacking (1 subexpression)")
        (check-equal? (expr->strings EXAMPLE 7)
                      (list "((1"
                            "  *"
                            "  2)"
                            " +"
                            " (+ 3"
                            "    4))")
                      "two level stacking (2 subexpressions)"))

  • If an expression cannot be rendered, even with stacking, then the function should report an appropriate error message. Use the error function to report an error. To test erroring function calls, use check-error.

    (check-error (expr->strings EXAMPLE 4) "doesn't fit")

There is a display-strings! function in extras.rkt to help you debug.
; display-strings! : ListOf<String> -> Void
; EFFECT: Prints the given list of strings, one per line.

Examples:

> (require "extras.rkt")

extras.rkt Mon Jan 12 13:33:22 2015

> (display-strings! (list "(+ 22"
                          "   333"
                          "   44)"))

(+ 22

   333

   44)

> (display-strings! (list "(+ (* 22"
                          "      333"
                          "      44)"
                          "   (66"
                          "    +"
                          "    67"
                          "    +"
                          "    68)"
                          "   (* 77 88))"))

(+ (* 22

      333

      44)

   (66

    +

    67

    +

    68)

   (* 77 88))