chemlambda pred(3): graphviz dot file equivalent to mol file

README.md

Generating a graphviz dot file equivalent to the mol file of pred(3) in chemlambda v2: pred_3.mol (original name was erroneous)

The lambda calculus expression for pred(3) (predecessor(3) == 2) is PRED := λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u) (ref wikipedia)

Writing the above expression as nodes in a graph leads to the below graph. The corresponding dot file was written manually and available further below in this gist. An annotated version of pred_3.mol to help compare it to pred_3.dot is available further below in this gist.

To generate the dot file automatically from lambda terms, check http://www.teamshadi.net/chemlambda-js/ (a fork from this jsfiddle ). Its current output for pred(3) matches with the manually specified graph below.

Version 4 (2019-04-11): shifted indeces back by 1 (e.g. L1 to L0) to match with the auto-generated graph from here

Compare the above graph to the chemlambda d3.js graph for pred_3.mol here

To experiment with graphviz, use http://www.webgraphviz.com/ or https://dreampuf.github.io/GraphvizOnline http://viz-js.com/

Notes:

• This work was prompted from chamlambda issue #6
• Older versions of graphs:

• Version 3 (2019-04-09):
• Version 2 (2019-04-07):

pred_3.dot

digraph G {
  rankdir = TB;

  // defaults for L
  node [shape=record, color=red, style=filled]; 
  L0 [label="<lo> u |{<mi> x|L0} | <ro> λu.x"];
  L1 [label="<lo> u |{<mi> u|L1} | <ro> λu.u"];
  L2 [label="<lo> h |{<mi> h (g f)|L2} | <ro> λh.h (g f)"];
  L3 [label="<lo> g |{<mi> λh.h (g f)|L3} | <ro> (λg.λh.h (g f))"];
  L4 [label="<lo> x |{<mi> n (λg.λh.h (g f)) (λu.x) (λu.u)|L4} | <ro> λx.n (λg.λh.h (g f)) (λu.x) (λu.u)"];
  L5 [label="<lo> f |{<mi> λx.n (λg.λh.h (g f)) (λu.x) (λu.u)|L5} | <ro> λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)"];
  L6 [label="<lo> n |{<mi> λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)|L6} | <ro> λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)"];

  // defaults for A
  node [shape=record, color=green, style=filled]; 
  A0 [label="<li> g |{A0|<mo> (g f)} | <ri> f"];
  A1 [label="<li> h |{A1|<mo> h (g f)} | <ri> (g f)"];
  A2 [label="<li> n |{A2|<mo> n (λg.λh.h (g f))} | <ri> (λg.λh.h (g f))"];
  A3 [label="<li> n (λg.λh.h (g f)) |{A3|<mo> n (λg.λh.h (g f)) (λu.x)} | <ri> (λu.x)"];
  A4 [label="<li> n (λg.λh.h (g f)) (λu.x) |{A4|<mo> n (λg.λh.h (g f)) (λu.x) (λu.u)} | <ri> (λu.u)"];

  // other
  T [ shape=point ]
  FROUT [ style=filled, color=blue ]
  //output [ style=filled, color=pink ]


  // aesthetics
//  {rank=same; L0 A4}
//  {rank=same; L1 L4}


  // build edges
  L0:lo -> T [ label=2 ]
  L1:lo -> L1:mi [ label=6 ]
  A1:mo -> L2:mi [ label=13 ]
  L2:ro -> L3:mi [ label=7 ]
  L3:ro -> A2:ri
  L6:lo -> A2:li
  A2:mo -> A3:li [ label="a03?" ]
  L0:ro -> A3:ri [ label=1 ]
  L1:ro -> A4:ri [ label=5 ]
  A3:mo -> A4:li [ label="a02?a42" ]
  A4:mo -> L4:mi [ label=4 ]
  L4:ro -> L5:mi [ label=7 ]

  // FIXME
  L5:ro -> L6:mi [ label="9?" ]
  // L5:ro -> FROUT [ label="9?" ]
  L6:ro -> FROUT [ label="9?" ]

  A0:mo -> A1:ri [ label=11 ]
  L2:lo -> A1:li [ label=12 ]

  L4:lo -> L0:mi [ label=3 ]
  L5:lo -> A0:ri [ label=8 ]
  L3:lo -> A0:li [ label=10 ]

  //L6:ro -> output
}


// https://en.wikipedia.org/wiki/Lambda_calculus
// PRED := λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)

pred_3.mol

L    3   2   1    3:x, 2:u1   L1
T    2            2:u1
L    6   6   5    6:u2
L    4   3   7    3:x         L5
L    7   8   9    8:f         L6
A   10   8  11    8:f, 10:g   A1
A   12  11  13                A2
L   13  12  14                L3
L   14  10 a43
A  a42   5   4                A5
A  a03   1 a02                A4!
FO a13 a11 a03
A  a11 a02 a12      
FO a43 a41 a13
A  a41 a12 a42                A4?


Not sure: L2, L4, L7?   A3, A4?

@mbuliga
The automatic generator of graphs from lambda calculus terms written in javascript is now updated at this link. Its output is currently matching with the manually specified file above (with the exception of the T term). Note that I still haven't tackled your comment above (Apr 9 )

Btw I published the most recent version on http://www.teamshadi.net/chemlambda-js/ (less clutter from the jsfiddle)

@mbuliga, I illustrated your Apr 9 comments in this jupyter notebook. Could you take a look and confirm if it makes sense to you?

@shadiakiki1986 thank you! Just now saw this. I shall update this comment after I read it.

@mbuliga
Where can I find the documentation of the 8 re-write steps implemented at http://imar.ro/~mbuliga/pred_3_is_2.html ?
I tried to figure the re-writes of the 1st step from the json files pred_2_0.json, pred_2_1.json that are used in that html page,
but I'm finding it very difficult to relate the links section in the two files