Home » forums » LtU Forum

A stackless runtime environment for a Pi-calculus

Frédéric Peschanski and Samuel Hym, A stackless runtime environment for a Pi-calculus, 2nd ACM/Usenix International Conference on Virtual Execution Environments.

From the abstract:

...We present in this paper the CubeVM, an interpreter architecture for an applied variant of the Pi-calculus, focusing on its operational semantics. The main characteristic of the CubeVM comes from its stackless architecture. We show, in a formal way, that the resource management model inside the VM may be greatly simplified without the need for nested stack frames. This is particularly true for the garbage collection of processes and channels. The proposed GC, based on a reference counting scheme, is highly concurrent and, most interestingly, does automatically detect and reclaim cycles of disabled processes...
The slides that accompany the paper can be found here. A little more information on the CubeVM, including an early release of the source code, can be found on the project website.

By Allan McInnes at 2006-10-31 04:05 | LtU Forum | previous forum topic | next forum topic | other blogs | 11252 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

A note on compilation

If you decide to download the CubeVM source, the following from an email by Frédéric Peschanski on the moca-announce list may prove helpful:

The configure scripts do not work, so you'll need to type make -f Makefile.old (and you'll also need gcc as well as flex/bison).

For the moment, the accepted language is the pure, untyped and polyadic pi-calculus (with value-passing). We think the interpreter is quite fast (for an interpreter) but there's still room for improvement, as suggested by the paper. Everything is ready to take snapshots of the VM (efficient strong migration was our original motivation) but the feature is not yet exploited.

We are now working on the second version with (hopefully) major performance improvements (a new scheduler code and a JIT is on the way) and new features (most notably type checking).

By Allan McInnes at Tue, 2006-10-31 04:30 | login or register to post comments

still doesn't build.

I was still not able to build it. Problems with the bison grammar.

bison -t -d -v  cubeparse.y
cubeparse.y contains 120 shift/reduce conflicts.
gcc -c -O2 -DNDEBUG -DYYDEBUG=1 -DYYERROR_VERBOSE=1  -I ./lib/eXdbm cubeparse.tab.c -o cubeparse.tab.o
cubeparse.y:101: error: conflicting types for 'YYSTYPE'
cubeparse.tab.h:6: error: previous declaration of 'YYSTYPE' was here
/usr/share/bison.simple:138: error: conflicting types for 'yylval'
cubeparse.tab.h:42: error: previous declaration of 'yylval' was here
make: *** [cubeparse.tab.o] Error 1

By James McCartney at Wed, 2006-11-01 19:58 | login or register to post comments

Thanks for the heads up

That's a shame. I hadn't got around to trying to compile the CubeVM yet, but was looking forward to playing with. I may send an email to the authors, pointing them to this thread and letting them know that there are problems with compilation. Thanks for the heads up.

By Allan McInnes at Thu, 2006-11-02 04:23 | login or register to post comments

More detailes compilation instructions

Hello all,

Thanks for your interest in the CubeVM... I've just checked again the compilation instructions. Here's what I do (within the source directory):

cd lib/eXdbm
./configure
make

cd ../..
make

and copilot gets compiled on my (somewhat old) linux machine...
gcc is 4.0.2 20050808
flex is 2.5.31
bison is 2.0

Maybe you are using an either more recent or older version
of bison... That could be the problem.

Cheers,
Fred.

By fredokun at Thu, 2006-11-02 09:12 | login or register to post comments

thanks

updating bison fixed it.

By James McCartney at Thu, 2006-11-02 12:41 | login or register to post comments

Interesting...where can I find more information?

The .pdf contains a presentation with lots of formulas and very little text; the ACM paper is not accessible and the project web site is under construction...is there a way to know more about this? a link to a document that contains an analysis without too many formulas would be greatly appreciated (in order to understand what it is all about)...

By Achilleas Margaritis at Tue, 2006-10-31 15:47 | login or register to post comments

More info

It turns out that Samuel Hym has made the paper available on his website. I've updated the links above accordingly. I'm not sure if there's any information available beyond that, at least until the project website gets updated.

By Allan McInnes at Wed, 2006-11-01 04:33 | login or register to post comments

infos about the CubeVM

Sadly, for the moment the paper is almost everything we have for the CubeVM. At least we give some more detailed information with the C source code (but who wants to read C source ? especially on lambda ;-). And it was coded in a rush so it's not a source code on may really count on (even if we use a somewhat defensive programming approach).

I think the CubeVM is for the moment mostly useful to understand and experiment with the expressivity of the pi-calculus. That is, you can take all the (untyped) examples in Milner's or Sangiori's book, encode them quite easily with the cube syntax, and ... see what happens. I think some of the provided examples are also interesting, e.g. the NQueens encoding (with a backtrack channel), the SC and RDV concurrency patterns, the dataflow examples also. I would like, also, to encode nice synchronous patterns e.g. for the game of life or other simulations...

Note that there is a subtle bug with the interpretation of sum processes because of (too) early commitments... Can you find a counter-example ?

The objectives of the project go a little bit further... and are not all scientific (The CubeVM is also my spare-time programming project)...

We want to create a full-featured scripting language based on the Pi-calculus. At the language level, we are now designing the type system for the cube. We also want to add join patterns as in the join-calculus. I recently got an idea about a scheduler algorithm that would allow to mix pi and join constructs in an (hopefully) efficient way (plus it would fix the early commitments bug for sums).

Scientifically speaking, most of the current work is dedicated to the static analysis and then compilation (probably to C code, or maybe using GNU lightning or a similar JIT environment) of processes in chain reaction forms, as described in the paper.

If people are interested in anything among these, I can start a wiki page for it (or maybe there's something for that kind of purpose on lambda ?).

Feel free to contact us, or keep posting on lambda, I'll check regularly.

Cheers,
Fred.

By fredokun at Thu, 2006-11-02 09:53 | login or register to post comments