Call-by-Need Evaluation Strategy
Aug. 10th, 2014 03:41 pmhttps://gist.github.com/codedot/24f277ef4df5828c70a8
Call-by-need evaluation strategy using non-deterministic extension in Interaction Nets Compiler:
Call-by-need evaluation strategy using non-deterministic extension in Interaction Nets Compiler:
@@ -14,10 +14,18 @@ \print { /* Output results of read-back. */ puts(RVAL); - exit(EXIT_SUCCESS); + free(RVAL); } \atom; \read[a] { + /* Unshare variable. */ +} \share[\copy(b, \read_{LVAL}(a)), b]; + +\read[a] { + /* Initiate application. */ +} \apply[\lambda(b, \read_{LVAL}(a)), b]; + +\read[a] { /* Read back abstraction. */ } \lambda[\atom_{var(1)}, \read_{ABST(LVAL, var(0))}(a)]; @@ -29,10 +37,6 @@ /* Read back an atom. */ } \atom; -\bind[a, \atom_{RVAL}, a] { - /* Bind variable to an atom. */ -} \atom; - \copy[\atom_{RVAL}, \atom_{strdup(RVAL)}] { /* Copy an atom. */ } \atom; @@ -47,40 +51,56 @@ } \atom; \lambda[a, b] { + /* Unshare variable. */ +} \share[\copy(c, \lambda(a, b)), c]; + +\lambda[a, b] { + /* Initiate application. */ +} \apply[\lambda(c, \lambda(a, b)), c]; + +\lambda[a, b] { /* Apply a closed term. */ } \lambda[a, b]; +\copy[a, b] { + /* Unshare variable. */ +} \share[\copy(c, \copy(a, b)), c]; + +\copy[a, b] { + /* Initiate application. */ +} \apply[\lambda(c, \copy(a, b)), c]; + \copy[\lambda(a, b), \lambda(c, d)] { /* Initiate copy of a closed term. */ } \lambda[\dup(a, c), \dup(b, d)]; -\bind[a, \lambda(b, c), a] { - /* Bind variable to a closed term. */ -} \lambda[b, c]; +\dup[\amb(a, \share(b, c), c), \amb(d, \share(e, f), f)] { + /* Duplicate sharing. */ +} \share[\dup(b, e), \dup(a, d)]; + +\dup[\apply(a, b), \apply(c, d)] { + /* Duplicate application. */ +} \apply[\dup(a, c), \dup(b, d)]; \dup[\lambda(a, b), \lambda(c, d)] { - /* Duplicate abstraction or application. */ + /* Duplicate abstraction. */ } \lambda[\dup(a, c), \dup(b, d)]; -\dup[\copy(a, b), \copy(c, d)] { - /* Duplicate copy initiator. */ -} \copy[\dup(a, c), \dup(b, d)]; - -\dup[\bind(a, b, c), \bind(d, e, f)] { - /* Duplicate variable binding. */ -} \bind[\dup(a, d), \dup(b, e), \dup(c, f)]; - \dup[a, b] { /* Finish duplication. */ } \dup[a, b]; \erase { - /* Erase abstraction or application. */ -} \lambda[\erase, \erase]; + /* Erase sharing. */ +} \share[a, a]; \erase { - /* Erase variable binding. */ -} \bind[\erase, \erase, \erase]; + /* Erase application. */ +} \apply[\erase, \erase]; + +\erase { + /* Erase abstraction. */ +} \lambda[\erase, \erase]; \erase { /* Erase copy initiator. */ @@ -96,17 +116,12 @@ $$ -{"Application"} = result; -function = \lambda(argument, result); -shared1 = \copy(first1, second1); -shared2 = \copy(first2, second2); -shared3 = \copy(first3, second3); - -{"Abstraction"} = bind0; -bv1 = \bind(bind1, fv1, bind0); -bv2 = \bind(bind2, fv2, bind1); -bv3 = \bind(bind3, fv3, bind2); -bindn = \lambda(variable, body); +{"Application"} = \apply(function, argument); +first1 = \amb(second1, \share(shared1, back1), back1); +first2 = \amb(second2, \share(shared2, back2), back2); +first3 = \amb(second3, \share(shared3, back3), back3); + +{"Abstraction"} = \lambda(variable, body); term = \read_{strdup("")}(\print); term = {"Encoding"};