Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #43725 > unrolled thread

Atoms, Identifiers, and Primaries

Back to article view | Back to comp.lang.python

Contents

  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

Page 1 of 2  [1] 2  Next page →

#43725 — Atoms, Identifiers, and Primaries

These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:

1.  Section 5.2.1 indicates that an identifier occurring as an atom is a name.  However, Section 2.3 indicates that identifiers are names.  My question:  can an identifier be anything other than a name?

2.  Section 5.3 defines primaries as the most tightly bound operations of Python.  What does this mean?  In particular, if an atom is a primary, what operation is the atom performing that leads to the label "most tightly bound"?  To put it a different way, I think of atoms as things (i.e. identifiers).  The documentation makes me think atoms actually do something, as opposed to being things (I think I have in my mind the difference between a noun and a verb as I write this).  Perhaps the doing in this case (or binding, if you like) is linking (binding) the identifier to the underlying object?  I think it might help if I had a better working notion of what a primary is.

3.  Section 5.3.1 offers this definition of an attributeref:
    attributeref ::= primary "." identifier

Now, I was at first a little concerned to see the non-terminal primary on the right hand side of the definition, since primary is defined to include attributeref in section 5.3 (so this struck me as circular).  Am I correct in thinking attributeref is defined this way to allow for situations in which the primary, whether an atom, attributeref (example:  an object on which a method is called that returns another object), subscription, slicing, or call, returns an object with property identifier?

These are, I know, long-winded questions.  I appreciate in advance any thoughts the group can offer.

The relevant documentation link is:  http://docs.python.org/2/reference/expressions.html#expressions

Thanks,
Bruce

[toc] | [next] | [standalone]

#43726

On Apr 17, 7:57 am, Bruce McGoveran <bruce.mcgove...@gmail.com> wrote:
> These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:
>
> 1.  Section 5.2.1 indicates that an identifier occurring as an atom is a name.  However, Section 2.3 indicates that identifiers are names.  My question:  can an identifier be anything other than a name?
>
> 2.  Section 5.3 defines primaries as the most tightly bound operations of Python.  What does this mean?  In particular, if an atom is a primary, what operation is the atom performing that leads to the label "most tightly bound"?  To put it a different way, I think of atoms as things (i.e. identifiers).  The documentation makes me think atoms actually do something, as opposed to being things (I think I have in my mind the difference between a noun and a verb as I write this).  Perhaps the doing in this case (or binding, if you like) is linking (binding) the identifier to the underlying object?  I think it might help if I had a better working notion of what a primary is.
>
> 3.  Section 5.3.1 offers this definition of an attributeref:
>     attributeref ::= primary "." identifier
>
> Now, I was at first a little concerned to see the non-terminal primary on the right hand side of the definition, since primary is defined to include attributeref in section 5.3 (so this struck me as circular).  Am I correct in thinking attributeref is defined this way to allow for situations in which the primary, whether an atom, attributeref (example:  an object on which a method is called that returns another object), subscription, slicing, or call, returns an object with property identifier?
>
> These are, I know, long-winded questions.  I appreciate in advance any thoughts the group can offer.
>
> The relevant documentation link is:  http://docs.python.org/2/reference/expressions.html#expressions
>
> Thanks,
> Bruce

The specific details of python grammar I am not deeply familiar with,
so I'll leave others to comment.
One general comment I will make is regarding your distress at what you
call 'circular'
Circular just means recursive and recursion is the bedrock for
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 -- a useful language definition must start and
end and preferably fit in one's pocket!
The trick is to find ways of making an inifinite object finitely
generated. So much of language design is a generalization of Peano's
method of defining (designing?) natural numbers:
a. 0 is a natural number
b. If x is a natural number then the successor of x (informally x+1)
is a natural number

Note 1. that if we take the above as a definition of natural no. then
its a recursive definition, in particular b. You can call it circular
if you like. Just drop the pejorative color.
Note 2. We need to add the 'informally' because + needs to be defined
in terms of the above definition and not the other way round, else we
get a bad case of recursion. Such a definition would run as
0 + y = y
Sx + y = S(x+y)
(read Sx as successor of x)

Coming closer to your question, consider the 3 expressions:
A: 2*x + 3*y
B: (2*x) + 3*y
C: 2*(x+3)*y

