chymyst/chymyst-core

Declarative concurrency in Scala - The implementation of the chemical machine

Chymyst - Declarative concurrency in Scala

The Chymyst project is an application framework and library for developing general concurrent applications in Scala.

This project uses the Chymyst Core library, which implements the chemical machine paradigm of concurrency.

chymyst-core's Issues

Livelock detection should support nonlinear input

Currently, livelock warning is printed for a reaction with a nonlinear input pattern, such as

go { case a(x) + a(y) => a(x+y) }

Livelock detection should take into account that this reaction requires two copies of a but emits only one (if that can be reliably detected).

Failure to detect livelock with refutable tuple pattern

The reaction go { case a((1,_)) => a((1,1)) } with val a = m[(Int,Int)] should be detected as an unconditional compile-time livelock because a((1,1)) is a constant and the input pattern a((1,_)) matches that constant. However, tests show that this is not detected as a livelock. MacroErrorSpec.scala line 116.

Molecule search DSL

The reaction scheduler needs a much more efficient algorithm for choosing the subgroups of molecule values for a given reaction (when there are cross-molecule conditions). This algorithm can be fixed either at compile time (via macro) or at reaction site initialization time, by examining the input patterns of a given reaction.

The algorithm can be expressed as a "molecule value chooser machine" that executes instructions from a small instruction set (the "molecule search DSL"). A "program" in this instruction set represents a search that is done efficiently: first, examine larger cross-molecule group constraints, but at the same time impose constraints on subsets of the large groups; the order of group constraints is chosen to minimize the combinatorial explosion.

The molecule search DSL contains the following instructions:

single(Molecule)

single_cond(Molecule, T => Boolean)

repeated(Molecule, Int)

repeated_cond(Array[(Molecule, Int)])

group_cond(Molecule, ..., Cond, ...)

The actual instruction set and its operational semantics need to be made precise.

How does this compare to Futures?

It'd be good to add an example of how code using this paradigm compares to Futures (and Scala's ExecutionContext) in practice.

Merge guard conditions that constrain the same subsets of molecules

Guard conditions are reduced to CNF and split into clauses. It can happen that several clauses constrain the same subset of molecules (even though they refer to different pattern variables). It would be better for performance if all these clauses were merged into one guard condition at compile time.

Example:

go { case a(Person(name, address)) + b((t,x,y,z)) + c((p,q))
  if name.length > x && y < p && z < q
 => ??? }

The guard condition is in CNF. The first clause is a cross-molecule guard that constrains molecules a and b. The second and the third cross-molecule guard clauses both constrain molecules b and c.

Presently, the go macro will return a Reaction structure with three guard clauses, showing dependence on pattern variables name,x, y,p, and z,q respectively.

It is better if the last two cross-molecule guards were merged into one, y < p && z < q, depending on pattern variables y,p,z,q and constraining the molecules b and c.

Support patterns with type ascription

Not sure whether type ascriptions pq"$var @ (_: $type)" or pq"$var : $type" are supported when we detect irrefutable patterns. Tests need to verify this, and if type ascriptions are not supported, macros should be extended to support them.

Comparison to Temporal Logic , FRP , TLA+

Is it possible to compare this to FRP and Temporal logic and provide some counterexamples on the expressiveness of FRP?

Another variant of temporal logic is TLA+ and it seems that one can model the philosophers' dinning problem :
https://learntla.com/concurrency/processes/ (though this is written in plusCal)

I am interested in specifying self-organizing social systems and then creating the code that will enable their communication patterns. They are studied as Complex Systems and it seems that they draw many ideas from Statistical thermodynamics and Physics.

I haven't read this paper yet but it is one of the very few that uses formal methods (TLA+ , Event B) to prove properties about self-organizing systems.
https://hal.archives-ouvertes.fr/hal-01726402/document

Use static checks for static molecule emission

Static molecules should be emitted in an "at least one" environment by the static reaction, and in an "exactly one" environment by all other reactions. Static analysis must check that and flag any errors.

In particular, static molecules cannot be emitted in contexts where a reply cannot be emitted.

Failure to compile reactions with compound grouped pattern variables

In some cases, macros in ReactionMacros.scala/ Macros.scala fail to build correct pattern matching closures.

Testing with scalatest cannot uncover this failure: see https://github.com/Chymyst/joinrun-scala/blob/master/joinrun/src/test/scala/code/chymyst/jc/MacroErrorSpec.scala#L57

This test passes, but writing

val c = m[(Int, (Int, Int))]
go { case c((_, z@(_, _))) => }

