Subject: Re: grammatical complexity [was: Re: simple lisp interpreter]
From: rpw3@rpw3.org (Rob Warnock)
Date: Fri, 14 Sep 2007 03:27:35 -0500
Newsgroups: comp.lang.lisp
Message-ID: <RM2dnRnedf5q2HfbnZ2dnUVZ_ommnZ2d@speakeasy.net>
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-repository/doc/pubs/express.ps.gz
    http://www.cs.rice.edu/CS/PLT/Publications/Scheme/scp91-felleisen.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