Atoms, Identifiers, and Primaries

[Mark Lawrence]

On 18/04/2013 02:04, Mark Janssen wrote:
> On Wed, Apr 17, 2013 at 5:33 PM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>> 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.
>
> 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.
>
>>> 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.
>
>> For most languages, this set is infinite;
>
> This set is always finite, as you can see on the specification for
> Python's language.
>
>> 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?
>

Thanks for reminding me that I must add food for the trolls to the 
bottom of my shopping list.

-- 
If you're using GoogleCrap™ please read this 
http://wiki.python.org/moin/GoogleGroupsPython.

Mark Lawrence