473,289 Members | 1,963 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,289 software developers and data experts.

Lazy evaluation: overloading the assignment operator?


Python allows the binding behaviour to be defined for descriptors,
using the __set__ and __get__ methods. I think it would be a major
advantage if this could be generalized to any object, by allowing the
assignment operator (=) to be overloaded.

One particular use for this would be to implement "lazy evaluation".
For example it would allow us to get rid of all the temporary arrays
produced by NumPy.

For example, consider the expression:

y = a * b + c * d

If this expression is evaluated bya Fortran 90/95 compiler, it will
automatically generate code like

do i = 1,n
y(i) = a(i) * b(i) + c(i) * d(i)
enddo

On the other hand, conventional use of overloaded binary operators
would result in something like this:

allocate(tmp1,n)
do i = 1,n
tmp1(i) = a(i) * b(i)
enddo
allocate(tmp2,n)
do i = 1,n
tmp2(i) = c(i) * d(i)
enddo
allocate(tmp3,n)
do i = 1,n
tmp3(i) = tmp1(i) + tmp2(i)
enddo
deallocate(tmp1)
deallocate(tmp2)
do i = 1,n
y(i) = tmp3(i)
enddo
deallocate(tmp3)

Traversing memory is one of the most expensive thing a CPU can do.
This approach is therefore extremely inefficient compared with what a
Fortran compiler can do.

However, if we could overload the assignment operator, there would be
an efficient solution to this problem. Instead of constructing
temporary temporary arrays, one could replace those with objects
containing lazy expressions "to be evaluated sometime in the future".
A statement like

y = a * b + c * d

would then result in something like this:

tmp1 = LazyExpr('__mul__',a,b) # symbolic representation of "a * b"
tmp2 = LazyExpr('__mul__',c,d) # symbolic representation of "c * d"
tmp3 = LazyExpr('__add__',tmp1,tmp1) # symbolic "a * b + c * d"
del tmp1
del tmp2
y = tmp3 # tmp3 gets evaluated as assignment is overloaded
Should there be a PEP to overload the assignment operator? In terms of
syntax, it would not be any worse than the current descriptor objects
- but it would make lazy evaluation idioms a lot easier to implement.

Sturla Molden

May 2 '07 #1
9 3451
sturlamolden wrote:
Python allows the binding behaviour to be defined for descriptors,
using the __set__ and __get__ methods.
AFAIK, __getattribute__ calls them *explicitly*.
I think it would be a major
advantage if this could be generalized to any object, by allowing the
assignment operator (=) to be overloaded.
>
One particular use for this would be to implement "lazy evaluation".
For example it would allow us to get rid of all the temporary arrays
produced by NumPy.

For example, consider the expression:
[snip]
>
y = a * b + c * d

would then result in something like this:

tmp1 = LazyExpr('__mul__',a,b) # symbolic representation of "a * b"
tmp2 = LazyExpr('__mul__',c,d) # symbolic representation of "c * d"
tmp3 = LazyExpr('__add__',tmp1,tmp1) # symbolic "a * b + c * d"
del tmp1
del tmp2
y = tmp3 # tmp3 gets evaluated as assignment is overloaded
To allow lazy evaluation, you need overloading of the assignment
operator? Where should you overload it? y is less than None when you do
that assignment. I don't really see the need for overloading here.
Following the binding rules, __mul__ would (even without any hackery) be
evaluated before __add__.
>
Should there be a PEP to overload the assignment operator?
If -- after this discussion -- community seems to like this feature, you
could try to come up with some patch and a PEP. But not yet.
In terms of
syntax, it would not be any worse than the current descriptor objects
- but it would make lazy evaluation idioms a lot easier to implement.
--
Stargaming
May 2 '07 #2
sturlamolden schrieb:
Python allows the binding behaviour to be defined for descriptors,
using the __set__ and __get__ methods. I think it would be a major
advantage if this could be generalized to any object, by allowing the
assignment operator (=) to be overloaded.

One particular use for this would be to implement "lazy evaluation".
For example it would allow us to get rid of all the temporary arrays
produced by NumPy.

For example, consider the expression:

y = a * b + c * d

If this expression is evaluated bya Fortran 90/95 compiler, it will
automatically generate code like

do i = 1,n
y(i) = a(i) * b(i) + c(i) * d(i)
enddo

On the other hand, conventional use of overloaded binary operators
would result in something like this:

allocate(tmp1,n)
do i = 1,n
tmp1(i) = a(i) * b(i)
enddo
allocate(tmp2,n)
do i = 1,n
tmp2(i) = c(i) * d(i)
enddo
allocate(tmp3,n)
do i = 1,n
tmp3(i) = tmp1(i) + tmp2(i)
enddo
deallocate(tmp1)
deallocate(tmp2)
do i = 1,n
y(i) = tmp3(i)
enddo
deallocate(tmp3)

