Seite 1 von 1

Assignment 9: BindCC Usage

Verfasst: 17. Jan 2017 16:42
von MrGumby
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.

Re: Assignment 9: BindCC Usage

Verfasst: 17. Jan 2017 17:31
von 0b101101101
I thought about recursion at first, too! But then i noticed, continuations are not about going further inside, but about the outside :D

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

Re: Assignment 9: BindCC Usage

Verfasst: 17. Jan 2017 18:32
von prabhjot
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 :?

Re: Assignment 9: BindCC Usage

Verfasst: 17. Jan 2017 19:14
von MrGumby
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.

Re: Assignment 9: BindCC Usage

Verfasst: 17. Jan 2017 20:42
von Ragnar
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? :wink:

Code: Alles auswählen

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

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 03:43
von prabhjot
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.

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 03:48
von 0b101101101
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.

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 09:37
von MrGumby
That (dropping short-circuit evaluation) works for me too.

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 14:00
von Ragnar
ah! That is true. The tests of this task do assume that there is no short circuiting.

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 14:08
von labataschö
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 :oops:

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 15:36
von Ragnar
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 :wink:)

Re: Assignment 9: BindCC Usage

Verfasst: 18. Jan 2017 23:35
von labataschö
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.

Re: Assignment 9: BindCC Usage

Verfasst: 19. Jan 2017 10:16
von Ragnar
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 :wink:.