Due Monday, Dec 17, Submit your exam to me at your demo

Submission Locations:

1. email deugo@scs.carleton.ca with answer file as an attachment.
2. my mailbox in The School of Computer Science main office - 5302 Herzberg Building.
3. give to me during your demo on Monday, Dec 17.

Submission File Formats:

1. Word
2. RTF
3. text
4. HTML

Make sure you include the following:

1. Name:
2. Student #

Instructions (READ THESE INSTRUCTIONS CAREFULLY):

1. Students with an even last digit (0,2,4,6,8) in their student numbers should answer 5 out of 6 questions marked  EVEN. Students with an odd (1,3,5,7,9) last digit in their student numbers should answer 5 out of 6 questions marked  ODD.
2. You get to choose which 5 questions out of 6 you answer.
3. Ottawa University students use your Ottawa University student number, Carleton University students use your Carleton University student number.
4. Answer questions within the specified word limits. However, be direct and to the point. Remember less is often better.
5. Please be as neat as possible. If I can’t read it, I can’t give you credit for it.
6. Feel free to use point form instead of prose (it's easier to understand and uses less words) and, use examples/diagrams if you feel they are required.
7. Your answers should be your own. You are not permitted to work in groups on this exam.
8. If you have questions, send me an email

Questions:

EVEN QUESTIONS

1. [EVEN: 10 marks] Compare and contrast Scheme and Prolog as good or bad languages using the attributes of a good language discussed in class (600 word limit).
2. [EVEN:  10 marks] A) Since Scheme supports procedural application, why does it require special forms (200 word limit)? B) Scheme has a number of special forms that are not required. They are knows as syntactic sugar because the are easier for developers to write and can be transformed to other basic special forms. Identify four special forms that are syntactic sugar and show their translations to more basic forms, e.g. rewrite the syntactic sugar special form as the more basic special form offering the same functionality.
3. [EVEN: 10 marks] Describe (in words, do not physically provide code)  what you would need to change in the metacircular interpreter to support dynamic scoping (600 word limit).
4. [EVEN: 10 marks] Provide a Scheme implementation of a List object (similar to Scheme's list) with public instance methods (getHead, getTail, cons, and sizeOf),  three private instance variables (head, tail and value), and one constructor that is passed the value of the current list. Note that the tail and head of a List object are themselves List objects. You can add other private methods and instance variables as required.
5. [EVEN: 10 marks] Write the clauses for the Prolog relation sumList defined as follows:
 
sumList (Ns, Sum) ->
  Sum is the sum of the list of integers Ns.
6. [EVEN: 10 marks] Draw a contour diagram illustrating the bindings defined for the following code segment at the beginning of the min procedure (where you see *** below)  the first time it is evaluated (not when it is defined).

 

 

 (define (createMoney x1 x2)
   (let ( (dollars x1) (cents x2) (self 1)  )
    (define (getAmount) (+ ( * dollars 100) cents))
    (define (print) (list "$" dollars "." cents))
    (define (lessThan? aMoney) ( < (getAmount) ((aMoney 'getAmount))))
    (define (min aMoney)
        ***
     (if (lessThan? aMoney)
      self
      aMoney))
    (define (dispatch operation)
     (cond
      ((equal? operation 'getAmount) getAmount)
      ((equal? operation 'print) print)
      ((equal? operation 'lessThan?) lessThan?)
      ((equal? operation 'min) min)
      (else (error "wrong function call"))))
    (set! self dispatch)
    self))
 

 (define m1 (createMoney 10 50))
 (define m2 (createMoney 50 10))
 (define m3 ((m1 ‘min) m2))
 

ODD QUESTIONS

1. [ODD: 10 marks] Compare and contrast Scheme and Prolog as good or bad languages using the attributes of a good language discussed in class (600 word limit).
2. [ODD: 10 marks] A) Why does Scheme's procedure cons need to be a special form (200 word limit)? B) Scheme has a number of special forms that are not required. They are knows as syntactic sugar because the are easier for developers to write and can be transformed to other basic special forms. Identify four special forms that are syntactic sugar and show their translations to more basic forms, e.g. rewrite the syntactic sugar special form as the more basic special form offering the same functionality.
3. [ODD: 10 marks] Describe (in words, do not physically provide code)  what you would need to change in the metacircular interpreter to support dynamic scoping (600 word limit).
4. [ODD: 10 marks] Provide a Scheme implementation of a BinaryTree object with public instance methods (getLeftChild, getRightChild and depthOf ),  three private instance variables (leftChild, rightChild, value), and one constructor that is passed the value and the left and right children of the BinaryTree that are themselves BinaryTrees or nil. You can add other private methods and instance variables as required.
5. [ODD: 10 marks] Write the clauses for the Prolog relation range defined as follows:.
 
range (M, N, Ns) ->
  Ns is the list of integers between M and N inclusive.
6. [ODD: 10 marks] Draw a contour diagram illustrating the bindings defined for the following once the entire Scheme code segment has been evaluated (e.g., after evaluating the last line  -> (define m3 ((m1 ‘min) m2)) .
 
 (define (createMoney x1 x2)
   (let ( (dollars x1) (cents x2) (self 1)  )
    (define (getAmount) (+ ( * dollars 100) cents))
    (define (print) (list "$" dollars "." cents))
    (define (lessThan? aMoney) ( < (getAmount) ((aMoney 'getAmount))))
    (define (min aMoney)
     (if (lessThan? aMoney)
      self
      aMoney))
    (define (dispatch operation)
     (cond
      ((equal? operation 'getAmount) getAmount)
      ((equal? operation 'print) print)
      ((equal? operation 'lessThan?) lessThan?)
      ((equal? operation 'min) min)
      (else (error "wrong function call"))))
    (set! self dispatch)
    self))
 

 (define m1 (createMoney 10 50))
 (define m2 (createMoney 50 10))
 (define m3 ((m1 ‘min) m2))