simple lisp interpreter

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

> I think we're talking at crossed purposes and we should probably stop
> before it goes any further.

Well, that wasn't my intent either. Especially since you raise other
interesting questions here.

> 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.

Actually, I wish there were some notation of "grammatical complexity" that
was different than mere syntax-tokenization and grouping, which I might call
"syntactic complexity". In a sense, one might say CL has three levels, not
two:

text -> syntax -> structure -> grammar -> meaning

where other languages have just

text -> syntax/grammar -> meaning

I don't know of a particular literature on grammatical complexity, other
than perhaps the vaguely similar but perhaps analogous distinctions like
propositional/predicate logics.

Since you raise the point, is there anyone listening who knows
terminology for this that I might usefully apply in my own thoughts on
this? It might be related to the notion of expressional power I
sometimes throw around (and have informal ideas about how to express
that I've never written down) as an alternative to Turing power (which
is such a flat space that all things are equivalent and hence useless
to talk about as different); I think programs differ expressionally so
I posit some possible definition that would explain why.

That would be a more fun discussion for me. But I didn't mean to conflate
it with your discussion here, I just meant to say that Lisp tends to lean
heavy on grammatical issues and to eschew the syntactic.

Note further that I might mean to include macros in a discussion of
grammatical complexity, or I might just mean primitive language
syntax. I'm neutral on that. In a sense, macros give you the ability
to lift yourself to what seems like a more powerful space. But if you
can't describe the power as other than "Turing powerful" then you're,
by definition, not changing the power and you have to (bogusly) assume
you've done yourself no favor by moving from assembly language to
BASIC to Lisp to whatever; you're obliged to conclude that all of
these are equally good and to wonder why anyone spends time in
anything other than assembly language... So macros are probably not
the enabling factor of the power I refer to, but they are one way (of
possibly several) to enable experiments about the importance of that
power since they can shift the set of available
operators/forms/constructs and allow one to see whether programs
become easier/harder to write in the world augmented by their
presence. (Functional abstraction, object orientation, etc. are
perhaps others in the space. My question goes to the measuring of
power, not to the specific ways the capability manifests.)

I hope I'm making my question clear, but somehow I fear I'm not.
Maybe I've said it well enough that someone can clean it up and re-ask
it. But it seems to be the question that vexxes marketeers--i.e.,
how do I explain to someone why buying x or y paradigm adds "power"
other than just "telling success stories"...?

> 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.

No harm done, and no apology needed from my point of view, but I do
appreciate the clarification of intent just to put the discussion into
context.

Kent M Pitman <pitman@nhplace.com> writes:

> Since you raise the point, is there anyone listening who knows
> terminology for this that I might usefully apply in my own thoughts on
> this?

What you call "meaning" is typically called "semantics" in the
literature. For syntax, one should distinguish between concrete syntax
and abstract syntax. The concrete syntax also contains whitespace,
newlines etc. that are of no relevance in the abstract syntax.

> Note further that I might mean to include macros in a discussion of
> grammatical complexity, or I might just mean primitive language

A misunderstanding I sometimes see in this group is that the concrete
syntax must necessarily closely correspond to the abstract syntax in
order for macros to be useful; but that's not the case: The concrete
syntax is completely peripheral in this regard, and many languages
provide, for example, both infix and prefix concrete syntax, yet a
completely uniform abstract syntax that macros can easily work on.

On Sep 10, 8:20 pm, Markus Triska <e0225...@stud4.tuwien.ac.at> wrote:
> A misunderstanding I sometimes see in this group is that the concrete
> syntax must necessarily closely correspond to the abstract syntax in
> order for macros to be useful; but that's not the case: The concrete
> syntax is completely peripheral in this regard, and many languages
> provide, for example, both infix and prefix concrete syntax, yet a
> completely uniform abstract syntax that macros can easily work on.

What are the downsides (if any) to this approach?

Is all you need to do is define CONCRETE->ABSTRACT and its inverse?


Thanks,
Tayssir

Tayssir John Gabbour <tayssir.john@googlemail.com> writes:

