Transcript GRAFIX: A Small Programming Language for Graphs

GRAFIX: A Small Programming
Language for Graphs
Suratna Budalakoti
CMPS203
Background:

Project Aims:
Develop an operational semantics for a graph
language.
Implement this semantics.

Motivation:
Graphs are more complex than other common data
structures. So I hoped to get a better idea of the
language implementation process.
Two layered approach:


Implement a functional programming
language for graphs.
Implement an imperative programming
language (IMP) on top.
Sample Commands:
Ct( ): Create a vertex/edge.
 Del(): Delete vertex/edge.
 Srch(): Search if a vertex/edge exists.
 Neigh(): Give the neighbor of a vertex.
Degree(): Give the degree of a node.

Other Features:

Recursive and Mutually Recursive
Functions



Neigh(Neigh(Neigh(x)))
InNeigh(OutNeigh(InNeigh(OutNeigh("x"))))
Support for Set Operations

Union, Intersection, IsEqual
Other Features( cont’d)

Wildcard Search



Srch(E(a,#,5))
Srch(E(#,#,8))
Variable storage area:


Assign(Var, Valtype value)
GetVar(Var)
Design Decisions:


GRAFIX commands (exp) were defined
as (list exp) instead of exp;exp, for
reasons of readability.
This led to problems during interfacing
with IMP. Interfacing with IMP was not
a total success.
In Hindsight:

Fortunately:


An extremely close correspondence between oCAML
and operational semantics.
Unfortunately:

There are serious readability issues involved with
oCaml code. A lexical analyser should have been
present as a third layer. That could have prevented
some unfortunate design decisions.
Thank You