Discuss exercises?

[plo1234]

Hi,
since there are no sample solutions, is anyone interessted in discussing some exercises?
I'll start with ex.3 and will probably add more. Feel free to comment...

# Exercise 03


## Task 1: Immediate substitution vs deferred substitution

For the language F1WAE, we introduced environments as an alternative for
substitutions.

### 1. Why did we do this?

Increase efficiency: we don't have to traverse the whole program
(especially unvisited branches) for substitution before actually
interpreting.

### 2.Discuss the advantages and disadvantages of substitution versus environments.

* Substitution is hard to get right
* Environments are more efficient

### 3. Write F1WAE examples that notably behave differently when run with an interpreter that uses substitution versus environments.

Anyone?


## Task 2: Scoping

### 1. What is the difference between dynamic scoping and static (lexical) scoping?

With static scoping a name always refers to its lexically "closest" binding
(?). With dynamic scoping a name always refers to the value that has been
bound to the name most recently.

### 2. What does ‘static’ stand for in static scoping?

The scope of a name can be determined statically (at compile time), like in
static-analysis.

### 3. Why is dynamic scoping bad?

* it is counter-intuitive
* we cannot see the scope of a name only by looking at the code


## Task 3: Deferred substitutions and closures

Consider the interpreters for FWAE.

### 1. In the interpreter with environments we introduced closures. What is a closure? What do we need them for?

A closure is a function plus the environment at the time the closure has
been created. We needed Closures because in the interpreter with
environments, we have to save the current environment when we encouter a
function defintion.

### 2. Why did we not need closures in the interpreter with substitution?

Because all bound instances are substituted as soon as the interpreter
encounters a function definition.

### 3. Why did we not need closures in the F1WAE interpreter with environments?

Because only arguments and local variables are in the scope of F1-Functions.
Things like this are not possible:

val funDefs = Map('f -> FunDef('n, Add('n, 'x)))
i

best, plo1234

[bluefish]

Exercise 3

I think an Example for 1.3 could be:

Code: Alles auswählen

