Phases

1. Parsing
2. Normalization
3. Reduction

Parsing

Parsing of the program consists of two phases: lexing and parsing. Lexer takes the input stream and slices it into tokens ("meaningful words"). Parser reads a string of tokens and produces a syntax tree. For lexer we use JFlex. Parsing is carried out by CUP. The outputs are java classes representing the grammar. Grammar of rholang is defined using BNFC.

Normalization

Input to the normalization phase is the output from the parsing phase; it's an AST representing the rholang program. Normalizer produces terms where processes in parallel have been binned according to their type (sends, receives, expressions).

Another necessary step in the normalization phase is sorting. Because rholang's | is commutative, to normalize properly we need to sort terms. Sorting happens just after normalization (if it was done before, normalization would need to preserve ordering) and after substitution.

Reduction

Consists of two phases: substitution and evaluation. We go through the program recursively, substituting and then evaluating the terms. Substitution takes the term and replaces bound variables in it with their actual values from the environment. During evaluation terms are reduced. It's best to illustrate with an example:

Assuming there is an x=5 in the environment, rholang program

@{10+5+x | @x!(5)}!(Nil)

goes through the following steps:

1. Evaluate channel of the send -- {10+5+x | @x!(5)}
   1. Substitute: {10 + 5 + 5 | @5!(5)}
   2. Reduce: {20|@5!(5)}
2. Evaluate body of the send (no evaluation required)
3. Evaluate send
   1. Place the send in the RSpace
      
      

The spatial matching algorithm deserves a special mention here. It is used for matching targets with patterns. Spatial matching is performed in

1. for (<name pattern> <- <channel>) { <process> }
2. match <process> { <process pattern> => <process> }
3. <process> matches <process pattern>

For more information of patterns and spatial matching algorithms please consult Rholang tutorial.

Interaction with RSpace

"RSpace is the beating heart of RChain" -- Anonymous

The interaction between rholang's send-s and receive-s happens with the help of RSpace. When a Send is evaluated, RSpace checks whether there is a matching continuation waiting on the Send-s channel in the tuplespace. If there's no continuation on the channel, it stores the Send in the tuplespace. If there is, it validates whether data matches the pattern guard of the continuation. If the match is successful then the continuation is executed. Similarly, when evaluating a Receive, we search for a matching Send in the tuplespace.

Examples

1. Send then Receive

• Start with empty tuplespace.
• Evaluate send: @0!(1).
  • no receive reading from @0 channel in the tuplespace - store the send.
• Tuplespace state: @0!(1).
• Evaluate receive: for(x <- @0) { @1!(x) }:
  • There is a send on @0 channel in the tuplespace, retrieve it.
  • Validate that the pattern guard of the continuation matches data being sent on the channel. Since our pattern is a free variable (x) it will match anything.
  • Substitute occurrences of x in the continuation with the data received and execute. This will result in sending 1 over the @1 channel.
• Tuplespace state: @1(1).

2. Receive then Send

• Start with empty tuplespace.
• Evaluate Receive: for(@{Nil /\ x} <- @0) { @x!(10) }.
  • no send on @0 in the tuplespace - store the receive.
• Tuplespace state: for(@{Nil /\ x} <- @0) { @x!(10) }.
• Evaluate Send: @0!(10).
  • There is a receive listening on @0 but it's waiting for a @Nil being sent, so it doesn't match the data we send (10).
  • Store new send in the tuplespace.
• Tuplespace state: for(@{Nil /\ x} <- @0) { @x!(10) } | @0!(10).
• Evaluate Send: @0!(Nil).
  • send matches the receive in the tuplespace, retrieve it.
  • Bind data sent over from channel @0 to `x` and substitute all occurrences of x in the body of the continuation with bound data
  • Evaluate body @Nil!(10)
• Tuplespace state: @Nil!(10) | @0!(10)

Unforgeable names

Unforgeable names are very much like object references in languages like Python or Java.  Internally, they act like pointers, but there's no way in the language to supply an integer and get a reference to the object living at that address.  An unforgeable name is implemented internally as a 256-bit identifier, and that identifier is visible on the blockchain, but there is no language production that takes 256 bits and returns the corresponding name.  Unforgeable names are created with the new x in {...} production. The only way to get hold of an unforgeable name is to be in the lexical scope of that name or to receive it as part of a message. The algorithm used for generating the 256-bit random numbers is based on Blake2b512.

Cost Accounting

Every Rholang program has a cost associated with running it. Rholang programs are charged:

• when performing a substitution. Cost is proportional to the binary size of the data after substitution 
• when performing a spatial match - overall cost is an accumulated cost of all equality checks performed on all patterns against the data being matched. This is also the case when evaluating a consume (or produce) since this will perform a spatial match in search for matching produce (or consume) which results in COMM event.
• when stored in the Tuplespace - cost is proportional to the binary size of the data being stored.