Traversing memory is one of the most expensive thing a CPU can do.
This approach is therefore extremely inefficient compared with what a
Fortran compiler can do.
I fail to see where laziness has anything to do with this. In C++, this
problem can be remedied with the so called temporary base class idiom.

But this has nothing to do with laziness, which does not reduce the
amount of code to execute, but instead defers the point of execution of
that code.

And AFAIK the general overhead of laziness versus eager evaluation does
not pay off - haskell is a tad slower than e.g. an ML dialect AFAIK.

Diez
May 2 '07 #3
On May 2, 9:46 pm, Stargaming <stargam...@gmail.comwrote:
del tmp2
y = tmp3 # tmp3 gets evaluated as assignment is overloaded

To allow lazy evaluation, you need overloading of the assignment
operator?
No I don't. I could for example delay evaluation until some data from
y is requested, say when

x = y[5]

is executed. However, that can allow mutual dependencies between
unevaluated expressions. These can be complicated to resolve, and is
an issue similar to to that of cyclic dependencies in reference
counting. With an overloaded assignment operator, we would avoid this
as assignments are natural places to flush lazy evaluations. No
dangling unevaluated expression would be produced, and thus there
would be no strange bugs of this sort.

Where should you overload it? y is less than None when you do
that assignment.
In this case, I am not suggesting overloading

y =

but rather overloading

= tmp3

That is, when a variable is bound to an object, a method is called
(e.g. __get__) and the variable gets the return value output from that
function instead. It is analogous to the __get__ method of
descriptors. COnsider happens when we call

a = someObject.someProperty

and someProperty has a __get__ method. Even if a is less than None, we
still get a call to __get__.

On the other hand, if y had been bound to a value before hand, it
would be meaningful to call a method called __set__ on y when

y = tmp3

is executed. Just like

someObject.someProperty = value

would call __set__ on someProperty if it had one. Obviously if
someObject.someProperty had been unbound, there would have been no
call to __set__.

So I am suggesting generalising __set__ and __get__ to overload the
assignment operator.

This would be an example:
class Foo(object):

def __init__(self):
self.value = None

def __set__(self,value):
''' overloads bar = value after bar = Foo()'''
self.value = value

def __get__(self):
''' overloads obj = bar after bar = Foo()'''
return self.value
So it is just a generalization of the already existing descriptors. It
even makes descriptors and properties easier to understand.

I don't really see the need for overloading here.
Following the binding rules, __mul__ would (even without any hackery) be
evaluated before __add__.
Yes, but at the cost of generating several temporary arrays and
looping over the same memory several times. If the assignment operator
could be overloaded, we could avoid the temporary objects and only
have one loop. For numerical code, this can mean speed ups in the
order of several magnitudes.

Sturla Molden




>
Should there be a PEP to overload the assignment operator?

If -- after this discussion -- community seems to like this feature, you
could try to come up with some patch and a PEP. But not yet.
In terms of
syntax, it would not be any worse than the current descriptor objects
- but it would make lazy evaluation idioms a lot easier to implement.

--
Stargaming

May 2 '07 #4
On May 2, 11:08 pm, "Diez B. Roggisch" <d...@nospam.web.dewrote:
And AFAIK the general overhead of laziness versus eager evaluation does
not pay off - haskell is a tad slower than e.g. an ML dialect AFAIK.
In the numerical Python community there is already a prototype
compiler called 'numexpr' which can provide efficient evaluation of
expressions like y = a*b + c*d. But as long as there is no way of
overloading an assignment, it cannot be seamlessly integrated in an
array framework. One will e.g. have to type up Python expressions as
strings and calling eval() on the string instead of working directly
with Python expressions.

In numerical work we all know how Fortran compares with C++. Fortran
knows about arrays and can generate efficient code. C++ doesn't and
have to resort to temporaries returned from overloaded operators. The
only case where C++ can compare to Fortran is libraries like Blitz++,
where for small fixes-sized arrays the temporary objects and loops can
be removed using template meta-programming and optimizing compilers.
NumPy has to generate a lot of temporary arrays and traverse memory
more than necessary. This is a tremendous slow down when arrays are
too large to fit in the CPU cache. Numexpr deals with this, but Python
cannot integrate it seamlessly. I think it is really a matter of what
you are trying to do. Some times lazy evaluation pays off, some times
it doesn't.

