NAME (print clearly):  

CSCI 330: Spring 2024 Final Exam S24N01,N03

Question 1: Dynamic scope [6]

The table below shows one bash program and its resulting output and one lisp program and its resulting output.

Using the provided code/output as your evidence, explain which of the languages (if any) are using dynamic scoping and which are using lexical scoping. Be sure to use the provided code/output to clearly justify your answer. 

x=10

function f() {
   echo "at the start of f: x is ${x}"
   local x=20
   g
   echo "back in f after running g: x is ${x}"
}

function g() {
   echo "at the start of g: x is ${x}"
   x=30
}

function main() {
   echo "at the start of main: x is ${x}"
   f
   echo "at the end of main: x is ${x}"
}

main

(defvar x 10)

(defun f ()
   (format t "at the start of f: x is ~A~%" x)
   (let ((x 20))
        (g)
        (format t "back in f after running g: x is ~A~%" x)))

(defun g ()
   (format t "at the start of g: x is ~A~%" x)
   (setf x 30))

(defun main ()
   (format t "at the start of main: x is ~A~%" x)
   (f)
   (format t "at the start of main: x is ~A~%" x))

(main)

at the start of main: x is 10
at the start of f: x is 10
at the start of g: x is 20
back in f after running g: x is 30
at the end of main: x is 10

at the start of main: x is 10
at the start of f: x is 10
at the start of g: x is 20
back in f after running g: x is 30
at the start of main: x is 10

Question 2: Tail recursion [6]

This semester we discussed systematic transformations of iterative functions into tail-recursive ones.

Based on those discussions, provide a tail-recursive equivalent of the following (C++) function: 

int q2(int x, int y)
{
   int r = 0;
   int i = 1;
   while (i < y) {
      r = i + f(r);
      x = g(x);
      i++;
   }
   return r;
}
(The syntax for optional parameters with default values is simply x=value.)

Question 3: Variadic functions [6]

In lab6 we considered a way to implement variadic functions in C++ using a recursive template format.

Suppose we wanted something more like lisp's approach, where we could have a parameter specifier indicating any number of additional arguments could be passed, and they would all be gathered in the final parameter, e.g. 
   void myFunc(int x, int y, variadic int R[], int RSize)
   // all the "extra" arguments must be of type int
   // and are collected as the elements of array R
   //     whose size is then stored in RSize
Thus for function call myFunc(10, 17, 23, 4, 9) the elements of R would be 23, 4, 9 and RSize would be set at 3 automatically.

Discuss the benefits and problems that would arise from such an addition to the C++ language.

Question 4: Higher order functions [6]

In lab 6 we used templates to develop a C++ apply function, e.g. r = apply(pow, x, y); or r = apply(sqrt, x);.

Outline the strengths and weaknesses of such an apply function as compared to common lisp's version of apply.

Question 5: Macros [6]

Mark Shannon makes the following statement in support of macro systems (as part of Python Enhancement Proposal 638):

In the context of that statement, explain how well or how poorly (or a mix of both) common lisp has fared with its use of macros.

Question 6: CFGs and ambiguity [6]

The grammar below is ambiguous.

Briefly explain the source of the ambiguity, and provide a revised set of rules to remove the ambiguity while still accepting the same set of assignment expressions.

(The VARNAME token is an alphabetic string representing a variable name and the ASSIGNOP token is simply the = character.) 

assignment --> VARNAME
assignment --> assignment ASSIGNOP assignment

Question 7: CFGs, precedence, and associativity [6]

Study the following set of context free grammar rules with three operator tokens (XOP, YOP, ZOP) and four expression nonterminals (expression, exprA, exprB, exprC), then identify the relative precedence level and the associativity for each of the three operators and explain how you arrived at your answer. 

expression --> exprB
expression --> exprB XOP expression
exprA --> exprA ZOP exprC
exprA --> exprC
exprB --> exprA YOP exprB
exprB --> exprA

Question 8: Context sensitive checking and symbol tables [6]

Consider the following set of context free grammar rules (with tokens represented in uppercase and nonterminals in lowercase) and identify the correct spots in the correct rules where:

Briefly explain why these are the correct spots. 

statements --> statement
statments --> statement statements
statement --> assignment
statement --> declaration
assignment --> VARNAME ASSIGNOP value
declaration --> scopetype VARNAME
scopetype --> GLOBAL
scopetype --> LOCAL
value --> VARNAME
value --> NUMBER

Question 9: Type checking, conversions, and compatibility [6]

Erlang is a dynamically typed language that allows us to define function behaviour in terms of what the function does for different combinations of parameters, e.g. a function to compute the nth fibonacci number could be expressed as 

% rules for fib(N)
%    the conditions for a rule are left of the ->,
%    the result for the rule is to the right of the ->
fib(0) -> 0;
fib(N) when is_integer(N), N < 1 -> 0;
fib(N) when is_integer(N), N < 3 -> 1;
fib(N) when is_integer(N) -> fibhelper(N, 0, 1).

% rules for fibhelper(N, pp, p) where N is how many N's we have left to count
%    and pp, p are the two most recent fib numbers calculated
fibhelper(1, _, P) -> P;
fibhelper(N, PP, P) -> fibhelper(N-1, P, PP+P).

What we're interested in is that _ parameter: it is used to indicate a parameter whose value we don't care about (i.e. it can be ignored in this rule). In this particular rule it says the value of the PP parameter is irrelevant if the value of the N parameter is 1.

Suppose it were possible in lisp to pass a don't care value when calling a function, e.g. (foo 13 _ 4.6).

Discuss the possible benefits of this (if any), and the implications for runtime type checking by the caller.

Question 10: Attributes and binding [6]

In lectures we discussed a variety of types of attribute (name, value, type, storage, scope, lifetime) and the options to either statically or dynamically bind each of them.

For each of the six kinds of attribute, name a language where that attribute can be dynamically bound and provide a brief justification (justifying the claim that the named language can bind that attribute dynamically).

Question 11: Smart pointers [6]

In our final lecture we discussed smart pointers in the context of C++.

While a lisp programmer doesn't generally need to worry about how memory is handled, the developers of lisp compilers/interpretters do need to deal with how items (e.g. lists) are dynamically allocated/deallocated in the heap, and how to keep track of when deallocation should take place.

If we were to use C++ as the language in which we wrote our lisp compiler, would smart pointers be a sensible choice, or would we be better off using standard raw pointers for the implementation? Discuss/justify your answer.

Question 12: Type implementations and implications [6]

When considering structs/records as a data type, we discussed the problems relating to memory alignment and the ordering of fields within the structure.

Suppose we were designing a new C-like language, and someone proposed the following as a solution to this problem:

Discuss the problems/drawbacks with such a solution.