Process man­age­ment with a queue

Created: Fri Nov 30 17:34:21 CET 2018

Last mod­i­fied: Wed Dec 26 08:49:29 CET 2018


This might be use­ful when do­ing ex­er­cises of sec­tion 3.3 in TSPL3.

Here is queue.scm

(define (make-queue)
    (cons '() '()))

(define (putq! q v)
  (let ((end (cons v '())))
    (begin
      (if (null? (car q))
          (set-car! q end)
          (set-cdr! (cdr q) end))
      (set-cdr! q end))))

(define (getq q)
  (caar q))

(define (delq! q)
  (begin
    (set-car! q (cdar q))
    (and (null? (car q))
         (set-cdr! q '()))))

(define (emptyq? q)
  (null? (car q)))

Now lwp.scm

(define call/cc call-with-current-continuation)

(load "queue.scm")

(define lwp-list (make-queue))

(define (lwp thunk)
  (putq! lwp-list thunk))

(define (kill-k x)
    #f)

(define (next)
  (let ((p (getq lwp-list)))
    (delq! lwp-list)
    (p)))

(define (start)
  (call/cc
   (lambda (k)
     (begin
       (set! kill-k k)
       (next)))))

(define (pause)
  (call/cc
   (lambda (k)
     (lwp (lambda ()
            (k #f)))
     (next))))

(define (quit)
  (if (emptyq? lwp-list)
      (kill-k 'ended)
      (next)))

(lwp (lambda ()
       (let f ()
         (begin
           (pause)
           (display 'i-am-process-1)
           (newline)
           (kf)))))

(lwp (lambda ()
       (let f ()
         (begin
           (pause)
           (display 'i-am-process-2)
           (newline)
           (kf)))))

(start)

The process I had trou­ble pic­tur­ing is de­scribed be­low.

Basically, (start), (next), (quit) and (pause) are to be used in very specific ways:

Let’s first com­pare quit and pause. We see that both of them are call­ing next at some point. (Except that quit just kills the whole process man­ager in case there is no more process to (next) to. By strip­ping down this edge case of quit, we get (define quit next) as an al­most valid de­f­i­n­i­tion.

It ap­pears that pause is like an im­proved quit. When called, it will store a lambda at the be­gin­ning of the queue (with a view to process it last). Before call­ing next, which will call the pro­ce­dure stored at the end of the queue.

start is a bit like pause; ex­cept that the con­tin­u­a­tion we are in­ter­ested in is stored in a global vari­able. Also, start is as­sumed to be called at the end of our pro­gram, so call­ing this con­tin­u­a­tion al­lows to force quit the process man­ager.

When call­ing pause in­side of a process that con­tains a loop, we add a continuation at the end of the queue; in­deed, the same process, but start­ing from right af­ter (pause).

We then (next) to our sec­ond process. Again, we (pause) and save a continuation be­fore we (next). Wait, we only had two processes here! And they’ve been re­moved from the queue by nexts delq! What is it ex­actly that remains in our queue ?

Remain two con­tin­u­a­tions. We ex­pect them to be processed in the same or­der they were cre­ated, be­cause a queue is a first-in first-out data struc­ture.

The first con­tin­u­a­tion is equiv­a­lent to our first process, start­ing af­ter the pause, mean­ing that from now on, the process will ac­tu­ally do its thing, which is dis­play­ing a num­ber be­fore paus­ing and stor­ing the same con­tin­u­a­tion in the queue.

We just got our first process to per­form its task for the first time. We have two processes: one to re­sume our sec­ond process where it left, which we are about to call since we just paused and the new con­tin­u­a­tion of the first process; which we’ll in­voke on the next pause.

source code