home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / CONTRIB / LISP / DOC.TXT < prev    next >
Text File  |  1994-10-25  |  16KB  |  477 lines
  1. Sather Lisp
  2.  
  3. Robert Griesemer
  4. International Computer Science Institute, Berkeley
  5. gri@icsi.berkeley.edu
  6.  
  7. August 17, 1994
  8.  
  9.  
  10. 1. Introduction
  11.  
  12. Sather Lisp is a primitive Lisp interpreter completely written in Sather 1.0.
  13. Currently no local function definitions are possible, and therefore no higher
  14. order functions can be defined directly (i.e., local lambda's do not work
  15. correctly). However, arbitrary long integers and rational numbers are fully
  16. supported.
  17.   Sather Lisp serves as an example for a non_trivial but still comprehensible
  18. Sather 1.0 application. Its simplicity lead to a small and straightforward
  19. implementation (less than 1000 lines of code, including comments and empty
  20. lines), but the interpreter is still powerful enough to give valuable insights
  21. into the principles of list processing. It can either be used to learn Sather
  22. by studying a concrete application, or to get a glance of list processing by
  23. studying the implementation details.
  24.   This documentation is only a brief description of the interpreter
  25. functionality (its user interface) and is not intended as a Lisp tutorial. The
  26. reader is referred to the standard literature for a more thourough introduction 
  27. into the topic (e.g., P.H. Winston and B.K.P. Horn (1984), Lisp, 2nd edition,
  28. Addison_Wesley).
  29.  
  30.  
  31. 2. Usage
  32.  
  33. The Sather Lisp implementation consists of the file Lisp.sa and the necessary
  34. Sather library files. After compilation with:
  35.  
  36. cs Lisp.sa -main LISP -o Lisp <CR>
  37.  
  38. (assuming SATHER_COMMANDS set correctly), the Lisp interpreter can be started:
  39.  
  40. Lisp <CR>
  41. Sather Lisp - gri 15 Aug 94
  42. (symbols) returns a list of all defined symbols
  43. > 
  44.  
  45. The '>' prompt signals that the interpreter is ready for input. The
  46. interpreter accepts any sequence of Lisp expressions as input and evaluates
  47. them consecutively. The output is the result of the last evaluated expression
  48. (unless an error occured before). The program can be left by typing in Ctrl_D
  49. (indicating end of file) or by using the predefined function exit:
  50.  
  51. > (exit) <CR>
  52.  
  53.  
  54. 3. Expression syntax
  55.  
  56. The Sather Lisp syntax is described using an Extended Backus_Naur Formalism
  57. (EBNF): brackets [ and ] denote optionality of the enclosed sentential form,
  58. braces { and } denote its repetition (possibly zero times). Alternative forms
  59. are separated by vertical bars |. Syntactic entities (non_terminal symbols) are 
  60. denoted by English words starting with a capital letter (the only one is
  61. Expression). Tokens of the language vocabulary (terminal symbols) are either
  62. denoted by English words starting with a small letter (e.g., number), or are
  63. denoted by strings enclosed in double quotes (e.g., "."). No white space may
  64. appear within tokens. However, arbitrary white space and comments may appear
  65. between tokens. Comments are denoted by the curly braces { and } and may be
  66. nested.
  67.  
  68. Expression  =  "'" Expression |
  69.     "(" {Expression} ["." Expression] ")" |
  70.     symbol | number | string.
  71.  
  72. symbol  =  letter {letter | digit} |
  73.     special {special}.
  74. number  =  ["-"] digit {digit} ["/" digit {digit}].
  75. string  =  """ char """.
  76.  
  77. letter  =  "A" | "B" ... "Z" | "a" | "b" ... "z".
  78. digit  =  "0" | "1" ... "9".
  79. special  =  "!" | "#" | "$" | "%" | "&" | "*" | "+" | "-" | "/" | ":" |
  80.     "<" | "=" | ">" | "?" | "@" | "\\" | "^" | "|" | "~".
  81. char  =  any printable character except "
  82.  
  83. Examples:
  84.  
  85. -1234  (negative) integer
  86. 7/31  (positive) rational number
  87. "This is a string"  string
  88. ()  empty list, nil
  89. myFunc  symbol
  90. <=  (special) symbol
  91. 'a  quoted symbol
  92. (a (b 3/4 c) d)  list consisting of 3 elements
  93. (a . b)  dotted pair
  94. (a b c (u v w) x . d)  list terminated with dotted pair
  95. (a . (b . (c . ()))) = (a b c)  equivalence of dotted pair and list notation
  96.  
  97. Note: The negative sign of a number must be immediately before the first digit 
  98. and must not be preceeded by another special character, otherwise it is
  99. interpreted as (special) symbol. 'x is a shortcut for (quote x) (unless quote
  100. has been redefined).
  101.  
  102.  
  103. 4. Expression evaluation
  104.  
  105. Sather Lisp evaluates a list by first evaluating its first element (which must 
  106. evaluate to a function) and then applying the function to the remaining list.
  107. Whether the arguments are evaluated or not depends on the function; e.g., quote 
  108. (') never evaluates its (single) argument, but setq evaluates only its second
  109. argument, and + evaluates all its arguments, etc. Symbols evaluate to their
  110. bound values, which may be assigned using set or setq. Initially, they evaluate 
  111. to nil. Numbers, strings and functions evaluate to themselves. Truth values are 
  112. denoted by the empty list (i.e., nil) and non_nil values. The empty list (nil)
  113. stands for "false", and any non_nil value stands for "true". Usually the
  114. predefined symbols nil and t (which evaluate to the empty list () and t,
  115. respectively) are used to represent "false" and "true". In order to avoid
  116. confusion, they shouldn't be redefined. If they are, (setq nil ()) and (setq t
  117. 't) re_establishes their default values.
  118.  
  119. Examples:
  120.  
  121. 1234  ^  1234
  122. "hello world"  ^  "hello world"
  123. (+ 1 2 3 4 5 6 7 8 9 10)  ^  55
  124. '(a . b)  ^  (a . b)
  125. car  ^  [car]  ([...] denotes functions)
  126. (cons 'a 'b)  ^  (a . b)
  127. (car (cons 'a 'b))  ^  a
  128. (cdr (cons 'a 'b))  ^  b
  129. (cdr '(a b))  ^  (b)
  130. (setq a 4/6)  ^  2/3
  131. a  ^  2/3
  132. (lambda (x) (+ x 1))  ^  [((+ #0 1))]  (#i denotes argument no. i)
  133. ((lambda (x) (+ x 1)) 1)  ^  2
  134. (setq inc (lambda (x) (+ x 1)))  ^  [inc]
  135. (inc 1)  ^  2
  136.  
  137.  
  138. 5. Predefined functions
  139.  
  140. Several functions are predefined in Sather Lisp. Since predefined functions
  141. are bound to ordinary symbols, (the values of) these symbols may be redefined
  142. if desired (and the old function is lost unless it is bound to another symbol,
  143. too). User defined functions may be added (or redefined, resp.) by binding
  144. lambda expressions to symbols (see Section 6). A list of all symbols known to
  145. the system is obtained using (symbols). The following table gives a brief
  146. definition of all predefined functions.
  147.  
  148. Expression  Result  Constraints
  149.  
  150.  
  151. (+ arg0 arg1 [... argn])  (arg0 + arg1) + ... + argn  (numbers only)
  152. (- arg0 arg1 [... argn])  (arg0 - arg1) - ... - argn  (numbers only)
  153. (* arg0 arg1 [... argn])  (arg0 * arg1) * ... * argn  (numbers only)
  154. (/ arg0 arg1 [... argn])  (arg0 / arg1) / ... / argn  (numbers only)
  155. (% arg0 arg1 [... argn])  (arg0 % arg1) % ... % argn  (numbers only)
  156. (^ arg0 arg1 [... argn])  (arg0 ^ arg1) ^ ... ^ argn  (numbers only)
  157.  
  158. (= arg0 arg1 [... argn])  arg0 = arg1 = ... = argn  (numbers and strings only)
  159. (# arg0 arg1 [... argn])  arg0 # arg1 # ... # argn  (numbers and strings only)
  160. (< arg0 arg1 [... argn])  arg0 < arg1 < ... < argn  (numbers and strings only)
  161. (<= arg0 arg1 [... argn])  arg0 <= arg1 <= ... <= argn  (numbers and strings
  162. only)
  163. (> arg0 arg1 [... argn])  arg0 > arg1 > ... > argn  (numbers and strings only)
  164. (>= arg0 arg1 [... argn])  arg0 >= arg1 >= ... >= argn  (numbers and strings
  165. only)
  166.  
  167. (! arg)  factorial of floor(arg)  (numbers only)
  168. (floor arg)  floor of arg  (numbers only)
  169. (ceiling arg)  ceiling of arg  (numbers only)
  170.  
  171. (car arg)  head of arg  (arg must be a list)
  172. (cdr arg)  tail of arg  (arg must be a list)
  173. (cons arg0 arg1)  (arg0 . arg1)
  174. (atom arg)  t if arg is not a pair, () otherwise
  175. (eq arg0 arg1)  arg0 = arg1  
  176.  
  177. 'arg  shortcut for (quote arg)
  178. (quote arg)  returns arg without evaluation
  179. (eval arg)  evaluates the value of arg
  180.  
  181. (set sym arg)  binds the value of arg to the symbol sym
  182. (setq arg0 arg1)  binds the value of arg1 to the symbol value of arg1
  183.  
  184. (write arg)  writes arg to stdout and returns arg
  185. (writeLn)  starts a new line to stdout and returns ()
  186.  
  187. (lambda ...)  see Section 6
  188. (cond arg0 [arg1 ... argn])  each argument is considered to be a list consisting 
  189. of
  190.   a condition (which evaluates to nil or non_nil) and
  191.   a sequence of expressions. cond evaluates the first
  192.   sequence of expressions for which its condition is
  193.   evaluated to a non_nil value. The result of cond
  194.   is the last expression evaluated (see examples).
  195.  
  196. (readFile arg)  reads and evaluates file arg  (arg must be a string)
  197. (tracer arg)  arg = on: turns tracing output on and returns on
  198.   arg # on: turns tracing output off and returns off
  199. (tracer)  actual tracing mode (on or off)
  200. (symbols)  returns list of all known symbols
  201. (exit)  exits the interpreter
  202.  
  203. Note: Use = for comparison of numbers and strings; eq does only a pointer
  204. comparison, thus (eq 1 1) # t!
  205.  
  206.  
  207. 6. Function definition
  208.  
  209. New functions can be created using the lambda function. lambda expects a
  210. parameter list and a sequence of expressions. Three syntactic variants exist:
  211.  
  212. a) (lambda x expr0 expr1 ... exprm)
  213. b) (lambda (par0 par1 .. parn-1) expr0 expr1 ... exprm)
  214. c) (lambda (par0 par1 .. parn-1 . x) expr0 expr1 ... exprm)
  215.  
  216. a) This corresponds to case c) with n = 0.
  217. b) The function expects n parameters which are hold in par0 to parn-1. The
  218. result of a function invocation is the value of the last expression exprm
  219. evaluted using the parameter values (i.e., the parameters are evaluated before
  220. the expri's are evaluated). Symbols that are not parameters are considered to
  221. be global.
  222. c) The function expects at least n parameters. The values of the first n
  223. parameters are hold in par0 to parn-1 (i.e., these parameters are evaluated
  224. before the expri's are evaluated), the remaining parameter list is hold in x
  225. (i.e., the last parameter is not evaluated prior to evaluation of the expri's).
  226.  
  227. Variant a) and c) can be used to implement functions that accept variable long
  228. argument lists or functions that do only partially evaluate their arguments.
  229. For instance, quote could be defined by (setq quote (lambda x (car x))). The
  230. ReadFiles function definition in the example section below is another
  231. application of this feature. Furthermore, variant a) and c) can also be
  232. (mis_)used to implement functions with one local variable x. If more than one
  233. local variable are required, an auxiliary function must be called that
  234. specifies local variables as additional arguments which are not used (but
  235. initialized) by the call.
  236.  
  237. Note: A function which is used several times should be bound to a symbol (for
  238. efficiency reasons). This is especially important when using recursion.
  239.  
  240. Implementation restriction: Currently, local lambda definitions (lambdas within 
  241. lambdas) do not work correctly. Furthermore, quoting arguments within lambdas
  242. is erroneous. Both these problems are related and due to the simplified
  243. implementation. Solving these problems correctly requires a redesign of the
  244. function evaluation mechanism.
  245.  
  246. Examples:
  247.  
  248. (lambda (x) (add x 1))  defines an increment function
  249. (setq inc (lambda (x) (add x 1)))  the value of inc is the increment function
  250. (inc 1)  inc applied to 1 returns the value 2
  251.  
  252. (setq sum  defines a function sum which recursively
  253.    (lambda (n)  calculates the sum of the first n integers
  254.       (cond
  255.          ((< 0 n) (+ n (sum (- n 1))))  
  256.          (t 0)
  257.       )
  258.    )
  259. )
  260.  
  261. (sum 100)  5050
  262.  
  263. (setq list (lambda x x))  returns its arguments as a list without evaluation
  264. (list a b c)  (a b c)
  265.  
  266. (setq readFiles  extend the readFile function to arbitrary many
  267.    (lambda x  arguments
  268.       (cond
  269.          ((atom x))
  270.          (t (readFile (car x)) (eval (cons 'readFiles (cdr x))))
  271.       )
  272.    )
  273. )
  274.  
  275.  
  276. 7. Error recovery
  277.  
  278. Currently, after a parse_ or run_time, the interpreter only prints out a short 
  279. error message and returns to the read_eval_write loop. If the error hapens
  280. during file input (i.e., during the evaluation of a (readFile arg) expression,
  281. also the file name (arg) is displayed. However, the Lisp tracing facility can
  282. be used to simplify the location of bugs. The function tracer is turned on by
  283. evaluating (tracer on), and turned off by evaluating (tracer off). When on, the 
  284. interpreter prints out the every (predefined and user_defined) function call
  285. together with its arguments and the return value. The following shows the trace 
  286. of the expression (sum 3) (sum is defined in Section 8):
  287.  
  288. > (tracer on)
  289. on
  290. > (sum 3)
  291. [sum] called with (3)
  292.    [cond] called with (((<= #0 0) 0) (t (+ #0 (sum (- #0 1)))))
  293.       [<=] called with (#0 0)
  294.       [<=] returns nil
  295.       [+] called with (#0 (sum (- #0 1)))
  296.          [sum] called with ((- #0 1))
  297.             [-] called with (#0 1)
  298.             [-] returns 2
  299.             [cond] called with (((<= #0 0) 0) (t (+ #0 (sum (- #0 1)))))
  300.                [<=] called with (#0 0)
  301.                [<=] returns nil
  302.                [+] called with (#0 (sum (- #0 1)))
  303.                   [sum] called with ((- #0 1))
  304.                      [-] called with (#0 1)
  305.                      [-] returns 1
  306.                      [cond] called with (((<= #0 0) 0) (t (+ #0 (sum (- #0
  307. 1)))))
  308.                         [<=] called with (#0 0)
  309.                         [<=] returns nil
  310.                         [+] called with (#0 (sum (- #0 1)))
  311.                            [sum] called with ((- #0 1))
  312.                               [-] called with (#0 1)
  313.                               [-] returns 0
  314.                               [cond] called with (((<= #0 0) 0) (t (+ #0 (sum
  315. (- #0 1)))))
  316.                                  [<=] called with (#0 0)
  317.                                  [<=] returns t
  318.                               [cond] returns 0
  319.                            [sum] returns 0
  320.                         [+] returns 1
  321.                      [cond] returns 1
  322.                   [sum] returns 1
  323.                [+] returns 3
  324.             [cond] returns 3
  325.          [sum] returns 3
  326.       [+] returns 6
  327.    [cond] returns 6
  328. [sum] returns 6
  329. 6
  330. > 
  331.  
  332. Function names (i.e., the symbols to which the functions are bound to) are
  333. shown in brackets []. If there is no name for a particular function (i.e., in
  334. case of a anonymous lambda expression), the function definition is printed out
  335. instead. Parameters are denoted by #i, starting with i = 0 for the first
  336. parameter of a lambda expression. If the same function sum is called with a
  337. wrong argument, e.g., a string, the run_time error can be located easily:
  338.  
  339. > (sum "illegal argument")
  340. [sum] called with ("illegal argument")
  341.    [cond] called with (((<= #0 0) 0) (t (+ #0 (sum (- #0 1)))))
  342.       [<=] called with (#0 0)
  343. error in [sum]: 0 is not a string
  344. > 
  345.  
  346. Obviously, the error occured in the user_defined function sum (error messages
  347. refer to user_defined function names only). Within sum, the last function
  348. called was [<=] with the arguments #0 and 0. Since #0 refers to the string
  349. "illegal argument", the expression to be evaluated is (<= "illegal argument" 0) 
  350. which results in a run_time error, since [<=] requires all arguments to be
  351. either numbers or strings.
  352.  
  353.  
  354. 8. A few more examples
  355.  
  356. { Sum of the first n integers }
  357.  
  358. (setq sum
  359.    (lambda (n)
  360.       (cond
  361.          ((<= n 0) 0)
  362.          (t (+ n (sum (- n 1))))
  363.       )
  364.    )
  365. )
  366.  
  367. { Examples }
  368.  
  369. (sum 0)
  370. (sum 10)
  371. (sum 100)
  372. (sum 1000)
  373. (sum 0)
  374.  
  375.  
  376. { Factorial using Peano Axioms }
  377.  
  378. (setq s
  379.    (lambda (x)
  380.       (cons 's (cons x nil))))
  381.       
  382. (setq p
  383.    (lambda (x)
  384.       (car (cdr x))))
  385.       
  386. (setq myAdd
  387.    (lambda (x y)
  388.       (cond
  389.          ((atom x) y)
  390.          (t (s (myAdd (p x) y))))))
  391.          
  392. (setq myMul
  393.    (lambda (x y)
  394.       (cond
  395.          ((atom x) 0)
  396.          (t (myAdd (myMul (p x) y) y)))))
  397.          
  398. (setq gen
  399.    (lambda (n)
  400.       (cond
  401.          ((<= n 0) 0)
  402.          (t (s (gen (- n 1)))))))
  403.          
  404. (setq fact
  405.    (lambda (x)
  406.       (cond
  407.          ((atom x) (s 0))
  408.          (t (myMul x (fact (p x)))))))
  409.  
  410. { Examples (gen is used to create Peano Integers) }
  411.  
  412. (gen 0)
  413. (gen 2)
  414. (gen 10)
  415. (gen 100)
  416.  
  417. (p (gen 3))
  418.  
  419. { Peano addition }
  420.  
  421. (myAdd (gen 3) (gen 4))
  422. (myAdd (gen 0) (gen 2))
  423.  
  424. { Peano multiplication }
  425.  
  426. (myMul (gen 2) (gen 3))
  427.  
  428. { Peano factorial }
  429.  
  430. (fact (gen 0))
  431. (fact (gen 2))
  432. (fact (gen 4))
  433. (fact (gen 5))
  434. (fact (gen 6))
  435.  
  436.  
  437. { Towers of Hanoi }
  438.  
  439. (setq print
  440.    (lambda (x)
  441.       (write x) (writeLn)))
  442.  
  443. (setq move
  444.    (lambda (from to)
  445.       (print (cons from (cons to ())))))
  446.  
  447.  
  448. (setq hanoi
  449.    (lambda (from over to n)
  450.       (cond
  451.          ((> n 0)
  452.             (hanoi from to over (- n 1))
  453.             (move from to)
  454.             (hanoi over from to (- n 1))
  455.          ))))
  456.  
  457. { Example }
  458.  
  459. (hanoi 'a 'b 'c 5)
  460.  
  461.  
  462. { Ackerman function }
  463.  
  464. (setq A
  465.    (lambda (x y)
  466.       (cond
  467.          ((= x 0) (+ y 1))
  468.          ((= y 0) (A (- x 1) 1))
  469.          (t (A (- x 1) (A x (- y 1))))
  470.       )
  471.    )
  472. )
  473.  
  474. { Examples }
  475.  
  476. (A 3 2)
  477. (A 3 3)