Informally we may say that A and B are the same whereas C is
different.
Formally all three are different.
Not only are they different as strings, their parse-trees are
different. Their evaluations as defined by the python interpreter may
give the same value to A and B... thats a separate question from yours
which is really a syntax question.

A is an a_expr because 2*x is an m_expr and 3*y is an m-expr
Since an m-expr is (a trivial instance of an) a_expr therefore 2*x is
an a_expr
Since one way of making an a_expr is by doing a_expr + m_expr (note
the recursion) therefore 2*x + 3*y is an a_expr

In short Ive described the derivation:
a_expr -> a_expr + m_expr -> a_expr + 3*y -> m_expr + 3*y -> 2*x + 3*y

The derivation of B would be longer involving fact that (2*x) is a
parent-form therefore atom
atom -> enclosure -> enclosure -> parenth_form -> (expr_list) ->
(expression)
-> (conditional-e) -> (or_test) -> (and_test) -> (or-exp) -> (xor->
exp) -> (and-exp) -> (shift-e) -> (a_expr)

[And now I got fedup of following the grammar but hopefully you get
the idea!]

[toc] | [prev] | [next] | [standalone]

#43787

On Tue, Apr 16, 2013 at 8:55 PM, rusi <rustompmody@gmail.com> wrote:
> On Apr 17, 7:57 am, Bruce McGoveran <bruce.mcgove...@gmail.com> wrote:
>> 3.  Section 5.3.1 offers this definition of an attributeref:
>>     attributeref ::= primary "." identifier
>>
>
> One general comment I will make is regarding your distress at what you
> call 'circular'
> Circular just means recursive and recursion is the bedrock for
> language-design.

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".

> 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.:  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).  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 useful language definition must start and
> end and preferably fit in one's pocket!

Likewise, a language specification must end in its symbols.

> The trick is to find ways of making an inifinite object finitely
> generated.

There is no trick involved.

> So much of language design is a generalization of Peano's
> method of defining (designing?) natural numbers:
> a. 0 is a natural number
> b. If x is a natural number then the successor of x (informally x+1)
> is a natural number

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*.

This is what this list (python) has not figured out yet, because they
look up to the theoretical C.S. field and it hasn't yet been
published.

-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#43788

On Apr 18, 9:40 am, Mark Janssen <dreamingforw...@gmail.com> wrote:
> This is what this list (python) has not figured out yet, because they
> look up to the theoretical C.S. field and it hasn't yet been
> published.

No one here idolises "the theoretical C.S. field". They *use* Python
to *get things done*, not to engage in pointless masturbation.

Please keep your computer pseudo-science nonsense to your own threads,
don't use it to derail others.

[toc] | [prev] | [next] | [standalone]

#43790

On Wed, Apr 17, 2013 at 5:29 PM, alex23 <wuwei23@gmail.com> wrote:
> On Apr 18, 9:40 am, Mark Janssen <dreamingforw...@gmail.com> wrote:
>> This is what this list (python) has not figured out yet, because they
>> look up to the theoretical C.S. field and it hasn't yet been
>> published.
>
> No one here idolises "the theoretical C.S. field". They *use* Python
> to *get things done*, not to engage in pointless masturbation.

Woah!  "no one" you say....  Interesting...

Mark

[toc] | [prev] | [next] | [standalone]

#43793

On 18/04/2013 01:41, Mark Janssen wrote:
> On Wed, Apr 17, 2013 at 5:29 PM, alex23 <wuwei23@gmail.com> wrote:
>> On Apr 18, 9:40 am, Mark Janssen <dreamingforw...@gmail.com> wrote:
>>> This is what this list (python) has not figured out yet, because they
>>> look up to the theoretical C.S. field and it hasn't yet been
>>> published.
>>
>> No one here idolises "the theoretical C.S. field". They *use* Python
>> to *get things done*, not to engage in pointless masturbation.
>
> Woah!  "no one" you say....  Interesting...
>
> Mark
>

IMHO very few cos we all know that practically beats purity.

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

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#43809

On Apr 18, 4:40 am, Mark Janssen <dreamingforw...@gmail.com> wrote:
> On Tue, Apr 16, 2013 at 8:55 PM, rusi <rustompm...@gmail.com> wrote:
> > Circular just means recursive and recursion is the bedrock for
> > language-design.
>
> Rercursion the "bedrock" of language-design.  I don't think so.