But overloaded assignment operators have more use than lazy
evaluation. It can be used and abused in numerous ways. For example
one can have classes where every assignment results in the creation of
a copy, which may seem to totally change the semantics of Python code
(except that it doesn't, it's just an illusion).
Sturla Molden

May 2 '07 #5

"sturlamolden" <st**********@yahoo.nowrote in message
news:11**********************@n76g2000hsh.googlegr oups.com...
|
| Python allows the binding behaviour to be defined for descriptors,
| using the __set__ and __get__ methods. I think it would be a major
| advantage if this could be generalized to any object, by allowing the
| assignment operator (=) to be overloaded.

Conceptually, assignment is *not* an operator. Binary operators take two
values (of the same type) and produce a third (usually of either the input
type or a boolean) that usually depends on both inputs. Assignment does
nothing of the sort.

In Python, the equal sign is *not* an operator: it is a grammatical symbol.
One use of the operator fiction in C is to enable simple chained
assignment: a=b=2. Python does this directly without the fiction. C's
store-and-test usage can be implemented in Python with a 'purse' class.

| One particular use for this would be to implement "lazy evaluation".

Since (in Python, at least) operands are evaluated *before* the
operator/function is called, I do not see how.

| Should there be a PEP to overload the assignment operator?

You mean a PEP to make assignment an (pseudo)operation and hence
overloadable (as all operators are). That has been proposed and rejected
before, more than once, but I don't have a reference handy.

Terry Jan Reedy

May 3 '07 #6
Diez B. Roggisch wrote:
I fail to see where laziness has anything to do with this.
In C++, this problem can be remedied with the so called
temporary base class idiom.
I have seen this referred to as lazy evaluation in C++,
so I suspect that Diez and Sturia are using "Lazy evaluation"
in different contexts with different meaning.
But this has nothing to do with laziness, which does not
reduce the amount of code to execute, but instead defers the
point of execution of that code.
But that is precisely what Sturia is suggesting, defer
(for a few nanoseconds) the evaluation of the multiplications
and addition until the assignment occurs. Admittedly a big
difference to the lazy evaluation implied by python's yield
statement, but still a version of lazy evaluation and (at
least sometimes) referred to as such in a C++ context.

