-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.html
189 lines (156 loc) · 8.1 KB
/
index.html
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en-us">
<head>
<title>Universal Turing Machine in Forth</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="author" content="Maximilian Irro" />
<style type="text/css">
@font-face {
font-family: "Computer Modern";
src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunss.otf');
}
@font-face {
font-family: "Computer Modern";
src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunsx.otf');
font-weight: bold;
}
@font-face {
font-family: "Computer Modern";
src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunsi.otf');
font-style: italic, oblique;
}
@font-face {
font-family: "Computer Modern";
src: url('http://mirrors.ctan.org/fonts/cm-unicode/fonts/otf/cmunbxo.otf');
font-weight: bold;
font-style: italic, oblique;
}
body {
font-family: "Computer Modern", sans-serif;
}
* {
margin: 0;
padding: 0;
}
html,
body {
height: 100%;
}
body {
background-color: white;
font-family: "CMU Serif", helvetica, arial, clean, serif !important;
font-size: 11pt;
font-weight: 200;
text-align: justify;
line-height: 1.3;
}
h1 {
font-size: 22pt;
}
h2 {
font-size: 16pt;
margin-top: 1em;
margin-bottom:1em;
}
h3 {
font-size: 11pt;
font-weight: normal;
}
p {
margin: 1em 0;
}
a {
color: #2233FF;
}
a:hover, a:visited, a:link, a:active{
text-decoration: none;
}
.container {
min-width: 35em;
max-width: 50em;
margin: 0 auto;
margin-top: 2em;
margin-bottom: 2em;
}
ul{
margin-top: 1em;
margin-bottom:1em;
}
ol, ul{
margin-left: 2em;
}
</style>
</head>
<body>
<div class="container">
<h1>Universal Turing Machine in Forth</h1>
<p>by <a href="https://github.com/theresa77">Theresa Fröschl</a> and <a href="https://github.com/mpgirro">Maximilian Irro</a></p>
<p>This is a project for the course <a href="http://www.complang.tuwien.ac.at/anton/lvas/stack.html">Stackbasierte Sprachen (2014W)</a> (german for "<em>stack-based languages</em>") at <a href="http://www.informatik.tuwien.ac.at/english">TU Wien</a>. The <a href="https://github.com/mpgirro/universal-forth-machine">repository is available on GitHub</a>.</p>
<p>We amined to write a Universal Turing Machine using the language Forth. We developed our program for the <a href="http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/index.html#Top">Gforth</a> interpreter. If used with other Forth interpreters there might be issues (we never tested).</p>
<h2>Name explanation</h2>
<p>We call our program <em>Universal Forth Machine</em> (UFM), a wordplay between "Universal Turing Machine", being written in Forth, and Forth being a stack machine.</p>
<h2>Usage</h2>
<pre><code>ufm.forth /path/to/machine /path/to/tape
</code></pre>
<h2>Machine specification format</h2>
<p>We provide some example machines in <a href="machines/">machines/</a> and tapes to test them in <a href="tapes/">tapes/</a>. The basic file format looks like this:</p>
<pre><code>
start-state
state-term1 label
state1
sym-read sym-write next-state tape-ptr-move
sym-read sym-write next-state tape ptr-move
state-term2 otherlabel
state-term3 yetanotherlabel
state2
sym-read sym-write next-state tape-ptr-move
sym-read sym-write next-state tape ptr-move
</code></pre>
<p>The first line <strong>has</strong> to be the <code>start-state</code>. All following lines are state descriptions. A <code>term-state</code> (terminal state) is followbed by a <code>label</code> which is a string that will be the output of UFM if the machine terminates in this state. A line containing just a <code>state</code> token starts the definition of a regular state. All following lines until a new <code>state</code> or <code>state-term</code> line are the edge dedinitions for this state. An edge line has to consist of:</p>
<ol>
<li><code>sym-read</code>: the symbol read on the tape. If the machine is in the currently defined state, and this symbol is read, the machine will execute the following actions of this line. Think of it as the edge label when picturing the turing machine as a graph.<br></li>
<li><code>sym-write</code>: the symbol to write onto the current tape position.</li>
<li><code>next-state</code>: the next state the turing (state-)machine goes to.</li>
<li><code>tape-ptr-move</code>: the direction the tape pointer (<code>tape-ptr</code>) moves. It can go one step to the left (<code>-1</code>) or right (<code>1</code>), or just stay (<code>0</code>) at its current position.</li>
</ol>
<p><strong>Note</strong> that all tokens except the <code>label</code> for terminal states support literals only! They will all be converted into numbers. So no strings allowed here.</p>
<h2>Special stack feature</h2>
<p>The state transition of the machine is done in a loop calling the <code>transition</code> word. This is a word that will be dynamically compiled at runtime just before it's first execution. Therefore the code of <code>transition</code> is not hardcoded in the program file, but will be generated by a special compilation word <code>[compile-transition]</code> which is <code>compile-only</code> and <code>immediate</code>. It will compile Forth code into <code>transition</code> based on the input machine specification file. Have a look at the colon definition of <code>transition</code> in the source code, and at runtime using <code>see transition</code></p>
<h2>Structure of transition word</h2>
<p>The code structure of <code>transition</code> (which will be compiled depending on the machine-file) looks like this for the <a href="machines/increment.machine">machines/increment.machine</a>:</p>
<pre lang="forth"><code>: transition ( cur-state sym-read -- next-state flag )
over 1 =
IF cr 4546001056 16 type 4545995737 9 type cr 2drop 0 EXIT
THEN
over 0 =
IF dup 1 =
IF 2drop 1 tape-write 0 tape-ptr-move-right -1 EXIT
THEN
dup 0 =
IF 2drop 1 tape-write 1 tape-ptr-move-stay -1 EXIT
THEN
THEN ; ok
</code></pre>
<p>The <code>over <some-literal> = if</code> sequences will check for the state the machine is currently occupying. The <code>dup <some-literal> = if</code> parts then check the current symbol on the tape. With this mechanism it is decided which action the machine will perform next.</p>
<h2>Resources</h2>
<h3>Program:</h3>
<ul>
<li><a href="ufm.forth">ufm.forth</a></li>
</ul>
<h3>Machines:</h3>
<ul>
<li><a href="machines/increment.machine">increment.machine</a> -- increment the amount of <code>1</code>-symbols on the tape by one (at the right edge).</li>
<li><a href="machines/multi3.machine">multi3.machine</a> -- check if tape content holds a multiple of 3 <code>1</code>-symbols.</li>
<li><a href="machines/palindrom.machine">palindrom.machine</a> -- check if tape content is a palindrom. Border markers are <code>11</code> (left) and <code>33</code> (right).</li>
</ul>
<h3>Tapes:</h3>
<ul>
<li><a href="tapes/increment.tape">increment.tape</a></li>
<li><a href="tapes/multi3-yes.tape">multi3-yes.tape</a> -- <a href="machines/multi3.machine">multi3.machine</a> should recognize a multiple of 3 <code>1</code>-symbols.</li>
<li><a href="tapes/multi3-no.tape">multi3-no.tape</a> -- <a href="machines/multi3.machine">multi3.machine</a> should <em>not</em> recognize a multiple of 3 <code>1</code>-symbols</li>
<li><a href="tapes/palindrom-ok.tape">palindrom-ok.tape</a> -- <a href="machines/palindrom.machine">palindrom.machine</a> should accept a palindrom</li>
<li><a href="tapes/palindrom-nok.tape">palindrom-nok.tape</a> -- <a href="machines/palindrom.machine">palindrom.machine</a> should <em>not</em> accept a palindrom</li>
</ul>
</div>
</body>
</html>