## Assignment 9: BindCC Usage

MrGumby
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

### Assignment 9: BindCC Usage

Hi,

I don't understand how BindCC should work.

Maybe on the example of test10, can somebody explain how this is evaluated?

Code: Alles auswählen

runInterp(And(true, BindCC('k, Or(true, App('k, false)))))

It is said, that we should bind the body (Or(true, App('k, false))) to the param ('k). Recursive binding makes no sense, since it wouldn't terminate. And since we have no lazy evaluation k will surely be looked up (although it is not needed).

I just don't see how this could evaluate correctly.

0b101101101
Endlosschleifenbastler
Beiträge: 179
Registriert: 15. Apr 2015 18:24

### Re: Assignment 9: BindCC Usage

I thought about recursion at first, too! But then i noticed, continuations are not about going further inside, but about the outside

Take a look at the group exercise solution for bindcc and continuations:
https://repository.st.informatik.tu-dar ... FLAE.scala

prabhjot
Erstie
Beiträge: 11
Registriert: 5. Aug 2016 16:30

### Re: Assignment 9: BindCC Usage

I also have similar problem with understanding BindCC.

What I thought was that param - 'k will be bound to the continuation so far till BindCC in interpreted which will be
And(true, _)

But with this assumption, test10 should evaluate to :
Or(true, App('k, false))
Or(true, And(true, false))
Or(true, false)
BoolV(true)

But this is not the case .. so I'm confused

MrGumby
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

### Re: Assignment 9: BindCC Usage

Yeah, thank you!

Ok, then can you explain why test10 and test16 should return what the tests say that they return?

'Cause for 10 I would assume

Code: Alles auswählen

And(true, BindCC('k, Or(true, App('k, false))))  =>
And(true, Or(true, App('k, false))) =>
And(true, Or(true, false)) =>
And(true, true)  =>
true  != false

And for 16

Code: Alles auswählen

And(true, BindCC('k, Let('f, Fun('v, And('v, App('k, true))), App('f, false)))) =>
And(true, BindCC('k, App(Fun('v, And('v, App('k, true))), false))) =>
And(true, And(false, App('k, true))) =>
And(true, And(false, true)) = >
And(true, false) =>
false != true


Where did I go wrong? All other tests work fine now.

Ragnar
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

### Re: Assignment 9: BindCC Usage

As the name suggests, BindCC binds the current continuation, where the current continuation is “the rest of the program, after the call to BindCC”. And this continuation will be stored inside of k.
The evaluation MrGumby shows just ignores the call to App('k, …), but really it should now execute the continuation and run “the rest of the program, after the call to BindCC”.

It is a feature which can be used to implement all sorts of control flow abstractions, like exceptions, gotos, or async calls.
So you can not really think locally when applying continuations. And yes, that tends to be a tricky thing to do

Maybe as a first step let me pose this question: What is the “current continuation” after the call to BindCC in the test? Hint: It is not the body (not the Or(…)). So what else remains?

Code: Alles auswählen

And(true, BindCC('k, Or(true, App('k, false))))

prabhjot
Erstie
Beiträge: 11
Registriert: 5. Aug 2016 16:30

### Re: Assignment 9: BindCC Usage

Hi Ragnar,
So, even according to your explanation it seems my assumption is right that in case of test10 current continuation will be v => And(true, v)

But since we are following left to right evaluation of arguments, in the operation - Or(true, rhs), rhs expression should not be evaluated at all.. isn't it ?

So in that case it should be actually correct to ignore the call to App('k, )in test10.

It is actually the same case in test16, the evaluation generally simplifies to And(false, App('k, _ ))
Where again the rhs expression should not be evaluated.

0b101101101
Endlosschleifenbastler
Beiträge: 179
Registriert: 15. Apr 2015 18:24

### Re: Assignment 9: BindCC Usage

Hm, my reaction to failing test10 and 16 was to drop short-circuit evaluation for 'and' and 'or' and evaluate all arguments regardless of need.

MrGumby
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

### Re: Assignment 9: BindCC Usage

That (dropping short-circuit evaluation) works for me too.

Ragnar
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

### Re: Assignment 9: BindCC Usage

ah! That is true. The tests of this task do assume that there is no short circuiting.

labataschö
Windoof-User
Beiträge: 37
Registriert: 15. Apr 2015 16:43

### Re: Assignment 9: BindCC Usage

Yes, without short-circuiting it seems to work.
But in fact, I have no idea why. Could you explain that in detail after the deadline, please? At the moment I'm not able to understand my own solution

Ragnar
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

### Re: Assignment 9: BindCC Usage

The problem is if you have short circuiting in the test then the continuation is never applied

Code: Alles auswählen

 And(true, BindCC('k, Or(true, App('k, false))))
=> the inner Or will just evaluate to without looking at the App =>
And(true, BindCC('k, true)) 
without short circuiting however, to evaluate the or, the App has to be evaluated first,
which will result in the program “jumping” to the position where the continuation was bound.
(Feel free to share a correct execution trace of the test even before the deadline, I just do not want to spoil everything for you )

labataschö
Windoof-User
Beiträge: 37
Registriert: 15. Apr 2015 16:43

### Re: Assignment 9: BindCC Usage

Hmmm, so did I get this right?
The result of a BindCC is just the evaluated body of the BindCC. The BindCC will additionally just bind the current continuation. So that it can not only be called when you're at the tail call of the recursion but also as many times as you want at any other position (on the condition that the position is in the scope of the BindCC). It is just a very crazy thing to do with continuations regarding that they usually only define how the result of a call must be processed further.

Ragnar
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

### Re: Assignment 9: BindCC Usage

The first part sounds about right.
BindCC does nothing except binding the current continuation to a name. Because the interpreter is written using CPS it is very easy to get the current continuation (that is also why we implement the interpreter using CPS, so we can easily implement a language with BindCC). If one does not use the bound continuation, then BindCC will behave the same as just evaluating the body (you should be able to see that easily from the code of the interpreter in the lecture).

In the second part you confuse the interpreter and the interpreted language.
The interpreted language can call a continuation wherever it pleases and also possibly multiple times. However, this does not change the fact that the interpreter only calls the continuation in tail position. What the interpreter does is ignore the current continuation when calling the bound continuation, and this causes a “jump” in the execution order of the program.

And yes, I agree that continuations are a bit crazy .