UNB/ CS/ David Bremner/ tags/ cs3613

This feed contains pages with tag "cs3613".

The final exam, worth 50% of your mark, is tentatively scheduled for 7PM on April 22.

Posted Tue 22 Apr 2014 08:00:00 PM ADT Tags: /tags/cs3613

## Garbage Collection

Consider the following definitions in the format of Homework 2; the vector represents a heap, with each heap location either being a primitive or an object to other heap locations.

```(define-type Object
[object (Listof Index)]
[primitive])

(define example-heap
(vector
(primitive)          ; 0
(object (list 8))    ; 1
(object (list 1))    ; 2
(object (list 7))    ; 3
(object (list 0 3))    ; 4
(primitive)          ; 5
(object (list 0))    ; 6
(object (list 4 6)) ; 7
(object (list 2)))) ; 8
```
• (1) Give a minumum (smallest possible) set of roots so that a marking phase will find no garbage in the heap.

• (2) Suppose the set of roots is empty. How much of the heap will be marked as live by reference counting? Suppose the value at location 7 is a primitive, how does this change your answer?

Posted Thu 10 Apr 2014 12:00:00 AM ADT Tags: /tags/cs3613

## rewrite rules

-( 1) Give a rewrite rule (in the `#lang pl broken` dialect) for a short circuiting `nand` (negated and) by transforming it to not and.

```(test (nand #f) => #t)
(test (nand #f (/ 1 0)) => #t)
(test (nand #t #f (eq? (/ 1 0) 0)) => #t)
```
• (2) Give a rewrite rule for `and` (here called `and2` to reduce confusion) that uses andmap to implement it. You will probably need a computer to get the details right here. The real issue is quoting or delaying evaluation.
```(test (and2 #f) => #f)
(test (and2 #f (/ 1 0)) => #f)
(test (and2 #t #f (eq? (/ 1 0) 0)) => #f)
```
Posted Wed 09 Apr 2014 12:00:00 AM ADT Tags: /tags/cs3613

All of the examples are either the course language "PL", or the toy language "FLANG". It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

## Recursion

• (1) Use `let` and `lambda` to define a recursive list length function that takes itself as a parameter, so that the following test passes.
```#lang pl broken
(test
(let (
; ...
)
(len len  '(a b c d e))) => 5)
```
• (2) Write the curried version of `len`, (still using `let` and `lambda`) that makes the following test pass.
```#lang pl broken
(test
(let
;...
((len len)  '(a b c d e))) => 5)
```
• (3) fill in the definition of make-len to make the following test pass.
```#lang pl broken
(test
(let
((make-len
; stuff
(if (null? list)
0
(+ 1 (len (rest list)))))))))
(let ([len (make-len make-len)])
(len '(a b c d e)))) => 5)
```

## Evaluation Delay

• (1) What is the output of running this racket code?
```#lang pl broken

(define (make-test self)
(let ([test (self self)])
(lambda (arg)
(if arg
arg
(test (not arg))))))
(display "after define make-test\n")

(define test (make-test make-test))

(display "after define test\n")

(display (test #f))
```
• (2) Modify the let statement in the above code so that it runs to completion.

## Y combinator

• (1) What is the output from the following code? Explain your answer.
```((lambda (x) (x x)) (lambda (x)
(begin
(display "hi!\n")
(x x))))
```
• (2) Given the following definitions, trace the evalutation of `(test #f)` Use a computer for this one.
```#lang pl broken

(define (make-recursive f)
((lambda (x) (f (lambda (n) ((x x) n))))
(lambda (x) (f (lambda (n) ((x x) n))))))

(define test
(make-recursive
(lambda (test)
(lambda (arg)
(if arg
arg
(test (not arg)))))))
```
Posted Tue 08 Apr 2014 12:00:00 AM ADT Tags: /tags/cs3613

All of the examples are either the course language "PL", or the toy language "FLANG". It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

## Data structures with functions

Fill in the definitions of `empty-map` and `extend` such that the given tests pass.

