Implement a sorted? higher order predicate. It should be defined as a
function that takes in two inputs:
(sorted? l <=?)
a list l to be checked, and a binary <=? predicate that returns
true if its first argument is smaller than or equal to its second. Note
that it should deal properly with lists that are empty and lists that have
one element. Here are some tests to provide examples:
;; all of these are true
(test (sorted? '(1 2 3) <=))
(test (sorted? '(1 2) <=))
(test (sorted? '(1) <=))
(test (sorted? '() <=))
(test (sorted? '(2 2 2) <=))
(test (sorted? '(3 2 1) >=))
(test (sorted? '("z" "y" "x" "w") string>=?)) ; compares strings
;; and some false tests
(test (not (sorted? '(1 2 3) >=)))
(test (not (sorted? '(1 3 2) <=)))
Remember to write a proper type declaration (it is important here), and a
purpose statement.
(Hint: match can make the solution simple.)
Question 2: Racket Programming II
14 pts
In last semester’s midterm, we’ve implemented an optimize function
that takes in a unary function and returns a version that “remembers”
its last input and output, and if given that last input again, it will
return the same output and avoid running the function again. See the
“sample-midterm?.rkt” text for that implementation.
Your task in this exam is to extend that function so that instead of
remembering only the last input value and its corresponding result, it
will keep all of them. Once you implement this extension to
optimize, the tests from that exam would obviously change to indicate
that no results are forgotten:
(: foo : Number -> (Listof Number))
(define (foo n)
(printf "Foo was called with ~s\n" n)
(list (+ n 1)))
;; Now optimize it:
(define optimized-foo (optimize foo))
;; And we can now start testing -- we'll use a new `=output>'
;; that tests for printed output together with a value:
(test (optimized-foo 1)
=output> "with 1"
=> (list 2))
;; We now call it with a different value, so we still call the
;; original `foo' function
(test (optimized-foo 2)
=output> "with 2"
=> (list 3))
;; Call it with 2 again, and see that it returns the same result
;; with no output:
(test (optimized-foo 2)
=output> "" ; <--expect no output
=> (list 3))
And here is the change:
;; Using 1 again retrieves the saved value and does *not* call
;; the function again
(test (optimized-foo 1)
=output> "" ; <--expect no output
=> (list 2))
;; And using 1 again gets the remembered value and no output
(test (optimized-foo 1)
=output> "" ; <--expect no output
=> (list 2))
The type of optimize is still the same, so you can reuse it, but the
purpose statement should be adjusted, and, of course, the implementation
should change. You will need a different kind of value for the cache
(and a different type), and you will need to do a lookup for the input
value. For the lookup, you should write a small lookup helper, and
its implementation would be similar to the lookup function that we
have used in our interpreters (it can uses Racket’s assoc function
(same way we used assq), or do the loop itself). Don’t forget to
write a type for the helper as well.
Question 3: BNF Grammar
13 pts
Consider the following BNF grammar, for a silly language of fruit names:
<Fruits> ::= <Fruit> ...
<Fruit> ::= apple | orange
Valid “expressions” in this language have any number of apples and
oranges, in any order. Write a modified version of this grammar where
there could only be an odd number of apples (and still any number of
oranges). The modified language should still allow mixing them freely.
If you think that it is impossible to do this, the explain why.
(Hint: this is not a hard question, just consider how expressions
in the new language look like.)
Question 4: Fill in the blanks
15 pts
For each one of the following expressions, write a definition for blank
in Racket that makes the expression evaluate to 660. For example, a
correct answer for this expression:
(* (blank) 2)
is:
(define blank (lambda () 330))
If you think that it is impossible to write such a definition, explain why
this is the case. (Remember: this is Racket, not Schlac or FLANG, or
any other language that we’ve seen.)
The language is always the #lang pl that you’ve used so far. Unless
explicitly specified, you do not need to write types for the definitions, and
assume no mutation is allowed.
One of the very basic optimizations that practically all compilers do is
called “constant folding”. In this optimization, the compiler computes
and “inlines” results of expressions with known functions (or operators)
and known input constants. The result is that you can write code like:
int seconds_per_year = 60 * 60 * 24 * 365;
instead of computing it yourself
in seconds_per_year = 31536000; // 60*60*24*365
In this question you will implement a limited version of this optimization
for FLANG — dealing only with folding arithmetic expressions that have
known constant numeric inputs. Name your function fold-constants.
Here are a few tests that demonstrate it, using “parse” to make the
inputs and outputs readable, with comments that describe each case:
;; simple cases
(test (fold-constants (parse "12"))
=> (parse "12"))
(test (fold-constants (parse "{+ 1 2}"))
=> (parse "3"))
;; nothing to fold
(test (fold-constants (parse "x"))
=> (parse "x"))
(test (fold-constants (parse "{+ 1 x}"))
=> (parse "{+ 1 x}"))
;; only one part gets optimized
(test (fold-constants (parse "{* {+ 1 x} {* 2 3}}"))
=> (parse "{* {+ 1 x} 6}"))
;; even in functions and named expressions, etc
(test (fold-constants (parse "{fun {x} {* {+ 1 x} {* 2 3}}}"))
=> (parse "{fun {x} {* {+ 1 x} 6}}"))
(test (fold-constants (parse "{with {x {* {+ 1 x} {* 2 3}}} x}"))
=> (parse "{with {x {* {+ 1 x} 6}} x}"))
;; works for nested expressions too
(test (fold-constants (parse "{* {* 60 60} {* 24 365}}"))
=> (parse "31536000"))
(test (fold-constants (parse "{fun {x} {* {+ 1 2} {* 2 3}}}"))
=> (parse "{fun {x} 18}"))
;; optimizes division only if it's not by zero
(test (fold-constants (parse "{/ 1 0}"))
=> (parse "{/ 1 0}"))
;; note that it can see a 0 which is the result of folding
(test (fold-constants (parse "{/ {- 5 4} {- 6 6}}"))
=> (parse "{/ 1 0}"))
In your implementation you should avoid writing tons of code by creating a
local helper. The helper will get the two subexpressions and the Racket
function to be used with them. Note that for the case of division by
zero, you can compare the helper’s input function to know if it’s
division: (eq? f /). (This is not always a good idea but fine to do
here..)
You need to write only the definition of fold-constants, nothing
else.
Question 6: Extending the FLANG Language
18 pts
We want to extend the FLANG language by having default expressions for
function arguments. (We will extend the FLANG-ENV
implementation.) To make life easy for you, we’ll require all
functions to have defaults. To make it even easier, I’ll do most of the
work. The relevant parts that you need to know about are:
The BNF changes to have a default value expression value in
functions:
The AST and parser change too, we’ll use Call0 and Call1 for the
two, instead of Call:
(define-type FLANG
...
[Call0 FLANG] ; no argument, use the default
[Call1 FLANG FLANG]) ; plain call, not using the default
Function closures need to change too, to hold onto the expression,
first the VAL type:
(define-type VAL
[NumV Number]
[FunV Symbol FLANG FLANG ENV]) ; holds the expression
Finally, the only thing that you need to do is implement the changes to
the eval function.
You need to update the code that creates closures to store the
extra expression.
You need to replace the Call case with two cases for Call0
and Call1. Note that the body of these cases would be similar to
the current Call but with some differences — a tiny change in
Call1, and a slightly bigger one for Call0.
Notes:
Some quick tests:
;; x defaults to 1, but it is not used
(test (run "{with {foo {fun {x 1} x}}
{call foo 3}}")
=> 3)
;; x defaults to 1, and it is used
(test (run "{with {foo {fun {x 1} x}}
{call foo}}")
=> 1)
;; x defaults to 1+2
(test (run "{with {foo {fun {x {+ 1 2}} x}}
{call foo}}")
=> 3)
It is important to not evaluate the default expression when it is
not needed. Here’s a test for that:
;; x defaults to 9/0, not used => no error
(test (run "{with {foo {fun {x {/ 9 0}} x}}
{call foo 3}}")
=> 3)
It is important to evaluate the default expression in the right
environment — which one is it? The following will help:
;; test that the default is evaluated in the right scope
(test (run "{with {a 3}
{with {foo {fun {x {* a 2}} x}}
{with {a 10}
{call foo}}}}")
=> 6)
Question 7: 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.)
There is exactly one function that is different according to its semantics
from the other three. Which one is it?
Here’s a joke:
Why is “abbreviated” such a long word?
There’s a whole bunch of these gems:
Why is “short” longer than “long”?
Why is “big” smaler than “small”?
Why is “syllable” longer than “word”?
Why is “million” the same length as “hundred”?
What makes these sentences funny (to most people)?
They put together contrasting words in a similar context, which
makes people laugh.
Because the “dynamic scope” of the reader is used whereas people
natually assume lexical scope for human text.
Because they remind people of the Y combinator.
Because they mix the levels of syntax and of meaning.
Because they’re using complex words next to simple words in
unexpected ways.
They’re not funny.
After showing off your knowledge of black lambda magic to too many people,
you’re put up on trial and sentenced to be banished and live in exile on a
deserted hacker island. You’re allowed to take a limited number of
#lang pl forms with you, starting with lambda abstraction and
applications.
You now need to choose between list or cons with you — which one
should you choose?
list, since it’s more convenient.
list, because it can be used with any number of
arguments (so it can do more than cons).
cons, since it can do more than list.
cons, since it can do more than list, but this is
just a convenience because you have lambda, and can
implement your lists anyway.
Neither, since they cannot be used anyway, unless you
have the full#lang pl language with you.
In question 5 we have implemented a constant-folding optimization for
FLANG. As mentioned there, this is a common optimization that compilers
perform. There is a generally subtle point about this kind of an
optimization that we didn’t need to face, but it can be a real issue for
compiler implementors who need to do such optimizations very carefully.
What is this point?
We need to be careful to use exactly the same semantics for folding
the arithmetic operations as is used for running them. We get this for
free, because we use Racket arithmetics for both, but if we were
compiling to machine code, we’d to be aware of possible differences
between arithmetics in this machine code and the and in our own code.
For example, an integer could “roll back” on a 32 bit compiler which
would be bogus in a 64 bit environment.
When we implement a proper compiler, we need to be aware of the fact
that we’re dealing with lexical scope, not dynamic scope. The change in
semantics can lead to false optimizations when the two kinds of scopes
don’t agree. We didn’t need to deal with this since we implement an
interpreter.
Because we implement an interpreter, this optimization is completely
redundant and will not save any time running code, so we could just as
well skip it. However, with a proper compiler it can lead to saving
runtime, which is an important aspect of encouraging programmers to write
good code instead of hard-wiring pre-computed constants in their code.
In general, we need to be careful from the kinds of optimizations
that can run into an infinite loops. This is similar to the
simplification of the fib function in the Schlac language, and the
fact that we couldn’t simplify all of the immediate function
applications.
Question 8: Schlac
16 pts
In class, we have seen how the Lambda Calculus (or Schlac, in our case)
can be used to encode values of various types as functions. One thing
that we’ve seen is that certain functions can be viewed as an encoding of
values of different types. For example,
1 (a number) is also the identity function (an A -> A
function),
#f (a boolean) is also 0 (a number),
2 (a number) is also a square operation (a
Number -> Number function), and in fact, any encoded number n is
a xn operation when used as a Number -> Number function.
There are many more functions that can be viewed as doing different things
for different types. For example, consider or, defined as:
(define or (lambda (a b) (a a b)))
and view it as a Number -> Number function. When used as such a
function, we can show that (or n) computes
nn as follows:
(or n)
expanding the `or' definition
--> ((lambda (a b) (a a b)) n)
expanding shorthands
--> ((lambda (a) (lambda (b) ((a a) b))) n)
reducing the immediate application
--> (lambda (b) ((nn) b))
since everything is a function, this is the same as just
--> (nn)
and according to what we know about how numbers are viewed as
unary numeric functions:
--> nn
Show what and (not or) does when viewed as a binary numeric
function, (Number Number -> Number). Your explanation should be
formal.