App(
   Let('x,3,
      Fun('f,1)
   ), Map('f -> FunDef('y,'x)) //is equal to def f(y) = x
)

With enviroments this should be an error but with substition this should evaluate to 3.



Exercise 4

Am I Right that in Exercise 4 the recursive version of myfun myfun(n)=myfun(n+1) is?
Because thats a very stupid function... I'm feeling very bad about that solution

[plo1234]

Code: Alles auswählen

App(
   Let('x,3,
      Fun('f,1)
   ), Map('f -> FunDef('y,'x)) //is equal to def f(y) = x
)

With enviroments this should be an error but with substition this should evaluate to 3.

Yeah, I have though about something like that. But are there programs to don't abort, but have different results for env/subst?

Am I Right that in Exercise 4 the recursive version of myfun myfun(n)=myfun(n+1) is?
Because thats a very stupid function... I'm feeling very bad about that solution

I think it is more like this:

Code: Alles auswählen

    def scalaMyFun(myFix: (Int => Int)) =
        ((n: Int) => myFix(n + 1))

[bluefish]

Code: Alles auswählen

App(
   Let('x,3,
      Fun('f,1)
   ), Map('f -> FunDef('y,'x)) //is equal to def f(y) = x
)

With enviroments this should be an error but with substition this should evaluate to 3.

Yeah, I have though about something like that. But are there programs to don't abort, but have different results for env/subst?

I tested it, it aborts in the subst interpreter too.... Bad thing...

Am I Right that in Exercise 4 the recursive version of myfun myfun(n)=myfun(n+1) is?
Because thats a very stupid function... I'm feeling very bad about that solution

I think it is more like this:

Code: Alles auswählen

    def scalaMyFun(myFix: (Int => Int)) =
        ((n: Int) => myFix(n + 1))

Yes, of course, but the function adds itsself still to infinite, doesn't it?

[biz]

I tested it, it aborts in the subst interpreter too.... Bad thing...

Shouldn't something like this work:

Code: Alles auswählen

Let('x, Num(3), 
       Add(
             Let('x, Num(1), Id('x)),
             Id('x) ))

Substitution should evaluate to 6 and env interp to 4.




My solution to exercise 10.2:

Evaluate the following expression with the:
1. Call-By-Value
2. Call-By-Name
3. Call-By-Need (Expression Result Caching)
4. Call-By-Need (Memoization)
evaluation strategy, respectively. Provide the result of the evaluation and the calls to 'fac in total (including recursive calls).

Code: Alles auswählen

Let('fac,
    Fun('x,
      If0('x,
        1,
        Mult('x, App('fac, Sub('x, 1))))),
    Let('x,  Div(7,0),
      Let('y, App('fac, 4)
        Add('y, Add('y, App('fac, 3)))
        )
    )

• // 1. Call-by-Value:

breaks at Div(7,0), because of eager evaluation

• // 2. Call-by-Name:

App('fac, 4) App('fac, 3) App('fac, 2) App('fac, 1) App('fac, 0)
App('fac, 4) App('fac, 3) App('fac, 2) App('fac, 1) App('fac, 0)
App('fac, 3) App('fac, 2) App('fac, 1) App('fac, 0)

14 Calls, Result: 54

• // 3. Call-by-Need (Expression Result Caching):

App('fac, 4) App('fac, 3) App('fac, 2) App('fac, 1) App('fac, 0)
App('fac, 3) App('fac, 2) App('fac, 1) App('fac, 0)

9 Calls, Result: 54

• // 4. Call-by-Need (Memoization):

App('fac, 4) App('fac, 3) App('fac, 2) App('fac, 1) App('fac, 0)

5 Calls, Result: 54

[plo1234]

Code: Alles auswählen

Let('x, Num(3), 
       Add(
             Let('x, Num(1), Id('x)),
             Id('x) ))

Substitution should evaluate to 6 and env interp to 4.

Both evaluate to 4. Subsitution does not subst. in the "body" if it encounters a new Let with the same identifier.

Regarding 10.2: Don't the different evaluation strategies only affect the way function parameters are evaluated? So those different strategies dont affect wheter Div(7, 0) is evaluated at defintion or not?! We would need to know whether the interpreter is eager or lazy.

So, I would say call-by-name and call-by-value are the same in this example: both call fac 14 times and yield 54.
I don't really know what the differences between the two call-by-need strategies are (does it have something to do with the scope of the cache?). So I will just go with the "simple" call-by-need definition from the lecture. And then I would even say, that the result is also the same for call-by-need: result=54 with 14 calls to fac. Because:
So we have something like this:

Code: Alles auswählen

  ...
  Add(App('fac, 4), Add(App('fac, 4), App('fac, 3)))

First we evaluate the inner Add. both fac(4) and fac(3) have to be called .Then Add adds up and returns. Now we evaluate Add(App('fac, 4), 30) but the cache of the previous Add is lost at this point. So fac(4) has to called again. I am quite sure that I am missing something here, but to me it seems the slides explain things my way...

Can anyone tell me where is the difference between the call-by-need strategies explained?

[biz]

Regarding 10.2

Call-By-Value
See V4.pdf page 51: Standard form of eager evaluation called "call-by-value".
If I'm not mistaken it is implemented in SCFWAEInterp.scala. The With/Let uses:

case With(boundId, namedExpr, boundBody) => {
val (namedVal, s1) = interp(namedExpr, env, store)
val newLoc = nextLocation
interp(boundBody, env + (boundId -> newLoc), s1 + (newLoc -> namedVal))
}

which interps the namedExpr first and should break after trying to evaluate Let('x, Div(7,0), ....).

Call-By-Name
uses Lazy evaluation as specified by V9.pdf, aswell as Call-By-Need. Call-By-Name re-evalutes each Let/With, so it has 14 Calls.

Call-By-Need
uses Expression Result Caching which stores the result of the namedExpr from the Let/With in the variable / boundId. So 'y is assined to 24. The Add is evaluated to Add(24, Add(24, App('fun, 3))). The App('fun,3) is called and results in 6. Afterwards Add evalutes.

Call-By-Need
the Memoization strategy caches the result of each function call in the memory and looks them up. After it calls App('fac, 4) once it has saved App('fac, 4) to App('fac, 0) and doesnt need anymore calls. (There strategys are not mentioned in the lecture, they explained them in the excercise)

[plo1234]

Ah, I see. I should have looked into the interpreters earlier.. Thanks!

[Mr.B]

Does someone have the solution for ex6 Task 2?

Is it correct that just the Boxes "Box(x3),Box(x2),Box(x1),Box(10)" are freed during the whole process?
For my understanding all other boxes remain on the heap because they are still referenced by some variables on the stack?

Best
Mr.B

[plo1234]

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)

## 1. Non-moving GC

Env             Store
----+-----      ----+---------
 x1 | 1           1 | Num(10)
 x2 | 2           2 | Box(1)
 x3 | 3           3 | Box(2)
      |               |
      |               |
      |               |
      |               |
res | 8           8 | Box(3)

## 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)

Generally, it can be necessary to update references with a moving-GC, but not
in this example.

## 3. Copying GC

So I guess we should assume that everything we have allocated to far fits in the heap?

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)
----+-----      ----+---------
      |               |
      |               |
      |               |
      |               |
      |               |
      |               |
      |               |
      |               |

After GC:
Env             Store
----+-----      ----+---------
      |               |
      |               |
      |               |
      |               |
      |               |
      |               |
      |               |
      |               |
----+-----      ----+---------
 x1 | 8           8 | Num(10)
 x2 | 9           9 | Box(8)
 x3 | 10         10 | Box(9)
res | 11         11 | Box(10)
      |               |
      |               |
      |               |
      |               |

[plo1234]

Hi,

# Exercise 03

## Task 1: Immediate substitution vs deferred substitution

For the language F1WAE, we introduced environments as an alternative for
substitutions.

### 1. Why did we do this?

Increase efficiency: we don't have to traverse the whole program
(especially unvisited branches) for substitution before actually
interpreting.

Could anyone comment on this? Was that really the reason?
The only "technical" shortcoming I see in substitution is that you cannot implement state with it. But we didnt do that at that point. We were only implementing functions...

[r1chard]

I think the main reason where the Closure in the FWAE interpreter. We have a FWAE Interpreter with Substitution, but it is easier with enviroments.
In addition the Closure closes the function and the environment, which is not possible without an enviroment =).
Therefore we can not return Closures without the enviroment.

We got the ability of the state by the store and not by the environment.

[Mr.B]

I think the main reason where the Closure in the FWAE interpreter. We have a FWAE Interpreter with Substitution, but it is easier with enviroments.
In addition the Closure closes the function and the environment, which is not possible without an enviroment =).
Therefore we can not return Closures without the enviroment.

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?

Apart of this, I belive plo1234's reasoning is right. The main point for not using substituation is computational overhead:

Though we have a working definition of functions, you may feel a slight unease about it. When the interpreter sees an identifier, you might have had a sense that it needs to “look it up”. Not only did it not look up anything, we defined its behavior to be an error! While absolutely correct, this is also a little surprising. More importantly, we write interpreters to understand and explain languages, and this implementation might strike you as not doing that, because it doesn’t match our intuition.

There’s another difficulty with using substitution, which is the number of times we traverse the source program. It would be nice to have to traverse only those parts of the program that are actually evaluated, and then, only when necessary. But substitution traverses everything—unvisited branches of conditionals, for instance—and forces the program to be traversed once for substitution and once again for interpretation.

source: http://cs.brown.edu/courses/cs173/2012/ ... ments.html

[plo1234]

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)?

[Mr.B]

@plo1234 Thx for your solution for ex06.2.

So it's obviously exactly the other way round than I first thought. Thx for that clarification
I have some questions though.

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?

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?
Like this:

Code: Alles auswählen

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

I'm not sure if this where small mistakes by you or if I just don't get it. Could you pls clarify this

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]