Last active
December 29, 2020 20:25
-
-
Save tgrospic/25ab1c3767d09e682e03f21ab6c22c32 to your computer and use it in GitHub Desktop.
Simple Rholang with higher-order channels and continuations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment