Assignment 9: BindCC Usage

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

Assignment 9: BindCC Usage

Beitrag von MrGumby » 17. Jan 2017 16:42

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
Endlosschleifenbastler
Beiträge: 179
Registriert: 15. Apr 2015 18:24

Re: Assignment 9: BindCC Usage

Beitrag von 0b101101101 » 17. Jan 2017 17:31

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

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

Re: Assignment 9: BindCC Usage

Beitrag von prabhjot » 17. Jan 2017 18:32

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
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

Re: Assignment 9: BindCC Usage

Beitrag von MrGumby » 17. Jan 2017 19:14

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
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

Re: Assignment 9: BindCC Usage

Beitrag von Ragnar » 17. Jan 2017 20:42

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

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

Re: Assignment 9: BindCC Usage

Beitrag von prabhjot » 18. Jan 2017 03:43

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
Endlosschleifenbastler
Beiträge: 179
Registriert: 15. Apr 2015 18:24

Re: Assignment 9: BindCC Usage

Beitrag von 0b101101101 » 18. Jan 2017 03:48

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
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

Re: Assignment 9: BindCC Usage

Beitrag von MrGumby » 18. Jan 2017 09:37

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

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

Re: Assignment 9: BindCC Usage

Beitrag von Ragnar » 18. Jan 2017 14:00

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

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

Re: Assignment 9: BindCC Usage

Beitrag von labataschö » 18. Jan 2017 14:08

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:

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

Re: Assignment 9: BindCC Usage

Beitrag von Ragnar » 18. Jan 2017 15:36

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

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

Re: Assignment 9: BindCC Usage

Beitrag von labataschö » 18. Jan 2017 23:35

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
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

Re: Assignment 9: BindCC Usage

Beitrag von Ragnar » 19. Jan 2017 10:16

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:.

Antworten

Zurück zu „Archiv“