Comparative Programming Languages

Ga naar: navigatie, zoeken
FrankPiessens.jpg

Informatie over het examen

Oplossingen van (sommige) examens en oefeningen (zonder enige garanties).

Examenvragen

2016-01-28

1. Gegeven het volgende programma in PROC:

 let f = proc(f) proc(x) (f(f x))
 in let x = proc(x) x
   in ((f x) 2)

a) Wat is de waarde van het programma na evaluatie?

b) Teken de AST en teken daar de contour diagrams op. Teken vanuit iedere bounded variable een pijl naar zijn declaratie.

c) Vertaal naar LEXADDR.


2. Uitbreiding van CHECKED met datatype tuples van de vorm ty1*ty2. Moet 3 nieuwe methodes ondersteunen: newTuple(exp1,exp2), p1(exp1) en p2(exp1). newTuple maakt een nieuw tuple aan, exp1 en exp2 mogen naar een verschillend type evalueren. p1 en p2 geven respectievelijk de eerste en tweede component van exp1 terug indien exp1 evalueert tot een type.

a) Geef de regels voor type checking in CHECKED voor newTuple, p1 en p2.

b) Geef de nodige uitbreiding van type-of voor CHECKED.

c) Welke equations in INFERRED zouden de drie nieuwe methodes geven?


3. Schrijf de value-of/k trace uit voor een THREADS programma als er een lang tijdsslot wordt gegeven. Gebruik maken van notatie met holes [] en je mag de environment negeren.


4. Gegeven het volgende CLASSES programma. Het programma had 3 klasses, object was superklasse van c1, c1 van c2 en c2 van c3. Een object van c3 wordt aangemaakt, de constructor van c3 roept deze van c1 op. Daarna wordt een methode van het object opgeroepen die een super methode oproept van c2, deze roept op zijn beurt een super methode op van c1.

a) Voor elke method invocation (inclusief constructor en super calls), geef:

- De naam van de methode die wordt opgeroepen en de klasse waarin ze gedefinieerd is.

- De environment (inclusief bindings voor parameters, self, super en fields) waarin de method invocation plaatsvindt.

b) Geef de contents van de store op het einde van de uitvoering van dit programma. De initial environment van het programma bevat i, v en x met respectievelijk waardes 1, 5 en 10.


5. Vraag over case study language RUST. Gegeven was een programma met een main en 6 korte methodes waarbij in elke method header en method call plaats was gelaten om & of &mut in te vullen of om het open te laten.

a) Geef de output van het programma.

b) Vul de method headers en method calls aan met & of &mut of laat het open. & staat voor immutable borrow, &mut voor mutable borrow en open laten voor ownership doorgeven. Vul het programma zo aan zodat elke methode zijn taak kan volbrengen en zodat bij een oproep parameters minimaal worden door gegeven (& > &mut > leeg laten) en bij een returnvalue maximaal wordt doorgegeven (leeg laten > &mut > &).

2016-01-23

1. Consider the following PROC programs

let f = proc(x) 1 in
   let f = proc(y) if zero? y then 0 else (f (y-1)) in
     (f 2)
let g = let x = 1 in proc(f) (f 0) in
   let x = 2 in (g   proc(y) x)

1A. To what values do these programs evaluate?

1B. To what value would they evaluate when PROC uses dynamic scoping instead of static scoping?

1C. Write a PROC program p such that p evaluates to the constant function that maps any integer to 0, and such that p would evaluate under dynamic scoping to the function that doubles its integer argument.


2. Extend the IMPLICIT-REFS language with an address-of operator (&) that can be applied to variables only. The expression &v returns the location of variable v in the store. Also extend the language with setref and deref expressions such that these locations can be used. These extensions make it possible to simulate call-by-reference in IMPLICIT-REFS.

For instance, the following program in the extended language should return the value 1:

let a = 3 in
  let b = 4 in
    let swap = proc(x) proc(y)
                let temp = deref x in
                  begin setref(x, deref y); setref(y, temp) end
    in begin ((swap &a) &b); (a-b) end

Extend the interpreter of IMPLICIT-REFS:

2A. How should the datatype of expressions be extended?

2B. How should the datatype of expressed values be extended?

2C. Write the additional cases that need to be added to the value-of function.


3. Consider the continuation-passing interpreter for LETREC. Write down the trace of invocations of value-of/k that occur during evaluation of the following expressions. For each invocation, just write the expression and continuation that are passed in as parameters (i.e. you can ignore the environment parameter).

Write the expression in concrete syntax and the continuation as an expression in concrete syntax with a hole (written as [ ]). For continuations that contain values (as opposed to expressions), write them as follows: a num-val is written as an underlined number (here: written in bold), any proc-val is written just as: proc.

Here is an example:

value-of/k(2-1, []) --> value-of/k(2, [] - 1) --> value-of/k(1, 2 - []) --> 1
3A. ((x - v) - i)  // Remember that x, v and i are bound to 10, 5 and 1 in the initial environment
3B. ((10 - 9) - (6 - 4))
3C. let f = proc(x) x in ((f 2) - (f 3))
3D. let f = proc(x) (1-x) in let g = proc(y) (1 - (f y)) in (g 0)