Imperative programmers may be forgiven for not understanding how
pervasive the idea of recursion is in CS.
For example most C programmers dont understand that the standard
definition of linked list is not just recursive, its mutually
recursive:
pointer <points to> struct
struct <contains> pointer

I have a collection of some of the variety of the uses of recursion in
CS here:
http://blog.languager.org/2012/05/recursion-pervasive-in-cs.html

Or see the first line of http://en.wikipedia.org/wiki/Recursion_theory
recursion theory is by definition the same subject as computation
theory

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#43800

On Wed, 17 Apr 2013 18:33:09 -0600, Ian Kelly 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.

Incorrect. Early Fortran, which was definitely Turing complete, was 
incapable of using recursion. But that doesn't matter, since any 
recursive algorithm can be re-written as iteration. So long as a language 
can iterate an indefinite number of times, it may be Turing complete.

(Languages which can only iterate a fixed number of times cannot be 
Turing complete.)

Hell, Turing machines themselves are not recursive. Since they don't have 
a concept of functions, they don't have a concept of functions that call 
themselves. A Turing machine only has a couple of trivial operations:

* read a cell
* write a cell
* advance the tape
* change direction

and so it's grammar is correspondingly trivial. Actually, talking about 
the grammar of a Turing machine is probably wrong. In practice, Turing 
machines are specified as a finite (and usually small) table of states 
and cells. See here for examples: 

http://en.wikipedia.org/wiki/Turing_machine_examples

