Palgol is a high-level domain-specific language for Pregel, and it currently compiles to Pregel+. Main features of this language include:

  1. Vertex-centric programming paradigm with flexible remote reads and writes
    • Highly declarative way of describing remote data access (via remote reads or writes)
    • A message-passing-based Pregel implementation is then automatically derived
  2. Highly structured way of programming + inherent support for iteration
    • The atomic Palgol programs (called Palgol steps)
    • The sequence operation naturally concatenates two Palgol programs
    • The iteration operation iteratively executes a Palgol program until some condition is satisfied
  3. Efficient compiler-generated code
    • Around 2.53% speedup to 6.42% slowdown compared to well-optimized human written code in most cases, and 30% slowdown for a few graph algorithms that benefit from voting to halt mechanism of Pregel.
    • Tested on real-world graphs using popular graph applications (PageRank, SSSP, SCC, S-V, LR, MSF)


The Compiler

The compiler requires the following environments:

  1. cmake
  2. a c++ compiler (C++11 compatible)

The following steps build the compiler:

$ cd $(top)
$ cmake .
$ make

The compiler is a single executable ./palgol

Syntax Highlighting

Vim users can enable syntax highlighting of Palgol programs (.pal files) through the following steps:

$ cp $(top)/vim/syntax/palgol.vim ~/.vim/syntax/
$ cp $(top)/vim/ftdetect/palgol.vim ~/.vim/ftdetect/

Sublime Text users can follow the following steps (work for Sublime Text 3):

  1. Open: Tool -> Developer -> New Syntax
  2. Copy the syntax file $(top)/sublime/Palgol.sublime-syntax and paste it to the opening window. Save it as Palgol.sublime-syntax in a speciefied folder, then enjoy the syntax highlighting.

Compiling and Executing Sample Applications

The Applications

A bunch of Palgol sample programs are included in this repository. They can be found in the folder: $(top)/examples/

  1. PageRank (pagerank.pal)
  2. Single-Source Shortest Path (sssp.pal)
  3. Shiloach-Vishkin Practical Pregel Algorithm (sv.pal, sv_improved.pal)
  4. Strongly Connected Components (scc.pal, scc2.pal)
  5. Randomized Bipartite Matching (bm.pal)
  6. Randomized Graph Coloring (gc.pal)
  7. Minimum Spanning Forest (msf.pal)
  8. Triangle Counting (tc.pal)
  9. Attribute Broadcasting (bcast.pal)
  10. List Ranking Algorithm (ranking.pal)

Compiling Palgol Programs

The follow command compiles a Palgol program to Pregel+ code (in C++).

$ ./palgol [-o <output>] <input>

By default, the output file is run.cpp, but the filename can be specified by the -o flag. The output source code should be compiled with two additional files:

$ ls template/
auxiliary.hpp   external.hpp

"external.hpp" is not necessary unless you use external functions in Palgol. You can read examples/msf.pal to see how to use external functions in Palgol.

Please follow the Pregel+ documentation for compiling and running the compiler-generated code. Note that the generated code uses several features of C++11, so you need to add the flag -std=c++11 in Pregel+'s Makefile.

Play with Palgol

Currently, we have published a technical report on, which is an extended version of our APLAS 2017 paper. The technical report introduces the core part of Palgol and the compilation techniques. The syntax of current Palgol (which is slightly different from what we introduced in the technical report) can be found here. A tutorial containing abundant examples and detailed explanation of the semantics can be found here.


  title={Palgol: A High-Level DSL for Vertex-Centric Graph Processing with Remote Data Access},
  author={Zhang, Yongzhe and Ko, Hsiang-Shang and Hu, Zhenjiang},
  booktitle={Proceedings of the 15th Asian Symposium on Programming Languages and Systems},


Yongzhe Zhang (Ph.D. student)
The Graduate University of Advanced Studies (SOKENDAI), Japan
National Institute of Informatics