I am still working on grading the midterms and hope to be done before class. In the meantime, here are some detailed comments on individual questions, based on what I have seen so far: [I haven't proofread this, sorry for any typos]:
- This was about type errors being caught more easily in the OO approach. Most people got this. The point is that since nodes that are instances of a given non-terminal are represented as objects that are instances of the corresponding class, there being one class for each non-terminal, if we do something like, "d.execStmt()" where d represents a node of type, say, and hence is an object of class Decl, the compiler [when compiling your interpreter] will catch the error since the method execStmt() doesn't apply to objects of type Decl. [Some seemed to think this will cause a runtime crash. No! The whole point is that we want this to be caught at compile time and that is what will happen.]
The second part asked about the static mechanism and where it is used. We used it for the Id class because when we encounter an id in the input stream (during parsing), we don't want to blindly construct a new Id object because an Id object with that name might already exist; in that case, we should just return that object. That is what the static mechanism allowed us to do. Similarly, in order to avoing having multiple Tokenizer objects, we used the static mechanism. We didn't need this in the ParseTree class approach because all the identifiers were inside the single ParseTree object; so we could look at all of them to see if an id with the given name already exists.
- This was about dyn. scope. The idea of dyn scope is that a called function can refer to the variables of the calling function (and the function that called the calling function etc.). So if we have two functions F1 and F2, and F1's parameters are called p1, p2, p3 and F2's parameters are called q1, q2; then if there is a call to F2 in the body of F1, then during this call, in the body of F2 we can make use not only of q1 and q2 but also p1, p2, p3.
The way this is implemented is via the a-list. The a-list contains the bindings of all the functions whose evaluation is not currently complete. In the above scenario, when F1 is called (from, say, the top level), the argument values corresponding to its parameters p1, p2, p3 will be added to the a-list. Then the body of F1 is evaluated. During that evaluation, it calls F2. So the argument values (passed in this call) corresponding to F2's parameters q1, q2 will be added to the a-list. Then the body of F2 will be evaluated. During this evaluation, if we refer to q2, we will get the value bound to q2, this being the second argument value passed during the call to F2 inside F1. If we refer to p3, we will get the value bound to p3, this being the third argument value passed during the call to F1 from the top level.
Of course if we call F2 directly from the top level, during the evaluation of this call, we will get an error when we refer to p3 because, at this point, there is no binding for p3 on the a-list.
Many people got his wrong; they talked about things like global variables (which List does not have) or "dynamic" means that the "scope is changing" etc.
- This asked you to find result of a number of Lisp/Scheme expressions. Most people got this right, the most common mistake being using lists when you had to use dotted s-expressions. For example, in the first one, "(cons (cons 2 3) (= 2 3))", the correct result is ((2 . 3) . #f) and many people wrote, ((2 3) #f)
Also some people said that (quote 4) will give errors etc. Not true; it will just return 4.
-
This asked you to define a function "good" that takes a non-empty list of numbers as arguments and returns #t if the first element was equal to the sum of the remaining elements. Most got this right.
-
This was similar and again most got this right.
-
This defined a function ckList that takes a list of three or more integers as argument:
ckList[L] :: [ <[sum[L], 0] --> car[L]; | =[sum[L], 0] --> cadr[L]; | <[sum[L], 10] --> caddr[L]; | #t --> 0; ]
The question was, why is this inefficient and can we make it efficient.
It is inefficient because it repeatedly calls sum[] to compute the same result. We can make it more efficient by introducing an auxiliary function and calling that in ckList[]:
ckList[L] :: ckList2[ sum[L], L ]
ckList2[x, L] :: [ <[x, 0] --> car[L]; | =[x, 0] --> cadr[L]; | <[x, 10] --> caddr[L]; | #t --> 0; ]
Here, ckList[] computes sum[L] once and passes it as an argument to ckList2 which can use it as many times as needed without having to recompute the sum [since the value of sum[L], passed by ckList[] in its call to ckList2[], is bound to x on the a-list and can be used as many times as needed].
--Neelam