> What are the downsides (if any) to this approach?
> Is all you need to do is define CONCRETE->ABSTRACT and its inverse?

As a *user*, you don't have to do anything, as you typically only see
a representation of the abstract syntax in macros. Functions like
"read" perform the concrete->abstract transformation for you. The
inverse (abstract->concrete) is part of what a "pretty-printer" does
and is typically not well-defined (there are several valid outputs).

As an *implementer*, you have to extend your parser to handle the
variants of the concrete syntax; that's hardly news: Concrete and
abstract syntax differ in Lisp as well (otherwise you'd have to handle
comments and the like in macros), and there are many concrete variants
(more newlines etc.) for one and the same abstract syntax tree.

On 10 Sep 2007 13:03:51 -0400, Kent M Pitman <pitman@nhplace.com>
wrote:

>George Neuner <gneuner2/@comcast.net> writes:
>
>> I think we're talking at crossed purposes and we should probably stop
>> before it goes any further.
>
>Well, that wasn't my intent either. Especially since you raise other
>interesting questions here.
>
>> 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.
>
>Actually, I wish there were some notation of "grammatical complexity" that
>was different than mere syntax-tokenization and grouping, which I might call
>"syntactic complexity".

I'm not sure there is much literature on this topic pertaining to
programming ... syntactic complexity is studied much more for natural
languages than for synthetic ones. Most literature on the complexity
of programming languages relates them to elements of the Chomsky
hierarchy.


>In a sense, one might say CL has three levels, not two:
>
> text -> syntax -> structure -> grammar -> meaning
>
>where other languages have just
>
> text -> syntax/grammar -> meaning
>
>I don't know of a particular literature on grammatical complexity, other
>than perhaps the vaguely similar but perhaps analogous distinctions like
>propositional/predicate logics.

All "interesting" languages - ie. those that have meaning - require
some kind of organizing structure.

I would order it differently (without including grammar) as

text -> syntax -> structure -> meaning

I don't include grammar because it is too generic a term and because
it covers syntax (more on that below).


>Since you raise the point, is there anyone listening who knows
>terminology for this that I might usefully apply in my own thoughts on
>this?

Is Chris F. Clark in the house? I know he lurks here.


>It might be related to the notion of expressional power I
>sometimes throw around (and have informal ideas about how to express
>that I've never written down) as an alternative to Turing power (which
>is such a flat space that all things are equivalent and hence useless
>to talk about as different); I think programs differ expressionally so
>I posit some possible definition that would explain why.
>
>That would be a more fun discussion for me. But I didn't mean to conflate
>it with your discussion here, I just meant to say that Lisp tends to lean
>heavy on grammatical issues and to eschew the syntactic.

I'm not sure I understand fully how you are using the terms. I'm
going to expound a little bit on how I view Lisp in linguistic terms.
Feel free to jump on my head (you will anyway 8-).


First, "syntax" has dual meaning - in linguistics it can refer to both
of a pattern and an instance of a pattern. It is proper to speak of
"a syntax" which denotes a particular pattern form which is a subset
of a grammar. Conversely a grammar can contain multiple syntax
patterns. Additionally, "syntax" is both singular and plural - it can
refer to one form or many and I will use it, in context, either way.

With Lisp the discussion is complicated by the issue of semantics.
Language semantics are, necessarily, defined on syntax[*] because
syntax denotes structure and structure denotes meaning. The question
then is, what exactly is the syntax of Lisp?
[*] There are, of course, additional semantics not defined by syntax
but we can ignore them for the moment.


Unlike virtually all other languages, Lisp defines a particular
(initial) intermediate representation for code composed of structured
graphs of Lisp objects, and further Lisp defines mappings from text to
objects and from a stylized form of source text, s-exprs, to graphs of
objects. However, not all text maps to legal code or data forms ...
Lisp's semantics are defined on only a particular set of objects and
graphs. Thus, I would say that the actual syntax of Lisp is that
particular set of structured object graphs for which semantics have
been defined. The grammar however, is the set of all possible
s-exprs, including those that don't map to legal code forms, _plus_
the set of all constructible Lisp objects which may or may not have a
human readable s-expr representation.

