anatoliykmetyuk / free-acp Goto Github PK

Choices that are discarded should be notified about it somehow in order to terminate gracefully.

Natural transformations are almost always used in situations when the upper bound for A in apply[A] is known. Currently, this knowledge is present in the form of type casts where needed, which is not good.

Implicit functions as in ordinary functions accepting the parameters that are currently implicit. So that we can run "isDefinedAt" without having the implicits.

Currently, the tree that needs resumption is processed as follows:

            resume.apply(t)
              .map((f.apply[Tree[S]] _) andThen G.extract andThen rewriteLoop)
              .find(!_.isInstanceOf[Failure[S]])
              .getOrElse(Failure[S]())

All the elements are mapped with G.extract in order. G.extract may be blocking, like Await.result on a Future. So one choice that never happens may prevent all the subsequent ones from being considered.

Instead, what is needed is a kind of an Observable which will try to extract all the choices simultaneously and will emit them in order in which they happen.

The first choice that does not evaluate to Failure should be considered. Optionally, the remaining choices should be cancelled, allowing them to terminate gracefully.

• Natural transformations-based compilers
• Lazy loops, calls and recursion

When defining extensions to the default language, a pattern emerges:

trait SayElem {
  import LanguageT._

  case class Say(s: String) extends LanguageT[Result[LanguageT]]
  def say(s: String, name: String = "suspend"): Tree[LanguageT] = new Suspend[LanguageT](Say(s)) { override def toString = name }

  def sayCompiler[F[_]: Suspended]: PartialCompiler[F] = _ => new (LanguageT ~> OptionK[F, ?]) {
    override def apply[A](s: LanguageT[A]): Option[F[A]] = ({
      case Say(s) => implicitly[Suspended[F]].apply { () => println(s); ε.asInstanceOf[A] }
    }: PartialFunction[LanguageT[A], F[A]]).lift.apply(s)
  }
}

trait PromiseElem {
  import LanguageT._

  case class PromiseContainer(p: Promise[Result[LanguageT]]) extends LanguageT[Result[LanguageT]]
  def promise(p: Promise[Result[LanguageT]], name: String = "promise") = new Suspend[LanguageT](PromiseContainer(p)) { override def toString = name }

  def promiseCompiler: PartialCompiler[Future] = _ => new (LanguageT ~> OptionK[Future, ?]) {
    override def apply[A](s: LanguageT[A]): Option[Future[A]] = ({
      case PromiseContainer(p) => p.future
    }: PartialFunction[LanguageT[A], Future[A]]).lift.apply(s)
  }
}

In both cases, we have a custom compiler and a case class that extends LanguageT[Result[LanguageT]]. Is it possible to also define Loop[S[_]] <: Tree[S] this way? If so, resumption and rewriting will be affected.

δ + x != x + δ. This is because:

• The dummy Eval implementation always selects the RHS operand
• For arbitrary functor, F[A <: Tree], there is no way of knowing the result of that functor until running it with a Comonad.

Hence, it can be a better idea to move the Choice logic from resumption to run/runM. The resumption then will return a List[F[Tree]].

Currently, a pattern emerges whenever we try to define all the type classes needed for the suspension functor:

trait EvalImpl {
  implicit val suspendedEval: Suspended[Eval] = new ( (() => ?) ~> Eval ) {
    override def apply[A](x: () => A): Eval[A] = Eval.always(x())
  }

  implicit val monoidKEval: MonoidK[Eval] = new MonoidK[Eval] {
    override def combineK[A](e1: Eval[A], e2: Eval[A]): Eval[A] = e2
    override def empty[A] = Eval.always[Nothing] { throw new NotImplementedError }
  }
}

trait FutureImpl {
  implicit val suspendedFuture: Suspended[Future] = new ( (() => ?) ~> Future ) {
    override def apply[A](x: () => A): Future[A] = Future { x() }
  }

  implicit val monoidKFuture: MonoidK[Future] = new MonoidK[Future] {
    override def combineK[A](e1: Future[A], e2: Future[A]): Future[A] = Future.firstCompletedOf(List(e1, e2))
    override def empty[A] = Future.never
  }

  implicit val comonadFuture: Comonad[Future] = new Comonad[Future] {
    override def extract[A](x: Future[A]): A = Await.result(x, Duration.Inf)
    override def coflatMap[A, B](fa: Future[A])(f: Future[A] => B): Future[B] = map(coflatten(fa))(f)
    override def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f)
  }
}

Probably, these traits could be turned into type classes for arbitrary S[_]. Benefits from it:

• Ability to test these type classes via laws (see #11)
• More concise code: three type classes are replaced by only one

This is a continuation of a mail discussion. The editing in Mac Mail is terrible, so I started this issue.

Shorthand notations can vastly improve readability.
In SubScript there is script.., and similar constructs can be made for def, var, val, object, class and case class. For more macro power, with a kind of parameters, I propose that

• a line starting with .. starts a shorthand section
• the shorthand section ends at the first line
  • that has it first token right below or even more to the left of ..
  • and that has the same parentheses level (i.e. not deeper in (), {} or [])
  • and that is neither in a deeper string level
• the first line, possibly with next ones, starts a template
  • next lines are included as long as the nesting level is higher at the line end
  • or as long as a backslash is at the line end, like in C macros
• thereafter follows an instantiation table

The template may contain placeholders of 1 of the following forms (not both!):

• anonymous placeholders; these are by default two or more hash symbols: ##
• named placeholders; these are character sequences between some special quotation delimiters, by default those are backticks. The character sequences should start and end with non-whitespace.
• the table cell separator is by default the vertical bar: |

It is possible to override these placeholder characters, quotation delimiters and cell separators, see later.

Examples:

..
  case class #### [S[_]](####)(implicit val S: Suspended[S],
                                          val F:   Functor[S]) extends ####[S] {
    override def toString = s"####"
  }

  Suspend  | t : () => S[Tree[S]] | Tree   | suspend      
  Call     | t : () => S[Tree[S]] | Tree   | call    
  Sequence | ts:    List[Tree[S]] | Tree   | [*](${ts.mkString(" * ")})                    
  Choice   | ts:    List[Tree[S]] | Tree   | [+](${ts.mkString(" + ")})                
  Success  |                      | Result | 1
  Failure  |                      | Result | 0
  Loop     |                      | Tree   | ...

..
  object #### {
    def apply[S[_]](ts: Tree[S]*)(implicit S: Suspended[S],
                                           F:   Functor[S]): ####[S] = ####[S](ts.toList)
  }
  Sequence | Sequence | Sequence  
  Choice   | Choice   | Choice  

The latter table has some repetitions. Therefore we can add a first row that makes columns in next rows superfluous:

..
  object #### {
    def apply[S[_]](ts: Tree[S]*)(implicit S: Suspended[S],
                                           F:   Functor[S]): ####[S] = ####[S](ts.toList)
  }
  #### | $1 | $1
  Sequence  
  Choice

There we see that only 1 #### placeholder remains, hence the last two rows have only one cell.
The other placeholders are resolved,to the value of the first placeholder ($1). We could also do invoke macros here, e.g.,

camelCase($1)

or do a kind of string interpolation, e.g. for prefixing with an underscore:

$"_$1"

Instead of ##### placeholders, we may also have named placeholders.
These must be between quotation symbols, by default `. It is possible to override these, e.g., to <<...>>. In case of named placeholders, the instance table gets a header row with the placeholder names, and a separator row with dashes and plusses:

..

  case class `Name` [S[_]](`Params`)(implicit val S: Suspended[S],
                                              val F:   Functor[S]) extends `SuperC`[S] {
    override def toString = s"`Representation`"
  }

  Name     | Params               | SuperC | Representation
  ---------+----------------------+--------+----------------      
  Suspend  | t : () => S[Tree[S]] | Tree   | suspend      
  Call     | t : () => S[Tree[S]] | Tree   | call    
  Sequence | ts:    List[Tree[S]] | Tree   | [*](${ts.mkString(" * ")})                    
  Choice   | ts:    List[Tree[S]] | Tree   | [+](${ts.mkString(" + ")})                
  Success  |                      | Result | 1
  Failure  |                      | Result | 0
  Loop     |                      | Tree   | ...

..

  object `Name` {
    def apply[S[_]](ts: Tree[S]*)(implicit S: Suspended[S],
                                           F:   Functor[S]): `Name`[S] = `Name`[S](ts.toList)
  }

  Name
  ----------
  Sequence  
  Choice

There should be a possibility to do some name manipulation between the placeholder quotes. In the latter object, we reused Name twice. Suppose we wanted to camelCase, or add an underscore, then something like the following would do:

`${camelCase($Name)}`
`_$Name`

Or maybe it should be different. Anyway, it must not be significantly longer.

An expression a * b * c will be parsed as (a * b) * c in Scala. This can cause problems with special operands.

The reason is that Scala's operators are binary.

One solution may be a compiler plugin that allows for n-ary operators.

A workaround is to apply the operator functions directly: Sequence(a, b, c).

IMO this needs a separate check.

Special elements ..., break and break? are useful to have, but they mess up axioms and properties.

E.g.

property("Commutativity of +" ) = forAll { (x: Language, y: Language) => x + y <-> y + x }

This does not hold for x or y being such a special element.

property("Associativity of *") = forAll { (x: Language, y: Language, z: Language) => (x * y) * z <-> x * (y * z) }

This should not hold if x, y or z is ....
Or maybe it should, and is the problem that we need an alternative for the parentheses (Call(...)?), as long as we are sticking to Scala syntax.
BTW x*y*z should be yet another thing.

There have been rewriting approaches to ACP before, such as in Toolbus and PSF. Those were not successful:

• One problem was IMO that Toolbus and PSF did not have a smooth coexistence with a normal programming language. SubScript and Free-ACP have that.
• PSF was very slow; I am not sure about Toolbus. Maybe the Free-ACP implementation in Scala is fast enough in many practical cases, but I doubt the scalability.

AFAIK SubScript VM's complexity is O(n), that is: execution overhead is proportional to the program size (code fragments, special elements, calls, operators).

I have the impression that Free-ACP will have complexity O(n^2) or worse.
Consider for instance k processes in a parallel composition, that each perform m actions in sequence. Say n = m*k.

Free-ACP will start with constructing a k-fold choice, namely: what process should start. Each choice contains a starting action, followed by another parallel composition, etc.
It seems that for each step you will have a k-fold overhead. So the complexity may be as bad as O(k*n) which is almost O(n^2).

Is that true? Or will complexity be worse or better?

Features of the free language:

• Code fragments with (optional) executors
• All the operands

Type classes for the language should implement all the operations by reification.

The free compiler should capture the reifications given correspondent type classes of the target category.