Who Am I?

Hi, my name is Rohan Mehta, and I am a high schooler (11th grade) at Moravian Academy

I have an intense passion for computer science, and how it intersects physics, mathematics, and biology

So I find the Wolfram Language to be pretty darn amazing!

On the side, I enjoy reading dystopian fiction, playing golf and tennis, and writing on my blog: https://mehta-rohan.com/

Today I’m going to be sharing with you some work I completed at this year’s Wolfram High School Summer Camp

This work is ongoing, but I’ll be taking you through some of the most interesting results, so far!

A Brief Introduction To the π-calculus

Concurrent vs. Sequential vs. Parallel Programming

The simplest, functional, sequential programming language is the λ-calculus

Less widely known is the π-calculus, which aims to be the simplest, functional, concurrent programming language

Note: the π-calculus deals with concurrent programs only, not parallel programs (there is a BIG difference!)

Concurrency: multiple different tasks are competing for compute vs. Parallelism: there is enough compute for all tasks to be executed simultaneously

In other words, concurrency can happen even we have only a single computing device whereas parallelism always needs more than one

Concurrency is a good way to model multiple agents competing for some finite resource (e.g., ticket sales, client-server querying, even biological reactions!)

A Theory of Mobile Processes

The π-calculus was created by Robert Milner as a way to model mobile processes

Mobile processes are processes that can change their connections with one another, as well as send information over those connections

The π-calculus introduces a strange abstraction to help facilitate this mobility: “names”

Names are “addresses” referring to a physical place as well as a piece of information that can be used to locate that place

They are both the data processes exchange with one another, and the place processes navigate to to get that data

This mobility makes the π-calculus extremely expressive

The Syntax of the π-Calculus

Send and Receive operators exchange names between processes (at different names)

Choice operators allow a process to randomly select one of two actions

Replicate operators continually spawn new instances of their (programs with never terminate)

A "Mild" π-Calculus Program

Define three processes in our π-calculus syntax, using only Send and Receive commands

p1 = {PiSend[z, x], PiTerminate[]}; 

p2 = {PiReceive[y, x],
      PiSend[x, y],
      PiReceive[y, x],
      PiTerminate[]};
     
p3 = {PiReceive[v, z],
      PiSend[v, v],
      PiTerminate[]};

Compose these three processes in parallel

mildProgram =  {p1, p2, p3};

A "Medium" π-Calculus Program

Define a new set of processes, making use of the Choice operator

p1 = {{PiSend[x, b]} || {PiSend[x, e]},
       PiTerminate[]};

p2 = {PiReceive[x, b],
      PiSend[x, c],
      PiTerminate[]};

p3 = {PiReceive[x, c],
     {PiSend[x, d]} || {PiSend[x, f2]},
      PiTerminate[]}; 

p4 = {PiReceive[x, e],
      PiSend[x, f1],
      PiTerminate[]};

p5 = {{PiReceive[x, f1 ]} || {PiReceive[x, f2]},
       PiSend[x, g],
       PiTerminate[]};

p6 = {PiReceive[x, d],
      PiSend[x, h1],
      PiTerminate[]};

p7 = {PiReceive[x, g],
      PiSend[x, h2],
      PiTerminate[]};

p8 = {{PiReceive[x, h1]} || {PiReceive[x, h2]},
       PiSend[x, i],
       PiTerminate[]};

Compose them in parallel

mediumProgram = {p1, p2, p3, p4, p5, p6, p7, p8};

A "Spicy" π-Calculus Program

Generate a new program by wrapping all constituent processes of the previous program in replicators

spicyProgram = PiReplicate/@mediumProgram;

Evaluating a π-calculus Program

Choosing a Process to Evaluate

There are many possible statements to evaluate first (this is the π-calculus’ signature non-determinism at work)

To reduce a given program, we must identify the set of valid statements, and then randomly evaluate a statement from this set

Select processes which don't begin with a "Receive" operation

