6.7

Homework 7

home work!

Programming Language ISL with Lambda

Due Date Wednesday November 30 at 11:00 pm

Purpose To get hands-on experience developing interpreters.

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 if): 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.

    You may assume that all expressions given to and and or evaluate to true or false, rather than an arbitrary Husky value.

  2. Add String as a clause for the HExp data definition, add the evaluation logic for string expressions to eval, and add the primitive operations substring and string-append, so you can write programs in Husky that operate on strings.

  3. Extend the fun form to permit functions with variable arity (like "+"). Add an additional HExp form (fun param body), where param is a single symbol. This expression evaluates to a function where param is bound to the *list* of arguments to the function. Update the ev function to account for this new expression type.

    As mentioned in the challenge problem below, it’s not obvious how to implement recursion in Husky, but you need some form of looping in order to write interesting functions of this form. Here are primops for map and foldl that you may use:

    (make-binding 'map
                  (make-primop
                   (lambda (args)
                     (apply map (husky-1arg-proc->racket (first args)) (rest args)))))
    (make-binding 'foldl
                  (make-primop
                   (lambda (args)
                     (apply foldl (husky-2arg-proc->racket (first args)) (rest args)))))

    The above require these helper functions:

    ; Returns a Racket procedure for a 1-argument Husky procedure
    (define (husky-1arg-proc->racket f)
      (lambda (arg1) (app f (list arg1))))
     
    ; Returns a Racket procedure for a 2-argument Husky procedure
    (define (husky-2arg-proc->racket f)
      (lambda (arg1 arg2) (app f (list arg1 arg2))))

    Feel free to define/import other helpful primops.

  4. Add a let form with the following syntax: (let ((var exp) ...) body). The let form is similar to local, but it omits the extra define keyword.

    A let expression first extends the environment by evaluating each exp and adding a binding from var to the value of its exp. It then evalutes the body under this new environment and returns the result. For the purpose of this assignment, you may assume that no let expression has multiple bindings for the same variable.

  5. Challenge problem (not to be graded):

    What if we tried to define the length function in Husky? You might expect it would look something like this:

    (let ([length
           (fun (xs)
             (if (empty? xs)
                 0
                 (add1 (length (rest xs)))))])
      ; rest of your program...)

    But wait! We don’t have a binding for length to evaluate our recursive call! This is because we are defining let in terms of itself. The current Husky forms do not allow us to provide a binding for length while we’re defining it (Recall that let only extends the binding for its body, not for its definitions).

    To solve this issue, we need to define a new form, let-recursive, with the following syntax:

    (let-recursive ((var (param ...) fun-body) ...) body)

    This is like let, but each definition is a function, and the variables it defines are bound in the fun-body of each of its function definitions in addition to the main body expression.

    This exercise will not be graded, because it requires the use of side effects (which you haven’t dealt with much) to install the right environment into each closure. If you choose to attempt this problem, use the Advanced Student Language (ASL) and learn about the new function that define-struct provides in ASL.