## Discuss exercises?

Mr.B
Mausschubser
Beiträge: 65
Registriert: 13. Dez 2009 17:04

### Re: Discuss exercises?

So I guess no one else has an idea for something that I cannot implement using substitution that I could implement using environments (without a store)?
I think the idea was that code which has side effects evaluates differently in substitution vs environment. Think of a "let" which binds an expression which makes your programm terminate to a variable which is never used. If you have (lazy) substitution, it will not error out because the bound expression is never evaluated. If you use environments, your interpreter will evaluate the bound expression and then terminate.
by lordhoto: viewtopic.php?f=300&t=30645

Since the program notably behaves different when using either subst or enviroments, I guess this answeres the question asked in the exercise.

r1chard
Erstie
Beiträge: 19
Registriert: 26. Mai 2011 17:23

### Re: Discuss exercises?

Mr.B hat geschrieben: That doesn't make much sense to me :/. Do you really need the enviroment to implement closures? U can also just substitute all "enviromental" variables in the closure when defining it. This should have the same effect as saving the enviroment at the point of definition, doesn't it?
I think a closure is defined as a function and its environment. Therefore ich meant that you cannot implement a closure without an enviroment.
We also have an interpreter for FWAE using substitution, therefore it is also possible.
But I think it does not use closures, but functions without identifiers (except the param).

So this was about the word closure, not about the ability of first-class functions.

plo1234 hat geschrieben:Jep, I'm with Mr.B here.
So I guess no one else has an idea for something that I cannot implement using substitution that I could implement using environments (without a store)?
I would assume recursion is not possible with substution.

plo1234
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

### Re: Discuss exercises?

Mr.B hat geschrieben: I think the idea was that code which has side effects evaluates differently in substitution vs environment. Think of a "let" which binds an expression which makes your programm terminate to a variable which is never used. If you have (lazy) substitution, it will not error out because the bound expression is never evaluated. If you use environments, your interpreter will evaluate the bound expression and then terminate.
by lordhoto: viewtopic.php?f=300&t=30645
I see. That makes sense.

r1chard hat geschrieben:I would assume recursion is not possible with substution.
Depends on wheter you have first class functions or not. Recursion is possible with substitution and first order functions!

Edit: Comming to think about it, it should also be possible with first order functions and lazy substitution.

Mr.B
Mausschubser
Beiträge: 65
Registriert: 13. Dez 2009 17:04

### Re: Discuss exercises?

So this was about the word closure, not about the ability of first-class functions.
I am talking about closures .
Ok, maybe you should not call it closure, but isn't it possible to archive the same effect with substituation though?
You could substitute free variables in a first class function definition. This would have the semantics of a closure, right? You have to watchout not overriting the parameters though.

plo1234
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

### Re: Discuss exercises?

Regarding ex.06.2
Mr.B hat geschrieben:

Code: Alles auswählen

## 2. Moving-GC
Env             Store
----+-----      ----+---------
x1 | 1           1 | Num(10)
x2 | 2           2 | Box(1)
x3 | 3           3 | Box(2)
res | 8           8 | Box(3)
Shouldn't be the adress of Box(3) be 4? And then ofcourse the pointer of res 4 as well?
Yes, I think so, too.

Code: Alles auswählen

After GC:
Env             Store
----+-----      ----+---------
|               |
|               |
|               |
|               |
|               |
|               |
|               |
|               |
----+-----      ----+---------
x1 | 8           8 | Num(10)
x2 | 9           9 | Box(8)
x3 | 10         10 | Box(9)
res | 11         11 | Box(10)
|               |
|               |
|               |
|               |
Shouldn't the adresses of Num(10)-Box(10) be incremented by 1?
Yep, my mistake!
What also comes to my mind, what's about the ordering when using a copying approach, shouldn't it be the other way round?
Like, res is referrenced so you put Box(3) in the second part of the heap and then see Box(3) is referenced so put Box(2) also in the second part of the heap and so on:

