DiGr: Directed Graph Processing LanguageAri GolubBryan OemlerDennis V. PerepelitsaColumbia UniversityCOMS W4115: Programming Languages and Translators22 December 2010Final Project PresentationGolub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageIntroduction to DiGrWhat can DiGr do?Represent trees, graphs, walks, (mirrors, knots, etc).Model everything from basic computer science constructs tonetwork-based problems in engineering and industry.Store information in nodes and edges without overhead orhassle.Recursively or iteratively walk and modify directed graphs inuser-specified ways.Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageIntroduction to DiGrWhat is the DiGr language / compiler like?Imperative.Compiled. Target language is C++, which is in turn compiledwith g++ and linked against the DiGr backend.Statically (and locally) scoped.Specific graph-related objects (nodes, edges, walks) on top ofa typed C-like base.Strongly typed.Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguagePrimitive types and optsIntegers, floating point numbers and strings are primitivetypes.: this is a comment :str name = "Ari"!int age!age = 22!flt gpa = 4.0! : statements end with a ! :Opts have no return types, but have in (not globally bound)and out (in-scope from the program that called them)variables.opt times two(in int n; out int doubled){doubled = n * 2!}Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageNodes and edgesThe high-level objects in DiGr are nodes and edges:node n1!node n2!n1 -> n2! : n1 and n2 are now connected :Node and edge identifiers are handles. Edges are usuallycreated anonymously:edge e = n1.outedge(0)!node target = e.innode!Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageConnection contexts and attributesAttributes are created as soon as they are referenced orassigned:node city!city.population = 60000!print(city.population)! : prints 60000 :print(city.area)! : defaults to 0 :Connection contexts efficiently create graphs, and store thehandles to the nodes in an array:node binaryTree[7] = |3->(1->0,2),(5->4,6)| !Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageCrawls and rulesA crawl is an opt run on a node, and can call a rule thattells it where to go next.crawl markNode(in int marker) {current.mark = marker!call! }Rules modify the queue of nodes to visit when called:rule followLighterEdge{edge e1 = current.outedge(0)!edge e2 = current.outedge(1)!if (e1.weight < e2.weight){ add(e1.child(0))! }else { add(e2.child(0))! }}Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageDiGr in one slidecrawl printNode() { print(current.id)! call! }: print the node id and call the rule :rule preOrder { addByFront(node.id,˜,2)! }: add up to two children, smallest id first :opt main() {node tree[5] = |3->(1->0,2),4| !tree[0].id = 0! tree[1].id = 1! tree[2].id = 2!tree[3].id = 3! tree[4].id = 4!printNode() from tree[3] with preOrder!: prints 3 1 0 2 4 :}Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageCompiler Front EndlexerparsertokensinterpreterDiGr ASTverified DiGr ASTDiGr codeDiGr AST definitionScanner turns DiGr program from standard input into tokens.Lexical correctness.Parser creates initial AST (nested OCaml tree of typedtuples). Syntactical correctness.Interpreter verifies AST. Semantic correctness.Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageStatic Semantic CheckingThe interpreter has several duties:Create global scope for opt/rule/crawl signatures.Create symbol table for all local scopes (inside functions andblocks).Check the scope of all identifiers.Check typing for all statements (recurse into expressions),including assignment, function calls, etc.After the front-end stage, intermediate representation of asensible program (instance of DiGr AST).Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageCompiler Back Endtranslator compilerC++ ASTg++C++ codeexecutableverified DiGr ASTminimal C++ AST definitionDiGr C++ backendC++ AST: stripped-down, holds intermediate representationof C++ program. A few shortcuts, but largely extensible.C++ AST assures syntactical correctness of output.Translator: converts DiGr AST to C++ AST. Does nosemantic checking.Compiler: crawls the C++ AST and outputs C++ code.g++: turns compiled DiGr code into an executable.Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageDiGr code pre-compilationrule myrule {int n = 0!while (n < current.outedges) {edge tmp edge = current.outedge(n)!if (tmp edge.mark == 1) {node destination = tmp edge.innode!add(destination)!}n = n + 1!}}crawl thecrawl() {print (current.id)!call!}Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageDiGr compiler output#include "digr.h"#include <iostream>void myrule(DiGrNode *current, deque<DiGrNode*> *returnQueue) {int n = 0 ;while(n < current->OutEdges()){DiGrEdge *tmp edge = current->getOutEdge(n);if(tmp edge->getAttribute("mark") == 1 ){DiGrNode *destination = tmp edge->inNode();returnQueue->push back(destination);}else{}n=n + 1 ;}}void thecrawl(DiGrNode *current, void (*rule)(DiGrNode*, deque<DiGrNode*>*)) {deque<DiGrNode*> *queue = new deque<DiGrNode*>();queue->pushback(current);do {current=queue->front();queue->pop front();std::cout << current->getAttribute("id") << std::endl;rule(current, queue);} while (queue->size() > 0 );}Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing LanguageDiGr Test PlanFor each test program, we have a gold standard thatexecution should output. Every build, we compile and executeall tests and compare output with the gold standard.Test atomic DiGr elements from low-level (basic types,arithmetic, function calls, etc.) to high-level (graphs,attributes, connection contexts, etc.).Test programs which integrate a wide cross-section of features.Test errors at compilation (really, the interpret stage), and atrun-time.Golub, Oemler, Perepelitsa DiGr: Directed Graph Processing
View Full Document
Unlocking...