I was recently reading in Robert Sedgewick's Algorithms, and happened to open to the (rather short) section on parsing. Although it is not covered in the book, I got an idea about writing a simple S-expression (sexp) evaluator. Because I know very little about the subject in general, it would be very helpful if somebody were to share a tiny smidgen of their knowledge with me. Yes, I have STFW, but I haven't found much.

Thanks,
Drew K.

What's STFW mean?

Anyway, here's some pieces of a toy Lisp interpreter:


(defun soil-whitespacep (char)
(if (member char (list #\Space
#\Tab
#\Newline))
t
nil))

(defun soil-chomp-whitespace (stream)
(loop while (soil-whitespacep (peek-char nil stream nil))
do (read-char stream)))


(defun soil-read-preserving-whitespace (stream)
(soil-chomp-whitespace stream)
(case (peek-char nil stream nil)
(#\( (read-char stream)
(soil-read-list stream))
(#\) (read-char stream)
(error "Unbalanced parens"))
(#\' (read-char stream)
;; Mispeling of `quote' is to make it obvious when SBCL
;; prints it (SBCL prints (quote thing) as 'thing)
(list 'qwote (soil-read-preserving-whitespace stream)))
(otherwise (soil-ratom stream))))

(defun soil-read-list (stream)
(let ((result ()))
(loop until (eql (peek-char nil stream t) #\))
do (push (soil-read stream) result))
(read-char stream)
(reverse result)))

(defun soil-ratom (stream)
(let ((sym "")
(charchecker (lambda (c)
(or (null c)
(eql c #\))
(soil-whitespacep c)))))
(loop until (funcall charchecker (peek-char nil stream nil))
do (setq sym (concatenate 'string sym (vector
(read-char stream)))))
(intern sym)))

(defun soil-read (stream)
(prog1
(soil-read-preserving-whitespace stream)
(soil-chomp-whitespace stream)))


Copy-and-yanked from an XTerm, so sorry, may not be indented well. Last time I tried it it worked.

Quote:
On 2002-05-21 12:26, bpt wrote:
What's STFW mean?


"Search The scandiskin Web"?

...Does MooKeen know lisp?

bpt: Thanks! That will be very helpful.

fsvara: I'm a newbie to Lisp, and yes, I intended to write the sexp evaluator in it. This is meant to be a learning experience --nothing more.

What semantics is your language going to have?

You could always cheat and just implement LAMBDA and SET not quite Lisp but at least it's Turing complete (IIANM)...

[this isn't ``pure'' lambda calculus since it uses named functions, doesn't matter for this purpose]


(set true (lambda (f x y) x))
(set false (lambda (f x y) y))
(set if (lambda (f x y) (f x y)))

(set not (lambda (x) (if x false true)))
(set and (lambda (x y) (if x (if y true false) false)))
(set or (lambda (x y) (if x true (if y true false))))
(set xor (lambda (x y) (if x (if y false true) (if y true false))))

(set compose (f g) (lambda (x) (f (g x))))

;; Y combinator.
(set Y (lambda (f x) (f f x)))

;; ... etc ...

Somehow, this project has morphed into an infix expression evaluator. I'll post some code once it is "working", and some people (namely, bpt), can pick it apart and show me the Right Way