| 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 |
|