4. Consider the following CLASSES program:

class c1 extends object
     field x
     method initialize() x := 1
     method m1(z) x := (x - z)
class c2 extends c1
     field x
     method m1(z) begin x := 111; super m1(z) end
class c3 extends c2
     field x
     field y
     method initialize()
          begin super initialize(); x := 2222; y := 3333 end
let o3 = new c3()
in begin send o3 m1(44); o3 end

4A. For each method invocation that this program performs (including constructor and super calls), write down:

a) The name of the method being called, and the class in which it is defined.

b) The environment (including bindings for parameters, self, super and fields) in which that method invocation takes place.

4B. Write down the contents of the store at the end of the execution of this program. (Keep in mind that the initial environment of the program contains i, v and x with values 1, 5 and 10 respectively)


5. What types would the type inference algorithm from the INFERRED language infer for the following programs? Write out each of the programs below with all question marks replaced by the inferred types, and also write down the type of the entire program:

A. proc(x:?) proc(y:?) x
B. proc(x:?) (x x)
C. proc(f:?) letrec ? g(x:?) = (g x) in let y = (f (g 1)) in (g 1)
D. let f = proc(x:?) 1 in (f   proc(x:?) x) - (f 1)


September 2015-09-01

1) Gegeven het volgende programma in IMPLICIT-REFS:

let z = 1
in let a = proc(x) let z = 10
                   in proc(y) begin x := 20; y end
   in ((a z) z)

a) Gegeven een initieel leeg environment, hoe ziet de store er uit na het uitvoeren?

b) Wat is de waarde van het programma na evaluatie?


2) Gegeven het volgende programma in PROC:

let x = proc(x) (x-1)
in let x = proc(x) x
   in ((x x) 1)

a) Wat is de waarde van het programma na evaluatie?

b) Teken de AST en teken daar de contour diagrams op. Teken vanuit iedere bounded variable een pijl naar zijn declaratie.

c) Vertaal naar LEXADDR.


3) Schrijf de value-of/k trace voor volgende programma's in LETREC:

a) ((x-v)-i) //x,v,i are bound to 10, 5, 1 in the initial environment.
b) ((10-9) - (6-4))
c) let f = proc(x) x in ((f 2) - (f 3))
d) let f = proc(x) (1-x) in let g = proc(y) (1 - (f y)) in (g 0)


4) Breid LETREC uit met primitieve support voor lijsten. Breid de syntax uit met cons, car, cdr, null? en emptylist. Breid de interpreter uit om correct met deze functies om te gaan.


5) Welke types zal het type inference algoritme van INFERRED voor volgende programma's bepalen? Schrijf telkens het programma opnieuw op, waarbij elk vraagteken vervangen wordt door het type. Schrijf ook het type op van het gehele programma.

a) proc(x:?) proc(y:?) x
b) proc(x:?) (x x)
c) proc(f:?) letrec ? g(x:?) = (g x) in let y  = (f (g 1)) in (g 1)
d) let f = proc(x:?) 1 in (f proc(x:?) x) - (f 1)


Januari 2015-01-29

1) Gegeven het volgende programma in IMPLICIT-REFS:

let g = let x = 100
    in prox(y) let r = x
               in begin x := y; r end
in (g 99)

a) Gegeven een initieel leeg environment, hoe ziet de store er uit na het uitvoeren?

b) Wat is de waarde van dit programma na evaluatie?


2) De interpreter voor PROC implementeert static scoping. Beschrijf alle aanpassingen die gedaan moeten worden om dynamic scoping te ondersteunen.


3) Gegeven de continuation-passing interpreter for LETREC. Schrijf de gedetailleerde trace van invocaties van value-of/k voor:

a) (100 - 98) - (60 - 50)
b) let x = 20 in (x - 44)
c) let d = proc (f) proc(x) (f (f x)) in ((d proc(x) (x-1)) 3)


4) Gegeven het volgende CLASSES-programma:

class c1 extends object
    field x
    field y

    method initialize()
        x := 1

    method m1(z)
        y := z

class c2 extends c1
    field y

    method m1(z)
        begin y := 100; super m1(z) end

class c3 extends c2
    field y
    field z

    method m1(x)
        begin super m1(x); y := 1000; z := 2000 end

let o3 = new c3()
in begin send 03 m1(13); o3 end

a) Teken het environment voor de drie invocaties van m1

b) Geef de store na het uitvoeren (vertrekkende van een initieel leeg environment)

c) Het kan gebeuren dat een methode geen toegang heeft tot alle velden in het object. Beschrijf in detail onder welke voorwaarden dit wel zo is.


5) Breid de type checker van CHECKED uit om om te gaan met EXPLICIT-REFS. (Boek pagina 248, oef. 7.10)


Januari 2015-01-24

1) Gegeven het volgende programma in PROC:

let g = proc(x) let y =x 
    in proc(z) (x-(y-z)
in ((g 1) 1)
a) Teken de AST en teken daar de contour diagrams op. 
   Teken vanuit iedere bounded variable een pijl naar zijn declaratie 
