Principles of Programming Languages — Homework 12

Due by class time Tuesday, October 29

    Download the file assign12.scm and use it as your starting point for this assignment. This is the version of the interpreter we developed in class today with support for application expressions with any number of arguments and user-defined functions (fun expressions) with any number of parameters.

    You can use the auto-tester for exercises 2 and 3 below by downloading hw12-tester.scm and auto-tester-base.scm and putting them in the same folder as assign12.scm. Then uncomment the line (require "hw12-tester.scm") at the top of assign12.scm and type (test:) at the DrRacket prompt. There are no test cases available for exercise 1, so for that exercise you will have to test your code manually.

  1. The expression (fun (x y z) : (x + (y + z))) creates a function with three input parameters x, y, and z that returns the sum x+y+z. If we give this function the name f, the application expression (f 1 2 3) will call the function on the arguments 1, 2, and 3, and the value 6 will be returned: 

       (run '(with [f = (fun (x y z) : (x + (y + z)))] :
            (f 1 2 3)))
    → 6
    If we call the function on more than three arguments, for example: (f 1 2 3 4 5), it will also work and we will get the same result of 6. However, this is not really desirable behavior, because passing an incorrect number of arguments to a function should generate an error message. The function should first check to make sure that the number of arguments passed into it matches the number of function parameters, and only execute the body expression if the right number of arguments was provided.

    Modify the interpreter so that if a function is passed an incorrect number of arguments, it will generate the error message "Wrong number of arguments received" (using Scheme's built-in error function). The same goes for the primitive functions square, squareroot, minus, !, average, and quadratic in the initial environment. For example:

    ;; should return 6
(run '(with [f = (fun (x y z) : (x + (y + z)))] :
         (f 1 2 3)))

;; should generate the error Wrong number of arguments received
(run '(with [f = (fun (x y z) : (x + (y + z)))] :
         (f 1 2 3 4 5)))

;; should return 25
(run '(square 5))

;; should generate the error Wrong number of arguments received
(run '(square 1 2 3))

;; should return 6
(run '(average 5 7))

;; should generate the error Wrong number of arguments received
(run '(average 1))

;; should generate the error Wrong number of arguments received
(run '(quadratic))

  2. Currently, application expressions must be of the form (<var> <exp> ...), that is, the application operator <var> must be a symbol like f, square, average, etc. Modify the interpreter so that the application operator can be any expression in our language. Hint: see Homework 9 exercise 2. Tester program: test cases 1-8. For example: 

    ;; should return 81
(run '(with [choice = 1] :
        ((if (choice == 1) then square else squareroot) 9)))

;; should return 3
(run '(with [choice = 2] :
        ((if (choice == 1) then square else squareroot) 9)))

;; should return 120
(run '((if True then ! else minus) 5))

;; should return -5
(run '((if False then ! else minus) 5))

;; should return 42
(run '((fun (a) : a) 42))

;; should return 6
(run '((fun (x y z) : (x + (y + z))) 1 2 3))

;; should return 25
(run '((with [sq = square] : sq) 5))

;; should return 16
(run '(((fun (f) : (fun (a) : (f a))) square) (2 + 2)))

  3. Ben Bitdiddle has decided to add two new primitive functions to our interpreted language, called (and exp1 exp2) and (or exp1 exp2), which are intended to work like and and or expressions in Scheme. He has modified the definition of the initial environment as shown below: 

    (define initial-env
  (extend (list 'a 'b 'c 'd ... 'and 'or)
          (list 1 2 3 4 ...
                ...
		;; and
		(lambda (args-list)
		  (let ([x (first args-list)]
			[y (second args-list)])
		    (and x y)))
		;; or
		(lambda (args-list)
		  (let ([x (first args-list)]
			[y (second args-list)])
		    (or x y)))
                )
          empty-env))
    When he tests his new functions, they seem to work: 
      (run '(and (1 == 1) (2 == 2))) → #t
  (run '(and (1 == 0) (2 == 2))) → #f
  (run '(and (1 == 1) (2 == 0))) → #f

  (run '(or (1 == 1) (2 == 0))) → #t
  (run '(or (1 == 0) (2 == 2))) → #t
  (run '(or (1 == 0) (2 == 0))) → #f
    Much to his surprise, however, when he tries the examples below, he gets errors, unlike in Scheme: 
    Interpreter:
  (run '(and (1 == 0) (zebra == 0))) → ERROR: unknown value for variable: zebra
  (run '(or (1 == 1) (zebra == 0))) → ERROR: unknown value for variable: zebra

Scheme:
  > (and (= 1 0) (= zebra 0)) → #f
  > (or (= 1 1) (= zebra 0)) → #t

    Explain in detail in a comment in your code why Ben's approach doesn't work.

    Then add support to the interpreter so that (and exp1 exp2) and (or exp1 exp2) expressions will work correctly. The and operator should evaluate exp2 only if exp1 evaluates to true; otherwise it should immediately return false. Conversely, or should evaluate exp2 only if exp1 evaluates to false; otherwise it should immediately return true. Both operators should return #t or #f as their final result. Tester program: test cases 9-26.

Turning in Your Homework