Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #26332 > unrolled thread

Co-routines a la Knuth

Back to article view | Back to comp.lang.forth

Contents

  Co-routines a la Knuth mhx@iae.nl - 2013-10-05 11:50 -0700
    Re: Co-routines a la Knuth Paul Rubin <no.email@nospam.invalid> - 2013-10-05 14:15 -0700
      Re: Co-routines a la Knuth mhx@iae.nl - 2013-10-06 03:22 -0700
        Re: Co-routines a la Knuth mhx@iae.nl - 2013-10-06 09:58 -0700
    Re: Co-routines a la Knuth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-07 12:33 +0000
      Re: Co-routines a la Knuth m.a.m.hendrix@tue.nl - 2013-10-07 07:17 -0700
        Re: Co-routines a la Knuth mhx@iae.nl - 2013-10-07 13:43 -0700
          Re: Co-routines a la Knuth "Elizabeth D. Rather" <erather@forth.com> - 2013-10-07 12:58 -1000
            Re: Co-routines a la Knuth mhx@iae.nl - 2013-10-08 23:58 -0700
              Re: Co-routines a la Knuth "Elizabeth D. Rather" <erather@forth.com> - 2013-10-08 21:08 -1000
        Re: Co-routines a la Knuth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-08 15:05 +0000
          Re: Co-routines a la Knuth mhx@iae.nl - 2013-10-09 13:23 -0700

#26332 — Co-routines a la Knuth

Donald E. Knuth's Chapter 1.4.2 in 'Fundamental Algorithms' 2nd Ed., 
has interesting, but unconvincing, things to say about coroutines. 

I found a co-routine implementation that doesn't use the R-stack 
at all and only needs a single variable. (It is a special case.)

The code is specific for a subroutine-threaded / optimizing Forth.
It took a lot of time to get this right. The source is far 
from obvious, even when excluding CO itself. I don't think this
will be a hit.

Prof. Knuth has one convincing example for co-routines: They may
make it unnecessary to save a temporary copy. For filters
with complex output requirements the intermediate phase output 
might be larger than available memory. 

-marcel

-- ------------------------------------------------------------------
DOC
(*
  Task:
  Translate one code in another.
  Input code is a sequence of alphameric characters terminated by a 
  period, e.g.,
     
     A2B5E3426FGOZYW3210PQ69R.	  (1)

  Blanks are ignored. Input is understood as follows, left to right:
  If the next character is a digit (i.e., 0, 1, ..,9), say n, it 
  indicates (n+1) repetitions of the following character, whether 
  the following character is a  digit or not. A nondigit simply 
  denotes itself. The output of the program is to consist of a 
  sequence indicated in this manner and separated into groups of 
  three characters each (where the last group may have less than 
  three characters). For example, (1) should be translated by our 
  program into

  ABB  BEE  EEE  E44  446  66F  GZY  W22  220  OPQ  999  999  999  R.

  The output consists of a maximum of 16 groups per line.
*)
ENDDOC

-- Co-routines & Stuff --------------------------------

VARIABLE remember  
0 VALUE #out	

: ?CR	#out #80 >= IF  CR  CLEAR #out  ENDIF ; 

