In Haskell, you can section infix operators. This is a simple form of partial evaluation. Using Python syntax, the following are equivalent:
    (2*)
    lambda x: 2*x

    (*2)
    lambda x: x*2

    (*)
    lambda x, y: x*y
So, can we do the same in Python?

Grammar

The first form, (2*), is unambiguous. There is no place in Python where an operator can be legally followed by a close-paren. That works for every binary operator, including boolean and comparison operators. But the grammar is a bit tricky. Without lookahead, how do you make sure that a '(' followed by an expr followed by a binary operator followed by a ')' doesn't start parsing as just a parenthesized expression? I couldn't find a way to make this ambiguous without manually hacking up ast.c. (If you're willing to do that, it's not hard, but you shouldn't be willing to do that.)

The second form, (*2) looks a lot simpler--no lookahead problems. But consider (-2). That's already legal Python! So, does that mean you can't section the + and - operators?

The third form, (*) is the simplest. But it's really tempting to want to be able to do the same with unary operators. Why shouldn't I be able to pass (~) or (not) around as a function instead of having to use operator.not_ and operator.neg? And of course that brings us right back to the problem with + and - being ambiguous. (Plus, it makes the compile step a little harder. But that's not a huge deal.)

I solved these problems using a horrible hack: sectioned operators are enclosed in parens and colons. This looks hideous, but it did let me get things building so I can play with the idea. Now there's no lookahead needed—a colon inside parens isn't valid for anything else (unless you want to be compatible with my bare lambda hack…). And to resolve the +/- issue, only the binary operators can be sectioned, which also means (: -3* :) is a SyntaxError instead of meaning lambda x: -3 * x. Ick. But, again, it's good enough to play with it.

The key grammar change looks like this:
    atom: ('(' [yield_expr|testlist_comp] ')' |
           '(' ':' sectionable_unop ':' ')' |
           '(' ':' sectionable_binop ':' ')' |
           '(' ':' expr sectionable_binop ':' ')' |
           '(' ':' sectionable_binop expr ':' ')' |
           '[' [testlist_comp] ']' |
           '{' [dictorsetmaker] '}' |
           NAME | NUMBER | STRING+ | '...' | 'None' | 'True' | 'False')

What about precedence?

Ignored. It only matters if you want to be able to section expressions made up of multiple operators, like (2+3*). Which I don't think you do. For non-trivial cases, there are no readability gains for operator sectioning, and having to think about precedence actually might be a readability cost. If you still don't want to use lambda, do what you'd do in Haskell and compose (2+) with (3*).

AST

For the AST, each of those four productions creates a different node type. Except that you _also_ need separate node types for normal binary operators, comparison operators, and boolean operators, because they have different enums for their operators. So I ended up with 10 new types: UnOpSect, BinOpSect, BinOpSectRight, and BinOpSectLeft, CmpOpSect, etc. There's probably a better way to do this.

Symbol table

How do you deal with an anonymous argument in the symbol table for the function we're going to generate? You don't want to have to create a whole args structure just to insert a name just so you can refer to it in the compiler. Plus, whatever name you pick could collide with a name in the parent scope, hiding it from a lambda or a comprehension that you define inside the expr. (Why would you ever do that? Who knows, but it's legal.)

This problem must have already been solved. After all, generator expressions have created hidden functions that don't collide any names in the outer scope since they were first created, and in 3.x all comprehensions do that. It's a little tricky to actually get at these hidden functions, but here's one way to do it:
    >>> def f(): (i for i in [])
    >>> f.__code__.co_consts
    (None, <code object <genexpr> at 0x10bc57a50, file "<stdin>", line 1>, 'z.<locals>.<genexpr>')
    >>> f.__code__.co_consts[1].co_varnames
    ('.0', 'i')
So, the parameter is named .0 which isn't legal in a def or lambda and can't be referenced. Clever. And once you dig into symtable.c, you can see that this is handled in a function named symtable_implicit_arg. So:
        VISIT(st, expr, e->v.BinOpSectLeft.right);
 if (!symtable_enter_block(st, binopsect,
      FunctionBlock, (void *)e, e->lineno,
      e->col_offset))
     VISIT_QUIT(st, 0);
 if (!symtable_implicit_arg(st, 0))
            VISIT_QUIT(st, 0);
        if (!symtable_exit_block(st, (void *)e))
            VISIT_QUIT(st, 0); 

Compiler

The compilation works similar to lambda. Other than sprintf'ing up a nice name instead of just <lambda>, and the fact that everything is simpler when there's exactly one argument with no defaults and no keywords, everything is the same except the body, which looks like this:
    ADDOP_I_IN_SCOPE(c, LOAD_FAST, 0);
    VISIT_IN_SCOPE(c, expr, e->v.BinOpSectLeft.right);
    ADDOP_IN_SCOPE(c, binop(c, e->v.BinOpSectLeft.op));
    ADDOP_IN_SCOPE(c, RETURN_VALUE);
    co = assemble(c, 1);
I did have to create that ADDOP_I_IN_SCOPE macro, but that's trivial.

Does it work?

    >>> (: *2 :)
    <function <2> at 0x10bc9f048>
    >>> (: *2 :).__code__.co_varnames
    ('.0',)
    >>> (: *2 :)(23)
    46
As you can see, I screwed up the name a bit.

More importantly, I screwed up nonlocal references in the symtable. I think I need to visit the argument? Anyway, what happens is this:
    >>> a = 23
    >>> (: *a :)(23)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "<stdin>", line 1, in <a>
    SystemError: no locals when loading 'a'
But that's much better than the segfault I expected. :)

Is it useful?

Really, most of the obvious use cases for this are already handled by bound methods, like spam.__add__ instead of (spam+), and the operator module, like operator.add instead of (+). Is that perfect? No:
  • spam.__add__ isn't as flexible as (spam+), because the latter will automatically handle calling its argument's __radd__ when appropriate.
  • Often, you want to section with literals. Especially with integers. But 0.__add__ is ambiguous between a method on an integer literal or a float literal followed by garbage, and therefore a SyntaxError, so you need 0 .__add__ or (0).__add__.
  • For right-sectioning, spam.__radd__ to mean (+spam) isn't so bad, but spam.__gt__ to mean (<spam) is a bit less readable.
Still, it's hard to find a non-toy example where (<0) is all that useful. Most examples I look at, what I really want is something like lambda x: x.attr < 0. In Haskell I'd probably write that by the rough equivalent of composing operator.attrgetter('attr') with (<0). But, even if you pretend that attribution is an operator (even though it isn't) and add sectioning syntax for it, and you use the @ operator for compose (as was proposed and rejected at least twice during the PEP 465 process and at least once since…), the best you can get is (<0) @ (.attr) which still doesn't look nearly as readable to me in Python as the lambda.

And, without a compelling use case, I'm not sure it's worth spending more time debugging this, or trying to think of a clever way to make it work without the colons and without lookahead, or coming up with a disambiguating rule for +/-. (It's obviously never going to make it into core…)

Anything else worth learning here?

When I was having problems getting the symbol table set up (which I still didn't get right…), I realized there's another way to tackle this: Just stop at the AST, which is the easy part. The result, when run normally, is that any operator-sectioning expression resolves to an empty tuple, which doesn't seem all that useful… but you've got an AST node that you can transform with, say, MacroPy. And converting the meaningless AST node into a valid lambda node in Python is a lot easier to building the symbol table and bytecodes in C. Plus, you don't have to rebuild Python every time you make a change.

I don't think this is an argument for adding do-nothing AST structures to the core, of course… but as a strategy for hacking on Python, I may start with that next time around.
1

View comments

  1. This comment has been removed by a blog administrator.

    ReplyDelete
Hybrid Programming
Hybrid Programming
5
Greenlets vs. explicit coroutines
Greenlets vs. explicit coroutines
6
ABCs: What are they good for?
ABCs: What are they good for?
1
A standard assembly format for Python bytecode
A standard assembly format for Python bytecode
6
Unified call syntax
Unified call syntax
8
Why heapq isn't a type
Why heapq isn't a type
1
Unpacked Bytecode
Unpacked Bytecode
3
Everything is dynamic
Everything is dynamic
1
Wordcode
Wordcode
1
For-each loops should define a new variable
For-each loops should define a new variable
4
Views instead of iterators
Views instead of iterators
2
How lookup _could_ work
How lookup _could_ work
2
How lookup works
How lookup works
7
How functions work
How functions work
2
Why you can't have exact decimal math
Why you can't have exact decimal math
2
Can you customize method resolution order?
Can you customize method resolution order?
1
Prototype inheritance is inheritance
Prototype inheritance is inheritance
1
Pattern matching again
Pattern matching again
The best collections library design?
The best collections library design?
1
Leaks into the Enclosing Scope
Leaks into the Enclosing Scope
2
Iterable Terminology
Iterable Terminology
8
Creating a new sequence type is easy
Creating a new sequence type is easy
2
Going faster with NumPy
Going faster with NumPy
2
Why isn't asyncio too slow?
Why isn't asyncio too slow?
Hacking Python without hacking Python
Hacking Python without hacking Python
1
How to detect a valid integer literal
How to detect a valid integer literal
2
Operator sectioning for Python
Operator sectioning for Python
1
If you don't like exceptions, you don't like Python
If you don't like exceptions, you don't like Python
2
Spam, spam, spam, gouda, spam, and tulips
Spam, spam, spam, gouda, spam, and tulips
And now for something completely stupid…
And now for something completely stupid…
How not to overuse lambda
How not to overuse lambda
1
Why following idioms matters
Why following idioms matters
1
Cloning generators
Cloning generators
5
What belongs in the stdlib?
What belongs in the stdlib?
3
Augmented Assignments (a += b)
Augmented Assignments (a += b)
11
Statements and Expressions
Statements and Expressions
3
An Abbreviated Table of binary64 Values
An Abbreviated Table of binary64 Values
1
IEEE Floats and Python
IEEE Floats and Python
Subtyping and Ducks
Subtyping and Ducks
1
Greenlets, threads, and processes
Greenlets, threads, and processes
6
Why don't you want getters and setters?
Why don't you want getters and setters?
8
The (Updated) Truth About Unicode in Python
The (Updated) Truth About Unicode in Python
1
How do I make a recursive function iterative?
How do I make a recursive function iterative?
1
Sockets and multiprocessing
Sockets and multiprocessing
Micro-optimization and Python
Micro-optimization and Python
3
Why does my 100MB file take 1GB of memory?
Why does my 100MB file take 1GB of memory?
1
How to edit a file in-place
How to edit a file in-place
ADTs for Python
ADTs for Python
5
A pattern-matching case statement for Python
A pattern-matching case statement for Python
2
How strongly typed is Python?
How strongly typed is Python?
How do comprehensions work?
How do comprehensions work?
1
Reverse dictionary lookup and more, on beyond z
Reverse dictionary lookup and more, on beyond z
2
How to handle exceptions
How to handle exceptions
2
Three ways to read files
Three ways to read files
2
Lazy Python lists
Lazy Python lists
2
Lazy cons lists
Lazy cons lists
1
Lazy tuple unpacking
Lazy tuple unpacking
3
Getting atomic writes right
Getting atomic writes right
Suites, scopes, and lifetimes
Suites, scopes, and lifetimes
1
Swift-style map and filter views
Swift-style map and filter views
1
Inline (bytecode) assembly
Inline (bytecode) assembly
Why Python (or any decent language) doesn't need blocks
Why Python (or any decent language) doesn't need blocks
18
SortedContainers
SortedContainers
1
Fixing lambda
Fixing lambda
2
Arguments and parameters, under the covers
Arguments and parameters, under the covers
pip, extension modules, and distro packages
pip, extension modules, and distro packages
Python doesn't have encapsulation?
Python doesn't have encapsulation?
3
Grouping into runs of adjacent values
Grouping into runs of adjacent values
dbm: not just for Unix
dbm: not just for Unix
How to use your self
How to use your self
1
Tkinter validation
Tkinter validation
7
What's the deal with ttk.Frame.__init__(self, parent)
What's the deal with ttk.Frame.__init__(self, parent)
1
Does Python pass by value, or by reference?
Does Python pass by value, or by reference?
9
"if not exists" definitions
"if not exists" definitions
repr + eval = bad idea
repr + eval = bad idea
1
Solving callbacks for Python GUIs
Solving callbacks for Python GUIs
Why your GUI app freezes
Why your GUI app freezes
21
Using python.org binary installations with Xcode 5
Using python.org binary installations with Xcode 5
defaultdict vs. setdefault
defaultdict vs. setdefault
1
Lazy restartable iteration
Lazy restartable iteration
2
Arguments and parameters
Arguments and parameters
3
How grouper works
How grouper works
1
Comprehensions vs. map
Comprehensions vs. map
2
Basic thread pools
Basic thread pools
Sorted collections in the stdlib
Sorted collections in the stdlib
4
Mac environment variables
Mac environment variables
Syntactic takewhile?
Syntactic takewhile?
4
Can you optimize list(genexp)
Can you optimize list(genexp)
MISRA-C and Python
MISRA-C and Python
1
How to split your program in two
How to split your program in two
How methods work
How methods work
3
readlines considered silly
readlines considered silly
6
Comprehensions for dummies
Comprehensions for dummies
Sockets are byte streams, not message streams
Sockets are byte streams, not message streams
9
Why you don't want to dynamically create variables
Why you don't want to dynamically create variables
7
Why eval/exec is bad
Why eval/exec is bad
Iterator Pipelines
Iterator Pipelines
2
Why are non-mutating algorithms simpler to write in Python?
Why are non-mutating algorithms simpler to write in Python?
2
Sticking with Apple's Python 2.7
Sticking with Apple's Python 2.7
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.