Atoms, Identifiers, and Primaries

[Ian Kelly]

On Wed, Apr 17, 2013 at 5:40 PM, Mark Janssen <dreamingforward at gmail.com> wrote:
> Rercursion the "bedrock" of language-design.  I don't think so.  From
> what I know, a well-defined language ends at its symbols.  It makes no
> use of "infinities".

>From what I know, you can't have a Turing-complete language without
some form of recursion.  So yeah, it's pretty damn important in
language design.

>> You cannot hope to define an infinite object such as the python
>> language (there are an infinite number of python programs) with a
>> finite specification
>
> You've committed two grave sins in C.S.:

You've just committed the grave sin of being needlessly hyperbolic.

> Conflating a programming
> language ("an infinite object such as python language") with a program
> written in that language ("there are an infinite number of python
> programs").   These two are entirely separate (at least anything
> implemented on a real computer).

Mathematically, a language (e.g. a programming language) is a set of
well-formed strings (i.e. programs) constructed from the symbols of an
alphabet (i.e. tokens).  For most languages, this set is infinite;
saying "the Python language is infinite" is equivalent to saying
"there are an infinite number of Python programs".

> Further, you've made a silly
> description of python "an infinite object such as the python
> language".  A programming language that is well defined has complete,
> finite, specification.  The fact that there are an endless number of
> programs that can be made from such is irrelevant to the language
> itself.

A finite, non-recursive grammar can only hope to accept a finite
number of strings.  To have an infinite language, the defining grammar
must then be either infinite (not practical) or recursive.

> Well now you're getting to the root of the confusion and what I'm
> arguing within the C.S. community:  there must be clear distinction
> between lambda calculii and programming languages rooted in actual
> hardware implementations.  While, traditionally, the field has not
> made much of a distinction, in practice the computational architecture
> is different.  One of these has a connection to reality and the other
> not as much ;^).

> In any case, talking about the mathematical realm *as a realm of
> Platonic thought* is irrelevant to the discussion of program spaces
> where *things actually get done*.

Of course it's relevant.  Without theory we would not have big-Oh
notation or efficient data structures or regular expressions or
context-free grammars; languages like Python would be harder to
invent.  I'm sure one could come up with a myriad other examples, but
that's enough for me.