: CO  	-OPT ]] remember @ [[
	$12345678 POSTPONE LITERAL ]] remember ! [[  HERE 4 - >R
	-OPT $5B C, $FF C, $E3 C, ( jmpI, ) HERE R> 32B! ; IMMEDIATE 

-- ----------------------------------------------------

0 VALUE ^input	
0 VALUE #input	
CREATE input 	  ,"   A2B5E3426  FG0ZYW3210PQ89R  ."


0 [IF] -- straightforward approach


: INIT ( -- ) input C@+ TO #input TO ^input  #80 TO #out ;  

-- Fetch next nonblank character.
-- Should only return valid chars. 
: GETCHAR ( -- char ok? ) 
	BEGIN  ^input C@  1 +TO ^input	
	       DUP BL = 
	WHILE  DROP  
	REPEAT DUP '.' <> ; 

-- Assume that line-length is multiple of 5 chars.
: ~EMIT~ ( char -- )
	?CR
	#out 5 MOD 3 = IF  2 SPACES 2 +TO #out  ENDIF  
	EMIT  1 +TO #out  ; 

-- Assume that all codes are valid, i.e. "3." doesn't happen.
: .CODE ( char -- ) 
	DUP  'A' 'Z' 1+  WITHIN IF  ~EMIT~ EXIT  ENDIF
	'0' - 1+ GETCHAR DROP >S 0 ?DO  S ~EMIT~  LOOP -S ; 

: TEST	INIT  BEGIN  GETCHAR WHILE  .CODE  REPEAT  ?CR EMIT ;

[ELSE] -- Knuth's approach

0 VALUE mychar    

-- Should only return valid chars (never 0)
: GETCHAR ( -- ) 
	BEGIN  ^input C@  1 +TO ^input	
	       DUP BL = 
	WHILE  DROP  
	REPEAT TO mychar ; 

: OUTS ( -- )
	BEGIN 
	   ?CR	
	   CO  mychar '.' <> WHILE mychar EMIT 
	   CO  mychar '.' <> WHILE mychar EMIT 
	   CO  mychar '.' <> WHILE mychar EMIT 
	   2 SPACES 5 TO #out
	REPEATED ; 

: INS ( -- )
	BEGIN  GETCHAR  mychar '.' <>
	WHILE  mychar 'A' 'Z' 1+  WITHIN 
		  IF  CO  
	        ELSE  mychar '0' - 1+  GETCHAR  0 ?DO  CO  LOOP 
	       ENDIF
	REPEAT '.' EMIT  
	R> DROP ; \ You're not supposed to understand this

: TEST ( -- ) 
	input CHAR+ TO ^input  
	#80 TO #out  
	['] INS remember !  
	0 OUTS ; 

[THEN]

: .HELP	CR ." Contrived example from D.E. Knuth's 'Fundamental 
	CR ."   Algorithms,' Chapter 1.4.2, Coroutines, 2nd Ed." 
	CR ." Try: TEST " 
	CR ." Result should be: "
	CR ." ABB  BEE  EEE  E44  446  66F  GZY  W22  220  0PQ  "
	   ." 999  999  999  R." ;

  .HELP

[toc] | [next] | [standalone]

#26333

mhx@iae.nl writes:
> I found a co-routine implementation that doesn't use the R-stack 
> at all and only needs a single variable. (It is a special case.)

The GA144 has a machine instruction for that.  It just swaps R (the top
of the return stack) with the program counter.

> Prof. Knuth has one convincing example for co-routines: They may
> make it unnecessary to save a temporary copy. 

A traditinal example is getting rid of the control inversion that it
takes to process a i/o stream using ordinary subroutine calls, while
keeping the i/o separate from the processing code:

  http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

[toc] | [prev] | [next] | [standalone]

#26334

On Saturday, October 5, 2013 11:15:02 PM UTC+2, Paul Rubin wrote:
> mhx@iae.nl writes:
>
> > I found a co-routine implementation that doesn't use the R-stack
> > at all and only needs a single variable. (It is a special case.)
>
> The GA144 has a machine instruction for that.  It just swaps R (the 
> top of the return stack) with the program counter.

Well, that needlessly limits use of the R-stack.
The word CO does *not* use the R-stack, actually you can see that 
the R-stack mechanism is a nuisance (start: in the below update). 

I think CO is best described as a restricted GOTO, where the 
restriction comes from the fact that (in my implementation) only 
two specified words are involved. It is possible to see to and 
from which word CO goes, respectively comes from. In more 
complicated examples with more than two COR's and maybe multiple
entries of the same COR, it might be necessary to use a 
double-linked list (or a cyclic stack).

[..]
> A traditinal example is getting rid of the control inversion that it
> takes to process a i/o stream using ordinary subroutine calls, while
> keeping the i/o separate from the processing code:
>   http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

Very good, instructive, and amusing. However, I don't think that
that C code supports multiple exits and entries to each of the
linked routines.

-marcel

-- updated code ------------------------
(*
 * LANGUAGE    : ANS Forth with extensions
 * PROJECT     : Forth Environments
 * DESCRIPTION : From Donald E. Knuth's Chapter 1.4.2 in 'Fundamental 
               :  Algorithms' 2nd Ed. 
 * CATEGORY    : Contrived Coroutine example
 * AUTHOR      : Marcel Hendrix 
 * LAST CHANGE : October 5, 2013, Marcel Hendrix 
 *)


	NEEDS -miscutil

	REVISION -coroutines "--- Coroutine example   Version 0.02 ---"

	PRIVATES

DOC
(*
  Task:
  Translate one code in another.
  Input code is a sequence of alphameric characters terminated by a 
  period, e.g.,
     
     A2B5E3426FGOZYW3210PQ69R.	  (1)

  Blanks are ignored. Input is understood as follows, left to right:
  If the next character is a digit (i.e., 0, 1, ..,9), say n, it 
  indicates (n+1) repetitions of the following character, whether 
  the following character is a  digit or not. A nondigit simply 
  denotes itself. The output of the program is to consist of a 
  sequence indicated in this manner and separated into groups of 
  three characters each (where the last group may have less than 
  three characters). For example, (1) should be translated by our 
  program into

  ABB  BEE  EEE  E44  446  66F  GZY  W22  220  OPQ  999  999  999  R.

  The output consists of a maximum of 16 groups per line.

  See also: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html .
*)
ENDDOC

-- Co-routines & Stuff --------------------------------

0 VALUE #out	PRIVATE

: ?CR	#out #80 >= IF  CR  CLEAR #out  ENDIF ; PRIVATE

VARIABLE remember  PRIVATE
0 VALUE start

: start: 	HERE TO start ; IMMEDIATE
: start		start remember ! ;

: CO  	-OPT ]] remember @ [[
	$12345678 POSTPONE LITERAL ]] remember ! [[  HERE 4 - >R
	-OPT $5B C, $FF C, $E3 C, ( jmpI, ) HERE R> 32B! ; IMMEDIATE 

-- ----------------------------------------------------

0 VALUE ^input	PRIVATE
0 VALUE #input	PRIVATE
CREATE input 	PRIVATE  ,"   A2B5E3426  FG0ZYW3210PQ89R  ."


0 [IF] -- straightforward approach


: INIT ( -- ) input C@+ TO #input TO ^input  #80 TO #out ; PRIVATE 

-- Fetch next nonblank character.
-- Should only return valid chars. 
: GETCHAR ( -- char ok? ) 
	BEGIN  ^input C@  1 +TO ^input	
	       DUP BL = 
	WHILE  DROP  
	REPEAT DUP '.' <> ; PRIVATE

-- Assume that line-length is multiple of 5 chars.
: ~EMIT~ ( char -- )
	?CR
	#out 5 MOD 3 = IF  2 SPACES 2 +TO #out  ENDIF  
	EMIT  1 +TO #out  ; PRIVATE

-- Assume that all codes are valid, i.e. "3." doesn't happen.
: .CODE ( char -- ) 
	DUP  'A' 'Z' 1+  WITHIN IF  ~EMIT~ EXIT  ENDIF
	'0' - 1+ GETCHAR DROP >S 0 ?DO  S ~EMIT~  LOOP -S ; PRIVATE

: TEST	INIT  BEGIN  GETCHAR WHILE  .CODE  REPEAT  ?CR EMIT ;

[ELSE] -- Knuth's approach

0 VALUE mychar    PRIVATE

-- Should only return valid chars (never 0)
: GETCHAR ( -- ) 
	BEGIN  ^input C@  1 +TO ^input	
	       DUP BL = 
	WHILE  DROP  
	REPEAT TO mychar ; PRIVATE

: OUTS ( -- )
	BEGIN 
	   ?CR	
	   CO  mychar '.' <> WHILE mychar EMIT 
	   CO  mychar '.' <> WHILE mychar EMIT 
	   CO  mychar '.' <> WHILE mychar EMIT 
	   2 SPACES 5 TO #out
	REPEATED ; PRIVATE

: INS ( -- )
start:	BEGIN  GETCHAR  mychar '.' <>
	WHILE  mychar 'A' 'Z' 1+  WITHIN 
		  IF  CO  
	        ELSE  mychar '0' - 1+  GETCHAR  0 ?DO  CO  LOOP 
	       ENDIF
	REPEAT '.' EMIT ; PRIVATE

: TEST ( -- ) 
	input CHAR+ TO ^input  
	#80 TO #out  
	start OUTS ; 

[THEN]

:ABOUT	CR ." Contrived example from D.E. Knuth's 'Fundamental 
	CR ."   Algorithms,' Chapter 1.4.2, Coroutines, 2nd Ed." 
	CR ." Try: TEST " 
	CR ." Result should be: "
	CR ." ABB  BEE  EEE  E44  446  66F  GZY  W22  220  0PQ  "
	   ." 999  999  999  R." ;

		.ABOUT -coroutines CR
		DEPRIVE

                              (* End of Source *)

[toc] | [prev] | [next] | [standalone]

#26336

On Sunday, October 6, 2013 12:22:46 PM UTC+2, m...@iae.nl wrote:
[..]

This works too ( shows that the rack, data stack, and locals 
neatly fit in ).

-marcel

-- ------------------------------------------------
: PRINTER ( -- )
	BEGIN 
	   CR	
	   CO  DUP '.' <> WHILE  EMIT 
	   CO  DUP '.' <> WHILE  EMIT 
	   CO  DUP '.' <> WHILE  EMIT 
	   2 SPACES ':' EMIT
	REPEATED  
	EMIT ;

: GENERATOR ( -- ) 
start:	'0' 2- LOCAL nul  
	 2  #10 0 DO  nul I + OVER + CO  LOOP  DROP 
	 '.' CO ; 

: TEST ( -- ) starting PRINTER ; 

FORTH> test
012  :
345  :
678  :
9. ok

[toc] | [prev] | [next] | [standalone]

#26343

mhx@iae.nl writes:
>Donald E. Knuth's Chapter 1.4.2 in 'Fundamental Algorithms' 2nd Ed., 
>has interesting, but unconvincing, things to say about coroutines. 
>
>I found a co-routine implementation that doesn't use the R-stack 
>at all and only needs a single variable. (It is a special case.)

That may be enough for Knuth's example, but general coroutines should
have their own stacks.  As Knuth himself writes:

|The usefulness of the couroutine idea emerges when both A and B are
|complicated and each one calls the other one in numerous places.

E.g., you have data in a sort tree, and you want to output it in
filled lines (but without wrapping lines); A would walk the tree using
recursion, and B would be a doubly nested loop.  E.g., what if, in
your later example with a DO LOOP in the generator, you would also
like to have a DO LOOP in the printer?

IMO coroutines are a natural extension of the classical Forth
cooperative multi-tasking model.  Each coroutine has its own task, and
calling the other performs a task switch directly to the task of the
other coroutine (without the round-robin scheduler) and typically
moves some data or floating-point stack items from one task to the
other.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#26345

On Monday, October 7, 2013 2:33:49 PM UTC+2, Anton Ertl wrote:
> mhx@iae.nl writes: 
> >I found a co-routine implementation that doesn't use the R-stack 
> >at all and only needs a single variable. (It is a special case.) 
>
> That may be enough for Knuth's example, but general coroutines 
> should have their own stacks. 

Yes, in the general case I thought of swapping all stackpointers, not
only the instruction pointer, but I can indeed find an example where 
the stacks must be separate. That makes CO look like PAUSE (i.e. 
switching tasks). Interesting.

-marcel

[toc] | [prev] | [next] | [standalone]

#26349

On Monday, October 7, 2013 4:17:52 PM UTC+2, m.a.m....@tue.nl wrote:
[..]
> That makes CO look like PAUSE (i.e. 
> switching tasks). Interesting.

PAUSE indeed works.

-- -------------------

FORTH-PROCESS task1
FORTH-PROCESS task2

0 VALUE mychar

:NONAME ( -- )
	BEGIN 
	   CR
	   mychar '.' <> WHILE  mychar EMIT PAUSE
	   mychar '.' <> WHILE  mychar EMIT PAUSE
	   mychar '.' <> WHILE  mychar EMIT PAUSE
	   2 SPACES ':' EMIT
	REPEATED  
	mychar EMIT  STOP ; constant printer

:NONAME ( -- ) 
	 #10 0 DO  '0' I + TO mychar PAUSE  LOOP  DROP 
	 '.' TO mychar  STOP ; constant generator

: TEST ( -- ) 
	generator RUN task1
	printer   RUN task2 ; 

FORTH> test
012  :
345  :
678  :
9. 
FORTH>   ok

[toc] | [prev] | [next] | [standalone]

#26350

On 10/7/13 10:43 AM, mhx@iae.nl wrote:
> On Monday, October 7, 2013 4:17:52 PM UTC+2, m.a.m....@tue.nl wrote:
> [..]
>> That makes CO look like PAUSE (i.e.
>> switching tasks). Interesting.
>
> PAUSE indeed works.
>
> -- -------------------
>
> FORTH-PROCESS task1
> FORTH-PROCESS task2
>
> 0 VALUE mychar
>
> :NONAME ( -- )
> 	BEGIN
> 	   CR
> 	   mychar '.' <> WHILE  mychar EMIT PAUSE
> 	   mychar '.' <> WHILE  mychar EMIT PAUSE
> 	   mychar '.' <> WHILE  mychar EMIT PAUSE
> 	   2 SPACES ':' EMIT
> 	REPEATED
> 	mychar EMIT  STOP ; constant printer
>
> :NONAME ( -- )
> 	 #10 0 DO  '0' I + TO mychar PAUSE  LOOP  DROP
> 	 '.' TO mychar  STOP ; constant generator
>
> : TEST ( -- )
> 	generator RUN task1
> 	printer   RUN task2 ;
>
> FORTH> test
> 012  :
> 345  :
> 678  :
> 9.
> FORTH>   ok


On the systems I'm familiar with, EMIT would automatically PAUSE (as 
would any I/O operation). That's the key to an effective cooperative 
multitasker :-)

Cheers,
Elizabeth



-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#26360

On Tuesday, October 8, 2013 12:58:39 AM UTC+2, Elizabeth D. Rather wrote:
> On 10/7/13 10:43 AM, mhx@iae.nl wrote:
[..]
> On the systems I'm familiar with, EMIT would automatically PAUSE (as
> would any I/O operation). That's the key to an effective cooperative
> multitasker :-)

