Хуяк-хуяк, и в продакшн:

$ make
        make parsers
        node_modules/.bin/jison mlc.jison
        node_modules/.bin/jison inet.jison
`parsers' is updated.
        make example
        node parse.js example.mlc >example.in
        inc <example.in
        mv in.tab.c example.c
        cc    -o example example.c 
        time -p ./example
v1: v2: v1 (v1 (v1 (v2)))
real 0.09
user 0.08
sys 0.00
        make example.p2p
        node parse.js example.mlc p2p >example.p2p
        time -p node interact.js example.p2p
v1: v2: v1 (v1 (v1 (v2)))
real 0.79
user 0.76
sys 0.02
$ 

Осталось немного причесать, и цель достигнута.
Наконец-то, дошли руки до портирования MLC (Macro Lambda Calculus) и INC (Interaction Nets Compiler) на JavaScript. Транслятор из языка MLC в язык INC получилось сделать на Node.js с помощью Jison довольно быстро. INC все еще есть только в первоначальном виде на Си.

Как только появилась возможность потестировать всю цепочку, выяснилась одна проблема с правилами взаимодействия, которую смог починить следующий патч (соответствующее изменение внесено также в заметку на Scribd):

--- a/template.in
+++ b/template.in
@@ -69,9 +69,13 @@ char *place(char *buf, const char *format, char *str);
        /* Initiate copy of a closed term. */
 } \lambda[\dup(a, c), \dup(b, d)];
 
-\dup[\amb(a, \share(b, c), c), \amb(d, \share(e, f), f)] {
+\dup[a, b] {
+       /* Unshare variable. */
+} \share[\copy(c, \dup(a, b)), c];
+
+\dup[a, b] {
        /* Duplicate sharing. */
-} \share[\dup(b, e), \dup(a, d)];
+} \copy[\dup(\amb(c, \share(a, d), d), \amb(e, \share(b, f), f)), \dup(c, e)];
 
 \dup[\apply(a, b), \apply(c, d)] {
        /* Duplicate application. */

Для наглядности тестовая арифметика в цифрах Черча (Valgrind говорит, что память не течет):

$ cat example.mlc
I = x: x;
K = x, y: x;
S = x, y, z: x z (y z);

T = K;
F = x, y: y;
AND = p, q: p q F;
OR = p, q: p T q;
NOT = p: (a, b: p b a);

C0 = f, x: x;
C1 = f, x: f x;
C2 = f, x: f (f x);
C3 = f, x: f (f (f x));
SUCC = n: (f, x: f (n f x));
PLUS = m, n: (f, x: m f (n f x));
MULT = m, n: (f: m (n f));
EXP = m, n: n m;
PRED = n: (f, x: n (g, h: h (g f)) (K x) I);
MINUS = m, n: n PRED m;
ZERO = n: n (K F) T;

A = self, f: f (self self f);
Y = A A;
FACTR = self, n: (ZERO n) C1 (MULT n (self (PRED n)));
FACT = Y FACTR;

C24 = FACT (PLUS C2 C2);
C27 = EXP C3 C3;
MINUS C27 C24
$ make
        make parsers
        node_modules/.bin/jison mlc.jison
        node_modules/.bin/jison inet.jison
`parsers' is updated.
        make example
        node parse.js example.mlc >example.in
        inc <example.in
        mv in.tab.c example.c
        cc    -o example example.c 
        ./example
v1: v2: v1 (v1 (v1 (v2)))
$ 

Неизвестно, сколько потребуется времени, чтобы проверить корректность системы взаимодействия, так как теперь уже нельзя построить доказательство, просто сославшись на операционную эквивалентность, - слишком стала отличаться полученная система от описанных в литературе.
Encoding ω Α (K ω), where ω ≡ λx.x x, A ≡ λx.λf.f (x x f), and K ≡ λx.λy.x:

$ cat init.txt 
term = \read_{strdup("")}(\print);

term = \apply(\apply(omega1, a), \apply(k, omega2));

omega1 = \lambda(x1, \apply(\amb(y1, \share(x1, z1), z1), y1));
omega2 = \lambda(x2, \apply(\amb(y2, \share(x2, z2), z2), y2));

a = \lambda(self, \lambda(func, \apply(func1, rec)));
rec = \apply(\apply(self1, self2), func2);
self1 = \amb(self2, \share(self, back1), back1);
func1 = \amb(func2, \share(func, back2), back2);

k = \lambda(x, \lambda(\erase, x));
$ make
        printf '%s\n\n$$\n\n%s\n\n$$\n\n%s\n' >test.in \
                "`cat rset.txt`" \
                "`cat init.txt`" \
                "`cat tail.txt`"
        inc <test.in
        mv in.tab.c test.c
        cc    -o test test.c 
        valgrind ./test
==20346== Memcheck, a memory error detector
==20346== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==20346== Command: ./test
==20346== 
v1: (v1 (v1))
==20346== 
==20346== HEAP SUMMARY:
==20346==     in use at exit: 0 bytes in 0 blocks
==20346==   total heap usage: 606 allocs, 606 frees, 23,934 bytes allocated
==20346== 
==20346== All heap blocks were freed -- no leaks are possible
==20346== 
==20346== For counts of detected and suppressed errors, rerun with: -v
==20346== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 4 from 4)
$ 
https://gist.github.com/codedot/24f277ef4df5828c70a8

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"};
В компиляторе сетей взаимодействия INC (Interaction Nets Compiler) теперь есть поддержка недетерминированного расширения в виде специального бинарного агента Amb с двумя главными портами. Это расширение необходимо при реализации стратегии "call-by-need" для λ-исчисления.

