#directed-acyclic-graph #dag #markup #graph #parser #data-structures

app deml

The Directed Acyclic Graph Elevation Markup Language

1 unstable release

0.1.0 Oct 5, 2023

#2458 in Parser implementations

MIT/Apache

180KB
424 lines

DEML (DAG Elevation Markup Language)

Warning: Experimental

Languages designed to represent all types of graph data structures, such as Graphviz's DOT Language and Mermaid JS's flowchart syntax, don't take advantage of the properties specific to DAGs (Directed Acyclic Graphs).

DAGs act like rivers. Water doesn't flow upstream (tides and floods being exceptions). Sections of a river at the same elevation can't be the inputs or outputs of each other, like the nodes C, D, and E in the image below. Their input is B. C outputs to F, while D and E output to G.

Photo of a river to illustrate how DAGs operate

DEML's goal is to use this ordering as part of the file syntax to make it easier for humans to parse. In DEML we represent an elevation marker with ---- on a new line. The order of elevation clusters is significant, but the order of nodes between two ---- elevation markers is not significant.

UpRiver > A
----
A > B
----
B > C | D | E
----
C
D
E
----
F < C
G < D | E > DownRiver
----
DownRiver < F

Nodes are defined by the first word on a line. The defined node can point to its outputs with > and to its inputs with <. Inputs and outputs are separated by |.

Dagrs

Dagrs is a library for running multiple tasks with dependencies defined in a DAG. In DEML, shell commands can be assigned to a node with =. DEML files can be run via dag-rs with the comand deml run -i <filepath>.

To compare the difference in readability, here is the Dagrs YAML example in both YAML and DEML

YAML

dagrs:
  a:
    name: "Task 1"
    after: [ b, c ]
    cmd: echo a
  b:
    name: "Task 2"
    after: [ c, f, g ]
    cmd: echo b
  c:
    name: "Task 3"
    after: [ e, g ]
    cmd: echo c
  d:
    name: "Task 4"
    after: [ c, e ]
    cmd: echo d
  e:
    name: "Task 5"
    after: [ h ]
    cmd: echo e
  f:
    name: "Task 6"
    after: [ g ]
    cmd: python3 ./tests/config/test.py
  g:
    name: "Task 7"
    after: [ h ]
    cmd: node ./tests/config/test.js
  h:
    name: "Task 8"
    cmd: echo h

DEML

H > E | G = echo h
----
G = node ./tests/config/test.js
E = echo e
----
F < G = python3 ./tests/config/test.py
C < E | G = echo c
----
B < C | F | G = echo b
D < C | E = echo d
----
A < B | C = echo a

Mermaid JS

To convert DEML files to Mermaid Diagram files (.mmd) use the command deml mermaid -i <inputfile> -o <outputfile>. The mermaid file can be used to generate an image at mermaid.live

mermaid js flowchart image of the river DAG

Goals

  • Put my idea for an elevation based DAG representation into the wild
  • Run DAGs with dag-rs
  • Convert DEML files to Mermaid Diagram files
  • Add a syntax to label edges

Possible Goals

  • Syntax highlighting (Haskell syntax highlighting works well enough for the examples in this README)

Non-Goals

  • Supporting commercial products

Why, Though?

I was thinking about how it's annoying in languages like C when function declaration order matters. Then I wondered if there could be a case when it would be a nice feature for declaration order to matter and I thought of DAGs.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~6–15MB
~183K SLoC