Code: Alles auswählen

Env             Store
----+-----      ----+---------
x1 |12            |
x2 |11            |
x3 |10            |
res | 9             |
|               |
|               |
|               |
|               |
|          ----+---------
|            9 | Box(10)
|           10| Box(11)
|           11| Box(12)
|           12| Num(10)
|               |

[/code]
I guess that is an implementation detail?! An implementation could collect all live objects first and then copy them into the other part of the heap in any order it wants. But I like your idea of not splitting the env. in two parts seems reasonable!

plo1234
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

### Re: Discuss exercises?

Mr.B hat geschrieben: You could substitute free variables in a first class function definition. This would have the semantics of a closure, right?
Yes!

Mr.B
Mausschubser
Beiträge: 65
Registriert: 13. Dez 2009 17:04

### Re: Discuss exercises?

Thx for that clarification plo1234!
I guess that is an implementation detail?! An implementation could collect all live objects first and then copy them into the other part of the heap in any order it wants.
Mh guess you are right.

Do you see any advantages of the copy approach over the moving approach?
I do not at the moment. When using the copy approach, you have to move all boxes just in the worst case scenario. When using the moving approach, you have to copy all boxes everytime which obviously implys a lot of overhead .

errt
Mausschubser
Beiträge: 61
Registriert: 18. Okt 2012 19:12

### Re: Discuss exercises?

Mr.B hat geschrieben:Do you see any advantages of the copy approach over the moving approach?
Well, if you don't identify the live objects first but copy objects once known to be live, you don't need to scan the memory for live objects after a mark phase. That would be good if the number of live objects is small compared to the amount of garbage. Also, you don't need the space for the mark bit then.

Marc
Neuling
Beiträge: 1
Registriert: 21. Apr 2012 22:35

### Re: Discuss exercises?

Hello,
I believe there should be one entry more in the store because
val x1 = Box(10) is the same as Box(Num(10))
which should be contained in 2 entrys in the store:

env:
x1 2

store:
1 Num(10)
2 Box(1)

Also, I believe that the env should only contain res after the gc call, because foo is in another scope that the val res = foo() call, which means that the x1 - x7 shouldn't be in the env from the foo call.

andiderp
Erstie
Beiträge: 20
Registriert: 14. Apr 2012 13:37

### Re: Discuss exercises?

Did anyone solve the exercise 7? I'm not quiet sure if there are any special cases you have to be aware of if you want to implement local variables in the OO interpreters.

plo1234
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

### Re: Discuss exercises?

I am also not sure if there are any special cases. Everthing I did was add a Let case class

Code: Alles auswählen

  case class Let(boundId: Symbol, namedExpr: Expr, body: Expr) extends Expr
and match it

Code: Alles auswählen

    case Let(boundId, namedExpr, body) => {
interp(body, env + (boundId -> interp(namedExpr, env, ct)), ct)
}


LordHoto
BASIC-Programmierer
Beiträge: 135
Registriert: 14. Dez 2009 17:00

### Re: Discuss exercises?

plo1234 hat geschrieben:This is what I have for ex06.2

Code: Alles auswählen

Before GC:
Env             Store
----+-----      ----+---------
x1 | 1           1 | Num(10)
x2 | 2           2 | Box(1)
x3 | 3           3 | Box(2)
x4 | 4           4 | Num(13)
x5 | 5           5 | Num(14)
x6 | 6           6 | Box(4)
x7 | 7           7 | Box(6)
res | 8           8 | Box(3)

This looks wrong to me. I got the following solution before GC based on our implementation of boxes:

Code: Alles auswählen

Before GC:
Env
----+-----
( x1 | 1
x2 | 3
x3 | 5
x4 | 7
x5 | 9
x6 | 11
x7 | 13)
res | 15

Store
----+------
0 | NumV(10)
1 | Box(0)
2 | Box(0)
3 | Box(2)
4 | Box(2)
5 | Box(4)
6 | Num(13)
7 | Box(6)
8 | Num(14)
9 | Box(8)
10 | Box(6)
11 | Box(10)
12 | Box(10)
13 | Box(12)
14 | Box(4)
15 | Box(14)