Синтаксис для недетерминированного расширения сетей взаимодействия выбран наиболее консервативным образом (по отношению к основной части языка программирования) и отличается от того, который встречается в литературе: при описании правил взаимодействия и начальной конфигурации агент Amb обозначается как тернарный, первый дополнительный порт которого выполняет роль второго главного. К примеру, следующее изменение не меняет поведение тестовой программы:

 
 $$
 
-\fan_{1}(x, x) = \fan_{2}(\erase, {&wire1});
+\fan_{1}(x, x) = \amb({&wire1}, \fan_{2}(\erase, y), y);
 
 {&wire2} = \fan_{3}({&erase}, \erase);
 
Decoding extension for Implementation of Closed Reduction using Interaction Nets Compiler:

${
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *var(int fresh);
char *append(char *format, char *buf, char *str);

#define ABST(BUF, STR) append("%s%s: ", (BUF), (STR))
#define APPL(BUF, STR) append("%s%s ", (BUF), (STR))
#define ATOM(BUF, STR) append("%s(%s)", (BUF), (STR))
}$

\print {
	/* Output results of read-back. */
	puts(RVAL);
	exit(EXIT_SUCCESS);
} \atom;

\read[a] {
	/* Read back abstraction. */
} \lambda[\atom_{var(1)}, \read_{ABST(LVAL, var(0))}(a)];

\lambda[\read_{APPL(strdup(""), RVAL)}(a), a] {
	/* Read back application. */
} \atom;

\read[\atom_{ATOM(LVAL, RVAL)}] {
	/* 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;

\dup[\atom_{RVAL}, \atom_{strdup(RVAL)}] {
	/* Duplicate an atom. */
} \atom;

\erase {
	/* Erase an atom. */
	free(RVAL);
} \atom;

$$

term = \read_{strdup("")}(\print);
term = {"Encoding"};

$$

char *var(int fresh)
{
	static int id;

	char buf[BUFSIZ];

	if (fresh)
		++id;

	sprintf(buf, "v%d", id);
	return strdup(buf);
}

char *append(char *format, char *buf, char *str)
{
	size_t size = strlen(format) + strlen(str);
	char *result = malloc(strlen(buf) + size);

	sprintf(result, format, buf, str);

	free(buf);
	free(str);
	return result;
}
An Interaction Net Implementation of Closed Reduction by Ian Mackie using Interaction Nets Compiler:

\lambda[a, b] {
	/* Apply a closed term. */
} \lambda[a, b];

\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[\lambda(a, b), \lambda(c, d)] {
	/* Duplicate abstraction or application. */
} \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 {
	/* Erase variable binding. */
} \bind[\erase, \erase, \erase];

\erase {
	/* Erase copy initiator. */
} \copy[\erase, \erase];

\erase {
	/* Erase duplicator. */
} \dup[\erase, \erase];

\erase {
	/* Finish erasing. */
} \erase;

$$

{"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);
$ cat >hello.in 
${
#include <stdio.h>
}$

\alpha {
        printf("%s %s!\n", LVAL, RVAL);
} \beta;

$$

\alpha_{"Hello"} = \beta_{"World"};

$$

#include <stdlib.h>

inagent *inaux(void *aux, void *offline)
{
        return NULL;
}

int main()
{
        interact();
        return 0;
}
$ inc <hello.in
$ c99 in.tab.c
$ ./a.out
Hello World!
$ 
В компиляторе сетей взаимодействия INC (Interaction Nets Compiler) теперь есть поддержка начальной конфигурации. Конфигурация описывается на языке, близком к исчислению взаимодействия. Эта функциональность должна сильно упростить проект MLC: текст на языке MLC (Macro Lambda Calculus) можно будет целиком транслировать в исходный код для INC, а уже оттуда - в исполняемый код на Си. Трансляцию из MLC в INC можно сделать с помощью компактного представления λ-термов в сетях взаимодействия и механизма "readback" в виде системы взаимодействия с побочными действиями.

Ниже пример работы INC.

$ inc <example.in
$ c99 in.tab.c
$ ./a.out
inaux: rewired
inaux: returns
inaux: returns
inaux: returns
fan_1 >< fan_2
fan_3 >< fan_3
erase >< fan_3
fan_3 >< fan_3
erase >< erase
erase >< erase
$ 
What's your status?

Issue 735 Resolved and Accepted.

Issue 736 Needs an Interpretation and Accepted as Marked by Don Cragun:
Interpretation response
------------------------
The standard is unclear on this issue, and no conformance
distinction can be made between alternative implementations
based on this.  This is being referred to the sponsor.

Rationale:
-------------
The following changes make the grammar and text reflect existing
practice.

Notes to the Editor (not part of this interpretation):
-------------------------------------------------------
On page 2350, lines 74801-74808, change

%start  complete_command
%%
complete_command : list separator
                 | list
                 ;

to:

%start program
%%
program          : linebreak complete_commands linebreak
                 | linebreak
                 ;
complete_commands: complete_commands newline_list complete_command
                 |                                complete_command
                 ;
complete_command : list separator_op
                 | list
                 ;

Cross-volume change to XRAT...

At page 3700 line 126612 section C.2.10 delete:

The start symbol of the grammar (complete_command) represents
either input from the command line or a shell script.  It is
repeatedly applied by the interpreter to its input and represents
a single "chunk" of that input as seen by the interpreter.

Issue 737 Resolved and Accepted.

Most Popular Tags

Syndicate

RSS Atom

June 2017

S M T W T F S
    1 23
45678910
11121314151617
18192021222324
252627282930 
Powered by Dreamwidth Studios