b) Vertaal het programma naar LEXADDR waarbij er dus geen variable namen bestaan.

2) Gegeven het volgende programma in IMPLICIT-REFS waarbij we veronderstellen dat het initiële environment leeg is:

let d let f = proc(x) x
      in proc(g) begin f:=g; (f 1) end
in (d (proc(x)2))
a) Geef het resultaat van het programma
b) Geef de store aan het einde van het programma.

3) Gegeven een aantal types, geef een programma dat met inferrence dat type als resultaat geeft (%x is een var-type) bv.

a) (bool->bool) -> (int->int)
b) (%1->%2) -> (%2->int) -> (%1->bool) 
c) %1
d) %1 -> %2

4) Maak devolgende uitbreidingen op CLASSES: (1) fieldvalue obj field-name die de value teruggeeft van gegeven veld van het gegeven object (2) fieldvalue-set obj field-name exp die het gegeven veld van het gegeven object op de value van de gegeven expressie zet. Geef voor elk A) de syntax en B) de aanpassingen aan de interpreter en eventuele helper functies.

5) Iets met THREADS en wat de evaluatie is als er een lang tijdsslot wordt gegeven [idem dito]

September 2014

1) Beschrijf alle veranderingen die moeten worden uitgevoerd aan de proc interpreter, om ervoor te zorgen dat de zero? test beschikbaar is in de initiele environment, ipv hargecodeerd in de syntax van de taal.

2) let a = newref(newref(newref(0))) in

      let f = proc(l)
          begin
            setref(deref(deref(l)),l);
            deref(l)
          end in
      deref((fa))
 a) Als dit programma runt met een lege initiele environment en store, hoe ziet de store er dan uit als de executie gedaan is
 b) Naar wat evalueert het programma

3) Continuation passing interpreter LETREC. Schrijf de invocaties van value-of/k op dat gebeuren tijdens de evaluatie van de volgende expressies (negeer de environment parameter)

a. let x=0 in (1-x)

b. (15 - if zero?0 then 1 else 2)

c. let double = proc (f) proc (x) (f(f x)) in ((double proc(x) (x-1)3)

4) De type checker van CHECKED uitbreiden voor tuples

5) Extend classes met fieldref en fieldset (oefening 9.8 in boek)

Januari 2014

1) Gegeven een programmake:

a) Teken de AST.
b) Teken daar de contour diagrams op.
c) Teken vanuit iedere bounded variable een pijl naar zijn declaratie ofzoiets. (zoals in de slides, einde hoofdstuk 3)
d) Naar wat evalueert het programma?

2) gegeven een programmake in IMPLCIT(hoofdstuk 4):

a) Geef de uiteindelijke staat van de store.
b) Naar wat evalueert het programma?
c) Naar wat zou het evalueren moest het call-by-refence zijn ipv call-by-value?

3) Er zijn 3 stukjes programme gegeven met een "hole" in (hoofdstuk 5)

ze leken op (uit herinnering ...):
a) ((2-3) - [])
b) ([] - (2-3))
c) (let x = 3-1 in ([] x))   [en dus niet (let x = (2-3) in (x-2))]

Slechts 1 van de 3 is mogelijk. Welke en waarom?

4) Gegeven enkele expressies: Geef de unknown types en het type van de gehele expressies zoals INFERENCE (hoofdstuk 7) dat zou doen.

5) Vul CLASSES (hoofdstuk 9) aan met de expressie 'instanceof'(zoals bij Java).

Januari 2014 (25/01)

Zie kopie

1) Gegeven een programma:

a) Wat is het resultaat bij static-scoping
b) Wat is het resultaat bij dynamic-scoping
c) Schrijf een programma dat bij static-scoping de constante 0 functie is en bij dynamic-scoping het dubbel teruggeeft

2) Gegeven een programma:

a) Wat is de inhoud van de store op het einde van het programma
b) Wat is het resultaat van het programma bij call-by-value
c) Wat is het resultaat van het programma bij call-by-reference

3) Gegeven een programma, geef een trace van de value-of/k functie voor de continuation. (Zelfde trace als het scheme programma van de cursus geeft, maar dat enkel voor de value-of/k en niet de apply-cont).

bv.

   (x-5) => value-of/k((1-5), [])
         => value-of/k(1, []-<5>)
         => value-of/k(5, 1-[])
         => -4

maar dan met ingewikkeldere expressie...

4) Gegeven een aantal types, geef een programma dat met inferrence dat type als resultaat geeft (%x is een var-type)

bv.

   a) int
   b) (int -> int) -> (int ->bool)
   c) %1
   d) (%1 -> %2) -> (%2 -> int) -> (%1 -> bool)
   e) %1 -> %2
   f) (%1 -> %2) -> %1

5) Pas de interpreter (CLASSES) aan zodat je een methode kan oproepen op statische manier (met behulp van zijn klassenaam).

Zodat je kan schrijven: call-static <obj> <klassenaam> <methode-naam> <args>

Je moest hierbij de constraint afdwingen dat de klasse van obj dezelfde moest zijn als <klassenaam> of een subklasse.