►Fundamentals 1
▼Homeworks
    ← prev  up  next → 

Homework 11

home work!

Programming Language Advanced

This is the final problem set. You have until 10:00 pm, Wed April 19 to submit it.

Purpose This problem set is intended to help you gain understanding of the meta-circular interpreter we have developed in class.

image

Problem 1: Interpreter

Extend the Husky language and the interpreter for it that we have developed in class to add the following features:

  1. Add the and and or boolean forms to the Husky language. Note that these are not primitive functions. Rather, they are new control forms (like cond): since they do 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.

  2. Add the primitive operations substring and string-append, so you can write programs in Husky that operate on strings.

image

Problem 2: Extra credit

Get a little more experience with lexical scope and the management of environments in your Husky interpreter: add the let form to the language.

The syntax of this form is: (let ((var exp) ...) body)

The informal semantics is this: to evaluate a let form, first evaluate all the exp expressions, in the environment that exists outside the let. Then extend the current environment by binding all the var to the resulting values, and evaluate the body form in the extended environment. The result of evaluating the body form is the result produced by the entire let form.

We can put this more precisely, by simply saying that a let form produces exactly the same thing this does: ((lambda (var ...) body) exp ...). (Well, in Husky, you would use a fun instead of lambda...)

So, for example, here is Husky code using let that will compute the two solutions to the quadratic equation a*x^2 + b*x + c = 0:
(fun (a b c)
  (let ((discriminant (sqrt (- (* b b) (* 4 a c))))
        (two-a        (* a 2))
        (neg-b        (- b)))
    (list (/ (+ neg-b discriminant) two-a)
          (/ (- neg-b discriminant) two-a))))

(You can read up on let in the Racket documentation—or in just about any Scheme you can find. It’s a standard language element.)

    ← prev  up  next →