Atoms, Identifiers, and Primaries
Ian Kelly
ian.g.kelly at gmail.com
Wed Apr 17 20:33:09 EDT 2013
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.
More information about the Python-list
mailing list