git @ Cat's Eye Technologies Quylthulg / rel_1_0_2011_1214
Initial import of Quylthulg 1.0-2011.1214 sources. catseye 13 years ago
4 changed file(s) with 1124 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all
+362
-0
doc/quylthulg.html less more
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 -->
2 <html xmlns="http://www.w3.org/1999/xhtml" lang="en">
3 <head>
4 <title>The Quylthulg Programming Language</title>
5 <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
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 -->
10 </head>
11 <body>
12
13 <h1>The Quylthulg Programming Language</h1>
14
15 <h2>Overview</h2>
16
17 <p>Here is what is known about the programming language <dfn>Quylthulg</dfn>. Quylthulg:</p>
18
19 <ul>
20 <li>is a programming language;</li>
21 <li>is named Quylthulg;</li>
22 <li>was designed by Chris Pressey;</li>
23 <li>does <em>not</em>, quite apart from
24 prevailing trends in programming practice, shun the use of <code>goto</code>;</li>
25 <li>is, however, somewhat particular about <em>where</em>
26 <code>goto</code> may be used (<code>goto</code> may only occur inside a data structure);</li>
27 <li>is purely functional (in the sense that it does not allow "side-effectful" updates to values);</li>
28 <li>forbids recursion;</li>
29 <li>provides but a single looping construct: <code>foreach</code>, which
30 applies an expression successively to each value in a data structure;</li>
31 <li>is Turing-complete; and</li>
32 <li>boasts an argument-less macro expansion facility (in which recursion is also forbidden.)</li>
33 </ul>
34
35 <h2>Syntax</h2>
36
37 <p>The syntax for identifiers draws from the best parts of the esteemed languages BASIC and Perl.
38 Like Perl, all identifiers must be preceded by a <code>$</code> symbol, and like BASIC,
39 all identifiers must be followed by a <code>$</code> symbol. Well, OK, that's for strings anyway, but we don't
40 care about their types really, so we use <code>$</code> for everything. (Also, studies show that this syntax can help
41 serious TeX addicts from "bugging out".)</p>
42
43 <p>A nice practical upshot of this is that identifier names may contain any characters whatsoever
44 (excepting <code>$</code>), including whitespace.</p>
45
46 <p>Because of this, the syntax for string literals can be, and is, derived from the syntax for identifiers.
47 A string literal is given by a <code>~</code> followed by an identifier; the textual content of the
48 name of the identifier is used as the content of the string literal. A string literal consisting of a single
49 <code>$</code> symbol is given by <code>~~</code>.</p>
50
51 <p>Many find the syntax for labels to be quite sumilar to that for identifiers. (Some even find it to
52 be quite similar.) Labels are preceded and followed by <code>:</code> symbols, and may contain
53 any symbol except for <code>:</code>.</p>
54
55 <p>Syntax for binary operations follows somewhat in the footsteps of the identifier syntax. It is a
56 combination of prefix, infix, and postfix syntax, where the two terms must be preceeded, followed,
57 and seperated by the same symbol. We call this notation <em>panfix</em>. It is perhaps worth noting that, like
58 postfix, panfix does not require the deployment of arcane contrivances such as <em>parentheses</em>
59 to override a default operator precedence. At the same time, panfix allows terms to be specified
60 in the same order and manner as infix, an unquestionably natural and intuitive notation to those
61 who have become accustomed to it.</p>
62
63 <p>So, we give some examples:</p>
64
65 <pre>*+1+2+*3*
66 &amp;~$The shoes are $&amp;&amp;~~&amp;~$9.99 a pair.$&amp;&amp;</pre>
67
68 <p>The first example might be stated as (1+2)*3 in conventional, icky parenthesis-ful notation, and evaluates to 9.
69 The second evaluates to the string "The shoes are $9.99 a pair."</p>
70
71 <p>There are no unary operators in Quylthulg. (Note that <code>~</code> isn't really a unary operator, actually not an operator at all,
72 because it must be followed by an identifier, not an
73 expression. Well, maybe it's a special kind of operator then, an identifier-operator perhaps. But you see what I'm getting
74 at, don't you? Hopefully not.)</p>
75
76 <p>There is a special 6-ary operator, <code>foreach</code>. It has its own syntax which will
77 be covered below.</p>
78
79 <h2>Data Types</h2>
80
81 <h3>Strings and Integers</h3>
82
83 <p>Yes. Also a special type called <code>abort</code>, of which there is a single value <code>abort</code>,
84 which you'll learn about later.</p>
85
86 <h3>Lists</h3>
87
88 <p>The sole data structure of note in Quylthulg is the list. Lists are essentially identical
89 to those found in other functional languages such as Scheme: they are either the
90 special value <code>null</code>, which suggests an empty list, or they consist of a <code>cons</code>
91 cell, which is a pair of two other values. By convention, the first of this pair
92 is the value of this list node, and the second is a sublist (a <code>null</code>
93 or a <code>cons</code>) which represents the rest of this list.</p>
94
95 <p>The value of a list node may be any value: a scalar such as an integer or a string, another (embedded sub)list,
96 or the special value <code>abort</code>. <code>cons</code> cells are constructed by the <code>,</code>
97 panfix operator. Some examples follow:</p>
98
99 <pre>,1,,2,,3,null,,,
100 ,1,,2,3,,</pre>
101
102 <p>The first example constructs a proper list.
103 So-called "improper" lists, which purely by convention
104 do not end with <code>null</code>, can also be constructed: that's the second example.</p>
105
106 <p>When all of the terms involved are literal constants embedded in the program text,
107 there is a shorthand syntax for these list expressions, stolen from the Prolog/Erlang school:</p>
108
109 <pre>[1, 2, 3]
110 [1, 2 | 3]</pre>
111
112 <p>Note, however, that <code>[]</code> is not shorthand for <code>null</code>.
113 Note also that when this syntax is used, all values <em>must</em> be literal constants:
114 there will be no tolerance for variables. There will, however, be tolerance for <code>goto</code>s and
115 labels; see below for more on that.</p>
116
117 <h3>Cyclic Lists</h3>
118
119 <p>Labels and the <code>goto</code> construct enable the
120 definition of cyclic data structures like so:</p>
121
122 <pre>:A:[1, 2, 3, goto $A$]
123 :B:[1, 2, :C:[3, 4, goto $B$], 5, 6, goto $C$]</pre>
124
125 <p>Note that this can only be done in literal constant data structure expressions, not in
126 <code>,</code> (<code>cons</code>ing) operations or expression involving a variable. This is to avoid the
127 dynamic construction of labelled terms, which just a tad mind-bending and which I've decided to save for
128 a sequel to Quylthulg, whatever and whenever that might be. Note also that labels have their own
129 syntax during declaration, but (oh so helpfully) insist on being referred to in <code>goto</code>s by the <code>$</code>
130 syntax used for identifiers.</p>
131
132 <h3>List Operators</h3>
133
134 <p>The values contained in a <code>cons</code> cell can be extracted
135 by the felicitous use of the binary operators <code>&lt;</code> ('first') and <code>&gt;</code>
136 ('rest'). For both of these operators, the left-hand side is the <code>cons</code> cell to operate on, and the right-hand
137 side is an expression which the operator will evaluate to in the case that it cannot successfully
138 extract the value from the <code>cons</code> cell (e.g., the left-hand side is not in fact a <code>cons</code> cell
139 but rather something else like a <code>null</code> or a number or a string or <code>abort</code>.</p>
140
141 <p>There is also an operator <code>;</code> which appends one list (the right-hand side) onto the end of another
142 list (the left-hand side.) This is probably not strictly necessary, since as we'll see later can probably build something equivalent
143 using <code>foreach</code>es and macros, but what the hell, we can afford it. Party down.</p>
144
145 <p>These list operators honour cyclic lists, so that <code>&gt;[:X: 4 | goto :X:]&gt;abort&gt;</code>, to take
146 just one instance, evaluates to 4.</p>
147
148 <h2>Control Flow</h2>
149
150 <p>Quylthulg's sole looping construct, <code>foreach</code>, is a recursing abortable
151 "fold" operation. It is passed a data structure to traverse, an expression
152 (called the <em>body</em>) that it will
153 apply to each value it encounters in the traversed data structure,
154 and an initial value called the <em>accumulator</em>.
155 Inside the body, two identifiers are bound to two values: the value in the data structure that the body is currently
156 being applied to, and the value of the current value. The names of the idenfiers so bound are specified in
157 the syntax of the <code>foreach</code> operator. The value that the
158 body evaluates to is used as the accumulator for the next time the body is evaluated, on the next value
159 in the data structure. The value that <code>foreach</code> evaluates
160 to is the value of the FINAL accumulator (emphasis mine.) The full form of this operator is as follows:</p>
161
162 <pre>foreach <i>$var$</i> = <i>data-expr</i> with <i>$acc$</i> = <i>initial-expr</i> be <i>loop-expr</i> else be <i>otherwise-expr</i></pre>
163
164 <p><code>foreach</code> traverses the data structure in this manner:
165 from beginning to end. It is:</p>
166 <ul>
167 <li><em>recursing</em>, meaning if the current
168 element of the list is itself a (sub)list, <code>foreach</code> will
169 begin traversing that (sub)list (with the same body and current
170 accumulator, natch) instead of passing the (sub)list to the body; and</li>
171 <li><em>abortable</em>, meaning that the callback may evaluate to a special
172 value <code>abort</code>, which causes traversal of
173 the current (sub)list to cease immediately, returning to the traversal
174 of the containing list, if any.</li>
175 </ul>
176
177 <p>If the <i>data-expr</i> evaluates to some value besides a <code>cons</code> cell
178 (for example, <code>null</code> or an integer or a string), then the <i>loop-expr</i> is
179 ignored and the <i>otherwise-expr</i> is evaluated instead.</p>
180
181 <p>As an example,</p>
182
183 <pre>
184 -foreach $x$ = [2, 3, 4] with $a$ = 1 be *$a$*$x$* else be null-1-
185 </pre>
186
187 <p>will evaluate to 23. On the other hand,</p>
188
189 <pre>
190 foreach $x$ = null with $a$ = 1 be $a$ else be 23
191 </pre>
192
193 <p>will also evaluate to 23.</p>
194
195 <h2>Macro System</h2>
196
197 <p>Quylthulg boasts an argument-less macro expansion system. (Yes, there is no argument about it: it <em>boasts</em> it. It is quite arrogant, you know.)
198 Where-ever text of the form <code>{foo}</code> appears in the source code, the contents of the macro named <code>foo</code>
199 are inserted at that point, replacing <code>{foo}</code>. This process is called the <em>expansion</em> of <code>foo</code>.
200 But it gets worse: whereever text of the form <code>{bar}</code> appears in the contents of that macro called <code>foo</code>,
201 those too will be replaced by the contents of the macro called <code>bar</code>. And so on. Three things to note:</p>
202
203 <ul>
204 <li>If there is no macro called <code>foo</code>, <code>{foo}</code> will not be expanded.</li>
205 <li>If <code>{foo}</code> appears in the contents of <code>foo</code>, it will not be expanded.</li>
206 <li>Nor will it be expanded if it appears in the contents of <code>foo</code> as the result of expanding some other macro in the contents
207 of <code>foo</code>.</li>
208 </ul>
209
210 <p>(I stand corrected. That was more like 2.5 things to note.)</p>
211
212 <p>Macros can be defined and redefined with the special macro-like form <code>{*[foo][bar]}</code>. The first text between square
213 brackets is the name of the macro being defined; the text between the second square brackets is the contents. Both texts can contain
214 any symbols except unmatched <code>]</code>'s. i.e. you can put square brackets in these texts as long as they nest properly.</p>
215
216 <p>Now you see why we don't need arguments to these macros: you can simply use macros as arguments. For example,</p>
217
218 <pre>{*[SQR][*{X}*{X}*]}{*[X][5]}{SQR}</pre>
219
220 <p>uses an "argument macro" called <code>X</code> which it defines as <code>5</code> before calling the
221 <code>SQR</code> macro that uses it.</p>
222
223 <p>Note that macros are expanded before any scanning or parsing of the program text begins. Thus they can be used to
224 define identifiers, labels, etc.</p>
225
226 <h3>Comments</h3>
227
228 <p>The macro system also provides a way to insert comments into a Quylthulg program. It should be noted that there are
229 at least three schools of thought on this subject.</p>
230
231 <p>The first school (Chilton County High School in Clanton, Alabama) says
232 that most comments that programmers write are next to useless anyway (which is absolutely true) so there's no point in
233 writing them at all.</p>
234
235 <p>The second school (Gonzaga College S.J. in Dublin, Ireland — not to be confused with Gonzaga University
236 in Spokane, Washington) considers comments to be valuable <em>as comments</em>, but not as source code. They
237 advocate their use in Quylthulg by the definition of macros that are unlikely to be expanded for obscure syntactical reasons.
238 For example, <code>{*[}][This is my comment!]}</code>. Note that that macro <em>can</em> be expanded in Quylthulg
239 using <code>{}}</code>; it's just that the Gonzaga school hopes that you won't do that, and hopes you get a syntax
240 error if you try.</p>
241
242 <p>The third school (a school of fish) believes that comments
243 are valuable, not just as comments, but also as integral (or at least distracting) part of the computation, and champions their use in Quylthulg as string
244 literals involved in expressions that are ultimately discarded. For example, <code>&lt;"Addition is fun!"&lt;+1+2+&lt;</code>.</p>
245
246 <h3>Integration with the Rest of the Language</h3>
247
248 <p>To dispel the vicious rumours that the macro system used in Quylthulg and the Quylthulg language are really independent
249 and separate entities which just <em>happen</em> to be sandwiched together there, we are quick to point out that they are
250 bound by two very important means:</p>
251
252 <ul>
253 <li>At the beginning of the program, at a global scope, the identifier
254 <code>$Number of Macros Defined$</code> is bound to an integer constant containing
255 the number of unique macros that were defined during macro expansion before the program was parsed.</li>
256 <li>The panfix operator <code>%</code> applies macros to a Quylthulg string at runtime. The expression on the
257 left-hand side should evaluate to a string which contains macro definitions. The expression on the
258 right-hand side is the string to expand using these macro definitions.</li>
259 </ul>
260
261 <h2>Turing-Completeness</h2>
262
263 <p>Now, I claim that Quylthulg is Turing-complete — that is, that it can
264 compute anything that a Turing machine (or any other Turing-complete system) can.
265 I would provide a proof, but since the point of a proof is to dispel doubt, and since
266 you have not expressed any doubt so far (at least none that I have been able to observe
267 from my vantage point), and since (statistically speaking anyway)
268 you believe that fluoride in drinking water promotes dental health,
269 that the sun is a giant nuclear furnace, that Wall Street is substantially different
270 from Las Vegas, that a low-fat diet is an effective way to lose weight,
271 that black holes exist, and that point of the War on Drugs is to stop people from
272 harming themselves — well, in light of all that, a proof hardly seems called-for.
273 Instead, I shall perform a series of short vignettes, each intended to invoke the spirit
274 of a different forest animal or supermarket checkout animal. Then I shall spray you
275 with a dose of a new household aerosol which I have invented and which I am
276 marketing under the name "Doubt-B-Gone".</p>
277
278 <ul>
279 <li>We can use <code>foreach</code> as an if-then-else construct by using lists to represent booleans.
280
281 <p>Using <code>null</code> to represent false, and <code>cons</code> anything
282 to represent true, we use the <code>else</code> part of <code>foreach</code> to
283 accomplish a boolean if-then-else. We can employ <code>;</code> to get boolean OR and
284 nested <code>foreach</code>es to get boolean AND. (Detailed examples of these
285 can be found in the unit tests of the Quylthulg reference interpreter, which is called
286 "Qlzqqlzuup, Lord of Flesh".)</p></li>
287
288 <li>We can construct an infinite loop by running <code>foreach</code> on a cyclic
289 data structure.
290
291 <p>For example,</p>
292
293 <pre>
294 foreach $x$ = :L:[1, 2, 3, goto L] with $a$ = 0 be $x$ else be null
295 </pre>
296
297 <p>never finishes evaluating, and in the body, <code>$x$</code> takes on the values 1, 2, 3, 1, 2, 3, ... ad infinitum.</p></li>
298
299 <li>We can treat the accumulator of a <code>foreach</code> like an unbounded tape, just like on a Turing machine.
300
301 <p>We can pass in a <code>cons</code> cell where the first value is a list representing everything
302 to the left of the head, and the second value is a list representing everything to the right of the head.
303 Moving the head left or right can be accomplished by taking the first (<code>&lt;</code>) off the
304 appropriate list and cons (<code>,</code>) it onto the other list. There are also other ways to
305 do it, of course. The point is that there is no bound specified on the length of a list in Quylthulg.</p></li>
306
307 <li>We can, in fact, make <code>foreach</code> act like a <code>while</code> construct.
308
309 <p>We just combine the looping forever with an if-then-else which evaluates to <code>abort</code>
310 when the condition comes true.</p></li>
311
312 <li>We can give <code>foreach</code> a cyclic tree-like data structure which describes the
313 finite control of a Turing machine.
314
315 <p>Although we don't have to — we could just use nested <code>foreach</code>es to make a lot of
316 tests against constant values.</p></li>
317
318 <li>We can even make <code>foreach</code> work like <code>let</code> if we need to.
319
320 <p>Just bind the accumulator to <code>$Name$</code>, refer to <code>$Name$</code> in the
321 body, and ignore the contents of the one-element list. Or use it to bind two variables in one <code>foreach</code>.</p></li>
322
323 </ul>
324
325 <p style="color: blue">PHHSHHHHHHHHHHHHHHTt.</p>
326
327 <h2>Discussion</h2>
328
329 <p>Now I'm hardly the first person to suggest
330 using cyclic lists as an equivalent alternative to a general looping construct
331 such as <code>while</code>.
332 It has long been a <a class="external"
333 href="http://www.ccs.neu.edu/home/shivers/newstyle.html">stylish LISP programming
334 technique</a>. However, to comply with the Nietzschean-Calvinist mandate of our society
335 (that is, to <em>sustain</em> the <em>progress</em> that will <em>thrust</em> us toward the
336 "Perfect Meat at the End of Time" of which Hegel spoke,) we must <em>demonstrate</em> that
337 we have <strong>innovated</strong>:</p>
338
339 <ul>
340 <li>Quylthulg provides <em>only</em> this method of looping; without it, it would not be Turing-complete, and</li>
341 <li>Unlike the extant stylish programming techniques, which require side-effecting operations such
342 as <code>rplacd</code> to pull off, Quylthulg is a pure functional programming language
343 <em>without</em> updatable storage.</li>
344 </ul>
345
346 <p>Huzzah.</p>
347
348 <p>It is somewhat sad to consider just how long Quylthulg took to design and how much of that labour took
349 place aboard airplanes. It is even sadder to consider some of the delusions I was occupied with while designing
350 it. Some of the biggest were the idea that <code>foreach</code> somehow had to be recursable for this to
351 work — it doesn't, but I left it in. For similar reasons I left in <code>;</code>, the append operator.
352 And I've already mentioned the headaches with allowing labels and <code>goto</code>s in expressions
353 rather than only in literals.</p>
354
355 <p>Long live the new flesh, eh?
356 <br/>Chris Pressey
357 <br/>Seattle, Washington
358 <br/>Dec 6, 2008</p>
359
360 </body>
361 </html>
+606
-0
src/Qlzqqlzuup.hs less more
0 --
1 -- Copyright (c)2008-2011 Chris Pressey, Cat's Eye Technologies.
2 -- All rights reserved.
3 --
4 -- Redistribution and use in source and binary forms, with or without
5 -- modification, are permitted provided that the following conditions
6 -- are met:
7 --
8 -- 1. Redistributions of source code must retain the above copyright
9 -- notices, this list of conditions and the following disclaimer.
10 -- 2. Redistributions in binary form must reproduce the above copyright
11 -- notices, this list of conditions, and the following disclaimer in
12 -- the documentation and/or other materials provided with the
13 -- distribution.
14 -- 3. Neither the names of the copyright holders nor the names of their
15 -- contributors may be used to endorse or promote products derived
16 -- from this software without specific prior written permission.
17 --
18 -- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 -- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
20 -- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
21 -- FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
22 -- COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
23 -- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
24 -- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 -- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 -- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 -- LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
28 -- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 -- POSSIBILITY OF SUCH DAMAGE.
30 --
31
32 --
33 -- Qlzqqlzuup.hs v2011.0517
34 --
35 -- 'Qlzqqlzuup, the Lord of Flesh': Reference interpreter for
36 -- The Quylthulg Programming Language
37 -- v1.0
38 --
39
40 module Qlzqqlzuup where
41
42 import Char
43
44 -- ============ --
45 -- Environments --
46 -- ============ --
47
48 --
49 -- Environments associate names with values. Environments are used in three
50 -- places in this interpreter: to associate variable names with the values
51 -- bound to them, to associate macro names with the replacement text of each
52 -- macro, and to associate label names with the term being labelled.
53 --
54
55 findVal ((key,val):rest) x
56 | key == x = val
57 | otherwise = findVal rest x
58
59 extendEnv env key val = ((key, val):env)
60
61 newEnv = []
62
63 purgeEnv [] x = []
64 purgeEnv ((key, val):rest) x
65 | key == x = purgeEnv rest x
66 | otherwise = ((key, val):purgeEnv rest x)
67
68 -- ===== --
69 -- Terms --
70 -- ===== --
71
72 data Term = Int Integer
73 | Str String
74 | Cons Term Term
75 | Null
76 | Label String Term
77 | Goto String
78 | Abort
79 deriving (Show, Ord, Eq)
80
81 follow lenv (Label _ x) = follow lenv x
82 follow lenv (Goto label) = follow lenv (findVal lenv label)
83 follow lenv y = y
84
85 --
86 -- Terms support a number of operations which require the "meaning" of the
87 -- term, which may not be available in the term itself, since the term
88 -- might be a goto to a label which is labelling another quite disjoint
89 -- term. For these operations, an environment mapping labels to terms
90 -- is also passed, so that gotos can be followed.
91 --
92
93 type Op = [(String, Term)] -> Term -> Term -> Term
94
95 reduce lenv termA termB fn extract package =
96 let
97 valA = extract (follow lenv termA)
98 valB = extract (follow lenv termB)
99 in
100 package (fn valA valB)
101
102 strCat lenv a b = reduce lenv a b (++) (\(Str k) -> k) (\k -> Str k)
103
104 strExpand lenv a b =
105 reduce lenv a b (spander) (\(Str k) -> k) (\k -> Str k)
106 where
107 spander x y =
108 let
109 (expansions, expanded) = expand [("*","")] x
110 (_, expanded') = expand expansions y
111 in
112 expanded'
113
114 intAdd lenv a b = reduce lenv a b (+) (\(Int k) -> k) (\k -> Int k)
115 intMul lenv a b = reduce lenv a b (*) (\(Int k) -> k) (\k -> Int k)
116 intSub lenv a b = reduce lenv a b (-) (\(Int k) -> k) (\k -> Int k)
117
118 listCons lenv a b =
119 let
120 valA = follow lenv a
121 valB = follow lenv b
122 in
123 Cons valA valB
124
125 listFirst lenv term omgNo =
126 follow lenv (first (follow lenv term))
127 where
128 first (Cons a b) = a
129 first _ = omgNo
130
131 listRest lenv term omgNo =
132 follow lenv (rest (follow lenv term))
133 where
134 rest (Cons a b) = b
135 rest _ = omgNo
136
137 listAppend lenv a b =
138 let
139 valA = follow lenv a
140 valB = follow lenv b
141 in
142 if valA == Null then
143 valB
144 else
145 Cons (listFirst lenv valA Null) (listAppend lenv (listRest lenv valA Null) valB)
146
147 -- =========== --
148 -- Expressions --
149 -- =========== --
150
151 data Expr = Term Term
152 | Ident String
153 | ForEach String Expr String Expr Expr Expr
154 | BinOp Op Expr Expr
155
156 instance Show Expr where
157 show (Term t) =
158 show t
159 show (Ident s) =
160 "$" ++ s ++ "$"
161 show (ForEach x lis a acc body els) =
162 "foreach " ++ (show x) ++ "=" ++ (show lis) ++ " with " ++ (show a) ++ "=" ++ (show acc) ++
163 " be " ++ (show body) ++ " else be " ++ (show els)
164 show (BinOp op lhs rhs) =
165 "(" ++ (show lhs) ++ "," ++ (show rhs) ++ ")"
166
167 collectExprLabels (Term p) = collectTermLabels p
168 collectExprLabels (Ident _) = []
169 collectExprLabels (ForEach _ e1 _ e2 e3 e4) =
170 collectExprLabels e1 ++ collectExprLabels e2 ++ collectExprLabels e3 ++ collectExprLabels e4
171 collectExprLabels (BinOp _ a b) = collectExprLabels a ++ collectExprLabels b
172
173 collectTermLabels (Int _) = []
174 collectTermLabels (Str _) = []
175 collectTermLabels (Cons a b) = collectTermLabels a ++ collectTermLabels b
176 collectTermLabels (Null) = []
177 collectTermLabels (Label label term) = ((label, term): collectTermLabels term)
178 collectTermLabels (Goto _) = []
179 collectTermLabels (Abort) = []
180
181 -- =========== --
182 -- Interpreter --
183 -- =========== --
184
185 interpret :: [(String, Term)] -> [(String, Term)] -> Expr -> Term
186
187 interpret env lenv (Term x) =
188 x
189 interpret env lenv (Ident x) =
190 findVal env x
191
192 interpret env lenv (BinOp op a b) =
193 let
194 ra = interpret env lenv a
195 rb = interpret env lenv b
196 result = op lenv ra rb
197 in
198 result
199
200 --
201 -- The coup de grace, or perhaps coup d'etat: interpret foreach.
202 --
203
204 interpret env lenv (ForEach loopvar listExpr accvar accExpr applyExpr elseExpr) =
205 let
206 list = interpret env lenv listExpr
207 acc = interpret env lenv accExpr
208 in
209 if list == Null then
210 interpret env lenv elseExpr
211 else
212 qForEach list acc
213 where
214 qForEach Null acc = acc
215 qForEach (Cons first@(Cons _ _) rest) acc =
216 let
217 first' = follow lenv first
218 deepResult = qForEach first' acc
219 newAcc = follow lenv deepResult
220 nextResult = qForEach rest newAcc
221 in
222 follow lenv nextResult
223 qForEach (Cons first rest) acc =
224 let
225 first' = follow lenv first
226 env' = extendEnv env accvar acc
227 env'' = extendEnv env' loopvar first'
228 result = interpret env'' lenv applyExpr
229 newAcc = follow lenv result
230 nextResult = qForEach rest newAcc
231 in
232 if newAcc == Abort then
233 acc
234 else
235 follow lenv nextResult
236
237 -- =================== --
238 -- Monadic Interpreter --
239 -- =================== --
240
241 mInterpret :: [(String, Term)] -> [(String, Term)] -> Expr -> IO Term
242
243 mInterpret env lenv (Term x) =
244 return x
245 mInterpret env lenv (Ident x) =
246 return (findVal env x)
247
248 mInterpret env lenv (BinOp op a b) = do
249 ra <- mInterpret env lenv a
250 rb <- mInterpret env lenv b
251 return (op lenv ra rb)
252
253 --
254 -- The coup de grace, or perhaps coup d'etat: interpret foreach.
255 --
256
257 mInterpret env lenv (ForEach loopvar listExpr accvar accExpr applyExpr elseExpr) = do
258 list <- mInterpret env lenv listExpr
259 acc <- mInterpret env lenv accExpr
260 if
261 list == Null
262 then
263 mInterpret env lenv elseExpr
264 else
265 mqForEach list acc
266 where
267 mqForEach Null acc =
268 return acc
269 mqForEach (Cons first@(Cons _ _) rest) acc = do
270 deepResult <- mqForEach (follow lenv first) acc
271 nextResult <- mqForEach rest (follow lenv deepResult)
272 return (follow lenv nextResult)
273 mqForEach (Cons first rest) acc = do
274 result <- mInterpret (
275 extendEnv (extendEnv env accvar acc) loopvar (follow lenv first)
276 ) lenv applyExpr
277 newAcc <- do return (follow lenv result)
278 nextResult <- mqForEach rest newAcc
279 return (if newAcc == Abort then
280 acc
281 else
282 follow lenv nextResult)
283
284 -- =========== --
285 -- ParseEngine --
286 -- =========== --
287
288 data Expected = Token String
289 | Expr
290
291 parseEngine [] string = ([], string)
292
293 parseEngine (Token token:es) string =
294 parseEngine es (expect token string)
295
296 parseEngine (Expr:es) string =
297 let
298 (expr, rest) = parse string
299 (more, final) = parseEngine es rest
300 in
301 ((expr:more), final)
302
303 --
304 -- Given a mapping (as a list of pairs) between tokens
305 -- and functions to parse what comes after those tokens,
306 -- check the beginning of the given string for each of
307 -- those tokens and, upon a match, parse appropriately.
308 --
309
310 parseToken [] string omgNo = (omgNo string)
311 parseToken ((token, func):rest) string omgNo =
312 if take (length token) string == token then
313 func (drop (length token) string)
314 else
315 parseToken rest string omgNo
316
317 expect token string@(char:chars)
318 | isSpace char =
319 expect token chars
320 | take (length token) string == token =
321 drop (length token) string
322
323 stripspace [] = []
324 stripspace string@(char:chars)
325 | isSpace char =
326 stripspace chars
327 | otherwise = string
328
329 -- =========== --
330 -- Term Parser --
331 -- =========== --
332
333 --
334 -- This just handles constant literal terms. It is called
335 -- by the general parser when it doesn't know what else it
336 -- should do.
337 --
338
339 parseTerm string@(char:chars)
340 | isSpace char =
341 parseTerm chars
342 | isDigit char =
343 parseIntLit string 0
344 | otherwise =
345 parseToken termTokenList string omgNo
346 where
347 omgNo string = ((Str "BADTERM"), string)
348
349 termTokenList = [
350 ("~~", \string -> ((Str "$"), string)),
351 ("~", \string ->
352 let
353 ((Ident text), rest) = parse string
354 in
355 ((Str text), rest)),
356 ("[", parseList),
357 (":", parseLabel),
358 ("null", \string -> (Null, string)),
359 ("abort", \string -> (Abort, string)),
360 ("goto", \string ->
361 let
362 ((Ident label), rest) = parse string
363 in
364 ((Goto label), rest))
365 ]
366
367 --
368 -- Parse Prolog/Erlang-derived constant list syntax.
369 --
370
371 parseList string =
372 let
373 (terma, rest) = parseTerm string
374 rest' = stripspace rest
375 (termb, rest'') = parseList' rest'
376 in
377 (Cons terma termb, rest'')
378
379 parseList' (',':rest) = parseList rest
380 parseList' (']':rest) = (Null, rest)
381 parseList' ('|':rest) =
382 let
383 (term, rest') = parseTerm rest
384 rest'' = expect "]" rest'
385 in
386 (term, rest'')
387
388 --
389 -- Parse labels and identifiers.
390 --
391
392 parseLabel string =
393 let
394 (label, rest) = parseLabel' string
395 (term, rest2) = parseTerm rest
396 in
397 (Label label term, rest2)
398
399 parseLabel' (':':chars) =
400 ("", chars)
401 parseLabel' string@(char:chars) =
402 let
403 (movie, rest) = parseLabel' chars
404 in
405 ((char:movie), rest)
406
407 parseIdent ('$':chars) =
408 (Ident "", chars)
409 parseIdent string@(char:chars) =
410 let
411 ((Ident movie), rest) = parseIdent chars
412 in
413 (Ident (char:movie), rest)
414
415 parseFullIdent string = parseIdent (expect "$" string)
416
417 --
418 -- Parse nested strings.
419 --
420
421 parseNestedString string =
422 parseNestedString' 0 (expect "[" string)
423
424 parseNestedString' 0 (']':chars) =
425 ("", chars)
426 parseNestedString' level string@(char:chars) =
427 let
428 newLevel = level + adjustLevel char
429 (movie, rest) = parseNestedString' newLevel chars
430 in
431 ((char:movie), rest)
432 where
433 adjustLevel '[' = 1
434 adjustLevel ']' = -1
435 adjustLevel _ = 0
436
437 --
438 -- Parse numbers.
439 --
440
441 digitVal '0' = 0
442 digitVal '1' = 1
443 digitVal '2' = 2
444 digitVal '3' = 3
445 digitVal '4' = 4
446 digitVal '5' = 5
447 digitVal '6' = 6
448 digitVal '7' = 7
449 digitVal '8' = 8
450 digitVal '9' = 9
451
452 parseIntLit "" num = ((Int num), "")
453 parseIntLit string@(char:chars) num
454 | isDigit char =
455 parseIntLit chars (num * 10 + digitVal char)
456 | otherwise =
457 ((Int num), string)
458
459 -- ====== --
460 -- Parser --
461 -- ====== --
462
463 parse string@(char:chars)
464 | isSpace char =
465 parse chars
466 | otherwise =
467 parseToken tokenList string omgNo
468 where
469 omgNo string =
470 let
471 (term, rest) = parseTerm string
472 in
473 ((Term term), rest)
474
475 tokenList = [
476 ("$", parseIdent),
477 ("<", parsePanfix "<" listFirst),
478 (">", parsePanfix ">" listRest),
479 (",", parsePanfix "," listCons),
480 (";", parsePanfix ";" listAppend),
481 ("&", parsePanfix "&" strCat),
482 ("%", parsePanfix "%" strExpand),
483 ("+", parsePanfix "+" intAdd),
484 ("-", parsePanfix "-" intSub),
485 ("*", parsePanfix "*" intMul),
486 ("foreach", parseForEach)
487 ]
488
489 parsePanfix delim op string =
490 let
491 (expr1, rest1) = parse string
492 rest2 = expect delim rest1
493 (expr2, rest3) = parse rest2
494 rest4 = expect delim rest3
495 in
496 ((BinOp op expr1 expr2), rest4)
497
498 parseForEach string =
499 let
500 rules = [Expr, Token "=", Expr, Token "with", Expr, Token "=", Expr, Token "be", Expr, Token "else", Token "be", Expr]
501 ([(Ident loopvar), list, (Ident accvar), acc, expr, elsepart], rest) = parseEngine rules string
502 in
503 (ForEach loopvar list accvar acc expr elsepart, rest)
504
505 -- ============== --
506 -- Macro Expander --
507 -- ============== --
508
509 --
510 -- A macro environment maps macro names to macro definitions. A macro name
511 -- is a string. It would have been really nice to have a macro definition
512 -- be a function which takes a string (the input stream) and which returns
513 -- a string (the transformed input stream) and a new macro environment (for
514 -- macros which can define other macros.) But that means that macro env-
515 -- ironments would be of infinite type, and sadly, Haskell doesn't like that
516 -- very much. Instead, a macro definition is simply a string as well, and
517 -- some macro names (namely "*") are treated specially.
518 --
519
520 expand env "" =
521 (env, "")
522 expand env ('{':chars) =
523 expandMacro env env chars
524 expand env (char:chars) =
525 let
526 (env', rest) = (expand env chars)
527 in
528 (env', (char:rest))
529
530 expandMacro env [] string =
531 let
532 (env', more) = expand env string
533 in
534 (env', "{" ++ more)
535 expandMacro env ((name, body):defns) string =
536 if take (length name) string == name then
537 let
538 rest = (drop (length name) string)
539 (env', subst, rest') = handleMacro env name body rest
540 (env'', rest'') = expand env' rest'
541 in
542 (env'', subst ++ rest'')
543 else
544 expandMacro env defns string
545
546 handleMacro env "*" _ rest =
547 let
548 (name, rest2) = parseNestedString rest
549 (body, rest3) = parseNestedString rest2
550 env' = ((name, body):env)
551 in
552 (env', "", (expect "}" rest3))
553
554 handleMacro env name body rest =
555 let
556 env' = purgeEnv env name
557 (env'', expanded) = expand env' body
558 in
559 if expanded == body then
560 (env, expanded, (expect "}" rest))
561 else
562 handleMacro env'' name expanded rest
563
564 -- ======== --
565 -- Toplevel --
566 -- ======== --
567
568 integerLength [] = (0 :: Integer)
569 integerLength (x:y) = (1 :: Integer) + integerLength y
570
571 initialEnv expansions =
572 let
573 numberOfMacrosDefined = (integerLength expansions) - 1
574 in
575 extendEnv newEnv "Number of Macros Defined" (Int numberOfMacrosDefined)
576
577 parsed program =
578 let
579 (_, expanded) = expand [("*","")] program
580 (expr, _) = parse expanded
581 in
582 expr
583
584 run program =
585 let
586 (expansions, expanded) = expand [("*","")] program
587 (expr, _) = parse expanded
588 lenv = collectExprLabels expr
589 env = initialEnv expansions
590 result = interpret env lenv expr
591 in
592 result
593
594 showRun = show . run
595
596 mrun :: String -> IO Term
597
598 mrun program = do
599 (expansions, expanded) <- return (expand [("*","")] program)
600 expr <- return (fst (parse expanded))
601 lenv <- return (collectExprLabels expr)
602 env <- return (initialEnv expansions)
603 result <- mInterpret env lenv expr
604 print result
605 return result
+3
-0
test.sh less more
0 #!/bin/sh
1
2 cd src && falderal test ../tests/Quylthulg.falderal
+153
-0
tests/Quylthulg.falderal less more
0 -> encoding: UTF-8
1
2 Test Suite for Quylthulg
3 ========================
4
5 This test suite is written in the format of Falderal 0.5. It is far from
6 exhaustive, but provides a basic sanity check that the language I've designed
7 here comes close to what I had in mind.
8
9 Quylthulg Tests
10 ---------------
11
12 -> Tests for Haskell function Qlzqqlzuup:showRun
13
14 Integer expressions.
15 --------------------
16
17 | 5
18 = Int 5
19
20 | +6+9+
21 = Int 15
22
23 | +1+*7*-8-1-*+
24 = Int 50
25
26 String expressions.
27 -------------------
28
29 | &~$Shoes are $&&~~&~$4.99 a pair$&&
30 = Str "Shoes are $4.99 a pair"
31
32 List expressions.
33 -----------------
34
35 | [1,2,3]
36 = Cons (Int 1) (Cons (Int 2) (Cons (Int 3) Null))
37
38 | [1,2|3]
39 = Cons (Int 1) (Cons (Int 2) (Int 3))
40
41 | <[1,2|3]<abort<
42 = Int 1
43
44 | <1<abort<
45 = Abort
46
47 | >[1,2|3]>abort>
48 = Cons (Int 2) (Int 3)
49
50 | >1>null>
51 = Null
52
53 | ,1,,2,3,,
54 = Cons (Int 1) (Cons (Int 2) (Int 3))
55
56 | ;[1,2];[3];
57 = Cons (Int 1) (Cons (Int 2) (Cons (Int 3) Null))
58
59 | ;[1,2];3;
60 = Cons (Int 1) (Cons (Int 2) (Int 3))
61
62 | ;null;null;
63 = Null
64
65 | ;[1];null;
66 = Cons (Int 1) Null
67
68 | ;null;[1];
69 = Cons (Int 1) Null
70
71 Labels and gotos.
72 -----------------
73
74 | :A:goto$A$
75 = Label "A" (Goto "A")
76
77 Foreach expressions.
78 --------------------
79
80 | foreach $n$=[7,2,3] with $a$=0 be +$a$+$n$+ else be abort
81 = Int 12
82
83 | foreach $n$=null with $a$=0 be +$a$+$n$+ else be abort
84 = Abort
85
86 | foreach $n$=[1,2,3] with $a$=null be ,$n$,$a$, else be null
87 = Cons (Int 3) (Cons (Int 2) (Cons (Int 1) Null))
88
89 | foreach $n$=;[1];[1]; with $a$=[1] be $a$ else be null
90 = Cons (Int 1) Null
91
92 | foreach $n$=;null;[1]; with $a$=[1] be $a$ else be null
93 = Cons (Int 1) Null
94
95 | foreach $n$=;[1];null; with $a$=[1] be $a$ else be null
96 = Cons (Int 1) Null
97
98 | foreach $n$=;null;null; with $a$=[1] be $a$ else be null
99 = Null
100
101 This is how boolean expressions can be built with foreaches.
102
103 | foreach $n$=[1] with $a$=[1] be
104 | foreach $m$=$a$ with $b$=null be [1]
105 | else be null
106 | else be null
107 = Cons (Int 1) Null
108
109 | foreach $n$=null with $a$=[1] be
110 | foreach $m$=$a$ with $b$=null be [1]
111 | else be null
112 | else be null
113 = Null
114
115 | foreach $n$=[1] with $a$=null be
116 | foreach $m$=$a$ with $b$=null be [1]
117 | else be null
118 | else be null
119 = Null
120
121 | foreach $n$=null with $a$=null be
122 | foreach $m$=$a$ with $b$=null be [1]
123 | else be null
124 | else be null
125 = Null
126
127 Macros.
128 -------
129
130 | {*[Five][5]}{Five}
131 = Int 5
132
133 | {*[(A][1]}+{(A}+4+
134 = Int 5
135
136 | {*[SQR][*{X}*{X}*]}{*[X][5]}{SQR}
137 = Int 25
138
139 | {*[}][This is my comment!]}~${}}$
140 = Str "This is my comment!"
141
142 | {*[Dave][3]}{*[Emily][4]}$Number of Macros Defined$
143 = Int 2
144
145 | &~${$&~$*[S][T]}$&
146 = Str "{*[S][T]}"
147
148 | &~${$&~$S}$&
149 = Str "{S}"
150
151 | %&~${$&~$*[S][T]}$&%&~${$&~$S}$&%
152 = Str "T"