will not compile. The error is "scalac: Error: Could not find proxy for val x2: Tuple2 in List(value x2, method applyOrElse, ...)"

The error happens after macro expansion. The macro prepares a partial function

{ case (_, z@(_, _)) => } : PartialFunction[Any, Unit]

that should detect the pattern match. The code of the partial function is correct. However, the code fails to compile when this partial function is inserted into ReactionInfo.

Removing z@ makes the code compile.

The same thing happens with

val d = m[(Int, Option[Int])]
go { case d((x, z@Some(_))) => }

Removing z@ makes the code compile.

A very similar issue is discussed at http://stackoverflow.com/questions/41539029/how-to-use-scala-macros-to-create-new-partial-functions-or-transform-them/41548756

The workarounds discussed there have been tried. Perhaps what's missing is a type annotation on z, or some more c.untypecheck at the right place. Or perhaps it's a missing "owner" on some symbol.

Failure to compile a one-molecule guard that uses `Array` type

In GuardsSpec.scala line 278, a test is commented out:

val done = m[Array[Int]]
val reaction = go { case done(arr) if arr.nonEmpty => }

This fails to compile due to a type error in the conditional.

It seems that the guard if arr.nonEmpty is not produced correctly by the go macro, which generates the partial function

{ case (arr @ _) if scala.Predef.intArrayOps(arr).nonEmpty => () }

that does not compile with a type error: arr is typed as Any instead of Array[Int] as required.

Terminology nitpick: recursive molecule ~> chain reaction?

I'm just starting to study your work, so thank you for everything so far. Thanks especially for focusing on making concurrency easier to understand, which I like coming from researching Akka as inspiration for Rust and then Actix. To start, I've been trying to sort out how the families of conceptual models relate to one another and to see if some metaphor could help for terminologically organizing their features. I also just so happened to want a declarative scripting language built on top, so this project is a great find. :)

My question is, what do you think about calling MergeSort's reaction a chain reaction instead of a recursive molecule? Hopefully it would help to gain further insight about how these types of "chemical reactions" are set up and generally flow, and it would retain the metaphor which hides the internals.

Aside: I'm curious to see if another metaphor would work, either (possibly delegation-based) teamwork or supply chain logistics, so you can see my very rough first attempt with those terms in actix/actix#9. I don't know Actix' semantics for "chain reactions" but it would be very interesting to compare for these discussions.

Support nested `if` statements as output environments

Currently, only a single layer of if statements is supported when analyzing the output environments in the "shrink" operation at compile time.

However, the go macro already gathers complete tree of possible if statements and other output environments. This tree needs to be transformed at compile time into a more readily usable structure, so that emit-once, emit-at-least-once, and emit-maybe are determined for arbitrary nested if statements interspersed with function calls.

Replace Philosophers, Spaghetti, and Forks with Readers, Books, and Candles

There seems like no way to mentally picture any of this without tripping over a fallen Ugly Tree branch.

I'd take this issue upstream, but this project seems like the best ongoing work in the field.
So I propose to this project's community here:

• Philosopher ~> Reader
• Spaghetti ~> Book
• Forks ~> Lights (need both sides of the book lit in order to read)

To bolster this terminology, the latest solution fits N "readers", not 5 named participants, and makes a good bit of sense while using some messaging. So, this could easily be visualized as an After Dark Reading Circle. This way, thinking goes hand-in-hand with putting down reading material, which frees a light source, and reading can take place continuously for those who want it and while their neighbors keep thinking (or sleeping), as long as that works well for them. No one has to starve.

Implement granular locking

• When the reaction site decides on a new reaction, it should only lock the molecule values that it needs to examine. This will allow several reaction schedulers to operate concurrently, as long as they can operate on different molecule copies without contention.
• The locking should be both per-molecule and per-molecule value, such that a reaction could specify that it needs any 2 copies of a molecule regardless of their values, or it needs to examine potentially all copies of a molecule, etc.
• The reaction scheduler should hold a lock on a subset of molecules, on a subset of molecule values for a given molecule, and on a subset of copies of a molecule that has a given value.

Implement two locking principles:

1. Decreasing monotonicity: Once a lock is obtained on a subset of items, there cannot be a further lock obtained on a larger subset while still holding the lock on a smaller subset. The only change in locking can be the release of the lock on the entire subset or on a part of the subset.
2. Non-contention: We lock the items only because we cannot reach the correct decision without examining these items, and because other agents need to be prevented from withdrawing these items while we are still examining them. We release the lock on an item only when we learn that the correct decision can still be reached without using that item.