I am a python newbie (about one month) but I think
some of what Sturia wants could be achieved by partially
following what is usually done in C++ to achieve what he
wants. It would involve a replacement array class (possibly
derived from NumPy's arrays) and a proxy class.

+ Addition, multiplication, etc of arrays and proxy
arrays does not return the result array, but returns
a proxy which stores the arguments and the
operation.

+ Array indexing of the proxy objects results in
the indexing methods of the arguments being
called and the operation being carried out and
returned. In C++ this is normally very efficient
as the operations are all defined inline and
expanded by the compiler.

+ If necessary, define an additional method to evaluate
the entire array and return it.

I think this would allow code like (if the new array type is
XArray)

a = Xarray(...)
b = Xarray(...)
c = Xarray(...)
d = Xarray(...)

y = a*b+c*d # Returns a proxy object

x = y[4] # Computes x = a[4]*b[4] + c[4]*d[4]

v = y.eval() # Evaluates all elements, returning Xarray

z = ((a+b)*(c+d)).eval() # Also evaluates all elements

Whether it would be any faster is doubtful, but it would eliminate
the temporaries.

Charles
May 3 '07 #7
On 2007-05-03, Terry Reedy <tj*****@udel.eduwrote:
>
"sturlamolden" <st**********@yahoo.nowrote in message
news:11**********************@n76g2000hsh.googlegr oups.com...
|
| Python allows the binding behaviour to be defined for descriptors,
| using the __set__ and __get__ methods. I think it would be a major
| advantage if this could be generalized to any object, by allowing the
| assignment operator (=) to be overloaded.

Conceptually, assignment is *not* an operator. Binary operators take two
values (of the same type) and produce a third (usually of either the input
type or a boolean) that usually depends on both inputs. Assignment does
nothing of the sort.

In Python, the equal sign is *not* an operator: it is a grammatical symbol.
One use of the operator fiction in C is to enable simple chained
assignment: a=b=2. Python does this directly without the fiction. C's
store-and-test usage can be implemented in Python with a 'purse' class.

| One particular use for this would be to implement "lazy evaluation".

Since (in Python, at least) operands are evaluated *before* the
operator/function is called, I do not see how.
But they could evaluate to an expression tree instead of the actual
result. This tree could then be evaluate at the moment of assignment.

This is an idea I have been playing with myself in an other context.
You have a class of symbolic names. e.g. First, Last ... You can use
the normal operators to these names, the result will be an expression
tree. So Last - 2 will evaluate to something like

sub
/ \
Last 2

I want to use this in the context of a table (a list like structure
but with arbitrary start index, which can be negative, so tab[-1]
can't refer to the last element).

So I can use this as follows:

el = tab[Last - 2]

to access the element two places before the last, because the evaluation
of the tree happens in the __getitem__ method.

I could even write something like:

el = tab[(First + Last) / 2]

To get at the midle element.

--
Antoon Pardon
May 3 '07 #8
On May 3, 6:22 am, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
wrote:
y = a*b+c*d # Returns a proxy object

x = y[4] # Computes x = a[4]*b[4] + c[4]*d[4]

v = y.eval() # Evaluates all elements, returning Xarray

z = ((a+b)*(c+d)).eval() # Also evaluates all elements
When I suggested this on the NumPy mailing list, I too suggested using
the indexing operator to trigger the computations. But I am worried
that if an expression like

y = a*b+c*d

returns a proxy, it is somehow possible to mess things up by creating
cyclically dependent proxies. I may be wrong about this, in which case
__getitem__ et al. will do the job.

Whether it would be any faster is doubtful, but it would eliminate
the temporaries.
The Numexpr compiler in SciPy suggests that it can. It parses an
expression like 'y = a*b+c*d' and evaluates it. Numexpr is only a
slow prototype written in pure Python, but still it can sometimes give
dramatical speed-ups. Here we do not even need all the machinery of
Numexpr, as Python creates the parse tree on the fly.

Inefficiency of binary operators that return temporary arrays is
mainly an issue when the arrays in the expression is too large to fit
in cache. RAM access can be very expensive, but cache access is
usually quite cheap. One also avoids unnecessary allocation and
deallocation of buffers to hold temporary arrays. Again, it is mainly
an issue when arrays are large, as malloc and free can be rather
efficient for small objects.


May 3 '07 #9
On 2007-05-03, sturlamolden <st**********@yahoo.nowrote:
On May 3, 6:22 am, Charles Sanders <C.delete_this.Sand...@BoM.GOv.AU>
wrote:
> y = a*b+c*d # Returns a proxy object

x = y[4] # Computes x = a[4]*b[4] + c[4]*d[4]

v = y.eval() # Evaluates all elements, returning Xarray

z = ((a+b)*(c+d)).eval() # Also evaluates all elements

When I suggested this on the NumPy mailing list, I too suggested using
the indexing operator to trigger the computations. But I am worried
that if an expression like

y = a*b+c*d

returns a proxy, it is somehow possible to mess things up by creating
cyclically dependent proxies. I may be wrong about this, in which case
__getitem__ et al. will do the job.
How do you expect to handle the following kind of situation:

while <condition>:
x = y
a = ...
b = ...
y = a * x + b

--
Antoon Pardon
May 3 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

25
by: Steven Bethard | last post by:
So I end up writing code like this a fair bit: map = {} for key, value in sequence: map.setdefault(key, ).append(value) This code basically constructs a one-to-many mapping -- each value that...
3
by: jim.brown | last post by:
The attached code implements a test class to show an error in overloading operator=. This code works on Windows with Visual Studio and simpler cases work with gcc 3.3.2 on Solaris 9. On Windows,...
77
by: berns | last post by:
Hi All, A coworker and I have been debating the 'correct' expectation of evaluation for the phrase a = b = c. Two different versions of GCC ended up compiling this as b = c; a = b and the other...
12
by: Achim Domma | last post by:
Hi, I want to use Python to script some formulas in my application. The user should be able to write something like A = B * C where A,B,C are instances of some wrapper classes. Overloading...
22
by: clicwar | last post by:
A simple program with operator overloading and copy constructor: #include <iostream> #include <string> using namespace std; class Vector { private: float x,y; public: Vector(float u, float...
3
by: Philipp Brune | last post by:
Hi all, i just played around a little with the c# operator overloading features and an idea came to my mind. You all possibly know the Nullable<T> Datatype. Now i thought it would be a nice idea...
8
by: Wayne Shu | last post by:
Hi everyone, I am reading B.S. 's TC++PL (special edition). When I read chapter 11 Operator Overloading, I have two questions. 1. In subsection 11.2.2 paragraph 1, B.S. wrote "In particular,...
39
by: Boltar | last post by:
Why does C do lazy evaluation for logical boolean operations but not bitwise ones? Ie: the following program prints "1 2" , not "1 1" under gcc main() { int a = 1; int b = 1; 0 && ++a;
6
by: Peng Yu | last post by:
Hi, I'm wondering if the following assignment is lazy copy or not? Thanks, Peng std::vector<intv. v.push_back(1); v.push_back(2);
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.