Tuesday, May 31, 2005

Progress Update

For the few people who already know about Noodle and are waiting for the release: It doesn't look like I'll make the expected June 1st date. But over the holiday weekend (and in the course of a road trip to see in-laws in Sacramento) I was able to get a lot of good work done on Noodle.

There were some elusive problems caused by assumptions made by Python bytecodes. See, in Python, the stack is empty between each statement. But in Noodle, everything is an expression, so sometimes there will be things on the stack when they start. Most of the time, this doesn't cause a problem. But with things like Python's CONTINUE_LOOP and BREAK_LOOP, it makes big problems. They both simply wipe out the stack when called.

So, Noodle's continue and break special-operators [1] associated with loops now keep track of the stack state when they are created, and when called, POP_TOP items off the stack to get to that point. They also keep track of exception blocks and pop them off (POP_BLOCK) when appropriate. Finally, loops are implemented without the SETUP_LOOP construct, since it's only useful for making the CONTINUE_LOOP and BREAK_LOOP ops work. So continue and break have to manually jump to the correct place. For all this to work, Noodle needs to keep much stricter track of the exact predicted stacklevel for each individual opcode than it did before. But tightening that up has helped me to find one or two extra bugs that are now fixed. And these changes should make it simple to add support for things like (break 2) or (break-myloop) for breaking out of loops other than the innermost.

Distutils-ization is done, and there are more standard macros, and the Bison/Flex parser and scanner are working wonderfully. Along with that, compilation is faster, the error messages for failed parses and scans are more descriptive, and the lnotabs (line number tables) are much more accurate.

So I'm closer to having Noodle ready for a release (by which I mean, Noodle is almost to the point where I'm not as worried about having everyone mock me when they see it :).

[1] I'm not sure whether continue and break should be considered special operators, since they are defined and put into the macro dict when inside loops, by the special operators for loops. But they are defined in Python and are otherwise just like special operators.

Saturday, May 21, 2005

Practical Common Lisp

I have now had the opportunity to peruse the online pages of Peter Seibel's excellent work, Practical Common Lisp. I'm not quite finished yet, but it's been absolutely perfect for filling in the gaps in my knowledge recently lamented. I recommend it as strongly as I am able to anyone wanting to learn more about Lisp- and I'm not usually one to enjoy or recommend books on technical topics. I may even take the unusual step of buying the dead-tree edition. Thanks, Mr. Seibel.

Tuesday, May 17, 2005

Anonymous blocks (PEP 340)

PEP (Python Enhancement Proposal) 340 suggests adding a new block construct to the Python language which would "provide a mechanism for encapsulating patterns of structure". I don't understand the details of the whole proposal just yet, but it looks like the point is making it simpler to execute a blocks of code between other steps, without having to put all the other steps into the code individually. For example, from the PEP, a way to execute some commands while a file is open and guarantee it will be closed when done:
def opening(filename, mode="r"):
f = open(filename, mode)
yield f

Used as follows:
block opening("/etc/passwd") as f:
for line in f:
print line.rstrip()

Or to retry something several times:
def auto_retry(n=3, exc=Exception):
for i in range(n):
yield None
except exc, err:
# perhaps log exception here
raise # re-raise the exception we caught earlier

Used as follows:
block auto_retry(3, IOError):
f = urllib.urlopen("http://python.org/peps/pep-0340.html")
print f.read()

This seems to me to be trying to solve a problem long ago solved by Lisp's macros, which coincidentally also solve a plethora of other problems unaddressed by the proposed block facility. I'm happy to say Noodle should never need block. (Of course, if a programmer does need it, she can implement it as a macro pretty quickly!)

I see more and more how the capability of extending Lisp's syntax has made it so powerful and so capable of remaining competetive after being around for 50 years.

Wednesday, May 11, 2005

Todo list

