Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAMjeLr9Z9f1y1NyLs44UqGYrnEEpABxouB4pr=xaaOdB-+HfLA@mail.gmail.com>
References: <66e78281-542b-41b3-a56d-04bf736d1e0a@googlegroups.com> <14a9ca59-218d-4dec-9e03-b7ac6b92d378@af5g2000pbd.googlegroups.com> <CAMjeLr9Z9f1y1NyLs44UqGYrnEEpABxouB4pr=xaaOdB-+HfLA@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Wed, 17 Apr 2013 18:33:09 -0600
Subject: Re: Atoms, Identifiers, and Primaries
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.741.1366245233.3114.python-list@python.org>
Lines: 57
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:43789

On Wed, Apr 17, 2013 at 5:40 PM, Mark Janssen <dreamingforward@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.