Re: Designing Lisp from scratch

> I guess the main reason you may have a hard time finding lex/yacc
> parsers for Lisp is that Lisp parsers are built into every Lisp system.
> Thus, if you want to parse Lisp code, you just use Lisp and say (read).

Bzzzt.

READ does not *parse*.  Parsing is regarded as the process of
distinguishing valid terms from invalid terms, accounting for the
context-sensitive (and more) constraints of the language.  What READ
does is..."read": it produces an intermediate language of terms that
do not fully perform this distinction: that is, a term rejected by
READ is illegal, but one not rejected may also be illegal.  E.g.: The
following terms are not valid Scheme (or perhaps they are in some
bizarre Scheme, but pretend they aren't):

  (lambda (x))
  (define (f 5) 3)

but they do pass READ.  It is some other tool, the parser, that
distinguishes these from the valid terms of the language.  This tool
is hidden from the user of most Scheme systems.  Similarly, the
internal abstract syntax tree data structure used by the system (which
may be very different from s-expressions) is also hidden.  In terms of
types,

  read: char-stream -> s-exp  [exception: not-an-s-exp]
  parse: s-exp -> ast [exception: syntax-error]

Of course, this is the same as the distinction between well-formedness
and validity in XML.

I use the term "bicameral syntax" to distinguish these languages from
ones that do not have such a formal, intermediate syntax.  Bicameral
syntaxes are not to everyone's liking, but they do have the wonderful
property of reducing a fairly hard problem (parsing) into two very
easy ones (READing and parsing-read-structures).

-----

Incidentally, Daniel Corbier's rant about Lex and Yacc simply
recapitulates the reason why people have been studying and building
scannerless parsers for a long time.  There's something in his message
that I think means uCalc can get macros for free atop scannerless
parsing; that is intriguing but also awfully difficult, and it's hard
to judge these slightly extraordinary claims.

Shriram