Co_Routines Support for Oberon

http://www.zinnamturm.eu/downloadsAC.htm#Co_ http://sourceforge.net/projects/ta1/files/co2.0
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Josef Templ wrote:My understanding is that
he thinks that it will not be possible for his Co_ package to use the Kernel's coroutine services
but it should be possible. This has to be clarified.
I had a look at http://blackboxframework.org/unstable/i ... a1.816.zip
This Kernel version contains: InitStacks, AddStackInfo, SetStackBase, RemoveStackInfo, SwitchStackInfo and modified MarkLocals. It seems suitable for me (Of course, I made no specific tests). I can upgrade Co_ with the stable version of this Kernel.
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Directed coroutines exit point.
The directed coroutines entry point is Co.Transfer(g).
The directed coroutines entry point is Co.Yield.

What do you prefer, 1. Co.Transfer(g) - Co.Yield or 2. Co.Transfer(g) - Co.Tranfser(g.from)?
If answer 1 is not obvious, look at subroutine world:
What do you prefer, 1. CALL g - RETURN or 2. CALL g - GOTO gnext?

The Co.Transfer(g.from) is like GOTO, it introduces unpredictable program control flow.
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Directed routines entry point.

Unfortunately, removing Co.Transfer(g) is impossible without introducing new operators for coroutines support in Oberon.
Because Transfer is like subroutine call instruction, when all the work with local parameters we assign to compiler. The same was with Generators syntax in Perl, Lua languages.
Possible example with Coroutines compiler support.

Code: Select all

COROUTINE Gen(): INTEGER;
BEGIN
    YIELD 1;
    YIELD 2;
    YIELD 3;
END Gen;

PROCEDURE Run;
BEGIN
    Log.Int(Gen());Log.Ln; (* prints 1 *)
    Log.Int(Gen());Log.Ln; (* prints 2 *)
    Log.Int(Gen());Log.Ln; (* prints 3 *)
END Run;
I do not think to do or advertise extending Oberon syntax. The code above is just an example, which demonstrates fine code and local parameter usage instead of GOTO-like Transfer - Yield interfaces.
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Josef Templ wrote:Removing the 'Transfer' procedure looks quite radical to me.
I succeeded to use Yield instead of Transfer as an exit point.
Removing Transfer as an Entry point is impossible without extending the language (see above).
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Grep and Pipes example
The example is inherited from Donald King's book "Modern Principles for Effective Software Design". It uses Michael Jackson's methology from "Principles of Program Design".

The Commanders and console prints are below:

Commander !"Co_ObxMJackson.PipeInit('StartupBlackBox.vbs \Windows\setupact.log')" - initialize a pipe with 2 proposed files files
StartupBlackBox.vbs \Windows\setupact.log contents:
Commander !Co_ObxMJackson.More
' This is a vbs script to start BlackBox in server mode.
' Ensure that the value of prg is set correctly;
' the best way to achieve this is to create the script
' by invoking the menu command Help, Create Vbs in BlackBox.
'
---more---
Commander !Co_ObxMJackson.More
' Copy this file into any folder and double-click on it:
' BlackBox will start in server mode with that folder as the secondary one.
'----------------------------------------------------------
' Derived from a script by Bernhard Treutwein BdT(at)wildwein de
' This vertion by Fyodor Tkachov info21(at)inr ac ru 2008-12-19
---more---

In the example ReadBuffer and ReadString act as supplier/consumer. ReadBuffer fills it until BUFSIZE and yields control to ReadString. When ReadString is empty again, ReadBuffer suspends execution from the previous state.
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Same Fringe example

The problem setup is quoted from RichardGabriel's 1991 paper "The Design of Parallel Programming Languages" http://www.dreamsongs.com/10ideas.html:
"In 1977, in the pages of the ACM SIGART Newsletter, a debate raged over whether samefringe is the simplest problem that requires multiprocessing or CoRoutines to easily solve... The samefringe problem is this: two binary trees have the same fringe if they have exactly the same leaves reading from left to right."

Run: first compare two different trees with same fringe (a,b,c), then append 'd' to second. The solution yields from recursive call.

Commander !Co_ObxSameFringe.Problem
tree1(a,b,c) vs tree2(a,b,c): The Same Fringe is $TRUE
tree1(a,b,c) vs tree2(a,b,c,d) The Same Fringe is $FALSE
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

Anonymous Co_Routines & Cooperative Multitasking

Anonymous Co_Routines are designed to create multiple independent flows of control. Scheduler is needed for flow control. Scheduler selects each Co_Routine to switch to, according it's algorithm. It gains control to coroutine, but does not transmit data between packages.
Cooperative Multitasking is implemented with Co_Tasks, Co_Routines and Co_SchedTasks modules.

If was a paper http://cyberleninka.ru/article/n/ne-tolko-potoki(in russian) "Not Only Threads", dealing with scheduler architecture & implementation details.

Here it is necessary to mention, that Scheduler implements flow control upon Tasks/Coroutines, while Coroutines inform Scheduler on their State changes.
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

ObxShakespeare
Othello, Desdemona and Lodovico dialogue introduces the control delegation in a play. Each artist types a replica and asks Scheduler to gain control to other.
For example, Lodovico says a speech, suspends itself, sets Othello turn after a 1000 ms and yields:

Code: Select all

    Say(r, "I do beseech you, sir, trouble yourself no further.");
    Next(r, othello); Co.Yield; 

PROCEDURE Next (r, rnext: Player);
BEGIN
    r.Suspend(r);
    rnext.SchedSleep(rnext, 1000);
    rnext.Resume(rnext)
