home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format 52 / af052sub.adf / false.lha / False / false.doc < prev    next >
Encoding:
Text File  |  1993-07-17  |  17.5 KB  |  585 lines
  1.  
  2.                          The FALSE Programming Language
  3.  
  4.                            by Wouter van Oortmerssen
  5.  
  6.                                     Manual
  7.  
  8.  
  9. WHAT'S NEW in v1.1
  10. - one bug fix
  11. - other example sources (mainly written by Eelko, in the "other" dir.)
  12. - Portable False Interpreter/Debugger!
  13.   (read comments in the source for more infos)
  14.  
  15.  
  16. +-------------------------------+
  17. |    Introduction:        |
  18. +-------------------------------+
  19.  
  20. The language FALSE and it's compiler were designed for only two reasons:
  21. - building a working compiler in just 1k (!)
  22. - designing a language that looks cryptic and fuzzy (in the APL tradition)
  23.  
  24. the result is a language that is quite powerfull (for it's size).
  25. It's a Forth type language with lambda abstraction and lots of other goodies.
  26. I named the language after my favourite truthvalue.
  27.  
  28. NOTE: a) the compiler as well as the generated code need kickstart v37+
  29.       b) You're strongly advised to read this entire manual before
  30.          trying to operate the compiler.
  31.  
  32. +-------------------------------+
  33. |    The implementation:    |
  34. +-------------------------------+
  35.  
  36. To compile a FALSE program, type "false" followed by the source-code
  37. name, like:
  38.  
  39. 1> false helloworld.f
  40.  
  41. the compiler produces an executable called "a.out" in the same dir:
  42.  
  43. 1> a.out
  44. Hello, World!
  45. 1>
  46.  
  47. To squeeze the real compilation functions for all language elements in
  48. 1024 bytes, some things had to go: there are no error messages, and even
  49. worse: there are no syntax error checks. Luckily, the language is
  50. designed so that it's hard to make compile-time errors.
  51.  
  52. the compiler only signals an error in the following events:
  53. - it could not allocate memory
  54. - it could not read the source file
  55. - it could not write the executable
  56. - it could not open dos.library (very unlikely)
  57. - it found a symbol in the source, which isn't part of the language.
  58.  
  59. an error is signalled by returning value 10 instead of 0, it is
  60. therefore wise to have your cli-prompt display return values ("%R")
  61.  
  62. note: the compiler will start acting weird as soon as you try
  63. to compile sources or produce executables >32k
  64.  
  65. Working with FALSE
  66. ------------------
  67. It is actually possible to write small utilities and stuff in FALSE,
  68. and quite powerfull too once you see how to use stacks and lambda
  69. functions etc. However, with a minimal compiler like this it's hard to
  70. find errors, and I suppose you really have to be a Forth hacker or a
  71. hardcore programmer to get the most of it.
  72.  
  73. Helloworld in FALSE:
  74. --------------------
  75.  
  76. "Hello, World!
  77. "
  78.  
  79. (yes, that's all...).
  80. And this is the fac() function definition in FALSE:
  81.  
  82. [$1=$[\%1\]?~[$1-f;!*]?]f:
  83.  
  84. (fuzzy eh? we'll explain that later...)
  85.  
  86.  
  87. +-------------------------------+
  88. |    FALSE: The Language.    |
  89. +-------------------------------+
  90.  
  91. Format of the language:
  92. -----------------------
  93. FALSE sources are totally free-format, i.e you may have any number
  94. of tabs/spaces/lf's between two symbols. comments start with "{",
  95. end with "}" and may not be nested.
  96.  
  97.  
  98. evaluation:
  99. -----------
  100. FALSE inherits its way of evaluating expressions from Forth, so it
  101. really helps if you know that language, but for those who don't:
  102.  
  103. All elements in the language are defined by what they push on and/or
  104. pop from the stack. for example, a number like "1" or "100" simply
  105. pushes it's own value on the stack. An operator like "+" takes the
  106. two top elements of the stack, adds them, and pushes back the result:
  107.  
  108. 1 2 + 4 *    { (1+2)*4 }
  109.  
  110. the result of this expression is "12". We will use the notation
  111. (<pops>-<pushes>) to signify what a function does, so "1" does (-num)
  112. and "+" does (n1,n2-result)
  113.  
  114. complex expressions will keep lots of intermediate results on the stack,
  115. so mostly there's no need for local variables. FALSE doesn't even
  116. have expressions or statements; more likely a program is one stream
  117. of symbols that  manipulate the stack. It's very helpfull when you
  118. can imagine what the stack looks like in a particular part of the program
  119. when programming.
  120.  
  121.  
  122. elementary functions:
  123. ---------------------
  124.  
  125. available are:
  126.  
  127. "+"    "-"    "*"    "/"    "_"
  128.  
  129. these function as usual. "_" is the unary minus.
  130.  
  131.  
  132. "="    ">"
  133.  
  134. these result in 0 (false) or -1 (true)
  135.  
  136. unequal is "=~", and smaller than etc. can be made by swapping arguments
  137. and/or using "~"
  138.  
  139. example:    a;1_=~        { a<>-1 }
  140.  
  141.  
  142. "&"    "|"    "~"
  143.  
  144. "and", "or" and "not", as usual.
  145.  
  146. example:    a;0>a;99>~&    { (a>0) and (a<100) }
  147.  
  148.  
  149. values:
  150. -------
  151.  
  152. values are either integers like discussed before ("1", "100" etc.),
  153. or characters precede by a quote: 'A (equals 65) (do not mix up with
  154. backquote "`" !)
  155. note that the 1k parser only parses integers up to 320000, it uses
  156. full 32bit representation for them, however.
  157.  
  158.  
  159. global variables:
  160. -----------------
  161. variables to store values are less needed in FALSE than in other
  162. languages. in FALSE they are used mostly for functions, explained
  163. below.
  164.  
  165. a variable is a character "a" to "z" (just these).
  166. ":" is the assignment function, and ";" is contrary: it gets the
  167. variable's value:
  168.  
  169. 1a:    { a:=1 }
  170. a;1+b:    { b:=a+1 }
  171.  
  172. i.e: "a;" is used where in other languages you would just write "a"
  173.  
  174. all variables (and also stack-items) are 32bits.
  175.  
  176. lambda functions:
  177. -----------------
  178. a FALSE lambda function is a piece of code between []. for example:
  179.  
  180. [1+]
  181.  
  182. is a function that add 1 to it's argument. A function is really defined
  183. by what it takes from the stack (in this case the first arg to "+"), and
  184. what it puts back, just like builtin functions. Note that FALSE lambda
  185. functions are not restricted to just one return value.
  186.  
  187. what a [] expression really does, is push the function. this means in
  188. practise that it can be given to yet another function as argument etc.,
  189. just like in functional languages. The symbol "!" is called "apply",
  190. and applies a function to it's arguments, for example:
  191.  
  192. 2[1+]!
  193.  
  194. would result in "3"
  195. This wouldn't make much sense, since what you really want is define the
  196. function once, and then use it all-over. this is easy:
  197.  
  198. [1+]i:
  199.  
  200. this defines the function "i" (actually, it assign the function to "i"),
  201. so that it can be used simply by applying "i" to it's arguments:
  202.  
  203. 2i;!
  204.  
  205. WARNING: as with all other elements in FALSE, but even more important
  206.          with functions: the 1k compiler does not check if symbols like
  207.          "!" really get a function as argument (so "1!" means trouble),
  208.          the compiler may even crash if you don't balance your [ and ].
  209.  
  210.  
  211. stack functions:
  212. ----------------
  213.  
  214. "$"    (x-x,x)            dup:    duplicate topmost stackitem
  215. "%"    (x-)            drop:    delete topmost stack item
  216. "\"    (x1,x2-x2,x1)        swap:    swap to topmost stack-items.
  217. "@"    (x,x1,x2-x1,x2,x)    rot:    rotate 3rd stack item to top.
  218. "ø"    (n-x)            pick:    copy n-th item to top (0ø equals $)
  219.  
  220. examples:
  221.  
  222. 1$        equals        1 1
  223. 1 2%        equals        1
  224. 1 2\        equals        2 1
  225. 1 2 3@        equals        2 3 1
  226. 7 8 9 2ø    equals        7 8 9 7
  227.  
  228.  
  229. control structure:
  230. ------------------
  231. FALSE only has an IF and a WHILE.
  232. if is "?", and looks like this: (bool,fun-). example:
  233.  
  234. a;1=["hello!"]?        { if a=1 then print "hello!" }
  235.  
  236. the first argument is a boolean value, the second the lambda function
  237. to be executed (see below for "")
  238. there's no "else", so you'll have to mimic this with a second "?".
  239. this can be easily done by copying the truthvalue:
  240.  
  241. a;1=$["true"]?~["false"]?
  242.  
  243. after the first "?" (wether it's executed or not), a copy of the truthvalue
  244. is still on the stack, and we negate it for the else part.
  245. Beware that if the first "if" needs arguments on the stack from before
  246. the boolean expression, it's top is still the truthvalue.
  247.  
  248. While is a "#", and gets two lambda functions as args, one that results in
  249. a boolean, and the second as body:
  250.  
  251. [a;1=][2f;!]#        { while a=1 do f(2) }
  252.  
  253. note that with while, if and lambda's, you can build virtually
  254. any other control structure.
  255.  
  256.  
  257. Input/Output:
  258. -------------
  259.   watch out: all these are BUFFERED.
  260.  
  261. - strings printing: strings simply print themselves. Special: strings in FALSE
  262.   may contain <lf>'s, that explains why in the helloworld program, the second
  263.   " is on the next line:
  264.  
  265.   "Hello, World!
  266.   "
  267.  
  268. - integers: "." prints the topmost stack item as integer value:
  269.  
  270.   123.        { prints string "123" on console }
  271.  
  272. - characters: ","
  273.  
  274.   65,        { prints "A" }
  275.  
  276. - reading a character from stdin: "^"
  277.  
  278.   ^        { top stack is char read }
  279.  
  280. - flush: "ß"
  281.   when stdin and stdout are different (i.e. you started your compiled
  282.   FALSE program with <infile >outfile you will hardly need to flush, however,
  283.   if you both use "^" and the output operations on the same console,
  284.   you may need to flush between input and output.
  285.   "ß" flushes both input and output.
  286.  
  287.   ß[^$1_=~][,]#        { while c:=getc()<>EOF do putc(c) }
  288.  
  289.   for example, above program copies input to output until eof,
  290.   so no flushing is needed after every read when used with two
  291.   files, however:
  292.  
  293.   "press return:"ß^%ß"continuing..."
  294.  
  295.   it is, since we get input on the same console as the output.
  296.  
  297.  
  298. +-------------------------------+
  299. |    Example programming    |
  300. +-------------------------------+
  301.  
  302. How the $#%! am I going to write a decent program with all this, you may ask.
  303. Well, the first barrier one has to take into account, is that FALSE doesn't
  304. support any amiga-specific programming, some io-functions is as far as
  305. it gets. However, with those, you can create some stunningly compact
  306. utilities, for example the FALSE version of the "copy" command we saw above,
  307. in just 13 bytes!
  308.  
  309. ß[^$1_=~][,]#
  310.  
  311. ok, what happens: first recognise the four main parts in this program,
  312. we have a flush, then two arguments and then a while. The first []
  313. function is supposed to deliver the boolean for the while: it reads
  314. a character, duplicates it, the compares it it with -1 (EOF). at the end
  315. of this function, we do not only have a boolean, but also an extra copy
  316. of the character we read. This immediately demonstrates a powerfull
  317. feature of FALSE: we can have any number of interim-results on the
  318. stack. the body of the while loop [,] just prints the character to
  319. stdout.
  320. Note that if the body is not executed, we leave with a non-empty stack.
  321. This is no problem at the end of a program, however, doing this within an
  322. iteration would be fatal.
  323.  
  324.  
  325. another example of FALSE programming: the fac() function.
  326.  
  327. [$1=$[\%1\]?~[$1-f;!*]?]f:
  328.  
  329. thus we call fac(6) (=720) like:
  330.  
  331. 6f;!
  332.  
  333. no range checking is done by the "f" function, that is what
  334. is done by the fac.f example program.
  335.  
  336. Well, how does it work? (does it?) First recognise the f;! within
  337. the function implementation: that's the recursion. Let us recall what
  338. fac() looks like in a hypotheticall procedural/functional programming
  339. language:
  340.  
  341. fac(n) = if n=1 then 1 else n*fac(n-1)
  342.  
  343. our FALSE code goes just along these lines, only we use two "if"'s (hence
  344. the two [] blocks) insteas of one if-then-else.
  345. we start with (n-) on the stack:
  346.  
  347. $1=$
  348.  
  349. duplicate the n, and compare it with 1, and leave a second truthvalue (t),
  350. thus: (n,t,t-)
  351.  
  352. [\%1\]?
  353.  
  354. first push the [], and after the "if" (=?) we have (n,t-). we won't
  355. be needing the lower n anymore, so we swap and drop. then we push the
  356. final result "1", and swap it below the truthvalue for the second "if".
  357. (1,t-)
  358.  
  359. ~[$1-f;!*]?
  360.  
  361. we first have to negate the truthvalue, because this is the else part.
  362. in the "if"-body, we have just (n-), and we add a "n-1" to that as argument
  363. for the recusive call. after f;! we have (n,r-) (r is result of the call),
  364. and we simply multiply the two together as result of the whole.
  365.  
  366. this may look all awfully complicated, but infact, it isn't. it's
  367. just a very different style of programming. once you fully understand
  368. it's power, you won't want to live without it :-)
  369.  
  370. if by now you haven't understood zip of how FALSE works, this probably
  371. isn't the language for you. however, if you got the slightest feeling
  372. that some things are getting clear to you, try understanding the examples,
  373. and your on your way of becoming a real FALSE programmer ! :-). however,
  374. the examples are not heavily commented, as that is considered bad-taste
  375. in FALSE (see some section below).
  376.  
  377.  
  378. +-------------------------------+
  379. |    FALSE wizards corner    |
  380. +-------------------------------+
  381.  
  382. "Inline assembly" in FALSE:
  383. -------------------------
  384.  
  385. one topic has been kept undiscussed (on purpose), and it's the
  386. possibility to add assembly code to a FALSE program, to allow it to
  387. be extended with custom functions.
  388.  
  389. syntax:        <integer>`
  390.  
  391. any integer value 0..65535 folowed by a backquote. an expression like
  392. this causes the a 16bit value to be put directly into the code.
  393. A series of backquoted values may allows you a primitive form of
  394. inline assembly. for example:
  395.  
  396. [8221`29184`9336`4`50510`20142`65338`50510`11008`]a:    { allocmem (size-mem) }
  397. [8221`8797`9336`4`50510`20142`65326`50510`]f:        { freemem (mem,size-) }
  398.  
  399. are two assembly functions that allow you to allocate memory
  400. from within FALSE (see example alloc.f)
  401.  
  402. register conventions:
  403. when writing assembly code for use with FALSE, use following registers:
  404.  
  405. A6 = dosbase
  406. A5 = evaluation stack. use MOVE.L (A5)+,D0 to read a paramenter into D0,
  407.      and MOVE.L D0,-(A5) to write one.
  408. A4 = variables. 0(A4) = a, 4(A4) = b etc.
  409. D6 = stdout
  410. D5 = stdin
  411.  
  412. example code for allocmem/freemem above:
  413.  
  414. alloc:    move.l    (a5)+,d0
  415.     moveq    #0,d1
  416.     move.l    4.w,a2
  417.     exg    a2,a6        ; we need to restore dosbase later.
  418.     jsr    -198(a6)
  419.     exg    a2,a6
  420.     move.l    d0,-(a5)    ; no rts, that's done by []
  421.  
  422. free:    move.l    (a5)+,d0    ; second argument first!
  423.     move.l    (a5)+,a1
  424.     move.l    4.w,a2
  425.     exg    a2,a6
  426.     jsr    -210(a6)
  427.     exg    a2,a6
  428.  
  429.  
  430. peek/poke:
  431. ----------
  432.  
  433. ":" and ";" are operators to read and write variables, but they can be
  434. (mis-)used to do arbitrary peek and poking, even array-indexing!
  435. (see vcheck.f for an example: we read execbase)
  436.  
  437. array indexing and structure reading:
  438. if p is a pointer to an array/structure, then:
  439.  
  440. p;<index>+;
  441.  
  442. reads p[<index>].
  443.  
  444. unfortunately, this way you can only read 32bit values.
  445.  
  446. cli arguments:
  447. --------------
  448.  
  449. reading files is mostly done with redirection on the commandline, however,
  450. for future extensability, a pointer to the command-line arguments is
  451. passed in var a. see also "command line tips" below.
  452.  
  453. stack:
  454. ------
  455.  
  456. you can use the stack as a buffer, and reverse-indexing the values
  457. on it with ø. however, the FALSE stack is the lower-half of the normal
  458. amigados stack, and thus normally only 2k. You can write programs
  459. that need arbitrarily large stack-buffers by increasing the stack
  460. size before running.
  461.  
  462. command line tips:
  463. ------------------
  464.  
  465. - make sure you write an input redirection when testing some
  466.   programs: if the program simply does "nothing", than the
  467.   computer is not hung, but it's simply waiting for input.
  468. - if you do not write a flush (ß) at the start of a program that
  469.   processes the input to the output, you will get a <lf> as
  470.   first input: this is actually the commandline. example:
  471.  
  472.   a.out blabla <in >out
  473.  
  474.   then a.out will first read "blabla" as a line, then the contents
  475.   of "in".
  476.  
  477.  
  478. good style:
  479. -----------
  480.  
  481. programming in FALSE has a certain kind of taste: it's not easy, but
  482. when it works, it works good, and the resulting sources look great.
  483. Therefore, it may be tempting to "indent" while-loops in larger
  484. programs, but remember:
  485. - indentation, spacing and comments are for wimps :-)
  486. - real FALSE programmmers:
  487.   - write dense code
  488.   - write only very "global" comments.
  489.   - use the stack intensively, and thus dislike to use variables
  490.     for other purposes than function definitions.
  491.  
  492.  
  493.  
  494. +---------------------------------------+
  495. |    FALSE language overview.    |
  496. +---------------------------------------+
  497.  
  498. syntax:        pops:        pushes:        example:
  499.         -->top        -->top
  500. --------------- --------------- --------------- -------------------------------
  501.  
  502. {comment}    -        -            { this is a comment }
  503. [code]        -        function    [1+]    { (lambda (x) (+ x 1)) }
  504. a .. z        -        varadr        a    { use a: or a; }
  505. integer        -        value        1
  506. 'char        -        value        'A    { 65 }
  507. num`        -        -        0`    { emitword(0) }
  508.  
  509. :        n,varadr    -        1a:    { a:=1 }
  510. ;        varadr        varvalue    a;    { a }
  511. !        function    -        f;!    { f() }
  512.  
  513. +        n1,n1        n1+n2        1 2+    { 1+2 }
  514. -        n1,n2        n1-n2        1 2-
  515. *        n1,n2        n1*n2        1 2*
  516. /        n1,n2        n1/n2        1 2/
  517. _        n        -n        1_    { -1 }
  518.  
  519. =        n1,n1        n1=n2        1 2=~    { 1<>2 }
  520. >        n1,n2        n1>n2        1 2>
  521.  
  522. &        n1,n2        n1 and n2    1 2&    { 1 and 2 }
  523. |        n1,n2        n1 or n2    1 2|
  524. ~        n        not n        0~    { -1,TRUE }
  525.  
  526. $        n        n,n        1$    { dupl. top stack }
  527. %        n        -        1%    { del. top stack }
  528. \        n1,n2        n2,n1        1 2\    { swap }
  529. @        n,n1,n2        n1,n2,n        1 2 3@    { rot }
  530. ø (alt-o)    n        v        1 2 1ø    { pick }
  531.  
  532.  
  533. ?        bool,fun    -        a;2=[1f;!]?
  534.                         { if a=2 then f(1) }
  535. #        boolf,fun    -        1[$100<][1+]#
  536.                         { while a<100 do a:=a+1 }
  537.  
  538. .        n        -        1.    { printnum(1) }
  539. "string"    -        -        "hi!"    { printstr("hi!") }
  540. ,        ch        -        10,    { putc(10) }
  541. ^        -        ch        ^    { getc() }
  542. ß (alt-s)    -        -        ß    { flush() }
  543.  
  544.  
  545.  
  546. +-------------------------------+
  547. |    additional infos    |
  548. +-------------------------------+
  549.  
  550. FALSE was created for fun, just to see how small a compiler I could
  551. write while still compiling a relatively powerfull language.
  552. The result is even better than I thought: it's great fun to
  553. program in FALSE, and it looks even better.
  554.  
  555. about the compiler source: note that throughout the program ALL
  556. variables reside in registers without saving on the stack!
  557. please: don't come and tell me you found a way to reduce
  558. the size of the executable by 4 more bytes... I think it's small
  559. enough as it is now. If you enjoy compilers just because of
  560. their lenght, make sure you get a look at the "brainfuck"
  561. language by Urban Mueller in less than 256 bytes!
  562.  
  563. Donations? who would want to give something for a program that
  564. has the size of a bootblock virus? anyway, the only thing I'd
  565. like to receive is large and complex FALSE sources (of working
  566. applications, of course). Please always put a comment at the
  567. top of your source, otherwise you'll give me a hard time guessing
  568. if it's FALSE or uuencoded. don't ask me to debug your code, as
  569. understanding other peoples FALSE programs is horrible.
  570.  
  571. If you want to contact me:
  572.  
  573.  
  574.     Wouter van Oortmerssen ($#%!)
  575.     Levendaal 87
  576.     2311 JG  Leiden
  577.     HOLLAND
  578.  
  579. or better if you have access to Email:
  580.  
  581.     Wouter@alf.let.uva.nl        (E/FALSE etc. programming support)
  582.     Wouter@mars.let.uva.nl        (personal)
  583.     Oortmers@gene.fwi.uva.nl    (other)
  584.  
  585.