I wanted to try this on SwiftForth but it appears there's no round-robin loop 
of tasks anymore? When I start a task that does KEY, the job finishes without doing any input.

-marcel

[toc] | [prev] | [next] | [standalone]

#26362

On 10/8/13 8:58 PM, mhx@iae.nl wrote:
> On Tuesday, October 8, 2013 12:58:39 AM UTC+2, Elizabeth D. Rather wrote:
>> On 10/7/13 10:43 AM, mhx@iae.nl wrote:
> [..]
>> On the systems I'm familiar with, EMIT would automatically PAUSE (as
>> would any I/O operation). That's the key to an effective cooperative
>> multitasker :-)
>
> I wanted to try this on SwiftForth but it appears there's no round-robin loop
> of tasks anymore? When I start a task that does KEY, the job finishes without doing any input.

SwiftForth's multitasker has been modified to be compatible with Windows 
multitasking. I recommend that you consult Leon for assistance (I never 
really came up to speed with Windows, myself).

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#26354

m.a.m.hendrix@tue.nl writes:
>Yes, in the general case I thought of swapping all stackpointers, not
>only the instruction pointer, but I can indeed find an example where 
>the stacks must be separate. That makes CO look like PAUSE (i.e. 
>switching tasks). Interesting.

The two differences between a coroutine call and PAUSE are that