activeProcesses[processes_] := Module[{pattern1, pattern2,indexed, active},
	pattern1 = {PiReceive[_,_],___};
	pattern2 = {pattern1||pattern1..,___};
	indexed  = MapIndexed[Flatten[{#1,#2}]&,processes];
	active=Cases[indexed,Except[pattern1|pattern2]] ;
	
	If[Head@#[[1]]===Or, 
	   Table[Join[#[[1]][[n]], Rest@#],{n, Length@#[[1]]}], 
	   {#}]&/@active]//Flatten[#,1]&

Sending and Receiving

Sending and receiving information is how a given statement in the π-calculus is evaluated

The Wolfram Language’s symbolic nature and aptitude for pattern matching makes it possible to implement this logic very elegantly

Extract what is being sent and where it is being sent from a given Send command

extractSent[sendCommand_] :=
	({sendCommand} /. PiSend[sent_, to_] :> 
		<|"sent" -> sent, "to" -> to|>)[[1]];

Determine all processes which are receiving on the channel that is being sent over

allReceivers[sendData_, processes_] := 
	Module[{indexed, pattern1, pattern2, pattern3},
		indexed  = MapIndexed[Flatten@{#1,#2}&, processes];
		pattern1 = PiReceive[received_, sendData["to"]];
		pattern2 = {pattern1, rest___, index_};
		pattern3 = {___||{pattern1}||___, rest___, index_};
		Cases[indexed, pattern2|pattern3 -> {received, {rest}, index}]]

Update the chosen receiver with the sent information

initiateSend[sendData_, receiver_, processes_] :=
	ReplacePart[processes, receiver[[2]] /. 
		receiver[[1]] -> sendData["sent"], receiver[[3]]]

Updating the Program

To fully reduce a given program, we must repeat the two aforementioned steps until we arrive at a program state that is irreducible

Of course, if the program makes use of Replicators, it will never terminate, and so we can only compute its reduction after a finite number of steps

Given a send command, extract the send data and update a receiver

updateWithSend[chosenProcess_, newProcesses_, possibilities_] := 
	Module[{sendData, receivers},
		sendData = extractSent@(chosenProcess[[1]]);
		receivers = allReceivers[sendData, newProcesses];
		If[possibilities,
			If[receivers == {},
				{newProcesses},
				initiateSend[sendData, #, newProcesses]&/@receivers],
			If[receivers == {},
				newProcesses, 
				initiateSend[sendData, RandomChoice@receivers, newProcesses]]]]

Given any command, evaluate it and update the program

updateStep[processes_, chosen_, possibilities_: False, track_: False] := 
	Module[{newProcesses, sendData, result, receivers},
		newProcesses = ReplacePart[processes, chosen[[2;;-2]], chosen[[-1]]]; 
		newProcesses = If[chosen[[1]][[0]]===PiSend, newProcesses, processes];			  				      
		result = 
			Which[chosen[[1]][[0]]===PiSend, 
				  updateWithSend[chosen, newProcesses, possibilities],
				  chosen[[1]][[0]]===PiReplicate,
				  Append[newProcesses, chosen[[1]][[1]]]
				  ] /. {PiTerminate[]}|{}|Null -> Nothing;

	 If[track,
		If[chosen[[1]][[0]]===PiReplicate,
			{processes -> {result}, chosen},
			{processes -> result, chosen}], 
		result]]

Randomly choose a valid command the update the program

randomUpdateStep[processes_] := 
	Module[{active}, 
	active =activeProcesses@processes;
	If[active=={},
		processes, 
		updateStep[processes, RandomChoice@activeProcesses@processes]]]

Completely reduce a program, or reduce an irreducible program some finite number of steps

reductionRule[processes_, stepCount_:0] :=
	If[stepCount==0,
		NestWhileList[randomUpdateStep, processes, (activeProcesses@#!={})&],
		NestList[randomUpdateStep, processes, stepCount]]/.{}->Nothing

Let’s Evaluate some π-calculus Programs!

simplePrograms = {mildProgram, mediumProgram};

Reduce our terminating programs

reductionRule/@simplePrograms

Reduce our non-terminating program by 100 steps

reductionRule[spicyProgram, 100]

Some Vain Pretty-Printing...

We just created a functioning π-calculus interpreter!

But it’s basically impossible to parse the jumbled-up mass of π-calculus code that it’s returning...

We need to come up with a better way to visualize this output

Converting to the Canonical π-calculus Syntax

While the canonical π-calculus syntax is rather arcane, it is also very compact, so we want to employ it in our visualizations

To do this, we will need to map each “atom” of our syntax to its corresponding “atom” in the canonical syntax

Convert custom π-calculus syntax to canonical syntax for a single process

processPrettyPrint[process_] := 
	Module[{replicateConvert, orConvert, sendConvert,receiveConvert, converted},
		replicateConvert = PiReplicate[{a__}] :> "!"<>"("<>processPrettyPrint[{a}]<>")";
		orConvert = a__||b__ :> (processPrettyPrint[a]<>"+"<>processPrettyPrint[b]);
		sendConvert = PiSend[sent_, to_]:>(ToString@to<>"⟨"<> ToString@sent <>"⟩");
		receiveConvert = PiReceive[received_, at_]:> (ToString@at<>"("<>ToString@received<>")"); 
		converted = process /.{sendConvert, receiveConvert, orConvert,replicateConvert, PiTerminate[]->"0"};
		
		If[converted[[0]]===List,
			StringRiffle[converted, "."],
			converted]]

Convert custom π-calculus syntax to canonical syntax for an entire program, and then style it

processesPrettyPrint[processes_, color_] :=
	Framed[Column[
		Style[Framed[processPrettyPrint[#]<>"|"],Background->color]
		&/@processes]]

lightColorList = ;

Display the fully-evaluated form of our third, non-terminating program in the canonical syntax

processesPrettyPrint[#[[-1]], RandomChoice@lightColorList]&/@reductionRule/@simplePrograms // Row[#, "    "]&

Visualizing Program Evolution in this Syntax

If we want to get a bit more fancy, we can try to visualize each step of the program reduction in this manner, as well

Notice the different trends followed by each our our different programs (do they grow or shrink?)

Convert custom π-calculus syntax to canonical syntax after each reduction step

visualizeEvolution[processes_, stepCount_: 0] := Module[{randomColor},
	randomColor=RandomChoice@lightColorList;
	(processesPrettyPrint[#, randomColor]&/@reductionRule[processes, stepCount])]

dynamicallyVisualizeEvolution[processes_, stepCount_: 0] :=
	FoldList[Row[{#1,#2},"  ⟶  "]&, visualizeEvolution[processes, stepCount]] // ListAnimate[#, Alignment -> {Left,Center}]&

dynamicallyVisualizeEvolution/@simplePrograms // Column

dynamicallyVisualizeEvolution[spicyProgram, 4]

Visualizing the Multiway System of Reductions

Remember, the π-calculus is non-deterministic, so these visualizations represent only one (of potentially many) possible outcomes

Is there some way for us visualize all the possible reduction states of a given program, at once?

YES! It’s known as a Multiway System (https://www.wolframscience.com/nks/p209--multiway-systems/)

Determine All Possible Next States

Instead of randomly choosing an expression to evaluate, we now need to evaluate all valid expressions

This will allow us to compute all possible next states for our program

Generate all possible evaluation outcomes for a given π-calculus program and turn them into the connections of a graph

allPossible[processes_] := updateStep[processes,#, True, True]&/@(activeProcesses@processes)

helper1[processes_] := ((allPossible/@#[[1]][[2]])&/@processes) // Flatten[#,2]&
helper2[processes_] := (processes[[1]][[1]]->#)->Placed[processes[[2]][[1]],3/4]&/@processes[[1]][[2]]
helper3[processes_] := helper2[#]&/@processes

generateConnections[processes_, stepCount_:-1] :=
	If[stepCount==-1,
		(helper3/@NestWhileList[DeleteDuplicates@*helper1, allPossible@processes,#1!=#2&, 2]),
		(helper3/@NestList[DeleteDuplicates@*helper1, allPossible@processes,stepCount])] // Flatten[#,2]&

Generate (and Graph) the Multiway System of Reductions

If we recursively do this until a program terminates, then we end up with a graph

Each node in this graph represents a distinct program state, and each edge represents the π-calculus statement which was evaluated the get from the previous program state to the current program state

This graph IS the Multiway System! Behold:

Graph these connections, and build up the Multiway System

graphMultiwaySystem[connections_, small_:True]:= Module[{newConnections},
	newConnections = (# /. ((a_ -> b_) -> c_) :> ((Column@(processPrettyPrint/@(a)) -> Column@(processPrettyPrint/@(b))) -> c)&/@connections);
	Graph[((#[[1]])&/@(newConnections)) // DeleteDuplicates, VertexLabels->If[small,Placed["Name",Tooltip],None],EdgeLabels->If[small,newConnections,None],EdgeLabelStyle->If[small,Directive[Black,Bold,FontSize->Scaled[0.032],FontFamily->"Courier",Background->RandomChoice[lightColorList]],None]]]

generateMultiwaySystem[processes_, stepCount_:-1, small_:True]:=
	processes//generateConnections[#,stepCount]&//graphMultiwaySystem[#,small]&

generateMultiwaySystem/@simplePrograms

Visualizing the Evolution of these Multiway Systems

As before, we can try to visualize each reduction step to get a more interactive account of what’s happening

Generate a list of Multiway Graphs, each representing a single reduction step

dynamicallyGenerateMultiwaySystem[processes_, stepCount_:0, small_:True]:=
	graphMultiwaySystem[#, small]&/@Table[generateConnections[processes, i], {i,0,stepCount}] // ListAnimate[#, Alignment -> Center]&

dynamicallyGenerateMultiwaySystem[mediumProgram, 5, True]

dynamicallyGenerateMultiwaySystem[spicyProgram, 3, False]

Notice some of the prevalent motifs in these graphs:

Divergence: If a path diverges, it means that a single program state can lead to two or more different program states

Convergence: If multiple paths converge, it means that two or more distinct program states can simplify into a single program state

Approximate Symmetries: Programs with Replicators have a rough symmetry, because they can choose to Replicate at each step

Clusterings: This symmetry is characterized by periodical clusters, each of which represents a single “Replication branch”

"Mining the Computational Universe" of Simple π-calculus Programs

The π-calculus programs we’ve been playing around with so far are pretty arbitrary

They only represent a small sampling of the whole space of π-calculus programs

In a NKS-like spirit, we can randomly “mine” this computational space and try to unearth its underlying structure

Generating a Random π-Calculus Program

For these programs, we will limit our vocabulary of names to {a,b,c}

Even with this limitation, the programs we can generate are still very complex!

Then, we randomly decide which type of statement we should include, compose these statements into a process, and stack these processes into a program

I.e., a 2x2 program is a program with two processes, each of which is two statements long

Generate a random m by n π-calculus program

names = {a,b,c};

makeSend[] := PiSend[RandomChoice@names, RandomChoice@names]
makeReceive[] := PiReceive[RandomChoice@names, RandomChoice@names]
makeSendOrReceive[] := (RandomChoice@{makeSend, makeReceive})[]
makeComposite[] := {makeSendOrReceive[]}||{makeSendOrReceive[]}
makeProcess[] := (RandomChoice[{0.4,0.4,0.2}->{makeSend, makeReceive, makeComposite}])[]
makeReplicate[process_, probability_] := If[RandomChoice@Range@10<=probability, PiReplicate[process], process]

randomlyGenerateProcess[processLength_] :=
	Append[Table[makeProcess[],{n, processLength}], PiTerminate[]]

randomlyGenerateWithSend[processLength_] :=
	Insert[randomlyGenerateProcess[processLength-1],makeSend[],1]

randomlyGenerateProcesses[processesLength_, processLength_, replication_:False] := Module[{sender},
	sender = randomlyGenerateWithSend[processLength]//If[replication,makeReplicate[#,5], #]&;
	Insert[Table[randomlyGenerateProcess[processLength]//If[replication,makeReplicate[#,5], #]&,{n, processesLength-1}],sender,1]]

randomlyVisualizeEvolution[processes_, stepCount_:5] :=
	If[Cases[processes, PiReplicate[__]]!={},
		visualizeEvolution[processes, stepCount],
		visualizeEvolution[processes]]

randomlyGenerateGraphs[processes_, stepCount_:5]:=
	If[Cases[processes, PiReplicate[__]]!={},
		generateMultiwaySystem[processes, stepCount, False],
		generateMultiwaySystem[processes,-1,False]]

makeExperiment[processesLength_, processLength_, replication_, amount_] := Module[{experiments},
	experiments = Table[randomlyGenerateProcesses[Range[processesLength], Range[processLength], replication], {n, amount}];
	Parallelize[(randomlyGenerateGraphs/@experiments)]//Partition[#, 10]&//Grid]

Simulations of Terminating Programs

For this set of simulations, we will only look at terminating programs (i.e., those that don’t include Replicators)

Visualize the evolution of 10 2x2 programs

randomlyVisualizeEvolution/@Table[randomlyGenerateProcesses[2,2], {n,10}]

Visualize the Multiway Graph of a random 2x2 program

randomlyGenerateGraphs[randomlyGenerateProcesses[2,2,False]]

Wow, that’s pretty complicated right! And only for a 2x2 program!

Even though the the ten 2x2 programs we generated earlier reduced in only two or three steps, we have to remember that those reduction-paths were only one of many possible reduction-paths

The Multiway System, one the other hand, shows us all possible reduction-paths, and as a result, is noticeably more complex!

These two pieces of do corroborate; after all, any given path of in our Multiway System only lasts two or three segments, it’s just that there are many such paths

Generate 50 2x2 π-calculus programs and graph their Multiway Systems

makeExperiment[2,2,False,50]

Notice the juxtaposition of simplicity and complexity!

Generate 50 3x3 π-calculus programs and graph their Multiway Systems

makeExperiment[3,3,False,50]

Generate 50 4x4 π-calculus programs and graph their Multiway Systems

makeExperiment[4,4,False,50]

Here are some of the most interesting Multiway Systems I was able to generate (the first represents a 2x2 program, while the second is of a 4x4 program):

Simulations of Non-Terminating Programs

We can do the same thing for programs with Replicators too

As we might suspect, they grow much bigger much faster!

Generate 50 2x2 non-terminating π-calculus programs and graph their Multiway Systems after five steps

makeExperiment[2,2,True,50]

Generate 50 3x3 non-terminating π-calculus programs and graph their Multiway Systems after five steps

makeExperiment[3,3,True,50]

Again, here are some of the most interesting Multiway Systems I was able to generate (for non-terminating programs, this time):

The Connection To Petri Nets

We can connect all of these ideas to another type of mathematical structure, known as the Petri Net

Petri Nets provide another (albeit more constrained) way of representing concurrent processes

What’s In a Petri Net?

Traditionally, Petri Nets are composed of three things: tokens, places, and transitions

I say traditionally, because more complicated Petri Net variants do exist (e.g., Colored Petri Nets, Stochastic Petri Nets, etc.)

At each discrete timestep, transitions dictate the movement of tokens from place to place; but only one transition (of potentially many) can fire per timestep

Just like in the π-calculus, where we must choose one of potentially many valid statements to reduce

As such, Petri Nets are also non-deterministic!

They were originally invented to model chemical reactions, but have since been applied more generally

Two example Petri Nets are shown above; notice how the second is able to very succinctly model creation/splitting of water

The Big Idea: π-calculus Programs ARE Evolving Petri Nets

So, here’s a question: if Petri Nets and the π-calculus are both fundamentally doing the same thing (modelling concurrency), then how do we translate from one to the other?

E.g., which π-calculus program encodes the two Petri Nets shown above?

It turns out that while any “static” π-calculus program has a corresponding Petri Net, each reduction-state of a π-calculus program can have a different associated Petri Net

Remember the π-calculus has a notion of mobility, or changing connections, that Petri Nets do not!

As such, evaluating  corresponds to updating the edges of its associated Petri Net

A π-calculus program describes a Petri Net whose edges CHANGE WITH TIME!

As a first step, let’s try and visualize the corresponding Petri Net for the unreduced form of a π-calculus program

Transform an unreduced π-calculus program into its associated Petri Net

breakDown[process_] :=
	Table[If[n[[0]]===Or,Level[n,1],n] ,{n,process/.PiReplicate[stuff__]->stuff}]//Flatten//DeleteDuplicates

graphFormat[processes_] := 
	Module[{programState, processNames, rule1, rule2,rule3},
		programState = Cases[#,type_[_, place_]->{type, place}]&/@((breakDown/@processes)//DeleteDuplicates);
		processNames = Table["p"<>ToString@n, {n, Length@programState}];
		rule1 = (process_->commands_:{{___}..}):> (process->#&/@commands);
		rule2 = (process_->{PiSend, place_}) -> (process->place);
		rule3 = (process_ -> {PiReceive, place_}) -> (place->process);
		{#/.{rule2, rule3}&/@(Thread[processNames->programState] /. rule1), processNames}]

renderGraph[processes_]:= 
	Module[{edges, processNames,otherNames, vertexShapes, vertexColors, otherColors}, 
			{edges,processNames} = graphFormat[processes]//DeleteDuplicates;
			otherNames = DeleteCases[edges /.(a_->b_):>{a,b}//Flatten,Alternatives@@processNames] ;
			vertexShapes = Table[Annotation[n, VertexShapeFunction->"Square"], {n,processNames}];
			vertexColors = Table[n->Red, {n, processNames}];
			otherColors=Table[n->Pink, {n, otherNames}];
				Graph[vertexShapes,Flatten[edges],VertexStyle->Join[vertexColors,otherColors],GraphLayout->"SpringEmbedding",VertexSize->Large,VertexLabels->Table[n->Placed[n,Center],{n,otherNames}],VertexLabelStyle->Directive[Black,Bold,FontSize->Scaled[0.025],FontFamily->"Courier"]]]]

renderGraph@mediumProgram

Look familiar?

We can also try and visualize what the evaluation process of a π-calculus program looks like, by using Petri Nets as a proxy

This offers another insight, as well: our Multiway System graph is actually describing transitions (morphisms?) between different Petri Nets!

Each execution of a π-calculus statement updates the Petri Net that is isomorphic to our program state

Reduce a π-calculus program, and visualize the corresponding Petri Net at each reduction state

{renderGraph/@(reductionRule@mediumProgram)//Manipulate[#[[n]],{n,1,Length@#,1}]&, dynamicallyGenerateMultiwaySystem[mediumProgram,5,True]}

Questions Yet to be Answered

We’ve really only scratched the surface of this relationship; there are many more questions to be asked!

How do Replicators fit into this idea (as well as scoping structures, which we haven’t even talked about yet!)

How do these ideas fit into the mathematical conception of Petri Nets (which have been extensively studied from a Category Theory perspective)?

How much more expressive does this make the π-calculus? What types of situations can it model that a single, unchanging Petri Net can’t?

How does these ideas fit in with the Multicomputation paradigm (https://writings.stephenwolfram.com/2021/09/even-beyond-physics-introducing-multicomputation-as-a-fourth-general-paradigm-for-theoretical-science/)?

The short answer to these questions: I’m not completely sure!

Although I do have a few inklings!

The (slightly) long(er) answer: I’m going to be trying to find out!

Conclusion

That’s a lot of stuff to remember! What does it all mean again?

A Short Recap

The π-calculus is the slightly more esoteric cousin to the λ-calculus; it is a minimalist, functional, way of modelling concurrent computation

It has a notion of mobility, can describe both terminating and non-terminating programs, and is very useful for describing real-world situations with multiple, competing agents

It is non-deterministic, and we can visualize its non-determinism using Multiway Systems

Even simple π-calculus programs, while commensurately simple in a single reduction-path, generate very complex Multiway Systems

They are simple in the first order, but complex in the second order!

A given π-calculus program has an isomorphic Petri Net, and reducing it corresponds to updating the edges of that Petri Net

This is the π-calculus’ mobility at work

This also probably corresponds to some form of Multicomputation

Further Work

Do some programming: Add the entire π-calculus syntax to my current implementation (e.g., scoping mechanisms)

Do some math: Figure out how this is all expressed in the math of Category Theory, and how it fits together with the ideas of Multicomputation

Do some chemistry: Apply these ideas to see if a new way of modeling chemical reactions can be developed (i.e., if Petri Nets = chemical reactions nets, π-calculus programs = ?)

I find chemical reaction nets to be VERY interesting!

Thank You For Listening!

I hope you found this talk to be interesting!

If you did, and would like to talk to me about these ideas some more, please consider reaching out at rohanm1024@gmail.com

My own knowledge of these concepts is still pretty incomplete, so I would be super excited to learn from those who are more experienced!

THANK YOU!