EDIT: The x1 to x7 values in the environment shouldn't be there because they are inside the "foo" and should thus be removed from the environment after execution, it's just for reference to get the behavior of the foo function.

The reason why I think this is correct is that these "var variable = exp" statements are "With" statements in our language. As a result we evaluate "exp" and then store the result at a new location at which the environment for "var" points at. Since each "With" allocates a new location for each variable and each "Box" call allocates a new location for the box value, we will have 2 times the number of "var x# = Box(...)" statements memory slots allocated, this should be 16 and matches the number of allocated slots I have.

A quick test with an interpreter run on the following program seems to give the same results:

Code: Alles auswählen

	val prog = With('x1, NewBox(10),
With('x2, NewBox('x1),
With('x3, NewBox('x2),
With('x4, NewBox(13),
With('x5, NewBox(14),
With('x6, NewBox('x4),
With('x7, NewBox('x6),
NewBox('x3)
)
)
)
)
)
)
)
val (_, resStore) = interp(With('res, prog, 1337), store = new NoGCStore(50))

Zuletzt geändert von LordHoto am 20. Jul 2014 16:30, insgesamt 1-mal geändert.
Compiler 1 Tutor WS 12/13

Eichhorn
Windoof-User
Beiträge: 36
Registriert: 9. Mär 2012 18:11

### Re: Discuss exercises?

plo1234 hat geschrieben:I am also not sure if there are any special cases. Everthing I did was add a Let case class

Code: Alles auswählen

  case class Let(boundId: Symbol, namedExpr: Expr, body: Expr) extends Expr
and match it

Code: Alles auswählen

    case Let(boundId, namedExpr, body) => {
interp(body, env + (boundId -> interp(namedExpr, env, ct)), ct)
}

Wouldn't this potentially result in conflicts in

case Invoke(oexp, method, args) => {
val rcv@Object(cl, fvals) = interp(oexp, env, ct)
val Class(fnames, methods) = ct(cl)
val Method(params, body) = methods(method)

val argVals = args map (e => interp(e, env, ct))
val paramEnv = Map() ++ (params zip argVals)
val envInvoke = paramEnv + ('this -> rcv)

interp(body, envInvoke, ct)
}

if there are name conflicts between parameters and local variables, potentially overwriting values calling interp(body, envInvoke, ct)?

andiderp
Erstie
Beiträge: 20
Registriert: 14. Apr 2012 13:37

### Re: Discuss exercises?

Maybe you need to forbid the usage of Let('this, _, _) because you also have a 'this binding when you invoke a method. The 'this binding is hardcoded, so it is a reserved word.

plo1234
BASIC-Programmierer
Beiträge: 116
Registriert: 14. Nov 2009 18:51

### Re: Discuss exercises?

LordHoto hat geschrieben:
plo1234 hat geschrieben:This is what I have for ex06.2
...
This looks wrong to me. I got the following solution before GC based on our implementation of boxes:
You are totally right. Thanks for the tipp!
So I guess the right solution should look something like this:

Code: Alles auswählen

## 1. Non-moving GC

Env             Store
----+-----      ----+---------
res | 15          0 | Num(10)
2 | Box(0)
4 | Box(2)
14 | Box(4)
15 | Box(14)

## 2. moving GC

Env             Store
----+-----      ----+---------
res | 4           0 | Num(10)
1 | Box(0)
2 | Box(1)
3 | Box(2)
4 | Box(3)

## 3. copying GC

Again I am not entirely sure how to handle the fact that with a  copy GC we
need a size limit. So I will again just assume that the whole heap has 30
"slots" (15 for each part).

Env             Store
----+-----      ----+---------
res | 20            |
----|---------
16 | Num(10)
17 | Box(16)
18 | Box(17)
19 | Box(18)
20 | Box(19)