END Next;
The console messages appear in the speed of declamation:

[Enter OTHELLO, LODOVICO, DESDEMONA, EMILIA and Attendants]
Lodovico. I do beseech you, sir, trouble yourself no further.
Othello. O, pardon me: 'twill do me good to walk.
Lodovico. Madam,good night; I humbly thank your ladyship.
Desdemona. Your honour is most welcome.
Othello. Will you walk, sir? O, -Desdemona,-
Desdemona. My lord?
Othello. Get you to bed on the instant; I will be returned forthwith: dismiss your attendant there: look it be done.
Desdemona. I will, my lord
Dmitry Dagaev
Posts: 68
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Post by Dmitry Dagaev »

ObxProducerConsumer

Cooperative Multitasking needs special inter-task communication tools. Co.Semaphores are used for inter-Co_Routine communication. They can be used only for Anonymous Co_Routines with Scheduler and dispatcher.

ProducerConsumer Example contains MessageBox structure, protected by the Semaphores. Each message box has sempty and sdata semaphores.

Code: Select all

	PROCEDURE Send (VAR mb: MessageBox; VAR msg: Ct.Message);
	BEGIN
		Co.SemDown(mb.sempty);
		WITH msg: Message DO
			mb.msg := msg
		| msg: AckMessage DO
			mb.ack := msg
		END;
		Co.SemUp(mb.sdata)
	END Send;
		
	PROCEDURE Recv (VAR mb: MessageBox; VAR msg: Ct.Message);
	BEGIN
		Co.SemDown(mb.sdata);
		WITH msg: Message DO
			msg := mb.msg
		| msg: AckMessage DO
			msg := mb.ack
		END;
		Co.SemUp(mb.sempty)
	END Recv;
The Send waits until MessageBox is empty, then puts sdata and increments sdata semaphore.
The Recv waits until MessageBox has data, then reads sdata and increments sempty semaphore.
Josef Templ
Posts: 262
Joined: Tue Sep 17, 2013 6:50 am

Re: Co_Routines Support for Oberon

Post by Josef Templ »

Dmitri, first of all thanks for the detailed comments.
I have not yet read all of the latest postings but hope that I am not creating too much confusion.

Here are some design thoughts from my side.
You may find the first paragraphs destructive, but please read on. It gets more constructive below.

The distinction between directed and undirected coroutines is not very well established in the community.
I can only find the mentioned reference in the Wiki2, which is not the same as wikipedia.
It looks to be more like an ad-hoc classification of somebody than established terminology.
Personally, I have never heard this before.

All coroutine packages that I have ever seen had something like a directed TRANSFER.
Limiting the target of TRANSFER leads to special programming patterns that are application specific.
Removing the directed transfer at all because it can be used erroneously seems quite radical to me.
It is much like removing recursion because it can lead to stack overflow.
This is probably the reason why I couldn't get started with the Co_ package easily.

Saying that coroutines must be stacked like subroutines is also quite radical.
In general, they may not be stacked like subroutines. There is, however, one aspect that is
like subroutine stacking at least in many cases and this is the starting of coroutines.
Every coroutine (except main) has exactly one coroutine that started it and usually, but not necessarily,
the starting coroutine survives the started coroutine.
I will come back to this below.

A special problem arises with a RETURN from a coroutine. As I have mentioned earlier in the center forum,
it was not clear to me if the current definition is appropriate. The current definition allows a RETURN
and means a transfer to the caller (from), if the caller still exists, otherwise to main. In most cases the caller will
exist but it is of course possible to construct cases where it does not exist any more because it has already returned.
Many coroutine packages don't allow a RETURN at all but require an explicit transfer at the end of the coroutine.
This would also be easy to implement. Allowing the RETURN has the advantage that it saves an extra statement
at the end of a coroutine if the default behavior fits with the coroutine's need. Disallowing the RETURN has the
advantage that it makes it explicit which transfer is done and it avoids any discussion about the semantics.
Anyway, the more I think about it the less I like the current implementation.

If a special programming pattern requires that the starting coroutine, let's call it "parent", is the same as the
transferring coroutine this could be implemented inside the coroutine by introducing a local "parent" variable
initialized as parent := this.from at the beginning of the coroutine. After any transfer an ASSERT(parent = this.from)
can be inserted. This pattern could be simplified further by introducing a "parent" field in
the Coroutine base type. The overhead is very small and it does not have any overhead in a
Transfer operation. Then there is at least a simple possibility for runtime checking some patterns.
Furthermore there could also be a wrapper around the Transfer operation (Yield?) that has this ASSERT included.
Such a special Transfer can be done in the application code or it could be added to Coroutines.
Similarly, a Transfer wrapper can be used in the starting coroutine (Generate?).
It adds ASSERT(current.from = target) after the Transfer(target). Generate and Yield would be Transfer
wrappers for the iterator pattern.

If a "parent" field is introduced in the Coroutine base type this would lend itself as a better target for
RETURN. The semantics would be that RETURN transfers to parent and if parent does no longer exist,
it traps, and thereby eventually transfers to main.
Or, more traditionally, RETURN is not allowed at all.

My latest update introduces the mentioned features (parent, Iterator, Task).
Some details are also changed e.g. from renamed to source and Pause renamed to Sleep.
RETURN now transfers to parent.
You may want to look into the latest build at http://blackboxframework.org/unstable/i ... a1.833.zip.
The diffs are here: https://redmine.blackboxframework.org/p ... e1ac8bf0c0.

- Josef
Post Reply