```(define-type Map = String -> Number)

; stuff

(define test-map
(extend "mary" 1
(extend "bob" 2
(empty-map))))

(test (test-map "bob") => 2)
(test (test-map "mary") => 1)
(test (test-map "happiness") =error> "empty map!")
```

## Embedding

• (1) Given the syntactic (i.e. not using racket procedures) definition of an FLANG function, write the `funcall` function that allows calling FLANG functions from Racket. This one you probably will need a computer to get the details right, but try to get the main idea on paper.
```(define-type VAL
[NumV Number]
[FunV Symbol FLANG ENV])

(define foo (eval (parse "{fun {x} {+ x 1}}") (EmptyEnv)))
(define bar (eval (parse "41") (EmptyEnv)))
(: funcall : VAL VAL -> VAL)
; define funcall
(test (funcall foo bar) => (NumV 42))
```
• (2) Now consider the FLANG interpreter that uses union types to represent FLANG values. Write funcall for this intepreter.
```  (define-type VAL = (U Number (VAL -> VAL)))

; write funcall; don't forget a type signature.

(test (funcall f 41) => 42)
```
Posted Mon 07 Apr 2014 12:00:00 AM ADT Tags: /tags/cs3613

All of the examples are either the course language "PL", or the toy language "FLANG". It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

## Substitution Caches

• (1) Write a lookup function with this type signature to look up a symbol in a substitution cache / environment. For extra practice, use match.
```    (: lookup : Symbol (Listof (List Symbol Sexp)) -> Sexp)

```
• (2) Explain why environments use a list or list-like structure, rather than something more efficient like a hash table.

## Dynamic and Lexical Scope

• (1) Explain why the following evaluation rule guarantees our the corresponding interpreter will not have lexical scope.

eval ({fun { x } E} , sc ) = {fun { x } E}

• (2) Evaluate the following dynamically scoped racket code.

```#lang pl dynamic

(define (blah func x)
(func x))
;
(let ((x 7))
(let ((f (lambda (y) (+ x y))))
(let ((x 6))
(blah f 5))))
```
• (3) Evaluate the same code using substitution semantics.

• (4) Modify the following evaluation rules so that they make sense for the limited dialect of racket used in the preceding example.

```  eval(N,env)         = N
eval({+ E1 E2},env) = eval(E1,env) +
eval(E2,env)
; ...
eval(x,env)                = lookup(x,env)
eval({with {x E1} E2},env) = eval(E2,extend(x,eval(E1,env),env))
eval({fun {x} E},env)      = <{fun {x} E}, env>
eval({call E1 E2},env1)  =
if eval(E1,env1) = <{fun {x} Ef}, env2> then
eval(Ef,extend(x,eval(E2,env1),env2))
else
error!
```
• (5) Evaluate the previous example using your new environment based evaluation rules.

• (6) Compare the behaviour of the following code under dynamic scope, substitution, and environment based evaluation.

```    {with {f {fun {y} {+ x y}}}
{with {x 7}
{call f 1}}}

```
Posted Sun 06 Apr 2014 12:00:00 AM ADT Tags: /tags/cs3613

There will be one midterm, worth 25% of your mark, on March 20, 2014.

Posted Thu 20 Mar 2014 09:48:00 AM ADT Tags: /tags/cs3613

All of the examples are either the course language "PL", or the toy languages "WAE" or "FLANG" (WAE with functions). It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

## Lazy evaluation

1. Evaluate the following using purely lazy substitution and purely eager substitution
``` {with {x 1}
{with {x {+ x 1}}
x}}
```

1. Give an example of WAE code exhibiting name capture,

## de Bruijn Indices

Convert the following WAE expression to deBruijn form.

```{with {x 1}
{with {x {+ x 1}}
{with {y x} x}}
```
Posted Sat 15 Mar 2014 12:00:00 AM ADT Tags: /tags/cs3613

All of the examples are either the course language "PL", or the toy languages "WAE" or "FLANG" (WAE with functions). It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

