determinism.anubis.c
2.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
*Project* The Anubis Project
*Title*
*Copyright* Copyright (c) Alain Prouté 2005.
*Released*
This file can be compiled by the two compilers 'anubis' and 'gcc'.
This file contains an example showing how an automaton may be programmed
deterministically, and explains why it is better to do so.
We make a program taking a vector X = (x,y) (with Int coordinates) and producing
M^n(X), where n is a positive integer and M the matrix:
(1 -1)
(1 1)
define (Int,Int)
compute
(
Int x,
Int y,
Int n
) =
if n =< 0 then (x,y) else
compute(x-y,x+y,n-1).
The next function is for testing the program:
read tools/basis.anubis
global define One
determinism_example
(
List(String) args
) =
if compute(1,1,10) is (x,y) then
print(x+" "+y+"\n").
The following (non deterministic) program in C seems to compute the same thing.
*/
#include <stdio.h>
main()
{
int x = 1;
int y = 1;
int n = 10;
while (n > 0)
{
x = x-y;
y = x+y;
n = n-1;
};
printf("%d %d\n",x,y);
}
/* Of course, it is not true, because the non deterministic instruction
x = x-y;
changes the value of x, so that the computation of the new value of y is false at the
next line. You may say that the fault was obvious. Nevertheless, the same kind of fault
may be non obvious in a more complicated program. The advantage of deterministic
programming is that it cannot happen.
Also, notice that since the recursive call to 'compute' is terminal, the Anubis
compiler produces a true loop (the stack does not grow during the computation). Hence,
deterministic programming has the same efficiency as non deterministic programming, if
the compiler is clever enough (and of course, if the language itself is well
structured).
*/