Re: Atoms, Identifiers, and Primaries

References	<66e78281-542b-41b3-a56d-04bf736d1e0a@googlegroups.com> <14a9ca59-218d-4dec-9e03-b7ac6b92d378@af5g2000pbd.googlegroups.com> <CAMjeLr9Z9f1y1NyLs44UqGYrnEEpABxouB4pr=xaaOdB-+HfLA@mail.gmail.com> <CALwzidmyVjmiqu5L7rNN=y62TP2JPudE-AGS32jmBPQ8b6upzw@mail.gmail.com> <CAMjeLr_i76ADLRg91BtqYGmKTV89HCBdc0dter7Rg-2O1AGNvQ@mail.gmail.com>
From	Ian Kelly <ian.g.kelly@gmail.com>
Date	2013-04-17 21:10 -0600
Subject	Re: Atoms, Identifiers, and Primaries
Newsgroups	comp.lang.python
Message-ID	<mailman.751.1366254671.3114.python-list@python.org> (permalink)

Show all headers | View raw

On Wed, Apr 17, 2013 at 7:04 PM, Mark Janssen <dreamingforward@gmail.com> wrote:
> On Wed, Apr 17, 2013 at 5:33 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> 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.
>
> A Turing-complete language generally has items that are defined in
> terms of other, simpler items, but this is not called recursion in any
> C.S. paper I know.
> In C.S. of my world, recursion is a specific term that is related to
> functional calculii.  This type of recursion is sometimes often found
> in imperative/iterative languages, but is rooted in the fomer.

You are thinking of recursive procedures.  Recursion is the more
general concept of self-repetition.  In a programming language, it can
be implemented by recursive procedures, or it can equivalently be
implemented by looping constructs.

Incidentally, in computability theory (also known as "recursion
theory"), "recursive" is basically a synonym for "computable", which
relates back to my point that recursion is necessary for
Turing-completeness; a Turing-complete language is one that can
compute any computable (i.e. recursive) function.

>>> 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).
>
> Mathematically, perhaps, but from C.S. theory, a language is a
> fully-specified set of expressions and tokens which are considered
> valid -- it's grammar.

Sorry, but as computer science *is* math, the computer science
definition is the same as the mathematical one.  See for example this
CS paper which formally defines "language" as I described:

http://www.cs.ucr.edu/~jiang/cs215/tao-new.pdf

>> For most languages, this set is infinite;
>
> This set is always finite, as you can see on the specification for
> Python's language.

No, the set of valid Python programs is not finite.

>> saying "the Python language is infinite" is equivalent to saying
>> "there are an infinite number of Python programs".
>
> I don't think Guido would agree that "the Python language is
> infinite", but then perhaps he doesn't care either.
>
>> A finite, non-recursive grammar can only hope to accept a finite
>> number of strings.
>
> Is the language we're speaking in now one with a finite, non-recursive grammar?

No, English is also recursive.

Thread

Atoms, Identifiers, and Primaries Bruce McGoveran <bruce.mcgoveran@gmail.com> - 2013-04-16 19:57 -0700
  Re: Atoms, Identifiers, and Primaries rusi <rustompmody@gmail.com> - 2013-04-16 20:55 -0700
    Re: Atoms, Identifiers, and Primaries Mark Janssen <dreamingforward@gmail.com> - 2013-04-17 16:40 -0700
      Re: Atoms, Identifiers, and Primaries alex23 <wuwei23@gmail.com> - 2013-04-17 17:29 -0700
        Re: Atoms, Identifiers, and Primaries Mark Janssen <dreamingforward@gmail.com> - 2013-04-17 17:41 -0700
        Re: Atoms, Identifiers, and Primaries Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-04-18 02:04 +0100
      Re: Atoms, Identifiers, and Primaries rusi <rustompmody@gmail.com> - 2013-04-18 00:40 -0700
    Re: Atoms, Identifiers, and Primaries Ian Kelly <ian.g.kelly@gmail.com> - 2013-04-17 18:33 -0600
      Re: Atoms, Identifiers, and Primaries Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-18 02:14 +0000
        Re: Atoms, Identifiers, and Primaries Ian Kelly <ian.g.kelly@gmail.com> - 2013-04-17 21:12 -0600
    Re: Atoms, Identifiers, and Primaries Mark Janssen <dreamingforward@gmail.com> - 2013-04-17 18:04 -0700
    Re: Atoms, Identifiers, and Primaries Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-04-18 02:08 +0100
    Re: Atoms, Identifiers, and Primaries Chris Angelico <rosuav@gmail.com> - 2013-04-18 11:56 +1000
    Re: Atoms, Identifiers, and Primaries Ian Kelly <ian.g.kelly@gmail.com> - 2013-04-17 21:10 -0600
  Re: Atoms, Identifiers, and Primaries Ian Kelly <ian.g.kelly@gmail.com> - 2013-04-17 01:21 -0600
    Re: Atoms, Identifiers, and Primaries 88888 Dihedral <dihedral88888@googlemail.com> - 2013-04-17 21:29 -0700
    Re: Atoms, Identifiers, and Primaries 88888 Dihedral <dihedral88888@googlemail.com> - 2013-04-17 21:29 -0700
  Re: Atoms, Identifiers, and Primaries Dave Angel <davea@davea.name> - 2013-04-17 07:07 -0400
  Re: Atoms, Identifiers, and Primaries Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-17 11:43 +0000
  Re: Atoms, Identifiers, and Primaries Bruce McGoveran <bruce.mcgoveran@gmail.com> - 2013-04-17 10:15 -0700
    Re: Atoms, Identifiers, and Primaries Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-04-18 04:43 +1000
      Re: Atoms, Identifiers, and Primaries rusi <rustompmody@gmail.com> - 2013-04-18 10:04 -0700

csiph-web