home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / gawk213b / walk.ms < prev    next >
Encoding:
Text File  |  1993-07-29  |  14.5 KB  |  504 lines
  1. .\" troff -ms
  2. .\" ...if no CW font available, change CW to B globally
  3. .de ZB
  4. .DS
  5. .ft CW
  6. .nf
  7. ..
  8. .de ZE
  9. .DE
  10. .ft R
  11. .fi
  12. .br
  13. ..
  14. .TL 
  15. A LISP interpreter in Awk
  16. .AU
  17. Roger Rohrbach
  18. .AI
  19. 1592 Union St.,  #94
  20. San Francisco,  CA 94123
  21. .ND
  22. January 3,  1989
  23. .AB ABSTRACT
  24. .PP
  25. This note describes a simple interpreter for the LISP programming
  26. language,  written in \fBawk\fR.  It provides
  27. intrinsic versions of the basic functions on s-expressions,  and many others
  28. written in LISP.  It is compatible with the commonly
  29. available version of \fBawk\fR that is
  30. supplied with most UNIX systems.  The interpreter serves to illustrate
  31. the use of \fBawk\fR for prototyping or implementing language
  32. translators,  as well as providing a simple example of LISP
  33. implementation techniques.
  34. .AE
  35. .SH
  36. Intrinsic functions.
  37. .PP
  38. The interpreter has thirteen built-in functions.
  39. These include the five elementary functions on s-expressions defined
  40. by McCarthy [1];  some conditional expression operators;  an
  41. assignment operator,  and some functions to control the evaluation process.
  42. .PP
  43. The intrinsic functions are summarized below.
  44. Familiarity with existing LISP systems is assumed in the
  45. descriptions of these functions.
  46. .IP "\f(CW(car \fIl\fP)\fR"
  47. .br
  48. Returns the first element of the list \fIl\fR.
  49. An error occurs if \fIl\fR is atomic.
  50. .IP "\f(CW(cdr \fIl\fP)\fR"
  51. .br
  52. Returns the remainder of the list \fIl\fR,  \fIi.e.\fR,
  53. the sublist containing the second through the last
  54. elements.  If \fIl\fR has only one element,  \fBnil\fR is
  55. returned.  \fBcdr\fR is undefined on atoms.
  56. .IP "\f(CW(cons \fIe l\fP)\fR"
  57. .br
  58. Constructs a new list whose \fBcar\fR is \fIe\fR
  59. and whose \fBcdr\fR is \fIl\fR.
  60. .IP "\f(CW(eq \fIx y\fP)\fR"
  61. .br
  62. Returns \fBt\fR if \fIx\fR and \fIy\fR
  63. are the same LISP object,  \fIi.e.\fR,  are either atomic and
  64. have the same print name,  or evaluate to the same
  65. list cell.  Otherwise,  \fBnil\fR is returned.
  66. .IP "\f(CW(atom \fIs\fP)\fR"
  67. .br
  68. Returns \fBt\fR if \fIs\fR is an atom,  otherwise \fBnil\fR.
  69. .IP "\f(CW(set \fIx y\fP)\fR"
  70. .br
  71. Assigns the value \fIy\fR to \fIx\fR and returns \fIy\fR.
  72. \fIx\fR must be atomic,  and may not be a constant
  73. or name an intrinsic function.
  74. .IP "\f(CW(eval \fIs\fP)\fR"
  75. .br
  76. Evaluates \fIs\fR and returns the result.
  77. .IP "\f(CW(error \fIs\fP)\fR"
  78. .br
  79. Halts evaluation and returns \fBnil\fR.
  80. The atom \fIs\fR is printed.
  81. .IP "\f(CW(quote \fIs\fP)\fR"
  82. .br
  83. Returns \fIs\fR,  unevaluated.  The form
  84. .ZB
  85. \'\fIexpr\fP
  86. .ZE
  87. is an abbreviation for
  88. .ZB
  89. (quote \fIexpr\fP)
  90. .ZE
  91. .IP "\f(CW(cond (\fIp1 \f(CW[\fIe1\f(CW]) \fI...\fP (\fIpN \f(CW[\fIeN\f(CW]))\fR"
  92. .br
  93. Evaluates each \fIp\fR from left to right.  If any
  94. evaluate to a value other than \fBnil\fR,  the
  95. corresponding \fIe\fR is evaluated and the result is returned.
  96. If there is no corresponding \fIe\fR,  the value of the \fIp\fR
  97. itself is returned instead.
  98. If no \fIp\fR has a non-null value,  \fBnil\fR is returned.
  99. .IP "\f(CW(and \fIe1 ...  eN\fP)\fR"
  100. .br
  101. Evaluates each \fIe\fR and returns \fBnil\fR if any evaluate to \fBnil\fR.
  102. Otherwise  the value of the last \fIe\fR is returned.
  103. .IP "\f(CW(or \fIe1 ...  eN\fP)\fR"
  104. .br
  105. Evaluates each \fIe\fR and returns the first whose
  106. value is non-null.  If no such \fIe\fR is found,  \fBnil\fR is returned.
  107. .IP "\f(CW(list \fIe1 ...  eN\fP)\fR"
  108. .br
  109. Constructs a new list with elements \fIe1 ...  eN\fR.
  110. Equivalent to
  111. .br
  112. \f(CW(cons \fIe1\fP (cons \fI...\fP (cons \fIeN\fP nil)\fR.
  113. .SH
  114. Lambda functions.
  115. .PP
  116. The following functions are written in LISP and are
  117. defined in the file \fBwalk.w\fR.  Most of
  118. these are commonly supplied with LISP systems.
  119. .IP "\f(CW(cadr \fIs\fP)\fR"
  120. .IP "\f(CW(cddr \fIs\fP)\fR"
  121. .IP "\f(CW(caar \fIs\fP)\fR"
  122. .IP "\f(CW(cdar \fIs\fP)\fR"
  123. .IP "\f(CW(cadar \fIs\fP)\fR"
  124. .IP "\f(CW(caddr \fIs\fP)\fR"
  125. .IP "\f(CW(cddar \fIs\fP)\fR"
  126. .IP "\f(CW(cdadr \fIs\fP)\fR"
  127. .br
  128. These correspond to various compositions of
  129. \fBcar\fR and \fBcdr\fR,  \fIe.g.\fR,
  130. .br
  131. \f(CW(cadr \fIs\fP)\fR \(-> \f(CW(car (cdr \fIs\fP))\fR.
  132. .IP "\f(CW(null \fIs\fP)\fR"
  133. .br
  134. Equivalent to \f(CW(eq \fIs\fP nil)\fR.
  135. .IP "\f(CW(not \fIs\fP)\fR"
  136. .br
  137. Same as \fBnull\fR.
  138. .IP "\f(CW(ff \fIs\fP)\fR"
  139. .br
  140. Returns the first atomic symbol in \fIs\fR.
  141. .IP "\f(CW(subst \fIx y z\fP)\fR"
  142. .br
  143. Substitutes \fIx\fR for all occurrences of the atom \fIy\fR in \fIz\fR.
  144. \fIx\fR and \fIz\fR are arbitrary s-expressions.
  145. .IP "\f(CW(equal \fIx y\fP)\fR"
  146. .br
  147. Returns \fBt\fR if \fIx\fR and \fIy\fR are
  148. the same s-expression,  otherwise \fBnil\fR.
  149. .IP "\f(CW(append \fIx y\fP)\fR"
  150. .br
  151. Creates a new list containing the elements of x and y,
  152. which must both be lists.
  153. .IP "\f(CW(member \fIx y\fP)\fR"
  154. .br
  155. Returns \fBt\fR if \fIx\fR is an element of the list \fIy\fR,
  156. otherwise \fBnil\fR.
  157. .IP "\f(CW(pair \fIx y\fP)\fR"
  158. .br
  159. Pairs each element of the lists \fIx\fR and \fIy\fR,
  160. and returns a list of the resulting pairs.  The number
  161. of pairs in the result will equal the length of the
  162. shorter of the two input lists.
  163. .IP "\f(CW(assoc \fIx y\fP)\fR"
  164. .br
  165. Association list selector function.
  166. \fIy\fR is a list of the
  167. form \f(CW((\fIu1\fP \fIv1\fP) \fI...\fP (\fIuN\fP \fIvN\fP))\fR
  168. where the \fIu\fR's are atomic.  If \fIx\fR is
  169. one of these,  the corresponding pair \f(CW(\fIu\fP \fIv\fP)\fR
  170. is returned,  otherwise \fBnil\fR.
  171. .IP "\f(CW(sublis \fIx y\fP)\fR"
  172. .br
  173. \fIx\fR is an association list.
  174. Substitutes the values in \fIx\fR for the keys in \fIy\fR.
  175. .IP "\f(CW(last \fIl\fP)\fR"
  176. .br
  177. Returns the last element of \fIl\fR.
  178. .IP "\f(CW(reverse \fIl\fP)\fR"
  179. .br
  180. Returns a list that contains the elements in \fIl\fR,
  181. in reverse order.
  182. .IP "\f(CW(remove \fIe l\fP)\fR"
  183. .br
  184. Returns a copy of \fIl\fR with all
  185. occurrences of the element \fIe\fR removed.
  186. .IP "\f(CW(succ \fIx y\fP)\fR"
  187. .br
  188. Returns the element that immediately follows the atom \fIx\fR
  189. in the list \fIy\fR.  If \fIx\fR does not occur in \fIy\fR
  190. or is the last element,  \fBnil\fR is returned.
  191. .IP "\f(CW(pred \fIx y\fP)\fR"
  192. .br
  193. Returns the element that immediately precedes the atom \fIx\fR
  194. in the list \fIy\fR.  If \fIx\fR does not occur in \fIy\fR
  195. or is the first element,  \fBnil\fR is returned.
  196. .IP "\f(CW(before \fIx y\fP)\fR"
  197. .br
  198. Returns the list of elements occurring before y in x.
  199. If \fIy\fR does not occur in \fIx\fR
  200. or is the first element,  \fBnil\fR is returned.
  201. .IP "\f(CW(after \fIx y\fP)\fR"
  202. .br
  203. Returns the list of elements occurring after y in x.
  204. If \fIy\fR does not occur in \fIx\fR
  205. or is the last element,  \fBnil\fR is returned.
  206. .IP "\f(CW(plist \fIx\fP)\fR"
  207. .br
  208. Returns the property list for the atom \fIx\fR.
  209. .IP "\f(CW(get \fIx i\fP)\fR"
  210. .br
  211. Returns the value stored on \fIx\fR's property list
  212. under the indicator \fIi\fR.
  213. .IP "\f(CW(putprop \fIx v i\fP)\fR"
  214. .br
  215. Stores the value \fIv\fR on \fIx\fR's property list under
  216. the indicator \fIi\fR.
  217. .IP "\f(CW(remprop \fIx i\fP)\fR"
  218. .br
  219. Remove the indicator \fIi\fR
  220. and any associated value from \fIx\fR's property list.
  221. .IP "\f(CW(mapcar \fIf l\fP)\fR"
  222. .br
  223. Applies the function \fIf\fR to each element of \fIl\fR and returns
  224. the list of results.
  225. .IP "\f(CW(apply \fIf args\fP)\fR"
  226. .br
  227. Calls \fIf\fR with the arguments \fIargs\fR,  \fIe.g.\fR,
  228. .ZB
  229. (apply 'cons '(a (b)))
  230. .ZE
  231. is equivalent to
  232. .ZB
  233. (cons 'a '(b))
  234. .ZE
  235. .SH
  236. Syntactic conventions.
  237. .LP
  238. Atoms take the following forms:
  239. .IP "\fIRegular identifiers\fR"
  240. .br
  241. Atoms matching the regular expression
  242. .br
  243. .sp
  244. .nf
  245.     \f(CW[_A-Za-z][-A-Za-z_0-9]*\fR
  246. .fi
  247. .sp
  248. The initial value of an identifier is \fBnil\fR.
  249. .IP "\fIIntegers\fR"
  250. .br
  251. Atoms matching the regular expression \f(CW[0-9][0-9]*\fR.
  252. Integers are constants,  \fIi.e.\fR,  evaluate to themselves.
  253. .IP "\fIWeird atoms\fR"
  254. .br
  255. Identifiers matching the regular expression \f(CW".*"\fR.  Weird
  256. atoms are not constants.
  257. .LP
  258. A semicolon introduces a comment,  which continues for the rest
  259. of the line.
  260. .SH
  261. Usage.
  262. .LP
  263. The command for running the interpreter is
  264. .ZB
  265. walk [ \fIfiles\fP ]
  266. .ZE
  267. on BSD UNIX and derivative systems,  or
  268. .ZB
  269. awk -f walk [ \fIfiles\fP ]
  270. .ZE
  271. on UNIX System V.
  272. The file name \f(CW\-\fR represents the standard input.
  273. This can be omitted if no other files are being read in,  or
  274. if the interpreter is being run non-interactively.
  275. .PP
  276. Normally,  the interpreter is used interactively,  augmented
  277. with the functions defined in \fBwalk.w\fR,  and,  perhaps,  other files.
  278. The command line to use for this purpose is
  279. .ZB
  280. walk walk.w [ \fIother files\fP ] p -
  281. .ZE
  282. The interpreter will first read \fBwalk.w\fR,  printing
  283. the results of evaluating the function definitions
  284. therein.  Then it will read \fBp\fR.  This file
  285. contains no LISP definitions;  the interpreter recognizes
  286. it by name and prints a prompt to signal the user that all
  287. the prerequisite files have been read and that the interpreter
  288. is waiting for input.  (This is the only way to get \fBawk\fR
  289. to do this;  this can be hidden from the user
  290. with a shell program that invokes the interpreter if desired.)
  291. Thereafter,  it will evaluate expressions typed in by
  292. the user,  printing a prompt after each one.
  293. Normally the prompt is \f(CW\->\fR;  the first character of the
  294. prompt changes when appropriate to an integer that represents the number
  295. of unmatched left parentheses read in so far.
  296. .PP
  297. The interpreter exits when it encounters the end of its last input file.
  298. If this file is the standard input,  the number of LISP objects
  299. created is reported.
  300. .PP
  301. Several files defining auxiliary functions are provided.
  302. .SH
  303. Implementation.
  304. .PP
  305. So that it can run on any UNIX system,  The
  306. LISP interpreter has been written using the UNIX V7 version
  307. of \fBawk\fR,  which
  308. predates the version described in \fIThe Awk Programming Language\fR [2].
  309. The only complex data type provided by this language is the array.
  310. Data that in C might be stored in structures is
  311. represented,  therefore, using
  312. multiple arrays,  one for each field.  For example,  the C code
  313. .ZB
  314.     p = allocate_cell();
  315.     p->car = s;
  316.     p->cdr = NIL;
  317. .ZE
  318. can be approximated with:
  319. .ZB
  320.     p = ++cell;
  321.     car[p] = s;
  322.     cdr[p] = nil;
  323. .ZE
  324. Lists (using nested array references)
  325. and stacks are also simulated with arrays.  The most important data
  326. structures are explained in the program and in the following description.
  327. .PP
  328. As is usual for LISP implementations,  the interpreter is constructed as a
  329. loop that reads an s-expression,  evaluates it,  and prints the
  330. result.  The reader collects an s-expression,  reading multiple
  331. input lines if necessary.  Like the other two phases of the
  332. interpreter,  this is a recursive procedure and
  333. in \fBawk\fR this must be managed explicitly.
  334. When an s-expression is read,  its internal representation in
  335. list structure is formed using the stack \fBread[]\fR.  Atoms and
  336. \fBcons\fR operators are pushed onto the read stack and periodically
  337. `reduced' or replaced
  338. with list cells when a complete list has been read;  the reader returns
  339. an atom or list on the top of the stack.
  340. The reader must
  341. be able to return an s-expression in the middle of an input line,  so the
  342. entire interpreter is enclosed in a loop that allows the
  343. current input line to be completely scanned before the next
  344. input record is read.  The general outline is:
  345. .ZB
  346. BEGIN {
  347. .ft I
  348.     initialize interpreter 
  349.     say hello if interactive
  350. .ft R
  351. .ft CW
  352. }
  353.  
  354. {
  355. .ft I
  356.     initialize reader variables
  357. .ft R
  358. .ft CW
  359.  
  360.     while (\fIchars left on this line\fR\f(CW)
  361.     {
  362. .ft I
  363.         read
  364. .ft R
  365. .ft CW
  366.  
  367.         if (\fIhave read an s-expression\fR\f(CW)
  368.         {
  369. .ft I
  370.             eval
  371.  
  372.             print
  373. .ft R
  374. .ft CW
  375.         }
  376.     }
  377.  
  378. .ft I
  379.     prompt if interactive
  380. .ft R
  381. .ft CW
  382. }
  383.  
  384. END {
  385. .ft I
  386.     say goodbye if interactive
  387.     exit
  388. .ft R
  389. .ft CW
  390. }
  391. .ZE
  392. .PP
  393. The evaluator maintains two stacks,  one for input and one for output.
  394. The result returned by the reader is copied onto the input stack
  395. (\fBeval[]\fR),  and evaluated according to the usual LISP rules.
  396. Evaluated s-expressions are placed on the output stack,  \fBarg[]\fR.
  397. When an intrinsic function that takes evaluated arguments appears on
  398. the top of the evaluation stack,  its arguments are popped from the
  399. argument stack.  Functions (like \fBcond\fR) that take unevaluated
  400. arguments are handled as special forms before their arguments have been
  401. pushed onto \fBeval[]\fR.  The arguments are handled differently
  402. depending on the
  403. semantics of the function.  Lambda (user-defined) functions are evaluated
  404. by temporarily binding the formal parameters in the function
  405. definition to the results of evaluating the actual arguments with which
  406. the function was called,  and then evaluating the body of the function.
  407. Temporary bindings only are kept on a special
  408. pushdown list (the \fIalist\fR).  Atoms have a global value that is
  409. stored separately;  this keeps the alist small.
  410. .LP
  411. The evaluation procedure is sketched below:
  412. .ZB
  413. .ft I
  414. atom?
  415. .ft CW
  416.     lambda
  417. .ft R
  418.         restore previous environment (lambda function
  419.         body has been evaluated already)
  420. .ft I
  421.     constant?
  422. .ft R
  423.         return
  424. .ft I
  425.     bound?
  426. .ft R
  427.         look up local value
  428. .ft I
  429.     otherwise
  430. .ft R
  431.         return global value
  432.  
  433. .ft I
  434. intrinsic function?
  435. .ft R
  436.     apply to already evaluated arguments
  437.  
  438. .ft I
  439. lambda function?
  440. .ft R
  441.     bind formal parameters to already evaluated arguments
  442.     evaluate function body
  443.  
  444. .ft I
  445. form?
  446.     intrinsic function application?
  447. .ft R
  448. .ft CW
  449.         quote
  450. .ft R
  451.             return unevaluated argument
  452. .ft CW
  453.         cond
  454.         and
  455.         or
  456. .ft R
  457.             begin evaluating arguments according to operator semantics
  458. .ft CW
  459.         list
  460. .ft R
  461.             expand to repeated applications of cons
  462. .ft I
  463.     other?
  464. .ft R
  465.         push function variable,  arguments
  466.     
  467. .ft I
  468. lambda function application?
  469. .ft R
  470.     push lambda function,  body
  471. .ft I
  472. other?
  473. .ft R
  474.     eval \fBcar\fR,  \fBcdr\fR
  475. .ZE
  476. .PP
  477. When the evaluation stack is emptied,  the result
  478. is popped from the argument stack and printed.  A stack is again
  479. used to manage recursion.
  480. .SH
  481. Conclusion.
  482. .PP
  483. The goal of writing a small LISP interpreter and extending it
  484. in LISP has been realized.  Though it was not my original intention,  it
  485. would be easy to incorporate the
  486. LISP functions as intrinsics,  and many other extensions (such as
  487. numeric functions) could be made,  in which case the interpreter
  488. might fulfill more than a pedagogic function.
  489. Even so,  it can be used as is for an introduction to LISP programming
  490. and implementation concepts.  I hope it also inspires more of us to
  491. learn how to program in \fBawk\fR!
  492. .SH
  493. References.
  494. .IP "[1]"
  495. .br
  496. McCarthy, J.  Recursive Functions of Symbolic Expressions
  497. and their Computation by Machine,  Part
  498. I.  \fIComm. ACM\fR,  3,  4,  pp. 185-195
  499. April 1960
  500. .IP "[2]"
  501. .br
  502. Aho, A.,  Weinberger,  P.,  & Kernighan,  B.W.  \fIThe
  503. Awk Programming Language\fR.  Addison-Wesley,  Reading,  MA 1988
  504.