*CSci 2041: Advanced Programming Principles, Fall 2015*
These are some examples of questions similar to those that will
appear on the second midterm.
##1. Program representation and analysis
+ Recall our data types for representing programs and the associated
analysis functions:
```
type expr =
Const of int | Bool of bool
| Add of expr*expr | Mul of expr*expr
| If of expr*expr*expr | Gt of expr*expr | Eq of expr*expr
| Set of string*expr | Name of string
| While of expr*expr | Seq of expr list
| Print of expr | Readint
type result = IntR of int | BoolR of bool | UnitR
type expType = IntT | BoolT | UnitT
type state = (string*result) list
type tyEnv = (string*expType) list
val typeOf : expr -> tyEnv -> expType = <fun>
val eval : expr -> state -> (result * state) = <fun>
```
+ Suppose we were to extend the above representation to allow integer
array values in the program (internally represented as lists of
integers), by adding the following variants to expr:
```
type expr = ...
| NewArr of expr*expr (* NewArr(n,v) makes a new array of n ints set to v *)
| ArrGet of expr*expr (* ArrGet(a,i) returns the item at index i of array a *)
| ArrSet of expr*expr*expr (* ArrSet(a,i,v) returns a copy of a with index i
set to value v *)
| ArrLen of expr (* ArrLen(a) returns the length of array a *)
```
What other types would we need to change in order to evaluate and
typecheck expressions with these features?
+ Recall that a "type judgement" is a rule for assigning a type to an
expression given the types of its subexpressions, e.g:
+ ` e1 : Int , e2 : Int `⇒ `Add(e1,e2) : Int`
+ `Const i : int`
+ `n : t, e : t` ⇒ `Set(n,t) : Unit`
Assuming that array values have type `Array`, what are the type
judgements for each of the new expression variants above?
+ Using these judgements, write the match clauses for each of the new
variants in `typeOf`.
+ Complete the match clasues in `eval` for each of the new variants in
`typeOf`. We'll make accessing an array at an out of bounds index
result in a runtime exception (e.g. in this situation `failwith
"array index out of bounds"` would be an acceptable result of evaluation)
+ Explain the difference between *static* and *dynamic* program
analyses, and give an example of each.
##2. Induction
Consider the following tree data type:
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller YourAssignmentHandlers01. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $14.99. You're not tied to anything after your purchase.
