simple lisp interpreter

Matthias Buelow <mkb@incubus.de> wrote:
+---------------
| Yes but the OP was asking whether the "Lisp language" can be parsed by
| an LL parser, by which I understand that he means in textual source-code
| form, otherwise it wouldn't make much sense.
+---------------

A better question might be whether the Common Lisp *reader* --
the CLHS function READ -- can usefully be implemented using an
LL parser. Having once written most of a CL READ in C, ISTR that
you need at least one and maybe in some rare cases two tokens
of read-ahead [when parsing dotted lists maybe?] to decide what
to do next using straightforward recursive descent [which is
sort of LL, right?]. It's not all that hard to do. [My reader
was less than 500 lines of C.]

But because of "#." and backquote & friends and other readmacros,
I doubt a *full* CL reader can be implemented using any kind of
"pure" or static table-driven parser, LL or otherwise, since you
need to be able to call back into Lisp at READ time.


-Rob

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

George Neuner <gneuner2/@comcast.net> writes:

> On Wed, 05 Sep 2007 12:37:48 +0200, Matthias Buelow <mkb@incubus.de>
> wrote:
>
> >Can you construct (theoretically) an LL(n) grammar that can produce any
> >Common Lisp program?
>
> In general ... no.
>
> Kent pointed out (and I guess you were alluding to) that readtable
> macros might do absolutely anything - including parsing a completely
> different language - and so it is very hard to reason about the
> grammar complexity of a Lisp program.
>
> If you confine the problem to Lisp syntax then the answer is yes.

Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
by users is _still_ Lisp syntax.

I'm afraid I feel it necessary to belabor this point because it's key:

We certainly don't refer to programs that are not given by the standard but
written by users as if they were not "Lisp programs". The same should be
true of Lisp syntax.

By design, Common Lisp intends you to extend the syntax. This is not
a baroque exception that may be swept under the rug as an anomalous
and embarrassing quirk. It is absolutely core to the way that you are
intended to program, and it is a key missing feature that drives me
absolutely nuts when working with other languages. If I had this
ability to extend and control the language syntax in other languages,
I would consider that a MAJOR step forward in those languages bridging
the gaping void between Lisp and those languages. The ability to merely
tweak parse precedences, touted by a recent vocal super-minority as an
important capability, pales in comparison to this very valuable feature.

I have written programs that represent complex technologies (like XML,
MIF, and other document structures, Symbolic Algebra expressions, new
languagey datatypes as specific as URLs or as general as alternate
object systems, and so on) as things with print and read syntaxes that
allowed me to use this kind of data compactly and gracefully as
program data, including as literal constants in the middle of other
code. There is just no comparison between that level of
organizational/presentational capability and mere changing of the
order of operators or removing a few parens.

My expectations for mainstream languages are so low that I find myself
cheering when languages like C# even have ubiquitous .ToString() on all
Objects. That, at least, means there's a vague way to debug stuff.
However, it's nothing compared to Lisp not just because it's only half
a protocol (there's no way to use the text that comes from there as input,
and consequently the format of .ToString() results varies hugely in a way
that makes them not comparable to the output of PRIN1. It's more like
what PRINC does, which would never be a suitable counterpart to READ).

Common Lisp, in particular, builds on many years of development by other
dialects, by offering powerful tools for users to gracefully extend the
reader and printer in a way that makes complicated, interconnected programs
be able to interchange programs and data not just as objects but even
when marshaled as strings that must be read (i.e. parsed).

> From experience, I know Scheme grammar is mostly LL(1) with just a
> couple of forms that require more look ahead - LL(2) or LL(3), nothing
> drastically hard. A grammar for Lisp should be of the same order
> complexity - Lisp's additional keywords, expanded parameter lists, and
> multiple name spaces don't materially affect the grammar complexity
> ... the parser complexity, but not the grammar.

Yes, if I recall how it went in the design discussions, the authors of
the Scheme report went to considerable explicit work to design the
Scheme language in an appropriately restrictive way (given that
conservativism is one of its core themes) that was explicitly intended
to allow people who wanted a "parser model" to just do that without
realizing that others were using an object model for semantics. Both
styles were intended to work.

