Icon Co-Expressions in Ada

Icon Co-Expressions in Ada

[Ehud Lamm]

I am thinking about implimenting Goal Directed Evaluation ala Icon, as an
Ada package. I considred two options:
1. Using "static" data (that is, variables stored in the package's body,
in Ada) to impliment the suspend mechanism. This has its obvious problems.

2. Using Ada's tasking facilites. This has the disadvantage of making the
user use tasks. It is sad, since as far as I know you can't simply make an
Ada procedure behave in a task like way, by invking other procedures. The
task must be explicit.

Any thoughts or ideas are more than welcome. If someone did it already -
so much the better. I'd also be happy to see references (esp. Web based)
on implimenting co-expressions.

Thanks. 

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il

Re: Icon Co-Expressions in Ada

[dennison]

In article
<Pine.A41.3.96-heb-2.07.981216194156.29486C-100000@pluto.mscc.huji.ac.il>,
  Ehud Lamm <mslamm@mscc.huji.ac.il> wrote:

> user use tasks. It is sad, since as far as I know you can't simply make an
> Ada procedure behave in a task like way, by invking other procedures. The
> task must be explicit.

If we are talking Ada 95, there actually are (at least) *two* to do this.
Either way you start with a task type, and a manager or registrar package.
Each routine you want to "task-ize" must register with the manager. When a
procedure registers, it provides a subprogram with a standard interface(or
multiple ones). The registrar creates a task object and gives it the
subprogram to call. So far this is your standard C GUI-style "callback"
interface.

Now you just need to specify the procedure(s). One method is to define a
subprogram access type. But the method we have used here is to define an
abstract subprogram as an interface, and have the registrar pass a
(classwide) pointer to the tagged object to the newly-created task. To use
this system, the user just has to derive a type from the abstract class, and
put his Ada procedure code in the override of the abstract method. As soon as
he calls the registrar, his procedure will start getting called from its very
own task automagicly!

--
T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Icon Co-Expressions in Ada

[Stephen Leake]

Ehud Lamm <mslamm@mscc.huji.ac.il> writes:

> I am thinking about implimenting Goal Directed Evaluation ala Icon, as an
> Ada package. I considred two options:
> 1. Using "static" data (that is, variables stored in the package's body,
> in Ada) to impliment the suspend mechanism. This has its obvious problems.

Since I don't know anything about Icon, can you explain what "the
suspend mechanism" does?

> 2. Using Ada's tasking facilites. This has the disadvantage of making the
> user use tasks. It is sad, since as far as I know you can't simply make an
> Ada procedure behave in a task like way, by invking other procedures. The
> task must be explicit.

If "suspend" has its usual English meaning, the user should be using
tasks; one task is suspended while another is running.

An Ada procedure can call task entries, and task entry bodies can call
procedures. Not clear what else you need.

-- Stephe

Re: Icon Co-Expressions in Ada

[Al Christians]

Stephen Leake wrote:
> 
> Since I don't know anything about Icon, can you explain what "the
> suspend mechanism" does?
> 

It's like a return statement in the body of a loop, where the next call
to the function continues the iteration where it left off to get the
next value.  

Al

Re: Icon Co-Expressions in Ada

[Ehud Lamm]

A bit about goal directed evaluation in general. Co-Expressions are really
a special mechanism, and for some reason I slumped them together in my
post.

I'll give an example of how Goal directed eval works:
Icon has a built in function find(s1,s2) which returns (potentially) all
the indexes in s2, where s1 start (find("e","ehud") should be 1).
suppose I say
if find("e","element")>1 then...

What will happen is that find will be executed, it will return 1 which
doesn't satisfy the condition, it will then be resumed, and return the
value 3. Than the "then-clause" will be executed.

For this to work from arbitrary procedures, the language provides the
suspend statement, which is like return but after which the procedure may
be resumed.(you can have a procedure say suspend 4; suspend 5; for
example).

I was thinking about implimenting this statement. Note that you ahve to
remember exactly where the computation stopped.

Co-expression are another mechanism. The allow you a limited sort of
parallel execution, of two or more procedure that can be supended. This
allows you to take one value from one routine, another from the second
routine etc.

Hopes this clears things up, a bit.

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il
P.S
If any one is interested let them browse to http://www.cs.arizona.edu/icon

If anyone wants to read more, I have a litle memo called "Integrating User
Defined Procedures With Built-In Language Features: The Case of J, Icon
and C++". It deals with Icon generators (= routines that use suspend) and
other clever programming languages features. 

Re: Icon Co-Expressions in Ada

[Stephen Leake]

Ehud Lamm <mslamm@mscc.huji.ac.il> writes:

> A bit about goal directed evaluation in general. Co-Expressions are really
> a special mechanism, and for some reason I slumped them together in my
> post.
> 
> I'll give an example of how Goal directed eval works:
> Icon has a built in function find(s1,s2) which returns (potentially) all
> the indexes in s2, where s1 start (find("e","ehud") should be 1).
> suppose I say
> if find("e","element")>1 then...
> 
> What will happen is that find will be executed, it will return 1 which
> doesn't satisfy the condition, it will then be resumed, and return the
> value 3. Than the "then-clause" will be executed.

I can see this is a general mechanism, difficult to implement in Ada.
The "Ada way" to get this particular result is to pass a "terminate
condition" function to an iterator :

