Here is a thunk, a kind of delayed apply that takes a function and arguments but, rather than calling the function right away returns another function that, when called, will call the first function with the arguments originally given.
thunk = lambda name, *args: lambda: name(*args)
Here is a trampoline that basically unwraps nested thunks until a result is found.
def _trampoline(bouncer): while callable(bouncer): bouncer = bouncer() return bouncer
Here is a useful wrapper function that turns a function into a trampolined version.
trampoline = lambda f: lambda *args: _trampoline(f(*args))
Now let's just define one more ingredient, an identity function.
identity = lambda x: x
Now we can write factorial in continuation-passing style:
_factorial = lambda n, c=identity: c(1) if n == 0 else thunk(_factorial, n - 1, lambda result: thunk(c, n * result))
and trampoline it:
factorial = trampoline(_factorial)
We now have a factorial function that doesn't have stack limitations. You can say
print factorial(100000)
and (a couple of minutes later) Python will happily display the result :-)
I did consider currying thunk:
thunk = lambda name: lambda *args: lambda: name(*args)
so the CPS factorial would be:
_factorial = lambda n, c=identity: c(1) if n == 0 else thunk(_factorial)(n - 1, lambda result: thunk(c)(n * result))
UPDATE: Sorry to the first few commentors, due to a cute-and-paste SNAFU I was using the curried version of thunk for the first definition of _factorial. Now fixed.
by : Created on March 30, 2008 : Last modified March 30, 2008 : (permalink)
(on a bit of a roll with the Poincaré Project recently)
Back in 2006, I talked about the notion of a coordinate system which, for some region of a manifold, provides a tuple of real numbers identifying each point in that region. The mapping is homeomorphic so the coordinate system is continuous.
You can think of each component of the tuple as a separate function that maps from a point on the manifold to a real number. So, for a two-dimensional manifold, there's an x-coordinate function and a y-coordinate function that respectively tell you the x-coordinate and y-coordinate of a given point. The tuple for point p is then just (x(p), y(p)). The situation for a three-dimensional manifold is similar, you just need a third coordinate function. (Note these functions aren't inherent to the manifold, they are structure added to a manifold and you can, of course, have any number of alternative coordinate systems for the same region of a manifold.)
Each of these coordinate functions is no different than something like temperature or electric potential. They are all scalar fields—continuous real-valued functions on a region of a manifold—that give a real value for every point in that region in a way that if you traveled along a continuous path through the manifold, the value would change continuously.
Now say we wanted to describe how one of these coordinate functions changes as one moved in a particular direction from a particular point on the manifold. Well, we've already seen that
stack-type vectors are about rates of change of some quantity as position changes.
so you can actually think of a coordinate system as defining N stack-type vectors at every point, where N is the number of dimensions of the manifold. Just look at a piece of graph paper and you can see the stack-type vectors. Because the stack-type vectors are showing the rate of change of the coordinate, they are actually the derivative of the coordinate with respect to position (i.e. the gradient).
You can probably already see it, but something interesting happens when we combine the notion of traveling in a particular direction at a particular rate with the notion of a particular quantity (coordinate or otherwise) changing according to position. We'll talk about that next.
by : Created on March 28, 2008 : Last modified March 28, 2008 : (permalink)
In my previous post I mentioned Joyner's paper Mathematics of the Rubik's Cube.
The phrase "The Rubik's Cube" sounds odd because you can't normally use an article with a pre-nominal genitive if the pre-nominal itself wouldn't normally take an article.
You can say "the paper", "the professor" and "the professor's paper". You can say "David's paper" but not "*the David's paper". (Although note that if talking about the sculpture "the David", you can say things like "the David's left hand". And, because of Donald Trump, you could say "the Donald's hair".)
You can't say "the Rubik" and so "the Rubik's cube" seems ungrammatical if you think about its component parts.
What's happening is, of course, that "Rubik's" isn't acting as a genitive anymore but rather "Rubik's Cube" has been reanalyzed as an opaque compound noun. It's just still written in terms of its components.
by : Created on March 27, 2008 : Last modified March 27, 2008 : (permalink)
I've talked about the Rubik's Cube before and linked to last year's paper by Kunkle and Cooperman proving Twenty-Six Moves Suffice for Rubik’s Cube.
Now Tomas Rokicki has proved that Twenty-Five Moves Suffice for Rubik's Cube. Actually, what he proved is that no configuration takes 26. If x <= 26 and x != 26 then x <= 25 QED.
It is known that some configurations need 20 moves and that no configuration needs 21. So the possible optimal move maxima are 20, 22, 23, 24 and 25.
Via Dave Long, I also found out about Joyner's Mathematics of the Rubik's Cube (pdf) which became the book Adventures in Group Theory.
UPDATE: Actually, I don't think it's been proven that no configuration needs 21, just no configuration has been found that needs 21.
UPDATE 2: David Joyner informs me a 2nd edition of his book is coming out soon.
by : Created on March 27, 2008 : Last modified March 28, 2008 : (permalink)
So I was about to blog on the fact that in the last two hours I've read about both Opera and WebKit reaching 98/100 on the Acid 3 Test and that I was wondering who would hit 100/100 first.
Then I saw this ACID3: Strike ninety-eight. Make that 100
Congratulations!
UPDATE: WebKit is the first to make it public, though. Note, neither actually pass the full test yet (which requires pixel-accuracy with a reference image).
by : Created on March 26, 2008 : Last modified March 27, 2008 : (permalink)
The name of Japanese athletic equipment company ASICS is an acronym for the Latin phrase anima sana in corpore sano—"a sound mind in a sound body".
by : Created on March 26, 2008 : Last modified March 26, 2008 : (permalink)
I just was documenting some code that looked (roughly) like this:
def a(x, m): for i, o in enumerate(sorted(x)): if o > m: break return i
and my comment was "return how many items in x are less than or equal to m".
The very act of writing the comment made me realise the code could be rewritten as:
def a(x, m): return len([o for o in x if o <= m])
which is not only more succinct but runs 6-8 times faster! (UPDATE: ...on my data size -- as Sergio points out below, the two algorithms differ in complexity)
(Incidentally, the list comprehension also runs twice as fast as the equivalent using filter)
UPDATE (2008-03-26): Fascinating discussion going on in the comments :-) Although still largely orthogonal to the main point which is that I was originally trying to solve a domain-specific problem and it was only when I went to comment the code that I realised that what I was really doing was trying to find how many items in a list are less than or equal to a certain number. How best to do that is a topic for...well, I guess the comment thread :-)
by : Created on March 25, 2008 : Last modified March 26, 2008 : (permalink)
One of the important takeaways from arrows and stacks as duals is that
Every linear space has a dual space whose elements are the linear, scalar-valued functions on the original space.
These linear, scalar-valued functions have a number of different names. They are variously called linear functionals, linear forms or, more specifically, and as we will call them, one-forms.
For our purposes, the one-forms are real-valued (because our linear spaces are real), although in quantum mechanics I think dual spaces are always made of complex-valued functions (and complex linear spaces).
Let's just quickly demonstrate that the dual space is itself a linear space:
Firstly, by virtue of the fact the one-forms are linear, we know:
We define addition of one-forms:
and scaling of one-forms:
We can see that one-forms do form a linear space, just by the algebraic properties of real number addition and multiplication:
Remember that if we view vectors in the context of a manifold as arrows, the corresponding one-forms are stacks.
In matrix algebra, column vectors and row vectors are similarly duals of one another.
In the next entry, we'll look at the relationship between one-forms and coordinate systems.
by : Created on March 23, 2008 : Last modified March 23, 2008 : (permalink)
Owing to the amount of interest I received about A New Kind of Graded Reader,
I have started a mailing list at
http://groups.google.com/group/graded-reader
and also I plan to make my code available at
http://code.google.com/p/graded-reader/
If you're interested in the idea applied to any language (not just NT Greek) please join us.
by : Created on March 22, 2008 : Last modified March 22, 2008 : (permalink)
Part of the glacial Poinaré Project.
We've introduced the notion of a linear space and seen that, in the context of a manifold, there are at least two distinct types of linear spaces:
Arrow-type linear spaces are about position on the manifold and rates of change of position. Stack-type linear spaces, on the other hand, are about rates of change of some other quantity defined on the manifold as position changes.
These two types of linear spaces have a special relationship to one another. An arrow-type vector and a stack-type vector can be multiplied together to give a quantity which has no reference to distance or direction (what is called a scalar) and which is immune to transformations that maintain the topology of the manifold. Geometrically, you can calculate this quantity by counting how many "stacks" of the stack-type vector the arrow-type vector passes through.
Because this operation of multiplying arrow-type and stack-type vectors doesn't require any additional structures and is preserved under a homeomorphism, is it more fundamental than, say, the inner (or dot) product. As we will see in the next couple of entries, though, it has a relationship to the inner product, mediated through the metric.
We can go one step further and, algebraically, think of a stack-type vector as a function that turns arrow-type vectors into scalars. In other words if V is an arrow-type linear space then a particular stack-type vector w can be thought of as a function w: V -> R. Because the stack-type vectors that apply to the arrow-type vectors in V follow the axioms of linear spaces, the following rules fall out:
Or put more succinctly, w is a linear, real-valued function on V.
Because the linear space of stack-vectors that apply to V has a special relationship to V, it is said to be the dual of V.
It is worth noting that everything above still works if you swap arrows and stacks. In other words, you can view arrow-type vectors as linear, real-valued functions on the linear space of stack-type vectors. The dual relationship is symmetrical. In fact, the only thing that makes one "arrow-type" and the other "stack-type" is their relationship to a manifold.
You can talk about a linear space and its dual without reference to an underlying manifold on which the vectors live. For example, the n-tuple space has a dual as well. For a given linear space of n-tuples, this dual space is the space of all linear, real-valued functions on those n-tuples.
by : Created on March 22, 2008 : Last modified March 22, 2008 : (permalink)
Forte Magazine has a review of Nelson Clemente's EP and had this to say about You Me Us We (which I composed and co-produced):
Aussie boy Nelson Clemente has been impressing blogger types for most of 2007; his ace track "You Me Us We" left a mark on many electronic music fans with its subtle throwbacks to mellow house and 80’s europop. Its gorgeous harmony, solid production and heart-tugging lyrics helped the track along in earning its title as EQ’s Song Of The Year, 2007. Nelson’s debut E.P. "6th Perception" features this pop masterpiece along with several remixes and two new tracks.
and later...
For a first E.P (three tracks, four remixes,) this is a solid start. The perfect and sublime "You Me Us We" is still the best song on here.
Emphasis mine :-)
by : Created on March 21, 2008 : Last modified March 21, 2008 : (permalink)
Special Relativity uses straightforward mathematics with mind-bending physical implications. General Relativity uses mind-bending mathematics with straightforward physical implications.
Or so I described it to someone at PyCon tonight.
by : Created on March 19, 2008 : Last modified March 19, 2008 : (permalink)
Set up directories as follows:
drwxr-xr-x 2 jtauber staff 68 Mar 18 17:57 A drwxr-xr-x 3 jtauber staff 102 Mar 18 17:58 B lrwxr-xr-x 1 jtauber staff 3 Mar 18 17:58 C -> B/C
Now cd into B
jtmbp:TEST jtauber$ cd B
If you try to "execute" A from here, it tells you it's a directory
jtmbp:B jtauber$ ../A -bash: ../A: is a directory
Now go back to the top directory
jtmbp:B jtauber$ cd ..
and cd into C (the symlinked directory)
jtmbp:TEST jtauber$ cd C
If you try to execute A from here, it can't find it via "../A" only "../../A"
jtmbp:C jtauber$ ../A -bash: ../A: No such file or directory jtmbp:C jtauber$ ../../A -bash: ../../A: is a directory
so the attempt at execution is based on the actual absolute path, not the path based on following the symlink.
However,
jtmbp:C jtauber$ cd ../A jtmbp:A jtauber$
So cd uses the path based on following the symlink but relative paths for execution do not.
I realise this is likely because cd is shell-based (and so knows the path that was followed to get to the current directory) whereas execution is a system call (which doesn't know the path that was followed to get to the current directory) but it's interesting nevertheless (and occasionally annoying).
This is on OS X but the behaviour is the same on Linux as far as I know.
by : Created on March 18, 2008 : Last modified March 18, 2008 : (permalink)
I am proud to announce that a couple of hours ago, I was elected to both membership and to the board of directors of the Python Software Foundation. Thank you to David Goodger for nominating me for membership and for encouraging me to run for the board again.
It's a nice coincidence that it happened on Pi Day.
This afternoon at PyCon I'm looking forward to some exciting Django news from Adrian.
Tonight we're running a BOF for anyone interested in mentoring Python projects in the Google Summer of Code.
Note: the last twenty minutes has been the longest I've had a working network connection since I got here :-(
UPDATE: It was actually Jacob that made the announcement. I don't want to steal his blog thunder so I won't mention it here other than to say, it's something I want to help out with :-) Very exciting!
by : Created on March 14, 2008 : Last modified March 14, 2008 : (permalink)
On Wednesday, I'll be heading to Chicago for PyCon. I'm looking forward to catching up with people there and getting a lot of Django hacking done.
by : Created on March 11, 2008 : Last modified March 11, 2008 : (permalink)
I have a song on iTunes!
Previously, I've written about my song You Me Us We which was a finalist in the Unisong International Songwriting Contest and named by ElectroQueer as their Number One Song for 2007.
Well, now Nelson Clemente's debut EP 6th Perception, which features the song, is available on iTunes!
BUY THE ALBUM! Or at least buy the song :-) It's track number 3.
by : Created on March 1, 2008 : Last modified March 1, 2008 : (permalink)