Simple Rholang with higher-order channels and continuations

SimpleRholangWithContinuations.scala

// Recordings: https://www.youtube.com/watch?v=syXuWv1PZRg&list=PLniEJXpXl6-qSgCMKT2ocQIYt_BQZe04u&index=12

object rholang {

  /**
    * This interface represents terms in our Simple Rholang language.
    * Everything is a process.
    */
  trait Process

  /**
    * AST of our Simple Rholang language. It's private and accessible only
    * inside this object. The only way to change the state (Set[Process]) is to
    * call defined operations (nil, par, send, receive).
    */
  private final case class Par(
      sends: Seq[(Process, Process)] = Seq(),
      receives: Seq[(Process, Process)] = Seq(),
      exprs: Seq[Process] = Seq()
  ) extends Process {
    override def toString: String = {
      val ss  = sends.map { case (n, v) => s"Send($n, $v)" }
      val rs  = receives.map { case (n, v) => s"Receive($n, $v)" }
      val es  = exprs.map { case p => s"$p" }
      val all = ss ++ rs ++ es
      if (all.isEmpty) "nil" else all.mkString(" | ")
    }
  }

  /**
    * `nil` and `par` are Monoid operations (empty, combine).
    *
    * All terms (processes) are collected in a Set defined in Par(Set[Process]).
    */
  def nil: Process = Par()

  def par(p1: Process, p2: Process = nil): Process = (p1, p2) match {
    // Combine states from both Par's
    // This rule also "erase" `nil` from both sides of Par
    //   nil | p  ==  p  ==  p | nil
    case (Par(s1, r1, e1), Par(s2, r2, e2)) =>
      Par(sends = s1 ++ s2, receives = r1 ++ r2, exprs = e1 ++ e2)

    // Next two cases flatten nested Par's
    //   Par(Set(Par(Send(A)))) => Par(Set(Send(A)))
    case (Par(s, r, e), p2) => Par(s, r, e :+ p2)
    case (p1, Par(s, r, e)) => Par(s, r, e :+ p1)

    // All other cases just collect as expressions
    case (p1, p2) => Par(exprs = Seq(p1, p2))
  }

  /**
    * `send` and `receive` represent basic operations.
    */
  def send(name: Process, value: Process): Process = Par(sends = Seq((name, value)))

  def receive(name: Process, cont: Process): Process = Par(receives = Seq((name, cont)))

  /**
    * Support for ground types (built-in processes).
    */
  private trait Ground extends Process
  private final case class GString(x: String) extends Ground {
    override def toString: String = s""""${x}""""
  }
  private final case class GInt(x: Int) extends Ground {
    override def toString: String = s"${x}"
  }
  private final case class GSystem(id: String, proc: Process) extends Ground {
    override def toString: String = s"SYS($id, $proc})"
  }
  private final case class GTuple(args: Seq[Process]) extends Ground {
    override def toString: String = s"(${args.mkString(", ")})"
  }

  def string(x: String): Process = Par(exprs = Seq(GString(x)))

  def int(x: Int): Process = Par(exprs = Seq(GInt(x)))

  def sys(x: String, proc: Process): Process = Par(exprs = Seq(GSystem(x, proc)))

  def tuple(p1: Process, p2: Process): Process = Par(exprs = Seq(GTuple(Seq(p1, p2))))

  /**
    * Converter to process
    */
  trait ToProcess[A] {
    def convertToProcess(a: A): Process
  }

  // Helper if process cannot be converted automatically
  def p[A](x: A)(implicit instance: ToProcess[A]): Process = instance.convertToProcess(x)

  def par[A: ToProcess, B: ToProcess](x: A, y: B): Process = par(p(x), p(y))

  // Tuples defined as infix function e.g. (a ~ b)
  def t[A: ToProcess, B: ToProcess](x1: A, x2: B): Process = tuple(p(x1), p(x2))

  // Extensions
  def send[A: ToProcess, B: ToProcess](n: A, v: B): Process = send(p(n), p(v))

  def receive[A: ToProcess, B: ToProcess](n: A, v: B): Process = receive(p(n), p(v))

  def sys[A: ToProcess](id: String, proc: A): Process = sys(id, p(proc))

  /**
    * Matching
    */
  type TupleSpace = Seq[(Process, Process)]

  def matchProc(name: Process, st: TupleSpace): (TupleSpace, Option[Process]) = {
    type Param = (TupleSpace, Option[Process])
    st.foldLeft[Param]((Seq(), None)) {
      case ((acc, None), (n, v)) if n == name => (acc, Some(v))
      case ((acc, b), pp)                     => (acc :+ pp, b)
    }
  }

