krc.1
1 .TH KRC 1 2016-03-31 2 .SH NAME 3 krc \- Kent Recursive Calculator 4 .SH SYNOPSIS 5 .B krc 6 [\fIoptions\fR] [\fIfile\fP] [\fIarguments\fP] ... 7 .SH OPTIONS 8 .TP 9 \fB-h\fR \fIcells\fR 10 Specify the size of the heap. 11 On a 32-bit computer, each cell requires 12 16 bytes, on a 64-bit computer 32 bytes. 13 The default is 128000 cells. 14 .TP 15 \fB-d\fR \fIbytes\fR 16 Specify the size of the dictionary, or "string space", 17 used to store identifiers, comments and strings. 18 The default is 64000 bytes. 19 .TP 20 \fB-n\fR 21 Don't include the prelude of standard definitions. 22 .TP 23 \fB-l\fR \fIlib\fR 24 Use \fIlib\fR in place of the prelude. 25 .TP 26 \fB-L\fR 27 Use a legacy prelude from 1981 in place of the prelude. 28 .TP 29 \fB-s\fR 30 Load prelude or \fIlib\fR stripped of comments (saves string space). 31 .TP 32 \fB-c\fR 33 Turn on reduction counting (the same as the \fB/count\fR command). 34 .TP 35 \fB-g\fR 36 Turn on garbage collector statistics (the same as the \fB/gc\fR command). 37 .TP 38 \fB-o\fR 39 Turn on the printing of compiled objects (the same as the \fB/object\fR command). 40 .TP 41 \fB-z\fR 42 Sets base for list indexing to 1 instead of 0 (legacy option). 43 .TP 44 \fB-e \fIexpression[?!]\fR 45 Instead of being interactive, evaluate \fIexpression\fR and display its 46 value (with `?') or flat-print the value (with `!'). 47 .PP 48 If a file name is given after the options, its contents will 49 be loaded as the \fIcurrent script\fR. 50 If you don't give a file name the current script is initially empty. 51 .PP 52 Arguments following the file are permitted only when a \fB-e\fP option 53 is present and in this case the file name and any arguments are placed 54 in a list of strings called "\fBargv\fP". 55 .SH DESCRIPTION 56 Kent Recursive Calculator was one of the earliest higher-order, lazy, 57 purely functional programming systems. Written around 1980, it was a 58 simplified version of its author's language SASL, 59 developed at St Andrews University in 1972-6, and in turn was succeeded 60 by Miranda, the main precursor of Haskell. These days it has the 61 advantages of being a simple language of this kind capable of running 62 in very little memory (75KB code plus whatever space is allocated for 63 heap and dictionary). 64 .PP 65 A KRC program is called a \fIscript\fP, which consists of 66 a sequence of \fIdefinitions\fP each of which consists of an 67 optional comment followed by one or more \fIequations\fP, one per line. 68 .PP 69 When you invoke krc, it loads a set of standard 70 definitions called the \fIprelude\fP, then prints a welcome 71 message followed by a prompt, \fBkrc>\fP. You have now entered a KRC \fIsession\fP. 72 In a session you can type commands, expressions to be evaluated, and 73 definitions to be entered in the current script. 74 A new prompt appears as each task is completed, until you end the session. 75 .SH COMMANDS 76 The interpreter accepts a range of commands 77 to inspect, edit, load and save scripts, 78 as well as a few system-oriented things. Each command is 79 entered on a single line, followed by [Enter]. 80 .PP 81 The command to inspect a definition, say of `foo', is just the name 82 on a line by itself 83 .br 84 \ \ \ \ foo 85 .br 86 the system responds by displaying the definition associated with 87 `foo', which may be in the prelude or in the current script. 88 If the definition has more than one equation these are shown 89 numbered, from \fB1\fP, the numbers are used when editing definitions. 90 .PP 91 You can display a section of the script, say from 92 the definition of `foo' to `bar' by typing 93 .br 94 \ \ \ \ foo\ ..\ bar 95 .br 96 .PP 97 The other commands all start with a \fB/\fR character. 98 .TP 99 \fB/\fR 100 Displays all of the current script 101 .TP 102 \fB/quit\fP 103 Ends a KRC session. Shorthand:\ \fB/q\fP. 104 Typing control-D also has this effect. 105 .PP 106 Be aware that ending a session does not automatically save the current 107 script, for that you must use \fB/save\fP (see below). 108 .PP 109 In the commands which follow `\fIname\fP' means 110 one of the names defined in the current script; 111 .PP 112 Where it says `\fIname(s)\fP' 113 you can put a name, several names separated by 114 spaces, or a range 115 \fIfoo\fB..\fIbar\fR which refers to definitions \fIfoo\fP through \fIbar\fP 116 of the current script, 117 or \fIfoo\fB..\fR which means from the definition of \fIfoo\fP 118 to the end of the script. 119 .PP 120 Where it says `\fIpart(s)\fP', this refers to equation numbers 121 from a definition in the script, for deletion or reordering. 122 .PP 123 A \fIpart\fP can be a single number like \fB1\fP, 124 a range like \fB2..4\fP, 125 something like \fB4..\fP, which means from 126 equation \fB4\fP to the end of the definition; 127 \fIpart(s)\fP means a list of these separated by spaces. 128 .TP 129 \fB/delete\fP \fIname(s)\fP 130 Deletes one or more definitions from the script. 131 Shorthand:\ \fB/d\fP 132 .br 133 If no 134 \fInames\fP are supplied, it deletes the whole script (\fBbeware!\fP). 135 .TP 136 \fB/delete\fP \fIname\fP \fIpart(s)\fP 137 Deletes the numbered equations from the definition of \fIname\fP. 138 To delete the comment, enter an empty comment for the same name, 139 for example "foo:-;" 140 .TP 141 \fB/reorder\fP \fIname\fP \fIname(s)\fP 142 Place the definitions of one or more \fInames\fP immediately after those 143 for the first mentioned \fIname\fP, in the order shown. 144 .TP 145 \fB/reorder\fP \fIname\fP \fIpart(s)\fP 146 Reorder the equations within a definition by moving the 147 numbered equations listed in \fIpart(s)\fP to the top of the 148 definition, in the order shown. 149 .TP 150 \fB/aborder\fP 151 Sorts the script's definitions into alphabetical order. 152 .TP 153 \fB/rename\fP \fIfrom\fB,\fIto\fR 154 Change the name `\fIfrom\fP' into `\fIto\fP', in all 155 the places where it is used in the 156 script; \fIfrom\fP and \fIto\fP can both be lists of names 157 separated by spaces, in which case the first name in \fIfrom\fP is 158 changed to the first name in \fIto\fP and so on. This allows you 159 to swap two or more names in the script without losing any of them. 160 .TP 161 \fB/save\fP \fIfilename\fP 162 Saves the script in the named file. 163 If \fIfilename\fP is omitted, it saves to the last filename mentioned. 164 .TP 165 \fB/get\fP \fIfilename\fP 166 Adds the contents of a file to the script. 167 If \fIfilename\fP is omitted, from the last filename mentioned. 168 .TP 169 \fB/file\fP 170 Shows the current default filename. Shorthand:\ \fB/f\fP 171 .TP 172 \fB/file\fP \fIfilename\fP 173 Changes the default filename. 174 .TP 175 \fB/list\fP \fIfilename\fP 176 Lists the contents of a disk file, like Unix's "cat" or DOS's "type" commands. 177 If the \fIfilename\fP is omitted, it reads from the last filename mentioned. 178 .TP 179 \fB/dir\fR 180 List the filenames in the current directory or folder, like Unix's "ls" 181 or DOS's "dir" commands. 182 .TP 183 \fB/names\fP 184 Displays the names defined in the script. 185 .TP 186 \fB/lib\fP 187 Displays the names defined in the prelude. 188 .TP 189 \fB/openlib\fP 190 Allows you to modify the definitions of the prelude (they are normally write-protected). 191 Any changes are made to the copy of the definitions held in memory during 192 the session - only if you use \fB/save\fP (filename) do they get written to a file. 193 .TP 194 \fB/clear\fP 195 Clear all memo fields. When a simple definition in the script is expanded 196 i.e. one like \fBfoo\fP = STUFF, the value is stored in a memo field for \fBfoo\fP 197 so STUFF need not be evaluated again. These are cleared automatically when any 198 definition in the script is changed. 199 .TP 200 \fB/count\fP 201 Turns on reduction counting. 202 .TP 203 \fB/gc\fP 204 Enables the printing of memory usage information each time a 205 garbage collection happens. 206 .TP 207 \fB/reset\fP 208 Turns off reduction counting, garbage collection information 209 and object display (see below). 210 .TP 211 \fB/dic\fP 212 Report current state of string space. 213 .TP 214 \fB/help\fR 215 Prints a list of help topics. Shorthand: \fB/h\fR 216 .TP 217 \fB/help\fR \fItopic\fP 218 Displays the relevant helpfile, using the UNIX command `\fBless\fR'. 219 This allows you to move backwards 220 (type `b') in the file as well as forwards (type SPACE, or ENTER to move 221 forward one line at a time), type `q' to quit. Say `\fBman\ 1\ less\fR' 222 on the UNIX command line for more details. 223 .PP 224 These last commands are for use in debugging the system: 225 .TP 226 \fB/object\fP 227 Displays the internal representation of each expression before evaluating it. 228 .TP 229 \fB/lpm\fP 230 The "List Post Mortem" displays the KRC machine's internal state. 231 .SH EXPRESSION EVALUATION 232 An \fIexpression\fP is a mathematical formula denoting a value. For details 233 of what can be in an expression see later sections: 234 IDENTIFIERS, DATA TYPES, OPERATORS and ZF EXPRESSIONS. 235 To evaluate an expression in a KRC session and print the result 236 on the screen, type the expression followed by `\fB?\fP'. 237 .PP 238 For example, you could type \fB2+2?\fP to obtain \fB4\fP. 239 .PP 240 If the value is a data structure it is printed as you would enter it, with 241 quote marks around strings, 242 square brackets around lists and commas between list elements. 243 For example (`++' joins lists together): 244 .PP 245 \ \ \ \ \fBkrc>\fP [1..3]++["...\\n"]++[2*2]? 246 .PP 247 \ \ \ \ \fB[1,2,3,"...\\n",4]\fP 248 .PP 249 Note that with `\fB?\fP' control characters in a string are shown, 250 not obeyed ("\\n" means newline). 251 .PP 252 An alternative method of printing uses `\fB!\fP' in place of `\fB?\fP'. 253 .PP 254 \ \ \ \ \fBkrc>\fP [1,2,3,"...\\n",4]! 255 .PP 256 \ \ \ \ \fB123... 257 .br 258 \ \ \ \ 4\fP 259 .PP 260 `\fB!\fP' prints strings without quotes, obeying any control characters, numbers 261 are printed in the usual way and with lists 262 `\fB!\fP' scans left to right, recursively scanning any sublists encountered, 263 printing only the atoms (numbers and strings). 264 The effect is as if the data were squashed flat and joined up 265 into a single string (although `\fB!\fP' does not actually use 266 any additional string space). 267 .PP 268 As a general guide `?' (print values to show structure) is used when developing 269 and testing functions and `!' (flat-print) for the final output of a program 270 where you want to control layout. 271 Note that `?' adds a trailing newline while `!' doesn't. 272 .PP 273 The reader may find it helpful to study the function \fBshow\fP defined in the 274 prelude; 275 .RS 276 \fBx?\fP 277 .RE 278 is actually equivalent to 279 \fBshow\ x\ :\ ["\\n"]!\fP 280 .PP 281 \fBReminder\fP: For KRC to print the value of an expression it must be followed 282 by `\fB?\fP' or `\fB!\fP'. 283 .SH THE SCRIPT: COMMENTS AND EQUATIONS 284 A KRC script consists of a sequence of \fIdefinitions\fP, each of which 285 is composed of an optional \fIcomment\fP followed by one or more \fIequations\fP. 286 The order of the definitions has no significance as they are all in scope 287 throughout the script, but the order of 288 the equations within a definition may affect its meaning, as they are tried 289 in the order written. 290 .PP 291 A comment is the name, of a function or other data item, followed by the two 292 characters "\fB:-\fP" followed by any number of lines of text 293 and terminated by the first semicolon "\fB;\fP". 294 .br 295 \ \ \ \ flub :- here is some text 296 .br 297 \ \ \ \ \ \ \ \ \ \ \ \ ... explaining "flub"; 298 .PP 299 An equation is one line of a definition and has this form: 300 .RS 301 \fBLHS = expression\fP 302 .RE 303 or 304 .RS 305 \fBLHS = expression, guard\fP 306 .RE 307 where \fBLHS\fP ("left hand side") is a 308 name optionally followed by formal parameters and \fBexpression\fP 309 describes the value which the lhs assumes in this case. 310 .PP 311 The optional \fBguard\fP is a Boolean (i.e. truth-valued) expression which determines 312 if the equation is applicable. If the guard evaluates to "TRUE" 313 the equation is used, otherwise it is not. 314 .PP 315 Note that equations are written one per line 316 (no terminating semicolons needed, or allowed). Examples 317 .RS 318 radix = 10 319 .br 320 girls = ["susan","jill","pandora"] 321 .RE 322 are simple definitions. A simple definition has just a name as its LHS. 323 .PP 324 We can define a function by introducing a formal parameter 325 .RS 326 sq n = n * n 327 .RE 328 The formal parameter `n' is a local variable of the equation. Any name 329 can be used as a formal parameter, it does not have to be a single letter. 330 However name clashes, like using `sq' as a formal parameter when it 331 is also a top-level name, are best avoided (occurences of the name 332 on the right of the equation will refer to the formal parameter). 333 .PP 334 Names which appear at the head of an LHS, which to this point are 335 `radix', `girls' and `sq', are known as \fItop-level names\fP and have the whole 336 script as their scope, as do the names defined in the prelude. (The scope of 337 a name is the region of text in which it can be used with the same meaning.) 338 .PP 339 Here is a function of two parameters 340 .RS 341 sqdiff m n = m*m - n*n 342 .RE 343 We call it by writing e.g. 344 .RS 345 sqdiff 2 3 346 .RE 347 not sqdiff(2,3) as you would in some other programming languages. 348 .PP 349 More complex function definitions 350 may require several equations, for example 351 .RS 352 fac 0 = 1 353 .br 354 fac n = n * fac(n-1) 355 .RE 356 defines a factorial function which can then 357 be used, for example by writing 358 .RS 359 fac\ 10? 360 .RE 361 Note the use of a constant, 0, as formal parameter in the first equation. 362 This is one way to do case analysis. 363 .PP 364 Guards can also be used to do case analysis. 365 A safer version of `fac' would be: 366 .RS 367 fac n = 1, n <= 0 368 .br 369 \ \ \ \ \ \ = n * fac(n-1) 370 .RE 371 Here we use a guard, `n <= 0', to stop `fac' going into a loop on negative numbers. 372 Entering an equation with no left hand side 373 means that the LHS is the same as in the line previously entered. 374 .PP 375 We have seen that a formal parameter can be a name or a literal constant. 376 It can also be a pattern to match list structure as in this example \- 377 `rotor' carries out a simple rotation on lists of length 3. 378 .RS 379 rotor [a,b,c] = [b,c,a] 380 .RE 381 .PP 382 To match lists of unknown length we use a pattern involving `:', 383 for example the functions `hd', `tl', which return the first element 384 of a list, and the remainder of the list without the first element, are defined 385 .RS 386 hd (a:x) = a 387 .br 388 tl (a:x) = x 389 .RE 390 .PP 391 Another example is this function which copies lists of length <=2 and extracts 392 the first 2 elements of lists with length >2. 393 .RS 394 take2 [] = [] 395 .br 396 take2 [a] = [a] 397 .br 398 take2 (a:b:x) = [a,b] 399 .RE 400 Note that ':' is right associative so `a:b:x' means `a:(b:x)'. 401 .PP 402 In summary, an LHS consists of the name being defined followed by zero 403 or more formal parameters. Each formal parameter can be 404 .RS 405 a \fIname\fP like \fBx\fP or \fBheight\fP 406 .br 407 a \fIliteral\fP number or string like \fB3\fP or \fB"bill"\fP 408 .br 409 a \fIpattern\fP like \fB[p,q,r]\fP or \fB(a : x)\fP 410 .br 411 where any of the p, q, r, a, x could themselves be a name, literal or pattern. 412 .RE 413 Names introduced by formal parameters are local to the equation in 414 which they appear. 415 .PP 416 An equation with 417 one or more patterns in its LHS applies when the actual parameters 418 of a function invocation 419 match the corresponding formal parameters; that is they have the same list 420 structure and, where the pattern contains a literal, the values are equal. 421 If there is also a guard, that must evaluate to "TRUE". 422 .PP 423 Where a definition has more than one equation they must all have the 424 same number of formal parameters. Notwithstanding this, it is possible 425 in KRC to define functions which take a variable number of arguments, 426 because the right hand sides can be of varying type. (Terminology \- 427 the actual parameters of a function are also called its \fIarguments\fP.) 428 .PP 429 KRC supports the interactive development of scripts. 430 .PP 431 To enter definitions in the script during a session you simply type in the 432 equations and comments at the prompt, one at a time. You can then enter 433 expressions to test your definitions and edit them (i.e. delete, 434 reorder etc) using the COMMANDS listed earlier and re-enter equations as 435 needed. The line editing facilities provided by "linenoise" and/or 436 the use of a mouse to cut and paste make this task relatively easy. 437 .PP 438 If you enter an equation with the same LHS and 439 guard as an existing one it will replace it. Entering a comment will replace an 440 earlier comment on the same name. To delete a comment enter an empty replacement 441 .RS 442 name :-; 443 .RE 444 .PP 445 Another way of proceeding is to use an editor to create the script and 446 then start a krc session with it as the file. The 447 KRC system was designed to allow it to be used without a separate editor (back 448 in 1980 screen editors like \fBvi\fP and \fBemacs\fP were not widely 449 available as they are now). 450 .SH IDENTIFIERS 451 The names used in scripts and expressions are built from 452 \fBA-Z\fP \fBa-z\fP \fB0-9\fP underscore (\fB_\fP) and apostrophe (\fB\'\fP), 453 start with a letter 454 and can be of any length. Case is significant, so X and x are different identifiers. 455 Note that KRC has no reserved words. 456 .SH DATA TYPES 457 KRC has four data types: numbers, strings, lists and functions. 458 .PP 459 The four types of value have the same "civil rights" \- any value can be (i) named, 460 (ii) included in a list, (iii) passed to a function 461 as its argument, (iv) returned by a function as result. 462 .PP 463 There is no static type system \- values of different types can be freely mixed, for 464 example as elements of a list and a function can accept 465 arguments of more than one type and return results of different 466 types for different inputs. 467 Type errors, e.g. trying to multiply two strings, are detected at 468 run time. Languages of this kind (LISP is another example) are often 469 called `typeless', but \fIdynamically typed\fP is more accurate. 470 .PP 471 A value can be tested by the four functions `number', `string', `list' and 472 `function' and returns "TRUE" for one of these, 473 "FALSE" for the others. There is also a function `char' which recognises 474 strings of length 1 and a function `bool' which reconises the strings "TRUE" and "FALSE". 475 .PP 476 \fBNumbers\fP are integers (whole numbers, positive, negative and zero) 477 written in the usual decimal notation, e.g. 3 -17 500 478 .PP 479 \fBStrings\fP are sequences of characters enclosed in double quotes, e.g. 480 .RS 481 "cattle" "oh my!" 482 .RE 483 .PP 484 Control characters are written using `\\', e.g. "\\n" is newline. 485 The escape conventions are as in C 486 .RS 487 \\a (bell) \\b (backspace) \\f (formfeed) \\n (newline) \\r (carriage return) 488 \\t (tab) \\v (vertical tab) \\\\\ (backslash) \\' \\" 489 .RE 490 and numeric character codes 491 .RS 492 \\ddd (up to three decimal digits). 493 .RE 494 KRC character codes are in the range 0\-255 (of which 0\-127 are ascii, 495 the meaning of codes above 127 depends on the \fIlocale\fP). 496 .PP 497 Note the strings "TRUE", "FALSE" are used as truthvalues, 498 there is no separate Boolean type. 499 .PP 500 KRC has no separate type `character' distinct from `string'. 501 A character is just a string of length 1, e.g. "a" 502 (you cannot write this as \'a\', that would not be recognised). 503 .PP 504 The prelude function `explode' converts a string into 505 a list of characters, e.g. 506 .RS 507 \fBkrc>\fP explode "hello"? 508 .br 509 ["h","e","l","l","o"] 510 .RE 511 .PP 512 KRC treats strings as atomic; they are stored uniquely in packed 513 form. Strings can be tested for equality or order without unpacking them but 514 to access the internal structure you must use `explode'. 515 .PP 516 There is a function `implode' which compresses a list of strings into a 517 single string, but this is less often needed. Processing of textual 518 data is typically done on lists of characters (or sometimes trees) 519 and given `!' there is no need to convert 520 the result back into a single string before printing. 521 .PP 522 \fBLists\fP are written using square brackets and commas between 523 elements, e.g. [1,2,3,"eric"]. Note 524 the empty list, [] and singletons, e.g. [3]. 525 .PP 526 An important operation on lists is `\fB:\fP' which prefixes an element 527 to the front of a list. So `a:[]' is `[a]', `a:b:[]' is 528 `[a,b]' and so on. 529 Note also the `\fB++\fP' operator which appends one list to another. The 530 elements of `x++y' are those of `x' followed by those of `y'. 531 .PP 532 As some, or all, of the elements of a list can be lists it 533 is possible to construct multi-dimensional arrays (as lists of lists of ...) 534 and more generally trees, of any shape. 535 Lists can be of infinite length, for example 536 .RS 537 ones = 1 : ones 538 .RE 539 is an infinite list of ones and 540 .RS 541 abyss = ["down",abyss,"up"] 542 .RE 543 is a tree of infinite depth. These examples are possible because of KRC's general strategy 544 of \fIlazy evaluation\fP, which includes not evaluating the parts of a structure until they are accessed. 545 .PP 546 There is a notation `[a..b]' for a sequence of consecutive integers, e.g. `[-10..10]' 547 is a list with 21 elements. This notation also has an infinite form, e.g. `[2..]' 548 is a list of the integers starting at 2. 549 .PP 550 Similarly the notation `[a,b..c]' can be used for an arithmetic sequence running 551 from a to c with step (b-a). E.g. [1,3..99] are the odd numbers from 1 to 99. 552 Again this has an infinite form, e.g. [0,-5..] 553 .PP 554 A list can be applied to a non-negative number, n say, 555 to extract its n'th element (counting from 0). So given 556 .RS 557 x = ["mon","tue","wed","thu","fri"] 558 .RE 559 then `x 0' is "mon", `x 6' is "fri", and `x 7' is an error. 560 A list can therefore be supplied in a context where a function is expected, for example 561 as an operand of `.' the functional composition operator. 562 .PP 563 \fBFunctions\fP: a function calculates an output 564 value from given input value(s). The rules of calculation are given by its defining equations 565 (except for a few built-in functions defined in machine code). 566 .PP 567 Applying a function to its input values (or \fIarguments\fP) is done by juxtaposition, e.g. 568 .RS 569 f x y 570 .RE 571 If an argument is an operator expression or another function application 572 it needs parentheses to force the correct parse. E.g. 573 .RS 574 f (g x) (y+2) 575 .RE 576 .PP 577 A prefix or infix operator in single quotes 578 denotes the corresponding one- or two-argument function, e.g. 579 .RS 580 ops = [\'+\', \'-\', \'*\', \'/\'] 581 .RE 582 is a list of the four functions of arithmetic. See below, under OPERATORS. 583 .PP 584 \fIContinued application\fP: a function application can return a function, 585 e.g. (ops n) is a function, which one depends on `n'. 586 We can immediately apply this to its arguments, thus 587 .RS 588 ops n x y 589 .RE 590 We could write `(ops n) x y' but the parentheses are not needed as 591 function application is \fIleft associative\fP. 592 .PP 593 \fIPartial application\fP: a function of two or more arguments 594 can be applied to a smaller number of arguments and 595 the result is a function that is waiting for the remaining arguments. 596 For example 597 .RS 598 double = \'*\' 2 599 .RE 600 is a function that can be applied to a number and will multiply it by 2. 601 .PP 602 Partial application works because KRC uses a model of functions 603 derived from \fIcombinatory logic\fP. In this model, all functions 604 actually take a single argument. An n-ary function, for n>1, is a 605 function that, when applied to its argument, returns an (n-1)ary 606 function that is waiting for the next argument. So taking the case 607 n=3 as an example 608 .RS 609 \fBf a b c\fP 610 .RE 611 means 612 .RS 613 \fB((f a) b) c\fP 614 .RE 615 but because of the left-associative rule the parentheses are normally omitted. 616 .SH OPERATORS 617 The following table lists KRC's prefix and infix operators in order of increasing binding 618 power. 619 .PP 620 The second column gives associativity:- a left associative operator, e.g. `-' has 621 .RS 622 \fBa - b - c\fP \ ==> \ \fB(a - b) - c\fP 623 .RE 624 while a right associative operator, e.g. `++' has 625 .RS 626 \fBa ++ b ++ c\fP \ ==> \ \fBa ++ (b ++ c)\fP 627 .RE 628 Infix operators in the same row have the same binding power and are jointly 629 right or left associative. 630 .PP 631 The third column gives a brief statement of meaning. 632 Where needed the notes below add further detail. 633 .TS 634 l l l 635 l l l. 636 \fBoperator\fP \fBassociativity\fP \fBmeaning\fP 637 : ++ -- right list prefix, append, listdiff 638 | right logical \fIor\fP 639 & right logical \fIand\fP 640 \\ prefix logical \fInot\fP 641 > >= \\= == <= < see below comparisons 642 + - left add, subtract 643 + - prefix plus, minus 644 * / % left multiply, integer divide, remainder 645 ** . right exponent, function-compose 646 # prefix length of list 647 .TE 648 .PP 649 The application of a function to its arguments binds more tightly 650 than any operator. Parentheses \fB(...)\fP can be inserted freely 651 in expressions to enforce the intended parse or to make it clearer to the reader 652 \- redundant parentheses do not change the meaning (this is true both in expressions 653 and in formal parameters). 654 .PP 655 The operators \fB:\fP (prefix) and \fB++\fP 656 (append) have been discussed earlier, in the section on DATA TYPES. 657 The expression \fBx -- y\fP returns a list of the elements of \fBx\fP without 658 those that appear in \fBy\fP, the exact definition is given by the 659 prelude function \fBlistdiff\fP. 660 .PP 661 The logical operators \fB|\fP, \fB&\fP do not evaluate their second operand 662 if this is not needed. 663 .RS 664 \fBa\ |\ b\fP 665 .RE 666 returns "TRUE" if \fBa\fP is "TRUE", otherwise it returns \fBb\fP. 667 Similarly 668 .RS 669 \fBa\ &\ b\fP 670 .RE 671 returns "FALSE" if \fBa\fP is "FALSE", otherwise it returns \fBb\fP. 672 .PP 673 The relational operators \fB>\fP, \fB>=\fP, \fB==\fP, \fB<=\fP, \fB<\fP have a special syntax which allows 674 continued relations, as commonly used in mathematics books. For example 675 .RS 676 \fB0 <= x <= 10\fP \ means \ \fB0 <= x & x <= 10\fP 677 .br 678 \fBa == b == c < 0\fP \ means \ \fBa == b & b == c & c < 0\fP 679 .RE 680 .PP 681 The operators \fB==\fP and \fB\\=\fP can be used to test for equality or inequality 682 on any pair of values, returning "TRUE" or "FALSE". Values of different types 683 are always unequal. Two lists count as equal if and only if they are of the 684 same length and (recursively for sublists) corresponding elements are equal. 685 .PP 686 Equality tests between functions give unpredictable results and should 687 not be used. 688 (Example: `\fBmap\ ==\ map\fP' has value "TRUE" but 689 `\fBmap\ abs\ ==\ map\ abs\fP' is "FALSE".) 690 .PP 691 The order testing operators \fB> >= <= <\fP work on numbers in the usual way and 692 on strings compare according to the C function \fIstrcmp()\fP. For 693 words all in upper case, or all in lower case, this amounts to dictionary order, 694 but be aware that upper case letters 695 precede lower case letters, so "ZEBRA"\ <\ "ant". It is an error to test 696 lists or functions for order, or two values of different type. 697 .PP 698 \fB + - * /\fP are the usual arithmetic operations, with \fB%\fP for remainder. 699 KRC arithmetic deals only with integers thus `\fB/\fP' discards the 700 fractional part, rounding towards \fB0\fP, while 701 \fBa % b\fP takes the remainder on dividing `\fBa\fP' by `\fBb\fP', 702 the sign of the result being that of `\fBa\fP' (these rules 703 for integer division and remainder are the same as C). 704 .PP 705 Prefix `\fB-\fP' reverses the sign of its integer operand (leaving \fB0\fP unchanged). 706 A negative constant like `\fB-1\fP' is, syntactically, an operator 707 expression and must be parenthesised when passed to a function, thus 708 `\fBf(-1)\fP' whereas `\fBf\ -1\fP' would attempt to subtract \fB1\fP 709 from \fBf\fP. Prefix `\fB+\fP' does nothing and is discarded. 710 .PP 711 \fBa ** b\fP raises `\fBa\fP' to the power of `\fBb\fP' which must be 712 non-negative. 713 .PP 714 The composition of two functions `\fBf\ .\ g\fP' is defined as follows 715 .RS 716 \fB(f . g) x \ = \ f (g x)\fP 717 .RE 718 .PP 719 The operator \fB#\fP gives the length of a list, for example `\fB#[1,2,3]\fP' 720 is \fB3\fP. To find the length of a string use the prelude function 721 \fBprintwidth\fP. 722 .PP 723 A prefix or infix operator in \fIsingle quotes\fP denotes the corresponding one- 724 or two-argument function. For example \fB\(fm+\(fm\fP is the addition function 725 and \fB\(fm#\(fm\fP and \fB\(fm\e\(fm\fP are functions 726 which take the length of a list and the negation of a truthvalue. 727 Note that \fB\(fm-\(fm\fP 728 is subtraction, for unary minus you can use the prelude function \fBneg\fP. 729 .SH ZF EXPRESSIONS 730 ZF expressions are a notation to generate lists from other lists. 731 (These would now called \fIlist comprehensions\fP, a 732 term coined by Phil Wadler in 1985.) 733 .PP 734 We start with some simple examples 735 .RS 736 \fB{n*n; n<-[1..]}\fP 737 .RE 738 is a list of all square numbers [1,4,9,16,25...]. The expression before 739 `;' is the \fIbody\fP of the ZF expression while `n<-[1..]' is called 740 a \fIgenerator\fP and `n' is a local variable of the ZF expression. The effect 741 is to create a list of the values taken by the body for each value of `n' 742 drawn from the list given in its generator. 743 .PP 744 The next example is a function for finding the factors of a number 745 .RS 746 \fBfactors n = {r; r<-[1..n/2]; n%r==0}\fP 747 .RE 748 This makes a list of the numbers between 1 and n/2 which divide n exactly. 749 The expression after the second semicolon is called a \fIfilter\fP \- only 750 those values of the generator are used for which the filter is "TRUE". 751 .PP 752 A ZF expression can have two or more generators, so 753 .RS 754 \fB{a+b; a<-[1,2,3]; b<-[10,20,30]}\fP 755 .RE 756 gives you a list of nine two-digit numbers. 757 .PP 758 Our last example finds 759 all positions on a chess board which are a knight's move from [x,y] 760 .RS 761 \fBknights_move [x,y] = {[i,j]; i,j<-[1..8]; (i-x)**2 + (j-y)**2 == 5}\fP 762 .RE 763 Searching the whole board in this way is not very efficient, but never mind. 764 Note that `i,j<-[1..8]' is shorthand for two generators with i, j 765 both drawn from [1..8]. 766 .PP 767 The general form of a ZF expression is 768 .RS 769 \fB{expression; qualifier; ... ; qualifier}\fP 770 .br 771 with one or more qualifiers, each of which is either a \fIgenerator\fP, of the form 772 .br 773 \ \ \ \ \ \ \ \ name-list <- expression 774 .br 775 or a \fIfilter\fP, which is an expression whose value is "TRUE" or "FALSE". 776 .RE 777 .PP 778 If the first qualifier is a generator, which is usually the case, 779 the initial `\fB;\fR' can be written `\fB|\fR', which aids readability. 780 .PP 781 For examples of programming with ZF expressions see 782 David Turner's papers "The Semantic Elegance of Applicative Languages'' (1981) 783 and "Recursion Equations as a Programming Language" (1982). 784 .PP 785 (\fBHistorical note\fR: The semantics of ZF expressions in KRC differ from 786 those of modern list comprehensions 787 in \fIinterleaving\fP outputs of multiple generators 788 to ensure that all combinations are eventually reached, 789 even with two or more infinite generators. The motivation was to make them behave 790 more like set comprehensions, whence the use of {}. List comprehensions 791 with square brackets and the now familiar "nested loop" semantics first appeared 792 in Miranda, in 1984.) 793 .SH THE PRELUDE 794 When KRC is started it first loads the \fBprelude\fP, a library of standard definitions, 795 most of which are in KRC but some are in machine code, including functions to access 796 the operating system (e.g. \fBread\fP, \fBwrite\fP). 797 .PP 798 To list the names defined in the currently loaded prelude during a KRC session, type 799 .RS 800 \fB/lib\fP 801 .RE 802 You can inspect any of the definitions by typing the name, e.g. 803 .RS 804 \fBmap\fP 805 .RE 806 Each has an comment explaining what it does, in addition to its defining equations. 807 .PP 808 The standard prelude is usually at \fB/usr/lib/krc/prelude\fP but may be placed 809 elsewhere by the installer. To view the standard prelude in a KRC session, say 810 "\fB/help prelude\fP". 811 .PP 812 Another library in place of the standard prelude can be specified 813 on the command line when KRC is invoked by the option \fB-l \fIlib\fR. 814 If you invoke KRC with option \fB-n\fP, no prelude is loaded.\"\fBchar__ chr__ explode__ function__ implode__ list__ number__ ord__ printwidth__ read__ seq__ string__ write__\fP 815 .PP 816 If KRC is invoked with option \fB-L\fR, a legacy prelude 817 is used in place of the standard one. To view this in a KRC session, say 818 "\fB/help lib1981\fP". 819 .PP 820 Note that without a prelude you cannot use ZF expressions, 821 whose implementation requires \fBinterleave\fP 822 nor can you use the `\fB--\fP' operator, which 823 requires the function \fBlistdiff\fP. 824 .SH LINE EDITING AND ESCAPE TO UNIX SHELL 825 \fBLine editing\fP: if KRC is compiled with the "linenoise" module, 826 the arrow keys and other keys can be used to scroll back and forth through 827 lines typed in a KRC session, to edit and resubmit them. 828 For a summary of available key bindings, with and without "linenoise", 829 say \fB/help keys\fP in a KRC session. 830 .PP 831 \fBEscape to Unix shell\fP: 832 type Ctrl-Z to suspend KRC and return to Unix command line, 833 say \fBfg\fP to resume the KRC session. 834 .SH MAKING UNIX COMMANDS 835 You can write a Unix command in KRC by making its script 836 executable through the "magic string" mechanism. To do this, 837 add a line as the start of the script, of the form: 838 .RS 839 #! /usr/bin/krc -e \fIexpression\fP! 840 .RE 841 where \fIexpression\fP is to be evaluated when 842 the program is run. This can be a KRC expression 843 of any complexity, terminated by `\fB?\fP' if its value is to be shown 844 with its structure or `\fB!\fP' if it is to be flat-printed. 845 .PP 846 Other flags such as "\fB\-l\ \fIlib\fR" for an alternative prelude, 847 "\fB\-h\ \fIsize\fR" for a larger heap, can precede "\fB-e\fP". 848 .PP 849 The name by which the script is called, followed by the command-line arguments 850 that the user supplies when it is run, 851 are placed in a list of strings called "\fBargv\fP". 852 .PP 853 Example: A simple command to display the contents of files. 854 Put the following 2 lines in a file called "list". 855 .RS 856 #! /usr/bin/krc -e main! 857 .br 858 main = map read (tl argv) 859 .RE 860 then make it executable 861 .RS 862 chmod +x list 863 .RE 864 now you can use it, for example 865 .RS 866 ./list list 867 .RE 868 will display the contents of the file itself. 869 .PP 870 Any KRC script can be made executable by placing a "magic string" at the start. 871 When used as the script in an interactive KRC session an initial line in `#!' 872 is treated as a comment and ignored; it has effect only if the file is invoked 873 as a command on the Unix command line. 874 .SH LANGUAGE CHANGES 875 The KRC language described here is as David Turner designed it around 1980, 876 except for the following changes. 877 .PP 878 The base for indexing lists has been changed from \fB1\fR to \fB0\fR. 879 The option \fB-z\fP reverts to lists being indexed from 1 (this may be 880 needed for legacy KRC scripts dating from the 1980's). 881 .PP 882 A revised prelude has been provided, with some more efficient definitions 883 (e.g. \fBreverse\fR, \fBsort\fP) and a more modern collection 884 of functions. 885 A legacy prelude from 1981 886 is also available (option \fB-L\fP). 887 .PP 888 Escape characters in strings, "\\n" etc., as in C, have been added. 889 KRC as originally designed used instead names for special characters: \fBnl\fP 890 \fBnp\fP \fBquote\fP \fBtab\fP \fBvt\fP, 891 these remain in the prelude. Example: 892 instead of \fB"123\\tgo\\n"\fP you can say \fB["123",tab,"go",nl]\fP 893 to get the same effect with ``!''. 894 .PP 895 A distinction has been introduced between `\fB=\fP', definitional equals 896 and `\fB==\fP' the equality test (KRC originally used `\fB=\fP' for both). 897 .PP 898 In-line comments, from "||" to end of line, have been added, thus 899 .RS 900 || this is a comment 901 .RE 902 these don't fit very naturally with KRC's model of interactive script 903 development as they are discarded when entered during a 904 session. But the facility is useful for scripts prepared with an editor as 905 it allows comments on individual equations and on the whole script. 906 .SH LEGACY SYNTAX 907 With option \fB-z\fP these alternative operator forms are accepted 908 and converted to their standard variants: 909 .RS 910 \fB~\fR as a synonym for \fB\e\fR (prefix \fInot\fR) 911 .br 912 \fB~=\fR as a synonym for \fB\e=\fR (\fInot-equals\fR) 913 .br 914 \fB=\fR as a synonym for \fB==\fR (\fIequality test\fR) 915 .RE 916 .SH LIMITATIONS 917 Guards do not work correctly with simple definitions, for example 918 .RS 919 feb = 29, leap_year 920 .br 921 \ \ \ \ = 28 922 .RE 923 fails with strange error when leap_year="FALSE". 924 The language as originally defined did not allow guards with simple 925 definitions, only with functions. The syntactic restriction has been removed 926 but the corresponding semantics still needs fixing. 927 .PP 928 The length of a string limited to 255 characters. 929 The space used by strings created during a session is never freed, 930 mitigated only by the fact that multiple copies of the same 931 string are shared. This means that programs which create a 932 lot of temporary strings as part of their operation 933 will soon run out of the space in which strings, 934 identifiers, file names and comments are stored. Note, however, 935 that KRC's ``\fB!\fP'' output mode removes much of the need to create 936 temporary strings. 937 .PP 938 Numbers are limited in range to that of the underlying processor's 939 machine word, i.e. they are signed 32-bit or 64-bit integers. 940 Calculations which exceed this range cause a run-time error. 941 .PP 942 If linenoise is enabled, multiline comments cannot be entered interactively 943 in a KRC session. 944 .SH FILES 945 .TP 946 \fB/usr/lib/krc/prelude\fP 947 The standard prelude. 948 .TP 949 \fB/usr/lib/krc/lib1981\fP 950 A legacy prelude dating from 1981 (invoked by option -L). 951 .PP 952 KRC looks for the prelude first in \fB./krclib\fP if present, 953 then in \fB/usr/lib/krc\fP (this may be changed by the installer). 954 .SH SEE ALSO 955 .TP 956 \fBhttp://krc-lang.org/\fP 957 The KRC home page. 958 .TP 959 \fBRecursion Equations as a Programming Language\fP, D. A. Turner, January 1982 960 This includes an overview of the KRC language and can be found at the above website. 961 .TP 962 \fBhttp://github.com/antirez/linenoise\fP 963 The "linenoise" line-editing module (the version included with the KRC sources has 964 been lightly edited to configure it appropriately). 965 .SH AUTHOR 966 The KRC system was designed by David Turner 967 who implemented it in BCPL for the EMAS operating system from 968 November 1979 to October 1981. 969 .PP 970 This implementation was created by translating the original BCPL sources into C for 971 the Unix family of operating systems. 972 .PP 973 KRC is Copyright (c) D. A. Turner 1981 and is released under an open source license, 974 for terms see the file "COPYING" included in the distribution.