The list of items to be completed in Noodle before the public alpha release (at 0.1.0) is continuing to dwindle. Some of the bigger items currently there include:

  • Sufficient documentation for easy learning and usage of Noodle

  • Larger suite of acceptance tests

  • Rewrite parser (and possibly scanner as well) to be in C, using bison or PyBison. Bison is much more powerful, faster, etc., makes it simpler to define and handle error conditions, and won't require GPL code to be distributed with Noodle as does PLY. (I plan to release Noodle under an MIT/X11-style license)

  • Errors from scanner should indicate position in text

  • Class docstrings

  • Disallow some code arrangements that will make the Python VM upset-

    • No using unqualified 'exec' when there are any cell or free variables

    • No using import-all-from (like "from foo import *") except at the module level

  • Macro called get-module which will be used to implement "import foo as bar" functionality

  • Conditionals in for loops (including list comprehensions and generator expressions): (for (foo in bar if baz) do-something)

  • Consider adding syntax for what I call Python's multidimensional for loops (no idea what they're really called): i.e.,
    [t for foo in bar for t in foo]

  • Function argument unpacking, as when a function is declared with tuples in the argument list: i.e.,
    (define (my-function foo (bar (baz bonk) boom))

  • Define builtin functions to complement certain builtin macros; especially those which might be useful to pass to map, filter, etc, or might need to accept *varargs arguments. For example, the + macro.

  • Fix a bug with nested quasiquote calls

  • Add a syntax for the functionality offered by Python's print chevron

  • Tweaks to the Vim syntax-highlighting definition

Most of these are fairly simple and won't take much time. Of course everything depends on available time, but I'm planning on an initial public release June 1st.

Friday, May 06, 2005


I found the Python Challenge a couple days ago and haven't been able to do any work on Noodle as a result. The puzzles are much too engaging! Hard, too. I've just started on #16, and I don't know how many more there are, but hopefully I run out soon, because when the problems are right there waiting to be solved, I can't ignore them!

I have a suspicion it was put up by Perl enthusiasts (or maybe PHP) to distract the Python programmers and cut down on development and maintenance time.

Monday, May 02, 2005

Release approved

I met with Novell's Open Source Review Board to make sure the Noodle code was in the clear. The process may not have been completely necessary, but I wanted to be safe down the road, just in case. Most likely simply paranoia.

So Noodle is now approved for release. The existing code will have a "Copyright (C) 2005 by Novell, Inc." added but I've got it under the MIT license, so that doesn't bother me at all. I'm glad to see Novell's name on free software projects anyway.

The existing code uses yacc.py from the PLY project, as I may have mentioned before, and that's under the GPL. So the whole package as it currently exists is only distributable under the GPL. I'm planning to replace yacc.py with a PyBison parser before too long, so the impending public alpha release of Noodle may be GPL'd, or it may be under the MIT license.

Tail recursion

Noodle can now do limited tail call optimization. Only the tail recursion case is optimized in this way. That is, when a function calls itself and immediately returns the result of that call, Noodle can transform the bytecode so that the new function call doesn't take up any extra stack space. The initial function's stack space is no longer needed, once the arguments to the function call are computed, so there's no reason to keep it there. This is accomplished by transforming the function call into a series of assignments, one for each input variable, and simply jumping to the top of the function again.

The most difficult part of this is not the transformation- it's determining under which cases those steps are actually valid. When the tail-recursive call uses keyword arguments or varargs (*) or kwargs (**), for example, it's trickier to come up with valid bytecode to correctly reinitialize the function. Default arguments cause another problem, since a code object has no way of knowing which default arguments are attached to it in a containing function object.

So the current requirements for taking advantage of Noodle's tail call optimization are thus:

  • Tail call must be at the end of the function, in addition to being in a tail position (this restriction is expected to go away at some point)

  • Tail call must be to the current function, by the same name

  • Tail call must give arguments for all positional parameters and all default parameters, in order, and must not give any keyword arguments, varargs, or kwargs.

When you're writing a recursive function, these restrictions should in general be rather simple to get around.

I don't expect Noodle will be able to support any further tail call optimization, since Python bytecode is currently incapable of jumping between code objects. Jumping can only be done to elsewhere in the current code object.