tag:blogger.com,1999:blog-86994315087303757432024-03-08T05:47:03.486-08:00The History of PythonA series of articles on the history of the Python programming language and its community.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.comBlogger32125tag:blogger.com,1999:blog-8699431508730375743.post-17471258818873715242018-05-12T09:37:00.000-07:002019-03-22T22:26:33.236-07:00The origins of pgenDavid Beazley's talk at US PyCon 2018, about parser generators, reminded me I should write a bit about its history. Here's a brief brain dump (maybe I'll expand later).<br />
<br />
There are actually two pgens. The original, in C, and a rewrite in Python, under lib2to3/pgen2.<br />
<br />
I wrote both. The original was actually the first code I wrote for Python. Although technically I had to write the lexer first (pgen and Python share their lexer, pgen just doesn't have any uses for most tokens).
<br />
<br />
The reason for writing my own parser generator was that at the time the landscape of parser generators (that I was familiar with) was pretty sparse -- basically there was Yacc (the GNU rewrite named Bison existed, but I don't know if I knew); or you could write a parser by hand (which is what most people did). I had used Yacc in college and was familiar with how it worked from the Dragon book, but for some reason I didn't like it much; IIRC I found it hard to reason about what the limitations on an LALR(1) grammar would be. I was also familiar with LL(1) parsers and had written some serious recursive-descent LL(1) parsers by hand -- I liked that fine but I was also familiar (again from the Dragon book) with LL(1) parser generation techniques, and I had one improvement over that that I wanted to try out: using regular expressions (sort of) instead of the standard BNF format. The Dragon book had also taught me how to turn regular expressions into DFAs, so I combined all that and pgen was born. [<b>Update:</b> see below for a slightly different version for the reason.]<br />
<br />
I was not familiar with more advanced techniques, or I deemed them too inefficient. (I think most people working in parsers did, at the time.)
<br />
<br />
For the lexer I decided I would not use a generator -- I had a much lower opinion of Lex than of Yacc, since the version of Lex that I was familiar with would just segfault when trying to scan a token longer than 255 bytes (really!). Also I figured that indentation would be hard to teach to a lexer generator.
<br />
<br />
The story of pgen2 is quite different: I was employed by a startup in San Mateo (Elemental Security, it died in 2007, after I had left and joined Google) where I was given the task to design a custom language (for security assertions about system configuration), and was given pretty much free reign. I decided to design something vaguely like Python, implemented in Python, and decided that I wanted to reuse pgen, but with a backend in Python, using tokenize.py as the lexer. So I just rewrote the exact algorithm from pgen in Python and then moved on to build the rest of that language. Open-sourcing the tooling made sense to management so they quickly approved that, and some time later (I had probably moved on to Google by then?) it made sense to use those tools for 2to3. (It was easy to generate a Python parser with it because the input format was identical to the original pgen -- I just had to feed the Grammar file into the tool. :-)<br />
<br />
<b>Update: more color behind my reason for creating pgen</b><br />
<br />
<div>
I don't quite recall why I did things this way but I just peeked at <a href="https://en.wikipedia.org/wiki/LL_parser#Conflicts" target="_blank">https://en.wikipedia.org/wiki/<wbr></wbr>LL_parser#Conflicts</a>
and I may have seen this as a new (to me) way of addressing the various
conflicts that may occur without adding helper rules. E.g. what that
page calls left-factoring (replace A -> X | X Y Z with A -> X B; B
-> Y Z | <empty>) I would rewrite instead as A -> X [Y Z].
IIRC the parsing engine (function syntacticAnalysis from earlier on that
page) still works with parsing tables derived from such rules through
the regex -> NFA -> DFA transformation; I think the requirement
not to have any empty productions was required here.</div>
<div>
<br /></div>
<div>
The
other thing I came up with was that the parse tree nodes produced by
the parsing engine would have a variable number of children, e.g. for
the rule A -> X [Y Z] above the node for A would have either 1 child
(X) or 3 (X Y Z). A simple check in the code generator would then be
needed to determine which alternative the parser had encountered. (This
has turned out to be a double-edged sword, and later we added a parse
tree -> AST step driven by a separate generator to simplify the byte
code generator.)</div>
<div>
<br /></div>
<div>
So the reason I used regular expressions
was probably to make the grammar easier to read: after resolving the
conflicts using the needed rewrites I found the grammar not all that
easy to read (insert Zen of Python reference here :-) hence the regular
expressions -- no helper rules with awkward names, and [optional] parts
or repeated* parts are closer to how I think about a typical language's
syntax. It certainly did not change the power beyond LL(1), nor did it
reduce the power. And yes by "regular expressions" I meant the EBNF
conventions -- I'm not sure that at the time "EBNF" was a well-defined
notation, it might just have meant any extension to BNF.</div>
<div>
<br /></div>
<div>
Converting
EBNF to BNF and taking it from there would cause awkward extra parse
tree node types, so I don't think that would have been an improvement.</div>
<div>
<br /></div>
If
I had to do it all over again I might opt for a more powerful parsing
engine, perhaps a version of LALR(1) (i.e. Yacc/Bison). There are
several areas of the grammar where something more powerful
than LL(1) would be helpful, e.g. keyword args: the rule 'arg: [NAME =]
expr' is not a valid rule, since NAME occurs in the FIRST-set of expr
and the algorithm doesn't handle that. IIRC LALR(1) can handle it. But
keyword args were several years in the future when I wrote the first
version of pgen, and I didn't want to redo the parser at that point.<br />
<br />
<b>UPDATE March 2019:</b> Python 3.8 will drop the C version of pgen, in favor of a tweaked version of pgen2. See <a href="https://github.com/python/cpython/pull/11814">https://github.com/python/cpython/pull/11814</a>.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com0tag:blogger.com,1999:blog-8699431508730375743.post-60966821692984309562013-11-11T16:29:00.004-08:002013-11-11T16:29:45.913-08:00The history of bool, True and FalseWriting up the reasons why True and False, when introduced, weren't reserved words, I realized there's another interesting lesson in the history of Python's bool type.
It was formally introduced in Python 2.3, as a new type with two constants, and the type was introduced in <a href="http://www.python.org/dev/peps/pep-0285/" target="_blank">PEP 285</a> ("Adding a bool type").<br />
<br />
But bool, True and False were also introduced in Python 2.2.1 (a bugfix release!). The Misc/NEWS file said:<br />
<blockquote class="tr_bq">
<div style="background-color: white; color: #222222; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">
<div>
<span style="font-family: "Courier New",Courier,monospace;">What's New in Python 2.2.1 final?</span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;">Release date: 10-Apr-2002</span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;">==============================</span><wbr></wbr><span style="font-family: "Courier New",Courier,monospace;">===</span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;"><br /></span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;">Core and builtins</span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;"><br /></span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;">- Added new builtin function bool() and new builtin constants True and</span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;"> False to ease backporting of code developed for Python 2.3. In 2.2,</span></div>
<div>
<span style="font-family: "Courier New",Courier,monospace;"> bool() returns 1 or 0, True == 1, and False == 0.</span></div>
</div>
</blockquote>
<span style="font-size: small;"><span style="font-family: inherit;"><br class="Apple-interchange-newline" /></span></span>
<span style="font-size: small;"><span style="font-family: inherit;"><span style="background-color: white; color: #222222; display: inline ! important; float: none; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">This was the last (and the most criti<span style="font-family: inherit;">cized) time we added a new feature in a bugfix release -- we'd never do that these days. </span></span></span><span style="font-family: inherit;"><span style="background-color: white; color: #222222; display: inline ! important; float: none; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">Also note that bool/True/False in 2.2.1 were different from 2.3: in 2.3, bool is a new type; in 2.2.1, bool() is a built-in function and the constants are just ints.</span></span></span><br />
<br />
<span style="font-size: small;"><span style="font-family: inherit;"><span style="background-color: white; color: #222222; display: inline ! important; float: none; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">The chronology is also interesting: the proper new bool type was introduced in 2.3a1, released on Dec 31 2002, well after the above-mentioned 2.2.1 release. And the final 2.3 release didn't come out until July 29 2003. And yet, the above comment talks about backporting from 2.3 to 2.2.1. PEP 285 was created on March 8, 2002, accepted on April 3, and declared final on April 11 (i.e. after Python 2.2.1 was released). I'm assuming that by then the proper bool implementation had landed in the 2.3 branch. That's a breakneck pace compared to how we do things a decade later!</span></span></span>Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com0tag:blogger.com,1999:blog-8699431508730375743.post-55262351312172914402013-11-10T14:40:00.000-08:002013-11-11T16:11:22.366-08:00The story of None, True and False (and an explanation of literals, keywords and builtins thrown in)I received an interesting question in the mail recently:<br />
<blockquote class="tr_bq">
<i>What is the difference between keywords and literals? Why are True and False keywords rather than literals in python3?</i> </blockquote>
<blockquote class="tr_bq">
<i>I was horrified recently to find that assigning to True/False works in
python2. So I went digging, and found that True and False were created
to be 'constants' like None in PEP 285. Assignment to None was
disallowed in 2.4, but not to True/False until python3. Was there a
reason None was originally built as a variable rather than a literal? </i></blockquote>
Let's start with the first question: keywords and literals.<br />
<br />
A keyword, in the context of defining the syntax of a language, also known as a reserved word, is something that looks like an identifier in the language, but from the parser's point of view act like a token of the language. An identifier is defined as a sequence of one or more letters, digits and underscores, not starting with a digit. (This is Python's definition, but many languages, like C or Java, use the same or a very similar definition.)<br />
<br />
The important thing to remember about keywords is that a keyword cannot be used to name a variable (or function, class, etc.). Some well-known keywords in Python include 'if', 'while', 'for', 'and', 'or'.<br />
<br />
A literal, on the other hand, is an element of an expression that describes a constant value. Examples of literals are numbers (e.g. 42, 3.14, or 1.6e-10) and strings (e.g. "Hello, world"). Literals are recognized by the parser, and the exact rules for how literals are parsed are often quite subtle. For example, these are all numeric literals in Python 3:<br />
<blockquote class="tr_bq">
123<br />
1.0<br />
1.<br />
.01e10<br />
.1e+42<br />
123.456e-100<br />
0xfffe<br />
0o755</blockquote>
but these are not:<br />
<blockquote class="tr_bq">
. (dot)<br />
e10 (identifier)<br />
0y12 (the literal 0 followed by the identifier y12)<br />
0xffe+10 (the literal 0xffe followed by a plus sign and and the number 10)</blockquote>
Note the distinction between a constant and a literal. We often write code defining "constants", e.g.<br />
<blockquote class="tr_bq">
MAX_LEVELS = 15</blockquote>
Here, 15 is a literal, but MAX_LEVELS is not -- it is an identifier, and the all-caps form of the name suggests to the reader that it is probably not changed anywhere in the code, which means that we can consider it a constant -- but this is just a convention, and the Python parser doesn't know about that convention, nor does it enforce it.<br />
<br />
On the other hand, the parser won't let you write<br />
<blockquote>
15 = MAX_LEVELS</blockquote>
This is because the left-hand side of the assignment operator (=) must be a variable, and a literal is not a variable. (The exact definition of variable is complex, since some things that look like expressions are also considered to be variables, such as d[k], (a, b), and foo.bar -- but not f() or () or 42. This definition of variable is also used by the "del" statement.)<br />
<br />
Now on to None, True and False.<br />
<br />
Let's begin with None, because it has always been in the language. (True and False were relatively recent additions -- they first made their appearance in Python 2.2.1, to be precise.) None is a singleton object (meaning there is only one None), used in many places in the language and library to represent the absence of some other value. For example, if d is a dictionary, d.get(k) will return d[k] if it exists, but None if d has no key k. In earlier versions of Python, None was just a "built-in name". The parser had no special knowledge of None -- just like it doesn't have special knowledge of built-in types like int, float or str, or built-in exceptions like KeyError or ZeroDivisionError. All of these are treated by the parser as identifiers, and when your code is being interpreted they are looked up just like any other names (e.g. the functions and variables you define yourself). So from the parser's perspective, the following are treated the same, and the parse tree it produces (<name> = <name>) is the same in each case:<br />
<blockquote class="tr_bq">
x = None<br />
x = int<br />
x = foobar</blockquote>
On the other hand, the following produce different parse trees (<name> = <literal>):<br />
<blockquote class="tr_bq">
x = 42<br />
x = 'hello'</blockquote>
because the parser treats numeric and string literals as different from identifiers. Combining this with the earlier MAX_LEVEL examples, we can see that if we swap the left and right hand sides, the first three will still be accepted by the parser (<name> = <name>), while the swapped version of the second set will be rejected (<literal> = <name> is invalid).<br />
<br />
The practical consequence is that, if you really want to mess with your readers, you can write code that reassigns built-ins; for example, you could write:<br />
<blockquote class="tr_bq">
int = float<br />
def parse_string(s):<br />
return int(s)<br />
print(parse_string('42')) # Will print '42.0'</blockquote>
Some of you may respond to this with "So what? Reasonable programmers don't write such code." Others may react in the opposite way, saying "Why on earth does the language allow assignment to a built-in name like 'int' at all?!"<br />
<br />
The answer is subtle, and has to do with consistency and evolution of the language. I bet that without looking it up you won't be able to give a complete list all built-in names defined by Python. (I know I can't.) Moreover, I bet that many of you won't recognize every single name on that list. (To see the list, try typing dir(__builtins__) at the Python command prompt.)<br />
<br />
Take for example the weird built-ins named copyright, credits or license. They exist so that we can mention them in the greeting shown when you start Python interactively:<br />
<blockquote class="tr_bq">
<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">Python 3.4.0a4+ (default:0917f6c62c62, Oct 22 2013, 10:55:35)<br />[GCC 4.2.1 Compatible Apple LLVM 4.2 (clang-425.0.28)] on darwin<br />Type "help", "copyright", "credits" or "license" for more information.<br />>>> credits<br />Thanks to CWI, CNRI, BeOpen.com, Zope Corporation and a cast of thousands<br />for supporting Python development. See www.python.org for more information.<br />>>> </span></span></blockquote>
In order for this to work, we made them built-ins. But does this mean you shouldn't be allowed to use 'credits' as a variable or parameter name? I think not. Certainly many people don't realize that these esoteric built-ins even exist, and they would be surprised if they were prevented from using them as variable names. From here, it's just a gradual path. Many people write functions or methods with arguments named str or len, or with names like compile or format. Moreover, suppose you wrote some Python 2.5 code where you used bytes as a variable name. In Python 2.6, we added a built-in function named 'bytes' (it's an alias for str, actually). Should your code now be considered invalid? There's no reason for that, and in fact your code will be fine. (Even in Python 3, where bytes is one of the fundamental types.)<br />
<br />
On the other hand, you cannot have a variable named 'if' or 'try', because these are reserved words (keywords) that are treated special by the parser. Because you cannot use these as variable or function names anywhere, ever, in any Python program, everyone using Python has to know about all the reserved words in the language, even if they don't have any need for them. For this reason, we try to keep the list of reserved words small, and the core developers hem and haw a lot before adding a new reserved word to the language.<br />
<br />
In fact, many proposed new features have been killed because they would require a new keyword; others have been modified to avoid that need. Also, when we do decide to add a new keyword, we start a deprecation campaign at least one release before the new keyword is introduced, warning developers to choose a different name for their variables. (There's also a trick to allow developers to choose to use the new keyword right away; this is why we have e.g. "from __future__ import with_statement".)<br />
<br />
There's no such concern for built-ins. Code that happens to use the name of a new built-in as a variable or function name will continue to function (as long as you don't also try to use the new built-in in the same function). While we still try to be conservative with the introduction of new built-ins, at least we don't have to worry about breaking working code by merely adding something to the language. The (small) price we pay for this is the possibility that some joker intentionally redefines a built-in just to confuse others. But there are tons of other ways to write unreadable code, and I don't see this as a particularly bad problem.<br />
<br />
So, after this long detour about built-ins vs. keywords, back to None. Why did we eventually make None a reserved word? Frankly, the reasons were perhaps mostly social. Unlike some built-ins and many exceptions, None is so central to using Python that you really can't be using Python without knowing about None. So people were (like our question-asker) "horrified" when they found that assignment to None was actually allowed at all. Worse, there was the concern (whether founded or not) that the way name lookup in Python works, "evaluating" the expression None is slow, because it requires at least two dictionary lookups (all names are looked up in the globals dict before being looked up in the built-ins dict).<br />
<br />
In the end we decided that there was no downside to making None a keyword (there is no code that actually assigns to it) and it might make some code a tiny bit faster, or catch rare typos. There was still a one-time cost to the developer community (changes to the parser and documentation) but this was small enough that we din't hesitate very long.<br />
<br />
The situation for True/False is a little different. They weren't always part of the language, and many people had invented their own convention. People would define constants named true and false, True and False, or TRUE and FALSE, and use those consistently throughout their code. I don't recall which spelling was most popular, but when we introduced True and False into the language, we definitely did not want to break any packages that were defining their own True and False constants. (One concern was that those packages would have to have a way to continue to run on previous Python versions.)<br />
<br />
So, essentially our hand was forced in this case, and we had to introduce True and False as built-in constants, not as keywords. But over time, code defining its own versions of True and False (by whichever name) became more and more frowned upon, and by the time Python 3 came around, when we looked at opportunities for cleaning up the language, we found that it was logical to make True and False keywords, by analogy to None.<br />
<br />
And there you have it. It's all completely logical, once you understand the context. :-) Sorry for the long response; I hope it's been educational.<br />
<br />
<b>UPDATE:</b> I still forgot to answer whether None/True/False are literals or keywords. My answer is that they are both. They are keywords because that's how the parser recognizes them. They
are literals because that's their role in expressions and because they
stand for constant values. One could argue about whether things like
{'foo': 42} are literals; personally I'd prefer to give these some other
name, because otherwise what would you call {'foo': x+1}? The <a href="http://docs.python.org/3/reference/expressions.html#displays-for-lists-sets-and-dictionaries" target="_blank">language reference</a> calls both of these "displays".Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com16tag:blogger.com,1999:blog-8699431508730375743.post-31464445321583661502013-10-24T09:58:00.000-07:002013-10-24T09:58:02.515-07:00Origin of metaclasses in Python<div>
There was some speculation on python-ideas today on whether Python's metaclass design came from Ruby. It did not. And as long as we are speculating about the origins of language features, I feel the need to set the record straight.</div>
<div>
<br />I
was not inspired by Ruby at that point (or ever :-). Ruby was in fact
inspired by Python. Mats once told me that his inspiration was 20%
Python, 80% Perl, and that Larry Wall is his hero.<br />
</div>
<div>
</div>
<div>
I wrote about metaclasses in Python in 1998: <a href="http://www.python.org/doc/essays/metaclasses/" target="_blank">http://www.python.org/doc/<wbr></wbr>essays/metaclasses/</a>.</div>
<div>
</div>
<div>
New-style classes were just the second or third iteration of the idea.</div>
<div>
</div>
<div>
I was inspired to implement new-style classes by a very
specific book, "Putting Metaclasses to Work" by Ira Forman and Scott
Danforth (<a href="http://www.amazon.com/Putting-Metaclasses-Work-Ira-Forman/dp/0201433052" target="_blank">http://www.amazon.com/<wbr></wbr>Putting-Metaclasses-Work-Ira-<wbr></wbr>Forman/dp/0201433052</a>).<br />
</div>
<div>
But even Python's original design (in 1990, published in
1991) had the notion that 'type' was itself an object. The type pointer
in any object has always been a pointer to a special object, whose
"data" was a bunch of C function pointers implementing the behavior of
other objects, similar to a C++ vtable. The type of a type was always a
special type object, which you could call a meta-type, to be recognized
because it was its own type.<br />
</div>
I was only vaguely aware of Smalltalk at the time; I
remember being surprised by its use of metaclasses (which is quite different from that in Python or Ruby!) when I read about
them much later. Smalltalk's bytecode was a bigger influence of Python's
bytecode though. I'd read about it in a book by Adele Goldberg and
others, I believe "Smalltalk-80: The Language and its Implementation" (<a href="http://www.amazon.com/Smalltalk-80-The-Language-its-Implementation/dp/0201113716" target="_blank">http://www.amazon.com/<wbr></wbr>Smalltalk-80-The-Language-its-<wbr></wbr>Implementation/dp/0201113716</a>).Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com1tag:blogger.com,1999:blog-8699431508730375743.post-87376720533834726712013-10-24T08:44:00.000-07:002013-10-24T08:44:20.890-07:00Why Python uses 0-based indexingI was asked on Twitter why Python uses 0-based indexing, with a link to a new (fascinating) post on the subject (<a class="ot-anchor" href="http://exple.tive.org/blarg/2013/10/22/citation-needed/" rel="nofollow">http://exple.tive.org/blarg/2013/10/22/citation-needed/</a>).
I recall thinking about it a lot; ABC, one of Python's predecessors,
used 1-based indexing, while C, the other big influence, used 0-based.
My first few programming languages (Algol, Fortran, Pascal) used 1-based
or variable-based. I think that one of the issues that helped me decide
was slice notation.<br /><br />Let's first look at use cases. Probably the
most common use cases for slicing are "get the first n items" and "get
the next n items starting at i" (the first is a special case of that for
i == the first index). It would be nice if both of these could be
expressed as without awkward +1 or -1 compensations.<br /><br />Using
0-based indexing, half-open intervals, and suitable defaults (as Python
ended up having), they are beautiful: a[:n] and a[i:i+n]; the former is
long for a[0:n].<br /><br />Using 1-based indexing, if you want a[:n] to
mean the first n elements, you either have to use closed intervals or
you can use a slice notation that uses start and length as the slice
parameters. Using half-open intervals just isn't very elegant when
combined with 1-based indexing. Using closed intervals, you'd have to
write a[i:i+n-1] for the n items starting at i. So perhaps using the
slice length would be more elegant with 1-based indexing? Then you could
write a[i:n]. And this is in fact what ABC did -- it used a different
notation so you could write a@i|n.(See <a class="ot-anchor" href="http://homepages.cwi.nl/%7Esteven/abc/qr.html#EXPRESSIONS" rel="nofollow">http://homepages.cwi.nl/~steven/abc/qr.html#EXPRESSIONS</a>.)<br /><br />But
how does the index:length convention work out for other use cases? TBH
this is where my memory gets fuzzy, but I think I was swayed by the
elegance of half-open intervals. Especially the invariant that when two
slices are adjacent, the first slice's end index is the second slice's
start index is just too beautiful to ignore. For example, suppose you
split a string into three parts at indices i and j -- the parts would be
a[:i], a[i:j], and a[j:].<br /><br />So that's why Python uses 0-based indexing.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com15tag:blogger.com,1999:blog-8699431508730375743.post-33793777897276955292011-07-08T16:13:00.000-07:002011-07-08T19:22:45.003-07:00Karin Dewar, Indentation and the ColonIn a <a href="http://neopythonic.blogspot.com/2011/06/depth-and-breadth-of-python.html">recent post on my other blog</a> I mentioned a second-hand story about how Python's indentation was invented by the wife of Robert Dewar. I added that I wasn't very sure of the details, and I'm glad I did, because the truth was quite different. I received a long email from Lambert Meertens with the real story. I am going to quote it almost completely here, except for some part which he requested not to be quoted. In summary: Karin Dewar provided the inspiration for the use of the colon in ABC (and hence in Python) leading up to the indentation, not for indentation itself. Here is Lambert's email:<br /><br /><blockquote> The Dewar story is not about indentation, but about the invention of the colon.<br /><br />First about indentation in <i>B</i>. Already <i>B</i><small>0</small>, the first iteration in the <i>B</i><small>0, </small><i>B</i><small>1, </small><i>B</i><small>2,</small> ... sequence of designs leading to ABC, had non-optional indentation for grouping, supplemented by enclosing the group between <tt>BEGIN</tt> and <tt>END</tt> delimiters. This can be seen in [GM76], section 4.1 (<i>Layout</i>). The indentation was supposed to be added, like pretty printing, by a dedicated <i>B</i> editor, and the user had no control over this; they were not supposed to be able to turn this off or otherwise modify the indentation regime.<br /><br />Given the mandatory indentation, separate <tt>BEGIN</tt> and <tt>END</tt> delimiters are of course superfluous; in <small> </small><i>B</i><small>1</small> we had no <tt>BEGIN</tt>, but only <tt>END IF</tt>, <tt>END FOR</tt>, and so on, and then the latter delimiters were also dropped in <small> </small><i>B</i><small>2</small><small>,</small> leaving pure indentation as the sole indicator of grouping. See [ME81], Section 4 (STATEMENT SYNTAX).<br /><br />The origin of indentation in ABC is thus simply the desire to have the program text look neat and be suggestive of the meaning, codifying what was already common practice but not enforced. The decision to remove the noise of <tt>BEGIN</tt> ... <tt>END</tt> may have been influenced by [PL75], which actually advocated using pure indentation for grouping. Since occam came later (1983), the feature can't have been copied from that language. Same for Miranda (1985). As far as I am aware, <i>B</i> was the first actually published (and implemented) language to use indentation for grouping.<br /><br />Now the Dewar story, which is how I got the idea of the colon, as I wrote it down in a memoir of the ABC design rationale: </blockquote><br />And here I will paraphrase, at Lambert's request.<br /><br />In 1978, in a design session in a mansion in Jabłonna (Poland), Robert Dewar, Peter King, Jack Schwartz and Lambert were comparing various alternative proposed syntaxes for B, by comparing (buggy) bubble sort implementations written down in each alternative. Since they couldn't agree, Robert Dewar's wife was called from her room and asked for her opinion, like a modern-day Paris asked to compare the beauty of Hera, Athena, and Aphrodite. But after the first version was explained to her, she remarked: "You mean, in the line where it says: 'FOR i ... ', that it has to be done for the lines that follow; not just for that line?!" And here the scientists realized that the misunderstanding would have been avoided if there had been a colon at the end of that line.<br /><br />Lambert also included the following useful references:<br /><br /><blockquote> [PL75] P. J. Plauger. <a href="http://portal.acm.org/citation.cfm?id=800181.810322" target="_blank">Signal and noise in programming language</a>. In J. D. White, editor, <i>Proc. ACM Annual Conference 1975</i>, page 216. ACM, 1975.<br /><br />[GM76] Leo Geurts and Lambert Meertens. <a href="http://www.kestrel.edu/home/people/meertens/publications/papers/Designing_a_beginners_programming_language.pdf" target="_blank">Designing a beginners' programming language</a>. In S.A. Schuman, editor, <em>New Directions in Algorithmic Languages 1975</em>, pages 1–18. IRIA, Rocquencourt, 1976.<br /><br />[ME81] Lambert Meertens. <a href="http://www.kestrel.edu/home/people/meertens/publications/papers/Issues_in_the_design_of_a_beginners_programming_language.pdf" target="_blank">Issues in the design of a beginners' programming language</a>. In J.W. de Bakker and J.C. van Vliet, editors, <em>Algorithmic Languages</em>, pages 167–184. North-Holland Publishing Company, Amsterdam, 1981.</blockquote>Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com7tag:blogger.com,1999:blog-8699431508730375743.post-70232943339893599162010-08-24T09:49:00.000-07:002014-10-18T19:23:47.924-07:00Why Python's Integer Division Floors<div>
I was asked (again) today to explain why integer division in Python returns the floor of the result instead of truncating towards zero like C.</div>
<div>
<br /></div>
<div>
For positive numbers, there's no surprise:</div>
<div>
<br /></div>
<div>
>>> 5//2</div>
<div>
2</div>
<div>
<br /></div>
<div>
But if one of the operands is negative, the result is floored, i.e., rounded away from zero (towards negative infinity):</div>
<div>
<br /></div>
<div>
>>> -5//2</div>
<div>
-3</div>
<div>
>>> 5//-2</div>
<div>
-3</div>
<div>
<br /></div>
<div>
This disturbs some people, but there is a good mathematical reason. The integer division operation (//) and its sibling, the modulo operation (%), go together and satisfy a nice mathematical relationship (all variables are integers):</div>
<div>
<br /></div>
<div>
a/b = q with remainder r</div>
<div>
<br /></div>
<div>
such that</div>
<div>
<br /></div>
<div>
b*q + r = a and 0 <= r < b<br />
<div>
<br /></div>
<div>
(assuming a and b are >= 0).</div>
<div>
<br /></div>
<div>
If you want the relationship to extend for negative a (keeping b positive), you have two choices: if you truncate q towards zero, r will become negative, so that the invariant changes to 0 <= abs(r) < otherwise, you can floor q towards negative infinity, and the invariant remains 0 <= r < b.<span style="font-weight: bold;"> [update: fixed this para]</span><br />
<div>
<br /></div>
<div>
In mathematical number theory, mathematicians always prefer the latter choice (see e.g. <a href="http://en.wikipedia.org/wiki/Modulo_operation">Wikipedia</a>). For Python, I made the same choice because there are some interesting applications of the modulo operation where the sign of a is uninteresting. Consider taking a POSIX timestamp (seconds since the start of 1970) and turning it into the time of day. Since there are 24*3600 = 86400 seconds in a day, this calculation is simply t % 86400. But if we were to express times before 1970 using negative numbers, the "truncate towards zero" rule would give a meaningless result! Using the floor rule it all works out fine.</div>
<div>
<br /></div>
<div>
Other applications I've thought of are computations of pixel positions in computer graphics. I'm sure there are more.</div>
<div>
<br /></div>
<div>
For negative b, by the way, everything just flips, and the invariant becomes:</div>
<div>
<br /></div>
<div>
0 >= r > b.</div>
<div>
<br /></div>
<div>
So why doesn't C do it this way? Probably the hardware didn't do this at the time C was designed. And the hardware probably didn't do it this way because in the oldest hardware, negative numbers were represented as "sign + magnitude" rather than the two's complement representation used these days (at least for integers). My first computer was a Control Data mainframe and it used one's complement for integers as well as floats. A pattern of 60 ones meant negative zero!</div>
<div>
<br /></div>
<div>
Tim Peters, who knows where all Python's floating point skeletons are buried, has expressed some worry about my desire to extend these rules to floating point modulo. He's probably right; the truncate-towards-negative-infinity rule can cause precision loss for x%1.0 when x is a very small negative number. But that's not enough for me to break integer modulo, and // is tightly coupled to that.</div>
<div>
<br /></div>
<div>
PS. Note that I am using // instead of / -- this is Python 3 syntax, and also allowed in Python 2 to emphasize that you know you are invoking integer division. The / operator in Python 2 is ambiguous, since it returns a different result for two integer operands than for an int and a float or two floats. But that's a totally separate story; see <a href="http://www.python.org/dev/peps/pep-0238/">PEP 238</a>.</div>
</div>
</div>
Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com18tag:blogger.com,1999:blog-8699431508730375743.post-50964272497182066142010-06-29T08:39:00.000-07:002010-07-15T06:45:31.090-07:00From List Comprehensions to Generator ExpressionsList comprehensions were added in Python 2.0. This feature originated as a set of patches by Greg Ewing with contributions by Skip Montanaro and Thomas Wouters. (IIRC Tim Peters also strongly endorsed the idea.) Essentially, they are a Pythonic interpretation of a well-known notation for sets used by mathematicians. For example, it is commonly understood that this:<br /><blockquote>{x | x > 10}</blockquote><br />refers to the set of all x such that x > 10. In math, this form implies a universal set that is understood by the reader (for example, the set of all reals, or the set of all integers, depending on the context). In Python, there is no concept of a universal set, and in Python 2.0, there were no sets. (Sets are an interesting story, of which more in a future blog post.)<br /><br />This and other considerations led to the following notation in Python:<br /><blockquote>[f(x) for x in S if P(x)]</blockquote><br />This produces a list containing the values of the sequence S selected by the predicate P and mapped by the function f. The if-clause is optional, and multiple for-clauses may be present, each with their own optional if-clause, to represent nested loops (the latter feature is rarely used though, since it typically maps a multi-dimensional entity to a one-dimensional list).<br /><br />List comprehensions provide an alternative to using the built-in map() and filter() functions. map(f, S) is equivalent to [f(x) for x in S] while filter(P, S) is equivalent to [x for x in S if P(x)]. One would think that list comprehensions have little to recommend themselves over the seemingly more compact map() and filter() notations. However, the picture changes if one looks at a more realistic example. Suppose we want to add 1 to the elements of a list, producing a new list. The list comprehension solution is [x+1 for x in S]. The solution using map() is map(lambda x: x+1, S). The part “lambda x: x+1” is Python’s notation for an anonymous function defined in-line.<br /><br />It has been argued that the real problem here is that Python’s lambda notation is too verbose, and that a more concise notation for anonymous functions would make map() more attractive. Personally, I disagree—I find the list comprehension notation much easier to read than the functional notation, especially as the complexity of the expression to be mapped increases. In addition, the list comprehension executes much faster than the solution using map and lambda. This is because calling a lambda function creates a new stack frame while the expression in the list comprehension is evaluated without creating a new stack frame.<br /><br />Given the success of list comprehensions, and enabled by the invention of generators (of which more in a future episode), Python 2.4 added a similar notation that represents a sequence of results without turning it into a concrete list. The new feature is called a “generator expression”. For example:<br /><blockquote>sum(x**2 for x in range(1, 11))</blockquote><br />This calls the built-in function sum() with as its argument a generator expression that yields the squares of the numbers from 1 through 10 inclusive. The sum() function adds up the values in its argument resulting in an answer of 385. The advantage over sum([x**2 for x in range(1, 11)]) should be obvious. The latter creates a list containing all the squares, which is then iterated over once before it is thrown away. For large collections these savings in memory usage are an important consideration.<br /><br />I should add that the differences between list comprehensions and generator expressions are fairly subtle. For example, in Python 2, this is a valid list comprehension:<br /><blockquote>[x**2 for x in 1, 2, 3]</blockquote><br />However this is not a valid generator expression:<br /><blockquote>(x**2 for x in 1, 2, 3)</blockquote><br />We can fix it by adding parentheses around the "1, 2, 3" part:<br /><blockquote>(x**2 for x in (1, 2, 3))</blockquote><br />In Python 3, you also have to use these parentheses for the list comprehension:<br /><blockquote>[x**2 for x in (1, 2, 3)]</blockquote><br />However, in a "regular" or "explicit" for-loop, you can still omit them:<br /><blockquote>for x in 1, 2, 3: print(x**2)</blockquote><br />Why the differences, and why the changes to a more restrictive list comprehension in Python 3? The factors affecting the design were backwards compatibility, avoiding ambiguity, the desire for equivalence, and evolution of the language. Originally, Python (before it even had a version :-) only had the explicit for-loop. There is no ambiguity here for the part that comes after 'in': it is always followed by a colon. Therefore, I figured that if you wanted to loop over a bunch of known values, you shouldn't be bothered with having to put parentheses around them. This also reminded me of Algol-60, where you can write:<br /><blockquote><span style="font-weight: bold;">for</span> i := 1, 2, 3 <span style="font-weight: bold;">do</span> <span style="font-style: italic;">Statement</span></blockquote><br />except that in Algol-60 you can also replace each expression with step-until clause, like this:<br /><blockquote><span style="font-weight: bold;">for</span> i := 1 <span style="font-weight: bold;">step</span> 1 <span style="font-weight: bold;">until</span> 10, 12 <span style="font-weight: bold;">step</span> 2 <span style="font-weight: bold;">until</span> 50, 55 <span style="font-weight: bold;">step</span> 5 <span style="font-weight: bold;">until</span> 100 <span style="font-weight: bold;">do</span> <span style="font-style: italic;">Statement</span></blockquote><br />(In retrospect it would have been cool if Python for-loops had the ability to iterate over multiple sequences as well. Alas...)<br /><br />When we added list comprehensions in Python 2.0, the same reasoning applied: the sequence expression could only be followed by a close bracket ']' or by a 'for' or 'if' keyword. And it was good.<br /><br />But when we added generator expressions in Python 2.4, we ran into a problem with ambiguity: the parentheses around a generator expression are not technically part of the generator expression syntax. For example, in this example:<br /><blockquote>sum(x**2 for x in range(10))</blockquote><br />the outer parentheses are part of the call to sum(), and a "bare" generator expression occurs as the first argument. So in theory there would be two interpretations for something like this:<br /><blockquote>sum(x**2 for x in a, b)</blockquote><br />This could either be intended as:<br /><blockquote>sum(x**2 for x in (a, b))</blockquote><br />or as:<br /><blockquote>sum((x**2 for x in a), b)</blockquote><br />After a lot of hemming and hawing (IIRC) we decided not to guess in this case, and the generator comprehension was required to have a single expression (evaluating to an iterable, of course) after its 'in' keyword. But at the time we didn't want to break existing code using the (already hugely popular) list comprehensions.<br /><br />Then when we were designing Python 3, we decided that we wanted the list comprehension:<br /><blockquote>[f(x) for x in S if P(x)]</blockquote><br />to be fully equivalent to the following expansion using the built-in list() function applied to a generator expression:<br /><blockquote>list(f(x) for x in S if P(x))</blockquote><br />Thus we decided to use the slightly more restrictive syntax of generator expressions for list comprehensions as well.<br /><br />We also made another change in Python 3, to improve equivalence between list comprehensions and generator expressions. In Python 2, the list comprehension "leaks" the loop control variable into the surrounding scope:<br /><blockquote>x = 'before'<br />a = [x for x in 1, 2, 3]<br />print x # this prints '3', not 'before'</blockquote><br />This was an artifact of the original implementation of list comprehensions; it was one of Python's "dirty little secrets" for years. It started out as an intentional compromise to make list comprehensions blindingly fast, and while it was not a common pitfall for beginners, it definitely stung people occasionally. For generator expressions we could not do this. Generator expressions are implemented using generators, whose execution requires a separate execution frame. Thus, generator expressions (especially if they iterate over a short sequence) were less efficient than list comprehensions.<br /><br />However, in Python 3, we decided to fix the "dirty little secret" of list comprehensions by using the same implementation strategy as for generator expressions. Thus, in Python 3, the above example (after modification to use print(x) :-) will print 'before', proving that the 'x' in the list comprehension temporarily shadows but does not override the 'x' in the surrounding scope.<br /><br />And before you start worrying about list comprehensions becoming slow in Python 3: thanks to the enormous implementation effort that went into Python 3 to speed things up in general, both list comprehensions and generator expressions in Python 3 are actually <span style="font-style: italic;">faster</span> than they were in Python 2! (And there is no longer a speed difference between the two.)<br /><br /><span style="font-weight: bold;">UPDATE:</span> Of course, I forgot to mention that Python 3 also supports set comprehensions and dictionary comprehensions. These are straightforward extensions of the list comprehension idea.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com10tag:blogger.com,1999:blog-8699431508730375743.post-90805352817987223952010-06-23T10:41:00.001-07:002010-07-05T21:41:43.984-07:00Method Resolution OrderIn languages that use multiple inheritance, the order in which base classes are searched when looking for a method is often called the Method Resolution Order, or MRO. (In Python this also applies to other attributes.) For languages that support single inheritance only, the MRO is uninteresting; but when multiple inheritance comes into play, the choice of an MRO algorithm can be remarkably subtle. Python has known at least three different MRO algorithms: classic, Python 2.2 new-style, and Python 2.3 new-style (a.k.a. C3). Only the latter survives in Python 3.<br /><br />Classic classes used a simple MRO scheme: when looking up a method, base classes were searched using a simple depth-first left-to-right scheme. The first matching object found during this search would be returned. For example, consider these classes:<br /><blockquote><pre>class A:<br /> def save(self): pass<br /><br />class B(A): pass<br /><br />class C:<br /> def save(self): pass<br /><br />class D(B, C): pass</pre></blockquote>If we created an instance x of class D, the classic method resolution order would order the classes as D, B, A, C. Thus, a search for the method x.save() would produce A.save() (and not C.save()). This scheme works fine for simple cases, but has problems that become apparent when one considers more complicated uses of multiple inheritance. One problem concerns method lookup under "diamond inheritance." For example:<br /><blockquote><pre>class A:<br /> def save(self): pass<br /><br />class B(A): pass<br /><br />class C(A):<br /> def save(self): pass<br /><br />class D(B, C): pass</pre></blockquote>Here, class D inherits from B and C, both of which inherit from class A. Using the classic MRO, methods would be found by searching the classes in the order D, B, A, C, A. Thus, a reference to x.save() will call A.save() as before. However, this is unlikely what you want in this case! Since both B and C inherit from A, one can argue that the redefined method C.save() is actually the method that you want to call, since it can be viewed as being "more specialized" than the method in A (in fact, it probably calls A.save() anyways). For instance, if the save() method is being used to save the state of an object, not calling C.save() would break the program since the state of C would be ignored.<br /><br /> Although this kind of multiple inheritance was rare in existing code, new-style classes would make it commonplace. This is because all new-style classes were defined by inheriting from a base class object. Thus, any use of multiple inheritance in new-style classes would always create the diamond relationship described above. For example:<br /><blockquote><pre>class B(object): pass<br /><br />class C(object):<br /> def __setattr__(self, name, value): pass<br /><br />class D(B, C): pass</pre></blockquote>Moreover, since object defined a number of methods that are sometimes extended by subtypes (e.g., __setattr__()), the resolution order becomes critical. For example, in the above code, the method C.__setattr__ should apply to instances of class D.<br /><br />To fix the method resolution order for new-style classes in Python 2.2, I adopted a scheme where the MRO would be pre-computed when a class was defined and stored as an attribute of each class object. The computation of the MRO was officially documented as using a depth-first left-to-right traversal of the classes as before. If any class was duplicated in this search, all but the last occurrence would be deleted from the MRO list. So, for our earlier example, the search order would be D, B, C, A (as opposed to D, B, A, C, A with classic classes). <br /><br />In reality, the computation of the MRO was more complex than this. I discovered a few cases where this new MRO algorithm didn't seem to work. Thus, there was a special case to deal with a situation when two bases classes occurred in a different order in the inheritance list of two different derived classes, and both of those classes are inherited by yet another class. For example:<br /><blockquote><pre>class A(object): pass<br />class B(object): pass<br />class X(A, B): pass<br />class Y(B, A): pass<br />class Z(X, Y): pass</pre></blockquote>Using the tentative new MRO algorithm, the MRO for these classes would be Z, X, Y, B, A, object. (Here 'object' is the universal base class.) However, I didn't like the fact that B and A were in reversed order. Thus, the real MRO would interchange their order to produce Z, X, Y, A, B, object. Intuitively, this algorithm tried to preserve the order of classes for bases that appeared first in the search process. For instance, on class Z, the base class X would be checked first because it was first in the inheritance list. Since X inherited from A and B, the MRO algorithm would try to preserve that ordering. This is what I implemented for Python 2.2, but I documented the earlier algorithm (naïvely thinking it didn't matter much).<br /><br />However, shortly after the introduction of new-style classes in Python 2.2, Samuele Pedroni discovered an inconsistency between the documented MRO algorithm and the results that were actually observed in real-code. Moreover, inconsistencies were occurring even in code that did not fall under the special case observed above. After much discussion, it was decided that the MRO adopted for Python 2.2 was broken and that Python should adopt the C3 Linearization algorithm described in the paper "A Monotonic Superclass Linearization for Dylan" (K. Barrett, et al, presented at OOPSLA'96).<br /><br />Essentially, the main problem in the Python 2.2 MRO algorithm concerned the issue of monotonicity. In a complex inheritance hierarchy, each inheritance relationship defines a simple set of rules concerning the order in which classes should be checked. Specifically, if a class A inherits from class B, then the MRO should obviously check A before B. Likewise, if a class B uses multiple inheritance to inherit from C and D, then B should be checked before C and C should be checked before D.<br /><br />Within a complex inheritance hierarchy, you want to be able to satisfy all of these possible rules in a way that is monotonic. That is, if you have already determined that class A should be checked before class B, then you should never encounter a situation that requires class B to be checked before class A (otherwise, the result is undefined and the inheritance hierarchy should be rejected). This is where the original MRO got it wrong and where the C3 algorithm comes into play. Basically, the idea behind C3 is that if you write down all of the ordering rules imposed by inheritance relationships in a complex class hierarchy, the algorithm will determine a monotonic ordering of the classes that satisfies all of them. If such an ordering can not be determined, the algorithm will fail.<br /><br />Thus, in Python 2.3, we abandoned my home-grown 2.2 MRO algorithm in favor of the academically vetted C3 algorithm. One outcome of this is that Python will now reject any inheritance hierarchy that has an inconsistent ordering of base classes. For instance, in the previous example, there is an ordering conflict between class X and Y. For class X, there is a rule that says class A should be checked before class B. However, for class Y, the rule says that class B should be checked before A. In isolation, this discrepancy is fine, but if X and Y are ever combined together in the same inheritance hierarchy for another class (such as in the definition of class Z), that class will be rejected by the C3 algorithm. This, of course, matches the Zen of Python's "errors should never pass silently" rule.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com10tag:blogger.com,1999:blog-8699431508730375743.post-34968105141988119362010-06-21T11:31:00.000-07:002010-06-23T11:21:00.353-07:00import antigravityThe antigravity module, referencing the <a href="http://xkcd.com/353/">XKCD comic mentioning Python</a>, was added to Python 3 by Skip Montanaro. You can read more about it here, one of the first spottings that I know of: <a href="http://sciyoshi.com/blog/2008/dec/30/import-antigravity/">http://sciyoshi.com/blog/2008/dec/30/import-antigravity/</a>).<br /><br />But it really originated in Google App Engine! It was a last-minute addition when we launched App Engine on April 7, 2008. A few weeks before launch, when most code was already frozen, the App Engine team at Google decided we wanted an easter egg. After a great many suggestions, some too complex, some too obscure, some too risky, we chose the "antigravity" module. The App Engine version is a little more elaborate than the Python 3 version: it defines a fly() function while can randomly do one of two things: with a probability of 10%, it redirects to the XKCD comic; otherwise, it simply renders the text of the comic in HTML (with a link to the comic on the last line). To invoke it in your App Engine app, you'd have to write a little main program, like this:<blockquote><pre>import antigravity<br /><br />def main():<br /> antigravity.fly()<br /><br />if __name__ == '__main__':<br /> main()</pre></blockquote><br /><br /><b>Update:</b> The Python 3 stdlib version has an easter egg inside the easter egg, if you inspect the source code: it defines a function that purports to implement the <a href="http://xkcd.com/426/">XKCD geohashing algorithm</a>.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com2tag:blogger.com,1999:blog-8699431508730375743.post-80597798663697418652010-06-21T11:26:00.000-07:002010-06-21T11:28:21.683-07:00import this and The Zen of PythonBarry Warsaw posted an interesting blog that tells an obscure part of Python history (the kind I like to keep alive): <a href="http://www.wefearchange.org/2010/06/import-this-and-zen-of-python.html">http://www.wefearchange.org/2010/06/import-this-and-zen-of-python.html</a>Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com1tag:blogger.com,1999:blog-8699431508730375743.post-23476934136018083512010-06-21T11:18:00.000-07:002010-06-23T14:21:32.584-07:00The Inside Story on New-Style Classes[Warning, this post is long and gets very technical.]<br /><br />On the surface, new-style classes appear very similar to the original class implementation. However, new-style classes also introduced a number of new concepts:<br /><ul><li>low-level constructors named __new__()</li><li>descriptors, a generalized way to customize attribute access</li><li>static methods and class methods</li><li>properties (computed attributes)</li><li>decorators (introduced in Python 2.4)<br /></li><li>slots</li><li>a new Method Resolution Order (MRO)<br /></li></ul> In the next few sections, I will try to shine some light on these concepts.<br /><br /><span style="font-weight: bold;">Low-level constructors and __new__()</span><br /><br />Traditionally, classes defined an __init__() method which defined how new instances are initialized after their creation. However, in some cases, the author of a class may want to customize how instances are created—for example, if an object was being restored from a persistent database. Old-style classes never really provided a hook for customizing the creation of objects although there were library modules allowed certain kinds of objects to be created in non-standard ways (e.g., the "new" module).<br /><br />New-style classes introduced a new class method __new__() that lets the class author customize how new class instances are created. By overriding __new__() a class author can implement patterns like the Singleton Pattern, return a previously created instance (e.g., from a free list), or to return an instance of a different class (e.g., a subclass). However, the use of __new__ has other important applications. For example, in the pickle module, __new__ is used to create instances when unserializing objects. In this case, instances are created, but the __init__ method is not invoked.<br /><br />Another use of __new__ is to help with the subclassing of immutable types. By the nature of their immutability, these kinds of objects can not be initialized through a standard __init__() method. Instead, any kind of special initialization must be performed as the object is created; for instance, if the class wanted to modify the value being stored in the immutable object, the __new__ method can do this by passing the modified value to the base class __new__ method.<br /><br /><span style="font-weight: bold;">Descriptors</span><br /><br />Descriptors are a generalization of the concept of bound methods, which was central to the implementation of classic classes. In classic classes, when an instance attribute is not found in the instance dictionary, the search continues with the class dictionary, then the dictionaries of its base classes, and so on recursively. When the attribute is found in a class dictionary (as opposed to in the instance dictionary), the interpreter checks if the object found is a Python function object. If so, the returned value is not the object found, but a wrapper object that acts as a currying function. When the wrapper is called, it calls the original function object after inserting the instance in front of the argument list.<br /><br />For example, consider an instance x of a class C. Now, suppose that one makes a method call x.f(0). This operation looks up the attribute named "f" on x and calls it with an argument of 0. If "f" corresponds to a method defined in the class, the attribute request returns a wrapper function that behaves approximately like the function in this Python pseudocode:<br /><blockquote><pre>def bound_f(arg):<br /> return f(x, arg)</pre></blockquote>When the wrapper is called with an argument of 0, it calls "f" with two arguments: x and 0. This is the fundamental mechanism by which methods in classes obtain their "self" argument.<br /><br />Another way to access the function object f (without wrapping it) is to ask the class C for an attribute named “f”. This kind of search does not return a wrapper but simply returns the function f. In other words, x.f(0) is equivalent to C.f(x, 0). This is a pretty fundamental equivalence in Python.<br /><br />For classic classes, if the attribute search finds any other kind of object, no wrapper is created and the value found in the class dictionary is returned unchanged. This makes it possible to use class attributes as “default” values for instance variables. For example, in the above example, if class C has an attribute named “a” whose value is 1, and there is no key “a” in x’s instance dictionary, then x.a equals 1. Assignment to x.a will create an key “a” in x’s instance dictionary whose value will shadow the class attribute (by virtue of the attribute search order). Deleting x.a will reveal the shadowed value (1) again.<br /><br />Unfortunately, some Python developers were discovering the limitation of this scheme. One limitation was that it was prevented the creation of “hybrid” classes that had some methods implemented in Python and others in C, because only Python functions were being wrapped in such a way as to provide the method with access to the instance, and this behavior was hard-coded in the language. There was also no obvious way to define different kinds of methods such as a static member functions familiar to C++ and Java programmers.<br /><br />To address this issue, Python 2.2 introduced a straightforward generalization of the above wrapping behavior. Instead of hard-coding the behavior that Python function objects are wrapped and other objects aren’t, the wrapping is now left up to the object found by the attribute search (the function f in the above example). If the object found by an attribute search happens to have a special method named __get__, it is considered to be a "descriptor" object. The __get__ method is then called and whatever is returned is used to produce the result of the attribute search. If the object has no __get__ method, it is returned unchanged. To obtain the original behavior (wrapping function objects) without special-casing function objects in the instance attribute lookup code, function objects now have a __get__ method that returns a wrapper as before. However, users are free to define other classes with methods named __get__, and their instances, when found in a class dictionary during an instance attribute lookup, can also wrap themselves in any way they like.<br /><br />In addition to generalizing the concept of attribute lookup, it also made sense to extend this idea for the operations of setting or deleting an attribute. Thus, a similar scheme is used for assignment operations such as x.a = 1 or del x.a. In these cases, if the attribute "a" is found in the instance's class dictionary (not in the instance dictionary), the object stored in the class dictionary is checked to see if it has a __set__ and __delete__ special method respectively. (Remember that __del__ has a completely different meaning already.) Thus, by redefining these methods, a descriptor object can have complete control over what it means to get, set, and delete an attribute. However, it's important emphasize that this customization only applies when a descriptor instance appears in a class dictionary—not the instance dictionary of an object.<br /><br /><span style="font-weight: bold;">staticmethod, classmethod, and property</span><br /><br />Python 2.2 added three predefined classes: classmethod, staticmethod, and property, that utilized the new descriptor machinery. classmethod and staticmethod were simply wrappers for function objects, implementing different __get__ methods to return different kinds of wrappers for calling the underlying function. For instance, the staticmethod wrapper calls the function without modifying the argument list at all. The classmethod wrapper calls the function with the instance's class object set as the first argument instead of the instance itself. Both can be called via an instance or via the class and the arguments will be the same.<br /><br />The property class is a wrapper that turned a pair of methods for getting and setting a value into an "attribute." For example, if you have a class like this,<br /><blockquote><pre>class C(object):<br /> def set_x(self, value):<br /> self.__x = value<br /> def get_x(self):<br /> return self.__x</pre></blockquote>a property wrapper could be used to make an attribute "x" that when accessed, would implicitly call the get_x and set_x methods.<br /><br />When first introduced, there was no special syntax for using the classmethod, staticmethod, and property descriptors. At the time, it was deemed too controversial to simultaneously introduce a major new feature along with new syntax (which always leads to a heated debate). Thus, to use these features, you would define your class and methods normally, but add extra statements that would "wrap" the methods. For example:<br /><blockquote><pre>class C:<br /> def foo(cls, arg):<br /> ...<br /> foo = classmethod(foo)<br /> def bar(arg):<br /> ...<br /> bar = staticmethod(bar)</pre></blockquote>For properties, a similar scheme was used:<br /><blockquote><pre>class C:<br /> def set_x(self, value):<br /> self.__x = value<br /> def get_x(self):<br /> return self.__x<br /> x = property(get_x, set_x)<br /></pre></blockquote><span style="font-weight: bold;">Decorators</span><br /><br />A downside of this approach is that the reader of a class had to read all the way till the end of a method declaration before finding out whether it was a class or static method (or some user-defined variation). In Python 2.4, new syntax was finally introduced, allowing one to write the following instead:<br /><blockquote><pre>class C:<br /> @classmethod<br /> def foo(cls, arg):<br /> ...<br /> @staticmethod<br /> def bar(arg):<br /> ...</pre></blockquote>The construct @expression, on a line by itself before a function declaration, is called a decorator. (Not to be confused with descriptor, which refers to a wrapper implementing __get__; see above.) The particular choice of decorator syntax (derived from Java's annotations) was debated endlessly before it was decided by “BDFL pronouncement”. (David Beazley wrote a piece about the history of the term BDFL that I'll publish separately.)<br /><br />The decorator feature has become one of the more successful language features, and the use of custom decorators has exceeded my widest expectations. Especially web frameworks have found lots of uses for them. Based on this success, in Python 2.6, the decorator syntax was extended from function definitions to include class definitions.<br /><br /><span style="font-weight: bold;">Slots</span><br /><br />Another enhancement made possible with descriptors was the introduction of the __slots__ attribute on classes. For example, a class could be defined like this:<br /><blockquote><pre>class C:<br /> __slots__ = ['x','y']<br /> ...</pre></blockquote>The presence of __slots__ does several things. First, it restricts the valid set of attribute names on an object to exactly those names listed. Second, since the attributes are now fixed, it is no longer necessary to store attributes in an instance dictionary, so the __dict__ attribute is removed (unless a base class already has it; it can also be added back by a subclass that doesn't use __slots__). Instead, the attributes can be stored in predetermined locations within an array. Thus, every slot attribute is actually a descriptor object that knows how to set/get each attribute using an array index. Underneath the covers, the implementation of this feature is done entirely in C and is highly efficient.<br /><br />Some people mistakenly assume that the intended purpose of __slots__ is to increase code safety (by restricting the attribute names). In reality, my ultimate goal was performance. Not only was __slots__ an interesting application of descriptors, I feared that all of the changes in the class system were going to have a negative impact on performance. In particular, in order to make data descriptors work properly, any manipulation of an object's attributes first involved a check of the class dictionary to see if that attribute was, in fact, a data descriptor. If so, the descriptor was used to handle the attribute access instead of manually manipulating the instance dictionary as is normally the case. However, this extra check also meant that an extra lookup would be performed prior to inspecting the dictionary of each instance. Thus the use of __slots__ was a way to optimize the lookup of data attributes—a fallback, if you will, in case people were disappointed with the performance impact of the new class system. This turned out unnecessary, but by that time it was of course too late to remove __slots__. Of course, used properly, slots really can increase performance, especially by reducing memory footprint when many small objects are created.<br /><br />I'll leave the history of Python's Method Resolution Order (MRO) to the next post.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com9tag:blogger.com,1999:blog-8699431508730375743.post-52413519185060864142010-06-21T11:07:00.000-07:002010-08-20T18:49:34.198-07:00New-style Classes[After a long hiatus, this blog series is back! I will continue where I left off last year. I'll try to keep the frequency up.]<br /><br />Earlier, I described how the addition of classes to Python was essentially an afterthought. The implementation chosen was definitely an example of Python's "cut corners" philosophy. However, as Python evolved, various problems with the class implementation became a popular topic of griping from expert Python users.<br /><br />One problem with the class implementation was that there was no way to subclass built-in types. For example, lists, dictionaries, strings, and other objects were somehow "special" and could not be specialized via subclassing. This limitation seemed rather odd for a language that claimed to be "object oriented."<br /><br />Another problem was that whole type system just seemed to be "wrong" with user defined classes. For example, if you created two objects a and b, statements such as type(a) == type(b) would evaluate as True even if a and b were instances of completely unrelated classes. Needless to say, developers who were familiar with languages such as C++ and Java found this be rather odd since in those languages, classes were tightly integrated with the underlying type system.<br /><br />In Python 2.2, I finally took the time to reimplement classes and "do it right." This change was, by far, the most ambitious rewrite of a major Python subsystem to date and one could certainly accuse me of a certain amount of "second-system syndrome" in this effort. Not only did I address the immediate problem of allowing built-in types to be subclassed, I also added support for true metaclasses, attempted to fix the naïve method resolution order for multiple inheritance, and added a variety of other features. A major influence on this work was the book "Putting Metaclasses to Work" by Ira Forman and Scott Danforth, which provided me with a specific notion of what a metaclass is, different from a similar concept in Smalltalk.<br /><br />An interesting aspect of the class rewrite was that new-style classes were introduced as a new language feature, not as a strict replacement for old-style classes. In fact, for backwards compatibility, the old class implementation remains the default class creation protocol in Python 2. To create a new-style class, you simply have to subclass an existing new-style class such as object (which is the root for the new-style class hierarchy). For example:<br /><blockquote><pre>class A(object):<br /> statements<br /> ...</pre></blockquote>The change to new-style classes has been a major success. The new metaclasses have become popular amongst framework writers and explaining classes has actually become easier since there were fewer exceptions. The fact that backwards compatibility was maintained meant that old code has continued to work as new-style classes have evolved. Finally, although the old-style classes will eventually be removed from the languages, users are getting used to writing "class MyClass(object)" to declare a class, which isn't so bad.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com3tag:blogger.com,1999:blog-8699431508730375743.post-83751608780033240332009-04-24T09:14:00.000-07:002009-04-24T09:15:24.411-07:00Metaclasses and Extension Classes (a.k.a. “The Killer Joke”)In Python’s original implementation, classes were first class objects that could be manipulated just like any other object. However, the process of creating a class object was something that was set in stone. Specifically, when you defined a class such as this<br /><blockquote><pre>class ClassName(BaseClass, ...):<br /> ...method definitions... </pre></blockquote>The body of the class would be executed in its own local dictionary. The name of the class, a tuple of base classes, and this local dictionary would then be passed to an internal class creation function that was responsible for creating the class object. Since all of this machinery was hidden away behind the scenes, it was an implementation detail that users didn’t need to worry about.<br /><br />Don Beaudry was the first to point out that this was a missed opportunity for expert users. Specifically, if classes were simply special kinds of objects, why couldn’t you create new kinds of classes that could be customized to behave in different ways? He then suggested a very slight modification to the interpreter that would allow new kinds of class objects to be created by C code extension modules. This modification, first introduced in 1995, has long been known as the “Don Beaudry hook” or “Don Beaudry hack”, where the ambiguity about the name was an intentional joke. Jim Fulton later generalized the modification where it remained a part of the language (albeit under-documented) until it was replaced by true support for metaclasses through the introduction of new-style classes in Python 2.2 (see below).<br /><br />The basic idea behind the Don Beaudry hook is that expert users would be able to create custom class objects if there was some way to supply a user-supplied function in the final step of class creation. Specifically, if the class name, base classes, and local dictionary could be passed to a different construction function, then that function could do whatever it wanted with the information to create a class object. The only catch was that I didn't want to make any changes to the class syntax which had already been well-established.<br /><br />To do this, the hook required you to create a new type object in C that was callable. Then, when an instance of such a callable type was used as a base class in a class statement, the class creation code would magically call that type object instead of creating a standard class object. The behavior of classes created this way (and their instances) was completely up to the extension module providing the callable type object.<br /><br />To modern Python users it may sound strange that this was considered such a hack. But at the time, type objects were not callable -- e.g. 'int' was not a built-in type but a built-in function that returned an instance of the int object, and the int type was neither easily accessible nor callable. User-defined classes were of course callable, but this was originally special-cased by the CALL instruction, as these were implemented in a completely different way than built-in types. Don Beaudry is eventually responsible for planting the insight in my head that led first to metaclasses and later to new-style classes and the eventual death of classic classes.<br /><br />Originally, Don Beaudry’s own set of Python extensions named MESS was the only user of this feature. However, by the end of 1996, Jim Fulton had developed a very popular third-party package called Extension Classes, which used the Don Beaudry hook. The Extension Classes package eventually became unnecessary after Python 2.2 introduced metaclasses as a standard part of the object machinery.<br /><br />In Python 1.5, I removed the requirement to write a C extension in order to use the Don Beaudry hook. In addition to check for a callable base class type, the class creation code now also checked for an attribute named “__class__” on the base class, and would call this if present. I wrote an essay about this feature that was the first introduction to the idea of metaclasses for many Python users. Due to the head-exploding nature of the ideas presented therein, the essay was soon nicknamed “The Killer Joke” (a Monty Python reference).<br /><br />Perhaps the most lasting contribution of the Don Beaudry hook is the API for the class creation function, which was carried over to the new metaclass machinery in Python 2.2. As described earlier, the class creation function is called with three arguments: a string giving the class name, a tuple giving the base classes (possibly empty or a singleton), and a dictionary giving the contents of the namespace in which the indented block with method definitions (and other class-level code) has been executed. The return value of the class creation function is assigned to a variable whose name is the class name.<br /><br />Originally, this was simply the internal API for creating classes. The Don Beaudry hook used the same call signature and hence it became a public API. The most important aspect of this API is that the block containing the method definitions is executed before the class creation function is called. This places certain restrictions on the effectiveness of metaclasses, since a metaclass cannot influence the initial contents of the namespace in which the method definitions are executed.<br /><br />This was changed in Python 3000, so that now a metaclass can provide an alternative mapping object in which the class body is executed. In order to support this, the syntax for specifying an explicit metaclass is also changed: it uses keyword argument syntax in the list of base classes, which was introduced for this purpose.<br /><br />In the next episode I'll write more about how the idea of metaclasses led to the introduction of new-style classes in 2.2 (and the eventual demise of classic classes in 3.0).Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com3tag:blogger.com,1999:blog-8699431508730375743.post-27573498770544463512009-04-23T11:01:00.000-07:002009-04-23T11:12:03.530-07:00New! Now in Japanese!There's now a <a href="http://python-history-jp.blogspot.com/">Japanese translation</a> of this blog. Yay! There is also a <a href="http://elornitorrincoenmascarado.blogspot.com/">Spanish version</a>, and a French version (sorry, I don't know the URL yet -- let me know if you do).<br /><br />I don't read those languages (or not well enough) and am not in a position to "approve" them, but I'm fine with their existence. If you want to start another translation, be my guest -- send me a link to the blog so I can update this page. If you see a mistake in a translation, just contact the translator directly. (However, I do <span style="font-style: italic;">not</span> want to see <span style="font-style: italic;">copies</span> of my blogs appearing. There's no point for those, and typically sites that copy popular blogs are just trying to attract eyeballs to their ads by reproducing popular material without putting any creative work into it.)Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com5tag:blogger.com,1999:blog-8699431508730375743.post-57736142618173093792009-04-22T16:35:00.000-07:002009-04-22T17:10:46.364-07:00And the Snake AttacksAlright. Fine. In 1995, when I was first exposed to Python, any reference to "snake" was verboten. Python was named after <a href="http://en.wikipedia.org/wiki/Monty_Python">Monty Python</a>, not the reptile. If anybody was attacking, it was <a href="http://en.wikipedia.org/wiki/Knights_who_say_Ni">Knights who say Ni</a> or possibly the <a href="http://en.wikipedia.org/wiki/Rabbit_of_Caerbannog">Rabbit of Caerbannog</a>.<br /><br />In any case... back in 1994, I was battling fictitious baddies in the LPMUD scene. The Web was barely present, and broadband was unheard of. Low-bandwidth entertainment was the order of the day.<br /><br />Wait. One more step back. 1979. My first computer was an Apple ][, and one of my favorite games was the <a href="http://en.wikipedia.org/wiki/Colossal_Cave">Colossal Cave</a>. Soon after that, I learned about and played Zork. I fell in love with the concept of interaction fiction and how a computer could lead you through these stories. These games hooked me, and led me into a life of computers. <i>(and yes, you can imagine my ecstasy at meeting Don Woods some 25+ years later!)</i><br /><br />So the MUD scene was quite interesting to me. But I wanted to help <i>build</i> these games. I met <a href="http://viega.org/">John Viega</a>, a fellow <a href="http://en.wikipedia.org/wiki/Lima_Mudlib">LPMUD game author</a>, coder, and designer. At the time, he was working at the University of Virginia in their Computer Graphics Lab, working on a system called Alice. Their system was intended for less computer-savvy and they wanted an easy-to-learn language for people to create animations. They chose Python for its clarity, power, and simplicity.<br /><br />John was a huge fan, and pointed me at Python. "You have to learn this!" "Fine. Fine.", I said. The language was easy, yet powerful. It could do everything, without a lot of hassle.<br /><br />That was February, 1995, and I haven't turned back.<br /><br />Little did I know, at the time, just how pivotal Python would be to my career and my life. Thank you, Guido, for your creation.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8699431508730375743.post-59099346513340269022009-04-21T11:05:00.000-07:002014-09-05T07:11:40.379-07:00Origins of Python's "Functional" FeaturesI have never considered Python to be heavily influenced by functional languages, no matter what people say or think. I was much more familiar with imperative languages such as C and Algol 68 and although I had made functions first-class objects, I didn't view Python as a functional programming language. However, earlier on, it was clear that users wanted to do much more with lists and functions.<br />
<br />
A common operation on lists was that of mapping a function to each of the elements of a list and creating a new list. For example:<br />
<blockquote>
<pre>def square(x):
return x*x
vals = [1, 2, 3, 4]
newvals = []
for v in vals:
newvals.append(square(v))</pre>
</blockquote>
<br />
In functional languages such as Lisp and Scheme, operations such as this were provided as built-in functions of the language. Thus, early users familiar with such languages found themselves implementing comparable functionality in Python. For example:<br />
<blockquote>
<pre>def map(f, s):
result = []
for x in s:
result.append(f(x))
return result
def square(x):
return x*x
vals = [1, 2, 3, 4]
newvals = map(square,vals)</pre>
</blockquote>
<br />
A subtle aspect of the above code is that many people didn't like the fact that you to define the operation that you were applying to the list elements as a completely separate function. Languages such as Lisp allowed functions to simply be defined "on-the-fly" when making the map function call. For example, in Scheme you can create anonymous functions and perform mapping operations in a single expression using lambda, like this:<br />
<blockquote>
<pre>(map (lambda (x) (* x x)) '(1 2 3 4)) </pre>
</blockquote>
<br />
Although Python made functions first-class objects, it didn't have any similar mechanism for creating anonymous functions.<br />
<br />
In late 1993, users had been throwing around various ideas for creating anonymous functions as well as various list manipulation functions such as map(), filter(), and reduce(). For example, Mark Lutz (author of "Programming Python") posted some code for a function that created functions using exec:<br />
<blockquote>
<pre>def genfunc(args, expr):
exec('def f(' + args + '): return ' + expr)
return eval('f')
# Sample usage
vals = [1, 2, 3, 4]
newvals = map(genfunc('x', 'x*x'), vals)</pre>
</blockquote>
<br />
Tim Peters then followed up with a solution that simplified the syntax somewhat, allowing users to type the following:<br />
<blockquote>
<pre>vals = [1, 2, 3, 4]
newvals = map(func('x: x*x'), vals)</pre>
</blockquote>
<br />
It was clear that there was a demand for such functionality. However, at the same time, it seemed pretty "hacky" to be specifying anonymous functions as code strings that you had to manually process through exec. Thus, in January, 1994, the map(), filter(), and reduce() functions were added to the standard library. In addition, the lambda operator was introduced for creating anonymous functions (as expressions) in a more straightforward syntax. For example:<br />
<blockquote>
<pre>vals = [1, 2, 3, 4]
newvals = map(lambda x:x*x, vals)</pre>
</blockquote>
<br />
These additions represented a significant, early chunk of contributed code. Unfortunately I don't recall the author, and the SVN logs don't record this. If it's yours, leave a comment! <b>UPDATE: </b>As is clear from Misc/HISTORY in the repo these were contributed by Amrit Prem, a prolific early contributor.<br />
<br />
I was never all that happy with the use of the "lambda" terminology, but for lack of a better and obvious alternative, it was adopted for Python. After all, it was the choice of the now anonymous contributor, and at the time big changes required much less discussion than nowadays, <a href="http://www.python.org/dev/peps/pep-0001/">for better</a> and <a href="http://yellow.bikeshed.com/">for worse</a>.<br />
<br />
Lambda was really only intended to be a syntactic tool for defining anonymous functions. However, the choice of terminology had many unintended consequences. For instance, users familiar with functional languages expected the semantics of lambda to match that of other languages. As a result, they found Python’s implementation to be sorely lacking in advanced features. For example, a subtle problem with lambda is that the expression supplied couldn't refer to variables in the surrounding scope. For example, if you had this code, the map() function would break because the lambda function would run with an undefined reference to the variable 'a'.<br />
<blockquote>
<pre>def spam(s):
a = 4
r = map(lambda x: a*x, s)</pre>
</blockquote>
<br />
There were workarounds to this problem, but they counter-intuitively involved setting default arguments and passing hidden arguments into the lambda expression. For example:<br />
<blockquote>
<pre>def spam(s):
a = 4
r = map(lambda x, a=a: a*x, s)</pre>
</blockquote>
<br />
The "correct" solution to this problem was for inner functions to implicitly carry references to all of the local variables in the surrounding scope that are referenced by the function. This is known as a "closure" and is an essential aspect of functional languages. However, this capability was not introduced in Python until the release of version 2.2 (though it could be imported "from the future" in Python 2.1).<br />
<br />
Curiously, the map, filter, and reduce functions that originally motivated the introduction of lambda and other functional features have to a large extent been superseded by list comprehensions and generator expressions. In fact, the reduce function was removed from list of builtin functions in Python 3.0. (However, it's not necessary to send in complaints about the removal of lambda, map or filter: they are staying. :-)<br />
<br />
It is also worth nothing that even though I didn't envision Python as a functional language, the introduction of closures has been useful in the development of many other advanced programming features. For example, certain aspects of new-style classes, decorators, and other modern features rely upon this capability.<br />
<br />
Lastly, even though a number of functional programming features have been introduced over the years, Python still lacks certain features found in “real” functional programming languages. For instance, Python does not perform certain kinds of optimizations (e.g., tail recursion). In general, because Python's extremely dynamic nature, it is impossible to do the kind of compile-time optimization known from functional languages like Haskell or ML. And <a href="http://hugunin.net/story_of_jython.html">that's fine</a>.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com21tag:blogger.com,1999:blog-8699431508730375743.post-88120059435969641142009-03-31T08:44:00.000-07:002009-03-31T09:18:46.706-07:00The Great (or Grand) RenamingWhen Python was first created, I always envisioned it as a stand-alone program, occasionally linking in third-party libraries. The source code therefore freely defined global names (in the C/linker sense) like ‘object’, ‘getlistitem’, ‘INCREF’ and so on. As Python’s popularity grew, people started to ask for an “embedded” version of Python, which would itself be a library that could be linked into other applications – not unlike the way that Emacs incorporates a Lisp interpreter.<br /><br />Unfortunately, this embedding was complicated by name clashes between Python’s global names and those defined by the embedding application – the name 'object’ was especially popular. To deal with this problem, a naming convention was chosen, whereby all Python globals would have a name starting with “Py” or “_Py” (for internal names that had to be global for technical reasons) or “PY” (for macros).<br /><br />For backwards compatibility reasons (there were already many third party extension modules) and to ease the transition for core developers (who had the old names engrained in their brain) there were two phases. In phase one the linker saw the old names, but the source code used the new names, which were translated to the old names using a large number of C preprocessor macros. In phase two the linker saw the new names, but for the benefit of some laggard extension modules that hadn’t been ported yet, another set of macros now translated the old names to the new names. In both phases, the code could mix old and new names and work correctly.<br /><br />I researched the history of these renamings a bit in our <a href="http://svn.python.org/view/python/trunk/">Subversion logs</a>. I found <a href="http://svn.python.org/view?view=rev&revision=4583">r4583</a> from January 12, 1995, which signalled phase two of the great renaming was started by introducing the new names to all header files. But in December 1996 the renaming of .c source files was still going on. Around this time the renaming seems to have been renamed, and checkin comments often refer to the "Grand Renaming". The backwards compatibility macros were finally removed in May 2000, as part of the Python 1.6 release effort. The check-in comment for <a href="http://svn.python.org/view?view=rev&revision=15313">r15313</a> celebrates this event.<br /><br />Much credit goes to Barry Warsaw and Roger Masse, who participated in the unthankful task of renaming the contentes of file after file after file (albeit with the help of a script). They also helped with the equally tedious task of adding unit tests for much of the standard library.<br /><br />Wikipedia has a reference to an earlier Great Renaming event, which apparently involved renaming USENET groups. I probably unconsciously remenbered that event when I named Python's Great Renaming. I also found some references to a later Grand Renaming in Sphinx, the package used for generating Python's documentation. Zope also seems to have had a Grand Renaming, and some recent Py3k discussions also used the term for the PyString -> PyBytes renaming (although this is a minor one compared to the others).<br /><br />Great or Grand Renamings are often traumatic events for software developer communities, since they requires the programmers' brains to be rewired, documentation to be rewritten, and complicate the integration of patches created before the renaming but applied after. (This is especially problematic when unrenamed branches exist.)Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com1tag:blogger.com,1999:blog-8699431508730375743.post-17690269267290453562009-03-17T13:07:00.000-07:002009-03-17T13:16:46.904-07:00Dynamically Loaded ModulesPython’s implementation architecture made it easy to write extension modules written in C right from the start. However, in the early days, dynamic loading technology was obscure enough that such extensions had to be statically linked into Python interpreter at build time. To do this, C extension modules had to be added to a shell script that was used to generate the Makefile for Python and all of its extension modules.<br /><br />Although this approach worked for small projects, the Python community started producing new extension modules at an unanticipated rate, and demanded that extension modules could be compiled and loaded separately. Shortly thereafter, code interfacing to the platform-specific dynamic linking API was contributed which allowed the import statement to go out to disk looking for a shared library as well as a “.py” file. The first mention of dynamic loading in the CVS logs stems from January 1992 and most major platforms were supported by the end of 1994.<br /><br />The dynamic linking support proved to be very useful, but also introduced a maintenance nightmare. Each platform used a different API and some platforms had additional constraints. In January 1995, the dynamic linking support was restructured so that all the dynamic linking code was concentrated in a single source file. However, the approach resulted in a large file cluttered with conditional compilation directives (#ifdef). In December 1999, it was restructured again with the help of Greg Stein so that the platform-specific code for each platform was placed in a file specific to that platform (or family of platforms).<br /><br />Even though Python supported dynamically loadable modules, the procedure for building such modules often remained a mystery to many users. An increasingly large number of users were building modules--especially with the introduction of extension building tools such as SWIG. However, a user wishing to distribute an extension module faced major hurdles getting the module to compile on all possible combinations of platforms, compilers, and linkers. In a worst-case scenario, a user would have to write their own Makefile and configuration script for setting the right compiler and linker flags. Alternatively, a user could also add their extension module to Python's own Makefile and perform a partial Python rebuild to have the module compiled with the right options. However, this required end users to have a Python source distribution on-hand.<br /><br />Eventually, a Python extension building tool called distutils was invented that allowed building and installing extension modules from anywhere. The necessary compiler and linker options were written by Python’s makefile to a data file, which was then consulted by distutils when building extension modules. Largely written by Greg Ward, the first versions of distutils were distributed separately, to support older Python versions. Starting with Python 1.6 it was integrated into Python distributions as a standard library module.<br /><br />It is worth noting that distutils does far more than simply building extension modules from C source code. It can also install pure Python modules and packages, create Windows installer executables, and run third party tools such as SWIG. Alas, its complexity has caused many folks to curse it, and it has not received the maintenance attention it deserved. As a result, in recent times, 3rd party alternatives (especially ez_install, a.k.a. "eggs") have become popular, unfortunately causing fragmentation in the development community, as well as complaints whenever it doesn't work. It seems that the problem in its full generality is just inherently difficult.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com4tag:blogger.com,1999:blog-8699431508730375743.post-75371296256220574602009-03-10T13:31:00.000-07:002009-03-10T13:43:58.091-07:00The Problem with Integer DivisionPython's handling of integer division is an example of early mistake with huge consequences. As mentioned earlier, when Python was created, I abandoned the approach to numbers that had been used in ABC. For example, in ABC, when you divided two integers, the result was an exact rational number representing the result. In Python however, integer division truncated the result to an integer.<br /><br />In my experience, rational numbers didn't pan out as ABC's designers had hoped. A typical experience would be to write a simple program for some business application (say, doing one’s taxes), and find that it was running much slower than expected. After some debugging, the cause would be that internally the program was using rational numbers with thousands of digits of precision to represent values that would be truncated to two or three digits of precision upon printing. This could be easily fixed by starting an addition with an inexact zero, but this was often non-intuitive and hard to debug for beginners.<br /><br />So with Python, I relied on the other numerical model with which I was familiar, C. C has integers and floating point numbers of various sizes. So, I chose to represent Python integers by a C long (guaranteeing at least 32 bits of precision) and floating point numbers by a C double. I then added an arbitrary precision integer type which I called "long."<br /><br />The major mistake was that I also borrowed a rule that makes sense in C but not so much in a very-high-level language. For the standard arithmetic operations, including division, the result would always be the same type as the operands. To make matters worse, I initially used another misguided rule that forbade mixed-mode arithmetic, with the aim of making the type implementations independent from each other. So, originally you couldn’t add an int to a float, or even an int to a long. After Python was released publicly, Tim Peters quickly convinced me that this was a really bad idea, and I introduced mixed-mode arithmetic with the usual coercion rules. For example, mixing an int and a long operand would convert the argument of type int to long and return a long result and mixing either with float would convert the int or long argument to float and return a float result..<br /><br />Unfortunately, the damage was done--integer division returned an integer result. You might be wondering "Why was this so bad?" Was this really just an ado about nothing? Historically, the proposal to change this has had some tough opposition from folks who believed that learning about integer division was one of the more useful "rites of passage" for all programmers. So let me explain the reasons for considering this a design bug.<br /><br />When you write a function implementing a numeric algorithm (for example, calculating the phase of the moon) you typically expect the arguments to be specified as floating point numbers. However, since Python doesn’t have type declarations, nothing is there to stop a caller from providing you with integer arguments. In a statically typed language, like C, the compiler will coerce the arguments to floats, but Python does no such thing – the algorithm is run with integer values until the wonders of mixed-mode arithmetic produce intermediate results that are floats.<br /><br />For everything except division, integers behave the same as the corresponding floating point numbers. For example, 1+1 equals 2 just as 1.0+1.0 equals 2.0, and so on. Therefore one can easily be misled to expect that numeric algorithms will behave regardless of whether they execute with integer or floating point arguments. However, when division is involved, and the possibility exists that both operands are integers, the numeric result is silently truncated, essentially inserting a potentially large error into the computation. Although one can write defensive code that coerces all arguments to floats upon entry, this is tedious, and it doesn’t enhance the readability or maintainability of the code. Plus, it prevents the same algorithm from being used with complex arguments (although that may be highly special cases).<br /><br />Again, all of this is an issue because Python doesn’t coerce arguments automatically to some declared type. Passing an invalid argument, for example a string, is generally caught quickly because few operations accept mixed string/numeric operands (the exception being multiplication). However, passing an integer can cause an answer that is close to the correct answer but has a much larger error – which is difficult to debug or even notice. (This recently happened to me in a program that draws an analog clock – the positions of the hands were calculated incorrectly due to truncation, but the error was barely detectable except at certain times of day.)<br /><br />Fixing integer division was no easy task due to programs that rely on the behavior of integer truncation. A truncating division operator (//) was added to the language to provide the same functionality. In addition, a mechanism ("from __future__ import division") was introduced by which the new integer division semantics could be enabled.Finally , a command line flag (-Qxxx) was added both to change the behavior and to aid in program conversion. Fortunately, the correct behavior has become the default behavior in Python 3000.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com13tag:blogger.com,1999:blog-8699431508730375743.post-77262733951972304222009-03-06T09:26:00.000-08:002009-03-07T07:26:01.941-08:00How Exceptions Came to be ClassesEarly on, I knew I wanted Python to use exceptions for error handling. However, a critical part of making exceptions work is to come up with some kind of scheme for identifying different kinds of exceptions. In modern languages (including modern Python :-), exceptions are defined in terms of user-defined classes. In early Python however, I chose to identify exceptions by strings. This was unfortunate, but I had two reasons for taking this approach. First, I learned about exceptions from Modula-3, where exceptions are unique tokens. Second, I introduced exceptions before I introduced user-defined classes.<br /><br />In theory, I suppose I could have created a new type of built-in object to be used for exceptions, but as every built-in object type required a considerable coding effort in C, I decided to reuse an existing built-in type. And, since exceptions are associated with error messages, it seemed natural to use strings to represent exceptions.<br /><br />Unfortunately I chose semantics where different string objects would represent different exceptions, even if they had the same value (i.e. contained the same sequence of characters). I chose these semantics because I wanted exceptions defined in different modules to be independent, even if they happened to have the same value. The idea was that exceptions would always be referenced by their name, which would imply object identity, never by their value, which would require string equality.<br /><br />This approach was influenced by Modula-3’s exceptions, where each exception declaration creates a unique “exception token” that can’t be confused with any other exception token. I think I also wanted to optimize testing for exceptions by using pointer comparisons instead of string value comparisons in a misguided attempt to prematurely optimize execution time (a rare one – I usually optimized for my own coding time!). The main reason however is that I worried about name clashes between unrelated exceptions defined in different modules. I intended the usage pattern to strictly adhere to the convention of defining an exception as a global constant in some module, and then using it by name in all code raising or catching it. (This was also long before certain string literals would be automatically be “interned”.)<br /><br />Alas, in practice things never quite work out as you expect. Early Python users discovered that within the same module, the byte code compiler would unify string literals (i.e., create a single shared object for all occurrences of string literals with the same value). Thus, by accident, users found that exceptions could either be caught be specifying the exception name or the string literal containing the error message. Well, at least this seemed to work most of the time. In reality, it only worked for code defined in the same module---if one tried to catch exceptions using the exception error message in a different module, it broke mysteriously. Needless to say, this is the sort of thing that causes widespread confusion.<br /><br />In 1997, with Python 1.5, I introduced class exceptions into the language. Although class exceptions have been the recommended approach ever since, string exceptions were still supported for use by certain legacy applications through Python 2.5. They were finally removed in Python 2.6.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com6tag:blogger.com,1999:blog-8699431508730375743.post-52492853088164819892009-03-03T12:02:00.000-08:002009-03-03T12:05:45.428-08:00How Everything Became an Executable StatementNew users to Python are sometimes surprised to find out that every part of the language is an executable statement, including function and class definitions. That means that any statement can appear anywhere in a program. For instance, a function definition could appear inside an "if" statement if you wanted.<br /><br />In a very early version of Python’s grammar, this was not the case: grammar elements that had a “declarative flavor”, like import statements and function definitions, were allowed only at the top level in a module or script (where they were being executed in order to become effective). However, at the time I was adding support for classes, I decided that this was too restrictive.<br /><br />My reasoning went roughly as follows. Rather than defining the class body as a series of function declarations only, it seemed to make sense to also allow regular variable assignments there. However, if I was going to allow that, why not go one step further and allow arbitrary executable code? Or, taking this even further, why not allow function declarations inside an “if” statement, for example? It quickly became clear that this enabled a simplification of the grammar, since now all uses of statements (whether indented or not) could share the same grammar rule, and hence the compiler could use the same byte code generation function for all of them.<br /><br />Although this reasoning allowed me to simplify the grammar and allowed users to place Python statements anywhere, this feature did not necessarily enable certain styles of programming. For example, the Python grammar technically allowed users to write things such as nested functions even though the underlying semantics of Python didn't support nested scopes. Therefore, code such as that would often operate in ways that were unexpected or "broken" compared to languages that were actually designed with such features in mind. Over time, many of these "broken" features have been fixed. For example, nested function definitions only began to work more sanely in Python 2.1.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com0tag:blogger.com,1999:blog-8699431508730375743.post-82896118536467027752009-02-27T11:59:00.000-08:002009-02-27T12:13:55.362-08:00First-class Everything<span style="font-style: italic;">[Folks, please don't use the comments section of this blog to ask questions. If you want to suggest a topic for a future blog entry, send me email. (Use Google to find my home page, which has my email address.) If you want to propose a change or discuss the merits of alternative designs, use the python-ideas mailing list at python.org.]</span><br /><br />One of my goals for Python was to make it so that all objects were "first class." By this, I meant that I wanted all objects that could be named in the language (e.g., integers, strings, functions, classes, modules, methods, etc.) to have equal status. That is, they can be assigned to variables, placed in lists, stored in dictionaries, passed as arguments, and so forth.<br /><br />The internal implementation of Python made this simple to do. All of Python's objects were based on a common C data structure that was used everywhere in the interpreter. Variables, lists, functions, and everything else just used variations of this one data structure---it just didn't matter if the structure happened to represent a simple object such as an integer or something more complicated such as a class.<br /><br />Although the idea of having "first-class everything" is conceptually simple, there was still one subtle aspect of classes that I still needed to address---namely, the problem of making methods first class objects.<br /><br />Consider this simple Python class (copied from last week's blog post):<br /><pre><span style="font-family: courier new;">class A:</span><br /><span style="font-family: courier new;"> def __init__(self,x):</span><br /><span style="font-family: courier new;"> self.x = x</span><br /><span style="font-family: courier new;"> def spam(self,y):</span><br /><span style="font-family: courier new;"> print self.x, y</span></pre>If methods are going to be first-class objects, then they can be assigned to other variables and used just like other objects in Python. For example, someone could write a Python statement such as "s = A.spam". In this case, the variable "s" refers to a method of a class, which is really just a function. However, a method is not quite the same as ordinary function. Specifically, the first argument of a method is supposed to be an instance of the class in which a method was defined.<br /><br />To deal with this, I created a type of callable object known as an "unbound method." An unbound method was really just a thin wrapper around the function object that implemented a method, but it enforced a restriction that the first argument had to be an instance of the class in which the method was defined. Thus, if someone wanted to call an unbound method "s" as a function, they would have to pass an instance of class "A" as the first argument. For example, "a = A(); s(a)". (*)<br /><br />A related problem occurs if someone writes a Python statement that refers to a method on a specific instance of an object. For example, someone might create an instance using "a = A()" and then later write a statement such as "s = a.spam". Here, the variable "s" again refers to a method of a class, but the reference to that method was obtained through an instance "a" . To handle this situation, a different callable object known as a "bound method." is used. This object is also a thin wrapper around the function object for the method. However, this wrapper implicitly stores the original instance that was used to obtain the method. Thus, a later statement such as "s()" will call the method with the instance "a" implicitly set as the first argument.<br /><br />In reality, the same internal object type is used to represent bound and unbound methods. One of the attributes of this object contains a reference to an instance. If set to None, the method is unbound. Otherwise, the method is bound.<br /><br />Although bound and unbound methods might seem like an unimportant detail, they a critical part of how classes work underneath the covers. Whenever a statement such as "a.spam()" appears in a program, the execution of that statement actually occurs in two steps. First, a lookup of "a.spam" occurs. This returns a bound method--a callable object. Next, a function call operation "()" is applied to that object to invoke the method with user supplied arguments.<br /><br />__________<br />(*) In Python 3000, the concept of unbound methods has been removed, and the expression "A.spam" returns a plain function object. It turned out that the restriction that the first argument had to be an instance of A was rarely helpful in diagnosing problems, and frequently an obstacle to advanced usages --- some have called it "duck typing self" which seems an appropriate name.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com3tag:blogger.com,1999:blog-8699431508730375743.post-11327672064725883372009-02-18T11:25:00.000-08:002009-03-03T11:33:34.869-08:00Adding Support for User-defined ClassesBelieve it or not, classes were added late during Python’s first year of development at CWI, though well before the first public release. However, to understand how classes were added, it first helps to know a little bit about how Python is implemented.<br /><br />Python is implemented in C as a classic stack-based byte code interpreter or “virtual machine” along with a collection of primitive types also implemented in C. The underlying architecture uses “objects” throughout, but since C has no direct support for objects, they are implemented using structures and function pointers. The Python virtual machine defines several dozen standard operations that every object type may or must implement (for example, “get attribute”, “add” and “call”). An object type is then represented by a statically allocated structure containing a series of function pointers, one for each standard operation. These function pointers are typically initialized with references to static functions. However, some operations are optional, and the object type may leave the function pointer NULL if it chooses not to implement that operation. In this case, the virtual machine either generates a run-time error or, in some cases, provides a default implementation of the operation. The type structure also contains various data fields, one of which is a reference to a list of additional methods that are unique to this type, represented as an array of structures containing a string (the method name) and a function pointer (its implementation) each. Python’s unique approach to introspection comes from its ability to make the type structure itself available at run-time as an object like all others.<br /><br />An important aspect of this implementation is that it is completely C-centric. In fact, all of the standard operations and methods are implemented by C functions. Originally the byte code interpreter only supported calling pure Python functions and functions or methods implemented in C. I believe my colleague Siebren van der Zee was the first to suggest that Python should allow class definitions similar to those in C++ so that objects could also be implemented in Python.<br /><br />To implement user-defined objects, I settled on the simplest possible design; a scheme where objects were represented by a new kind of built-in object that stored a class reference pointing to a "class object" shared by all instances of the same class, and a dictionary, dubbed the "instance dictionary", that contained the instance variables.<br /><br />In this implementation, the instance dictionary would contain the instance variables of each individual object whereas the class object would contain stuff shared between all instances of the same class--in particular, methods. In implementing class objects, I again chose the simplest possible design; the set of methods of a class were stored in a dictionary whose keys are the method names. This, I dubbed the class dictionary. To support inheritance, class objects would additionally store a reference to the class objects corresponding to the base classes. At the time, I was fairly naïve about classes, but I knew about multiple inheritance, which had recently been added to C++. I decided that as long as I was going to support inheritance, I might as well support a simple-minded version of multiple inheritance. Thus, every class object could have one or more base classes.<br /><br />In this implementation, the underlying mechanics of working with objects are actually very simple. Whenever changes are made to instance or class variables, those changes are simply reflected in the underlying dictionary object. For example, setting an instance variable on an instance updates its local instance dictionary. Likewise, when looking up the value of a instance variable of an object, one merely checks its instance dictionary for the existence of that variable. If the variable is not found there, things become a little more interesting. In that case, lookups are performed in the class dictionary and then in the class dictionaries of each of the base classes.<br /><br />The process of looking up attributes in the class object and base classes is most commonly associated with locating methods. As previously mentioned, methods are stored in the dictionary of a class object which is shared by all instances of the same class. Thus, when a method is requested, you naturally won't find it in the instance dictionary of each individual object. Instead, you have to look it up in the class dictionary, and then ask each of the base classes in turn, stopping when a hit is found. Each of the base classes then implements the same algorithm recursively. This is commonly referred to as the depth-first, left-to-right rule, and has been the default method resolution order (MRO) used in most versions of Python. More modern releases have adapted a more sophisticated MRO, but that will be discussed in a later blog.<br /><br />In implementing classes, one of my goals was to keep things simple. Thus, Python performs no advanced error checking or conformance checking when locating methods. For example, if a class overrides a method defined in a base class, no checks are performed to make sure that the redefined method has the same number of arguments or that it can be called in the same way as the original base-class method. The above method resolution algorithm merely returns the first method found and calls it with whatever arguments the user has supplied.<br /><br />A number of other features also fall out of this design. For instance, even though the class dictionary was initially envisioned as a place to put methods, there was no inherent reason why other kinds of objects couldn't be placed there as well. Thus, if objects such as integers or strings are stored in the class dictionary, they become what are known as class variables---variables shared by all instances of a given class instead of being stored inside each instance.<br /><br />Although the implementation of classes is simple, it also provides a surprisingly degree of flexibility. For instance, the implementation not only makes classes “first-class objects”, which are easily introspected at run time, it also makes it possible to modify a class dynamically. For example, methods can be added or modified by simply updating the class dictionary after a class object has already been created! (*) The dynamic nature of Python means that these changes have an immediate effect on all instances of that class or of any of its subclasses. Likewise, individual objects can be modified dynamically by adding, modifying, and deleting instance variables (a feature that I later learned made Python's implementation of objects more permissive than that found in Smalltalk which restricts the set of attributes to those specified at the time of object creation).<br /><br /><span style="font-size:130%;"><span style="font-weight: bold;">Development of the class Syntax</span></span><br /><br />Having designed the run-time representations for user-defined classes and instances, my next task was to design the syntax for class definitions, and in particular for the method definitions contained therein. A major design constraint was that I didn’t want to add syntax for methods that differed from the syntax for functions. Refactoring the grammar and the byte code generator to handle such similar cases differently felt like a huge task. However, even if I was successful in keeping the grammar the same, I still had to figure out some way to deal with instance variables. Initially, I had hoped to emulate implicit instance variables as seen in C++. For example, in C++, classes are defined by code like this:<br /><pre><br /><span style="font-family:courier new;">class A {</span><br /><span style="font-family:courier new;">public:</span><br /><span style="font-family:courier new;"> int x;</span><br /><span style="font-family:courier new;"> void spam(int y) {</span><br /><span style="font-family:courier new;"> printf("%d %d\n", x, y);</span><br /><span style="font-family:courier new;"> }</span><br /><span style="font-family:courier new;">};</span><br /></pre><br />In this class, an instance variable x has been declared. In methods, references to x implicitly refer to the corresponding instance variable. For example, in the method spam(), the variable x is not declared as either function parameter or as local variable However, since the class has declared an instance variable with that name, references to x simply refer to that variable. Although I had hoped to provide something similar in Python, it quickly became clear that such an approach would be impossible because there was no way to elegantly distinguish instance variables from local variables in a language without variable declarations.<br /><br />In theory, getting the value of instance variables would be easy enough. Python already had a search order for unqualified variable names: locals, globals, and built-ins. Each of these were represented as a dictionary mapping variable names to values. Thus, for each variable reference, a series of dictionaries would be searched until a hit was found. For example, when executing a function with a local variable p, and a global variable q, a statement like “print p, q” would look up p in the first dictionary in the search order, the dictionary containing local variables, and find a match. Next it would look up q in the first dictionary, find no match, then look it up in the second dictionary, the global variables, and find a match.<br /><br />It would have been easy to add the current object’s instance dictionary in front of this search list when executing a method. Then, in a method of an object with an instance variable x and local variable y, a statement like “print x, y” would find x in the instance dictionary (the first dictionary on the search path) and y in the local variable dictionary (the second dictionary).<br /><br />The problem with this strategy is that it falls apart for setting instance variables. Python’s assignment doesn’t search for the variable name in the dictionaries, but simply adds or replaces the variable in the first dictionary in the search order, normally the local variables. This has the effect that variables are always created in the local scope by default (although it should be noted that there is a “global declaration” to override this on a per-function, per-variable basis.)<br /><br />Without changing this simple-minded approach to assignment, making the instance dictionary the first item in the search order would make it impossible to assign to local variables in a method. For example, if you had a method like this<br /><pre><br /><span style="font-family:courier new;">def spam(y):</span><br /><span style="font-family:courier new;"> x = 1 </span><br /><span style="font-family:courier new;"> y = 2 </span><br /></pre><br />The assignments to x and y would overwrite the instance variable x and create a new instance variable y that shadowed the local variable y. Swapping instance variables and local variables in the search order would merely reverse the problem, making it impossible to assign to instance variables.<br /><br />Changing the semantics of assignment to assign to an instance variable if one already existed and to a local otherwise wouldn’t work either, since this would create a bootstrap problem: how does an instance variable get created initially? A possible solution might have been to require explicit declaration of instance variables as was the case for global variables, but I really didn’t want to add a feature like that given that that I had gotten this far without any variable declarations at all. Plus, the extra specification required for indicating a global variable was more of a special case that was used sparingly in most code. Requiring a special specification for instance variables, on the other hand, would have to be used almost everywhere in a class. Another possible solution would have been to make instance variables lexically distinct. For example, having instance variables start with a special character such as @ (an approach taken by Ruby) or by having some kind of special naming convention involving prefixes or capitalization. Neither of these appealed to me (and they still don't).<br /><br />Instead, I decided to give up on the idea of implicit references to instance variables. Languages like C++ let you write this->foo to explicitly reference the instance variable foo (in case there’s a separate local variable foo). Thus, I decided to make such explicit references the only way to reference instance variables. In addition, I decided that rather than making the current object ("this") a special keyword, I would simply make "this" (or its equivalent) the first named argument to a method. Instance variables would just always be referenced as attributes of that argument.<br /><br />With explicit references, there is no need to have a special syntax for method definitions nor do you have to worry about complicated semantics concerning variable lookup. Instead, one simply defines a function whose first argument corresponds to the instance, which by convention is named "self." For example:<br /><pre><br /><span style="font-family:courier new;">def spam(self,y):</span><br /><span style="font-family:courier new;"> print self.x, y</span><br /></pre><br />This approach resembles something I had seen in Modula-3, which had already provided me with the syntax for import and exception handling. Modula-3 doesn’t have classes, but it lets you create record types containing fully typed function pointer members that are initialized by default to functions defined nearby, and adds syntactic sugar so that if x is such a record variable, and m is a function pointer member of that record, initialized to function f, then calling x.m(args) is equivalent to calling f(x, args). This matches the typical implementation of objects and methods, and makes it possible to equate instance variables with attributes of the first argument.<br /><br />The remaining details of Python’s class syntax follow from this design or from the constraints imposed by the rest of the implementation. Keeping with my desire for simplicity, I envisioned a class statement as a series of method definitions, which are syntactically identical to function definitions even though by convention, they are required to have a first argument named "self". In addition, rather than devising a new syntax for special kinds of class methods (such as initializers and destructors), I decided that these features could be handled by simply requiring the user to implement methods with special names such as __init__, __del__, and so forth. This naming convention was taken from C where identifiers starting with underscores are reserved by the compiler and often have special meaning (e.g., macros such as __FILE__ in the C preprocessor).<br /><br />Thus, I envisioned that a class would be defined by code that looked like this:<br /><pre><br /><span style="font-family:courier new;">class A:</span><br /><span style="font-family:courier new;"> def __init__(self,x):</span><br /><span style="font-family:courier new;"> self.x = x</span><br /><span style="font-family:courier new;"> def spam(self,y):</span><br /><span style="font-family:courier new;"> print self.x, y</span><br /></pre><br />Again, I wanted to reuse as much of my earlier code as possible. Normally, a function definition is an executable statement that simply sets a variable in the current namespace referencing the function object (the variable name is the function name). Thus, rather than coming up with an entirely different approach for handling classes, it made sense to me to simply interpret the class body as a series of statements that were executed in a new namespace. The dictionary of this namespace would then be captured and used to initialize the class dictionary and create a class object. Underneath the covers, the specific approach taken is to turn the class body into an anonymous function that executes all of the statements in the class body and then returns the resulting dictionary of local variables. This dictionary is then passed to a helper function that creates a class object. Finally, this class object is then stored in a variable in the surrounding scope, whose name is the class name. Users are often surprised to learn that any sequence of valid Python statements can appear in a class body. This capability was really just a straightforward extension of my desire to keep the syntax simple as well as not artificially limiting what might possibly be useful.<br /><br />A final detail is the class instantiation (instance creation) syntax. Many languages, like C++ and Java, use a special operator, “new”, to create new class instances. In C++ this may be defensible since class names have a rather special status in the parser, but in Python this is not the case. I quickly realized that, since Python’s parser doesn’t care what kind of object you call, making the class object itself callable was the right, “minimal” solution, requiring no new syntax. I may have been ahead of my time here---today, factory functions are often the preferred pattern for instance creation, and what I had done was simply to turn each class into its own factory.<br /><br /><span style="font-size:130%;"><span style="font-weight: bold;">Special Methods</span></span><br /><br />As briefly mentioned in the last section, one of my main goals was to keep the implementation of classes simple. In most object oriented languages, there are a variety of special operators and methods that only apply to classes. For example, in C++, there is a special syntax for defining constructors and destructors that is different than the normal syntax used to define ordinary function and methods.<br /><br />I really didn't want to introduce additional syntax to handle special operations for objects. So instead, I handled this by simply mapping special operators to a predefined set of "special method" names such as __init__ and __del__. By defining methods with these names, users could supply code related to the construction and destruction of objects.<br /><br />I also used this technique to allow user classes to redefine the behavior of Python's operators. As previously noted, Python is implemented in C and uses tables of function pointers to implement various capabilities of built-in objects (e.g., “get attribute”, “add” and “call”). To allow these capabilities to be defined in user-defined classes, I mapped the various function pointers to special method names such as __getattr__, __add__, and __call__. There is a direct correspondence between these names and the tables of function pointers one has to define when implementing new Python objects in C.<br /><br />__________<br />(*) Eventually, new-style classes made it necessary to control changes to the class __dict__; you can still dynamically modify a class, but you must use attribute assignment rather than using the class __dict__ directly.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com8tag:blogger.com,1999:blog-8699431508730375743.post-21163321145301013412009-02-10T11:27:00.000-08:002009-02-10T11:31:01.799-08:00Python's Use of Dynamic TypingAn important difference between <a href="http://homepages.cwi.nl/%7Esteven/abc/">ABC</a> and Python is the general flavor of the type system. ABC is statically typed which meant that the ABC compiler analyzes the use of types in a program and decides whether they are used consistently. If not, the program is rejected and its execution cannot be started. Unlike most statically typed languages of its days, ABC used type inference (not unlike <a href="http://www.haskell.org/">Haskell</a>) instead of explicit type declarations as you find in languages such as in C. In contrast, Python is dynamically typed. The Python compiler is blissfully unaware of the types used in a program, and all type checking is done at run time.<br /><br />Although this might seem like a large departure from ABC, it is not as different as you might imagine. Unlike other statically typed languages, ABC doesn't (didn't? it's pretty much purely historic now :-) exclusively rely on static type checking to keep the program from crashing, but has a run-time library that checks the argument types for all operations again each time they are executed. This was done in part as a sanity check for the compiler’s type-checking algorithms, which were not fully implemented in the initial prototype implementation of the language. The runtime library was also useful as a debugging aid since explicit run time type checking could produce nice error messages (aimed at the implementation team), instead of the core dumps that would ensue if the interpreter were to blindly go ahead with an operation without checking if the arguments make sense.<br /><br />However, the most important reason why ABC has run time type checking in addition to static type checking is that it is interactive. In an interactive session, the user types ABC statements and definitions which are executed as soon as they are completed. In an interactive session, it is possible to create a variable as a number, delete it, and then to recreate it (in other words, create another variable with the same name) as a string. Inside a single procedure, it would be a static typing error to use the same variable name first as a number and then as a string, but it would not be reasonable to enforce such type checking across different statements entered in an interactive session, as the accidental creation of a variable named x as a number would forever forbid the creation of a variable x with a different type! So as a compromise, ABC uses dynamic type checking for global variables, but static type checking for local variables. To simplify the implementation, local variables are dynamically type checked as well.<br /><br />Thus, it is only a small step from ABC’s implementation approach to type checking to Python’s approach--Python simply drops the compile-time type checking completely. This is entirely in line with Python’s “corner-cutting” philosophy as it’s a simplification of the implementation that does not affect the eventual safety, since all type errors are caught at run time before they can cause the Python interpreter to malfunction.<br /><br />However, once you decide on dynamic typing, there is no way to go back. ABC’s built-in operations were carefully designed so that the type of the arguments could be deduced from the form of the operation. For example, from the expression “<span style="font-family: courier new;">x^y</span>” the compiler would deduce that variables x and y were strings, as well as the expression result. In Python, such deductions cannot generally be made. For example, the expression “<span style="font-family: courier new;">x+y</span>” could be a string concatenation, a numeric addition, or an overloaded operation on user-defined types.Guido van Rossumhttp://www.blogger.com/profile/12821714508588242516noreply@blogger.com6