Debian Codegraph @

HOWTOs/GNU-APL-Designers-Guide.asciidoc

raw
1 //vim: et:ts=4:sw=4:tw=78
2
3 :Author: Dr. Jürgen Sauermann, GNU APL
4
5 :page-width: 120em
6 :toc: auto
7 :toclevels: 4
8 :iconsdir: /usr/share/asciidoc/icons
9 :icons:
10
11 = An Introduction for Designers and Contributors to the GNU APL Interpreter
12
13 == Abstract
14
15 This document contains a number of unrelated hints that may be useful to
16 understanding the GNU APL source code. Its primary purpose is to support
17 the fading memory of the author, but it may be interesting for others as well.
18 In addition to the hints there are also a number of rules. These rules
19 should be observed by those who contribute C/Cpp source code to the
20 GNU APL project (as opposed to those that contribute APL code).
21
22 This document is *NOT* aimed at the normal GNU APL user, i.e. at the APL
23 programmer. Those users are referred to the various *README* files in the
24 top-level GNU APL directory.
25
26 == The GNU APL Build System
27
28 All commands described below shall executed in the top-level GNU APL directory.
29 The top-level GNU APL directory is the directory that contains - after
30 unpacking a GNU APL tar file like *apl-2.0.tar.gz* or after fetching the GNU
31 APL sourced with SVN or with git - the file named *configure.ac*.
32
33 GNU APL uses *automake* and *autoconf* to build the interpreter. The build
34 system performs a number of major steps in typically different places and
35 by different persons (C/Cpp designer/maintainer vs. user):
36
37 === Step 1: Generate ./configure and a Makefile.in for every Makefile.am
38
39 Every directory of the GNU APL source tree contains a file named *Makefile.am*.
40 The command *autoreconf*, performed in top-level directory of the GNU APL
41 source tree:
42
43 ----
44 $ autoreconf
45 ----
46
47 generates a file named *Makefile.in* for every *Makefile.am*. In addition it
48 creates a script named *configure*. This is normally done by the maintainer
49 and the *Makefile.in* files produced are shipped with GNU APL (tar file or
50 svn/git repository).
51
52 The absolutely cool thing about *autoconf* (as opposed to e.g. *Cmake* or GUI
53 based IDEs) is that *autoconf* and *automake* themselves need not be installed
54 by the end users. The *configure* script produced by *autoreconf* is
55 self-contained and can be executed by the end user to configure different
56 aspects of the GNU APL interpreter. To accommodate this, the different
57 *Makefile.in* files are shipped with GNU APL even though they are somewhat
58 redundant (and, compared to the *Makefile.am*, pretty large).
59
60 In essence *Makefile.am* files are easy to read and maintain by humans, while
61 *Makefile.in*s are easy to decode by machines, in particular by the *configure*
62 script that is produced along with them. In GNU APL the *autoreconf* command
63 produces a more than 1,000 line top-level *Makefile.in* from a 150 line
64 *Makefile.am* and a 25,000 line ./configure script from its 1,000 line
65 *configure.ac*
66
67 NOTE: If a maintainer adds a new directory to the source tree, then she needs
68 to add the final *Makefile* in the top-level file *configure.ac* (in m4 macro
69 *AC_CONFIG_FILES), otherwise the *Makefile.am* will be ignored.
70
71 The most important take-away here is that the user or maintainer should never
72 edit **Makefile**s or **Makefile.in**s because doing so is cumbersome,
73 error-prone, and useless since *autoreconf* will overwrite any changes made.
74
75 === Step 2: Generate a Makefile for every Makefile.in
76
77 The next step is to run the *configure* script produced in the previous step.
78 It is performed by the end user (or by the system administrator where
79 appropriate) in the top-level directory of the GNU APL source tree:
80
81 ----
82 $ ./configure
83 ----
84
85 The typical end user will run *./configure* without any arguments, while
86 experts may run it with additional arguments (see README-2-configure
87 for details). The primary task of *./configure* is to convert every
88 *Makefile.in* into a corresponding *Makefile*. In doing so, the script tries
89 to determine which and where the libraries and header files used by GNU APL
90 are installed on the user's system. The system functions and variables of the
91 final GNU APL interpreter behaves differently depending on the libraries and
92 header files present. For example, *⎕FFT* (Fast Fourier Transforms) depends
93 on library *libfftw3* and if that library (or its header files) are missing
94 then ⎕FFT will raise a syntax error instead of computing the FFT.
95
96 NOTE: On typical Debian systems, libraries and header files are often
97 contained in different packages that should all be installed.
98
99 For example, in the ⎕FFT case there are 3 packages:
100
101 * libfftw3-bin # the library itself
102 * libfftw3-dev # header files for the library, and
103 * libfftw3-doc # documentation related to the library
104
105
106 For ⎕FFT to work the first two are needed and the third does not hurt.
107 Most of the other libraries follow the same naming scheme for Debian packages.
108
109 The configure script produces a lot of output that is useful if a library or
110 its header file(s) are missing. The final result of the decisions made by
111 configure is collected in file *config.h* so that the compiler can adapt
112 itself to the presence or absence of libraries and their header files.
113
114 If a library is not detected even though it is installed then either:
115
116 * the test performed by ./configure is faulty and then either configure.ac
117 or else a more complex test file in sub-directory *m4* need to be fixed, or
118
119 * the library only lives in a non-standard location (e.g. below the user's
120 home and then ./configure hopefully provides ./configure option to
121 specify that location.
122
123 === Step 3: Compile and Link the GNU APL Interpreter
124
125 The final step is to compile the interpreter:
126 ----
127 $ make
128 ----
129
130 The code base is quite large, therefore one may prefer to compile several
131 sources in parallel. For example, on an 8 core CPU:
132
133 ----
134 make -j 7
135 ----
136
137 leaving one core for other purposes. If the compilation is successful then the
138 interpreter is named *apl* in directory *src*, i.e. *src/apl*. During
139 development, the interpreter can be started from there without installing it:
140
141 ----
142 $ src/apl
143 -----
144
145 After the development is done, the interpreter is installed properly.
146
147 NOTE: The steps described only require write permission in and below the
148 top-level directory, for instance below the user's $HOME directory.
149 The next step requires write permissions in directories that are normally not
150 writable by ordinary users.
151
152 === Step 4: Install the GNU APL Interpreter
153
154 Installation of the interpreter must be performed by root:
155
156 ----
157 $ sudo make install
158 ----
159
160 CAUTION: A common mistake (by the author) is to try to install the interpreter
161 after the previous step has failed. The build system will then try to
162 recompile missing files, but the resulting files will now be owned by root
163 and will no longer be writable by the user. To fix this:
164
165 ----
166 $ sudo chown -R username.username . # assume user is 'username'
167 ----
168
169 The *make install* installs a few files (all owned by root, but with read
170 permissions for everybody):
171
172 * The APL interpreter itself in */usr/local/bin/apl*,
173 * interpreter-related header files */usr/local/include/apl*,
174 * interpreter-related libraries */usr/local/lib/apl*,
175 * an info file in */usr/local/share/info/apl.info*,
176 * a man page in */usr/local/share/man/man1/apl.1*
177
178 The default installation prefix */usr/local* can be changed with *./configure*
179 options.
180
181 === Summary
182
183 The following picture illustrates the different steps to build the GNU APL
184 interpreter and the files involved:
185
186 ----
187 ┌─────────────┐
188 ┌┴────────────┐│ ┌──────────────┐
189 ┌┴────────────┐├┘ │ configure.ac │ autoreconf (GNU APL designer)
190 │ Makefile.am ├┘ └──────────────┘
191 └─────────────┘ ↓
192 ↓ ↓ ──────────────────────────
193 ┌─────────────┐ ↓
194 ┌┴────────────┐│ ┌───────────┐
195 ┌┴────────────┐├┘ │ configure │
196 │ Makefile.in ├┘ └───────────┘
197 └─────────────┘
198 ↓ ./configure (User)
199 ┌──────────┐ ┌──────────┐
200 ┌┴─────────┐│ ┌┴─────────┐│
201 ┌┴─────────┐├┘ ┌┴─────────┐├┘
202 │ Makefile ├┘ │ src/*.cc ├┘
203 └──────────┘ └──────────┘
204 ↓ ──────────────────────────
205 ┌─────────┐
206 │ src/apl │ make (User)
207 └─────────┘
208 ↓ ──────────────────────────
209 ╔════════════════════╗
210 ║ /usr/local/bin/apl ║ make install (root)
211 ╚════════════════════╝
212 ↓ ──────────────────────────
213 ----
214
215
216
217 === Special make targets
218
219 The typical user shall simply run 'make' in the top-level directory.
220
221 For experts there are some more make targets (defined in *Makefile.incl*),
222 again with *make* run in the top-level directory, unless noted otherwise.
223
224 === make help
225
226 Shows all top-level make targets:
227
228 ----
229 In addition to the standard make targets (all, install, clean, ...),
230 the following make targets may be supported (at this level):
231
232 make help - print this text
233 make DIST - dist + a Makefile that calls ./configure
234 make DOXY - create Doxygen documentation
235 make RPM - create (source and binary) RPMs
236 make DEB - create Debian packages
237
238 make SVNUP - update from SVN and ./configure
239
240 NOTE: The RPM and DEB targets may fail because they require additional tools
241 that may not be present on your machine. Don't worry if that happens, unless
242 you really need the RPM and/or Debian packages.
243
244 The following targets are shortcuts for lazy developers (like the GNU APL
245 author) and are not very useful for normal users:
246
247 make develop - enable full dependency tracking
248 make gprof - make develop + enable gprof profiling
249 make python - make develop + build python module
250 make parallel - enable multi-core APL (buggy and experimental!)
251 make parallel1 - make parallel for benchmarking
252 make VPATH_clean - prepare for VPATH build
253 ----
254
255 === make test
256
257 This make target is only available in sub-directory *src*. It builds the
258 interpreter and then runs all testcases (= files with extension *.tc*)
259 that are present in directory *src/testcases*. The total result of all
260 testcases is stored in *src/testcases/summary.log*, and every testcase
261 *x* produces a log file *src/testcases/x.tc.log* with details of the test
262 execution.
263
264 === make apl.lines
265
266 This make target is only available in sub-directory *src*. It produces a file
267 named *src/apl.lines* and must be run right after building the interpreter.
268 When the interpreter produces a stack trace (i.e. it lists the Cpp call stack)
269 then:
270
271 * If the *apl.lines* file is absent or older than the interpreter, the stack
272 trace will show function names and code offsets in hex. For short functions
273 that is sort of OK, but for longer ones the hex numbers can make it difficult
274 to find the exact location of the fault that has triggered the stack trace.
275
276 * If the *apl.lines* file is up-to-date (i.e. *make apl.lines* was run after
277 the interpreter binary was produced), then the stack traces will show source
278 file line numbers instead of hex numbers. Producing *apl.lines* takes quite
279 a while, therefore it is not built automatically.
280
281 === make gen / gen2
282
283 These make targets are only available in sub-directory *tools*. Each produces
284 the file *src/Prefix.def*. After every new token it reads, the interpreter has
285 to decide if (and which) a new reducible phrase is present. This check is
286 executed in the inner loop of the interpreter, therefore the efficiency
287 of this check is crucial for the performance of the interpreter.
288
289 * GNU APL uses *tools/phrase_gen* to produce *src/Prefix.def*.
290 * *src/Prefix.def* is therefore automatically generated and *#included* in
291 *Prefix.hh* and in *Prefix.cc* (= the interpreter source code that performs
292 the phrase matching).
293 * The *phrase_gen* tool can produce two types of code:
294 ** either a collision-free hash table (the default),
295 ** or else a search tree.
296 * After a *make gen* the next compiler build will use the hash table, while
297 after *make gen2 it will use a search tree. Performance tests of both
298 alternatives have shown only a marginal performance difference between
299 both methods, but the technique as such might be of interest.
300
301 == Source Code Documentation
302
303 GNU APL is fully documented with *Doxygen*. The term *fully* means that every
304 class member has a (typically rather brief) Doxygen description and *not* that
305 the description is exhaustive. The purpose is primarily to be a memory aid for
306 browsing the source code.
307
308 The entire *Doxygen* documentation of GNU APL can, provided that *Doxygen*
309 itself is installed, be produced like this:
310
311 ----
312 make DOXY
313 ----
314
315 The result is around 6,000 files in directory *html*. After generating them,
316 the files can be browsed with e.g.
317
318 ----
319 firefox html/index.html
320 ----
321
322 or with some other browser. The *Doxygen* documentation is a good starting
323 point for those that want to get a quick overview of the GNU APL source code.
324
325 == Source Code File Types
326
327 The *Makefile* files belong to the build system and were explained above.
328 What remains are:
329
330 * C source files (file extension *.c*) are almost never used,
331 * C header files (file extension *.h*) are almost never used, a noteworthy
332 exception is *config.h* which is produced by the *./configure* script,
333 * Cpp source files for inline functions (file extension *.icc*),
334 * Cpp source files (file extension *.cc*),
335 * Cpp header files (file extension *.hh*), and
336 * pure macro files (file extension *.def*).
337
338 By and large, the rules for C and Cpp source and header files are:
339
340 * Small and many rather than large and few (aka. modularity). Early versions
341 of GNU APL did not follow this rule and some left-overs still do not (but
342 those will be further modularized in the future).
343 * One class per file; the file name reflects the class name. Exceptions are:
344 * classes that are closely related (e.g. classes *Token* and *Token_string*).
345 * The .cc and .hh file names are the same, except for the file name extension
346 and classes with a small (say, < 100 lines) source footprint (e.g. those in
347 PrimitiveFunction.hh and PrimitiveFunction.cc).
348 * Cpp declarations can be made in the .cc file if their scope is local to the
349 .cc file (like static declarations in C), otherwise they go into the
350 corresponding .hh file.
351
352 === .def Files
353
354 C/Cpp source files primarily contain C/Cpp code and occasionally declarations.
355 C/Cpp header files primarily contain C/Cpp declarations and often (inline)
356 C/Cpp code. In contrast, .def files contain neither C/Cpp code nor
357 C/Cpp declarations. They only contain macro calls whereby the definition of
358 the macro is defined outside the .def file. Currently there are about 20 .def
359 files in the GNU APL source code so that they deserve an explanation.
360
361 ==== Why .def Files?
362
363 Suppose we have a number of integer error codes:
364
365 ----
366 enum ErrorCode
367 {
368 NO_ERROR = 0,
369 SYNTAX_ERROR = 1,
370 RANK_ERROR = 2,
371 LENGTH_ERROR = 4
372 };
373 ----
374
375 Sooner or later we need a string that describes the error in a human readable
376 format. This requires a mapping between integer error codes and string
377 literals. There are 2 standard methods in C/Cpp to define such a mapping.
378
379 ==== Method 1: struct definition
380
381 ----
382 struct _error_map
383 {
384 ErrorCode ecode;
385 const char * ename;
386 } error_map =
387 {
388 { NO_ERROR, "OK" },
389 { SYNTAX_ERROR, "Syntax Error" },
390 { RANK_ERROR, "Rank Error" },
391 { LENGTH_ERROR, "Length Error" }
392 } error_map;
393
394 const char *
395 get_error_string(ErrorCode ec)
396 {
397 return error_map[ec];
398 }
399 ----
400
401 ==== Method 2: switch statement
402
403 ----
404 const char *
405 get_error_string(ErrorCode ec)
406 {
407 switch(ec)
408 {
409 case NO_ERROR: return "OK";
410 case SYNTAX_ERROR: return "Syntax Error";
411 case RANK_ERROR: return "Rank Error";
412 case LENGTH_ERROR: return "Length Error";
413 }
414 return "Unknown error";
415 }
416 ----
417
418 Now suppose we add another ErrorCode *DOMAIN_ERROR* to the *enum ErrorCode*.
419 Suppose further that we add the new error code to the enum but not to the
420 *get_error_string()* function. This is a fairly common mistake, in particular
421 because *ErrorCode* is usually declared in a *.hh* file and
422 *get_error_string()* is defined in the corresponding *.cc* file. In that case
423 Method 1 will most likely produce a segmentation fault at runtime, which is
424 about the worst case that may happen. <Method 2 is a little better because a
425 smart compiler like g++ will issue a warning in this case. Both methods are,
426 however, quite inconvenient for the C/Cpp programmer, in particular if many
427 such mappings are needed in a larger program.
428
429 In GNU APL this problem is solved in the following way:
430
431 * #define a macro that expresses the relationship (between integer error codes
432 and C/Cpp literals for the corresponding error text in our example), and
433 * call that macro, typically in several different files with the macro
434 defined differently. Calling the macro is performed by #including
435 the .def file. In our example:
436
437 In e.g. *errors.def*:
438
439 ----
440 error_def(NO_ERROR , 0, OK )
441 error_def(SYNTAX_ERROR , 1, Syntax Error )
442 error_def(RANK_ERROR: 2, Rank Error )
443 error_def(LENGTH_ERROR: 3, Length Error )
444
445 #undef error_def /* to detect missing definitions of the error_def() macro */
446 ----
447
448 In, say, *errors.hh*:
449
450 ----
451 enum ErrorCode
452 {
453 #define error_def(enum_name, enum_value, _error_string) \
454 enum_name = enum_value,
455 #include "errors.def"
456 };
457 ----
458
459 And finally in *errors.cc*:
460
461 ----
462 const char *
463 get_error_string(ErrorCode ec)
464 {
465 switch(ec)
466 {
467 #define error_def(enum_name, _enum_value, error_string) \
468 case enum_name: return #error_string;
469 #include "errors.def"
470 }
471 return "Unknown error";
472 }
473 ----
474
475 Note the following:
476
477 * the macro invocations of *error_def()* (in the *.def* file) have more
478 arguments than are used in their macro definitions (in the *.hh* or *.cc*
479 files). GNU APL has a naming convention that unused macro arguments of
480 macros (which are typical for the *.cc* and *.hh* files) start with
481 underscore (_). For this reason the argument lists of the #defines above
482 differ slightly.
483 * *error_string* is not quoted in *errors.def* even though *get_error_string()*
484 returns a const char *. The quoting is performed by pass:[# in #error_string]
485 (a preprocessor feature).
486 * the example above uses a simple 1:1 relation between two types. Some *.def*
487 files use more than two sides, e.g. numeric IDs, string names, and help
488 texts.
489
490 === Rules for .def Files
491
492 * The *.def* file should *#undef* all macros that it uses. This is a safeguard
493 against forgetting to *#define* a macro before #including the *.def* file
494 (this may or may not be detectable by the compiler).
495 * A *.def* file should normally not use more than one macro. An exception
496 occurs when macros are very similar (e.g. SystemVariable.def with macro
497 * ro_sv_def* (for read-only system variables), *rw_sv_def* (for read/write
498 system variables), and *sf_def* for system functions).
499 * item separators such as , in enums or ; in case statements are contained in
500 the macro definitions (i.e. in the *.hh* or *.cc* file) and not in the macro
501 call (i.e. not in the *.def* file). This is because the separators may differ
502 for different macros.
503
504 The most important take-aways here are:
505
506 * *.def* files contain only macro invocations,
507 * *.def* files are #included in several files and almost certainly the macro
508 definitions (before #including a *.def* file) differ between the files,
509 * the macros are #defined outside the *.def* file but #undef'ed inside the
510 *.def* file. (This is normally a bad programming practice, but on purpose
511 here).
512
513 == Coding Style
514
515 GNU APL is a GNU project. For the most part it therefore follows the GNU
516 coding standard, see: https://www.gnu.org/prep/standards/standards.html
517 With some minor deviations which attempt to further improve the readability
518 of the C/Cpp code.
519
520 === General
521
522 * keep lines short (≤ 78 characters) where possible
523 * NEVER use tabs (ASCII 0x09) in the source code
524
525 === Indentation and Blanks
526
527 ==== Function bodies (.cc files)
528
529 * Variable declarations at top-level scope are *_not_* indented:
530 * Cpp code at the top-level scope is indented with 3 blanks:
531
532 ----
533 void
534 foo()
535 {
536 int x = 0; // declaration: not indented!
537
538 printf("%d:, x); // code: indented by 3 spaces
539
540 int y = 1; // another declaration.
541 ...
542 }
543 ----
544
545 * Variable declarations below top-level scope are indented with 2 (from the {
546 starting the scope
547 * Cpp code below the top-level scope are also indented with 2 blanks:
548
549 ----
550 void
551 foo()
552 {
553 int x = 0; // declaration: not indented!
554 int y = 1; // another declaration.
555
556 if (x)
557 { // start of sub-scope
558 printf("positive x=%d", x); // code: indented by 2 spaces
559 }
560 else
561 { // start of another sub-scope
562 printf("zero x"); // code: indented by 2 spaces
563 }
564 }
565 ----
566
567 ==== Conditionals
568
569 * conditionals are not functions! put 1 blank between the keyword and the
570 condition
571 * the body of the conditional is indented according to the opening *(* of the
572 condition (for short ones like if, else, or for), but no more than 2 blanks:
573
574 ----
575 void
576 foo()
577 {
578 int x = 0;
579
580 // DO NOT:
581 if(i == 0)
582
583 // DO:
584 if (i == 0)
585 {
586 ...
587 }
588
589 for (int i = 0; i < N; ++i)
590 {
591 ...
592 }
593
594 while (i == 0)
595 {
596 ...
597 }
598 }
599 ----
600
601 * you MAY put single statements or very short bodies onto the condition line,
602 * but NOT mix single- and multi-line styles for *if* and *else* clauses, and
603 * place the { and } of multi-line bodies on the same column, that is:
604 * you MUST NEVER NEVER NEVER use K&R style:
605
606 ----
607 // DO:
608
609 if (x >= 0) return "positive";
610 else return "negative";
611
612 // DO NOT:
613
614 if (x >= 0) { return "positive"; } // redundant { }
615 else { return "negative"; } // redundant { }
616
617 if (x >= 0) return "positive"; // single-line style
618 else // multi-line style
619 {
620 error = true;
621 return "negative";
622 }
623
624 // HEAVEN FORBID (aka. K&R style)
625 if (x >= 0) {
626 return "positive";
627 } else {
628 return "negative";
629 }
630 ----
631 ==== Function arguments
632
633 * one blank after every comma and between tokens:
634
635 ----
636 // DO:
637
638 int
639 main(int argc, char * argv[])
640 {
641 ...
642 }
643
644 // DO NOT ANY OF THE FOLLOWING...
645
646 int
647 main (int argc, char * argv[]) // extra space before arguments
648 {
649 ...
650 }
651
652 int
653 main( int argc, char * argv[] ) // extra spaces around arguments
654 {
655 ...
656 }
657
658 int
659 main(int argc, char *argv[]) // no space after *
660 {
661 ...
662 }
663
664 int
665 main(int argc, char* argv[]) // no space before *
666 {
667 ...
668 }
669 ----
670
671 === Naming Conventions
672
673 ==== Cpp Class Names
674
675 Class names should be in *CamelCase*. That is:
676
677 * No '_' between multiple words like in *CamelCase*,
678 * First letter of each word shall be uppercase, the rest lowercase,
679 * Abbreviations shall be all uppercase (in that case _ is allowed if it
680 improves readability or groups classes). E.g. Quad_XML.
681
682 ==== Cpp File Names
683
684 * class name and file names shall be the same (except for the .cc and .hh
685 extensions).
686 * file names: always use .cc (not .cxx or .cpp) and .hh (not .hxx or hpp).
687 * Pure C (as opposed to Cpp) files should use .c and .h as usual.
688
689 === Some Coding Conventions
690
691 * Use *(const) char ** for ASCII characters (i.e. 0x00...0x7F)
692 and *(const) UTF ** for UTF8 encoded strings. Keep in mind that
693 Cpp literals with APL characters (e.g. "A∆B") are automatically
694 UTF8 encoded by the compiler even though their type is *const char **.
695 * Use *basic_string<typename>* for simple C types (char, int, char \*, ...) and
696 *vector<typename>* for structs and classes, in particular for those with
697 constructors.
698 * Use *const* where possible.
699
700 These conventions have developed over time. Some old code does not follow them,
701 but new or updated code should.
702
703
704 ==== Class declarations (.hh files)
705
706 To the extent possible:
707
708 * declare public members (= the external interface) before protected
709 members (= the class implementation),
710 * declare members before static members,
711 * declare member functions before data members,
712 * keep the following declaration order:
713 ** constructors,
714 ** destructor,
715 ** inline functions,
716 ** non-inline functions
717 * always use *protected:* rather than *private:* for the members of a class.
718 GNU APL uses the convention that *private:* members are used to prevent the
719 accidental function calls that are sometimes generated by the Cpp compiler
720 (implicit conversion). In GNU APL, such members are declared, but not
721 defined (so that the linker will complain if the compiler should generate
722 them).
723
724 Indentation:
725
726 * indent all members with 2 spaces,
727 * indent inline function bodies by 3 more spaces
728 * do this recursively (nested classes)
729
730 And finally:
731
732 have a look at the existing *.cc* and *.hh* files. Even though this will
733 cause some extra work on your part, it simplifies the reading of your code
734 for many others. A project with different styles in different files looks
735 rather unprofessional, so please respect the style rules above even if you
736 do not like them.
737
738 == Debugging
739
740 GNU APL has a number of built-in means to locate faults. In a code base of
741 around 120,000 LOC, locating the fault in the source file takes most of the
742 time required to fix it. Many of the GNU APL debugging facilities have
743 performance impacts; they need to be enabled. The make target *develop*, i.e.
744
745 ----
746 make develop
747 ----
748
749 will enable a useful set of debugging facilities. *make develop* re-runs
750 *./configure*, therefore a normal build must have been performed beforehand
751 (otherwise the top-level Makefile would be missing).
752
753 === Assertions
754
755 GNU APL has more 600 Assertions spread throughout the source code. The
756 assertions check internal assumptions that the designer has made. If such
757 an assumption turns out to be false then a stack dump is produced which
758 tells which assumption (and where) was wrong.
759
760 Even though every single assertion has a negligible performance impact, the
761 accumulation of all assertions might become noticeable. It is therefore
762 possible to enable or disable some or all of them. This is done via the
763 ./configure argument ASSERT_LEVEL (see also *README-2-configure*):
764
765 ----
766 .configure ASSERT_LEVEL_WANTED=0 (the default, best performance)
767 .configure ASSERT_LEVEL_WANTED=1 disable trivial assertions, enable others
768 .configure ASSERT_LEVEL_WANTED=2 enable all assertions (worst performance)
769 ----
770
771 The *make develop* target sets, among other things, *ASSERT_LEVEL_WANTED=2*.
772
773
774 === Logging Facilities
775
776 Failed assertions primarily reveal major programming mistakes, such as
777 changing the code in one place and not considering the impact in other places.
778 In many cases the source code is faulty even though no assertion fails.
779 To isolate a fault one can enable one or more of almost 50 logging facilities
780 from the APL command line. Each logging facility addresses a functional area
781 of interest in the source code. When the code comes across such an area then a
782 printout is produced which provides additional information for the
783 troubleshooter. As of this writing, the following logging facilities exist:
784
785 ----
786 ]log
787 1: (OFF) AV details
788 2: (OFF) new and delete calls
789 3: (OFF) input from user or testcase file
790 4: (OFF) parser: parsing
791 5: (OFF) ... function find_closing()
792 6: (OFF) ... tokenization
793 7: (OFF) ... function collect_constants()
794 8: (OFF) ... create value()
795 9: (OFF) defined function: fix()
796 10: (OFF) ... set_line()
797 11: (OFF) ... load()
798 12: (OFF) ... execute()
799 13: (OFF) ... enter/leave
800 14: (OFF) State indicator: enter/leave
801 15: (OFF) ... push/pop
802 16: (OFF) Symbol: lookup
803 17: (OFF) ... push/pop and )ERASE
804 18: (OFF) ... resolve
805 19: (OFF) Value: glue()
806 20: (OFF) ... erase_stale()
807 21: (OFF) APL primitive function format
808 22: (OFF) character conversions
809 23: (OFF) APL system function Quad-FX
810 24: (OFF) commands )LOAD, )SAVE, )IN, and )OUT
811 25: (OFF) more verbose errors
812 26: (OFF) details of error throwing
813 27: (OFF) nabla editor
814 28: (OFF) execute(): state changes
815 29: (OFF) PrintBuffer: align() function
816 30: (OFF) Output: cork() functions
817 31: (OFF) Details of test execution
818 32: (OFF) Prefix parser
819 33: (OFF) ... location information
820 34: (OFF) FunOper1 and FunOper2 functions
821 35: (OFF) Shared Variable operations
822 36: (OFF) command line arguments (argc/argv)
823 37: (OFF) interpreter start-up messages
824 38: (OFF) optimization messages
825 39: (OFF) )LOAD and )SAVE details
826 40: (OFF) Svar_DB signals
827 41: (OFF) Parallel (multi-core) execution
828 42: (OFF) EOC handler functionality
829 43: (OFF) ⎕DLX details
830 44: (OFF) command ]DOXY
831 45: (OFF) details of Value allocation
832 46: (OFF) ⎕TF details
833 47: (OFF) ⎕PLOT details
834 ----
835
836 Like assertions, debugging facilities may have a performance impact. There are
837 almost 400 places in the source code where a decision is made about if and what
838 debug output shall be produced. For this reason, the logging facilities can
839 either be enabled/disabled at runtime from the APL command line (called
840 *dynamic logging*) or else at compile time (called *static logging*). *dynamic
841 logging* is the method of choice for trouble shooting and is therefore chosen
842 by *make develop*. In contrast *static logging* is the default and the
843 logging facilities that shall be enabled can be set in file *src/Logging.def*
844 (first argument of macro *log_def()*) before compiling the interpreter.
845
846 The logging Facility 37, _interpreter start-up messages_ is somewhat special.
847 Logging messages produced in the start-up of the interpreter occur before
848 the user has a chance to enter a *]LOG 37* command that enables them. For that
849 reason, the logging of start-up messages can be enabled from the command
850 line (option *-l 37*). None of the other logging facility can be enabled
851 from the command line. In the supposedly rare cases where other facilities
852 are needed before the interpreter has fully initialized itself, static
853 logging can be used instead.
854
855
856 === The )CHECK Command
857
858 GNU APL has adopted the )CHECK command from IBM APL2. The check command
859 performs an internal check of all data structures inside the interpreter.
860 The primary purpose is to find memory leaks:
861
862 ----
863 )CHECK
864 OK - no stale functions
865 OK - no stale values
866 OK - no stale indices
867 OK - no duplicate parents
868 ----
869
870 A value or function is *stale* if the current workspace cannot reach it
871 anymore. The interpreter does a sort of double-entry accounting of APL values
872 and defined functions, and the )CHECK triggers a consistency check of that
873 accounting. The runtime overhead is low therefore the double-entry accounting
874 cannot be disabled.
875
876 === Value Tracing
877
878 While every logging facility focuses on a particular functional area of
879 interest, value tracing focuses on the life-cycle of individual APL values.
880 If )CHECK finds a stale value (stale functions are rather rare) then the
881 next question is where the value was lost. An APL value sees a lot of places
882 in the source code and the value tracing keeps track of the major steps
883 in the lifetime of a value (creation, copying, destruction, etc). Value tracing
884 is disabled by default (Performance!) but enabled by *make develop*.
885
886
887 === Debug macros
888
889 If all debug means above fail, then the last resort is to either start a
890 debugger (like *gdb*) or to enter checkpoints in the source code and print the
891 information needed to isolate the fault. For this purpose (the author is using
892 debuggers only for analyzing core dump files) there are some macros that
893 simplify such printouts.
894
895 ==== The LOC macro
896
897 The macro *LOC* expands to the current source file name and line number. Many
898 Cpp functions use it for non-debug purposes to see from where they were
899 called. The expanded LOC macro is a string literal, therefore the overhead is
900 minimal:
901
902 ----
903 #define STR(x) #x
904 #define Loc(f, l) f ":" STR(l)
905 #define LOC Loc(__FILE__, __LINE__)
906 ----
907
908 ==== The Q() macro
909
910 The macro *Q(x)* prints the value of *x*, source file name and line number
911 at which the value of *x* was printed:
912
913 ----
914 /// print x and its source code location
915 #define Q(x) get_CERR() << std::left << setw(20) << #x ":" \
916 << " '" << x << "' at " LOC << endl;
917 ----
918
919 The other debug means are somewhat coarse-grained. Dividing around *120,000
920 LOC* (lines of source code) by 400 places where logging facilities may
921 provide some output yields an average of 300 lines of code between logging
922 outputs. The typical troubleshooting process is this:
923
924 . find an easy way to reproduce the fault (testcase file, APL script, etc.),
925 then
926 . use logging facilities and/or value tracing to narrow the possible locations
927 of the fault (to typically one source code file), and finally
928 . insert *Q()* macros if needed to further isolate the fault.
929
930 The build system checks that all *Q()* macros were removed before checking the
931 code into the Savannah SVN repository. This is because forgetting that used to
932 be a frequent mistake.
933
934 ==== The Q1() macro
935
936 The *Q1()* macro does the same as *Q()* but shall remain in the code. It is
937 (rarely) used in places of which the designer believes that they cannot be
938 reached but has no proof that this is the case. Similar to assertions, but
939 only printing values of interest without terminating with a stack dump.
940
941 == Top-Down Description of the GNU APL Source Code
942
943 The APL interpreter is, like almost any other interpreter, a program that
944 reads one line of input after another. For every line read (the *input*)
945 it produces zero or more lines of *output*. In doing so, the interpreter may
946 or may not change its internal state.
947
948 In the context of APL the internal state of the interpreter is called (the
949 current) *workspace*; it can be **)SAVE**d into a file and later **)LOAD**ed
950 or **)COPY**ed into another interpreter instance.
951
952 The top-level loop of the interpreter described above is commonly referred
953 to as *REPL*, an abbreviation for **R**ead-**E**valuate-**P**rint-**L**oop:
954
955 ----
956 ┌──────┐
957 │ INIT │
958 └──────┘
959 ↓
960 ○← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ← ←
961 ↓ ↑
962 ┌──────┐ ┌──────────┐ ┌───────┐ ┌──────┐
963 │ Read │→ → →│ Evaluate │→ → →│ Print │→ → →│ Loop │
964 └──────┘ └──────────┘ └───────┘ └──────┘
965 ↓
966 )OFF
967 ↓
968 ┌──────┐
969 │ EXIT │
970 └──────┘
971 ----
972
973 The *REPL* of GNU APL is located at the end of function *main()* in source
974 file *main.cc*:
975
976 ----
977 for (const bool exit_on_error = IO_Files::exit_on_error();;)
978 {
979 const Token tok = Workspace::immediate_execution(exit_on_error);
980 if (tok.get_tag() == TOK_OFF) Command::cmd_OFF(0);
981 }
982 ----
983
984 The **R**ead, **E**valuate, and **P**rint parts of the *REPL* are performed
985 in function *immediate_execution()* which returns *TOK_OFF* if the APL
986 command *)OFF* was processed and something else otherwise.
987
988 === The Workspace::immediate_execution() Function
989
990 Function *Workspace::immediate_execution()* processes one line of input,
991 in source file *Workspace.cc*. It simply calls *Command::process_line()*.
992 More importantly, it **catch**es Cpp errors that may be thrown and processes
993 the errors:
994
995 ----
996 Token
997 Workspace::immediate_execution(bool exit_on_error)
998 {
999 for (;;)
1000 {
1001 try
1002 {
1003 Command::process_line();
1004 }
1005 catch (Error & err)
1006 ...
1007 ----
1008
1009 NOTE: Some lines, notably the ∇-editor and, in certain cases, the *)COPY* and
1010 *)LOAD* commands have their own sub-REPL. They loop themselves until a
1011 particular condition (the closing ∇ for the ∇-editor or end-of-file for the
1012 *)COPY* and *)LOAD* commands) has occurred. Therefore:
1013
1014 * process_line() is *atomic* (in the sense that it processes only one input
1015 line), but
1016 * the functions called by process_line() will be called repeatedly until an
1017 error is returned. The close of the ∇-editor is also considered an error
1018 condition here).
1019
1020 This fact is sometimes missed by programmers using *libapl*. *libapl* is a
1021 library that contains most of the normal interpreter code, *but not* the REPL
1022 loops of the interpreter. The purpose of *libapl* is to provide a C-API to
1023 other front-ends like *Erlang*, *Python*, or *Cpp* programs. For example,
1024 if a front end opens a defined function with a line that starts with ∇, then
1025 the front-end is responsible for providing the subsequent (defined function-)
1026 lines including the final ∇ that closes the function definition. The same
1027 holds for *)LOAD* and *)COPY* of *.apl* scripts, but not for *)LOAD* and
1028 *)COPY* of workspace snapshots (*.xml* files). To summarize:
1029
1030 [width="30%", options="header"]
1031 |====
1032 | Operation | Atomicity
1033 | ∇-editor | non-atomic
1034 | )SAVE | atomic
1035 | )LOAD .apl | non-atomic
1036 | )LOAD .xml | atomic
1037 | )COPY .apl | non-atomic
1038 | )COPY .xml | atomic
1039 | multi-line string | non-atomic
1040 |====
1041
1042 === The Command::process_line() Functions
1043
1044 Function *Command::process_line()* reads the next input line
1045 (*InputMux::get_line()*), removes leading white-space (blanks) and then
1046 decides how to proceed. The first non-blank character determines the
1047 subsequent processing as follows:
1048
1049 . empty line: return
1050 . ⍝: APL comment: return
1051 . #: script comment: return
1052 . ): (regular) APL command: *Command::process_line(line...)*
1053 . ]: (debug) APL command: *Command::process_line(line...)*
1054 . """|«««: start of a multi-line string: loop until end of string
1055 . otherwise: APL expression: *Command::process_line(line)*
1056
1057 Function *Command::process_line()* is overloaded; the variant without arguments
1058 fetches a line while the variant with a line argument processes the fetched
1059 line. The decision about the further processing is done in the latter, i.e. in
1060 *process_line(line...I)*:
1061
1062 ----
1063 void
1064 Command::process_line(UCS_string & line, ostream * out)
1065 {
1066 line.remove_leading_white spaces();
1067 if (line.size() == 0) return; // empty input line
1068
1069 switch(line[0])
1070 {
1071 case UNI_R_PARENT: // regular command, e.g. )SI
1072 if (out == 0) out = &COUT;
1073 do_APL_command(*out, line);
1074 if (line.size()) break;
1075 return;
1076
1077 case UNI_R_BRACK: // debug command, e.g. ]LOG
1078 if (out == 0) out = &CERR;
1079 do_APL_command(*out, line);
1080 if (line.size()) break;
1081 return;
1082
1083 case UNI_NABLA: // e.g. ∇FUN
1084 Nabla::edit_function(line);
1085 return;
1086
1087 case UNI_NUMBER_SIGN: // e.g. # comment
1088 case UNI_COMMENT: // e.g. ⍝ comment
1089 return;
1090
1091 default: break;
1092 }
1093
1094 ++APL_expression_count;
1095 do_APL_expression(line);
1096 }
1097 ----
1098
1099 By default the output of process_line() is printed to the console, but a
1100 non-zero *out* redirects the output to *out*. This is used by functions that
1101 need to capture the output of a command, e.g. ⍎")COMMAND" (a GNU APL extension,
1102 normally APL commands cannot be used by ⍎).
1103
1104 As explained, further processing depends on the first character of the line:
1105
1106 ----
1107 ┌──────────────┐
1108 │ process_line │
1109 └──────┬───────┘
1110 │
1111 ┌───────────────┼──────────────────┐
1112 │ │ │
1113 ∇ ),] other
1114 │ │ │
1115 ┌────┴─────┐ ┌────┴─────┐ ┌───────┴────────┐
1116 │ ∇-editor │ │ )COMMAND │ │ APL expression │
1117 └──────────┘ │ ]COMMAND │ └────────────────┘
1118 └──────────┘
1119 ----
1120
1121 Strictly speaking the ∇-editor and APL commands are not part of the APL
1122 language (they have their own syntax). At this point it should suffice that
1123 the implementation of the ∇-editor is found in source file *Nabla*.cc
1124 (nabla is the name for ∇ in the Greek alphabet) while the implementations
1125 of most commands are found in *Command.cc*. Most of the functions in
1126 *Command.cc* are concerned with the decoding of command arguments and
1127 are not further discussed here. Most commands have a simple implementation
1128 which is also contained in *Command.cc*. The others have their own source
1129 file:
1130
1131 [width="40%", options="header"]
1132 |====
1133 | Command | Implementation
1134 | )CLEAR | Workspace.cc
1135 | )MORE | Workspace.cc
1136 | )SAVE .xml | Archive.cc
1137 | )COPY .xml | Archive.cc
1138 | )LOAD .xml | Archive.cc
1139 |====
1140
1141 Consult source file *Command.def* to find the implementation of a particular
1142 command. Most commands support TAB-completion: the user hits TAB and the
1143 possible completions are are displayed. Implemented in *TabExpansion.cc*.
1144
1145 === APL Expressions
1146
1147 The most interesting case occurs if the user enters an APL expression, from
1148 simple ones like *+/⍳10* or complex ones like calling a defined function. The
1149 behavior in this case is specified in the ISO APL standard and GNU APL
1150 follows this standard, at least for the most part. The processing of the input
1151 line is _essentially_ the same for the lines of defined APL functions and for
1152 lines entered in immediate execution. The minor differences, e.g. APL labels
1153 are not allowed in immediate execution, statement separators are not allowed
1154 in ⍎-strings, etc. are handled via a *ParseMode* declared and defined in
1155 *APL_types.hh*:
1156
1157 ----
1158 /// What is being parsed (defined function, immediate execution statements,
1159 /// or ⍎expr)
1160 enum ParseMode
1161 {
1162 PM_FUNCTION = 0, ///< defined function
1163 PM_STATEMENT_LIST = 1, ///< immediate execution
1164 PM_EXECUTE = 2, ///< execute (⍎)
1165 };
1166 ----
1167
1168 The *ParseMode* defines the origin of a particular line; the options are:
1169
1170 * The line was entered in immediate execution (as described above), or
1171 * The line is a line of a defined function (see later), or
1172 * The line was an APL string (⍎, ⎕EA, ⎕ES ...).
1173
1174 The next steps in the processing of a line are tokenization and pre-parsing:
1175
1176 ----
1177 ┌───────────────┐
1178 │ Tokenization │
1179 └───────┬───────┘
1180 ┌───────┴──────┐
1181 │ Pre-Parsing │
1182 ├──────────────┤
1183 │ Optimization │
1184 └──────────────┘
1185 ----
1186
1187 === Tokenization
1188
1189 Tokenization splits the (APL-) characters of a line into small fixed-sized
1190 units called *Token*s. Tokens are the machine-readable unit equivalents of the
1191 human readable input characters. For example, a possibly lengthy string like
1192 "3.142.0" is converted into a Token holding a C _double_. The whole purpose of
1193 tokenization is to convert the APL input into an internal representation that
1194 can be interpreted significantly faster than the APL characters enters by the
1195 APL programmer. For example:
1196
1197 ----
1198 A←1 2 3 ◊ B←'abc' ⍝ APL input string
1199 ----
1200 is tokenized into:
1201
1202 ----
1203 ┌───┐ ┌───┐ ┌───────┐ ┌───┐ ┌───┐ ┌───┐ ┌─────┐ ┌─────┐
1204 │ A │ │ ← │ │ 1 2 3 │ │ ◊ │ │ B │ │ ← │ │ abc │ │ EOL │
1205 └───┘ └───┘ └───────┘ └───┘ └───┘ └───┘ └─────┘ └─────┘
1206 ----
1207
1208 The function that performs the tokenization is:
1209
1210 ----
1211 ErrorCode tokenize(const UCS_string & input, Token_string & tos) const;
1212 ----
1213
1214 which is a member of *class Tokenizer*, see *Tokenizer.hh*. The result is
1215 a Token_string:
1216
1217 ----
1218 // A sequence of Tokens
1219 class Token_string : public std::vector<Token>
1220 {
1221 ...
1222 };
1223 ----
1224
1225 see file *Token.hh*.
1226
1227 === Pre-parsing
1228
1229 Pre-parsing is primarily an optimization step that performs a number of
1230 sub-steps, such as:
1231
1232 * splitting multiple statements (separated by ◊ Token) into individual
1233 statements (at ◊),
1234 * grouping multiple scalars into single APL values,
1235 * reversing the order of individual statements, and
1236 * performing some optimizations
1237
1238 In the example above, the token string
1239
1240 ----
1241 ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌─────┐ ┌─────┐
1242 │ A │ │ ← │ │ 1 │ │ 2 │ │ 3 │ │ ◊ │ │ B │ │ ← │ │ abc │ │ EOL │
1243 └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └─────┘ └─────┘
1244 ----
1245
1246 is first split into 2 statements:
1247
1248 ----
1249 ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
1250 │ A │ │ ← │ │ 1 │ │ 2 │ │ 3 │
1251 └───┘ └───┘ └───┘ └───┘ └───┘
1252 ┌───┐ ┌───┐ ┌─────┐
1253 │ B │ │ ← │ │ abc │
1254 └───┘ └───┘ └─────┘
1255 ----
1256
1257 The scalars 1, 2, and 3 are then combined into a single APL value (the APL
1258 value 'abc' is already a single value after tokenization):
1259
1260 ----
1261 ┌───┐ ┌───┐ ┌───────┐
1262 │ A │ │ ← │ │ 1 2 3 │
1263 └───┘ └───┘ └───────┘
1264 ┌───┐ ┌───┐ ┌─────┐
1265 │ B │ │ ← │ │ abc │
1266 └───┘ └───┘ └─────┘
1267 ----
1268
1269 Next, the individual statements are reversed:
1270
1271 ----
1272 ┌───────┐ ┌───┐ ┌───┐
1273 │ 1 2 3 │ │ ← │ │ A │
1274 └───────┘ └───┘ └───┘
1275 ┌─────┐ ┌───┐ ┌───┐
1276 │ abc │ │ ← │ │ B │
1277 └─────┘ └───┘ └───┘
1278 ----
1279
1280 and finally combined again:
1281
1282 ----
1283 ┌───────┐ ┌───┐ ┌───┐ ┌───┐ ┌─────┐ ┌───┐ ┌───┐ ┌────┐
1284 │ 1 2 3 │ │ ← │ │ A │ │ ◊ │ │ abc │ │ ← │ │ B │ │ EOL│
1285 └───────┘ └───┘ └───┘ └───┘ └─────┘ └───┘ └───┘ └────┘
1286 ----
1287
1288 The reason for reversing the tokens of every statement is somewhat subtle: APL
1289 statements are executed from left to right, but the tokens inside a statement
1290 are processed from right to left. Without the reversal the tokens would need to
1291 be processed like this:
1292
1293 ----
1294 → → → → → → → → → → → → → → → → → → → → → → → →
1295 ↓ ↑ ↓
1296 ┌───┐ ┌───┐ ┌───────┐ ┌───┐ ┌───┐ ┌───┐ ┌─────┐ ┌─────┐
1297 │ A │←│ ← │←│ 1 2 3 │ │ ◊ │←│ B │←│ ← │←│ abc │ │ EOL │
1298 └───┘ └───┘ └───────┘ └───┘ └───┘ └───┘ └─────┘ └─────┘
1299 ↓ ↑
1300 → → → → → → → → → → → → → → → → → → → →
1301
1302 ----
1303
1304 By reversing every statement the same processing order now becomes:
1305
1306 ----
1307 ┌───────┐ ┌───┐ ┌───┐ ┌───┐ ┌─────┐ ┌───┐ ┌───┐ ┌─────┐
1308 │ 1 2 3 │→│ ← │→│ A │→│ ◊ │→│ abc │→│ ← │→│ B │→│ EOL │
1309 └───────┘ └───┘ └───┘ └───┘ └─────┘ └───┘ └───┘ └─────┘
1310 ----
1311
1312 *DEFINITION*: in source code comments, we refer to the initial token order
1313 (statement tokens from left to right, statements from left to right,
1314 and lines from top to bottom) as the *APL order* and to the order after
1315 reversing the tokens of every statement (statement tokens from right to left,
1316 statements from left to right, and lines from top to bottom) as the
1317 *reversed order*. The reversal is performed in *Executable::parse_body_line().
1318 In other words, function *Tokenizer::tokenize()* produces a *Token_string tos*
1319 in APL order, which is later reversed into the final function body
1320 *Token_string Executable::body*.
1321
1322 The reversed order can be processed much faster since the order is now linear
1323 and no more back and forth jumps are needed when the token string is
1324 interpreted.
1325
1326 Another trick in the pre-parsing phase is to store the distance between
1327 opening and closing parentheses and square brackets (curly brackets are removed
1328 entirely in this phase) in the token itself. Sometimes the prefix-parser
1329 (*Prefix.cc*) that finally performs the interpretation has to jump
1330 over a pair of parentheses or brackets to find the token to their left.
1331 Instead of scanning the token string at runtime until a matching parenthesis
1332 or bracket is found, one can compute its location directly (i.e. in time
1333 O(1) rather than O(∆) for distance ∆ between the matching parentheses
1334 or brackets):
1335
1336 ----
1337 ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
1338 │ (,∆ │ ... │ ),∆ │ or │ [,∆ │ ... │ ],∆ │
1339 └─────┘ └─────┘ └─────┘ └─────┘
1340 │← ← ← ∆ → → →│ │← ← ← ∆ → → →│
1341 ----
1342 The Pre-parser function returns an error code and fills its argument *tos*
1343 as a side effect:
1344
1345 ----
1346 Parser.hh:
1347
1348 /// Parse token string \b input into token string \b tos.
1349 ErrorCode parse(const Token_string & input, Token_string & tos) const;
1350 ----
1351 The entire conversion (i.e. tokenization and pre-parsing
1352 happens in function *Executable::parse_body_line()*; the result is stored in
1353 member *body* of class Executable:
1354
1355 ----
1356 Executable.hh:
1357
1358 /// The tokens to be executed. They are organized line by line and
1359 /// statement by statement, but the tokens within a statement are
1360 /// reversed due to the right-to-left execution of APL.
1361 Token_string body;
1362 ----
1363 Every defined function, every line entered in immediate execution, and every
1364 statement from a ⍎ expression is converted into an object of base
1365 class *Executable*. That object contains some more information such as
1366 the original line(s) from which it was created, a reference counter to
1367 delete it if no longer used, etc.
1368
1369 From base class Executable three different classes for the different
1370 ParseModes are derived:
1371
1372 ----
1373 class ExecuteList : public Executable { ...} // in Executable.hh
1374 class StatementList : public Executable { ... } // in Executable.hh
1375 class UserFunction : public Function, public Executable // in UserFunction.hh
1376 ----
1377 This is because the minor differences between the ParseModes not only affect
1378 the parsing of the input line but also some runtime aspects. The base class
1379 Executable contains the common functionality while the derived classes
1380 contain the specific functionalities related to the different ParseModes.
1381
1382 Some debug printouts display the ParseMode, like this:
1383
1384 * ∇ for defined functions,
1385 * ◊ for a list of statements (i.e. immediate execution), and
1386 * ⍎ for executed APL strings (⍎, ⎕EA, ⎕EB, ⎕ES).
1387
1388 The difference between *◊* and *⍎* is mostly resolved during pre-parsing,
1389 therefore classes *StatementList* and *ExecuteList* are almost the same as
1390 class *Executable*. Both pertain to a single line of APL code and their
1391 implementation can be found in *Executable.cc*.
1392
1393 In contrast, defined functions are far more complex (multiple lines, labels,
1394 parameter passing) and have their own implementation file *UserFunction.cc*.
1395
1396 === Naming of APL objects
1397
1398 To conclude the discussion of pre-parsing we should mention the role of names.
1399 Ignoring comments and white-space (which are discarded rather early), the
1400 lines of every APL program consists of 3 types of objects:
1401
1402 . literals (constants) like 1 2 3 or 'abc', and
1403 . names of built-in primitives like + and -, system functions like ⎕UCS, and
1404 system variables like ⎕IO
1405 . (user-defined) names of variables and defined functions, in the following
1406 called *symbols*.
1407
1408 These objects are processed by the pre-parser according to the following
1409 rules:
1410
1411 . literals are converted to APL values,
1412 . every primitive, system function, or system variable has an integer ID which
1413 uniquely identifies it, and
1414 . every user defined name is entered into a symbol table, which is a hash
1415 table that contains all user defined names. The conversion from a name
1416 (i.e. string) to a user defined object happens during the pre-parsing (and
1417 therefore has no runtime overhead).
1418
1419 The IDs of all primitives are *#defined* in *Id.def*. The Ids are sorted by
1420 the first character in their name (the character after ⎕ for system functions
1421 and variables) or e.g. "P" for Plus, "M" for Minus etc. These IDs are not only
1422 used in the body tokens of executables but also in )SAVEd .xml snapshots. It
1423 is therefore essential that new IDs are added at the end of the ID group that
1424 starts with the same character, and that obsolete IDs are kept (or at least
1425 their IDs are never reused). The first character (upper 8 bits of the ID are
1426 chosen in a way that simplifies debugging at little or no cost.
1427
1428 All user defined symbols have the ID 0x0000 and their token contains a
1429 unique *Symbol ** pointer. The symbol table (class *SymbolTable* in file
1430 *SymbolTable.hh*) is only used by the pre-parser (to ensure that all symbols
1431 have the same *Symbol **) and by some APL commands like *)FNS*, *)VARS*,
1432 *)OPS*, etc.
1433
1434 The Id.def file classifies the around 200 IDs via 5 macros that indicate their
1435 purpose or usage:
1436
1437 * macro *pp(...)*: **p**retty **p**rint. For constructing the name (usually
1438 "---") of a token that has no permanent role, e.g. pass C function arguments.
1439 E.g. NO_VALUE, VARIABLE, ...
1440 * macro *qf(...)*: **q**uad **f**unction. Quad function,
1441 e.g. ⎕DL, ⎕FX, ...
1442 * macro *qv(...)*: **q**uad **v**ariable. Quad variable,
1443 e.g. ⎕CT, ⎕IO, ...
1444 * macro *sf(...)*: **s**ystem **f**unction. An APL primitive,
1445 e.g. ⍴, ⌽, ...
1446 ...
1447 * macro *st(...)*: **s**ystem **t**oken. An ID for other token,
1448 e.g. ⍺, →, ...
1449
1450
1451 === Token Structure
1452
1453 With the prerequisites above we can define the structure of a *Token*:
1454
1455 ----
1456 Token.hh:
1457
1458 class Token
1459 {
1460 ...
1461
1462 /// the (optional) value of the token.
1463 union sval
1464 {
1465 Unicode char_val; ///< the Unicode for TV_CHAR
1466 APL_Integer int_vals[2]; ///< the integer for TV_INT
1467 APL_Float_Base float_vals[2]; ///< the doubles for TV_FLT and TV_CPX
1468 Symbol * sym_ptr; ///< the symbol for TV_SYM
1469 Function_Line fun_line; ///< the function line for TV_LIN
1470 IndexExpr * index_val; ///< the index for TV_INDEX
1471 Function_P function; ///< the function for TV_FUN
1472 Value_P_Base apl_val; ///< the APL value for TV_VAL
1473
1474 /// a shortcut for accessing apl_val
1475 Value_P & _apl_val() const
1476 { return reinterpret_cast<Value_P &>
1477 (const_cast<Value_P_Base &>(apl_val)); }
1478 };
1479
1480 ...
1481
1482 protected:
1483
1484 /// The tag indicating the type of \b this token
1485 TokenTag tag;
1486
1487 /// The value of \b this token
1488 sval value;
1489
1490 ...
1491 }
1492 ----
1493
1494 In short this means that:
1495
1496 * a token is a tagged union (named *sval*), and
1497 * the tag (an *enum TokenTag*) determines which member (if any) of *union sval*
1498 a particular token holds.
1499
1500 The APL interpreter can be understood as virtual machine whose opcodes are
1501 Tokens. In this context the attribute *virtual* of _virtual machine_ must not
1502 be confused with the attribute *virtual* of _virtual Cpp functions_ or
1503 _classes_. The tokenization and pre-parsing is then the "compilation" of APL
1504 source code into machine code of this virtual APL machine.
1505 The rest of *Token.hh* defines quite a number of constructors and access
1506 functions of class Token, most of them _inline_ because the manipulation
1507 of Token is usually simple but performed frequently.
1508
1509 The *TokenTag* is a 32-bit (4 byte) number which has 3 sub-fields:
1510
1511 ----
1512 ------16 bit------ ---8 bit--- ---8 bit---
1513 ┌────────┬─────────┬────────────┬─────────────┐
1514 Token Tag: │ ID │ Value-type │ Token-class │
1515 └────────┴─────────┴────────────┴─────────────┘
1516 ----
1517
1518 ==== The ID of a Token
1519
1520 The 16 bit *ID* is the integer ID of system functions and variables explained
1521 above. The ID (i.e. its access function Token::get_Id()) is not used during
1522 the normal interpretation of APL code but only in error messages and for
1523 loading and saving of workspaces.
1524
1525 ==== The Value-Type of a token
1526
1527 The value type simply defines which of the members of *union sval* the token
1528 holds. The value type is only used when a Token is copied or moved around
1529 (most likely from the body of a defined function into the prefix parser as
1530 will be explained below). The knowledge of the type is needed because some
1531 the *union sval* members have constructors.
1532
1533 The value types are defined in *TokenEnums.hh*:
1534
1535 ----
1536 TokenEnums.hh:
1537
1538 /// The value type of a token
1539
1540 enum TokenValueType
1541 {
1542 // token value types. The token value type defines the type of the
1543 // token in the union 'value'.
1544 // Type union member
1545 TV_MASK = 0xFF00,
1546 TV_NONE = 0x0000, // value not used
1547 TV_CHAR = 0x0100, // Unicode .char_val
1548 TV_INT = 0x0200, // uint64_t .int_val;
1549 TV_FLT = 0x0300, // APL_Float .flt_val;
1550 TV_CPX = 0x0400, // cdouble .complex_val;
1551 TV_SYM = 0x0500, // Symbol * .sym_ptr;
1552 TV_LIN = 0x0600, // Function_Line .fun_line;
1553 TV_VAL = 0x0700, // Value_P .apl_val;
1554 TV_INDEX = 0x0800, // IndexExpr * .index_val;
1555 TV_FUN = 0x0900, // Function_P .function;
1556 };
1557 ----
1558
1559 The typical (inline) function that copies a Token is:
1560
1561 ----
1562 Token.hh:
1563
1564 Token::copy_N(const Token & src)
1565 {
1566 tag = src.tag;
1567 switch(src.get_ValueType())
1568 {
1569 case TV_NONE: value.int_vals[0] = 0;
1570 value.int_vals[1] = 0; break;
1571 case TV_CHAR: value.char_val = src.value.char_val; break;
1572 case TV_INT: value.int_vals[0] = src.value.int_vals[0];
1573 value.int_vals[1] = src.value.int_vals[1]; break;
1574 case TV_FLT: value.float_vals[0] = src.value.float_vals[0]; break;
1575 case TV_CPX: value.float_vals[0] = src.value.float_vals[0];
1576 value.float_vals[1] = src.value.float_vals[1]; break;
1577 case TV_SYM: value.sym_ptr = src.value.sym_ptr; break;
1578 case TV_LIN: value.fun_line = src.value.fun_line; break;
1579 case TV_VAL: value._apl_val() = src.value._apl_val(); break;
1580 case TV_INDEX: value.index_val = src.value.index_val; break;
1581 case TV_FUN: value.function = src.value.function; break;
1582 default: FIXME;
1583 }
1584 }
1585 ----
1586 In *copy_N()*, *src* is a token that is copied into token *this*, and *value*
1587 is the member (of *union sval*) that is being copied.
1588
1589 ==== The TokenClass-Type of a token
1590
1591 The most important part of a *TokenTag* is its class (not to be confused with
1592 Cpp classes). Like the token value types they are defined in *TokenEnums.hh*.
1593 There are two different kinds of token classes: **permanent token class**es and
1594 **temporary token class**es. The permanent classes are:
1595
1596 ----
1597 TokenEnums.hh:
1598
1599 enum TokenClass
1600 {
1601 // token classes.
1602 //
1603
1604 // permanent token classes. Only Token of these classes can appear in
1605 // the body of a defined function.
1606 //
1607 TC_ASSIGN = 0x01, ///< ←
1608 TC_R_ARROW = 0x02, ///< →N
1609 TC_L_BRACK = 0x03, ///< [ or ;
1610 TC_R_BRACK = 0x04, ///< ]
1611 TC_END = 0x05, ///< left end of statement
1612 TC_FUN0 = 0x06, ///< niladic function
1613 TC_FUN12 = 0x07, ///< ambivalent function
1614 TC_INDEX = 0x08, ///< [...]
1615 TC_OPER1 = 0x09, ///< monadic operator
1616 TC_OPER2 = 0x0A, ///< dyadic operator
1617 TC_L_PARENT = 0x0B, ///< (
1618 TC_R_PARENT = 0x0C, ///< )
1619 TC_RETURN = 0x0D, ///< return from defined function
1620 TC_SYMBOL = 0x0E, ///< user defined name
1621 TC_VALUE = 0x0F, ///< APL value
1622
1623 TC_MAX_PERM, ///< permanent token are < TC_MAX_PERM
1624 ...
1625 ----
1626
1627 In contrast, temporary tokens are never used in the body of an *Executable*.
1628 They are short-lived and vanish after some permanent token was created from
1629 them. For example, prefix parser creates a token of class *TC_PINDEX* (for
1630 partial index) when it sees the closing *]* of an APL index (remember:
1631 right-to-left) and creates a permanent token of class TC_INDEX when it sees
1632 the corresponding opening *[*. Likewise, a defined function without result
1633 returns a token of class TC_VOID which is passed from one prefix parser to
1634 another to indicate the result of a defined function.
1635
1636 In short, temporary token classes are only created and consumed inside the
1637 prefix parser. The temporary token classes are:
1638
1639 ----
1640 TokenEnums.hh:
1641 ...
1642 // temporary Token classes. Token of these classes only appear as
1643 // intermediate results during tokenization and prefix parsing
1644 //
1645 TC_PINDEX = 0x10, ///< partial index
1646 TC_VOID = 0x11,
1647 TC_MAX_PHRASE, ///< token in phrases are < TC_MAX_PHRASE
1648 TC_MAX_PHRASE_2 = TC_MAX_PHRASE*TC_MAX_PHRASE, // TC_MAX_PHRASE ^ 2
1649 TC_MAX_PHRASE_3 = TC_MAX_PHRASE*TC_MAX_PHRASE_2, // TC_MAX_PHRASE ^ 3
1650 TC_MAX_PHRASE_4 = TC_MAX_PHRASE*TC_MAX_PHRASE_3, // TC_MAX_PHRASE ^ 4
1651
1652 TC_OFF = 0x12,
1653 TC_SI_LEAVE = 0x13,
1654 TC_LINE = 0x14,
1655 TC_DIAMOND = 0x15, // ◊
1656 TC_NUMERIC = 0x16, // 0-9, ¯
1657 TC_SPACE = 0x17, // space, tab, CR (but not LF)
1658 TC_NEWLINE = 0x18, // LF
1659 TC_COLON = 0x19, // :
1660 TC_QUOTE = 0x1A, // ' or "
1661 TC_L_CURLY = 0x1B, // {
1662 TC_R_CURLY = 0x1C, // }
1663 ----
1664
1665 The phrase table (or phrase tree) described in
1666 <<_the_phrase_table, The Phrase Table,_the_phrase_table>>
1667 below maps particular sequences of token classes
1668 to reduce functions. To make the phrase table a little more readable,
1669 we define some shorter names (SN_xxx) for token classes that better reflect
1670 the relation between the APL point of view and the Cpp representation of
1671 it, and/or abbreviates them:
1672
1673 ----
1674 TokenEnums.hh:
1675 ...
1676 // shorter token class aliases for the phrase table
1677 //
1678 SN_A = TC_VALUE,
1679 SN_ASS = TC_ASSIGN,
1680 SN_B = TC_VALUE,
1681 SN_C = TC_INDEX,
1682 SN_D = TC_OPER2,
1683 SN_END = TC_END,
1684 SN_F = TC_FUN12,
1685 SN_G = TC_FUN12,
1686 SN_GOTO = TC_R_ARROW,
1687 SN_I = TC_PINDEX,
1688 SN_LBRA = TC_L_BRACK,
1689 SN_LPAR = TC_L_PARENT,
1690 SN_M = TC_OPER1,
1691 SN_N = TC_FUN0,
1692 SN_RETC = TC_RETURN,
1693 SN_RBRA = TC_R_BRACK,
1694 SN_RPAR = TC_R_PARENT,
1695 SN_V = TC_SYMBOL,
1696 SN_VOID = TC_VOID,
1697 SN_ = TC_INVALID
1698 ----
1699
1700 For example: the ISO APL standard defines a phrase table of 39 phrases. In
1701 particular phrase 7 is defined as:
1702
1703 _7 EVALUATE DYADIC FUNCTION (<A F B> R)_
1704
1705 In GNU APL code the ISO phrase *<A F B>* is represented as 3 short-names
1706 *SN_A, SN_F, SN_B,*. To further simplify matters, the *SN_* prefix is hidden
1707 by means of some macro magic, so that the same ISO phrase in the GNU APL
1708 phrase table (in *Prefix.def*) becomes:
1709
1710 ----
1711 Prefix.def :
1712
1713 PH( A F B , A_F_B_ , 0x03CEF , 33 , 0 , 3), // [EA]
1714
1715 ----
1716 Given that *SN_A* and *SN B* are both short names for *TC_VALUE*, and that
1717 *SN_F* the short name for *TC_FUN12*, after expanding macro PH() in the Cpp
1718 preprocessor this translated to something like:
1719
1720 _If a sequence of token classes TC_VALUE TC_FUN12 TC_VALUE is discovered, then
1721 call Cpp function reduce_A_F_B()._
1722
1723 == Evaluation of APL Expression
1724
1725 === The Phrase Table
1726
1727 The IBM APL Language Reference Manual describes the fundamental rule for the
1728 evaluation of APL expressions as follows:
1729
1730 _All functions execute according to their position within an expression.
1731 The rightmost function whose arguments are available is evaluated first._
1732
1733 In parser terms, one could just as well formulate this as:
1734
1735 * execution of an APL expression starts with an empty sequence of token
1736 classes,
1737 * the tokens in the sequence are then, from right to left, prepended to the
1738 sequence, and
1739 * whenever a prefix of the current sequence is found in the phrase table:
1740 ** the reduce function in the phrase table entry is called with the token of
1741 the prefix as arguments,
1742 ** the prefix in the sequence is replaced with the result of the reduce
1743 function.
1744
1745 Since GNU APL stores the token in reverse order as explained earlier, from
1746 right to left actually means left to right for the token string that is being
1747 interpreted. The rules above amount to what is commonly called a LALR(1)
1748 parser (short for **L**ook**A**head-**L**eft**R**ight-Parser with 1 lookahead
1749 token). In GNU APL terminology it is the *Prefix parser* in file *Prefix.cc*.
1750 The somewhat simplified algorithm of the GNU APL prefix parser is:
1751
1752 . Every Prefix parser starts execution at the beginning of some token string,
1753 say *body*, which is in most cases the body of a defined function.
1754 .. Its integer variable *PC* (actually of type *enum Function_PC*) is
1755 initialized to 0 (start of function), and
1756 .. the sequence of tokens read so far is cleared. Then:
1757 . The next token is read and PC is incremented.
1758 . If the token class is *TC_SYMBOL* (i.e. a name defined by the APL programmer)
1759 then the new token is replaced by the current value of the symbol, which is
1760 one of:
1761 .. *TC_VOID* - the symbol name was used (tokenized) but not assigned (e.g.
1762 the initial values of local variables of a defined function),
1763 .. *TC_VALUE* - an APL variable,
1764 .. *TC_FUN0* - a defined niladic function,
1765 .. *TC_FUN12* - a defined monadic or dyadic function,
1766 .. *TC_OPER1* - a defined monadic operator (i.e. 1 function argument), or
1767 .. *TC_OPER2* - a defined dyadic operator (i.e. 2 function argument).
1768 This name resolution step happens in function
1769 ** *Symbol::resolve_right()* for symbols right of *←* or in
1770 ** *Symbol::resolve_left()* for symbols left of *←*. The case *TC_VOID* happens
1771 when a name was tokenized, but no value or function was assigned to it.
1772 .. If the new token together with the sequence matches a phrase (as discussed
1773 above) then the phrase is reduced (called REDUCE in parser terminology).
1774 . Otherwise (no phrase matches) the new token is prepended to the sequence and
1775 the next token is read (called SHIFT in parser terminology). In this case
1776 execution continues with step 2. above.
1777 . If a phrase with an APL jump, such as *→N* (i.e. to line *N* of a defined
1778 function) is matched, then a new value for the *PC* is computed so
1779 that *body[PC]* is the first token of line N. If no such line exists,
1780 then the Prefix parser returns its result (either TOK_VOID for functions
1781 that return no result or TOK_VALUE otherwise.
1782 . If the parser sees a closing parenthesis *)* or bracket *]* then the parser
1783 creates a sub-parser and execution is continued (with the current PC) in
1784 the sub-parser until the corresponding opening parenthesis *(* or bracked
1785 *[* is reached. The result of the sub-parser, typically a token with class
1786 *TC_VALUE* for parentheses and *TC_INDEX* for brackets is returned to the
1787 calling parser,
1788 . an end of statement token (class TC_END) does not stop the parser. The
1789 necessary actions, e,g, printing of the value for non-committed APL values
1790 is performed in the reduce function (which calls
1791 *StateIndicator::statement_result()*), and the parser simply continues after
1792 the reduce function returns. Only the end of the *body* stops the parser,
1793 and the last token in the *body* performs the transfer of the value computed
1794 by a defined APL function to its caller.
1795
1796 The tokens in the current sequence are of Cpp type *Token_loc* instead of
1797 type *Token*. *Token_loc* is a Token and a range in the *body*. When a
1798 token is first fetched from, say, *body[PC]*) then the range of its
1799 *Token_loc* is *[PC:PC+1]*. As more and more consecutive tokens are being
1800 reduced, that range grows and contains all tokens that have contributed to
1801 the creation of every token. The range in the body of a defined function
1802 is needed for proper error reporting.
1803
1804 The case 3. above is the most tricky one and deserves a closer look at it.
1805
1806 ==== Ambiguity of APL symbols.
1807
1808 In compiled lanuages like C/Cpp every name defined by the user must be
1809 _declared_. Any use of a name without a prior declaration is an error detected
1810 by the compiler. The declaration determines, among other things, whether the
1811 name refers to a variable, or to a function, and in that latter case the arity
1812 (number of arguments) of a function.
1813
1814 In contrast, in APL the role of a user defined name is not defined at
1815 ⎕FX-time but at runtime. Due to the declarations in e.g. C/Cpp the scope
1816 of a name (and from that the relevant declaration) can be determined
1817 statically (i.e. at compile time) while in APL the role of a name must
1818 be inevitably determined at runtime. In both cases (APL vs. C/Cpp) the
1819 same name may have different roles at different times, but the point in
1820 time where the role is determined varies. As a consequence, the compiler uses
1821 its symbol table only at compile time while APL also uses it at runtime.
1822 Consider the following example:
1823
1824 ----
1825 )CLEAR
1826
1827 ⍝ define function LEAF (for a function that does not call others)
1828 ⍝
1829 ∇Z←LEAF
1830 Z←'LEAF is a niladic defined function.'
1831 ∇
1832
1833 ⍝ define function FOO, which localizes symbol LEAF
1834 ⍝
1835 ∇Z←FOO;LEAF
1836 LEAF←'LEAF is a (localized) variable.'
1837 BAR
1838 ∇
1839
1840 ⍝ define function BAR which calls LEAF.
1841 ⍝
1842 ∇Z←BAR
1843 Z←LEAF
1844 ∇
1845
1846 ⍝ then see what happens
1847 ⍝
1848 FOO ◊ BAR
1849 LEAF is a (localized) variable.
1850 LEAF is a niladic defined function.
1851 ----
1852
1853 In the simple example above, *BAR* is called twice: first from *FOO* and then
1854 directly from immediate execution (to simplify the example; the same
1855 would happen if *BAR* were called from some other defined function). The
1856 problem in the example above is that *BAR* cannot statically decide whether
1857 the symbol *LEAF* in its function body relates to the niladic function *LEAF*
1858 or to the local variable *LEAF* of function *FOO*. One can even construct
1859 more complex examples where _the same statement_ of a defined function
1860 must, according to the evaluation rules of APL, produce _different results_
1861 depending how it was called. As a
1862
1863 _Corollary:_ The parse tree of an APL statement is only unique when the
1864 statement contains no user defined symbols. And therefore:
1865
1866 _Corollary:_ In general, every APL statement yields a (possibly degenerated)
1867 parse tree, where each APL symbol in the statement is a branching point at
1868 which it has to be decided (at runtime) which branch down the tree shall be
1869 chosen.
1870
1871 The degenerated case is the one where all symbols can be resolved statically
1872 (such as labels in a defined function), and then the tree becomes a linear
1873 sequence. In real-life APL programs this degenerated case is fairly rare. It
1874 could be optimized in a simple manner, but its rarity seems not be worth the
1875 effort. A more frequent exception is non-conditional branches like *→LABEL*
1876 which are optimized in GNU APL.
1877
1878 Now, back to the *TC_SYMBOL*. If the prefix parser reads a symbol, then
1879 it consults the symbol table for the current meaning of the symbol.
1880 There are quite a few different cases:
1881
1882 * The symbol is undefined, for example a local variable before a value is
1883 assigned to it or a defined function with that name was created. In this
1884 case:
1885 ** If the symbol is referenced (i.e. on the right of →) then a SYNTAX ERROR
1886 is raised, otherwise
1887 ** The symbol is (the name of) a variable that is being assigned (either
1888 completely, or indexed, or selectively).
1889 * The symbol is a defined function, in that case the *TC_SYMBOL* token is,
1890 depending on the signature of the defined function, replaced with a token
1891 of class *TC_FUN0*, *TC_FUN12*, *TC_OPER1*, or *TC_OPER2*. The token value
1892 then points to a *UserFunction*. Note that APL primitives and APL system
1893 functions are not user-defined, and therefore no symbol table lookup is
1894 required. The pre-parser can therefore produce the corresponding tokens
1895 directly.
1896 * The symbol is a variable.
1897 ** A variable right of ← is referenced and the *TC_SYMBOL* token is replaced
1898 by a *TC_VALUE* token pointing to the current value of the variable.
1899 Otherwise the symbol is subject to an assignment and is, for the moment,
1900 left unchanged. At a later time one of the assignment phrases is supposed
1901 to match:
1902 *** *A←VALUE* ⍝ normal assignment (symbol *A* may or may not exist),
1903 *** *(A B ...)←VALUE* ⍝ vector assignment (symbols *A*, *B*... may or may
1904 not exist),
1905 *** *A[X]←VALUE* ⍝ indexed assignment (*A* must be a variable),
1906 *** *(f... A)←VALUE* ⍝ selective assignment (*A* must be a variable),
1907
1908 All this happens in *Prefix::push_Symbol()* which delegates most of its work
1909 to either *Symbol::resolve_left()* or *Symbol::resolve_right()*, depending
1910 on the position of the symbol in the statement. This position is tracked
1911 with *Prefix::set_assign_state()*, which is one of:
1912
1913 ----
1914 APL_types.hh:
1915 ...
1916 // the state of an assignment
1917 enum Assign_state
1918 {
1919 ASS_none = 0, ///< no assignment (right of ←)
1920 ASS_arrow_seen = 1, ///< ← seen but no variable yet
1921 ASS_var_seen = 2, ///< var and ← seen
1922 ASS_unknown = 3, ///< not known (too much effort to determine)
1923 };
1924 ...
1925 ----
1926
1927 NOTE: *Terminology:* The GNU APL prefixes are called *pattern* or *phrase*
1928 in the ISO standard. The token sequence above is called *stack* in the ISO
1929 standard and also in some of GNU APL debug printouts.
1930
1931 The main implementation of the algorithm above is Cpp function
1932 *Prefix::reduce_statements()*. It returns a *Token*. The function
1933 uses C/Cpp goto statements because that leads to much clearer code than the
1934 so called "structured programming" would. The goto labels in this function
1935 are:
1936
1937 * *grow:* do a SHIFT (if no phrase has matched),
1938 * *again:* repeat phrase matching (after a reduce function was called), and
1939 * *done:* the parser returns.
1940
1941 The point of *again:* is that the reduction of some phrases, for example an
1942 expression in parentheses, may produce a stack that could not be reduced
1943 before but now can without reading another token.
1944
1945 === An Example
1946
1947 Consider the APL code from our example above, for simplicity in immediate
1948 execution:
1949
1950 A←1 2 3
1951
1952 The tokenizer translates the string "A←1 2 3" into a 4-item *Token_string*:
1953
1954 ┌───────┐ ┌───┐ ┌───┐ ┌────────┐
1955 │ 1 2 3 │ │ ← │ │ A │ │ RETURN │
1956 └───────┘ └───┘ └───┘ └────────┘
1957
1958 To be precise, the *RETURN* token is actually appended by function
1959 *StatementList::fix()* and not by the Tokenizer itself. Then:
1960
1961 . The prefix parser reads (the single) token *1 2 3* and shifts.
1962 Pattern is now: *value(1 2 3)*.
1963 . The prefix parser reads *←* and shifts. Pattern is now: *← value(1 2 3)*.
1964 . The prefix parser reads *A*. The pattern matches and the parser
1965 reduces with *Prefix::reduce_A_ASS_B_()*. The result is
1966 *committed_value(1 2 3)* and the new pattern is also:
1967 *committed_value(1 2 3)*
1968 . The prefix parser reads *RETURN*. The pattern matches and the parser
1969 reduces with *Prefix::reduce_END_B__()*, which calls
1970 *StateIndicator::statement_result()* and clears the pattern to empty.
1971 . The parser has no more token to read and returns.
1972
1973 === Another Example
1974
1975 (1 + 2) FOO 4 ⍝ with dyadic defined function FOO
1976
1977 The tokenizer produces:
1978
1979 ┌───┐ ┌─────┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌────────┐
1980 │ 4 │ │ FOO │ │ ) │ │ 2 │ │ + │ │ 1 │ │ ( │ │ RETURN │
1981 └───┘ └─────┘ └───┘ └───┘ └───┘ └───┘ └───┘ └────────┘
1982
1983 . The parser shifts *4* and *FOO* and creates a sub-parser for ).
1984 . The sub-parser reduces *(1+2)* and returns the value *3*.
1985 . The parser reads the result *3* and computes *3 FOO 4*.
1986
1987 ==== Properties of the reduce_XXX() functions
1988
1989 * In GNU APL there is a total of 67 phrases and consequently 67 reduce
1990 functions.
1991 * reduce functions are typically short. Nevertheless they cannot be in-lined
1992 since they are being called via the function pointer
1993 *Prefix::Phrase::reduce_fun* in the phrase table (or tree).
1994 * reduce functions have return type *void* and no arguments. They access the
1995 token which they reduce directly from a ring-buffer named *Prefix::content*
1996 and also store the result there (function *Prefix::pop_args_push_result()*)
1997 * accessing the token is performed via functions *at0()*, *at1()*, *at2()*, or
1998 *at3()*, where *at0()* is the leftmost (in APL code order) and the rightmost
1999 (in reversed order) token. For example, in *reduce_V_ASS_B()* corresponds *V*
2000 to *at0()*, *ASS* to *at1()*, and *B* to *at2()*.
2001 * the lookahead token of the LALR(1) parser is always a token in the body of a
2002 defined function. It therefore needs not (yet) to be copied at the time of
2003 the lookahead. It is instead accessed with *Prefix::lookahead()*, which
2004 returns *TOK_VOID* if no lookahead token exists.
2005
2006 The principal structure of a reduce function is always:
2007
2008 . obtain the arguments (*at0()*, *at1()*, ...)
2009 . compute the desired side effect (assign a variable, evaluate a function,
2010 perform a branch, etc.)
2011 . remove (pop) the arguments from the stack and push the result on the stack,
2012 in most cases with *Prefix::pop_args_push_result()*, and finally
2013 . set member *Prefix::action* to the next action that the prefix parser shall
2014 perform. The possible actions are (enum *R_action* in *Prefix.hh*):
2015 .. *RA_CONTINUE*: repeat the phrase matching with the current stack (after a
2016 reduce_XXX() has modified it, e.g. with *pop_args_push_result()*.
2017 .. *RA_PUSH_NEXT*: push the next token onto the stack (aka. SHIFT)
2018 .. *RA_RETURN*: return from the current (sub-) parser and push its result onto
2019 the stack of the calling parser, or
2020 .. *RA_SI_PUSHED*: like *RA_RETURN* but without a result (called a *future*
2021 in esoteric computer languages). It indicates that a new parser with a new
2022 defined function was started and will or will not return a result. This
2023 case is slightly different from simply calling a sub-parser, because a
2024 sub-parser (e.g. for parentheses) remains in the same function body, while
2025 a new defined function has its own body.
2026
2027 === Construction of the phrase table (or tree)
2028
2029 The large number of phrases makes it error prone and cumbersome to handle
2030 them. For that reason the declaration of all *reduce_XXX()* functions (in
2031 *Prefix.hh*, as well as the instantiation of a hash table for fast lookup of
2032 phrases (or, alternatively a search tree) in *Prefix.cc* are realized by
2033 including *src/Prefix.def*. That is, *Prefix.def* is, with the help of the Cpp
2034 preprocessor, a code generator for *Prefix.hh* and *Prefix.cc*. *Prefix.def*
2035 itself is also generated (with *tools/phrase_gen*). And *tools/phrase_gen*
2036 itself *#includes* file *tools/phrase_gen*.def which contains the primary
2037 definition of all phrases (similar to the phrase table in the ISO standard.
2038 This machinery is hidden behind *tools/makefile* with targets: *gen* (for a
2039 hash table) and *gen2* (for a search tree). Note the lowercase *makefile*; the
2040 tools directory also contains an (uppercase) *Makefile* which belongs to the
2041 build system. The full picture is this:
2042
2043 ----
2044
2045 ╔═════════════════════╗ ╔══════════════════════╗
2046 ║ tools/phrase_gen.cc ║ ║ tools/phrase_gen.def ║
2047 ╚══════════╤══════════╝ ╚══════════╤═══════════╝
2048 │ │
2049 ┌────────┴───────┐ │
2050 │ tools/Makefile │ ↓
2051 └────────┬───────┘ │
2052 │ │
2053 g++ ─────── #include ───────┘
2054 │
2055 ╔════════╧═════════╗
2056 ║ tools/phrase_gen ║ ./configure
2057 ╚═════════╤════════╝
2058 │ ══════════════════
2059 ┌────────┴───────┐
2060 │ tools/makefile │ make
2061 └────────┬───────┘
2062 │
2063 write
2064 │
2065 ┌────────┴────────┐ ┌───────────────┐
2066 │ src/Prefix.def ├───────── #include ─── → ───┤ src/Prefix.hh │
2067 └────────┬────────┘ └───────┬───────┘
2068 │ │
2069 ↓ ↓
2070 │ ┌───────────────┐ │
2071 └── #include ──┤ src/Prefix.cc ├── #include ──┘
2072 └───────┬───────┘
2073 │
2074 g++
2075 │
2076 ┌─────────┴────────┐
2077 │ src/apl-Prefix.o │
2078 └──────────────────┘
2079 ----
2080
2081 NOTE: GNU APL is shipped with *src/Prefix.def* already produced, so that the
2082 "normal" designer is rarely concerned with the above. Unless she needs to
2083 change the GNU APL phrase table.
2084
2085 If, however, *tools/phrase_gen.def* was modified, then
2086
2087 ----
2088 make gen # generate new src/Prefix.def with a phrase table, or
2089 make gen2 # generate new src/Prefix.def with a phrase tree
2090 ----
2091
2092 needs to be performed once. The build system will then note the changed
2093 *src/Prefix.def* and a top-level make will recompile the affected files in
2094 directory *src*.
2095
2096
2097 == Noteworthy Classes
2098
2099 === String Classes
2100
2101 The GNU APL source code has more than 1000 places where strings are used.
2102 These strings come in 2 flavors:
2103
2104 . strings of 32-bit Unicodes (sometimes referred to as UCS-32),
2105 . strings of bytes in UTF8 encoding.
2106
2107 GNU APL uses 2 classes for these strings: class *UCS_string* for 32-bit
2108 Unicodes and *UTF8_string* for UTF8-encoded strings. In general:
2109
2110 * UCS_strings are far easier to use than UTF8_strings because UTF8 is a
2111 variable-length encoding, which makes indexing or iterating over them
2112 cumbersome and error-prone. For this reason all strings used internally
2113 in GNU APL are UCS_strings.
2114 * UTF8_strings are commonly used between GNU APL and its environment. They
2115 are shorter when transported over the Internet, therefore most web pages
2116 are UTF8-encoded. Also, filenames in operating systems are UTF8 encoded.
2117 Finally, most terminal emulators, in particular those that support APL in
2118 some way, send and expect all characters to be UTF8-encoded.
2119
2120 ==== UCS_string
2121
2122 The starting point is:
2123
2124 ----
2125 Unicode.hh:
2126
2127 enum Unicode
2128 {
2129 #define char_def(name, uni, _tag, _flags, _av_pos) UNI_ ## name = uni,
2130 #define char_uni(name, uni, _tag, _flags) UNI_ ## name = uni,
2131 #include "Avec.def"
2132
2133 Unicode_0 = 0, ///< End of unicode string
2134 Invalid_Unicode = 0x55AA55AA, ///< An invalid Unicode.
2135 };
2136 ----
2137
2138 where:
2139
2140 * The *char_def()* macro defines all Unicodes that are contained in the 256
2141 character *⎕AV* of GNU APL. In old APL1 the ⎕AV and its derivates (⎕FC, ⎕A,
2142 ⎕D, ...). These days, the ⎕AV is only maintained for backward compatibility
2143 with APL1. In APL2 it has been entirely obsoleted by *⎕UCS*. Keep in mind,
2144 however, that:
2145 ** The encoding of files produced with )OUT or read with )IN are still based
2146 on ⎕AV. To be precise: based on some IBM ⎕AV defined in the IBM APL2
2147 reference manual, not on the GNU APL ⎕AV. Generally ⎕AVs as well as their
2148 encodings are machine specific, some mainframes even used EBCDIC and older
2149 PC operating systems used special APL code pages which corresponded to the
2150 ⎕AV.
2151 ** GNU APL has two helpers for such conversions, see below.
2152 ** *class *Avec* contains numerous static functions for handling and
2153 classifying of Unicodes contained in the *⎕AV*.
2154 * In contrast, the *char_uni()* macro defines Unicodes that are used in
2155 the GNU APL source code but are not contained in the *⎕AV* of GNU APL.
2156 * In short:
2157 ** any Unicode with APL significance (primitives etc.) are (and
2158 must be) contained in the ⎕AV of the interpreter. These Unicodes are
2159 defined with macro *char_def()* in file *Avec.def*, while
2160 ** any Unicode used in the GNU APL Cpp source code is defined with
2161 macro *char_uni()*.
2162 ** Noteworthy examples of the latter are the sub- and superscripts
2163 (⁰, ¹, ², ..., ⁹, and ₀, ₁, ₂, ..., ₉). They are not contained in the ⎕AV
2164 of GNU APL but occur in the .xml files produced by GNU APL (and not only
2165 in the source code).
2166
2167 The helpers mentioned above are:
2168
2169 ----
2170 Avec.hh:
2171 /// a pointer to 256 Unicode characters that are exactly the APL2 character
2172 /// set (⎕AV) shown in LRM Appendix A, page 470. The ⎕AV of GNU APL is
2173 /// similar, but contains characters like ≢ that are not in IBM's ⎕AV
2174 /// IBM's ⎕AV is used in the )IN command
2175 static const Unicode * IBM_quad_AV();
2176
2177 /// recompute \b inverse_ibm_av from \b ibm_av and print it
2178 static void print_inverse_IBM_quad_AV();
2179 ----
2180
2181 After this digression into Unicodes we can now:
2182
2183 ----
2184 UCS_string.hh:
2185
2186 class UCS_string : public std::basic_string<Unicode>
2187 {
2188 ...
2189 UCS_string(const UTF8_string & utf);
2190 ...
2191 }
2192 ----
2193
2194 UCS_string has many constructors, most importantly the constructor from a
2195 UTF8_string which converts the UTF8_string into a UCS_string. In addition the
2196 UCS_string string class defines numerous convenience functions for the
2197 processing of UCS_strings.
2198
2199 ==== UTF8_string
2200
2201 In good old C, there were C literals like *"Hello, world"*. At that time the
2202 only relevant encoding of such literals was the 7-bit ASCII code and all
2203 literals contained only positive (signed) characters.
2204
2205 Next, Cpp defined a template class *std::basic_string<>* which provides
2206 numerous string processing methods (indexing, iteration) for *basic_string*
2207 that are also used in our derived classes *UCS_string* and *UTF8_string*.
2208 So far so good.
2209
2210 But now comes the problem. The Cpp standard string library says:
2211
2212 ----
2213 class string : public basic_string<char> { }
2214 ----
2215
2216 On almost all platforms (read: compilers), a *char* is *signed* as
2217 opposed to type *unsigned char*. Often this does not hurt because C and Cpp
2218 automatically convert between the signed and unsigned variants and not every
2219 programmer is always aware of the dire consequences of signedness. Like, for
2220 example:
2221
2222 ----
2223 !
2224 char(-56) = char(200) < char(100) = unsigned char(100) < unsigned char(200).
2225 ----
2226
2227 To make things worse, UTF8 encoding works on (unsigned) bytes while C/Cpp
2228 literals in compilers are, without specific qualifiers, signed. As a
2229 consequence, the APL character *'←'* has Unicode 8592 aka. 0x2190, and a UTF8
2230 encoding of (hex) *E2 86 90* which makes the string literal "→" a
2231 (0-terminated) sequence of 3 signed (!) and unfortunately negative (!)
2232 characters. Early versions of GNU APL used *std::string* instead of
2233 *UTF8_strings*, and the problems caused by that were numerous. These days
2234 GNU APL itself is clean when it comes to signed vs. unsigned chars, but some
2235 older contributions may still suffer. Comparisons for equality work well for
2236 mixed signed/unsigned operands, but < and > do not, and, as a consequence,
2237 *strcmp()* and friends frequently return the wrong order when used for sorting
2238 UTF-encoded strings.
2239
2240 Like *UCS_string* has a constructor from a *UTF8_string*, *UTF8_string* has a
2241 constructor from a *UCS_string*:
2242
2243 ----
2244 UTF8_string.hh:
2245
2246 /// one byte (not character)! of a UTF8 encoded Unicode (RFC 3629) string
2247 typedef uint8_t UTF8;
2248
2249 class UTF8_string : public std::basic_string<UTF8>
2250 {
2251 ...
2252 /// constructor: copy of UCS string. The Unicodes in ucs
2253 /// will be UTF8-encoded
2254 UTF8_string(const UCS_string & ucs);
2255 };
2256 ----
2257
2258 The take-aways for designers and contributors are:
2259
2260 * prefer UCS_string over UTF8_string where possible (efficiency),
2261 * never use std::string, but
2262 * instead use UTF8_string and
2263 * do not write your own conversion functions but use the constructors instead.
2264
2265
2266 === APL Values
2267
2268 The primary business of an APL interpreter is to manipulate APL values.
2269 An APL value is simply a *Shape* and a *Ravel*, although simplicity ends here.
2270
2271 In that, *Shape* is a class of its own, defined in *Shape.hh*. It has a bunch
2272 of constructors for various purposes and also numerous inline convenience
2273 functions that make the code that deals with shapes more readable.
2274
2275 Many of the Shape methods have trivial wrappers in *class Value*, because
2276 almost every shape is accessed in the context of a value. For example:
2277
2278 ----
2279 Shape.hh:
2280
2281 ...
2282 /// return the rank
2283 uRank get_rank() const
2284 { return rho_rho; }
2285
2286 Value.hh:
2287
2288 ...
2289 /// return the rank of \b this value
2290 uRank get_rank() const
2291 { return shape.get_rank(); }
2292 ...
2293 Shape shape;
2294 ...
2295 ----
2296
2297 The ravel is simply a Cpp array of type *Cell*:
2298
2299 ----
2300 Value.hh:
2301
2302 ...
2303 /// The ravel of \b this value.
2304 Cell * ravel;
2305
2306 /// the cells of a short (i.e. ⍴,value ≤ cfg_SHORT_VALUE_LENGTH_WANTED) value
2307 Cell short_value[cfg_SHORT_VALUE_LENGTH_WANTED];
2308 ----
2309
2310 Many real-life APL values are short. To avoid unnecessary memory allocations,
2311 GNU APL allocates short ravels inside the class instance and longer ravels
2312 outside (which then requires an additional new/delete for the ravel). Put
2313 differently, a short value has *ravel == &short_value*, while *ravel* in
2314 long values point to a separately allocated memory area. The border between
2315 short and long values can be changed with *./configure*; larger values of
2316 *SHORT_VALUE_LENGTH_WANTED* have (marginally) better performance, but the
2317 price is a (less marginal) increase in memory consumption.
2318
2319 Similar to *class Shape*, there are numerous constructors and (mostly trivial)
2320 access functions for various purposes. For example, a Value can be constructed
2321 from a UCS_string (and conversely a UCS_string can be constructed from a Value
2322 (provided that its rank and Cell types are correct). Most values are
2323 constructed sequentially and to simplify that, every value has a built-in
2324 iterator *Value::next_ravel()* which returns a pointer to the next
2325 not-yet-initialized Cell (if any) and 0 after the last Cell of the ravel
2326 was returned.
2327
2328 TIP: A frequent pitfall related to the *Value::next_ravel()* iterator is to
2329 (mistakenly) use it for empty values.
2330
2331 Empty APL values like *0⍴0* are never empty at the Cpp level because every APL
2332 value *V* has a _prototype_ *↑0⍴V* whose ravel has one item stored in
2333 *ravel[0]*. An old APL joke was, _How many empty arrays does it take to fill
2334 an APL workspace? One, if it's big enough._ If a value *V* is empty, then *⍴V*
2335 is 0 (i.e. its ravel has length 0) but length 1 at Cpp level (due to its
2336 prototype). For this reason, a *Value* has a *Value::element_count()*, which
2337 is the ravel length in APL, and a *Value::nz_element_count()* which is the
2338 ravel length in Cpp. The *Value::next_ravel()* iterator uses the former, which
2339 causes a segfault when used with an empty value. In short this means that APL
2340 values may be empty, but their Cpp implementations are never empty _and need
2341 to be properly initialized_.
2342
2343 CAUTION: This implies that a proper source code *loop()* over a ravel MUST
2344 either use *Value::nz_element_count()* (so that the prototype is initialized
2345 inside the loop), or else must have ruled out the empty case beforehand (and
2346 may then use *Value::element_count()* safely).
2347
2348 The typical design patterns are:
2349
2350 ----
2351 Value_P Z(...); // may be empty
2352
2353 loop(z, Z->nz_element_count()) // not element_count() !!!
2354 {
2355 new (Z->get_wravel(z)) XxxCell(...)); // safe, but (next_ravel_XXX() is not)
2356 }
2357 ----
2358
2359 and:
2360
2361 ----
2362 Value_P Z(...); // may be empty
2363
2364 if (Z->element_count()) // not Z->nz_element_count() !!!
2365 {
2366 // Z is not empty
2367 loop(z, Z->element_count()) Z->next_ravel_XXX(...)
2368 }
2369 else
2370 {
2371 new (Z->get_wproto()) XxxCell(...)); // init prototype
2372 }
2373 ----
2374
2375 *Z->get_wproto()* is the same as *Z->get_wravel(0)* and is used here to make
2376 the role of *get_wravel(0)* as the prototype of Z explicit.
2377
2378 ==== class Value_P
2379
2380 APL values are rarely copied but pointers to APL values are passed back and
2381 forth a lot in the interpreter (in more than 1200 source code locations),
2382 It is therefore easy to loose a Value, which then causes a memory leak. Early
2383 GNU APL versions were plagued by these memory leaks, but are now fixed
2384 using several counter-measures:
2385
2386 * Cpp overloading of operators ::new() and ::delete(). Every newly allocated
2387 Value, no matter if long or short, is tracked in a link list called
2388 *DynamicObject::all_values*, see *DynamicObject.hh*
2389 * The APL command )CHECK compares the values that are are reachable from APL,
2390 e.g. via a token of *class TC_Value*, with the values in
2391 *DynamicObject::all_values* and reports any mismatches as *stale values*.
2392 * Every value tracks itself with a *ValueHistory* which is, for performance
2393 reasons, disabled by default but can be enabled with *./configure*,
2394 or with *make develop*.
2395 * A reference counter named *Value::owner_count* in combination with *class
2396 Value_P*. A value is automatically deleted when its last owner (typically
2397 a *Token* is deleted.
2398 * Member *Value::check_ptr* to detect incorrect
2399 * overwriting or double deletion of a value. Every *Value* constructor sets
2400 *check_ptr* to *(this * * 7)* which points into the middle of a *uint64*
2401 (of member Value::shape). The destructor later checks that *check_ptr*
2402 is still *(this * * 7)* (to detect overwriting) and clears it (to detect
2403 double deletion). The *check_ptr* is:
2404 ** is different for every Value,
2405 ** is a pointer that cannot occur otherwise,
2406 ** becomes incorrect when a Value is incorrectly moved (e.g. with *memcpy()*)
2407
2408 Value_P is essentially a smart pointer (aka. shared pointer). A "normal" smart
2409 pointer typically consists of 2 pointers:
2410 * one pointing to the object itself, and
2411 * one to the reference counter that keeps track of the object's ownership
2412 (aka. the reference counter)
2413
2414 In contrast, the *Value_P* is a single pointer (to a Value), and the reference
2415 counter is allocated inside the value rather than somewhere else. The small
2416 advantage of a "normal" smart pointer is that they are not intrusive, which
2417 means that they can be used without any modifications of the object that they
2418 point to. But since we are in control of the Value class, this benefit does
2419 not really count and the smaller size of a *Value_P* outweighs the benefit of
2420 standard smart pointers. The Value_Ps are also decoupled from each other;
2421 one can always construct a Value_P from a Value * (and vice versa). The
2422 most important member functions of Value_P are:
2423
2424 * *Value_P()* : default constructor (points to no value)
2425 * *Value_P(Value * val, const char * loc)* : construct Value_P from a Value *
2426 * *Value_P(const Value_P & other, const char * loc)* : construct from *other*
2427 * *Value_P(const Shape & sh, const char * loc)* : construct Value_P to a new
2428 value with shape *sh*. The ravel of that value is not (yet) initialized.
2429 * *inline Value_P(const UCS_string & ucs, const char * loc)* : construct an APL
2430 text vector whose ravel Cells are initialized from the UCS_string,
2431 * *inline Value_P(const UTF8_string & utf, const char * loc)* : construct an APL
2432 text vector whose ravel Cells are initialized from the UTF8_string. ⍴Value is
2433 *utf.size()*, i.e. the UTF8 bytes are kept and no decoding into Unicodes is
2434 performed
2435 * *void reset()* : decrement the owner-count and clear the pointer
2436 * *init_pointer()* reset() without decrementing the owner-count
2437 * *void clear()* : reset and add an event to the ValueHistory (if enabled)
2438 * *bool operator +()* : *true* iff the pointer is valie (non-zero)
2439 * *bool operator !()* : *true* iff the pointer is invalie (zero)
2440 * *Value * operator->()* : return the Value * (to the Value)
2441 * *Value & operator *()* : return the Value & reference (of the Value)
2442 * *void increment_owner_count()* : dito.
2443 * *void decrement_owner_count()* : dito.
2444 * *void isolate(const char * loc)* : if the value has more than one owner then
2445 clone (deep copy) the value and set pointer to the new copy.
2446 * *void move(Value_P_Base & other, const char * loc)* :
2447 ** release ownership of the current pointer,
2448 ** take ownership of other's pointer, and
2449 ** reset other's pointer. This operation does not change the owner_count of
2450 the object.
2451
2452 All functions are inline and some can throw exceptions (primarily *WS FULL*).
2453 Note that some *Value_P* constructors above (e.g.
2454 *Value_P(const UCS_string & ucs, ...)* initialize the entire Value (shape
2455 and ravel) while others (e.g. *Value_P(const Shape & sh)*) only initialize the
2456 shape and leave the initialization of the ravel to the caller. In fact, the
2457 construction of a Value is always a two-step process (initializations of the
2458 shape followed by the initializations of the ravel) and the constructors that
2459 do both are mere convenience constructors for frequent cases. The following
2460 design pattern can found in many places:
2461
2462 ----
2463 Value_P Z(...); // construct Z (with un-initialized ravel)
2464 loop(x, z.element_count()) Z->next_ravel_XXX(...); // initialize the ravel
2465 Z->check_value(LOC) // set checked flag, detect un-initialized ravel items
2466 return Z;
2467 ----
2468
2469 The constructors for **Value**s are protected (with friend *Value_P*) to
2470 enforce that values are always constructed via *Value_P::Value_P(...)* rather
2471 than the corresponding *Value::Value(...) **. On the other hand, many
2472 functions use *const Value **" (note the const!) instead of *Value_P*,
2473 primarily for passing function arguments. This is safe and slightly more
2474 efficient if the called function does not modify the Value (and hence its
2475 ownership) passed as an argument.
2476
2477 ==== Cloning of Values
2478
2479 The cloning (deep aka. recursive copy) of a Value is somewhat expensive in
2480 terms of performance. Cloning is, however, only needed if the clone is
2481 modified later (which would corrupt the original). When a *Value* is assigned
2482 to a Symbol (i.e. a variable) then it must be cloned because the variable may
2483 or may not be changed later. Think of a literal in a function body:
2484
2485 ----
2486 ∇Z←FOO
2487 Z←1 2 3
2488 ∇
2489
2490 X←FOO ◊ X←4 5 6
2491 ----
2492
2493 If we do not clone the result of FOO, not cloned before assigning it to
2494 X, then the subsequent assignment to X would modify the body of FOO and the
2495 next call of FOO would return 4 5 6.
2496
2497 On the other hand:
2498
2499 ----
2500 ∇Z←FOO
2501 Z←1 2 3
2502 ∇
2503
2504 X←1 + FOO ◊ X←4 5 6
2505 ----
2506
2507 is safe because the addition + does not modify the result of FOO but rather
2508 discards it immediately. GNU APL versions have always cloned values before
2509 assigning them (to be on the safe side). Current versions check how many
2510 owners a value has before coning them:
2511
2512 ----
2513 Value.hh
2514
2515 #define NEW_CLONE
2516
2517 #ifdef NEW_CLONE /* new clone() scheme */
2518
2519 /// clone, given a Value_P. Result is a Value_P.
2520 # define CLONE_P(B_P, L) (B_P)
2521
2522 /// clone, given a const Value *. Result is a Value_P.
2523 # define CLONE(pB, L) Value_P(const_cast<Value *>(pB), L)
2524
2525 #else /* old clone() scheme */
2526
2527 /// clone, given a Value_P. Result is a Value_P.
2528 # define CLONE_P(B_P, L) (B_P).get()->clone(L)
2529
2530 /// clone, given a Value *. Result is a Value_P.
2531 # define CLONE(pB, L) (pB)->clone(L)
2532
2533 #endif
2534 ----
2535
2536 The rules are:
2537
2538 * If a Cpp function knows from its context that cloning is not needed (like in
2539 the second example above) then it may CLONE() and CLONE_P(). Determining if
2540 the cloning is actually performed, then depends on whether *NEW_CLONE*
2541 is *#defined* or not. This could be a mistake and then _not_ **#define**ing
2542 *NEW_CLONE* is a quick way to fall back to the old scheme.
2543 * Otherwise, _in particular if_ *#define NEW_CLONE* _makes a difference_, the
2544 function shall use *Value->clone() ** which clones unconditionally.
2545
2546 ==== Ravel Cells
2547
2548 The ravel of every *Value* is a simple C array and not a Cpp
2549 *std::vector<Cell>*. The alternative *std::vector<Cell>* has some performance
2550 penalties when used for the ravel of a *Value*:
2551
2552 * destructor calls for every Cell when the vector<> is destructed, and
2553 * no support for short values.
2554
2555 The other alternative, linked list of **Cell**s, was also not an option due
2556 to their overhead in memory allocation (one *new()* *delete()* per Cell. The
2557 huge number of Cells in a typical APL program on the one hand and the typical
2558 operations performed with the Cells on the other result in the following,
2559 somewhat conflicting, requirements:
2560
2561 * fixed *Cell* size
2562 * different cell contents (character, integer, float, complex, and nested) to
2563 support mixed APL values. In the old APL1 all values were homogeneous (and
2564 the type was a property of the value and its ravel). In APL2 the type
2565 became a property of the ravel Cells. Some APL interpreters optimize for
2566 the case of homogeneous ravels (probably a fair guess for APL2 programs
2567 inherited from an APL1 code base) while GNU APL assumes mixed APL values as
2568 the default. Both assumptions (homogeneous vs. mixed) have advantages and
2569 drawbacks:
2570 ** Homogeneous arrays are faster to process, but this backfires when the
2571 automatic type conversion of APL (bool to integer, integer to float, float
2572 to complex takes place.
2573 ** Loops in the mixed case for scalar functions become much simpler because
2574 the different combinations of types (e.g. Boolean + Boolean,
2575 Boolean + integer, integer + integer, ...). Making e.g. dyadic *{plus}(A, B)*
2576 a virtual member function *B.{plus}(A)* of *B* and monadic *{plus}(B)* a
2577 virtual member function *(B.{plus}()* of *B*, removes two case statements
2578 (with the dyadic one being quite ugly).
2579
2580 The base class *Cell* therefore defines a pretty large number of virtual
2581 functions (a monadic and a dyadic one for each of the scalar APL functions:
2582
2583 ----
2584 Cell.hh:
2585
2586 ...
2587 virtual ErrorCode bif_ceiling(Cell * Z) const
2588 virtual ErrorCode bif_conjugate(Cell * Z) const
2589 virtual ErrorCode bif_direction(Cell * Z) const
2590 ...
2591 virtual ErrorCode bif_add(Cell * Z, const Cell * A) const
2592 virtual ErrorCode bif_and(Cell * Z, const Cell * A) const
2593 virtual ErrorCode bif_and_bitwise(Cell * Z, const Cell * A) const
2594 ...
2595 ----
2596
2597 The base class *Cell* is inherited by the following derived classes:
2598
2599 * *CharCell*, their relevant content is a single 32-bit Unicode,
2600 * *IntCell*, their relevant content is a single 64-bit signed integer,
2601 * *RealCell*, their relevant content is a 64-bit floating point number,
2602 * *ComplexCell*, their relevant content is two 64-bit floating point numbers
2603 * *NumericCell*, the base class of *IntCell*, *RealCell*, and *ComplexCell*.
2604 Many Cell functions are almost identical for these base classes and these
2605 functions are implemented in *NumericCell* rather than implementing a
2606 copy in each base class. The simple trick that replaces hundreds of
2607 C/Cpp *switch* statements and **case**s is this:
2608 ** base class *Cell* implements virtual functions that either throws a
2609 *DOMAIN ERROR* (e.g. for a character to integer conversion) or else
2610 return the desired type:
2611 *** virtual Unicode get_char_value() const { DOMAIN_ERROR; }
2612 *** virtual APL_Integer get_int_value() const { DOMAIN_ERROR; }
2613 *** virtual APL_Float get_real_value() const { DOMAIN_ERROR; }
2614 *** virtual APL_Float get_imag_value() const { DOMAIN_ERROR; }
2615 *** virtual Value_P get_pointer_value() const { DOMAIN_ERROR }
2616 *** virtual Cell * get_lval_value() const { LEFT_SYNTAX_ERROR; }
2617 ** the derived classes then overload all access functions that they support.
2618 For example,
2619 *** *CharCell* overload only *get_char_value()*
2620 *** all **NumericCell**s overload *get_int_value()*, *get_real_value()*,
2621 and *get_imag_value()* but not *get_char_value()*,
2622 *** etc.
2623
2624 * *PointerCell*, their relevant content is a (nested) APL sub-value.
2625 * *LvalCell*, their relevant content is a *Cell* pointer. These **Cell**s are
2626 used to implement "selective specification". A selective specification like
2627 *(2⍴1↓A)←B* starts with (all **Cell**s of *A*) the rightmost variable *A*,
2628 which is then more and more reduced (by *1↓* and *2⍴*) before the new
2629 value *B* can be assigned to the Cells that survive.
2630
2631 Instead of declaring the data members of Cells in the derived class (the
2632 normal approach, i.e. APL_Integers as member of IntCells, APL_Float members
2633 in FloatCells, etc.) they are declared as a union in the base Class Cell:
2634
2635 ----
2636 Cell.hh:
2637 ...
2638 /// A union containing all possible cell values for the different Cell types
2639 union SomeValue
2640 {
2641 Unicode aval; ///< for CharCell
2642 APL_Float_Base cval[2]; ///< for ComplexCell
2643 ErrorCode eval; ///< an error code
2644 APL_Integer ival; ///< for IntCell
2645 Cell *lval; ///< for LvalCell (selective assignment)
2646 ...
2647 };
2648 ----
2649
2650 This union ensures that all derived classes have the same size.
2651
2652 Now back to the Cell functions. We take dyadic *A + B* and monadic *+ B*
2653 as an example, all other scalar APL functions follow suit:
2654
2655 . Every scalar APL function is implemented in a separate associated class,
2656 derived from base *class ScalarFunction*. GNU APL uses the naming convention
2657 that the class name starts with *Bif_*, followed by the function arity
2658 (*F12_* for nomadic functions, *F2_* for purely dyadic functions).
2659 . The interpreter creates a single static instance of each function (such
2660 static instances are initialized by the compiler before main() is executed).
2661 The instance is always called *fun*, here *Bif_F12_PLUS::fun*. At the same
2662 time, a pointer *_fun* is created.
2663 . The single instance of the class is needed because the base class
2664 *Function* of class *ScalarFunction* has virtual functions (which is
2665 impossible for fully static classes). See <<_apl_functions, APL Functions>>
2666 below for details.
2667 . The *eval_XXX()* functions like *Bif_F12_PLUS::eval_AB()* are implemented
2668 in inline function calls to *ScalarFunction::eval_scalar_AB()* which takes
2669 the Cell function *Cell::bif_add* that distinguishes the behaviors of the
2670 (in total many) single instances of the classes derived from
2671 *ScalarFunction*.
2672 . The naming convention is that virtual *Cell* functions are
2673 *Cell::bif_YYY*.
2674 . In short: base class *ScalarFunction* is essentially an iterator over the
2675 ravels the value arguments provided, and the difference between the derived
2676 functions are handled at the Cell level by means of different Cell
2677 functions.
2678 . While this may look a little complicated at the first glance, it is fairly
2679 efficient at runtime and saves a lot of mindless work for the GNU APL
2680 designer.
2681 . To summarize the example:
2682
2683 ----
2684 ScalarFunction.hh:
2685 ...
2686 ///
2687 class Bif_F12_PLUS : public ScalarFunction
2688 {
2689 ...
2690 /// overloaded Function::eval_B().
2691 virtual Token eval_B(Value_P B) const
2692 { return eval_scalar_B(B, &Cell::bif_conjugate); }
2693
2694 /// overloaded Function::eval_AB().
2695 virtual Token eval_AB(Value_P A, Value_P B) const
2696 { return eval_scalar_AB(A, B,
2697 inverse ? &Cell::bif_add_inverse : &Cell::bif_add); }
2698 ...
2699 static Bif_F12_PLUS * fun; ///< Built-in function.
2700 static Bif_F12_PLUS _fun; ///< Built-in function.
2701 };
2702
2703 ----
2704
2705 === Class IndexExpr
2706
2707 Class *IndexExpr* is a collection of 0 or more **Value_P**s or elided
2708 indices, where the *Value_P* 0 denotes an _elided index_ (= all
2709 indices along an axis). *IndexExpr* objects are created and deleted by
2710 the prefix parser *Prefix..cc*. More precisely, a TOK_R_BRACK (for *]*),
2711 starts a new IndexExpr, a *TOK_SEMICOL* (for *;* append new values (axes) to
2712 an IndexExpr, and TOK_L_BRACK finalizes the creation of the *IndexExpr* .
2713 The next token (i.e. the token left of the *IndexExpr*) then calls
2714 the appropriate function (such as *Value::index()* or
2715 *Symbol::assign_indexed()* and deletes the *IndexExpr* again.
2716
2717
2718 === Classes Bif_XXX and Quad_XXX
2719
2720 APL offers a rather large number of primitives. In GNU APL, every primitive
2721 is implemented in its own class and according to the following rules:
2722
2723 * The class name has a prefix that indicates the arity of the primitive and
2724 is one of:
2725 ** *Bif_F0* for niladic primitives; there is only one: *Bif_F0_ZILDE* (for ⍬),
2726 ** *Bif_F1_* for strictly monadic primitives; there is only one:
2727 **Bif_F1_EXECUTE* (for ⍎),
2728 ** *Bif_F2_* for strictly dyadic primitives,
2729 ** *Bif_F12_* for strictly nomadic primitives,
2730 ** *Bif_OPER1_* for monadic operators,
2731 ** *Bif_OPER2_* for dyadic operators, and
2732 ** *Quad_* for system functions. These are derived from class *QuadFunction*,
2733 primarily for grouping purposes. Note that the *Quad_* is also used for
2734 system variables. Similar to primitives, system functions with a large
2735 footprint have their own *.hh* and *.cc* files, while the remaining ones
2736 are collected in *QuadFunction.hh/QuadFunction.cc*.
2737 * classes with a large code footprint have their own implementation files
2738 (followed by *.hh* or *.cc*), where the filename is the class name,
2739 * the remaining classes (with a small code footprint) are declared/implemented
2740 in files *Primitivefunction.hh/Primitivefunction.cc*
2741 * Every class is, directly or indirectly, derived from base class *Function*.
2742 Class *FunctionC* defines all *virtual eval_XXX()* so that they thow a
2743 *VALENCE_ERROR*.
2744 * Every class then overrides (only) those *virtual eval_XXX()* whose
2745 signatures it supports. For example, the strictly monadic primitive ⍎
2746 (execute) overrides *virtual eval_B()*, the strictly dyadic primitive ⌷
2747 overrides *virtual eval_AB()*. Most primitives are nomadic and therefore
2748 override (at least) *virtual eval_B()* _and_ *virtual eval_AB()*. With this
2749 technique arity mismatches between the runtime parser and the supported
2750 signatures of a function (for example: the parser calls the stricly dyadic
2751 function ≠ monadically) are resolved without any runtime overhead.
2752 * Due to the *virtual eval_XXX()* functions, every class needs a single
2753 (class static) instance which is called *fun* and every such instance of
2754 *fun* has a (static) pointer named *_fun* pointing to it.
2755
2756 Except for the APL name (i.e. a single APL character for APL primitives and
2757 APL character ⎕ followed by 0 or more letters for APL system functions)
2758 there is no major difference between APL primitives and APL system functions.
2759 The different names are handled in *Tokenizer.cc*; the other noteworthy
2760 difference is that _all APL primitives_, but only a rather small _subset of
2761 APL system functions_ (and, for that matter, _system variables_) were
2762 standardized in the ISO standard for APL2.
2763
2764 === Symbols
2765
2766 A symbol identifies an APL object created by the user, i.e. a defined
2767 function or a user defined variable. In GNU APL, system functions (⎕-functions,
2768 e.g. ⎕FX) are _NOT_ symbols but *APL primitives*. The commonality between
2769 ⎕-functions and APL primitives is greater than the similarity
2770 between ⎕-variables and ⎕-functions. The only noteworthy difference between
2771 APL primitives and ⎕-functions is their name and the fact that the
2772 APL primitives are defined in the APL standard, while most ⎕-functions
2773 and ⎕-variables are not. They are used by APL interpreter providers to extend
2774 their functionality (and to lock-in their customers). The Cpp class hierarchy
2775 in GNU APL (excerpted, the full picture is shown in the .png files) are:
2776
2777 ----
2778 html/classSystemVariable__inherit__graph.png:
2779
2780 ┌─────────────┐
2781 │ NamedObject │
2782 └─────────────┘
2783 ↑
2784 ┌────────┐
2785 │ Symbol │
2786 └────────┘
2787 ↑
2788 ┌────────────────┐
2789 │ SystemVariable │
2790 └────────────────┘
2791 ↑
2792 ┌───────────────────┐
2793 │ NL-SystemVariable │
2794 └───────────────────┘
2795 ↑
2796 ╔═══════════════════╗
2797 ║ RO-SystemVariable ║
2798 ╚═══════════════════╝
2799 ----
2800
2801 and:
2802
2803 ----
2804 html/classFunction__inherit__graph.png:
2805
2806 ┌─────────────────────────────────┐
2807 │ NamedObject │
2808 └─────────────────────────────────┘
2809 ↑ ↑
2810 ┌────────────────────────────────────┐ ┌────────┐
2811 │ Function │ │ Symbol │
2812 └────────────────────────────────────┘ └────────┘
2813 ↑ ↑ ↑
2814 ┌─────────────────────────────────────────────────────┐ ┌──────────────┐
2815 │ PrimitiveFunction │ │ UserFunction │
2816 └─────────────────────────────────────────────────────┘ └──────────────┘
2817 ↑ ↑ ↑ ↑
2818 ╔══════════════╗┌────────────────┐┌───────────────────┐ ┌───────┐
2819 ║ QuadFunction ║│ ScalarFunction ││ NonscalarFunction │ │ Macro │
2820 ╚══════════════╝└────────────────┘└───────────────────┘ └───────┘
2821 ----
2822
2823 Some explanations might be helpful:
2824
2825 * the common base class *NamedObject*:
2826 ** provides *virtual UCS_string get_name()* to obtain the name of the object,
2827 ** *virtual const Function * NamedObject::get_function()* returns a
2828 valid *Function ** for functions, otherwise 0,
2829 ** *virtual Symbol * NamedObject::get_symbol()* returns a valid *Symbol ** for
2830 symbols, otherwise 0.
2831 * **SystemVariable**s are variables like *⎕IO*, *⎕FC*, ...
2832 * **NL_SystemVariable**s are **N**on-**L**ocal system variables (for which
2833 localizing is permitted, but has no effect): *⎕L*, *⎕R*, ...
2834 * **RO_SystemVariable**s are **R**ead-**O**nly global system variables
2835 (for which localizing makes no sense): *⎕AI*, *⎕ARG*, ...
2836 * base class *Function* defines default behavior of (*virtual eval_B()*,
2837 *eval_XB()*, *eval_AB()*, *eval_AXB()* ...). The default behavior is to
2838 throw a *VALENCE ERROR*, and derived classes simply overload the eval_XXX()
2839 functions that they implement.
2840 * *QuadFunction*, *ScalarFunction*, and *NonscalarFunction* are groupings
2841 that simplify the implementation. For example, all scalar functions are
2842 implemented in the same way and only differ by their details at the Cell
2843 level.
2844 * **UserFunction**s are the only functions that are also Symbols (so that
2845 their name appears in the symbol table. The system functions get their
2846 name via their ID.
2847 * *Macro* is a *UserFunction* that is defined and can only be used by the
2848 interpreter itself. It cannot be called from APL programs and simplifies
2849 built-in operators when they are called with *UserFunction* arguments
2850 considerably.
2851
2852 Symbols are created when the tokenizer detects a name for the first time
2853 *SymbolTable::lookup_symbol()*, *SymbolTable::lookup_existing_symbol()*,
2854 and *SymbolTable::add_symbol()*. Every symbol has a stack
2855 *Symbol::value_stack* of **ValueStackItem**s, which is pushed when the
2856 symbol is localized (at the beginning of a defined function) and popped
2857 when the execution of the defined function ends. The *ValueStackItem* at the
2858 top of the *Symbol::value_stack* defines the role (scope) that the symbol
2859 currently has. The possibilities are:
2860
2861 ----
2862 NamedObject.hh:
2863
2864 enum NameClass
2865 {
2866 NC_INVALID = 0x0100, ///< invalid name class.
2867 NC_UNUSED_USER_NAME = 0x0200, ///< unused user name, not yet assigned
2868 NC_LABEL = 0x0401, ///< Label.
2869 NC_VARIABLE = 0x0802, ///< (assigned) variable.
2870 NC_FUNCTION = 0x1003, ///< (defined) function.
2871 NC_OPERATOR = 0x2004, ///< (defined) operator.
2872 NC_SYSTEM_VAR = 0x4005, ///< system variable.
2873 NC_SYSTEM_FUN = 0x8006, ///< system function.
2874 NC_case_mask = 0x00FF, ///< almost ⎕NC
2875 NC_bool_mask = 0xFF00, ///< for fast selection
2876
2877 NC_FUN_OPER = (NC_FUNCTION | NC_OPERATOR) & NC_bool_mask,
2878 NC_left = (NC_VARIABLE |
2879 NC_UNUSED_USER_NAME |
2880 NC_SYSTEM_VAR |
2881 NC_INVALID // ⎕, ⍞, ⎕xx
2882 ) & NC_bool_mask
2883 };
2884 ----
2885
2886 The *NameClass* is equally well suited for C/Cpp *switch* statements (by using
2887 the lower byte) and for testing groups of **NameClass**es (by using the upper
2888 byte). After the tokenization (or localization) of a symbol it has the
2889 NameClass *NC_UNUSED_USER_NAME*; this changes to e.g. *NC_VARIABLE* when a
2890 value is assigned to the symbol, or to *NC_FUNCTION* when a defined function
2891 with the name of the symbol is defined with *⎕FX* or the ∇-editor.
2892
2893 The actual role of a user defined symbol can change over time, while the role
2894 of a system name is fixed and cannot be changed. E.g. *⎕IO* is always a
2895 variable and *⎕UCS* is always a function.
2896
2897 === Classes SymbolTable and SystemSymTab
2898
2899 Every Symbol is contained in one of two symbol tables:
2900
2901 * User-defined symbols are stored in a static instance of class *SymbolTable*,
2902 while
2903 * system defined symbols (for system functions and system variables) are
2904 stored in a static instance of class *SystemSymTab*.
2905
2906 Both symbol tables are contained in the base class *Workspace_0* of the
2907 static instance *Workspace::the_workspace*. The classes *SymbolTable* and
2908 *SystemSymTab* have a lot in common, but also differences. The common
2909 functionality is implemented in their template base class *SymbolTableBase*:
2910
2911 ----
2912 SymbolTable.hh:
2913 ...
2914 /// common part of user-defined names and distinguished names
2915 template <typename T, size_t SYMBOL_COUNT>
2916 class SymbolTableBase
2917 {
2918 ...
2919 };
2920 ----
2921
2922 The differences are:
2923
2924 * the table size (256 entries for *SystemSymTab* and 65536 entries for user
2925 defined names (constant *SYMBOL_HASH_TABLE_SIZE* in file *SystemLimits.def*
2926 * On success the lookup of a user defined name returns a *Symbol **,
2927 while a lookup of a system name returns a *SystemName **. Symbols are
2928 somewhat more complicated than SystemName because their role (like function
2929 or variable) can change over time while every SystemName has a fixed role
2930 (either function or variable) cannot. Also, every SystemName has a unique
2931 Id (defined in Id.def) while _all_ user defined symbols have the same Id
2932 named *ID_USER_SYMBOL*.
2933 * In a way **SystemName**s are more lightweight versions of **Symbol**s.
2934 * Symbol lookup. A lookup function has a single UCS_string argument with the
2935 name of a symbol. It returns a valid pointer on success and 0 otherwise.
2936 ** The base class *SymbolTableBase* has a lookup function
2937 *SymbolTableBase::lookup_existing_symbol()* which returns a valid (non-zero)
2938 pointer.
2939 ** The derived class *SymbolTable* has another lookup function
2940 *SymbolTable::lookup_symbol()* which always succeeds. Instead of returning
2941 0 to indicate that a given symbol name is not in the table, it creates a
2942 new symbol with the name given.
2943 ** In contrast, class *SystemSymTab* has functions *add_function()* and
2944 *add_variable()* to add system functions and system varibles (whose role
2945 is, unlike for user defined names, implied by their Id).
2946 * Both tables use a hash function *SymbolTableBase::function compute_hash()*
2947 to determine the position of a name in the table, from which a linked
2948 list of colliding names starts.
2949 * Erased names are not removed from a symbol table, but rather marked erased
2950 in the Symbol itself, while the symbol name remains in the table. This is to
2951 avoid searching for a user defined symbol in all existing tokens. Also, a
2952 symbol name could be )ERASEd at the top level but still exist as the name of
2953 a local in some defined function.
2954
2955 The lookup of (and possibly the insertion of a new) Symbol uses the following
2956 algorithm (*SymbolTable::lookup_symbol(const UCS_string & sym_name)*):
2957
2958 . compute a hash value from *sym_name*
2959 . if *symbol_table[hash]* is *0* then the name is the first symbol with that
2960 hash (unsuccessful lookup case 1.)
2961 .. Create a *new Symbol* with the name *sym_name*,
2962 .. Store the new symbol in *symbol_table[hash]*, and
2963 .. return the new symbol.
2964 . Otherwise one or more symbols with the same hash already exists and the
2965 name may or may not already exist in the symbol table.
2966 .. Chase the linked list from *symbol_table[hash]* to its end (via pointer
2967 *Symbol::next*).
2968 .. If a symbol with name *sym_name* is detected on the way then return that
2969 symbol (successful lookup).
2970 . Otherwise *sym_name* was not in the table. Chase the linked list again.
2971 .. If a symbol is detected on the way with:
2972 ... an empty value stack, or
2973 ... a value stack with 1 item and name class *NC_UNUSED_USER_NAME*,
2974 ... then re-initialize that symbol with a new name *sym_name* and return the
2975 symbol (unsuccessful lookup case 2). The condition 4.a.i. or ii. is
2976 returned by *Symbol::is_erased()*.
2977 . Otherwise (unsuccessful lookup case 3), the linked list contains no erased
2978 symbols that could be re-used. Append a new Symbol at the end of a list,
2979 like in (unsuccessful lookup case 1.) above.
2980
2981 This algorithm
2982
2983 * avoids unnecessary creation of new symbols by re-using formerly erased
2984 symbols (step 4.a.i above), and
2985 * avoids unnecessary removals and insertions into the linked list by not
2986 removing symbols that are (temporarily) not used, e.g. after an )ERASE
2987 command.
2988
2989 The case 4.a.i is not (or no longer) supposed to happen since all Symbol
2990 constructors now *push()* an item with name class *NC_UNUSED_USER_NAME* onto
2991 the Symbol's value stack and the *pop()* function asserts if the last item
2992 of the value stack would be removed,
2993
2994 The primary user of the symbol tables is the tokenizer (which translates human
2995 readable names into **Symbol**s. The vast majority of symbol table lookups
2996 occur when APL code is tokenized (∇-editor, ⎕FX) along with only a few system
2997 functions (those that use variable or function names or APL code strings at
2998 runtime).
2999
3000
3001 === Executables
3002
3003 Every APL input line is first tokenized, and the result of this tokenization
3004 is an *Executable*. The primary content of any *Executable* is a *TokenString*
3005 named *body*:
3006
3007 ----
3008 Token.hh:
3009
3010 class Token_string : public std::vector<Token> { ... }
3011
3012 Executable.hh:
3013
3014 // Base class for ExecuteList, StatementList, and UserFunction
3015 class Executable
3016 {
3017 ...
3018 Token_string body;
3019 ...
3020 }
3021 ----
3022
3023 The rest of class *Executable* are helper functions that support the
3024 execution of the raw *body*.
3025
3026 There are 3 cases where **Executable**s are produced (in order of decreasing
3027 relevance):
3028
3029 . The definition of a defined function, either interactively with the
3030 ∇-editor, or programmatically in APL with *⎕FX*.
3031 . The evaluation of a single input line in immediate execution, and
3032 . The evaluation of an APL string with APL primitive ⍎ (aka. Execute).
3033
3034 For each of these 3 cases (which also correspond to the *ParseMode* mentioned
3035 above), a corresponding class for that case is derived:
3036
3037 ----
3038 Executable.hh:
3039 ...
3040 class UserFunction : public Function, public Executable { ... }
3041 class StatementList : public Executable { ... }
3042 class ExecuteList : public Executable { ... }
3043 ....
3044 ----
3045
3046 In some debug outputs, as well as in some commands and in ⎕SI, the derived
3047 class of a particular *Executable* is displayed as a single character like
3048 this:
3049
3050 * class UserFunction: ∇
3051 * class StatementList: ◊
3052 * class ExecuteList: ⍎
3053
3054 Each of a derived class has a static function *fix()* which creates an
3055 instance of that class. The *fix()* function acts as a constructor for
3056 the derived class. Unlike a normal constructor (which either returns a
3057 valid object of the class or else throws an execption, the *fix()* function
3058 returns 0 if the construction fails (typically due to some SYNTAX ERROR in
3059 the input line(s) passed to it. The *fix()* functon of class *UserFunction*
3060 is essentially the implementation of *monadic ⎕FX*, and is also called after
3061 the ∇-editor finalizes a function definition (trailing ∇).
3062
3063 The main differences between the 3 classes are:
3064
3065 [cols="<,^,^,^,^,^", options="header,autowidth"]
3066 |====
3067 | Derived Class | Number of lines | Statements/Line | Jumps/Labels +
3068 | Arguments | Result
3069 | ExecuteList | single line | one | no | no | yes
3070 | StatementList | single line | several | no | no | no
3071 | UserFunction ∇, ⎕FX | multiple lines | several | yes | yes | yes
3072 | UserFunction { ... } | single line | one | no | yes | yes
3073 |====
3074
3075 ==== Classes ExecuteList and StatementList
3076
3077 The execution of **ExecuteList**s and **StatementList**s is rather simple:
3078 the tokens of their body are intepreted from the start of the body to its end,
3079 no arguments can be passed to the body, no change of the execution with
3080 branches (→N), etc.
3081
3082 ==== Class UserFunction
3083
3084 Defined functions (class UserFunction) are far more complex. As can be seen
3085 above, class UserFunction inherits from the two classes *Function* and
3086 *Executable*.
3087
3088 The inheritance from *Function* overrides its various virtual *eval_XXX()*
3089 functions, so that a defined function can be called like an APL primitive,
3090 The arity of a defined function (monadic, dyadic, operator, etc.) is
3091 determined by the function header and since class UserFunction cannot "know"
3092 it before the header is parsed, it must overload all possible virtual
3093 *eval_XXX()* declared in base class *Function*.
3094
3095 The inheritance from *Executable* provides the construction of the body
3096 (tokenization of the function lines (in class *Tokenizer*), pre-parsing (in
3097 class *Parser*), and some optimizations (also in class *Parser*).
3098
3099 There are two aspects of class *UserFunction* that are not considered in
3100 either of its base classes:
3101
3102 * Local variables, and
3103 * Branches (→N)
3104
3105 These aspects are implemented by means of two member variables:
3106
3107 * the variable *vector<Function_PC> UserFunction::line_starts* is a jump table
3108 that tells, for every function line N, which token is the start of line N
3109 in the (linear) body of the executable. For an APL jump statement, say *→N*,
3110 *line_starts[N]* is the first token in line N and its execution simply
3111 continues at token *body[line_starts[N]]*.
3112 * when a defined function is called, its arguments (if any) are assigned
3113 to the formal arguments declared in the function header and the local
3114 variables in the header are pushed. This happens in member
3115 *UserFunction::UserFunction_header header*, which is a functional grouping
3116 of the somewhat large class *UserFunction*.
3117
3118 Let:
3119
3120 ----
3121 ∇Z←A SUM B;C;D
3122 Z←A + B
3123 ∇
3124 ----
3125
3126 The typical life-cycle of Userfunction SUM is then:
3127
3128 . The *Userfunction* named *SUM*, is created with the ∇-editor or with *⎕FX*
3129 (which calls *Userfunction::fix()*).
3130 . The APL pattern matching (*Prefix.cc*) detects a call of *SUM*,
3131 say pattern *3 SUM 42*.
3132 . The function is called:
3133 .. Symbols *Z*, *A*, *B*, *C*, and *D* are pushed (and become, at this
3134 point in time, temporarily undefined).
3135 .. The actual arguments *2* and *42* of *SUM* are assigned to the formal
3136 arguments *A* and *B* of *SUM*. that is, *A←3 ◊ B←42*; *C*, *D* and *Z*
3137 remain undefined.
3138 .. The *Executable::body* is executed. This computes *Z←45*; *Z* is now
3139 defined.
3140 . At some point in time *SUM* returns (either when the end of the body is
3141 reached, or the when execution is stopped explitly (e.g. *→0*).
3142 .. The current value of *Z* (if any) is set aside (and will later be
3143 returned to the caller).
3144 .. The Symbols *Z*, *A*, *B*, *C*, and *D* are popped again (restored).
3145 .. The pattern matched above (*3 SUM 42*) is replaced by formerly defined
3146 value of *Z* (i.e. *45*).
3147
3148
3149 === Class StateIndicator
3150
3151 An *Executable*, as described above, is a static object that is essentially
3152 the tokenization of some APL source code string(s). An Executable is created
3153 once and deleted if no longer needed. Between the creation and the deletion of
3154 an Executable it remains unchanged (aka. static). An Executable is therefore
3155 comparable to the object code (binary) of a compiled language.
3156
3157 To produce a result, an Executable must be _executed_. While the Executable
3158 itself remains unchanged, the different executions of the same Executable
3159 can have rather different results, e.g. an APL value in one execution and an
3160 error in another.
3161
3162 Every execution of an Executable is performed in a context which tracks the
3163 state and the progress of the execution. This context is an object of class
3164 *StateIndicator*. The complete execution of an Executable consists of the
3165 following principle steps:
3166
3167 . Creation of a new StateIndicator, then
3168 . Execution of the Tokens in the body of the executable, then
3169 . returning the result of the execution (if any) to the initiator of the
3170 execution, and finally
3171 . Destruction of the StateIndicator.
3172
3173 In step 2. above, the execution of an executable (the same or a different) is
3174 started, i.e. before the current execution has completed. To accomplish this,
3175 the different contexts of different executions, regardless of whether the
3176 execution concerns the same Executable (direct recursion) or different ones
3177 (function call, possibly indirect recursion), are organized as a stack, known
3178 as the _)SI stack_. In GNU APL the )SI stack is a singly-linked list of
3179 StateIndicator objects, the link between adjacent StateIndicator objects
3180 in the )SI stack is member *StateIndicator::parent*.
3181
3182 The constructor of StateIndicator has two arguments: the executable to be
3183 executed and the parent that has initiated the execution:
3184
3185 ----
3186 StateIndicator.hh:
3187 ...
3188 /// constructor
3189 StateIndicator(const Executable * exec, StateIndicator * _par);
3190 ...
3191 ----
3192
3193 The constructor initializes *StateIndicator::parent*, which does not change
3194 thereafter. Since the )SI stack is a linked list, it can be represented as a
3195 single pointer to the most recent StateIndicator object. This pointer is
3196 stored in class *Workspace*:
3197
3198 ----
3199 Workspace.hh:
3200 ...
3201 /// the SI stack. Initially top_SI is 0 (empty stack)
3202 StateIndicator * top_SI;
3203 ----
3204
3205 The full picture is something like this:
3206
3207 ----
3208 ╔═══ Workspace ═══╗ ╔═════ StateIndicator ═══╗
3209 ║ ┌──────┐ ║ ║┌──────┐ ║
3210 ║ │top_SI├─╫─ → ─╢│ 0 │ ║ (latest )SI entry)
3211 ║ └──────┘ ║ ║└──────┘ ║
3212 ╚═════════════════╝ ╚╤═══════════════════════╝
3213 ↑
3214 ╔═══╪═ StateIndicator ═══╗
3215 ║┌──┴───┐ ║
3216 ║│parent│ ║
3217 ║└──────┘ ║
3218 ╚╤═══════════════════════╝
3219 ↑
3220 ...
3221 ↑
3222 ╔═══╪═ StateIndicator ═══╗
3223 ║┌──┴───┐ ║
3224 ║│parent│ ║
3225 ║└──────┘ ║
3226 ╚╤═══════════════════════╝
3227 ↑
3228 ╔═══╪═ StateIndicator ═══╗
3229 ║┌──┴───┐ ║
3230 ║│parent│ ║ (oldest )SI entry)
3231 ║└──────┘ ║
3232 ╚════════════════════════╝
3233 ----
3234
3235 By and large the only active StateIndicator is the topmost one. The
3236 StateIndicators below it are relatively passive and only come back
3237 to life when the topmost StateIndicator, sometimes referred to as *TOS*
3238 (for **T**op **O**f **S**tack) has finalized step 4. above. An error in the
3239 execution of TOS normally does not end it, but another StateIndicator is
3240 pushed (with mode immediate execution) onto the stack. The only cases that
3241 remove (pop) one or more items from the SI stack are:
3242
3243 * the executable in TOS reaches the end of the body of its Executable.
3244 This is the normal case,
3245 * the user issues )SIC command (in immediate execution mode). This clears
3246 the entire )SI stack,
3247 * the executable in TOS performs a → statement (aka. Escape), which rolls back
3248 the stack until the pop'ed StateIndicator was an Executable with mode
3249 immediate execution. That Executable was the one pushed above (i.e. due to
3250 an error). This pops the topmost item(s) until the TOS is an immediate
3251 execution context,
3252 * the execution of TOS had an error and TOS was under the control of
3253 ⎕EA, ⎕EB, or ⎕EC. This pops the topmost item(s) until TOS has the
3254 ⎕EA, ⎕EB, or ⎕EC that catches the error (as opposed to the normal
3255 error handling which would have pushed another StateIndicator onto
3256 the stack rather than popping items off it).
3257
3258 The TOS is needed in many different situations, therefore class *Workspace*
3259 provides, for convenience, a number of static wrapper functions that access
3260 frequently used members of its *top_SI*.
3261
3262 NOTE: Strictly speaking the _APL )SI stack_ refers to the entire linked
3263 list of contexts, i.e. to *Workspace::top_SI*. In GNU APL, though, the
3264 StateIndicator class implements an individual entry in that linked list.
3265
3266 The Class has two more members of interest:
3267
3268 ----
3269 StateIndicator.hh:
3270 ...
3271 /// details of the last error in this context.
3272 Error error;
3273
3274 /// the current-stack of this context.
3275 Prefix current_stack;
3276 ...
3277 ----
3278
3279 *StateIndicator::error* contains the error information (if any) for the
3280 StateIndicator, e.g. for ⎕EM. There can be several StateIndicators on the
3281 stack that were (temporarily) suspended and can be continued later
3282 (by some →N back into the failed Executable and therefore information on
3283 several errors may be present in the different StateIndicator objects.
3284
3285 *StateIndicator::current_stack* is far more interesting. It manages
3286 the inner loop that runs along the body of the Executable of the
3287 StateIndicator. See below.
3288
3289
3290 === Class Prefix
3291
3292 Class *Prefix* is an iterator over the body of an Executable. Its most
3293 important member is a stack named *content*:
3294
3295 ----
3296 Prefix.hh:
3297
3298 ...
3299 /// put pointer (for the next token at PC). Since content is a stack,
3300 /// its put position is also its size.
3301 int put;
3302
3303 /** the lookahead tokens (tokens that were shifted but not yet reduced).
3304 \b content is in body order, that is, content[0] is the oldest
3305 (= rightmost in APL order) token and content[put - 1] is the latest.
3306 **/
3307 Token_loc content[MAX_CONTENT];
3308 ...
3309 /// one phrase in the phrase table
3310 struct Phrase
3311 {
3312 const char * phrase_name; ///< phrase name
3313 const char * reduce_name; ///< reduce function name
3314 void (Prefix::*reduce_fun)(); ///< reduce function
3315 unsigned int phrase_hash; ///< phrase hash
3316 int prio; ///< phrase priority
3317 int misc; ///< 1 if MISC phrase
3318 int phrase_len; ///< phrase length
3319 uint8_t sub_nodes[TC_MAX_PHRASE+1]; ///< parent nodes
3320 };
3321 ----
3322
3323 Member *Prefix::content* is by and large processed as follows:
3324
3325 . The constructor *Prefix::Prefix()* starts with an empty stack.
3326 . If the stack starts with a valid phrase, then:
3327 .. The function *Phrase::reduce_fun* in the phrase is called;
3328 .. The *reduce_fun()* is a non-static member of class *Prefix* and can
3329 therefore access the content in order to produce a result.
3330 The *reduce_fun()* has no arguments because accessing *content* directly
3331 is far more efficient than using (Cpp) function arguments.
3332 .. The *reduce_fun()* will then:
3333 ... extract the relevant data from the tokens *Prefix::content*,
3334 remove (pop) the tokens from the *Prefix::content*, and
3335 ... push the result (if any) onto the *Prefix::content*.
3336 . Otherwise the stack does not start with a valid phrase. In this case
3337 the next *Token_loc* is fetched from the body of the *Executable*.
3338
3339 The following picture may illustrate the above (the entire algorithm is
3340 somewhat more complicated):
3341
3342 ----
3343 ╔══ StateIndicator::Executable->body ═════╗
3344 ║ ║
3345 ║ PC=0 ... PC=k-1 PC=k ... ║ PC is Prefix::PC
3346 ║┌────┐ ┌─────┐ ┌───┐ ┌───┐ ┌───┐ ║
3347 ║│ T0 │ ... │ Tₖ₋₁│ │ Tₖ│ │ T │ │ T │ ... ║ body
3348 ║└────┘ └─────┘ └─┬─┘ └───┘ └───┘ ║
3349 ╚═════════════════════│═══════════════════╝
3350 │
3351 ↓ Prefix::push_next_token()
3352 │
3353 ╔═══│══ Prefix::content ═════════╗
3354 ║ ┌─┴─┐┌─────┐ ┌─────┐ ┌───┐ ║
3355 ┌─── → ───│ Tₖ││ Tₖ₋₁│ │ Tₖ₋₂│ │ T │ ... ║
3356 │ ║ └─┬─┘└──┬──┘ └──┬──┘ └───┘ ║
3357 │ ╚═══│═════│═══════│══════════════╝
3358 │ │ │ │
3359 ↑ at0() at1() at2()
3360 │ │ │ │
3361 │ ┌─┴─────┴───────┴─┐
3362 │ │ reduce_XXX() │ i.e. (*Phrase::reduce_fun)()
3363 │ └───────┬─────────┘
3364 │ │
3365 └──── result ─────┘
3366 Prefix::pop_args_push_result(result)
3367 ----
3368
3369 Apart from *Prefix::content*, Prefix has the following members of interest
3370 (the others just helpers that make the code more readable):
3371
3372 * The Functions *Prefix::at0()*, *Prefix::at1()*, *Prefix::at2()*, and
3373 *Prefix::at3()* are primarily used by the different
3374 **Phrase::reduce_fun**s in order to access the (up to) 4 leftmost items
3375 in *Prefix::content*. The phrases have different lengths (from 1 to 4)
3376 and the matching of a phrase guarantees that sufficiently many
3377 **Token_loc**s exist on the stack. It is important to note that, although
3378 the body of the *Executable* is in reversed order as explained earlier,
3379 at0(), at1(), at2(), at3() are in APL order (to make the code easier to
3380 understand). For example the items in phrase *A + B* are:
3381 ** at0() ←→ *A*,
3382 ** at1() ←→ *+*, and
3383 ** at2() ←→ *B*.
3384
3385 * Put differently, *Prefix::content*, has a "hot end" that is manipulated
3386 with *Prefix::push_next_token()* and the various *reduce_XXX()* functions and
3387 a "cold end" containing tokens that are put on ice for a while.
3388
3389 * *Prefix::PC* is the **P**rogram **C**ounter. The APL interpreter can be
3390 considered as a (lightweight) virtual machine whose opcodes are Tokens
3391 and whose program(s) are lists of Tokens (= **Executable**s). In this
3392 model *PC* is the program counter of the virtual machine.
3393 ** The excution of an executable starts with PC=0 (= start of the body)
3394 in constructor *Prefix::Prefix()*.
3395 ** Whenever a new *Token_loc* is needed (in Step 3. above) then the new
3396 *Token_loc* is: *Token_loc(body[PC], PC)* and PC is incremented.
3397 ** The execution is complete when *PC == body.size()* (or after *→0* in defined
3398 functions).
3399
3400 * **saved_MISC**: many APL functions are _nomadic_, which means that they
3401 can be called monadically or dyadically. This includes _most_ APL primitives
3402 and _all_ non-niladic defined functions.
3403 ** There is a fixed set of 'MISC' tokens (more precisely: **TokenClass**es)
3404 that cause a nomadic function to be evaluated monadically: ← → [ ◊ F C M
3405 and (.
3406 ** All phrases that start with a *MISC* token (and differ only by that token)
3407 use the same *Phrase::reduce_fun*. For example, the two APL statements
3408 *X←⌊1.5* and *-⌊1.5* will both first match phrase MISC_F_B. This is because
3409 - (aka. F) and ← are *MISC* tokens. Therefore both phrases will first
3410 compute *⌊1.5* in *Prefix::reduce_MISC_F_B_()* and result *1*.
3411 ** In contrast, in APL statement *2⌊1.5* the leftmost value *2* is NOT a *MISC*
3412 token and therefore *Prefix::reduce_A_F_B_()* will be called.
3413 ** Unfortunately the decision about whether *Prefix::reduce_MISC_F_B_()* or
3414 *Prefix::reduce_A_F_B_()* matches can only be made _after_ either *MISC*
3415 or *A* was fetched. IOW: this decision requires a lookahead of 1 token (and
3416 Prefix is therefore essentially a so-called LALR(1) parser). If the
3417 decision is in favor of *Prefix::reduce_A_F_B_()*, then everything is fine.
3418 However, for *Prefix::reduce_MISC_F_B_()* the *MISC* token is not used and
3419 must be considered somehow. The solution is to store the *MISC* token in
3420 Cpp variable *Prefix::saved_MISC*. Note that one cannot simply decrement
3421 the PC in order to _undo_ the fetching of the *MISC* token. Decrementing
3422 the PC looks much simpler at first glance, but would only work if the *MISC*
3423 token came directly from the body of the *Executable*.
3424 Sometimes, though, (defined function *F*, defined operator *M*,
3425 or complete index *C*) the *MISC* token is the result of a Symbol
3426 resolution (cases *F* and *M*) or even of a prior computation with
3427 side effects (case complete index *C*).
3428
3429 The following picture is a slightly more detailed version of the previous one:
3430
3431 ----
3432 ╔══ StateIndicator::Executable->body ═════╗
3433 ║ ║
3434 ║ PC=0 ... PC=k-1 PC=k ... ║ PC is Prefix::PC
3435 ║┌────┐ ┌─────┐ ┌───┐ ┌───┐ ┌───┐ ║
3436 ║│ T0 │ ... │ Tₖ₋₁│ │ Tₖ│ │ T │ │ T │ ... ║ body
3437 ║└────┘ └─────┘ └─┬─┘ └───┘ └───┘ ║
3438 ╚═════════════════════│═══════════════════╝
3439 ↓
3440 Prefix::saved_MISC │
3441 ┌────┐ │
3442 ┌───┤ Tₖ ├─ → ─┤ saved_MISC ≠ TOK_VOID, otherwise body[PC++]
3443 │ └─┬──┘ ↓ in: Prefix::push_next_token()
3444 │ │ │
3445 │ ↑ ╔═══│══ Prefix::content ═════════╗
3446 │ └──MISC──┤ ║
3447 │ ║ ↓ ║
3448 ↑ ║ ┌─┴─┐┌─────┐ ┌─────┐ ┌───┐ ║
3449 │ ┌─── → ───│ Tₖ││ Tₖ₋₁│ │ Tₖ₋₂│ │ T │ ... ║
3450 │ │ ║ └─┬─┘└──┬──┘ └──┬──┘ └───┘ ║
3451 │ │ ╚═══│═════│═══════│══════════════╝
3452 │ │ │ │ │
3453 │ ↑ at0() at1() at2()
3454 │ │ │ │ │
3455 │ │ ┌─┴─────┴───────┴─┐
3456 │ │ │ reduce_XXX() │ i.e. (*Phrase::reduce_fun)()
3457 │ │ └──────┬──┬───────┘
3458 │ │ │ │
3459 │ └──── result ────┘ │ in: Prefix::reduce_XXX()
3460 │ │ └─── pop_args_push_result()
3461 │ │
3462 └──── clear_MISC() ────┘ in: Prefix::reduce_A_XXX()
3463 but not in: Prefix::reduce_MISC_XXX()
3464 ----
3465
3466 === APL Functions
3467
3468 APL implements two types of functions:
3469
3470 * APL primitives (functions and operators) and system functions. They are
3471 defined by the interpreter itself and are implemented in Cpp, and
3472 * defined functions, coded in APL by the programmer.
3473
3474 Every function has a *signature* that defines the combination of arguments
3475 that the function can be called with. The total number of possible signatures
3476 is somewhat large, but a single function only implements a rather small subset
3477 of them and returns a *VALENCE ERROR* when the *Prefix* parser calls a
3478 function with a signature that the called function does not support. In GNU
3479 APL the signature is a bitmap of *signature atoms* where every atom
3480 corresponds to a possible position of an argument in a *Prefix* pattern.
3481 However, not all possible bitmaps are valid signatures (e.g. a function with
3482 a left argument but no right argument):
3483
3484 ----
3485 APL_types.hh:
3486 ...
3487 /// signature of a defined function
3488 enum Fun_signature
3489 {
3490 // signature atoms
3491 //
3492 SIG_NONE = 0, ///<
3493 SIG_Z = 0x01, ///< function has a result
3494 SIG_A = 0x02, ///< function has a left argument
3495 SIG_LO = 0x04, ///< operator left operand
3496 SIG_FUN = 0x08, ///< function (always set)
3497 SIG_RO = 0x10, ///< operator right operand
3498 SIG_X = 0x20, ///< RO has an axis
3499 SIG_B = 0x40, ///< function has a right argument
3500
3501 // operator variants
3502 //
3503 SIG_FUN_X = SIG_FUN | SIG_X, ///< function with axis
3504 SIG_OP1 = SIG_LO | SIG_FUN, ///< monadic operator
3505 SIG_OP1_X = SIG_OP1 | SIG_X, ///< monadic operator with axis
3506 SIG_OP2 = SIG_OP1 | SIG_RO, ///< dyadic operator
3507 SIG_LORO = SIG_LO | SIG_RO, ///< monadic or dyadic operator
3508
3509 // argument variants
3510 //
3511 SIG_NIL = SIG_NONE, ///< niladic function
3512 SIG_MON = SIG_B, ///< monadic function or operator
3513 SIG_DYA = SIG_A | SIG_B, ///< dyadic function or operator
3514
3515 // allowed combinations of operator variants and argument variants...
3516
3517 // niladic
3518 //
3519 SIG_F0 = SIG_FUN | SIG_NIL, ///< dito
3520
3521 SIG_Z_F0 = SIG_Z | SIG_F0, ///< dito
3522
3523 // monadic
3524 //
3525 SIG_F1_B = SIG_MON | SIG_FUN, ///< dito
3526 SIG_F1_X_B = SIG_MON | SIG_FUN_X, ///< dito
3527 SIG_LO_OP1_B = SIG_MON | SIG_OP1, ///< dito
3528 SIG_LO_OP1_X_B = SIG_MON | SIG_OP1_X, ///< dito
3529 SIG_LO_OP2_RO_B = SIG_MON | SIG_OP2, ///< dito
3530
3531 SIG_Z_F1_B = SIG_Z | SIG_F1_B, ///< dito
3532 SIG_Z_F1_X_B = SIG_Z | SIG_F1_X_B, ///< dito
3533 SIG_Z_LO_OP1_B = SIG_Z | SIG_LO_OP1_B, ///< dito
3534 SIG_Z_LO_OP1_X_B = SIG_Z | SIG_LO_OP1_X_B, ///< dito
3535 SIG_Z_LO_OP2_RO_B = SIG_Z | SIG_LO_OP2_RO_B, ///< dito
3536
3537 // dyadic
3538 //
3539 SIG_A_F2_B = SIG_DYA | SIG_FUN, ///< dito
3540 SIG_A_F2_X_B = SIG_DYA | SIG_FUN_X, ///< dito
3541 SIG_A_LO_OP1_B = SIG_DYA | SIG_OP1, ///< dito
3542 SIG_A_LO_OP1_X_B = SIG_DYA | SIG_OP1_X, ///< dito
3543 SIG_A_LO_OP2_RO_B = SIG_DYA | SIG_OP2, ///< dito
3544
3545 SIG_Z_A_F2_B = SIG_Z | SIG_A_F2_B, ///< dito
3546 SIG_Z_A_F2_X_B = SIG_Z | SIG_A_F2_X_B, ///< dito
3547 SIG_Z_A_LO_OP1_B = SIG_Z | SIG_A_LO_OP1_B, ///< dito
3548 SIG_Z_A_LO_OP1_X_B = SIG_Z | SIG_A_LO_OP1_X_B, ///< dito
3549 SIG_Z_A_LO_OP2_RO_B = SIG_Z | SIG_A_LO_OP2_RO_B, ///< dito
3550 };
3551 ...
3552 ----
3553
3554 There are 0x80 = 128 possible signature bitmaps of which 22 are valid.
3555
3556 The base class *Function* of all functions has a non-virtual function
3557 *get_signature()* which is computed from some virtual functions related to
3558 signature atoms:
3559
3560 ----
3561 Function.cc:
3562 ...
3563 un_signature
3564 Function::get_signature() const
3565 {
3566 int sig = SIG_FUN;
3567 if (has_result()) sig |= SIG_Z;
3568 if (has_axis()) sig |= SIG_X;
3569
3570 if (get_oper_valence() == 2) sig |= SIG_RO;
3571 if (get_oper_valence() >= 1) sig |= SIG_LO;
3572
3573 if (get_fun_valence() == 2) sig |= SIG_A;
3574 if (get_fun_valence() >= 1) sig |= SIG_B;
3575
3576 return Fun_signature(sig);
3577 }
3578 ----
3579
3580 System functions do not use signatures because their classes know the
3581 signatures that they support already at compile time. Defined functions
3582 are different because all are handled by the same class *UserFunction* even
3583 though the signatures of different functions are defined by the user in
3584 the function header and the signatures differ. The only class that cares
3585 about the signature (of its left function argument) is *Bif_OPER1_EACH*.
3586
3587 For every signature *XXX* that a function class supports it must overload
3588 the corresponding *eval_XXX()* function. In our example, primitive *+*
3589 supports monadic *+B* and dyadic *A+B*. It therefore overloads *eval_B()*
3590 and *eval_AB()*. Likewise the axis variant A[X] is overloaded with
3591 *eval_AB()* and then delegated to their companions in class *ScalarFunction*.
3592
3593 ----
3594 ScalarFunction.hh:
3595 ...
3596 class Bif_F12_PLUS : public ScalarFunction
3597 {
3598 ...
3599 virtual Token eval_B(Value_P B) const
3600 { return eval_scalar_B(B, &Cell::bif_conjugate); }
3601
3602 /// overloaded Function::eval_AB().
3603 virtual Token eval_AB(Value_P A, Value_P B) const
3604 { return eval_scalar_AB(A, B,
3605 inverse ? &Cell::bif_add_inverse : &Cell::bif_add); }
3606 ...
3607 }
3608 ----
3609
3610 NOTE: You may wonder what is the matter with *bif_add_inverse()*. Some
3611 primitives have an inverse function which, if present, can be used by the
3612 dyadic operator *⍣* (power operator, not to be confused with the power
3613 function *⋆*) for negative power arguments. The inverse of *A+B* is
3614 *A-B* because A = (A+B)-B. Most of the circular functions "A○B" have
3615 inverses but most others do not. The power operator is, for good reasons,
3616 neither defined in the ISO APL standard, nor in the IBM APL2 language
3617 reference, but implemented in GNU APL. Avoid it where possible.
3618
3619 To summarize the execution of APL functions:
3620
3621 . The Prefix parser matches a pattern, for example *A F B*.
3622 . The reduce function for the pattern A F B is *reduce_A_F_B()*.
3623 . The *Function ** in token *F* is e.g. *Bif_F12_PLUS::fun*.
3624 . The pattern also implies that the eval_AB() function of *F*, i.e.
3625 *Bif_F12_PLUS::fun->eval_AB(A, B)* shall be called in order to produce the
3626 reduction result.
3627 . *Bif_F12_PLUS::fun->eval_AB()* is in-lined and calls
3628 *ScalarFunction::eval_AB()* with argument *Cell::bif_add*. It returns
3629 some result Z.
3630 . The Prefix parser replaces *A F B* with *Z* which finalizes the execution of
3631 *A F B*.
3632
3633 All other derivates of class *Function* are executed in the same fashion.
3634
3635 ==== Important differences
3636
3637 An important difference between *ExecuteList*, *StatementList*, and
3638 *UserFunction* concerns the last token in their body. This token is not
3639 produced by the tokenizer (since there is no APL code for it), but by the
3640 corrsponding *fix()* function of the derived class. The last token
3641 determines if and how a value is returned to the caller of the executable:
3642
3643 [cols="<,^,^", options="header,autowidth"]
3644 |====
3645 | Executable Type | Final Token | Result
3646 | ExecuteList | TOK_RETURN_EXEC | APL Value
3647 | StatementList | TOK_RETURN_STATS | None
3648 | UserFunction w/o result | TOK_RETURN_VOID | None
3649 | UserFunction with result | TOK_RETURN_SYMBOL | APL Value (if assigned)
3650 |
3651 |====
3652
3653 === Class Nable
3654
3655 Class *Nable* implements the interactive function editor (for lack of a
3656 better name, sometimes referred to as the ∇-editor). The constructor
3657 *Nable::Nabla(const UCS_string & cmd)* starts the editor with the first
3658 editor command (which either creates a new function or else modifies an
3659 existing one). Every serious APL programmer knows the ∇-editor and its
3660 implementation is straightforward.
3661
3662 IBM APL2 defines the ∇-editor to be recursive (so one can start the editing
3663 of some other defined function while editing another defined function),
3664 this feature was 'not' implemented in the GNU APL ∇-editor.
3665
3666
3667 === Class Workspace
3668
3669 Class *Workspace* is a container that includes all objects that were
3670 created or modified by the user (through the execution of APL programs,
3671 APL commands, and/or APL expressions). These objects are:
3672
3673 * Defined functions,
3674 * User variables,
3675 * (The values of) System variables,
3676 * the symbol table, and
3677 * The state indicator, aka. _the SI stack_.
3678
3679 APL primitives are constant in nature therefore need not be stored in a
3680 workspace.
3681
3682 The APL interpreter has (only) one static *Workspace* instance named
3683 *Workspace::the_workspace*.
3684
3685 The *)SAVE* command serializes the binary *Workspace::the_workspace* into a
3686 human readable .xml file. The *)LOAD* or *)COPY* commands may later
3687 de-serialized a .xml workspace file back into the *Workspace::the_workspace*
3688 of another APL session. Many of the APL commands modify the state of
3689 *Workspace::the_workspace*. According to *Workspace.hh* the data relevant
3690 members of class *Workspace* are:
3691
3692 ----
3693 Workspace
3694 ╔═══════════════════════════════════╗
3695 ║ ┌─────────┐ ┌────────────┐ ║
3696 ║ │ WS_name │ │ APL prompt │ ║
3697 ║ └─────────┘ └────────────┘ ║
3698 ║ ║
3699 ║ ┌─────────────────┐ ║
3700 ║ ┌─┴───────────────┐ │ ║
3701 ║ │ System Variable ├─┘ ∘∘∘ ║
3702 ║ └─────────────────┘ ║
3703 ║ ║
3704 ║ ┌────────────────┐ ║
3705 ║ ┌─┴──────────────┐ │ ║
3706 ║ │ StateIndicator ├─┘ ∘∘∘ ║
3707 ║ └────────────────┘ ║
3708 ╚═══════════════════════════════════╝
3709 ----
3710
3711 As a matter of fact, class *Workspace* is derived from a simple container
3712 *Workspace_0* which contains 2 more items *symbol_table* and
3713 *distinguished_names*,
3714
3715 ----
3716 Workspace.hh:
3717
3718 class Workspace_0
3719 {
3720 protected:
3721 /// the symbol table for user-defined names of this workspace.
3722 SymbolTable symbol_table;
3723
3724 /// the symbol table for system names (aka. distinguished names) of
3725 /// this workspace.
3726 SystemSymTab distinguished_names;
3727 };
3728 ----
3729
3730 The idea between this distinction between base class *Workspace_0* and
3731 derived class *Workspace* is twofold:
3732
3733 . It ensures that the two symbol tables *symbol_table* (for user-defined
3734 names) and *distinguished_names* for system functions and system variables
3735 are properly initialized (to empty tables) so that the constructor of the
3736 derived class *Workspace* can simply add system functions and variables
3737 without needing to drain (clear) the tables first.
3738 . It separates the interpreter state produced by the user (and which is
3739 **)SAVE**d into a .xml file) from the interpreter state produced by the
3740 intialization of the interpreter itself. Since _system functions_ are
3741 constant in nature, they have no state related to them. Therefore the
3742 initial state of the interpreter is primarily the initial state of all
3743 system variables, for example after a *)CLEAR* command.
3744
3745
3746 === Class XML_Archive
3747
3748 The **)SAVE**ing or **)LOAD**ing of workspaces into or from resp. .xml files
3749 is a somewhat lengthy process. It therefore has its own implementation files
3750 *Archive.hh* and *Archive.cc*. Class *Workspace* is the only user of these
3751 classes. There are actually 3 classes:
3752
3753 * Class *XML_Archive* is the base class. It merely contains an
3754 *enum ArchiveSyntax* for verifying that the archive software versions of
3755 a **)LOAD**ed .xml file is compatible with the software version that
3756 **)SAVE**d the archive (and warns the user if not).
3757 * Derived class *XML_Saving_Archive* contains the functions for serializing
3758 a *Workspace* object into a file. Serializing means that the internal
3759 (binary) representation of a workspace is written into a (human readable)
3760 format from which it can later be de-serialized. IOW: class derived
3761 *XML_Saving_Archive* implements the *)SAVE* command.
3762 * Class *XML_Loading_Archive* contains the functions for de-serializing a
3763 *Workspace* object from the (human readable) format back to its internal
3764 (binary) representation. IOW: class *XML_Loading_Archive* implements the
3765 various *)LOAD* and *)COPY* commands for .xml files.
3766
3767 ==== Serialization (APL to XML)
3768
3769 The serialization is split into a small number of categories or _loops_.
3770 Each such loop iterates over the same kind of data structures in the
3771 workspace. To simplify the later de-serialization of a .xml file, the order
3772 of the different loops matters, while the order of items inside a loop is
3773 arbitrary. The loops are:
3774
3775 . loop over all defined functions, then
3776 . loop over all APL values, then
3777 . loop over all symbols, then
3778 . loop over user defined commands (a non-standard GNU APL feature), then
3779 . loop over )SI stack entries.
3780
3781 The de-serializer expects the XML tags to appear in the same order. The
3782 following table shows the mapping between Cpp types and XML tags (some
3783 trivial Cpp types were omitted):
3784
3785 [cols="<,<", options="header,autowidth"]
3786 |====
3787 | Cpp type
3788 | XML Tag(s) and attributes
3789 | Cell []
3790 | <Ravel vid="..." bytes="..."/>
3791 | Prefix
3792 | <Parser size="..." assign-pending="..."
3793 action="..." lookahead-high="..."> ... </Parser>
3794 | StateIndicator
3795 | <SI-entry level="..." pc="..." line="..."> Body </SI-entry>
3796 | Symbol
3797 | <Symbol name="..." stack-size="..."> Value Stack... </Symbol>
3798 | SymbolTable []
3799 | <SymbolTable size="..."> Symbols... </SymbolTable>
3800 | Token
3801 | <Token pc="..." tag="..." val="..." />
3802 | UserFunction
3803 | <Function vid="..."/> Body </Function>
3804 | UserCommand []
3805 | <Commands size="..."> Command... </Commands>
3806 | UserCommand
3807 | <Command name="..." mode="..." fun="..."/>
3808 rk="..." sh_0="...".../>
3809 | UCS_string
3810 | <UCS uni="..."/>
3811 | Value
3812 | <Value flg="..." vid="..." parent="..."
3813 |====
3814
3815 Some remarks:
3816
3817 * The XML tag corresponds to the Cpp type,
3818 * the tag attributes correspond to the data members of the Cpp type.
3819 To the extent possible, all data members are stored in a single tag (i.e.
3820 <TAG ... /> in XML) as opposed to start and end tags (i.e. <TAG ...> ...
3821 </TAG> in XML. The exceptions are Cpp classes of variable size (arrays,
3822 vectors, linked lists, etc.), whose items are serialized between the
3823 corresponding start and end tags,
3824 * empty vectors, etc., may be omitted.
3825
3826 Most Cpp types are mapped to XML in a straightforward fashion. The exceptions
3827 are described in more detail in the following.
3828
3829 ==== Serialization of APL Values
3830
3831 The serialization of APL Values is implemented with two different loops: one
3832 for the (typically large) ravel of the value, and one for the rest (i.e.
3833 shape, flags, etc.
3834
3835 In Cpp, objects refer to each other by their addresses in memory (aka.
3836 _pointers_ in C, and/or _references_ in Cpp). Even though one could, in
3837 theory, emulate pointers with file offsets, this would lead to a rather
3838 complicated implementation. Instead, GNU APL uses IDs that define relations
3839 between different objects in the serialization; the IDs thus replace pointers
3840 and/or references in Cpp.
3841
3842 The IDs are different *enum* types (so that the Cpp compiler can detect
3843 the use of incompatible pointers). The *enum Vid { ... }* is the ID that
3844 relates XML <Value .../> tags to the corresponding XML <Ravel .../> tag.
3845
3846 For example, Let:
3847
3848 ----
3849 )CLEAR
3850 )WSID TEST
3851
3852 Z←1 2 3
3853
3854 )SAVE
3855 ----
3856
3857 The )SAVE command serializes workspace TEST (into file TEST.xml) like this:
3858
3859 ----
3860 TEST.xml:
3861 ...
3862 <Ravel vid="15" cells="³1³2³3"/>
3863 ...
3864 <Value flg="0x400" vid="15" parent="-1" rk="1" sh-0="3"/>
3865 ...
3866 <SymbolTable size="1">
3867 <Symbol name="Z" stack-size="1">
3868 <Variable vid="15"/>
3869 </Symbol>
3870 </SymbolTable>
3871 ----
3872
3873 The serialization of the <Ravel> deserves some more explanation. As already
3874 explained, the *vid="15"* attribute of the <Ravel> tag links the ravel to
3875 the <Value with (the same) *vid="15"*. This information alone suffices to
3876 de-serialize the right side *1 2 3* of the assignment *Z←1 2 3*. However,
3877 the assignment to APL variable (aka. Symbol) *Z* has created a second tag
3878 *<Variable vid="15"/>* which links the (current) APL value *1 2 3* to symbol
3879 *Z*. In the above example *Z* is a global variable, therefore there is only
3880 one *<Variable ...>* tag between the *<Symbol>* ... *</Symbol>* tags.
3881 However, if the symbol *Z* were localized, then every localization would
3882 have added a new XML item between the *<Symbol>* ... *</Symbol>* tags.
3883
3884 Now, a "proper" XML would have serialized the ravel *1 2 3* as follows:
3885
3886 <Ravel vid="15">
3887 <Cell type="integer" value="1"/>
3888 <Cell type="integer" value="2"/>
3889 <Cell type="integer" value="3"/>
3890 </Ravel>
3891
3892 Since ravels tend to be rather long (so that Cells are frequent), the "proper"
3893 <Cell /> tags were optimized into a far more compact format which may
3894 be called *micro tags* (or *μ-Tags* ). A micro tag is a single Unicode
3895 character that defines the following properties and purposes that are
3896 related to (and later needed to de-serialize) a Cell:
3897
3898 * the Cpp Cell Type (CharCell, IntCell, FloatCell, ComplexCell, PointerCell,
3899 or LvalCell)
3900 * the Encoding used for the Cell value (only relevant for CharCell), and
3901 * to serve as a delimiter between adjacent Cells of the ravel.
3902
3903 The different encodings of CharCells are needed because XML has restrictions
3904 on the characters that are permitted in XML attributes and to abbreviate
3905 the most likely characters (i.e ASCII).
3906
3907 The following table lists the micro tags used:
3908
3909 [cols="^,<,<,<,>", options="header,autowidth"]
3910 |====
3911 |μ-Tag|Cpp Cell Type|Encoding |Example |Cells
3912 | ⁰ | CharCell | end of Unicode character sequence | ²Hello⁰ |≥ 1
3913 | ¹ | CharCell | sprintf("%X", ASCII-value) | ¹A (aka. LF)|1
3914 | ² | CharCell | start of Unicode character sequence| ²World⁰ |≥ 1
3915 | ³ | IntCell | integer (sequence of digits 0-9) | ³42 |1
3916 | ⁴ | FloatCell | sprintf("%.17g", value) | ⁴42.56 |1
3917 | ⁵ | ComplexCell | sprintf("%17gJ%17g", real, imag) | ⁵1.2J3.4 |1
3918 | ⁶ | PointerCell | integer (vid) | ⁶42 |1
3919 | ⁷ | LvalCell | sprintf("%d[%lld]", vid, offset) | ⁷42[2] |1
3920 | ⁸ | FloatCell | integer ÷ integer | ⁸2÷3 |1
3921 |====
3922
3923 All Cell types except CharCell use one tag per Cell and the Cell value extends
3924 from the first character after the μ-Tag to the character before the next
3925 μ-Tag. Since the number of ASCII characters in the Cell value is somewhat
3926 larger, the overhead for the μ-Tag is relatively small.
3927
3928 In contrast, CharCells contain one character and the μ-Tag tags for a string
3929 like "Hello" would require 5 bytes for the ASCII "Hello", plus 10 to 15 bytes
3930 for the 5 μ-Tags (since the Unicodes of the μ-Tags are UTF8-encoded, and most
3931 have 2 or 3 bytes per Unicode).
3932
3933 Therefore, and since APL characters more often occur in groups than as
3934 individual characters, the ²...⁰ values can span entire strings with only
3935 one start μ-Tag ² and one end μ-Tag ⁰. This is similar to APL where
3936 'Hello' is the same as 'H' 'e' 'l' 'l' 'o'.
3937
3938 ==== Serialization of UCS_strings
3939
3940 UCS_strings do not only appear as groups of characters in the ravels of APL
3941 values (as described above) but also in other contexts (e.g. the APL text
3942 that defines a defined function). For these cases, a common XML tag
3943 *<UCS uni="..."/>* is used; the value of the tag attribute *uni=* is encoded
3944 with μ-Tags ⁰, ¹, and ² as described above. For example. the APL function:
3945
3946 ----
3947 ∇Z←A DIV B
3948 Z←A÷B
3949 ∇
3950 ----
3951
3952 will be serialized as:
3953
3954 ----
3955 <Symbol name="DIV" stack-size="1">
3956 <Function fid="0x55BCF671DC80" creation-time="1687101368729013"
3957 exec-properties="0,0,0,0">
3958 <UCS uni="²Z←A DIV B⁰¹A
3959 ² Z←A÷B⁰¹A
3960 "/>
3961 </Function>
3962 </Symbol>
3963 ----
3964
3965 Note the *¹A* above, which is the ASCII line feed character *0x0A* (which
3966 is not allowed in a tag attribute value in XML).
3967
3968 ==== De-Serialization (XML to APL)
3969
3970 All the complexity above was motivated by the following design goals:
3971
3972 * **)SAVE**d workspaces should be resonably compact,
3973 * it should be possible to fix a broken workspace with a simple ASCII text
3974 editor such as vi or emacs, with only some basic knowledge of the XML
3975 syntax, and
3976 * the **)LOAD**ing and **)COPY**ing of workspaces (i.e. the decoding of XML
3977 files should be simple and, for portability and maintenance reasons, not
3978 depend on external libraries.
3979
3980 Almost every serialization function, say *save_XXX()*, in class *SavingArchive*
3981 has a corresponding de-serialization function *read_XXX()* in class
3982 *LoadingArchive*:
3983
3984 [cols="<,<,<", options="header,autowidth"]
3985 |====
3986 | SavingArchive | LoadingArchive | Cpp class (de-)serialized
3987 | save() | read_Workspace() | entire Workspace
3988 | save_Derived() | read_Derived() | DerivedFunction
3989 | save_functions() | - | UserFunction (all)
3990 | save_Function() | read_Function() | UserFunction (one)
3991 | save_Function_name() | read_Function_name() | (helper for UserFunction)
3992 | save_Parser() | read_Parser() | Prefix
3993 | save_Ravel() | read_Ravel() | Cell (all in a ravel)
3994 | save_shape() | - | Shape
3995 | save_SI_entry() | read_SI_entry() | StateIndicator
3996 | save_Symbol() | read_Symbol() | Symbol
3997 | save_symtab() | read_SymbolTable() | SymbolTable
3998 | save_token_loc() | read_Token() | Token
3999 | save_UCS() | read_UCS() | UCS_string
4000 | save_user_commands() | read_Commands() | Command::user_command []
4001 | save_vstack_item() | - | (helper for Symbol)
4002 |====
4003
4004 De-serialization (aka, decoding) is inherently more complex than
4005 serialization (aka, encoding). Therefore some more *read_XXX()* functions
4006 have no corresponding *save_XXX()* function.
4007
4008 == Parallel (Multi-Core) Execution
4009
4010 Parallel execution of APL has a longer history.
4011
4012
4013 === Background
4014
4015 In the early 1980s the author learned APL (after ALGOL, Assembler, and BASIC,
4016 and before C. Cpp was in its early days and not (yet) commercially available.
4017 The platform was an IBM 5110 desktop, a precursor to the IBM PC which came
4018 later. C compilers and APL interpreters were expensive and on the IBM 5110 was
4019 slow, particularly in comparison with Assembler or compiled languages like C
4020 on comparable platforms.
4021
4022 Shortly afterwards, the owner of the IBM 5110 replaced it with a faster 16-bit
4023 machine (a Motorola 68000 CPU with an APL 68000 interpreter [today named APL-X]
4024 with multi-user capabilities). APL performance was still an issue.
4025
4026 To address the performance issue, the author undertook the construction of a
4027 parallel APL computer. The first draft architecture was based on
4028 **Transputer**s, a brand new CPU technology at that time (which died out
4029 shortly after). The advantage of Transputers was that every CPU had 4 fast
4030 communication channels which could be connected to neighboring Transputers.
4031 The resulting topology is then a torus (a mesh with the leftmost Transputers
4032 connected to the corresponding rightmost Transputers and the top Transputers
4033 connected to the bottom Transputers):
4034
4035 ----
4036 4×4 Transputer Torus
4037
4038 ┌─────┐ ┌───┐ ┌───┐ ┌───┐
4039 │ ┌───────────────────────────────┐
4040 │ │ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ │
4041 │ └─╢ T ╟───╢ T ╟───╢ T ╟───╢ T ╟─┘
4042 │ ╚═╤═╝ ╚═╤═╝ ╚═╤═╝ ╚═╤═╝
4043 │ ┌─ │ │ │ │ ─┐
4044 │ │ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ │
4045 │ └─╢ T ╟───╢ T ╟───╢ T ╟───╢ T ╟─┘
4046 │ ╚═╤═╝ ╚═╤═╝ ╚═╤═╝ ╚═╤═╝
4047 │ ┌─ │ │ │ │ ─┐
4048 │ │ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ │
4049 │ └─╢ T ╟───╢ T ╟───╢ T ╟───╢ T ╟─┘
4050 │ ╚═╤═╝ ╚═╤═╝ ╚═╤═╝ ╚═╤═╝
4051 │ ┌─ │ │ │ │ ─┐
4052 │ │ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ ╔═╧═╗ │
4053 │ └─╢ T ╟───╢ T ╟───╢ T ╟───╢ T ╟─┘
4054 │ ╚═╤═╝ │ ╚═╤═╝ │ ╚═╤═╝ │ ╚═╤═╝
4055 └─────┘ └───┘ └───┘ └───┘
4056 ----
4057
4058 Another architecture that was initially considered was the Intel Hypercube.
4059 However, neither the Transputer torus nor the Intel Hypercube seemed to suit
4060 APL very well. We therefore decided to develop our own architecture named
4061 DATIS-P (derived from the first names of the students that developed the
4062 hardware and software developed for the DATIS-P and probably the last name
4063 of the author. The developers were (in DATIS-P order):
4064 **D**ieter Scheerer <<Sch>>,
4065 **A**ndreas Gergen <<Ger>>,
4066 **T**homas Mörsdorf <<Mör>>, and last but not least
4067 **I**na Gläs <<Glä>>.
4068 The DATIS-P was prepared for 256 CPUs, but for budgetary reasons our
4069 prototype had only 32 CPUs. The power consumption was about 50 Amperes
4070 at 5 Volts per CPU (which blew the fuses in our lab when we turned it on for
4071 the first time). The size was three 19-inch cabinets (roughly the size of
4072 a mainframe at that time).
4073
4074 The most challenging part of the DATIS-P was its communication network. Its
4075 structure was a 3-stage permutation network as invented by *Waksman*. Since
4076 no suitable technology existed at that time we developed an ASIC (a 1-bit wide
4077 8×8 crossbar; the network for 32 CPUs was 8-bit wide and was comprized of
4078 8-bit × 3 stages × 4 width = 96 such ASICs. The 3 stages were pipelined,
4079 a reconfiguration of the network to an arbitrary permutation of the inputs
4080 was done in parallel by all CPUs and took only 3 CPU instructions. The
4081 communication bandwith was 2 CPU instructions per byte (one MOVE.B instruction
4082 to write into the network and one MOVE.B to read the byte (written by some
4083 other CPU) back. The total bandwidth of the network of our 32-CPU machine was
4084 therefore (with a 16 MHz clock) ÷ (3 clocks per MOVE.B) ÷ (2 MOVE.B per
4085 transfer) = 2.6 MBytes/s or 21 MBits/s per CPU = 670 MBits/s for the entire
4086 network (a lot at that time). The bandwidth of the DATIS-P scales linearly
4087 with the number of CPUs, therefore a 256 CPU machine would have had a total
4088 communication bandwidth of 5.3 Gigabits/s.
4089
4090 The architecture of the DATIS-P is:
4091
4092 ----
4093 Entire DATIS-P One CPU
4094 ────────────── ───────
4095
4096 ┌──────────────────────────┐ network ┌───┐
4097 │ Permutation Network │ │ ┌─┤CP1│
4098 └──┬────────┬───────────┬──┘ ╔══════╧══════╗ │ └───┘
4099 │ │ │ ║ MC68020 CPU ╟─┤ ┌───┐
4100 ╔══╧══╗ ╔══╧══╗ ╔══╧══╗ ║ 16 MHz ║ ├─┤CP2│
4101 ║ CPU ║ ║ CPU ║ ... ║ CPU ║ ╚══════╤══════╝ │ └───┘
4102 ╚══╤══╝ ╚══╤══╝ ╚══╤══╝ │ │ ...
4103 │ │ │ ┌──────┴──────┐ │ ┌───┐
4104 └────────┴─┬─────────┘ │ static RAM │ └─┤CP8│
4105 │ │ 1 MByte │ └───┘
4106 ╔══╧══╗ └──────┬──────┘
4107 ║ CPU ║ │
4108 ╚═════╝ Master
4109 ----
4110
4111 An entire DATIS-P consists of:
4112
4113 * The permutation network,
4114 * 32 worker CPUs, and
4115 * one master CPU. This master CPU does the APL interpretation and delegates
4116 all ravel computations to the worker CPUs. To support scalar extensions
4117 like *1 + 2 3 4 5* ... the master was able to broadcast the scalar 1 into
4118 the dual port memories of the worker with a single instruction.
4119
4120 Every CPU of the DATIS-P:
4121
4122 * was a Mototola 68020 processor (the cutting edge when the development
4123 of DATIS-P started),
4124 * had up to 8 numerical co-processors MC 68881 to boost the floating point
4125 performance
4126 * A dual-port 1 MByte static memory; one port connected to the local CPU the
4127 other to the Master CPU.
4128
4129 The development of the hardware (PCB designs, ASIC design) and the software
4130 took from 1985 to 1989; the author was managing the hardware development
4131 and finished a Ph.D thesis about the parallel algorithms for the DATIS-P in
4132 2.00 <<Sau>>.
4133
4134 The primary conclusion of the thesis was:
4135
4136 ───────────────────────────────────────────────────────────────────────────────
4137
4138 On the DATIS-P architecture with P processors:
4139
4140 * All scalar APL functions can be computed in parallel with a speed-up
4141 of *O(P)*. That is, the performance of every scalar function scales linearly.
4142 * Most of the non-scalar APL functions can be computed in parallel with
4143 speed-up *O(P÷log P)*. That is, the other functions scale almost linearly.
4144 * The remaining non-scalar functions are those that require sorting.
4145 Their speed-up is *O(P÷log²P)* (using Batcher's Bitonic Sort).
4146 * There is one exception which may happen for particular index vectors *X* in
4147 the indexed assignment *A[X]←B*, in the indexed reference *A←B[X]*, and
4148 functions derived from them, e.g. *X/B*. If the index vector *X* is such
4149 that all ravel items of A are concentrated on the same worker CPU, then
4150 the speed-up can degrade down to *O(1)* because that worker CPU has to do
4151 all of the work while the others are idle. Usually, though, the speed-up
4152 is *O(P÷log²P)* i.e. like the sorting functions ⍋ and ⍒. These days one
4153 can use P-RAM machines that do not suffer from this problem, but in 2.00
4154 P-RAMs were not available.
4155
4156 ───────────────────────────────────────────────────────────────────────────────
4157
4158 The benchmarks perfomed on the DATIS-P essentially confirmed the predictions
4159 of the Ph.D. thesis. Since we had no APL interpreter at that time, we only
4160 implemented the most important parallel algorithms performed by the workers.
4161 The implementation languages were C on the master and Assembler on the workers.
4162
4163 These results were also submitted to the 2.00 APL conference in Copenhagen,
4164 Denmark. Without any feedback. The author therefore pursued a career in
4165 the telecommunications industry.
4166
4167 Around 2000, the author came across a PC demo version of IBM APL2 and
4168 played a little with it. However, the license cost for a full version
4169 was entirely out of range for a private user. At about the same time
4170 he worked with Unicode, UTF8-encodings and the like and discovered that
4171 all APL characters were available in Unicode. Probably at that time the
4172 idea of writing my own APL interpreter began to mature.
4173
4174 Around 2008, the first version of the interpreter was ready. It was not
4175 yet a GNU project and not very stable either.
4176
4177 In 2013 the interpreter was accepted by the GNU project and became GNU APL.
4178 Version 1.0 was sort of stable (i.e. it did not crash immediately), but still
4179 rather buggy (primarily suffering from memory leaks).
4180
4181 In 2014, multi-core support (parallel APL) was added. However, only the
4182 APL workhorses (i.e. scalar functions and their outer products) were
4183 parallelized and benchmarked. The results were somewhat disappointing
4184 and suggested that non-scalar functions will not gain much by parallization.
4185 They are memory bound (as opposed to the more compute bound scalar functions)
4186 The main reason seems to be that the interface between the CPU cores and
4187 the memory does not scale with the number of cores so that the cores are
4188 competing for memory access. In contrast, the DATIS-P had only local
4189 memories whose total bandwidth grows linearly with the number of CPUs.
4190
4191 === Implementation
4192
4193 WARNING: Parallel APL is a purely experimental feature that should not be used
4194 for production code. Expect crashes from time to time.
4195
4196 The details are described in a separate document *Parallel-APL.html*, which
4197 is shipped with GNU APL in the same directory as this document.
4198
4199 == Exercise 1
4200
4201 We conclude our journey through the GNU APL source code with a little exercise
4202 for the alert reader:
4203
4204 _Add a new monadic system function named *⎕FOO* to GNU APL. *⎕FOO* takes a
4205 1-item integer argument *B* and returns the APL value (string) "FOO-B"._
4206
4207 You may look backwards in this document and consult the GNU APL source code,
4208 but not peek into the solution sketch below, If you stumble over something
4209 that is not properly described above then please report that on
4210 mailto:[email protected].
4211
4212 === Solution (sketch with comments)
4213
4214 . Add a symbol *FOO* to *src/Id.def:*
4215 +
4216 ----
4217 qf( FOO , "⎕FOO" , )
4218 ----
4219 +
4220 The proper position of *FOO* in *Id.def* is important (after the last
4221 ⎕-symbol group that starts with *F*, i.e. after the *⎕FFT* line.
4222
4223 . Add a header file *src/Quad_FOO.hh* like this:
4224 +
4225 ----
4226 #ifndef __Quad_FOO_HH_DEFINED__
4227 #define __Quad_FOO_HH_DEFINED__
4228
4229 #include "QuadFunction.hh"
4230 ...
4231
4232 class Quad_FOO : public QuadFunction
4233 {
4234 public:
4235 /// Constructor.
4236 Quad_FOO()
4237 : QuadFunction(TOK_Quad_FOO),
4238 system_wisdom_loaded(false)
4239 {}
4240
4241 static Quad_FOO fun; ///< Built-in function.
4242 static Quad_FOO * _fun; ///< Built-in function.
4243
4244 protected:
4245 /// overloaded Function::eval_B()
4246 Token eval_B(Value_P B) const;
4247
4248 ...
4249 };
4250
4251 #endif // __Quad_FOO_HH_DEFINED__
4252 ----
4253 +
4254 Since *⎕FOO* is monadic, we have one handler eval_B(Value_P B), which
4255 overloads *virtual Function::eval_B()* in *Function.hh* and causes our
4256 *Quad_FOO::eval_B* to be called instead of *eval_B()* of the base class. If
4257 *⎕FOO* should support more signatures then it is better to add them at a later
4258 point in time.
4259 +
4260 . Add a Cpp source file *src/Quad_FOO.cc* like this:
4261 +
4262 ----
4263 #include "Quad_FOO.hh"
4264
4265 Quad_FOO Quad_FOO::fun;
4266 Quad_FOO * Quad_FOO::_fun = &Quad_FOO::fun;
4267
4268 //-----------------------------------------------------------------------------
4269 Token
4270 Quad_FOO::eval_B(Value_P B) const
4271 {
4272 Value_P Z(LOC); // makes Z an APL scalar,
4273 Z->next_ravel_int(42); // which is the integer 42
4274 Z->check_value(LOC); // check Z and set its Z->VF_complete flag
4275 return Token(TOK_APL_VALUE1, Z); // return the result.
4276 }
4277 //-----------------------------------------------------------------------------
4278 ----
4279 +
4280 We have not (yet) implemented the requested functionality in
4281 *Quad_FOO::eval_B()*. It makes life easier to first integrate *⎕FOO* into the
4282 GNU APL framework (and test the integration) then to add the functionality
4283 later on.
4284 +
4285 . When using SVN then add the new files to the repository:
4286 +
4287 ----
4288 $ svn add Quad_FOO.cc Quad_FOO.hh
4289 $ svn commit -m "new file"
4290 ----
4291
4292 . Add the following line to several source files:
4293 +
4294 ----
4295 #include "Quad_FOO.hh"
4296 ----
4297 +
4298 This makes the new declarations available in the *.cc* files that need it.
4299 The files concerned are:
4300 +
4301 .. src/Archive.cc
4302 .. src/Id.cc
4303 .. src/QuadFunction.cc
4304 .. src/Workspace.cc
4305 +
4306 . Update *Makefile.am*.
4307 .. Add the new files *Quad_FOO.cc* and *Quad_FOO.hh* to the make variable
4308 *common_SOURCES* in *src/Makefile.am*:
4309 +
4310 ----
4311 Quad_FOO.cc Quad_FOO.hh
4312 ----
4313 +
4314 Keep *src/Makefile.am* sorted alphabetically and indented in the same way as
4315 the other files.
4316 +
4317 .. (re-)run *autoreconf* (in the GNU APL top-level directory)
4318 +
4319 ----
4320 $ autoreconf
4321 ----
4322 +
4323 This creates a new *src/Makefile.in* from *src/Makefile.am*, and
4324
4325 .. (re-)run *./configure* (also in the GNU APL top-level directory).
4326 +
4327 ----
4328 $ ./configure
4329 ----
4330 +
4331 This includes the new files in *src/Makefile* so that they are properly
4332 compiled and linked.
4333
4334 . Add a *TD()* macro for *⎕FOO* in *src/Token.def*:
4335 +
4336 ----
4337 TD(TOK_Quad_FOO , TC_FUN1 , TV_FUN , ID::Quad_FOO )
4338 ----
4339 +
4340 This defines a new Token with token class *TC_FUN1*, value type *TV_FUN* i.e.
4341 *Function* (-pointer), and ID *ID::Quad_FOO*. Note that:
4342 +
4343 .. *TC_FUN1* is an alias for *TC_FUN12* (and so is *TC_FUN2*. These aliases
4344 are used to make explicit that ⎕FOO is monadic. If you should add a dyadic
4345 signature later on then change the token class to *TC_FUN12*.
4346 +
4347 .. Since *src/Token.def* is a *.def* file, it will be *#included* by several
4348 *.cc* files and magically insert the new token in several source files.
4349
4350 . Add a *sf_def()* macro to *src/SystemVariable.def*:
4351 +
4352 ----
4353 sf_def(Quad_FOO, "FOO", "Definitely not ⎕BAR" )
4354 ----
4355 +
4356 This takes care of a number of things:
4357 +
4358 .. *)SAVE* of functions in *.xml* workspace snapshots,
4359 .. Tab expansion of ⎕-function names,
4360 .. update of the *)HELP* command (short help text), and
4361 .. Instantiation in workspaces.
4362 +
4363 . And finally: increment *ASX_MINOR* minor in *enum ArchiveSyntax* in file
4364 *src/Archive.hh*. Adding ⎕-functions to GNU is a backward compatible change
4365 of the *.xml* file format. The new interpreter can *)LOAD* files that were
4366 **)SAVE**d with older versions, but not vice versa. Incrementing *ASX_MINOR*
4367 will then issue a warning in older (but not too old) interpreters.
4368
4369 . After these changes you can build and test that the new intepreter compiles
4370 and works (if not then the author has missed something above).
4371 +
4372 ----
4373 $ make
4374 $ src/apl
4375
4376 ⎕FOO 5
4377 42
4378 ----
4379
4380 . If so, then we can add some more beef into *Quad_FOO::eval_B()*:
4381 +
4382 ----
4383 #include "Quad_FOO.hh"
4384
4385 Quad_FOO Quad_FOO::fun;
4386 Quad_FOO * Quad_FOO::_fun = &Quad_FOO::fun;
4387
4388 //-----------------------------------------------------------------------------
4389 Token
4390 Quad_FOO::eval_B(Value_P B) const
4391 {
4392 // check that B is a 1-item integer
4393 //
4394 if (B->element_count() != 1) // rank or length error
4395 {
4396 if (B->get_ranke() != 1) RANK_ERROR;
4397 else LENGTH_ERROR;
4398 }
4399
4400 const Cell & B0 = B->get_cfirst(); // first item in B
4401 const APL_Integer b = B0.get_int_value(); // DOMAIN_ERROR for non integers
4402 UCS_string z("FOO-"); // z is string "FOO-"
4403 z.append_number(b); // now z is e.g. "FOO-42"
4404
4405 Value_P Z(z); // constructor: APL value from string
4406 return Token(TOK_APL_VALUE1, Z); // return the result.
4407 }
4408 //-----------------------------------------------------------------------------
4409 ----
4410
4411
4412 == Exercise 2
4413
4414 This exercise is similar to <<Exercise 1>> above, but this time we want to
4415 create a system variable instead of a system function:
4416
4417 _Add a new system variable named *⎕FOO* to GNU APL so that:_
4418
4419 * _*⎕FOO←B* with 1-item integer B shall remember B, while_
4420 * _*Z←⎕FOO* shall be the APL value (string) "FOO-B"._
4421
4422 System variables are inherently more complex than system functions because
4423 most system functions are stateless, while system variables typically have
4424 state that needs to be **)SAVE**d in workspaces.
4425
4426 === Solution (sketch with comments)
4427
4428 The solution is for the most part, similar to the previous example. We
4429 therefore only discuss the differences.
4430
4431 * System variables are (directly or indirectly) derived from class
4432 *SystemVariable*, while system functions are derived from class *Function*.
4433 System functions overload one or more (virtual) *eval_XXX()*, while system
4434 variables overload the following (virtual) functions:
4435 ** *Value_P get_apl_value() const*, called when the variable is referenced,
4436 ** *assign(Value_P B, ...)*, called when a values is assigned to the variable,
4437 ** possibly *assign_indexed()*,
4438 called for indexed assignments (if the variable shall support it), and
4439 ** possibly *push()* and *pop()* functions if the variable can be localized.
4440 ** Therefore our *Quad_FOO.hh* reads:
4441
4442 ----
4443 //----------------------------------------------------------------------------
4444 #ifndef __Quad_FOO_HH_DEFINED__
4445 #define __Quad_FOO_HH_DEFINED__
4446
4447 /**
4448 System variable Quad-FOO.
4449 */
4450 /// The class implementing ⎕FOO
4451 class Quad_FOO : public SystemVariable
4452 {
4453 public:
4454 /// Constructor.
4455 Quad_IO()
4456 : SystemVariable(ID_Quad_IO)
4457 {
4458 Symbol::assign(IntScalar(0, LOC), false, LOC);
4459 }
4460
4461 protected:
4462 /// overloaded Symbol::assign().
4463 virtual void assign(Value_P B, bool clone, const char * loc);
4464
4465 // overloaded Symbol::push()
4466 virtual void push()
4467 {
4468 Symbol::push();
4469 Symbol::assign(IntScalar(0, LOC), false, LOC);
4470 }
4471 };
4472
4473 #endif // __Quad_FOO_HH_DEFINED__
4474 ----
4475 * and the *TD()* macro now becomes:
4476 +
4477 ----
4478 TD(TOK_Quad_FOO , TC_SYMBOL , TV_SYM , ID_Quad_FOO )
4479 ----
4480 +
4481 * The *sf_def()* macro (*sf* stands for **s**ystem **f**unction) above in
4482 *SystemVariable.def* now becomes:
4483 +
4484 ----
4485 rw_sv_def(Quad_FOO, "FOO", "not BAR " )
4486 ----
4487 +
4488 where *rw_sv_def* stands for **r**ead/**w**rite **s**ystem **v**ariable. If
4489 *⎕FOO* were read-only (which implies that localizing it has no effect), then
4490 macro *ro_sv_def* would have been used instead.
4491
4492 The name *SystemVariable.def* is a little misleading because it contains the
4493 macros for both variables and functions.
4494
4495
4496 [bibliography]
4497 == References
4498
4499 * [[[ISO]]] ISO/IEC Standard 13751.
4500 _Programming Language APL, Extended_
4501 +
4502 *www.math.uwaterloo.ca/~ljdickey/apl-rep/docs/is13751.pdf*
4503 +
4504 NOTE: This file is, despite its *.pdf* extension, a *gzip* compressed
4505 file which will only expand into a proper *.pdf* file after uncompressing
4506 it (with *gunzip*).
4507 {nbsp} +
4508 {nbsp} +
4509
4510 * [[[IBM]]] IBM Corp.
4511 _APL2: Language Reference_
4512 +
4513 *www.ibm.com/downloads/cas/ZOKMYKOY*.
4514 +
4515 NOTE: The exact download location seems to change every now and then.
4516 {nbsp} +
4517 {nbsp} +
4518
4519 * [[[Sau]]] Dr. Jürgen Sauermann
4520 _Ein Paralleler APL Rechner (A Parallel APL Computer)_.
4521 +
4522 Ph.D Thesis 2.00, Universität des Saarlandes.
4523 {nbsp} +
4524 {nbsp} +
4525
4526 * [[[Sch]]] Dipl. inf. Dieter Scheerer
4527 _Entwurf und Realisierung eines Verbindungsnetzwerks als Teil des
4528 Multiprozerssorsystems DATIS-P-256._
4529 +
4530 Masters Thesis 1989, Universität des Saarlandes.
4531 {nbsp} +
4532 {nbsp} +
4533
4534 * [[[Ger]]] Dipl. inf. Andreas Gergen
4535 _Entwurf und Realisierung einer Master-Slave Kommunikation im
4536 Multiprozerssorsystem DATIS-P-256_
4537 +
4538 Masters Thesis 1989, Universität des Saarlandes.
4539 {nbsp} +
4540 {nbsp} +
4541
4542 * [[[Mör]]] Dipl. inf. Thomas Mörsdorf
4543 _Entwurf, Bau, und Test einer 32-bit CPU als Teil des
4544 Multiprozerssorsystems DATIS-P-256._
4545 +
4546 Masters Thesis 1989, Universität des Saarlandes.
4547 {nbsp} +
4548 {nbsp} +
4549
4550 * [[[Glä]]]] Dipl. inf. Ina Gläs
4551 _Die Lösung spezieller Probleme bei der Realisierung eines
4552 Permutationsnetzwerkes als Teil des Multiprozerssorsystems DATIS-P-256._
4553 +
4554 Masters Thesis 1989, Universität des Saarlandes.
4555 {nbsp} +
4556 {nbsp} +
4557