CSCI 330: Spring 2025 Final Exam

NAME (print clearly):

CSCI 330: Spring 2025 Final Exam

Make sure your name is clearly written on the exam
Answer directly on the exam, extra paper and scrap paper is available if needed.
You have 3 hours to complete the exam (9am-noon)
The exam is closed book, closed notes, no electronics are permitted, but you are permitted one double-sided 8.5"x11" reference sheet ("cheat sheet").
There are 7 questions worth 12 marks each, plus 1 mark for remembering your name, for a total of 85 marks: attempt all questions.
All VIU official rules for writing exams in the gym apply.

Question	Mark
1. Dynamic binding [12 marks]
2. Recursion/tail recursion [12 marks]
3. Subroutines/parameters [12 marks]
4. Macro systems [12 marks]
5. Basic scanning and parsing [12 marks]
6. Augmented (context sensitive) grammars [12 marks]
7. Type conversions and compatibility [12 marks]
Wrote your name at the top :) [1 mark]
Exam Total [85 marks]

Question 1: Dynamic binding [12]

When looking at lisp this semester we considered three forms of dynamic binding that isn't seen in languages like C++/Java/C: dynamic binding of types, scopes, and names.

In your own words, for each of these three forms of binding (dynamic types, dynamic scopes, dynamic names):

(i) Provide a short (one sentence) description/definition of the term.

(ii) Briefly discuss what it enables us to do in common lisp that is not easily done in languages without that form of dynamic binding.

(iii) Briefly discuss the key problems it introduces for programmers using common lisp (problems not present in languages that do not utilize that form of dynamic binding).

Question 2: Recursion/tail recursion [12]

A typical first-year introduction to recursion often includes an algorithm for computing Fibonacci numbers, e.g.

Fibonacci(N)
   if N < 3 return 1
   else return Fibonacci(N-1) + Fibonacci(N-2)

Explain why this algorithm is not tail recursive, and outline a tail-recursive alternative.
(Suggestion: use accumulators for the two previous Fibonacci numbers.)

Question 3: Subroutines/parameters [12]

This semester we looked at common lisp's support for variadic functions using &rest, as well as common lisp's support for higher order functions using (among other things) funcall, apply, and eval.

We also examined ways to use C++ templates to support both variadic functions and higher order functions in C++.

Briefly outline two scenarios:

one scenario in which you would choose C++ over lisp due to the way it handles variadic and/or higher order functions, and
one in which you would choose lisp over C++ due to the way it handles variadic and/or higher order functions.

For both scenarios explain why the language's handling of variadic/higher-order functions would be the difference-maker in your choice.

Question 4: Macro systems [12]

This semester we looked at two forms of support for macros in programming languages: common lisp's defmacro and C++ templates.

For each of the two,

(i) Describe one way in which it can be used to re-write the programmer's source code prior to compilation.

(ii) Describe one advantage the approach provides in comparison to the other.

Question 5: Basic scanning/parsing [12]

First, provide regular expressions for each of the following token types:

An integer literal: begins with the character 'i', followed by a single sign character ('+' or '-'), followed by one or more digits ('0' to '9').
A procedure name: begins with the character 'p', followed by an uppercase alphabetic character ('A' to 'Z'), followed by zero or more alphanumeric characters (i.e. any one of 'a' to 'z', 'A' to 'Z', or '0' to '9').

Second, provide a context free grammar for the programming language with the structure described below. Assume we already have definitions for token types IDENTIFIER, DECLARED, EQUALS, LITERAL, WRITE, PLUS, MINUS, DIVIDE, TIMES, END.

A program consists of a definitionset followed by a statementset followed by a result.
A definitionset consists of one or more definitions.
A statementset consists of one or more statements.
A definition consists of an IDENTIFIER token followed by a DECLARED token
A statement consists of an IDENTIFIER token followed by an EQUALS token followed by an expression followed by an END token.
A result consists of a WRITE token followed by an IDENTIFIER token.
An expression consists of any one of the following:
- an IDENTIFIER token, or
- a LITERAL token, or
- two expressions followed by an operator.
An operator consists of any one of following token types: PLUS, MINUS, DIVIDE, or TIMES.

(Aside: the postfix nature of the expressions mean the grammar is not ambiguous.)

Question 6: Augmented (context sensitive) grammars [12]

First, briefly describe why augmented grammars are necessary in the checking/handling of checking things like type-checking of expressions and variable declarations/scope.

Second, outline the role(s) a symbol table can play in such checking, and how such checking relates to the rules in the underlying context free grammar for the language.

Question 7: Type conversions and compatibility [12]

First, briefly outline the distinction between narrowing and widening type conversions, and how they can relate to the underlying storage limitations on data types.

Second, briefly describe the difference between name-based and structure-based type compatibility, and why name-based compatibility is the preferred form for most modern programming languages.