►Fundamentals I
▼Problem Sets
    ← prev  up  next → 

Problem Set 11

home work!

Programming Language ISL+

This is the final problem set. You have until midnight, Tuesday December 8 to submit it.

Purpose This problem set (primarily) concerns the design of accumulator-style functions.

image

Problem 1: A number, n>1, is prime if it is not divisible by any numbers besides 1 and itself, such as 2, 3, 5 and 7.

  1. Design the function prime? which consumes a Natural Number, n and returns true if it is prime and false otherwise. Use the fact that if n is not prime, one if its factors must be less than or equal to the square root of n.

  2. Design the function list-primes which consumes a Natural Number, n, and produces the list of prime numbers up to n.

Problem 2: The Fibonacci numbers, which are the numbers in the following sequence: 0 ,1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,... are defined by the recurrence relation: Fn = Fn-1 + Fn-2, with seed values F0 = 0 and F1 = 1.

  1. Design the function fibonacci, (without accumulators) which consumes a Natural Number and produces its Fibonacci number. For example, (fibonacci 11) should produce 89.

  2. Use accumulators to design a more efficient version of fibonacci.

  3. Design a function, list-fibonacci, that consumes a Natural Number and produces the list of Fibonacci numbers from F0 to Fn.

image

Problem 3: 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 operators. Note that these are not primitive functions. Rather, they are new control operators (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 4: 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 →