• Main
• Overview
• Resources
• Homeworks

Sample Midterm 4

Date: Friday, March 15th

Question 1: Racket Programming, Part 1

 14 pts 

Two common ways to combine elements in a list into a single value are foldl and foldr. For example:

-> (foldl list 0 '(1 2 3 4))
'(4 (3 (2 (1 0))))
-> (foldr list 0 '(1 2 3 4))
'(1 (2 (3 (4 0))))

Do this in two steps. In the first step, define a map-pairs function that does the pair scan and produces a list of results. Here are a few tests to demonstrate how it works:

(test (map-pairs list '(1 2 3 4 5 6)) => '((1 2) (3 4) (5 6)))
(test (map-pairs list '(1 2 3 4 5))   => '((1 2) (3 4) 5))
(test (map-pairs list '(1 2))         => '((1 2)))
(test (map-pairs list '(1))           => '(1))
(test (map-pairs list '())            =error> "empty list")
(test (map-pairs +    '(1 2 3 4 5 6)) => '(3 7 11))
(test (map-pairs +    '(1 2 3 4 5))   => '(3 7 5))
(test (map-pairs +    '(1 2))         => '(3))
(test (map-pairs +    '(1))           => '(1))

Remember to write a good type declaration and a purpose statement.

(Negative hint: you cannot implement this function using map!)

Question 2: Racket Programming, Part 2

 12 pts 

For the second test you need to define the fold-pairs folding function.

Define a fold-pairs which applies the above repeatedly until a single element is left, and returns that value.

Examples:

(test (fold-pairs +    '(1 2 3 4 5 6)) => 21)
(test (fold-pairs list '(1 2))         => '(1 2))
(test (fold-pairs list '(1 2 3 4))     => '((1 2) (3 4)))
(test (fold-pairs list '(1 2 3 4 5 6)) => '(((1 2) (3 4)) (5 6)))
(test (fold-pairs list '(1 2 3 4 5))   => '(((1 2) (3 4)) 5))
(test (fold-pairs list '(1))           => 1)
(test (fold-pairs list '())            =error> "empty list")

Note that a proper type for this will be tricky, so you can skip it, and instead describe things more accurately in the purpose statement.

Question 3: BNF Grammar

 15 pts 

In class, we have seen a BNF for an infix syntax of the four basic arithmetical expressions, which properly makes multiplication and division have higher precedence, each level of operators is left-associative and we also had parenthesis grouping:

<AE>   ::= <AE> + <FAC>
         | <AE> - <FAC>
         | <FAC>

<FAC>  ::= <FAC> * <ATOM>
         | <FAC> / <ATOM>
         | <ATOM>

<ATOM> ::= <num>
         | ( <AE> )

Extend this syntax in two ways:

• Add an exponent "^" operator that is higher precedence than the other four (but not higher than parenthesis).
• Add a unary prefix "-" or "+" that is even higher than "^" (but still not higher than parenthesis, of course).

The resulting language would accept expressions like

-( 1 + -2 * 3 ^ +4 )
-+--+-4                <--- many unary prefix operators

Question 4: Fill in the blanks

 20 pts 

(* (blank) 2)

(define blank (lambda () 330))

1. (* blank (+(*)(*)))
2. (/ blank 12345)
   Hint: you do not need a calculator for this
3. ((lambda () (blank)))
4. (Y blank)
   This is assuming our definition of Y for Racket that we’ve seen in class:

   (define (Y f) ((lambda (x) (x x)) (lambda (x) (f (lambda (y) ((x x) y))))))

   Hint: this is way easier than it looks!
5. (let* ([blink blank] [blank blink]) blank)
   Reminder: let* works as a shorthand for a bunch of nested single-identifier binding let forms

Question 5: Structural Recursion with ASTs

 18 pts 

Implement a shadowed-identifiers function that consumes an AST syntax for FLANG (an input of type FLANG), and returns a list of all identifiers (a list of symbols) that are "shadowed" anywhere in the code. An identifier is shadowed if in its scope there is some arbitrarily nested scope with the same name. A few examples:

(: shadowed* : String -> (Listof Symbol))
;; a utility for the tests below
(define (shadowed* str)
  (shadowed-identifiers (parse str)))

(test (shadowed* "{with {x 1} {with {x 1} 1}}")
      => '(x))
(test (shadowed* "{with {x 1} {fun {x} x}}")
      => '(x))
(test (shadowed* "{with {x 1} {with {x 1} {fun {x} x}}}")
      => '(x))
(test (shadowed* "{with {x 1} {with {y 1} {fun {x} x}}}")
      => '(x))
(test (shadowed* "{with {x 1} {with {y 1} {fun {y} x}}}")
      => '(y))
(test (shadowed* "1") => '())
(test (shadowed* "{+ 1 2}") => '())
(test (shadowed* "{+ x y}") => '())

For reference, here is the definition of FLANG:

(define-type FLANG
  [Num  Number]
  [Add  FLANG FLANG]
  [Sub  FLANG FLANG]
  [Mul  FLANG FLANG]
  [Div  FLANG FLANG]
  [Id   Symbol]
  [With Symbol FLANG FLANG]
  [Fun  Symbol FLANG]
  [Call FLANG FLANG])

Note: you don’t need to worry about the order of symbols and repeating ones. This would be addressed using a predicate that compares two lists as sets, which you don’t need for this question.

Question 6: Extending the FLANG Language

 18 pts 

We want to extend the FLANG langugae with a new feature called upref. This will be a new special form that has an identifier, and it will evaluate to the value of the second binding of that identifer in the runtime environment. Again, we use a few tests to demonstrate this extension:

(test (run "{upref x}") =error> "...")
(test (run "{with {x 1} {upref x}}") =error> "...")
(test (run "{with {x 1} {with {x 2} {upref x}}}") => 1)
(test (run "{with {x 1}
              {with {f {fun {x} {upref x}}}
                {call f 2}}}") => 1)
(test (run "{with {x 1}
              {with {f {fun {x} {upref x}}}
                {with {x 3}
                  {call f 2}}}}") => 1)

To implement this on top of the FLANG langugae that uses environments, we need to:

• Extend the BNF:

  <FLANG> ::= ...same... | { upref <id> }

• The AST type definition:

  (define-type FLANG ;; ...same... [Upref Symbol])

• And the parser:

  (: parse-sexpr : Sexpr -> FLANG) ;; to convert s-expressions into FLANGs (define (parse-sexpr sexpr) (match sexpr ;; ...same... [(list 'upref (symbol: name)) (Upref name)] [else (error 'parse-sexpr "bad syntax in ~s" sexpr)]))

The main step is extending eval to handle these expressions:

(: eval : FLANG ENV -> VAL)
;; evaluates FLANG expressions by reducing them to values
(define (eval expr env)
  (cases expr
    ...same...
    [(Upref name) ???]))

Question 7: Schlac

 16 pts 

The standard way to encode booleans that we have seen in class is as two selector functions:

(define #t (lambda (x y) x))

(define #f (lambda (x y) y))

As usual, that’s not the only way you could encode them. We could, for example, try to do a more C-style encoding and use 0 for false, and any number bigger than 0 for true:

(define #f 0) ; note: it's actually the same as what we had!

(define #t 1) ; or 2, or 3, etc

This change will obviously require changing other aspects of booleans, and the most basic function that we need to deal with is if. Write its new definition:

(define if
  (lambda (cond then else)
    ...fill-in...))

Question 8: Language Features

 18 pts 

Unless told otherwise, choose the best answer in each of the following questions. (Note that there could be several answers that are correct, but one should be the most accurate.)

1. In the FLANG extension that we have implemented above we added a new kind of an "upref" identifier reference. An important issue is whether our language is still one that can be compiled or not. Can it?
   1. No, the fact that we can do this kind of upref dynamically at runtime means that we get a dynamically scoped language, and as we have discussed in class, such langugaes cannot be compiled. (Since the "offset" of a variable reference cannot be determined before running the code.)
   2. Almost, but no. Since all of the references are visible in the source code, we can still tell which binding is referenced at each upvar expression — but this works only if our language is not extended to have a conditional expression like if. Such an expression means that we can have code that goes an arbitrary number of levels at runtime, so we cannot tell statically which binding it refers to.
   3. Yes. Since the syntax still allows us to see the lexical structure of the code, we can still analyze it and compile it using de-Bruijn indexes. Even if we have a conditional if form added to the language we can see the lexical structure of the code since an upref expression returns a value, which means that we cannot do two (or more) uprefs somehow.
   4. Yes. Since the syntax still allows us to see the lexical structure of the code, we can still analyze it and compile it using de-Bruijn indexes. If we have a conditional ‘if’ form added to the language we will need to use a lazy evaluation strategy anyway, and that means that we don’t get expressions with a dynamically determined scope.
2. In the last midterm exam we’ve had this "blank" question:

   (* 330 (length (cons blank blank)))

   and a solution that was given to it was:

   (define blank (list 1))

   In the review session, I mentioned the fact that typing this might be tricky. To see this, you need to be aware of the type of cons:

   (: cons : (All (A) (A (Listof A) -> (Listof A))))

   Which of the following types can be used for this blank definition to work?
   1. Any
   2. (Listof Any)
   3. (Listof Number)
   4. (All (A) (Listof A))
   5. (List Number)
   6. Number
   There are exactly three of these that can work, and three that will not. You need to list all three.
3. Joe implemented a Flang evaluator similar to ours in an imperative language, whose name begins with "J". (This question is based on a true story from a past semester. The names have been changed to protect the innocent.)
   As common for such programmers, he made the mistake of making environment extension modify via mutation of the environment. Write a simple Flang program that demonstrates that his implementation is wrong.
   Note: you need to find such an example yourself, no multiple choices here. (But it is easy to do this.)
4. We’ve seen in class that if we write (list (foo)) in Racket, then the foo call is not a tail call. Intuitively, this is because there is still work to be done with the return value (wrap it in a list). What if we do something like this:

   ((lambda (x) x) (foo))

   — would the foo call be a tail call now?
   1. Yes, it would be a tail call. This is because dynamic scope means that there are no closures, so the lambda expression basically evaluates to just the code with no environment to hold on to the value of x. This means that when it is applied, we get just the value of the foo call, and there is no need to do something with that when we get an answer.
   2. No, it still would not be a tail call. This is because Racket is a strict language, and therefore no matter which function is called, we still need to evaluate the argument and only then apply the anonymous function onto the resulting value.
   3. Yes, it would be a tail-call now. Racket’s compiler performs optimizations like reducing an immediate ((lambda (x) ...) ...) to avoid runtime work on generating a closure that is immediately applied, and therefore the code that the whole expression compiles to is essentially just (foo), and that obviously has the semantics of a tail call (since there is no context).
   4. No, it still would not not be a tail call. This is because we have a language with first-class functions, and the only way to optimize away such calls of unknown functions is by a complete lexical analysis of calls, one that can be performed only on a more restricted language, one with just first-order functions.