1) PAUSE switches to any ready task, a coroutine call to a specific
one (so I am not sure if CO is a good name; what if you want to have
more than two coroutines?).

2) In a coroutine call you may want to pass one or more data or FP
stack items to the other task.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#26370

On Tuesday, October 8, 2013 5:05:11 PM UTC+2, Anton Ertl wrote:
> m.a.m.hendrix@tue.nl writes:
[..]
> The two differences between a coroutine call and PAUSE are that
> 
> 1) PAUSE switches to any ready task, a coroutine call to a specific
> one (so I am not sure if CO is a good name; what if you want to have
> more than two coroutines?).
 
Yes, I experimented and instrumented some more and you are right.
Enabling PAUSE in all I/O words is a bad thing for co-routines,
I couldn't understand what went on anymore, let alone why.

I have chosen to enable a single PAUSE in KEY?, because iForth's
round-robin always contains the console. Therefore the CONSOLE 
must execute PAUSE to start (and keep) things running.

FORTH-PROCESSES execute in the order you start them (the CONSOLE
has obviously run already when you execute e.g. 
: TEST ( -- ) 
	@generator RUN GENERATOR
	@printer   RUN PRINTER ; 
Therefore the order of execution is is (begin) CONSOLE 
GENERATOR PRINTER (again). 

More than two co-routines is no problem, just create an extra
FORTH-PROCESS .

> 2) In a coroutine call you may want to pass one or more data or FP
> stack items to the other task.

Yes, but I am not going to tackle this one. Putting the data in
variables is perfectly OK because there is no pre-emption.

-marcel

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web