YES, this is another 'I would like this and that'-posting, but I
recently
wondered why Python has map(), filter() and reduce() - already very nice
gadgets - but nothing like \exists or \forall - quantors. They can
easily
be implemented with eval() and dynamic programming, but having them
builtin
would be a VERY NICE THING, especially if your programming prototype
algorithms with mathematical background. These would then look very much
like,
what you normally see in papers (with only small modifications).
Now as Python is a state-of-the-art programming language, I propose the
following syntax:
if forall x in list: has_property(x): do_something(list)
and
if exists x in list: has_property(x): do_something(list)
-- MAL
---------------------------------------------------------------------------
lem...@informatik.uni-koeln.de Marc-Andre
Lemburg
===========================================================================
For more infos, type 'finger -l
lem...@nolde.informatik.uni-koeln.de'
-----------------There's nothing like
shoWWWbusiness-----------------------
Perhaps I misunderstand the meaning of forall and exists. Shouldn't the
argument to do_something be x? I think the intent was something like:
map(do_something, filter(has_property, list))
> map(do_something, filter(has_property, list))
It looks to me like the original poster was after something more like:
def forall(list, condition):
for item in list:
if not condition(item):
return 0
return 1
allowing us to write:
if forall(list, has_property):
do_something(list)
You could also implement forall as len(filter(condition, list)),
which might be more or less efficient. The builtin filter is probably
more efficient than a user-defined function, but the user-defined
forall could return right away if the first element of the list
fails the condition.
I like the idea of a forall function, but I want to use the mathematical
symbols for "forall" and "there exists". A quick demo using
these symbols got a "SyntaxError: invalid syntax". Is there some bit
of the Python interpreter which isn't 8 bit clean?
--
http://www.cs.su.oz.au/~gary/
I'll put my two cents in here. Common Lisp has exactly this notion, and
I find it tremendously useful. One thing: if we're going to make them
predicates, as they are in CL, we should probably make them parallel to
map, reduce, filter, etc., as they are in CL, with the element predicate
as the first argument and the list as the second.
Sam Bayer
The MITRE Corporation
s...@mitre.org
Ahhh. Then you should be able to use something like:
if reduce(operator.__add__, map(has_property, list), 0):
do_something(list)
Skip Montanaro | Check out:
sk...@calendar.com | Musi-Cal: http://concerts.calendar.com/
(518)372-5583 | Conference Calendar: http://conferences.calendar.com/
Perhaps I misunderstand the meaning of forall and exists. Shouldn't the
argument to do_something be x? I think the intent was something like:
map(do_something, filter(has_property, list))
Not always. What I wanted to do was to be able to write a prototype algorithm
from let's say a SAT-solver or an optimizer more or less directly in Python.
What I found, was that it is almost possible to this without even changing the
pseudo-way these algorithms are written down in papers or books. This already is
a very big PLUS for Python. Yet some little things like the simple quantors
are missing.
Now to your question: exists and forall are often used to check for some
condition over the whole input instance of the problem (e.g. list) and if it
holds, something can be done to the instance as a whole.
MAL
> Now as Python is a state-of-the-art programming language, I propose the
> following syntax:
After cluerobbing a friend who did a Real Computer Science degree, here's
what I've come up with (though I still may be Missing The Point).
:-)
> if forall x in list: has_property(x): do_something(list)
"do_something will be applied to all x that meet condition has_property"
map(do_something,filter(has_property, list))
well, not quite (maybe I should have used parenthesis): in mathematics
you normally write things like this:
* if we have, \forall x\in SomeSet with SomeValue(x) < Bound, then normalize
SomeSet with Bound
To stay close to Python-syntax (for x in range()...), I thought, my notation
would be a good idea, but people seem to have trouble with it...
What I meant was: if all x in list meet condition has_property, then execute
do_something.
> if exists x in list: has_property(x): do_something(list)
"do_something will be applied if any x meets condition has_property"
if reduce(lambda x,y: x or has_property(y), list, 0): do_something(list)
exactly...
I should have written the two each on two lines:
if forall x in list: has_property(x):
do_something(list)
and
if exists x in list: has_property(x):
do_something(list)
...clearer now ?
It looks like all that really matters is the
condition:
if (for all x in list, has_property(x) is true):
then whatever
if (for some x in list, has_property(x) is true):
then whatever
This is the interpretation i know consistent with
the mathematical symbols "forall" and "exists". If
this is the correct interpretation, all you need are
reduce(lambda x, y: x and y, map(has_property, list), 1)
reduce(lambda x, y: x or y, map(has_property, list), 0)
Ping
Thanks for the reduce-trick (really short!), but what is still bothering me, is
the syntax: if you would see the above statement in some code, would it
immediately spring to your mind, that the author wanted to implement an \exists ?
And have you ever seem somebody using this terminology in a jounal ?
MAL
BTW to the others: Please mail me your replies: my newsreader is broken... :-(
Yep, that's what I meant and you surely pointed out the
shortest way to express this in Python... except one little
thing: my point wasn't expressing exists and forall with
some tricky reduce or map, I would very much love a
syntax which let's me translate pseudo-algorithms easily
and directly into Python, which I think, is almost perfect
for this. It's just sometimes, trivial things like these
two quantors (is that the correct word in english for thingies
like exists and forall) blow up to compicated statements
like the two above... and having to use these a lot,
it seems to me, to be a good idea, having them builtin,
avoiding (Python) function calls.
Well, I guess it doesn't help. It doesn't look like anybody
is taking this seriously -- just what is so painful about
extending a syntax ? I would write the stuff needed myself,
but don't know enough about the internals of the interpreter.
MAL
> if reduce(operator.__add__, map(has_property, list), 0):
> do_something(list)
>
Thanks for the reduce-trick (really short!), but what is still bothering me, is
the syntax: if you would see the above statement in some code, would it
immediately spring to your mind, that the author wanted to implement an \exists ?
And have you ever seem somebody using this terminology in a jounal ?
No, but that's the situation for most mathematical notation. Specialized
systems like Macsyma and Mathematica have syntax for summation, integrals,
geometric progressions and derivatives because that is precisely the sort of
stuff most people use them for.
It's not clear that more general-purpose programming languages like Python,
Perl or C should support a lot of specialized mathematical notation. The
various binary and unary operators get used frequently enough to warrant
inclusion in most programming languages, and programming constructs like
functions, modules, classes and compound statements warrant their inclusion
for the same reason. If you want the above code to be a little more
mnemonic, especially if you're going to use it frequently, you can create a
module that defines exists and forall functions and contribute it to the
Python community. If it's sufficiently interesting it will wind up in the
distribution.
Okay, i'm glad i understood you.
> It doesn't look like anybody
> is taking this seriously -- just what is so painful about
> extending a syntax ?
Probably because it is trivially easy to define functions
that do the above for you, and then you have as near as to
your own syntax as you want. All you need is to say
def forall(list, property):
reduce(lambda x, y: x and y, map(property, list), 1)
def exists(list, property):
reduce(lambda x, y: x or y, map(property, list), 0)
...and then it's as simple as writing
if forall(my_list, some_property): do_whatever
It can't get much easier than that, can it?
If you want, you could ask for these tidbits to be included
in a Python module with a distribution, i suppose, and then
see what happens.
Ping
But that's just the answer you always get on this list... one side says:
why bother integrating this and that, when it can already be done in some way
(of course I know about modules, functions,... I'm NOT new to Python),
the other always moans about the language getting too heavy-weight. But it's
often the little things that get people interested in something -- Python
is nice, but there's no point in not making it even nicer (and with that
I mean not creating a module for every single bit -- it the same question,
as having += and ++ as operators in Python or not: some think they're nice,
some get the kreeps when being reminded of the OTHER languages; shouldn't
we stop acting like children ?!).
MAL
> But that's just the answer you always get on this list... one side says:
> why bother integrating this and that, when it can already be done in some way
> (of course I know about modules, functions,... I'm NOT new to Python),
> the other always moans about the language getting too heavy-weight. But it's
> often the little things that get people interested in something -- Python
> is nice, but there's no point in not making it even nicer (and with that
> I mean not creating a module for every single bit -- it the same question,
> as having += and ++ as operators in Python or not: some think they're nice,
> some get the kreeps when being reminded of the OTHER languages; shouldn't
> we stop acting like children ?!).
With all due respect, I think its a credible answer in the present case. The
first step to ask is whether it adds material functionality, or in the case
of python, whether it adds a material and substantial opportunity for
speed enhancement due to the uniquely expensive costs of function and
method calls. All this must be weighed against the likelihood that the
feature will be used or is necessary at all.
Your initial message barely got across the intented semantics, let alone
the justification for it. Why would a change in the python syntax be
justified in this case -- just what benefit is there over the status quo,
given that there exist simple and direct ways to provide equivalent
functionality at almost no cost. What are the failings of the status quo
in this regard?
At any rate, this complaint is unseemly unless and until you are willing
first to make an argument to support your proposed change! Advocacy needs
to begin with more than "here's some syntactic sugar I like -- gimme!"
Let's begin with some real examples, why the sugar would be important, and
so on.
If each quirk and interest suggested were implemented, we'd be back to PL/I
very, very quickly.
At any rate, I write not to piss you off, but to encourage you to explain
why this is helpful or important. I hope you will accept this invitation.
--
just another view,
Andy Greenberg (wer...@gate.net)
Carlton Fields
Python took several ideas from CWI's ABC language, and this is one that didn't
make the cut. I'd be interested to hear Guido's thoughts on this! They're
certainly very nice to have, although I wouldn't say they're of core
importance. But then a lot of "nice to have but hardly crucial" features did
survive the cut (like, e.g., "x < y < z" as shorthand for "x < y and y < z"),
and it's never clear where to draw the line.
In ABC, the additional keywords were "some", "each", "no" and "has", as in
(importing the ABC semantics into a virtual Python):
if some d in range(2,n) has n % d == 0:
print n, "not prime; it's divisible by", d
else:
print n, "is prime"
or
if no d in range(2,n) has n % d == 0:
print n, "is prime"
else:
print n, "not prime; it's divisible by", d
or
if each d in range(2,n) has n % d == 0:
print n, "is <= 2; test vacuously true"
else:
print n, "is not divisible by, e.g.,", d
So "some" is a friendly spelling of "there exists", "no" of "not there
exists", and "each" of "for all". In addition to testing the condition,
"some" also bound the test vrbls to "the first" witness if there was one, and
"no" and "each" to the first counterexample if there was one. I think ABC got
that all exactly right, so (a) it's the right model to follow if Python were
to add this, and (b) the (very useful!) business of binding the test vrbls if
& only if the test succeeds (for "some") or fails (for "no" and "each") makes
it much harder to fake (comprehensibly & efficiently) via map & reduce tricks.
side-effects-are-your-friends-ly y'rs - tim
Tim Peters tim...@msn.com, t...@dragonsys.com
not speaking for Dragon Systems Inc.
Skip Montanaro wrote:
> It's not the technical problem of extending the syntax. It's the language
> bloat that would result. Python is nice and clean as it is and should
> probably stay that way.
But that's just the answer you always get on this list... one side says:
why bother integrating this and that, when it can already be done in some way
(of course I know about modules, functions,... I'm NOT new to Python),
the other always moans about the language getting too heavy-weight.
Since you can get at syntax trees in python (so so it seems - though I've
not tried it), would it be possible to add full fledged macros? Maybe
not always executed, but enough to be able to add new syntax to the
language. Having a true macro language has always seemed to be one
of the most powerful parts of Lisp.
Then, someone who wants a new syntax or loop operator or whatever
could build it - probably given a few examples to start off.
--
je...@nmt.edu - Jeff Putnam, CS Dept, New Mexico Tech, Socorro, NM
http://nmt.edu/~jefu/ - "You never learn anything, you just get used to it."
First of all: thanks to all, who took it seriously ! (Although I probably
did not get a chance to reade all the answers, since I only get replies by
mail -- broken newsreader)
Yes, there where several solutions mentioned, but every single one of them
included some function defining - either for the condition, the quantifiers
themselves or both. For me, these quantifiers seem to be a natural
extension of what reduce, map an filter started -- so why not have them
builtin, just like them.
> Your double :: notation appears awkward (to me), violates existing
> syntax patterns, is unnecessary, and is not parallel to the existing
> map, reduce, etc.
Your probably right, I just thought that a similar syntax to the for-statement
would help to intuitively make people understand. It did not. But Tim Peters
mentioned a different syntax from ABC, that looks great and is easy to understand.
I would very much love a similar syntax.
MAL
>
> Python took several ideas from CWI's ABC language, and this is one that didn't
> make the cut. I'd be interested to hear Guido's thoughts on this! They're
> certainly very nice to have, although I wouldn't say they're of core
> importance. But then a lot of "nice to have but hardly crucial" features did
> survive the cut (like, e.g., "x < y < z" as shorthand for "x < y and y < z"),
> and it's never clear where to draw the line.
>
> In ABC, the additional keywords were "some", "each", "no" and "has", as in
> (importing the ABC semantics into a virtual Python):
>
[...]
>
> So "some" is a friendly spelling of "there exists", "no" of "not there
> exists", and "each" of "for all". In addition to testing the condition,
> "some" also bound the test vrbls to "the first" witness if there was one, and
> "no" and "each" to the first counterexample if there was one. I think ABC got
> that all exactly right, so (a) it's the right model to follow if Python were
> to add this, and (b) the (very useful!) business of binding the test vrbls if
> & only if the test succeeds (for "some") or fails (for "no" and "each") makes
> it much harder to fake (comprehensibly & efficiently) via map & reduce tricks.
>
That sounds great -- no function calls and even intelligently bound variables.
I would very much love this to be included.
MAL
Speed is a problem: if you call one or two functions some ten thousand
times, where you would normally (in C) just increment a list-pointer
(which
is probably the it could be handled, if it were builtin) then speed
becomes
an important topic.
>
> Your initial message barely got across the intented semantics, let alone
> the justification for it. Why would a change in the python syntax be
> justified in this case -- just what benefit is there over the status quo,
> given that there exist simple and direct ways to provide equivalent
> functionality at almost no cost. What are the failings of the status quo
> in this regard?
The two quantifiers are a very common notation in mathematics, physics
and are two very basic extensions to the set map, reduce and filter.
They
ARE useful and increase the speed and readability of programs dealing
with these kind of
things. But: I agree, my original proposition for a syntax wasn't
compatible
with the already existing map, reduce and filter builtin functions.
Nethertheless
they started a fruitful discussion and that's what I had in mind. So at
least
in that sense, the original posting was a success.
>
> At any rate, this complaint is unseemly unless and until you are willing
> first to make an argument to support your proposed change! Advocacy needs
> to begin with more than "here's some syntactic sugar I like -- gimme!"
> Let's begin with some real examples, why the sugar would be important, and
> so on.
>
Hey look, just take any journal on computer science, mathematics or
physics,
look up some new algorithm and then rethink your statement ! I'm not
posting
this for the fun of it ! If someone could give me a comprehensive
introduction
to the internals of the interpreter I'd have done the extension myself,
without
bothering asking, if someone could do it for me. I love this language
and
don't want to turn back to the old C-days everytime, I need to check a
new proposal for an algorithm. Python is (almost) perfect for giving it
a quick
try, yet not quick enough to get it running in the dimensions of core
problems,
so it needs every possible hint of what I want done on a syntax-basis.
> If each quirk and interest suggested were implemented, we'd be back to PL/I
> very, very quickly.
>
> At any rate, I write not to piss you off, but to encourage you to explain
> why this is helpful or important. I hope you will accept this invitation.
Sorry, but that didn't come across...
MAL
Most definitely. Then you could do what I did with my dissertation
demonstration code: I defined a completely new language syntax
using Common Lisp macros that no other person could possibly understand.
This guaranteed that I would be the only person ever to use the code
(a nice monopoly), but now I'm not even using it. Macros also allow
code size to balloon unexpectedly, if it's done right, and let's not
even consider doing it wrong (ala C or C++).
One of the nice thing about Python is that I can read and understand
just about any fragment of code which shows up in this list (except
for those that abuse globals ;) ).
def for_all(predicate, sequence):
if predicate is None:
for x in sequence:
if not x: return 0
else:
for x in sequence:
if not predicate(x): return 0
return 1
def exists(predicate, sequence):
if predicate is None:
for x in sequence:
if x: return [x] # return a witness (cylindric logic anyone?)
else:
for x in sequence:
if predicate(x): return [x]
return 0
A little verbose, but there ya go.
-- Aaron Watters
===
-- Quantifiers have to do with everything!
-- Well, some of them do.
(overheard after a logic colloquium)
> > In ABC, the additional keywords were "some", "each", "no" and "has", as in
> > (importing the ABC semantics into a virtual Python):
> >
> [...]
> >
> > So "some" is a friendly spelling of "there exists", "no" of "not there
> > exists", and "each" of "for all". In addition to testing the condition,
> > "some" also bound the test vrbls to "the first" witness if there was one, and
> > "no" and "each" to the first counterexample if there was one. I think ABC got
> > that all exactly right, so (a) it's the right model to follow if Python were
> > to add this, and (b) the (very useful!) business of binding the test vrbls if
> > & only if the test succeeds (for "some") or fails (for "no" and "each") makes
> > it much harder to fake (comprehensibly & efficiently) via map & reduce tricks.
> >
> That sounds great -- no function calls and even intelligently bound variables.
> I would very much love this to be included.
FWIW, I second that!
nick
---------------------------
Nick Seidenman
Science Applications International Corporation
It strikes me that map and filter are syntactically functions, not
anything special. You can do the same, no?
--da
You can't use a character outside the ranges a-z A-Z 0-9 _ in an
identifier or new keyword (if you are modifying the parser, which you
seem to be referring to here). This is intentional. The *source code
character encoding* is ASCII. It is done so that Python modules can
be exchanged freely by people whose default character encodings differ
in the interpretation of characters with the high bit set. This is
not a hypothetical problem: Mac, Windows and Unix all have different
characters in the 128-255 range!
--Guido van Rossum (home page: http://www.python.org/~guido/)
I probably could (haven't done any extensions before, but from what I've
seen in the contrib-dir, it shouldn't be too hard). Still, even then
Python will have to make a function call with all it's consequences...
and that's what I would like to avoid. By giving Python some more
information, all the function call overhead could easily be avoided, thus
making things a lot faster. (Yes, I am a bit picky when it comes to speed :-)
But I'll give it a try in your suggested direction...
(-: Thanks to everyone who listened to this thread and kept up with me :-)
------------------------------------------------------------------------------
Marc-Andre Lemburg http://fashion-forum.de/ikds/
Thanks for any hints.
Yes.
Extending the syntax is painful to me because I love python's
simplicity and capability to expand within its syntax. I don't
think that direct translation from a common form of pseudo-code
is a good enough reason. Python isn't purporting to be pseudo-code,
and is it so much trouble to go from "if exists list that qual:" or
whatever to "if exists(list, qual):"?!
* But that's just the answer you always get on this list... one side says:
* why bother integrating this and that, when it can already be done in some way
* (of course I know about modules, functions,... I'm NOT new to Python),
* the other always moans about the language getting too heavy-weight. But it's
I'm confused about exactly what you're requesting: a statement? An
operator? It seems like those two things you request are analagous to
filter(), reduce(), etc., and, if they were to make it into the language,
should be functions similarly.
However, is it too much to expect one to define one's own functions
until we get more requests for this?
Paul
--
(c) now me ... Paul Ezra Kautz, Jumbo Yaffa Blocks #94: p...@llama.net
bim http://llama.net/home/pek/ 1996 is the year of the accordion bom
bim "Sie sind ein sonderbarer Kautz." --Magnus Mulqvist bom
lists.py - a module for easy list handling
which is supposed to be sort of a test platform for a module
containing everything I ever wanted to have dealing with lists.
For the moment I'm looking for the fastest possible way to
express the routines there in Python, later on I'm planing
to make it into a buildin module (If that should speed things
up significantly).
So, everyone on this thread is gladly invited to have a look.
MAL