git @ Cat's Eye Technologies Emmental / rel_1_0_2011_1214
Import revision 2011.1214 (just some more HTML fixes.) Cat's Eye Technologies 13 years ago
1 changed file(s) with 25 addition(s) and 20 deletion(s). Raw diff Collapse all Expand all
00 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
1 <!-- encoding: UTF-8 -->
12 <html xmlns="http://www.w3.org/1999/xhtml" lang="en">
23 <head>
34 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
45 <title>The Emmental Programming Language</title>
6 <!-- begin html doc dynamic markup -->
7 <script type="text/javascript" src="/contrib/jquery-1.6.4.min.js"></script>
8 <script type="text/javascript" src="/scripts/documentation.js"></script>
9 <!-- end html doc dynamic markup -->
510 </head>
611 <body>
712
5358 how it works" to make it complete. This understanding might come
5459 from an implementation in some other programming language, or a specification
5560 in some formal language, or a description in some natural language, or simply
56 from intuition &mdash; but it has to come from somewhere.</p>
61 from intuition — but it has to come from somewhere.</p>
5762
5863 <p>Assuming that we do have that external source of understanding, the
5964 meta-circular interpreter can come in quite handy in codifying the semantics
112117
113118 <p>The operations can be thought of, abstractly, as functions which
114119 transform program states. Or they can be thought of, concretely, as
115 segments of code &mdash; mini-programs which implement these functions.
120 segments of code — mini-programs which implement these functions.
116121 In the case of a meta-circular interpreter, these mini-programs would be written
117122 <em>in the language being interpreted</em>.</p>
118123
144149 to describe interpreters:</p>
145150
146151 <pre>
147 % &rarr; XYZ+*!
148 &amp; &rarr; 'ap'ag'ag
152 % → XYZ+*!
153 &amp; → 'ap'ag'ag
149154 </pre>
150155
151156 <p>That is, the symbol <code>%</code>, when encountered in an Emmental
162167 <p>The inital Emmental interpreter is defined as follows:</p>
163168
164169 <pre>
165 a &rarr; a
166 b &rarr; b
167 c &rarr; c
170 a → a
171 b → b
172 c → c
168173 ...
169174 </pre>
170175
171176 <p>That is, for every symbol <var>x</var> in the ASCII set,
172 <var>x</var> <code>&rarr;</code> <var>x</var>.</p>
177 <var>x</var> <code>→</code> <var>x</var>.</p>
173178
174179 <p>Doesn't tell us a lot about Emmental's semantics, does it? No.
175180 Nothing at all, really. But remember what I said about needing an external
269274 <p><code>!</code> (sometimes called "supplant")
270275 pops a symbol, which we call <var>s</var>, off the stack.
271276 Then it pops a program <var>t</var>.
272 It then inserts the association <var>s</var> <code>&rarr;</code> <var>t</var> into the
277 It then inserts the association <var>s</var> <code>→</code> <var>t</var> into the
273278 interpreter definition. This overwrites whatever mapping of <var>s</var> might have
274279 been in the interpreter definition previously. This new interpreter definition
275280 is used for all subsequent execution (until it is changed again, of course.)</p>
377382 program.])</p>
378383
379384 <p>However, if it turns out that we need "duplicate" or "discard" in order
380 to write routines that can handle a variable-sized queue &mdash; and that
381 strikes me as likely &mdash; then it looks like we have a severe problem.</p>
385 to write routines that can handle a variable-sized queue — and that
386 strikes me as likely — then it looks like we have a severe problem.</p>
382387
383388 <p>Here's one way I could try to deal with it. I could say that the queue
384389 is <em>local</em> to the operation being defined (or the main program.)
406411 Emmental is Turing-complete. (Equivalently, prove that the set of
407412 Emmental programs that begin with <code>;#0#58!</code> is Turing-complete.
408413 The nice thing about Emmental is that you can always shoot yourself in
409 the foot &mdash; until you erase your pistol, that is.)</p>
414 the foot — until you erase your pistol, that is.)</p>
410415
411416 <p>And if you <em>really</em> like a challenge, try proving that Emmental
412417 without <code>~</code> is Turing-complete. I don't think that it is,
451456 opaque function would be; you can define all sorts of operations on them,
452457 for example concatenating two interpreters (for all symbols <var>s</var>
453458 in interpreter <var>a</var> and interpreter <var>b</var>,
454 <var>c</var>[<var>s</var>] <code>&rarr;</code> <var>a</var>[<var>s</var>]<var>b</var>[<var>s</var>] &mdash;
459 <var>c</var>[<var>s</var>] <code>→</code> <var>a</var>[<var>s</var>]<var>b</var>[<var>s</var>] —
455460 that sort of thing,) computing union or intersection of interpreters,
456461 Cartesian product, etc.)</p>
457462
459464 <em>multiple</em> meta-circular interpreters available inside Emmental, and symbols
460465 like <code>'</code> switch temporarily to an alternate MCI. This alternate MCI
461466 interprets every symbol as "push this symbol", then reinstates the previous MCI.
462 I like this explication better than the one above &mdash; MCIs begin
463 to look a bit like continuations! &mdash; but to do it justice would take some
467 I like this explication better than the one above — MCIs begin
468 to look a bit like continuations! — but to do it justice would take some
464469 work. I envision a language where the program has fine control
465470 over which MCI is in effect, possibly by keeping a map from symbols to MCIs,
466471 or maybe even being able to push MCIs onto the stack.
479484 about "what is a language", I think. Does a Pascal program fragment which
480485 defines a procedure called <code>PrintFibonacci</code> represent another
481486 programming language, one different from Pascal? You could certainly
482 say that it does &mdash; it's
487 say that it does — it's
483488 the language Pascal where the token <code>PrintFibonacci</code> has
484489 some meaning that it doesn't have in Pascal.</p>
485490
494499 Brainfuck, suitably extended.</p>
495500
496501 <p>You don't normally think of it that way, I bet, but you
497 <em>could</em> &mdash; and you would need to, to some degree,
502 <em>could</em> — and you would need to, to some degree,
498503 to claim that Emmental is "just" defining new functions.
499504 The reason you don't typically look at languages like this
500505 (unless you are very strange) is because it's much more useful to
521526 program states that occur internal to an operation.)</p>
522527
523528 <p>Happy interpreter-redefining!
524 <br>Chris Pressey
525 <br>Chicago, IL
526 <br>November 11, 2007</p>
529 <br/>Chris Pressey
530 <br/>Chicago, IL
531 <br/>November 11, 2007</p>
527532
528533 </body>
529534 </html>