We've been going back and forth recently about how the readtable
changes things, but I really don't think it does. The result of
reading must be a graph of Lisp objects, but every possible Lisp
object is already recognized as being part of the grammar, therefore
there is no impact on grammar. Similarly, there is no effect on
syntax - either the external form is being compiled to Lisp, in which
case the result must be a legal code or data form governed by Lisp's
semantics, or the external form is being transformed in some way
outside of Lisp semantics in which case the result is undefined with
respect to Lisp.


>Note further that I might mean to include macros in a discussion of
>grammatical complexity, or I might just mean primitive language
>syntax. I'm neutral on that. In a sense, macros give you the ability
>to lift yourself to what seems like a more powerful space. But if you
>can't describe the power as other than "Turing powerful" then you're,
>by definition, not changing the power and you have to (bogusly) assume
>you've done yourself no favor by moving from assembly language to
>BASIC to Lisp to whatever; you're obliged to conclude that all of
>these are equally good and to wonder why anyone spends time in
>anything other than assembly language... So macros are probably not
>the enabling factor of the power I refer to, but they are one way (of
>possibly several) to enable experiments about the importance of that
>power since they can shift the set of available
>operators/forms/constructs and allow one to see whether programs
>become easier/harder to write in the world augmented by their
>presence. (Functional abstraction, object orientation, etc. are
>perhaps others in the space. My question goes to the measuring of
>power, not to the specific ways the capability manifests.)
>
>I hope I'm making my question clear, but somehow I fear I'm not.

I guess it depends on how you define "power". I'm not aware of any
objective scale relating languages in terms of power ... apart from
classifying them as whether or not they are Turing complete.

I doubt anyone here would argue with the opinion that Lisp is "more
powerful" than C, but in fact they are both Turing complete and
therefore equivalent in power. Thus the ranking of Lisp above C is
really based on something else. Ease of abstraction, ease of
formulation and support for the programmer are perhaps closer to the
actual criteria, but none of these necessarily equate to additional
power. Nor do first class functions, higher order functions,
reflection, metaprogramming, etc., ad nauseam.

Chomsky ranks (classes of) languages according to the complexity of
their grammar - which affects the potential complexity of their
syntax. Power is a function of semantics and semantics are dependent
on syntactical complexity ... obviously there must be sufficient
complexity to be able to distinguish different semantics. But Lisp is
an existence proof that the syntactic complexity required to achieve
Turing completeness is quite low.


>Maybe I've said it well enough that someone can clean it up and re-ask
>it. But it seems to be the question that vexxes marketeers--i.e.,
>how do I explain to someone why buying x or y paradigm adds "power"
>other than just "telling success stories"...?
>
>> 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.
>
>No harm done, and no apology needed from my point of view, but I do
>appreciate the clarification of intent just to put the discussion into
>context.

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

George Neuner <gneuner2/@comcast.net> wrote:
+---------------
| Kent M Pitman <pitman@nhplace.com> wrote:
| >Actually, I wish there were some notation of "grammatical complexity"
| >that was different than mere syntax-tokenization and grouping, which
| >I might call "syntactic complexity".
|
| I'm not sure there is much literature on this topic pertaining to
| programming ...
+---------------

Here's the main one I remember reading [but it's from 16 years ago!!]:

ftp://ftp.cs.indiana.edu/pub/scheme-.../express.ps.gz
http://www.cs.rice.edu/CS/PLT/Public...elleisen.ps.gz
Matthias Felleisen, "On the Expressive Power of Programming Languages",
Science of Computer Programming, 1991.

Abstract
The literature on programming languages contains an abundance
of informal claims on the relative expressive power of
programming languages, but there is no framework for formalizing
such statements nor for deriving interesting consequences.
As a first step in this direction, we develop a formal notion
of expressiveness and investigate its properties. To validate
the theory, we analyze some widely held beliefs about the
expressive power of several extensions of functional languages.
Based on these results, we believe that our system correctly
captures many of the informal ideas on expressiveness, and
that it constitutes a foundation for further research in this
direction.


-Rob

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