Import revision 2011.1214 (just some more HTML fixes.)
Cat's Eye Technologies
13 years ago
0 | 0 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> |
1 | <!-- encoding: UTF-8 --> | |
1 | 2 | <html xmlns="http://www.w3.org/1999/xhtml" lang="en"> |
2 | 3 | <head> |
3 | 4 | <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> |
4 | 5 | <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 --> | |
5 | 10 | </head> |
6 | 11 | <body> |
7 | 12 | |
53 | 58 | how it works" to make it complete. This understanding might come |
54 | 59 | from an implementation in some other programming language, or a specification |
55 | 60 | in some formal language, or a description in some natural language, or simply |
56 | from intuition — but it has to come from somewhere.</p> | |
61 | from intuition — but it has to come from somewhere.</p> | |
57 | 62 | |
58 | 63 | <p>Assuming that we do have that external source of understanding, the |
59 | 64 | meta-circular interpreter can come in quite handy in codifying the semantics |
112 | 117 | |
113 | 118 | <p>The operations can be thought of, abstractly, as functions which |
114 | 119 | transform program states. Or they can be thought of, concretely, as |
115 | segments of code — mini-programs which implement these functions. | |
120 | segments of code — mini-programs which implement these functions. | |
116 | 121 | In the case of a meta-circular interpreter, these mini-programs would be written |
117 | 122 | <em>in the language being interpreted</em>.</p> |
118 | 123 | |
144 | 149 | to describe interpreters:</p> |
145 | 150 | |
146 | 151 | <pre> |
147 | % → XYZ+*! | |
148 | & → 'ap'ag'ag | |
152 | % → XYZ+*! | |
153 | & → 'ap'ag'ag | |
149 | 154 | </pre> |
150 | 155 | |
151 | 156 | <p>That is, the symbol <code>%</code>, when encountered in an Emmental |
162 | 167 | <p>The inital Emmental interpreter is defined as follows:</p> |
163 | 168 | |
164 | 169 | <pre> |
165 | a → a | |
166 | b → b | |
167 | c → c | |
170 | a → a | |
171 | b → b | |
172 | c → c | |
168 | 173 | ... |
169 | 174 | </pre> |
170 | 175 | |
171 | 176 | <p>That is, for every symbol <var>x</var> in the ASCII set, |
172 | <var>x</var> <code>→</code> <var>x</var>.</p> | |
177 | <var>x</var> <code>→</code> <var>x</var>.</p> | |
173 | 178 | |
174 | 179 | <p>Doesn't tell us a lot about Emmental's semantics, does it? No. |
175 | 180 | Nothing at all, really. But remember what I said about needing an external |
269 | 274 | <p><code>!</code> (sometimes called "supplant") |
270 | 275 | pops a symbol, which we call <var>s</var>, off the stack. |
271 | 276 | Then it pops a program <var>t</var>. |
272 | It then inserts the association <var>s</var> <code>→</code> <var>t</var> into the | |
277 | It then inserts the association <var>s</var> <code>→</code> <var>t</var> into the | |
273 | 278 | interpreter definition. This overwrites whatever mapping of <var>s</var> might have |
274 | 279 | been in the interpreter definition previously. This new interpreter definition |
275 | 280 | is used for all subsequent execution (until it is changed again, of course.)</p> |
377 | 382 | program.])</p> |
378 | 383 | |
379 | 384 | <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 — and that | |
381 | strikes me as likely — 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> | |
382 | 387 | |
383 | 388 | <p>Here's one way I could try to deal with it. I could say that the queue |
384 | 389 | is <em>local</em> to the operation being defined (or the main program.) |
406 | 411 | Emmental is Turing-complete. (Equivalently, prove that the set of |
407 | 412 | Emmental programs that begin with <code>;#0#58!</code> is Turing-complete. |
408 | 413 | The nice thing about Emmental is that you can always shoot yourself in |
409 | the foot — until you erase your pistol, that is.)</p> | |
414 | the foot — until you erase your pistol, that is.)</p> | |
410 | 415 | |
411 | 416 | <p>And if you <em>really</em> like a challenge, try proving that Emmental |
412 | 417 | without <code>~</code> is Turing-complete. I don't think that it is, |
451 | 456 | opaque function would be; you can define all sorts of operations on them, |
452 | 457 | for example concatenating two interpreters (for all symbols <var>s</var> |
453 | 458 | in interpreter <var>a</var> and interpreter <var>b</var>, |
454 | <var>c</var>[<var>s</var>] <code>→</code> <var>a</var>[<var>s</var>]<var>b</var>[<var>s</var>] — | |
459 | <var>c</var>[<var>s</var>] <code>→</code> <var>a</var>[<var>s</var>]<var>b</var>[<var>s</var>] — | |
455 | 460 | that sort of thing,) computing union or intersection of interpreters, |
456 | 461 | Cartesian product, etc.)</p> |
457 | 462 | |
459 | 464 | <em>multiple</em> meta-circular interpreters available inside Emmental, and symbols |
460 | 465 | like <code>'</code> switch temporarily to an alternate MCI. This alternate MCI |
461 | 466 | interprets every symbol as "push this symbol", then reinstates the previous MCI. |
462 | I like this explication better than the one above — MCIs begin | |
463 | to look a bit like continuations! — 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 | |
464 | 469 | work. I envision a language where the program has fine control |
465 | 470 | over which MCI is in effect, possibly by keeping a map from symbols to MCIs, |
466 | 471 | or maybe even being able to push MCIs onto the stack. |
479 | 484 | about "what is a language", I think. Does a Pascal program fragment which |
480 | 485 | defines a procedure called <code>PrintFibonacci</code> represent another |
481 | 486 | programming language, one different from Pascal? You could certainly |
482 | say that it does — it's | |
487 | say that it does — it's | |
483 | 488 | the language Pascal where the token <code>PrintFibonacci</code> has |
484 | 489 | some meaning that it doesn't have in Pascal.</p> |
485 | 490 | |
494 | 499 | Brainfuck, suitably extended.</p> |
495 | 500 | |
496 | 501 | <p>You don't normally think of it that way, I bet, but you |
497 | <em>could</em> — and you would need to, to some degree, | |
502 | <em>could</em> — and you would need to, to some degree, | |
498 | 503 | to claim that Emmental is "just" defining new functions. |
499 | 504 | The reason you don't typically look at languages like this |
500 | 505 | (unless you are very strange) is because it's much more useful to |
521 | 526 | program states that occur internal to an operation.)</p> |
522 | 527 | |
523 | 528 | <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> | |
527 | 532 | |
528 | 533 | </body> |
529 | 534 | </html> |