LOGO-L> Logo with parallel processes vs. ToonTalk

["Ken Kahn" <KenKahn@ToonTalk.com>]

In the recent discussion about Logo and ToonTalk, one of the issues was
about concurrency. I promised a longer response to the question about
whether the parallelism supported by MicroWorlds is as good as what ToonTalk
offers. Here's my 7 paragraph long answer:

Before I attempt to explain concurrent computation in ToonTalk and why it is
difficult to extend sequential languages to be concurrent, I'll explain the
relationship between concurrency, parallelism, and distributed computing.
Parallel processes are processes that are running within the same computer
system. The system typically has more than one processor. Distributed
processes are processes that typically running on different computer systems
connected via a network. The distinction between parallel and distributed is
important because distributed computing is typically across trust or
organizational boundaries. Hence only distributed computing need be
concerned with security, resource allocation, hardware failure recovery, and
the like. In discussions where the distinction is not important, I refer to
concurrent processes, i.e. processes that might be either parallel or
distributed.

ToonTalk is a thoroughly concurrent programming language. That is because
the only kind of sub-computation that can be expressed is as a new process.
If a robot needs to have some other robots perform some sub-computation, he
must be trained to load up a truck with those other robots. The new house
built by the crew in the truck is a new process. Unlike conventional
languages (C, Java, Logo, Lisp, Fortran, Cobol, Perl, Basic, etc.), there is
no way to express a subroutine call in ToonTalk. One can get the equivalent
behavior in ToonTalk by training a robot to load up a truck with robots and
a box with a bird in it. The robot should put the nest of the bird is his
box and do nothing more. That robot or other members of his team should be
programmed to look for something in the nest. Consequently this process will
suspend until the robots that were placed in the truck give the bird
something. The robots waiting on the nest will see what was delivered and
resume computation. In other words, a subroutine or procedure call in
ToonTalk is just a very special pattern of use of trucks, birds, and robots.
ToonTalk only provides the programmer with the more general ability to
express the spawning of new processes.

The lack of subroutines in ToonTalk makes it much more feasible to have much
larger number of processes than conventional programming languages. The
reason for this is that everyone implements subroutine calls using a data
structure called a stack. Stacks are a very effective way of implementing
procedural calls, including recursive calls. The problem is that each
process needs its own stack. This makes processes somewhat costly. I've
tested ToonTalk with tens of thousands of houses (i.e. processes). In
contrast, when I used Java, it stopped working when I had just a couple
hundred processes.

Conventional languages have shared state. The same variables, data
structures, and objects can be accessed from different processes (processes
that share data are often called threads). Sharing state is necessary in
these languages in order for threads to work together. This sharing between
concurrent independent processes is very dangerous, however. It leads to
race conditions. Consider a variable, A, that is supposed to represent the
current balance of a savings account. (A might be a global variable or it
might be an instance variable of an object - both kinds of variables have
this problem.) A subroutine has been written to withdraw X from A after
checking if X is less than or equal to A. It withdraws by assigning A to
A-X. In other words the subroutine allows a withdrawal only if there are
sufficient funds in the account. Now let us introduce concurrency. Suppose
there is an account with 10 dollars in it and one process would like to
withdraw 9 dollars and another process wants to withdraw 8 dollars. With bad
luck both withdrawals can occur. And even worse the balance might be 1
dollar, 2 dollars, or -7 dollars after processing the two withdrawals. How?
Consider this scenario:

Process 1 checks that A is less than X and computes A-X to be 1 but before
assigning A to 1, Process 2 runs and sees that A is still 10 so it processes
the entire withdrawal and sets A to 2. Process 1 resumes where it left off
and sets A to 1.

So how do conventional languages deal with race conditions? They introduce
new programming constructs: locks or critical regions. For example, the
withdrawal procedure could obtain a lock on A so that no other process can
access it. It can then safely compare it to X, compute A-X, and set A to the
result. It must then release the lock on A or else no one else can ever
access A. Not only does this add complexity to the task of making programs,
but it can lead to new problems: namely, deadlock. Suppose Process 1 locks A
and then needs to find the value of B that is locked by Process 2. So
Process 1 suspends and waits for Process 2 to unlock B. But what if Process
2 then needs to access the value of A. A is locked so Process 2 also
suspends. This is sometimes called a deadly embrace. You might think it
would be easy to program in such a way to avoid this kind of mutual
dependency. But the cycle of dependency might involve hundreds of processes.

So why doesn't ToonTalk suffer from these problems? The reason is that
ToonTalk has no shared state. A box can only exist in one place. And robots
in the same house take turns - they never work on the same box at the same
time. The lack of shared state is how ToonTalk avoids race or deadlock
problems. But doesn't this limit the expressivity of the language? It would,
if it wasn't for birds. Consider the ToonTalk bank account demo. Multiple
processes can withdraw money from the same account. Each process has a copy
of a bird whose nest is in the box that is representing the bank account.
Robots in different houses can give the birds to this account withdrawal
requests by giving the birds boxes containing the amount of money that to be
withdrawn. We don't know which box will end up on top of the nest - but all
them will be stacked up on the nest. (In other words, the requests are
queued up on the nest.) The robots working on the box for the account will
see a box appear on the nest for a withdrawal request. They will process the
request before starting on the next request. There is no problem, even if
the computation of the new balance requires a new sub-computation. The robot
will load up the truck with robots and a box to compute the new balance. And
then it will place the nest that will receive the answer in the location
where the current balance is kept. The next request won't be processed until
the sub-computation gives the bird the new balance and the appropriate nest
is covered.

In summary, attempts to add concurrency to languages with subroutines and
shared state lead to complexity, costly implementations of processes, and
bugs that are very hard to track down. ToonTalk, in contrast, was designed
from scratch to be concurrent. In ToonTalk there is no need to introduce
locks or critical regions, processes cost very little, and race conditions
and deadlocks are avoided.

Comments? Questions?

Best,

-ken kahn (www.toontalk.com)







---------------------------------------------------------------
Please post messages to the Logo forum to logo-l@gsn.org.  Mail
questions about the list administration to logofdn@gsn.org.  To
unsubscribe send    unsubscribe logo-l    to majordomo@gsn.org.