exercise on continuations (from previous course)

[leadermaxone]

Hello, I was looking at an exercise presented in a previous course (here: https://github.com/gioenn/pl/blob/master/ex4.rkt)

it mimics a parallel computation with tasks, a queue and accessory coroutines like enqueue, dequeue, fork and yield.

code is as following

(define *queue* '())

(define (empty-queue?)
  (null? *queue*))

(define (enqueue x)
  (set! *queue* (append *queue* (list x))))

(define (dequeue)
  (let ((x (car *queue*)))
    (set! *queue* (cdr *queue*))
    x))

(define (fork proc)
  (call/cc (lambda(k)
             (enqueue k)
             (proc))))

(define (yield)
  (call/cc (lambda(k)
             (enqueue k)
             ((dequeue)))))

(define (c-exit)
  (if (empty-queue?)
      (exit)
      ((dequeue))))

(define ((do-stuff-n-print str max))
  (let loop ((n 0))
    (display str)
    (display " ")
    (display n)
    (newline)
    (yield)
    (if (< n max)
        (loop (+ 1 n))
        (c-exit))))

(define (main)
  (begin
    (fork (do-stuff-n-print "This is A" 3))
    (fork (do-stuff-n-print "This is B" 4))
    (displayln "End")
    (c-exit)))

running (main) will fork A and B and display "end".

this is the output:

This is A 0 
This is B 0
This is A 1
End
This is B 1
This is A 2
This is B 2
This is A 3
This is B 3
This is B 4

in my understanding each fork puts in the queue the continuation (at the point it is called) and then call the process being forked.

When fork A 3 is called , the continuation and therefore what is enqueued should be "fork B, display end".

Afterwards process "do stuff n print A 3" is called, it will print "A 0" and yield.

Yield enqueues the continuation (this time it will be the loop inside dostuffnprint) and executes the result of dequeue ( there are double parenthesis around dequeue in yield).

The result of dequeue is the fist of the queue "fork B, display end, loop A=0" -> fork B. The fork will enqueue the continuation (which should be display END ?) and executes dostuffnprint B 4. "B 0" will be printed and yield called which will enqueue the loop in B.

At this point the queue should be "display end, loop A=0, (display end?), loop B=0" and in my understanding "display end" should be called; WHICH DOESN'T HAPPEN because another round of loop in A -> A 1 is called before printing end and continuing with alternating the two "processes", without calling end again even it is part of the continuation of fork A and of the continuation of fork B.

so what i don't understand is:

• why there is another round of A 1 instead of calling immediately display end after A 0 and B 0
• why display end is not called twice

i'm sure it is something silly i can't grasp, but i figured to ask it here and not privately to share the knowledge.

Thanks, Massimo.

[fcremo]

Hi, it took me a while to understand what's going on so I'll post what I understood hoping I'm right.

I think end is not displayed right after A0 and B0 because yield also enqueues its continuation, so when it is called by A0 the (if (< n max) ...) continuation is enqueued after the (do-stuff-n-print of B0).

[leadermaxone]

Hi and thank you for helping!

I agree that yield enqueues its continuation, thus when it's called by A0 it enqueues the continuation consisting of (if(< n max) which i originally called loop A = 0 in the first post.

But, in my opinion, since fork enqueues its continuation as well, "fork A" enqueues "fork B" and "display end" BEFORE process A is executed; meaning that when A will yield, the queue will be "fork B, display end" and "loop A = 0" will be appended at the end of it resulting in "fork B, display end, loop A=0".

Or maybe i didn't understand what you are trying to tell me.

[fcremo]

Fork A enqueues just a continuation that leads to fork B, not two continuations "fork B" and "display end" Have you tried to follow what the program is doing by drawing the queue on paper?

[leadermaxone]

yes, i even written in the first post what i think the queue is at every iteration. This is interesting, i thought that by "continuation" we mean "whatever is next" , and not just "the next procedure". Thats why by continuation of fork A i intend all the subsequent procedures, such as fork B and display. But maybe i understood it wrong

[osioalberto]

Let's try to follow the execution step by step (almost)

0. First of all, remember that do-something-n-print is a thunk (i.e. a lambda function!)

1. Let's start by executing

   (fork (do-stuff-n-print "This is A" 3))

   The evaluation of (do-stuff ...) produces a lambda function, which is then passed to fork

2. Forks puts the current continuation (that is, as someone said, "whatever there is next", in this case (fork (do-stuff-n-print "This is B" 4)) [let's call it CC1]) in the queue, and then evaluates the procedure passed in as proc. The state of the queue right now is (CC1)

3. The evaulation of proc caueses the line This is A 0 to be printed. After print, yield is invoked. This implies that the current continuation (the call to if (< n max) [call it CC_A1]) is enqueued (state of the queue (CC1 | CCA1)) and the first continuation from the queue is dequeued and evaluated (state of the queue (CCA1)).

4. The evaluation of the continuation extracted from the queue leads to the call of (fork (do-stuff-n-print "This is B" 4)). As of point 3, current continuation (in this case displayln "End" [CCE]) is enqueued, the evaulation of proc prints out "This is B 0" and by invoking yield the current continuation (if (< n max), call it CCB1) is enqueued. Current state of the queue is (CCA1 | CCE | CCB1)). Then first continuation in the queue is taken back, so we restart from where we left with CCA1.

5. Next instruction is the if (< n max), then there is the jump back of the loop and "This is A 1" is printed out. Again, the yield enqueues current continuation (as before, it enqueues a reference to if (< n max) [CCA2]) and dequeues CCE. Current queue is (CCB1 | CCA2).

6. CCE is evaluated, this prints out "End" and calls (c-exit).The c-exit dequeues the first continuation in queue, that is CCB1.

7. Like point 6, here we print out "This is B 1", we enqueue current continuation (CCB2) and dequeue first element in queue (CCA2). Current queue is (CCB2).

8. We can go on like this until we print out "This is B 3". Just before the invocation of the yield the state of the queue is (CCA4). Now the yield" enqueues CCB4 and dequeues CCA4. Since the max for A is 3, theifinstead of printing out "This is A 4" goes into thec-exit```, which simply extracts first element from the queue (that is CCB4)

9. Finally, we print out "This is B 4", we reach again the yield and we enqueue CCB5. Like before, yield takes out the first (and only) element from the queue (that is CCB5), reaches a c-exit that finds the queue empty and the program ends.

Hope this clarifies any doubt

[leadermaxone]

What bothered me in the first place was that the continuation of (fork A) should be "whatever is next" meaning both (fork B) AND (display end). After discussing with a friend after class we agreed that:

• the continuation is indeed everything after forkA (if you think at it as a saved Program Counter) it is indeed correct to say that the continuation are all the next instructions (and imprecise to say just the next one)
• i was thinking atomically, and thus i put in the queue each and every subsequent instruction in the continuation of (fork A). this led me to think i should have called display end right after forking B . But this is WRONG because (fork B) and (display end) are part of the SAME continuation of fork A (called CC1 in the previous example) meaning that they will occupy just one spot in the queue as a continuation entity and after resuming it and forking B we jump back once again, discarding the rest of the continuation .

That was what i misunderstood.

TL;DR: continuation is a BLOCK of instructions, not just the next one. But as such, it is a block occupying just one spot in the queue and not as many as the instructions in it.

[riccardotommasini]

Good job, it seems you're figuring it out. Just a little correction to the final point of @leadermaxone. The continuation point the next instruction. When the computation restarts from that point, it goes on procedurally on the instructions that follow the one point by the continuation.

Indeed:

(define cont #f)

(displayln "Before1")

(define (during)
  (begin
    (displayln "Before3")
(call/cc (lambda (k)

           (set! cont k) ))
           (displayln "Before4")))

(during)

(displayln "After1")
(displayln "After2")
(displayln "After3")

Before1 Before3 Before4 After1 After2 After3

(cont)

Before4