## BNF and Parsing

Consider the subset of Racket consisting of `define`, +,-,*, and numbers and identifiers. Complete the following BNF for this language, to include defining and calling functions. If you want to experiment, you may find lexer.rkt and driver.rkt helpful.

```expr: arith | define | IDENT | NUMBER
arith: "(" op NUMBER+ ")"
op: "+" | "-" | "*"
define: "(" "define" IDENT expr ")"
```

### Using BNF

The following expression reveals at least one error in the grammar given above. Correct it.

```(define (glug x) (if (zero? x) 1 (* x (glug (- x 1)))))
```

### Using match

Fill in the following `match` based parser for lists of `a`s and `b`s

```(define-type ABList
[Empty]
[A ABList]
[B ABList])

(: parse-sexpr : Sexpr -> ABList )
(define (parse-sexpr sexpr)
(match  sexpr
;; stuff
))

(test (parse-sexpr '(a b a)) => (A (B (A (Empty)))))
(test (parse-sexpr '(a)) => (A  (Empty)))
```

## More types

Give a valid type declaration for the following function

```(define (glonk f g)
(lambda (x)
(let* ((h (g x))
(i (f h)))
i)))
```

## Substitution

• Evaluate the following by substitution.
```{with {x {+ 4 2}}
{with {x {+ x 1}}
{* x x }}}
```
• Identify the problem with this definition of substitution semantics:

To substitute an identifier `i` in an expression `e` with an expression `v`, replace all instances of `i` that are not themselves binding instances, and that are not in any nested scope, with the expression `v`.

## More Higher Order Functions

For each of the function type declarations below, write a PL Racket function with that type declaration. Each function should do something "sensible"; describe what that is in a few words.

```(define-type UnaryFun  = (Real -> Real))
(define-type BinaryFun = (Real Real -> Real))

(: a : UnaryFun Real -> Real )

(: b : BinaryFun Real -> UnaryFun )

(: c  : BinaryFun UnaryFun UnaryFun -> BinaryFun)

(: d  : UnaryFun UnaryFun -> UnaryFun)
```
Posted Wed 12 Mar 2014 12:00:00 AM ADT Tags: /tags/cs3613

All of the examples are either the course language "PL", or the toy languages "WAE" or "FLANG" (WAE with functions). It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

## Racket

For each of the following untyped racket expressions, write what it evaluates to (if valid) or explain what the error is.

```#lang pl

(if "true" 0 1)

(first (rest '(a b)))

(cond
[(> 3 1) 0]
[(< 3 1)  1])

(+ 1 2 3)

(and #f (/ 1 0))

(cons 3 (list 1 2))

(let ([ x -1])
(let ([ x (+ 10 x)]
[ y (+ x 1) ])
(+ x y)))
```

## Types

Give a valid type declaration for each of the following functions. Don't worry too much about the subtleties of different kinds of numbers.

```(define (f) 8)

(define (g x)
(cond
[(string? x) x]
[(number? x) x]
[else #f]))

(define h  (lambda (x y)
(string-length (string-append x y))))
```

## Variant types

Given the following variant type declaration, define a function to test two shapes for equality (never mind the built-in `equal?` predicate does this perfectly well).

```(define-type Shape
[Square  Number] ; Side length
[Triangle Number Number]) ; height width
```

## Higher order functions

Consider the tests

```(test ((pair 1 3) +) => 4)
(test ((pair 1 3) -) => -2)
(test ((pair 2 3) *) => 6)
```
1. Write the function `pair` to pass these tests.

2. Give a valid type declaration for `pair`

## Tail recursive functions

In the following tail recursive function, what should `<if-expr>` and `<second-argument>` be?

```(: sum : (Listof Number) Number -> Number )
(define (sum list acc)
(if (null? list)
; <if-expr>
(sum (rest list)
; <second-argument>
)))

( test (sum '(4 5 6) 0) => 15)
```
Posted Mon 10 Mar 2014 12:00:00 AM ADT Tags: /tags/cs3613