  def matches(ts1: TupleSpace, ts2: TupleSpace): (TupleSpace, TupleSpace, Seq[Process]) =
    ts1.foldLeft[(TupleSpace, TupleSpace, Seq[Process])](Seq(), ts2, Seq()) {
      case ((t1, t2, cs), (name, value)) =>
        val (t2a, matched) = matchProc(name, t2)
        matched.fold(t1 :+ (name, value), t2a, cs) { cont =>
          // Match found, collect continuation (we don't have a way to use value from Send)
          (t1, t2a, cs :+ cont)
        }
    }

  def executeExprs(exprs: Seq[Process]): Seq[Process] =
    exprs.foldLeft(Seq[Process]()) {
      // System processes
      case (acc, GSystem(id, arg)) if id == "rho:io:stdout" =>
        // Standard output
        println(s"> ${arg}")
        acc
      case (acc, p) => acc :+ p
    }

  import scala.annotation.tailrec

  /**
    * Reductions of our Simple Rholang language.
    * When Send channel matches Receive channel, receive continuations are evaluated.
    * TODO: value from Send is not used currently. We need more machinery to bind it in Receive.
    */
  @tailrec
  def eval(proc: Process): Process =
    proc match {
      case Par(ss, rs, es) =>
        // Match sends and receives
        val (sends, receives, continuations) = matches(ss, rs)

        // Execute system processes and ground terms
        val exprs = executeExprs(es)

        // Result of evaluation (reduction)
        val evalRes = Par(sends, receives, exprs)

        if (continuations.nonEmpty) {
          // Matched continuations evaluated in par with the result of reduction
          val proc = (continuations :+ evalRes).fold(Par())(par)
          eval(proc)
        } else
          // If matching has no continuations we are at the end
          evalRes
      case p => p
    }
}

import rholang._

// Implicit conversion for Process (identity)
implicit object ProcessIdentity extends ToProcess[Process] {
  def convertToProcess(x: Process): Process = x
}

// Implicit conversion for String
implicit object StringToProcess extends ToProcess[String] {
  def convertToProcess(x: String): Process = string(x)
}

// Implicit conversion for Int
implicit object IntToProcess extends ToProcess[Int] {
  def convertToProcess(x: Int): Process = int(x)
}

// Binary infix functions
implicit class syntaxRholang[A](private val p1: A) extends AnyVal {
  // Defines pipe `|` as nicer syntax for `par`
  // `|` is not the best choice, already defined for numbers. `||` maybe?
  //   a | b      ==>  par(a, b)
  //   a | b | c  ==>  par(par(a, b), c)
  def |[B: ToProcess](p2: B)(implicit to: ToProcess[A]): Process = par(p1, p2)

  // Defines tilde `~` as nicer syntax for tuple (how to lift Scala tuple?)
  //   a ~ b      ==>  t(a, b)
  //   a ~ b ~ c  ==>  t(t(a, b), c)
  def ~[B: ToProcess](p2: B)(implicit to: ToProcess[A]): Process = t(p1, p2)
}

/**
 * Our first Simple Rholang program.
 */
val prog1: Process = {
  val p1 = send(nil | 42 | "A", 42) | send("A" | 42, 11)
  val p2 = send("B", 42) | send("B", 4222)
  val p3 = receive("B", receive("B", 444)) // | receive("B", 444)
  val p4 = send("C", 42) // | receive("C", sys("rho:io:stdout", "CONT PRINT"))
  val p5 = sys("rho:io:stdout", "Special channel!" ~ 42)
  val p6 = receive("A" | 42, sys("rho:io:stdout", "In continuation!"))

  p1 | p2 | p3 | p4 | p5 | p6 | nil
}

val prog2 = "Process String in par with Int" | 42

// P | Q  ==  Q | P

val prog3 = send("A" | "B", 42) // sends = Seq("A", "B")
val prog4 = send("B" | "A", 42) // sends = Seq("A", "B")

val prog3_4 = prog3 == prog4

val isSetSame = Set("A", "B") == Set("B", "A")

val s1 = Set("A", "B")
val s2 = Set("B", "A")

val li1 = List("A", "B").sorted
val li2 = List("B", "A").sorted

val isListSame = li1 == li2

val printExample = sys("rho:io:stdout", "Example continuations!")

// @{"A" | "B"}!(42) | for (_ <- @{"A" | "B"}) { *printExample } | @"C"!(42)

val prog5 = send("A" | "B", 42) |
  receive("A" | "B", printExample) |
  send("C", 42)

val prog5_res = eval(prog5)

/**
 * Evaluate the program and get remaining processes (state inside Par).
 */
val res = eval(prog1)