So it isn't even correct to say that recursion is necessary for a 
language's *grammar*. However, for any real-world practical language 
(there's a reason that no practical language is based on Turing machines) 
recursive grammars are extraordinarily useful.


> 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.

I don't believe that is true, so long as the grammar has a concept of 
"zero or more" of some syntactic element. For example, suppose your 
grammar has a concept of integers, defined recursively as either a digit, 
or a digit followed by an integer:

INTEGER ::= DIGIT | DIGIT INTEGER

This can be defined more naturally as a digit followed by zero or more 
digits:

INTEGER ::= DIGIT (DIGIT)*



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#43802

On Wed, Apr 17, 2013 at 8:14 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Incorrect. Early Fortran, which was definitely Turing complete, was
> incapable of using recursion. But that doesn't matter, since any
> recursive algorithm can be re-written as iteration. So long as a language
> can iterate an indefinite number of times, it may be Turing complete.

You're also confusing "recursion" with "recursive programming".  See
the response I just gave to Mark.

[toc] | [prev] | [next] | [standalone]

#43792

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.

>> 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?

-- 
MarkJ
Tacoma, Washington

[toc] | [prev] | [next] | [standalone]

#43794

On 18/04/2013 02:04, Mark Janssen 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.
>
>>> 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

[toc] | [prev] | [next] | [standalone]

#43798

On Thu, Apr 18, 2013 at 9:40 AM, Mark Janssen <dreamingforward@gmail.com> wrote:
> On Tue, Apr 16, 2013 at 8:55 PM, rusi <rustompmody@gmail.com> wrote:
>> On Apr 17, 7:57 am, Bruce McGoveran <bruce.mcgove...@gmail.com> wrote:
>>> 3.  Section 5.3.1 offers this definition of an attributeref:
>>>     attributeref ::= primary "." identifier
>>>
>>
>> One general comment I will make is regarding your distress at what you
>> call 'circular'
>> Circular just means recursive and recursion is the bedrock for
>> language-design.
>
> 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".

There's a difference between infinite and recursive, though. I was
defining a function (it converted from JSON to an internal format) and
wanted to explain that not all of JSON would reliably round-trip (ie
be able to be translated to the internal format and then back again).
To describe what _would_ round-trip correctly, I used this simple yet
technically illegal description:

typedef valid string|array(valid)|object(string:valid)

In other words, a string is valid, and a list/array of valid elements
is valid, and a dictionary/mapping/object with string keys and valid
elements is valid. It's a recursive definition, but it can't go
infinite (self-references aren't valid - though this isn't stated by
the typedef); however, it can go arbitrarily deep.

ChrisA

[toc] | [prev] | [next] | [standalone]

#43801

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.

[toc] | [prev] | [next] | [standalone]

#43739

On Tue, Apr 16, 2013 at 8:57 PM, Bruce McGoveran
<bruce.mcgoveran@gmail.com> wrote:
> These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:
>
> 1.  Section 5.2.1 indicates that an identifier occurring as an atom is a name.  However, Section 2.3 indicates that identifiers are names.  My question:  can an identifier be anything other than a name?

Yes.  For example:

from a import b

Here "a" is an identifier but not a name, as it does not carry
object-binding semantics.

> 2.  Section 5.3 defines primaries as the most tightly bound operations of Python.  What does this mean?

"Tightly bound" here refers to operator precedence.  For example, we
say that the multiplication operator binds more tightly [to the
surrounding operands] than the arithmetic operator, because the
multiplication takes precedence.  This section defines that the most
tightly bound operations in Python are attribute references,
subscriptions, slices and calls; these always take precedence over
other neighboring operations.

> In particular, if an atom is a primary, what operation is the atom performing that leads to the label "most tightly bound"?

An atom doesn't perform an operation.  The grammar defines that a
primary can be just an atom, so that anywhere in the grammar that
expects a primary, a simple atom with no primary operation performed
on it can equally be used.

[toc] | [prev] | [next] | [standalone]

#43807

Ian於 2013年4月17日星期三UTC+8下午3時21分00秒寫道：
> On Tue, Apr 16, 2013 at 8:57 PM, Bruce McGoveran
> 
>  wrote:
> 
> > These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:
> 
> >
> 
> > 1.  Section 5.2.1 indicates that an identifier occurring as an atom is a name.  However, Section 2.3 indicates that identifiers are names.  My question:  can an identifier be anything other than a name?
> 
> 
> 
> Yes.  For example:
> 
> 
> 
> from a import b
> 
> 
> 
> Here "a" is an identifier but not a name, as it does not carry
> 
> object-binding semantics.
> 
> 
> 
> > 2.  Section 5.3 defines primaries as the most tightly bound operations of Python.  What does this mean?
> 
> 
> 
> "Tightly bound" here refers to operator precedence.  For example, we
> 
> say that the multiplication operator binds more tightly [to the
> 
> surrounding operands] than the arithmetic operator, because the
> 
> multiplication takes precedence.  This section defines that the most
> 
> tightly bound operations in Python are attribute references,
> 
> subscriptions, slices and calls; these always take precedence over
> 
> other neighboring operations.
> 
> 
> 
> > In particular, if an atom is a primary, what operation is the atom performing that leads to the label "most tightly bound"?
> 
> 
> 
> An atom doesn't perform an operation.  The grammar defines that a
> 
> primary can be just an atom, so that anywhere in the grammar that
> 
> expects a primary, a simple atom with no primary operation performed
> 
> on it can equally be used.

An atom can not be divided into further details.
An atom can be created and cloned or just referenced 
in some relations.

An object is composed of atoms linked in someway.

Of course, one can box those atoms of an object 
to make the object immutable at least in some situations
to be named and used.

[toc] | [prev] | [next] | [standalone]

#43808

Ian於 2013年4月17日星期三UTC+8下午3時21分00秒寫道：
> On Tue, Apr 16, 2013 at 8:57 PM, Bruce McGoveran
> 
>  wrote:
> 
> > These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:
> 
> >
> 
> > 1.  Section 5.2.1 indicates that an identifier occurring as an atom is a name.  However, Section 2.3 indicates that identifiers are names.  My question:  can an identifier be anything other than a name?
> 
> 
> 
> Yes.  For example:
> 
> 
> 
> from a import b
> 
> 
> 
> Here "a" is an identifier but not a name, as it does not carry
> 
> object-binding semantics.
> 
> 
> 
> > 2.  Section 5.3 defines primaries as the most tightly bound operations of Python.  What does this mean?
> 
> 
> 
> "Tightly bound" here refers to operator precedence.  For example, we
> 
> say that the multiplication operator binds more tightly [to the
> 
> surrounding operands] than the arithmetic operator, because the
> 
> multiplication takes precedence.  This section defines that the most
> 
> tightly bound operations in Python are attribute references,
> 
> subscriptions, slices and calls; these always take precedence over
> 
> other neighboring operations.
> 
> 
> 
> > In particular, if an atom is a primary, what operation is the atom performing that leads to the label "most tightly bound"?
> 
> 
> 
> An atom doesn't perform an operation.  The grammar defines that a
> 
> primary can be just an atom, so that anywhere in the grammar that
> 
> expects a primary, a simple atom with no primary operation performed
> 
> on it can equally be used.

An atom can not be divided into further details.
An atom can be created and cloned or just referenced 
in some relations.

An object is composed of atoms linked in someway.

Of course, one can box those atoms of an object 
to make the object immutable at least in some situations
to be named and used.

[toc] | [prev] | [next] | [standalone]

#43754

On 04/16/2013 10:57 PM, Bruce McGoveran wrote:
> These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:
>
>
> 3.  Section 5.3.1 offers this definition of an attributeref:
>      attributeref ::= primary "." identifier
>
> Now, I was at first a little concerned to see the non-terminal primary on the right hand side of the definition, since primary is defined to include attributeref in section 5.3 (so this struck me as circular).  Am I correct in thinking attributeref is defined this way to allow for situations in which the primary, whether an atom, attributeref (example:  an object on which a method is called that returns another object), subscription, slicing, or call, returns an object with property identifier?
>

It is circular.  Nothing wrong with that.  It means that not only can 
you use
     a.b

but also
     a.b.c

and
     a.b.c.d.e.f.g

without any explicit limit.  if a non-circular definition were to be 
attempted, you might need a few dozen rules, just to cover what someone 
*might* happen to use in an expression.  Of course normally, one doesn't 
go much beyond a.b.c in a single expression.


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#43756

On Tue, 16 Apr 2013 19:57:25 -0700, Bruce McGoveran wrote:

> These are terms that appear in section 5 (Expressions) of the Python
> online documentation.  I'm having some trouble understanding what,
> precisely, these terms mean.  I'd appreciate the forum's thoughts on
> these questions:
> 
> 1.  Section 5.2.1 indicates that an identifier occurring as an atom is a
> name.  However, Section 2.3 indicates that identifiers are names.  My
> question:  can an identifier be anything other than a name?

Yes and no.

According to the Python grammar as documented, no, identifiers are just 
another name for, er, name.

But according to common practice, yes, we call many things identifiers:

x  # a bare name, or "identifier" according to the grammar

x.attr  # name with an attribute, or "attributeref"

x[key]  # name with a subscript, or "subscription"

x[5]  # name with an indexed subscript, or "slicing"

x[start:stop:step]  # name with a slice subscript



> 2.  Section 5.3 defines primaries as the most tightly bound operations
> of Python.  What does this mean?

It means that primaries are evaluated at the highest priority. For 
example, given:

x.a+b

that is evaluated as:

(x.a) + b

rather than:

x . (a+b)


In particular, if you have a variable:

name = "Fred"

then x.name will look for an attribute "name", *not* x.Fred.


> In particular, if an atom is a
> primary, what operation is the atom performing that leads to the label
> "most tightly bound"?  To put it a different way, I think of atoms as
> things (i.e. identifiers).

Correct.


> The documentation makes me think atoms
> actually do something, as opposed to being things (I think I have in my
> mind the difference between a noun and a verb as I write this).

The only thing they do is be evaluated.




> 3.  Section 5.3.1 offers this definition of an attributeref:
>     attributeref ::= primary "." identifier
> 
> Now, I was at first a little concerned to see the non-terminal primary
> on the right hand side of the definition, since primary is defined to
> include attributeref in section 5.3 (so this struck me as circular).  Am
> I correct in thinking attributeref is defined this way to allow for
> situations in which the primary, whether an atom, attributeref (example:
>  an object on which a method is called that returns another object),
> subscription, slicing, or call, returns an object with property
> identifier?

Yes. It means you can write things like this:

module.Class.method()[0](arg).attr.name[2]['spam'].aardvark()

and have it evaluated from left to right.



With respect, I think you may be confusing yourself unnecessarily with an 
excessive concern for the formal grammar of Python. You may find it makes 
a lot more sense in practice than it makes in theory. I strongly 
recommend you open up an interactive interpreter and just play around 
with the syntax and see what happens.




-- 
Steven

[toc] | [prev] | [next] | [standalone]

#43769

Thank you all for your thoughtful replies.  I appreciate your collective insight.  I didn't mean to cast the concept of recursion in a negative light - I'm actually comfortable with the concept, at least to some extent, and I appreciate the need for its use in this documentation.  I also appreciate the need to play with expressions at the command line, to gain a feel for how expressions are evaluated.  My interest in the language's formal description arises merely out of a desire to understand as precisely as possible what happens when I hit enter at the command line, or when I run a module.  
Your answers to my initial questions in this thread and the ones I posed in another thread ("Understanding Boolean Expressions") have lead me to some follow-up questions.  Suppose I'm working at the command line, and I bind x to the value 1 and y to the value 0.  Suppose I next type x and y and hit enter.  Python returns 0 (zero).  I'm glad I checked this before sending in this post because I thought it would return a value of False based on the presence of the and operand.  My question:  what did the interpreter have to do to evaluate the expression x and y and return a value of zero?
I know the lexical analyzer has to parse the stream of characters into tokens.  I presume this parsing generates the toxens x, y, and, and a NEWLINE.  Beyond that, things get a little fuzzy, and it occurs to me that this fuzziness is the result of my looking at the expression x and y knowing full well what each token means and what I want done with them, whereas the interpreter won't know these things until it can parse the character stream and sort the tokens into some recognizable (and syntactically correct) order.
As I look at it, the expression x and y has two atoms, namely x and y.  x and y are also primaries, and they represent the most tightly bound parts of this expression (meaning they bind more tightly to their underlying objects than to the and operator).   Incidentally, how does Python figure out that the x and y in this expression refer to the x and y I previously bound to integer values?  I know there's a symbol table in each execution frame.  How does Python know to go to that table and check for x and y?
The and token represents an operator, a boolean operator to be specific.  As I look at the grammar for and_test in section 5.10 of the documentation, it would appear that the and_test resolves via not_test's definition to two comparisons, which in turn resolve to or_expr, and then via a series of binary bitwise definitions to shift_expr, then to a_expr, then to m_expr, then to u_expr, to power, and then primary, and then to atom, which lands us finally at non-terminal identifiers (i.e. x and y themselves).  
Questions:  In working through these steps, what I have actually demonstrated?  Is this how Python deconstructs an and statement with two operands?  Do I take from the fact that the progression from and_test to identifier involved reference to bitwise operators that the boolean testing of x and y involves a bitwise comparison of x and y?  I have to admit these questions are a little confusing; this may reflect the fact I am not exactly sure what it is I am trying to ask.  In general terms, I am trying to understand how Python evalutes the expression x and y in this context.
For my sanity's sake (and, perhaps, for yours) I will stop there.  I send thanks in advance for any thoughts you have on my questions.



On Tuesday, April 16, 2013 10:57:25 PM UTC-4, Bruce McGoveran wrote:
> These are terms that appear in section 5 (Expressions) of the Python online documentation.  I'm having some trouble understanding what, precisely, these terms mean.  I'd appreciate the forum's thoughts on these questions:
> 
> 
> 
> 1.  Section 5.2.1 indicates that an identifier occurring as an atom is a name.  However, Section 2.3 indicates that identifiers are names.  My question:  can an identifier be anything other than a name?
> 
> 
> 
> 2.  Section 5.3 defines primaries as the most tightly bound operations of Python.  What does this mean?  In particular, if an atom is a primary, what operation is the atom performing that leads to the label "most tightly bound"?  To put it a different way, I think of atoms as things (i.e. identifiers).  The documentation makes me think atoms actually do something, as opposed to being things (I think I have in my mind the difference between a noun and a verb as I write this).  Perhaps the doing in this case (or binding, if you like) is linking (binding) the identifier to the underlying object?  I think it might help if I had a better working notion of what a primary is.
> 
> 
> 
> 3.  Section 5.3.1 offers this definition of an attributeref:
> 
>     attributeref ::= primary "." identifier
> 
> 
> 
> Now, I was at first a little concerned to see the non-terminal primary on the right hand side of the definition, since primary is defined to include attributeref in section 5.3 (so this struck me as circular).  Am I correct in thinking attributeref is defined this way to allow for situations in which the primary, whether an atom, attributeref (example:  an object on which a method is called that returns another object), subscription, slicing, or call, returns an object with property identifier?
> 
> 
> 
> These are, I know, long-winded questions.  I appreciate in advance any thoughts the group can offer.
> 
> 
> 
> The relevant documentation link is:  http://docs.python.org/2/reference/expressions.html#expressions
> 
> 
> 
> Thanks,
> 
> Bruce

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web