►Fundamentals I Honors
▼Problem Sets
    ← prev  up  next → 

Problem Set 10

home work!

Programming Language ISL+

This is the final problem set. Almost there!

Extending Husky

In this problem set, we will be extending the Husky language, as posted on the blog. As you go, do not forget to update the definition of Ident as appropriate.

Problem 1 As posted on the blog, the Husky language does not have full test coverage. Add tests as needed until it does. (Hint: you’ll need at least four tests.)

Problem 2 Extend Husky with Strings. This will involve changing the definitions of HExp and HValue, and adding a new cond branch to eval. And, of course, tests.

Problem 3 Extend Husky with the and and or boolean operators. Note that these cannot be primitive functions. Rather, they are new control operators (like if): since they use short-circuit evaluation, they do not necessarily evaluate all of their parts.

Here are the semantics for these two forms, in English:

  • (and exp1 exp2 ...) evaluates the exp expressions from left to right. As soon as some expression produces false, evaluation of the and form stops and the whole expression produces false. If all the exp expressions produce true, then the entire and produces true.

  • (or exp1 exp2 ...) evaluates the exp expressions from left to right. As soon as some expression produces true, evaluation of the or form stops and the whole expression produces true. If all the exp expressions produce false, then the entire or produces false.

The following check-expects should pass:
(check-expect (eval '(or  #f #t GARBAGE) empty) true)
(check-expect (eval '(and #t #f GARBAGE) empty) false)
Notice that the definitions above expect at least one argument to and or or. Your code will probably be made simpler if you allow for no arguments at all — in that case, think about how ormap and andmap work to decide what the behavior should be...

Problem 4 To make our lives easier, and to make eval much more elegant, we are going to lift out the apply branch to a helper function. Design the function happly, which has the following header:
; happly : HValue [Listof HValue] -> HValue
; Apply the-fun to the-args if it is a prim or clos, otherwise throw an error
(define (happly the-fun the-args)
  ...)

happly does not need to be explicitly tested. It should already be completely tested by your tests of eval.

Note: look very carefully at the signature for happly. That will guide you in deciding what code to leave behind in the function-application branch of eval, and what to lift out into the new happly function. (Among other things to notice: happly doesn’t need an environment parameter at all — why is that?)

Note: some of the remaining problems require this change in order for them to work. Make sure you do this problem before going on to the ones below!

Problem 5 What is the biggest feature our language is missing? Recursion, of course! Implementing arbitrary recursion is difficult, as you will soon discover in lecture, so we will extend husky with our favorite recursive function: foldr!

First, we will define a new abstract function data type:
; A Husky function [X Y Z... -Husky-> A] is a Prim or a Clos whose inputs
; are HValues with type X, Y, Z... and whose output is an HValue of type A

Now, we define husky-foldr. Look very carefully at the type here: husky-foldr is an ISL+ function that takes a Husky function as one of its arguments. Therefore in order for husky-foldr to call it, we must use happly...but in order for husky-foldr to recursively call itself, it just calls itself as normal:
; husky-foldr : [Y X -Husky-> Y] Y [Listof X] -> Y
; Takes a Husky function, a Husky base value, and a list of Husky values, and
; then folds the list from the right.  This is equivalent to ISL's foldr,
; except the order of args to the Husky function is reversed.
(define husky-foldr
  (λ(op base l)
    (cond
      [(empty? l) base]
      [else
       (happly op (list (husky-foldr op base (rest l)) (first l)))])))
(We’ve chosen to swap the order of arguments to the Husky function so they match the order of the arguments given to husky-foldr itself: first the initial base value, and then the list of values.)

To use this wonderful function, someone writing in the Husky language needs it as a language primitive. As such, extend ENV0 with the following pair:

(make-pair 'foldr (make-prim husky-foldr))

To test it, add the following check-expect, and modify ENV0 as necessary:
(check-expect
    (eval '(foldr
             (fun (acc x) (string-append (number->string x) acc))
             ""
             (const (0 1 2)))
          ENV0)
    "012")

Problem 6 Although we know we can write map with foldr, we cannot actually write the analogous husky-map with husky-foldr. Can you see why not? In either case, define husky-map similarly to husky-foldr, and extend ENV0 with husky-map the same way we did with husky-foldr. Test your function.

Husky+ Other programming languages have “for loops”, and far too many novice programmers think they’re essential for a “real” language. But with all of Fundies 1 under our belts, we know that loops are nothing more than recursion. Just...with slightly different syntax.

Writing an expression with foldr and map directly is somewhat verbose, with all those funky functions, so let’s see if we can modify the syntax of the language we write to allow for some terser code.

Our goal is to write expressions that look like the following:
'(for foldr ((acc "") (x (const (0 1 2))))
   (string-append (number->string x) acc)
)
We will introduce this special 'for form, provide it a looping function, identifiers, their initial values, and then a function that will give us the proper behavior we desire.

In other words, the above line will be semantically equivalent to

'(foldr (fun (acc x) (string-append (number->string x) acc)) "" (const (0 1 2)))

However, we will not be modifying HExp: we do not want to change our eval function, since it’s already fairly complicated.

Instead, we will create a new datatype, HExp+, which looks identical to HExp, except HExp is replaced with HExp+ everywhere, Ident is replaced with Ident+ eveywhere, and the following line is added:

; - (list 'for HExp+ [Listof (list Ident+ HExp+)] HExp+) – for expressions

Problem 7 Properly define HExp+ and Ident+.

Problem 8 Design the function simplify, that will take in a HExp+ and output the semantically equivalent HExp. Take note of the following equivalence:

’(for loopFunction ((arg1 value1) (arg2 value2) ...) body)

is the same as:

’(loopFunction (fun (arg1 arg2 ...) body) value1 value2 ...)

And the last expression is just a function application in HExp!

Notice that our language is much more flexible than most: we allow for-loops anywhere inside expressions, just like we allow if expressions anywhere. So, every time simplify encounters a for-loop expression, it should translate it as described above, and all other expressions should be recursively simplified (in case there are for-loops lurking inside them, too!).

Problem 9 Design the function eval+, which will evaluate HExp+ expressions in an Env. This should be a very short function.

Be sure to test on enough HExp+ expressions that test all of the looping functions in our language!

Armed with this simplify function as evidence, you can now convincingly and confidently state that there’s no really “new” expressiveness available with for-loops that couldn’t already be expressed with functions. (This approach, of defining more complicated language interpreters in terms of simpler core interpreters is how language researchers actually study languages.)

Extra Credit Problem 10 Did we actually gain any new expressiveness by adding and and or operators to our language? Convincingly and confidently make a yes or no claim, with evidence!

    ← prev  up  next →