find ("e", "element", index_greater_1'access)

It would be nice to have annonymous functions for this (like lisp
lambda functions), but local functions aren't too bad (in GNAT anyway :).

> For this to work from arbitrary procedures, the language provides the
> suspend statement, which is like return but after which the procedure may
> be resumed.(you can have a procedure say suspend 4; suspend 5; for
> example).
> 
> I was thinking about implimenting this statement. Note that you ahve to
> remember exactly where the computation stopped.

I think I understand "suspend"; it's what Knuth calls a "coroutine". I'm not
clear what "suspend <integer>" means?

You definitely need tasks to do this in Ada, since the task stack is
where the procedure state is saved. At each "suspend", you could have
an accept statement. The caller would still have to write a loop to
get the goal-directed behavior.

> Co-expression are another mechanism. The allow you a limited sort of
> parallel execution, of two or more procedure that can be supended. This
> allows you to take one value from one routine, another from the second
> routine etc.

Ok; Ada tasks are executed in parallel. You'll need a good naming
convention!

> 
> Hopes this clears things up, a bit.

Getting there ...

-- Stephe
> 
> Ehud Lamm     mslamm@pluto.mscc.huji.ac.il
> P.S
> If any one is interested let them browse to http://www.cs.arizona.edu/icon
> 
> If anyone wants to read more, I have a litle memo called "Integrating User
> Defined Procedures With Built-In Language Features: The Case of J, Icon
> and C++". It deals with Icon generators (= routines that use suspend) and
> other clever programming languages features. 

Re: Icon Co-Expressions in Ada

[Mats Weber]

Stephen Leake wrote:

> If "suspend" has its usual English meaning, the user should be using
> tasks; one task is suspended while another is running.

Not true on a multiprocessor, or even with time slicing.

Re: Icon Co-Expressions in Ada

[Mats Weber]

Ehud Lamm wrote:

> For this to work from arbitrary procedures, the language provides the
> suspend statement, which is like return but after which the procedure may
> be resumed.(you can have a procedure say suspend 4; suspend 5; for
> example).
> 
> I was thinking about implimenting this statement. Note that you ahve to
> remember exactly where the computation stopped.

This sounds like coroutines in other languages. The closest Ada has to
offer is tasks, but as Ada tasks can be called concurrently, you will
have a significant overhead over a simple coroutine mechanism.

Re: Icon Co-Expressions in Ada

[Ehud Lamm]

On 17 Dec 1998, Stephen Leake wrote:

> Ehud Lamm <mslamm@mscc.huji.ac.il> writes:
> 
> I think I understand "suspend"; it's what Knuth calls a "coroutine". I'm not
> clear what "suspend <integer>" means?

It is like return <integer>, only that the function's execution can be
resumed.

> 
> You definitely need tasks to do this in Ada, since the task stack is
> where the procedure state is saved. At each "suspend", you could have
> an accept statement. The caller would still have to write a loop to
> get the goal-directed behavior.

This, indeed, is the reason I mentioned tasks in the first place. I just
wanted to emphesize that this mechanism is less general than Ada tasking.

> Ok; Ada tasks are executedin parallel...

You don't say :-)

I was thinking along the lines of the user coding a routine and invokin
procedures which will you tasking capabilites in a limted way. Enough for
suspend etc. but not general tasking.

However as I mentioned in my first post on this topic, this can not be
done since a task must clearly be marked as such.

Ehud Lamm mslamm@mscc.huji.ac.il 
http://www2.cybercities.com/e/ehud/ada  Ada&SE and Ada challanges

Re: Icon Co-Expressions in Ada

[Ehud Lamm]

On Thu, 17 Dec 1998, Mats Weber wrote:

> Stephen Leake wrote:
> 
> > If "suspend" has its usual English meaning, the user should be using
> > tasks; one task is suspended while another is running.
> 
> Not true on a multiprocessor, or even with time slicing.
> 
I must also add, that one of the main points of this exercise, is hiding
the tasking details from the programmer.

Ehud Lamm     mslamm@mscc.huji.ac.il

Re: Icon Co-Expressions in Ada

[Ehud Lamm]

On Thu, 17 Dec 1998, Mats Weber wrote:

> Ehud Lamm wrote:
> 
> > For this to work from arbitrary procedures, the language provides the
> > suspend statement, which is like return but after which the procedure may
> > be resumed.(you can have a procedure say suspend 4; suspend 5; for
> > example).
> 
> This sounds like coroutines in other languages. The closest Ada has to
> offer is tasks, but as Ada tasks can be called concurrently, you will
> have a significant overhead over a simple coroutine mechanism.
> 
See my post about Co-Expressions and goal directed evaluation in general.
The concepts are near but not identical. You can have generators (that is,
routines that use suspend and return a series of values) without using
Co-Expressions.
I think Co-Expressions are what others call co-routines, but I am not 100%
sure.

About the overhead. Can we design something less costly using protected
objects?

Ehud Lamm     mslamm@mscc.huji.ac.il
http://www2.cybercities.com/e/ehud   E-List Home Page

Re: Icon Co-Expressions in Ada

[Chris Morgan]

Mats Weber <Mats.Weber@elca-matrix.ch> writes:

> This sounds like coroutines in other languages. The closest Ada has to
> offer is tasks, but as Ada tasks can be called concurrently, you will
> have a significant overhead over a simple coroutine mechanism.

A standard technique in JSD is to map many theoretical processes or
state machines in the design into one Ada task (often referred to as a
group). In the toolset I use to work on this meant that the Ada for a
particular process became a chunk of flat code with gotos and
labels. In the design we worked as if the process ran concurrently
with the other ones in the group and we could use loops and so
on. This structure was "read-inverted" by the toolset so each process
became just a procedure with an extra parameter of the state. The
loops were simulated of course. I thought this made sense as we were
taught to regard using a whole task as expensive. It often occurred to
me how grotesque it was stepping through spaghetti machine generated
code with gotos and labels, but that's the price for some of these
high-concept design techniques with "automatic" code generation.

Chris
-- 
Chris Morgan <mihalis at ix.netcom.com>		http://www.mihalis.net