(This, incidentally, places some pressure on the language when it
comes to issues like gensyms [which have little meaning as parsed
entities since by definition they are objects intended to have no
parsed representation so you can't accidentally make one], and I don't
recall how that was resolved. I watched the discussions go by but
didn't involve myself heavily in that aspect of the language, other
than to fuss a bit about the problems that result with trying to make
'gensym' work in a parsed situation. Probably this ended up finessed
by the hygienic-macro system, but I don't have the time to dig--maybe
someone else can look this up and report back here on it if they
care.)

On 06 Sep 2007 08:50:12 -0400, Kent M Pitman <pitman@nhplace.com>
wrote:

>George Neuner <gneuner2/@comcast.net> writes:
>
>> On Wed, 05 Sep 2007 12:37:48 +0200, Matthias Buelow <mkb@incubus.de>
>> wrote:
>>
>> >Can you construct (theoretically) an LL(n) grammar that can produce any
>> >Common Lisp program?
>>
>> In general ... no.
>>
>> Kent pointed out (and I guess you were alluding to) that readtable
>> macros might do absolutely anything - including parsing a completely
>> different language - and so it is very hard to reason about the
>> grammar complexity of a Lisp program.
>>
>> If you confine the problem to Lisp syntax then the answer is yes.
>
>Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
>by users is _still_ Lisp syntax.

Sort of. What I mean exactly is any sexpr syntax that conforms to
Lisp's prefix notation. Whether the symbols are pre-defined or user
defined is not really relevant to parsing them. Lispy macros also
fall into this category - even LOOP is very simple to parse in LL
despite not following normal Lisp conventions.

I think part of the issue in this discussion is where the boundary is
drawn between parsing and analyzing/evaluating the resultant internal
form. The Lisp reader conflates these operations (as do parsers in
compilers for most languages) for efficiency, but it is always
technically possible to separate them and talk about just the "parser"
or the "evaluator". I've been talking mostly about just parsing
because that's how this thread began, but I understand your point.


>I'm afraid I feel it necessary to belabor this point because it's key:
>
>We certainly don't refer to programs that are not given by the standard but
>written by users as if they were not "Lisp programs". The same should be
>true of Lisp syntax.
>
>By design, Common Lisp intends you to extend the syntax. This is not
>a baroque exception that may be swept under the rug as an anomalous
>and embarrassing quirk. It is absolutely core to the way that you are
>intended to program, and it is a key missing feature that drives me
>absolutely nuts when working with other languages. If I had this
>ability to extend and control the language syntax in other languages,
>I would consider that a MAJOR step forward in those languages bridging
>the gaping void between Lisp and those languages. The ability to merely
>tweak parse precedences, touted by a recent vocal super-minority as an
>important capability, pales in comparison to this very valuable feature.
>
>I have written programs that represent complex technologies (like XML,
>MIF, and other document structures, Symbolic Algebra expressions, new
>languagey datatypes as specific as URLs or as general as alternate
>object systems, and so on) as things with print and read syntaxes that
>allowed me to use this kind of data compactly and gracefully as
>program data, including as literal constants in the middle of other
>code. There is just no comparison between that level of
>organizational/presentational capability and mere changing of the
>order of operators or removing a few parens.
>
>My expectations for mainstream languages are so low that I find myself
>cheering when languages like C# even have ubiquitous .ToString() on all
>Objects. That, at least, means there's a vague way to debug stuff.
>However, it's nothing compared to Lisp not just because it's only half
>a protocol (there's no way to use the text that comes from there as input,
>and consequently the format of .ToString() results varies hugely in a way
>that makes them not comparable to the output of PRIN1. It's more like
>what PRINC does, which would never be a suitable counterpart to READ).
>
>Common Lisp, in particular, builds on many years of development by other
>dialects, by offering powerful tools for users to gracefully extend the
>reader and printer in a way that makes complicated, interconnected programs
>be able to interchange programs and data not just as objects but even
>when marshaled as strings that must be read (i.e. parsed).
>
>> From experience, I know Scheme grammar is mostly LL(1) with just a
>> couple of forms that require more look ahead - LL(2) or LL(3), nothing
>> drastically hard. A grammar for Lisp should be of the same order
>> complexity - Lisp's additional keywords, expanded parameter lists, and
>> multiple name spaces don't materially affect the grammar complexity
>> ... the parser complexity, but not the grammar.
>
>Yes, if I recall how it went in the design discussions, the authors of
>the Scheme report went to considerable explicit work to design the
>Scheme language in an appropriately restrictive way (given that
>conservativism is one of its core themes) that was explicitly intended
>to allow people who wanted a "parser model" to just do that without
>realizing that others were using an object model for semantics. Both
>styles were intended to work.
>
>(This, incidentally, places some pressure on the language when it
>comes to issues like gensyms [which have little meaning as parsed
>entities since by definition they are objects intended to have no
>parsed representation so you can't accidentally make one], and I don't
>recall how that was resolved. I watched the discussions go by but
>didn't involve myself heavily in that aspect of the language, other
>than to fuss a bit about the problems that result with trying to make
>'gensym' work in a parsed situation. Probably this ended up finessed
>by the hygienic-macro system, but I don't have the time to dig--maybe
>someone else can look this up and report back here on it if they
>care.)

George
--
for email reply remove "/" from address

On Thu, 06 Sep 2007 03:25:00 -0500, rpw3@rpw3.org (Rob Warnock) wrote:

>Matthias Buelow <mkb@incubus.de> wrote:
>+---------------
>| Yes but the OP was asking whether the "Lisp language" can be parsed by
>| an LL parser, by which I understand that he means in textual source-code
>| form, otherwise it wouldn't make much sense.
>+---------------
>
>A better question might be whether the Common Lisp *reader* --
>the CLHS function READ -- can usefully be implemented using an
>LL parser. Having once written most of a CL READ in C, ISTR that
>you need at least one and maybe in some rare cases two tokens
>of read-ahead [when parsing dotted lists maybe?] to decide what
>to do next using straightforward recursive descent [which is
>sort of LL, right?]. It's not all that hard to do. [My reader
>was less than 500 lines of C.]
>
>But because of "#." and backquote & friends and other readmacros,
>I doubt a *full* CL reader can be implemented using any kind of
>"pure" or static table-driven parser, LL or otherwise, since you
>need to be able to call back into Lisp at READ time.

Actually I think its only general readtable processing that is
troublesome. The set of standard abbreviation macros can be easily
recognized as special cases.

George
--
for email reply remove "/" from address

George Neuner <gneuner2/@comcast.net> writes:

> >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
> >by users is _still_ Lisp syntax.
>
> Sort of. What I mean exactly is any sexpr syntax that conforms to
> Lisp's prefix notation.

Well, except that this may be useful for some special-purpose one-off
thing, since virtually anything may be useful to a thing, but in terms
of "describing CL", it's not meaningful to say "handles things people
might write who have no pre-defined agreement with you" other than to
say "the full set of things people might write".

I asked earlier, I think, or maybe I started to ask and then didn't
send it, so I'll ask again: what would one do differently if one had a
parser for this allegedly interesting subset? Is there a goal here
that is logically distinct from discussing what the set of numeric
values Lisp could compute if bignums were not there? The reader does
define readmacros so I don't see quite what people are getting at in
discussing the properties of the reader absent readmacros. Is this
just a discussion of making toys that will grow up to not be able to
use the tools that bootstrapped them? Is there a proposal in play for
extending the LL(n) concept to be usefully able to accept arbitrary
code in the middle [as, for example, a "pratt parser" might do?] I'm
just completely out of context as to the goal, so it keeps catching my
eye that other readers who might be following along might be done the
misservice of thinking this was a discussion of the properties of the
actual CL reader, and it's not as far as I can see.

I guess you _could_ be talking about some hypothetical readmacro-free
subset, but you haven't appeared to label the conversation taht way. I
have to say that the reason I chimed in is that it appeared that some
people involved in the discussion (I am not sure I even know whom, and
I'm not trying to point fingers, but generally) didn't seem realize
readmacros are there, that they are important to day-to-day use of
many programmers, and call for a different way of thinking than
standard parsers tend to promote. It's like having a discussion of
DEFSTRUCT not realizing CLOS is there and talking about whether
Common Lisp would benefit from multiple inheritance. Anyone looking
on would take a discussion as if it was saying "CL doesn't have that
already."

I've got nothing against hypothetical discussions, when properly
labeled, but just starting a discussion that uses either a
hypothetical or a gaping whole in caveat-declaration is not that
because it risks that people reading on will get confused. My only
goal in injecting myself here is to make sure that people don't
mistake all the discussion here for discussion of what the real,
non-hypothetical Lisp reader actually does and needs. As soon as I
see appropriate caveats being mentioned in places that will avoid
confusion, I'll recede back into the background.

The only implicit constraint CL places on things, and I doubt it's
formally spelled out, is that the syntax you pick should, if it really
wants to sit inside other expressions [and it isn't required to do that
since you migth want to make your own readtable with data to be parsed
by READ that isn't intended to be embedded in s-expressions], is that
it wants to cleanly start and stop so that it can be embedded. So if you
make a syntax: #[...] then it's assumed that you can also make
(... #[...]). So if you make a FORTRAN parser and it parses to end of
file, you can't use eof as a terminator and still be embedded in other
expressions. But other than that, it pretty much can terminate as it likes.

Lisp-savvy text editors like Emacs (not talking about emacs-lisp here,
but just the implicit constraints of using something that even thinks
it understands Lisp) happens to usually place additional constraints,
like that the notation should not locally confuse the syntax
categorizations it makes, which is why #\x is chosen as it is, so that
if Emacs doesn't know what #\ is, it will presumably still know that \
quotes the character after it, which will mean #\a is harmless but,
importantly, #\( will not be taken as a syntactic open-paren. So if
you extend things in a way as to make a readmacro that returns an
n-length string by doing #3@abc, for example, you are going to
probably make Emacs mad because while abc is fine #3@((| is going to
trick Emacs into thinking there are pending open parens followed by a
pending |, all three of which characters need matches (and in the right
order).

But beyond all of that, there is still a huge wealth of difference in
what these readmacros might do, and certainly describing those things
in a grammar is not really useful because the grammar will have a gaping
"or anything else" at the bottom.

> Whether the symbols are pre-defined or user
> defined is not really relevant to parsing them. Lispy macros also
> fall into this category - even LOOP is very simple to parse in LL
> despite not following normal Lisp conventions.

I'm not talking about [expression] macros, I'm talking about reader macros.
Which are you talking about, because LOOP is something that takes an
expression as its argument, that is this single pointer (noted as argptr
here) is the argument to LOOP:

argptr
|
v
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+
| . | .---->| . | .---->| . | .---->| . | .---->| . | .----> ...
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
v v | v v
LOOP FOR | IN +---+---+ +---+---+
+---+---+ | . | .---->| . | / |
| . | . | +-|-+---+ |-|-+---+
+-|-+-|-+ v v
v v FIRST Y
A B

I don't know any parsers that take pointers to complex object structures as
args, but I suppose there could be such. Ordinarily, I assume that parsers
take either a string

"LOOP FOR (A . B) IN (FIRST Y) ..."

or a token stream

#("LOOP" "FOR" "(" "A" "." "B" ")" "IN" "(" "FIRST" "Y" ")" ...)

but Lisp uses neither of these.

> I think part of the issue in this discussion is where the boundary is
> drawn between parsing and analyzing/evaluating the resultant internal
> form. The Lisp reader conflates these operations (as do parsers in
> compilers for most languages) for efficiency, but it is always
> technically possible to separate them and talk about just the "parser"
> or the "evaluator".

As I see it, Lisp does not conflate them. It is one of the few
languages that keeps the separation extraordinarily clear.

READ returns objects. EVAL is defined on objects.

For convenience of reference, we refer by syntax to the objects that EVAL
takes as inputs since the nature of those objects are self-evident through
their notation thanks to the clear definition of READ. That's almost
unheard of in other languages.

> I've been talking mostly about just parsing
> because that's how this thread began, but I understand your point.

In the messages I've read and replied to, it doesn't seem clear.
Perhaps you're assuming people read whole threads from start to end
and recall their state, but that's asking a lot of usenet readers.

George Neuner <gneuner2/@comcast.net> wrote:
+---------------
| Kent M Pitman <pitman@nhplace.com> wrote:
| >George Neuner <gneuner2/@comcast.net> writes:
| >> If you confine the problem to Lisp syntax then the answer is yes.
| >
| >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
| >by users is _still_ Lisp syntax.
|
| Sort of. What I mean exactly is any sexpr syntax that conforms to
| Lisp's prefix notation.
+---------------

I think you've missed Kent's point entirely. When coding a CL READ in C
[and ignoring READ's &OPTIONAL parameters for the nonce], the top level
"parsing" routine looks like this [or something closely equivalent]:

lispobj
reader(lispobj stream)
{
for (; { /* Needed for reader macros that do nothing. */
lispobj obj;
int c = flush_whitespace(stream);
if (EOF == c)
return type_EOF;
obj = (*read_macro_table[c])(stream, c);
if (obj != type_ZeroValues) /* Comments, #+/-, and the like. */
return obj;
/* else keep reading... */
}
}

The key is that *ALL* "parsing" starts with that crucial indirection
through the current readtable. There *is* no such thing as a
"[conforming] s-expr syntax" unless the readmacro currently in
force for #\( just happens to be one which gives you the "usual"
s-expr syntax.


-Rob

p.s. And, no, that's not the way you'd really do it [except for an
inflexible toy CL subset], since that makes it too hard to switch
readtables. You need to add a level of indirection:

...
obj = (*(*read_macro_table)[c])(stream, c);
...

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

I think we're talking at crossed purposes and we should probably stop
before it goes any further. I do appreciate your exposition on the
workings of the Lisp reader - as I stated earlier, my experience with
Lisp-like languages has been mainly with Scheme which doesn't have a
standard for reader extension - in Scheme reader extension, if
supported at all, is implementation dependent.

One thing I would like to say though before we stop: the original
poster asked a theoretical question ... whether Lisp (he did not
specify CL) was LL(1). The answer to that is "no" regardless of
whether readtable processing is considered - some of the basic (I want
to avoid the word "standard") language forms are not LL(1).

However, because the reader can invoke any behavior whatsoever via the
readtable it can be made to accept virtually any language. Given
that, it makes little sense to talk about the grammatical complexity
of Common Lisp or the complexity of the reader because one can't even
define a grammar for the accepted language other than in situ.
Perhaps this is what you (Kent) and Matthias and Rob were getting at
all along. But then it doesn't make sense either to talk about Common
Lisp as a distinct language because it can be any language.

Also, I was not discussing CL in particular but rather sexpr based
languages which resemble Lisp in notation. I understand that that was
not made clear, and for that, I apologize.



On 06 Sep 2007 21:34:01 -0400, Kent M Pitman <pitman@nhplace.com>
wrote:

>George Neuner <gneuner2/@comcast.net> writes:
>
>> >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
>> >by users is _still_ Lisp syntax.
>>
>> Sort of. What I mean exactly is any sexpr syntax that conforms to
>> Lisp's prefix notation.
>
>Well, except that this may be useful for some special-purpose one-off
>thing, since virtually anything may be useful to a thing, but in terms
>of "describing CL", it's not meaningful to say "handles things people
>might write who have no pre-defined agreement with you" other than to
>say "the full set of things people might write".
>
>I asked earlier, I think, or maybe I started to ask and then didn't
>send it, so I'll ask again: what would one do differently if one had a
>parser for this allegedly interesting subset? Is there a goal here
>that is logically distinct from discussing what the set of numeric
>values Lisp could compute if bignums were not there? The reader does
>define readmacros so I don't see quite what people are getting at in
>discussing the properties of the reader absent readmacros. Is this
>just a discussion of making toys that will grow up to not be able to
>use the tools that bootstrapped them? Is there a proposal in play for
>extending the LL(n) concept to be usefully able to accept arbitrary
>code in the middle [as, for example, a "pratt parser" might do?] I'm
>just completely out of context as to the goal, so it keeps catching my
>eye that other readers who might be following along might be done the
>misservice of thinking this was a discussion of the properties of the
>actual CL reader, and it's not as far as I can see.
>
>I guess you _could_ be talking about some hypothetical readmacro-free
>subset, but you haven't appeared to label the conversation taht way. I
>have to say that the reason I chimed in is that it appeared that some
>people involved in the discussion (I am not sure I even know whom, and
>I'm not trying to point fingers, but generally) didn't seem realize
>readmacros are there, that they are important to day-to-day use of
>many programmers, and call for a different way of thinking than
>standard parsers tend to promote. It's like having a discussion of
>DEFSTRUCT not realizing CLOS is there and talking about whether
>Common Lisp would benefit from multiple inheritance. Anyone looking
>on would take a discussion as if it was saying "CL doesn't have that
>already."
>
>I've got nothing against hypothetical discussions, when properly
>labeled, but just starting a discussion that uses either a
>hypothetical or a gaping whole in caveat-declaration is not that
>because it risks that people reading on will get confused. My only
>goal in injecting myself here is to make sure that people don't
>mistake all the discussion here for discussion of what the real,
>non-hypothetical Lisp reader actually does and needs. As soon as I
>see appropriate caveats being mentioned in places that will avoid
>confusion, I'll recede back into the background.
>
>The only implicit constraint CL places on things, and I doubt it's
>formally spelled out, is that the syntax you pick should, if it really
>wants to sit inside other expressions [and it isn't required to do that
>since you migth want to make your own readtable with data to be parsed
>by READ that isn't intended to be embedded in s-expressions], is that
>it wants to cleanly start and stop so that it can be embedded. So if you
>make a syntax: #[...] then it's assumed that you can also make
>(... #[...]). So if you make a FORTRAN parser and it parses to end of
>file, you can't use eof as a terminator and still be embedded in other
>expressions. But other than that, it pretty much can terminate as it likes.
>
>Lisp-savvy text editors like Emacs (not talking about emacs-lisp here,
>but just the implicit constraints of using something that even thinks
>it understands Lisp) happens to usually place additional constraints,
>like that the notation should not locally confuse the syntax
>categorizations it makes, which is why #\x is chosen as it is, so that
>if Emacs doesn't know what #\ is, it will presumably still know that \
>quotes the character after it, which will mean #\a is harmless but,
>importantly, #\( will not be taken as a syntactic open-paren. So if
>you extend things in a way as to make a readmacro that returns an
>n-length string by doing #3@abc, for example, you are going to
>probably make Emacs mad because while abc is fine #3@((| is going to
>trick Emacs into thinking there are pending open parens followed by a
>pending |, all three of which characters need matches (and in the right
>order).
>
>But beyond all of that, there is still a huge wealth of difference in
>what these readmacros might do, and certainly describing those things
>in a grammar is not really useful because the grammar will have a gaping
>"or anything else" at the bottom.
>
>> Whether the symbols are pre-defined or user
>> defined is not really relevant to parsing them. Lispy macros also
>> fall into this category - even LOOP is very simple to parse in LL
>> despite not following normal Lisp conventions.
>
>I'm not talking about [expression] macros, I'm talking about reader macros.
>Which are you talking about, because LOOP is something that takes an
>expression as its argument, that is this single pointer (noted as argptr
>here) is the argument to LOOP:
>
> argptr
> |
> v
> +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
> | . | .---->| . | .---->| . | .---->| . | .---->| . | .----> ...
> +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
> v v | v v
> LOOP FOR | IN +---+---+ +---+---+
> +---+---+ | . | .---->| . | / |
> | . | . | +-|-+---+ |-|-+---+
> +-|-+-|-+ v v
> v v FIRST Y
> A B
>
>I don't know any parsers that take pointers to complex object structures as
>args, but I suppose there could be such. Ordinarily, I assume that parsers
>take either a string
>
> "LOOP FOR (A . B) IN (FIRST Y) ..."
>
>or a token stream
>
> #("LOOP" "FOR" "(" "A" "." "B" ")" "IN" "(" "FIRST" "Y" ")" ...)
>
>but Lisp uses neither of these.
>
>
>> I think part of the issue in this discussion is where the boundary is
>> drawn between parsing and analyzing/evaluating the resultant internal
>> form. The Lisp reader conflates these operations (as do parsers in
>> compilers for most languages) for efficiency, but it is always
>> technically possible to separate them and talk about just the "parser"
>> or the "evaluator".
>
>As I see it, Lisp does not conflate them. It is one of the few
>languages that keeps the separation extraordinarily clear.
>
>READ returns objects. EVAL is defined on objects.
>
>For convenience of reference, we refer by syntax to the objects that EVAL
>takes as inputs since the nature of those objects are self-evident through
>their notation thanks to the clear definition of READ. That's almost
>unheard of in other languages.
>
>> I've been talking mostly about just parsing
>> because that's how this thread began, but I understand your point.
>
>In the messages I've read and replied to, it doesn't seem clear.
>Perhaps you're assuming people read whole threads from start to end
>and recall their state, but that's asking a lot of usenet readers.

That's a good point. It is sometimes hard to include enough context
for a message to stand alone. I apologize for my role in contributing
to the confusion.

George
--
for email reply remove "/" from address

On Sep 7, 3:34 am, Kent M Pitman <pit...@nhplace.com> wrote:
> George Neuner <gneune...@comcast.net> writes:
> > >Terminology: You mean to say "pre-defined Lisp syntax". The stuff written
> > >by users is _still_ Lisp syntax.
>
> > Sort of. What I mean exactly is any sexpr syntax that conforms to
> > Lisp's prefix notation.
>
> Well, except that this may be useful for some special-purpose one-off
> thing, since virtually anything may be useful to a thing, but in terms
> of "describing CL", it's not meaningful to say "handles things people
> might write who have no pre-defined agreement with you" other than to
> say "the full set of things people might write".
>
> I asked earlier, I think, or maybe I started to ask and then didn't
> send it, so I'll ask again: what would one do differently if one had a
> parser for this allegedly interesting subset? Is there a goal here
> that is logically distinct from discussing what the set of numeric
> values Lisp could compute if bignums were not there? The reader does
> define readmacros so I don't see quite what people are getting at in
> discussing the properties of the reader absent readmacros.

If the discussion here is about writing something to parse Common
Lisp, then I agree with your implication here Kent that this is a
pretty pointless discussion. The CL reader algorithm is simple, and
obviously isn't reducable to any sub-Turing class of parsers.
However, CL is not the only interesting Lisp language. If I'm not
tripping, ISLISP doesn't have an extensible reader, which means that
its program texts can fall into some less powerful class of parsers.
The question of whether ISLISP is LL(n) might be worth wondering
about.

George Neuner <gneuner2/@comcast.net> wrote:
+---------------
| I think we're talking at crossed purposes and we should probably stop...
....
| One thing I would like to say though before we stop: the original
| poster asked a theoretical question ... whether Lisp (he did not
| specify CL) was LL(1). The answer to that is "no" regardless of
| whether readtable processing is considered - some of the basic (I want
| to avoid the word "standard") language forms are not LL(1).
....
| Also, I was not discussing CL in particular but rather sexpr based
| languages which resemble Lisp in notation.
+---------------

As you note, it is possible even in non-CL sexpr-based languages
that some of the basic forms might not be LL(1). E.g., consider a
hypothetical dialect of Scheme which adopted John Foderaro's IF*[1]:

(if* <predicate> ; [I don't know where the THENRET fits in.]
then <form>...
elseif <form>...
elseif <form>...
else <form>...)

I don't think this is LL(1), yet a simple recursive-descent parser
can handle it easily.

On the other hand, is there anything in Standard Scheme
[either IEEE or R4RS, take your pick (I'm not sure about
whether R5RS macros break this or not)] that isn't LL(1)?
Or at least LL(n) for *small* "n"?


-Rob

[1] http://www.franz.com/~jkf/ifstar.txt

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

"Thomas F. Burdick" <tburdick@gmail.com> writes:

> If I'm not tripping, ISLISP doesn't have an extensible reader, which
> means that its program texts can fall into some less powerful class
> of parsers. The question of whether ISLISP is LL(n) might be worth
> wondering about.

Yes, I don't recall it coming up for explicit discussion, so I'd hesitate
to go very far in trying to assert overt intent of any kind on this but
my personal sense is that it would be fair to say the group treated the
design more similarly to Scheme in that it blurred the "defined on structure"
vs "defined on text" issue in a neutral way. Since it didn't come up
explicitly that I remember, for all I know, some people/organizations/countries
did think one thing or the other and not all disagreed, which is entirely
possible in such groups.

But it's quite fair to say that this issue matters to other Lisp dialects
(or even to subsets of CL). Any discussion thus framed which someone felt
useful would not be one I'd want to dissuade. I just was trying to avoid the
notion that CL was accidentally characterized as "LL(1)" (or n>1) without a
clear understanding that this leaves out material details. And my main reason
for wanting to clearly make that point is that I think those details are not
well-known to everyone and lack of such clear framing can entrench
misconceptions rather than peel them back.