[Python-projects] Assertions, type checking, and testing

[Aurélien Campéas]

On Wed, Jun 21, 2006 at 11:01:18AM -0400, David G. Wonnacott wrote:
> Thanks, Aurélien, for your reply.

Well, answering hastily to this one ...

> 
> >  Date: Mon, 19 Jun 2006 11:36:35 +0200
> >  From: =?iso-8859-1?Q?Aur=E9lien_Camp=E9as?= <aurelien.campeas at logilab.fr>
> >
> >  On Fri, Jun 09, 2006 at 11:04:31AM -0400, David G. Wonnacott wrote:
> 
> ...
> 
> >  > I hope to start teaching introductory computer science with Python
> >  > (rather than C++), but am not that fluent with Python myself yet.
> >  > This is clearly a recipe for potential disaster, so in addition to
> >
> >  Since you are coming from C++ (fluent in that ?), I don't believe
> >  switching to python can be a recipe to disater, even if you are only
> >  learning the basics. You will be stunned by the amount of C++ verbiage
> >  that is just useless and has to be unlearned. This is a good move
> >  :)
> 
> I don't think that Python itself will be a disaster, but there is
> always great peril in teaching with a tool with which one has not yet
> achieved complete fluency oneself.
> 
> I know enough of Python to be excited about the lower level of
> redundant verbiage (vs. C++ or Java). However, I also have a respect
> for the fact that some level of redundancy is necessary for error
> detection (from a purely information-theoretic point of view). I have
> fond memories of my transition from languages without redundancy and
> static checks (Basic/Assembly language) to Pascal -- I was amazed at
> how much testing time was saved by a simple static type checker.

I don't remember for BASIC, but note that Python is completely
type-safe in the sense that no type error will ever pass silently like
in assembly or even some C programs. It is strongly typed if not
statically typed. 

<small rant>

The exception handling system is an important part
of modern languages, and while it is not of strict algorithmic
interest, it is of utmost importance for the practical developper,
with respect to program robustness. (this is slightly off-topic but I
am quite annoyed that exception handling receive so little academic
interest - in the context of teaching at least - and formal proofs and
invariants the lion's share; they are almost equally important, and
while a real-world program may not retain most of its invariants
checking (for performance reasons typically), it must be able to
handle errors gracefully; not all errors can be caught by formal
proofs, far from it).

<.../>

Also, you should have a looke at Pylint (and use it!)
... (http://www.logilab.org/projects/pylint). It will also notify you
about what it considers (and much in the Python community consider)
good/bad style.

Of course, the amount of possible type checking is limited (it is so
for well-known theoretical reasons, see :
http://www.python.org/pycon/2005/papers/11/Localized_Type_Inference_of_Atomic_Types_in_Python.pdf).

Pylint is of course freely available with source, and you can add
whatever fancy static checking you want.

> 
> Now that I write more sophisticated stuff, I spend (i.e., waste) a lot
> of my time trying (and sometimes failing) to explain the types in my
> system to the C++ compiler. I'd rather be spending my time developing
> the algorithms, and am happier with Haskell every time I use it.
> However, just declaring function parameter types is not be a big deal
> for the students in my introductory courses, so this particular aspect
> of the redundancy is not something I'd like to eliminate.

Right, but not in Python. However, there are other ways.

> 
> Of course, a lot of the redundancy in C++ does not help to detect
> errors early, such as the need to keep the signature of each function
> in the .h synchronized with the function header in the .cc; when these
> get out of line, there is a confusing error at _link_ time rather than
> a possibly helpful error at compile time; I suspect this is slower and
> more confusing for them than the equivalent basic mistake would be in
> Python (where an inappropriate type or number of arguments given in a
> call would not be found until run-time testing).

Python programmers 'solve' this problem with a methodology called
test-driven development. This consist of writting unit tests prior to
the actual code. This help ensure that most type errors are caught by
the tests (because, ... there are tests !), and in fact much more
important properties of the code will be thus caught. This way of
doing things is also quite robust in the face of code change/evolution
-- which is a common thing in the day-to-day world of commercial
development.

Note that the distinction between compile-time and run-time is not as
clear-cut in Python (or, say, SmallTalk or Lisp) than in languages
such as C++, Java, with their edit-compile-run development cycles.

Run-time testing is no less 'valuable' a technique than static
analysis, and it can catch many properties the developper wants it to
catch, not just type errors. It works well in practice.

> 
> Another drawback of our current system is that students naturally want
> to put type information in with their precondition statements. If a
> parameter must be a string whose length is a multiple of 3, it's just
> confusing to state these two facts in two different places. I think
> Python will produce a great improvement here.
> 
> ...
> 
> >  > I am also hoping to find either
> >  > 
> >  > a) testing tools to let us selectively disengage various classes of
> >  >    assertions (i.e. you want to test pre- and post-conditions and loop
> >  >    invariants during unit tests, but perhaps only pre-conditions
> >  >    during some integration tests), or
> >
> >  To me this looks like a software engineering requirement more than
> >  something needed in the context of algorithmic teaching ... (esp. the
> >  ability to selectively switch on and off various kinds of assertions)
> 
> I agree with your distinction between teaching about algorithms and
> teaching software engineering; our focus is on teaching students the
> basic ways we want them to be able to think about algorithms: from the
> point of mathematics and design, but also as a software artifact that
> must be tested if we are to trust it.
> 
> Important criteria for the language are:
> 
> 1) ability to make clear, concise statements of algorithms, data
>    structures, and inheritance heirarchies.
> 
> 2) support for simple uses of multiple paradigms, including functional
>    (though we don't need lazy evaluation, and can make do without
>    lambda's, at this level), procedural, and object-orientation (both
>    data encapsulation and inheritance).
> 
> 3) ability to make precise statements about what we expect to be true,
>    including but not limited to type information, and have these
>    statements checked somehow. This would have to work for both
>    classes and plain functions.
> 
>    This could be
> 
>    i) a simple "assert" statement combined with the ability to ask
> 	about the the type of an object at run-time (I think Python
> 	has both of these already); I'm not sure what "decorators"
> 	have to do with this, though.

About decorators, neither do I. Well, they might help you conveniently
hide some of the pre/post-conditions checking you want to perform on
function calls.

about simple asserts plus type checking :

assert isinstance(x, Foo)

is something seen very commonly in Python code.

> 
>    better than that would be
> 
>    ii) a way to simply distinguish among the different kinds of
> 	statements we want to make, with the purpose of helping
> 	students understand their different roles in thinking about
> 	and testing algorithms -- this assertion is a precondition,
> 	but that one is a claim about the internal workings of the
> 	function, this other one quantifies a bound on the amount of
> 	work left to be done.
> 
>    which could be further improved with
> 
>    iii)	a way to selectively turn off certain tests done at run-time
> 	as the students learn about unit testing vs. integration
> 	testing, or alternatively a way to prove the assertions
> 	statically so that there is no need to perform the run-time
> 	test.
> 
>    In C++, "assert" plus static type checking provides most of what is
>    described for Level "i" above, though I still don't have an good
>    way to check for "progress" in a recursion or loop as the program

Checking for progress depends entirely on *what* is supposed to
progress, and sometimes this is hard to know ... But if the
progressing elements are known, I see no reason you could not assert
whatever properties about them. Or maybe I didn't understand what you
meant there.

>    runs (a progress statement can, of course, be checked by hand when
>    one grades the assignment). Level "ii" can be achieved (except for
>    progress, of course) with a few lines of
> 
> 	#define precondition assert
> 
>    and similar stuff (progress(INT_QUANTITY) is defined as nothing,
>    though we should probably at least assert that it is not negative),
>    and with a bit more trouble we can put some #if's around these and,
>    for example, be able to turn off everything but preconditions via
>    something like "-DLOGIC_CHECKING_LEVEL=3" on the compilation
>    command line.

Bleh... see my continued collection of specialized switchable asserts :)

> 
>    I suspect that I could similarly write my own code for levels ii
>    and iii in Python after I get better with it, but (a) I'd rather
>    not "re-invent the wheel" (even if I am already familiar with that
>    old "B.C." cartoon in which the triangular wheel is touted as an
>    improvement over the square wheel because it "eliminates one bump")
>    and (b) I'd like to know now what this system will look like so
>    that I don't have to retrofit it later onto the first examples I
>    write.

What about :

ASSERT_TYPES = True
ASSERT_RANGES = True
ASSERT_EXPR = True 

def assert_subtype(obj, class):
    if ASSERT_TYPES:
       assert isinstance(obj, class)

def assert_range(var, range):
    if ASSERT_RANGES:
       assert range[0] <= var <= range[1]

def assert_expr(expr):
    if ASSERT_EXPR:
       assert expr()

---
can be used thusly: 

from math import pi
def foo(a, b, c):
    # preconditions
    assert_subtype(a, int)
    assert_subtype(b, float)
    assert_subtype(c, Foo)
    assert_range(i, (0, 42))
    assert_range(b, (1/3.0, pi))
    # body
    ...
    assert_expr(lambda a, b, c: c.quux(a) == b)
    ...


Isn't that enough for your students ?

Well, I don't have the time to complete this with specific checks for
pre/post-conditions around function/method calls, but with little pain
and some decorator magic (indeed), I suspect it can be done.

Note that turning off the switches does not eliminate the calls +
ASSERT_X checks at runtime. This is the reason Python programmers take
the time to write proper test suites. Of course, even C, C++, Java
applications need and have such test suites (static type checking
being mostly a performance hack anyway) and various toolsets to help
with that. I invite you to have a look at py.test (easily available if
you are a debian user at least). But the standard Python unittest
infrastructure is already quite nice.

> 
> Other significant but not vital criteria for the language are
> 
> 4) that it be "alive" -- i.e. have a visible user community and be
>    something the students think is cool.
> 
> 5) that it have some not-too-painful way to do interactive graphics to
>    run the GUI's for the functions the students are writing and
>    testing. It is vitally important that the labs be engaging and fun
>    as well as intellectually challenging and illustrative of the
>    concepts of computer science that we want to cover. The students in
>    the class do _not_ have to write the GUI, but the student
>    assistants do.
> 
> 6) that it be easy to install, hopefully including the necessary
>    graphics libraries, on various platforms.
> 
> Python is out ahead of C++ on 1 and 2 and probably 4 and 5. I suspect
> it at least equals C++ on 3 and 4, though these are less clear and #3
> depends a bit on whether I can get to level "ii" easily or not.

Also add 6 for Python. I believe 3/ii can be achieved without too much
effort. If I get some time, I'll delve into that, but I cannot promise
anything, being currently quite loaded.

> 
> ...
> 
> >  > Please let me know if you have any recommendations for tools for
> >  > specialized assertions, especially if they integrate with either
> >  > testing tools or static checks.
> 
> >  The aspects package from logilab could be of some help, wrt defining
> >  various kinds of invariants, pre- post- conditions on *methods* ...
> 
> I will look at the aspects package for use on classes in our data
> structures course, and if nothing better comes up, see if I can get by
> with just "assert" for one year until I can build something better
> myself, and try to make my own stuff look as much like the stuff in
> the aspects package as I can.

Note that the author of the aspect package is not too satisfied with
its current implementation (even if the overall result is quite nice).

But ... we don't really use it ! Maybe we don't really need something
that powerfull after all. Aspects were mainly a way to overcome
limitations of statically-minded, poorly reflexive languages like C++ or
Java. They are not so appealing in Python or whatever dynamic,
reflexive languages.

> 
> >  I don't know of any tool that would do a), but I don't know a great
> >  deal of the immense python toolset available out there, and it might
> >  be possible to build such a simple tool with a few lines of
> >  code. Could you give some examples of the kind of assertions you would
> >  want to check and be able to enable/disable on the fly, and also these
> >  properties you would want to statically check (something Pylint could
> >  be used for, maybe) -- in
> >  pseudo-code ?
> 
> Here are some simplified examples of stuff from our 1st semester; some
> of these could be checked easily with a static checker, others are
> more challenging; we would be quite happy to just get to level "ii"
> above, even if there is neither a static checker nor a way to
> selectively turn things off, though these level "iii" elements would
> be nice too :-)
> 
>    *) the "exponent" parameter is a non-negative integer
> 
> 	double power(double base, int exp)
> 	   precondition(exp >= 0);


def power(base, exp):
    # preconditions
    assert_subtype(base, float)
    assert_subtype(exp, int)
    assert_expr(lambda exp: exp >= 0)
    # body
    ...

> 
>    *) that four integers specifying a "window" on a screen are
>       ordered properly:
> 
>         double point_in_window(int x, int y,
> 			       int xmin, int xmax,
> 			       int ymin, int ymax)
> 	   precondition(xmin <= xmax && ymin <= ymax)
> 	   return xmin <= x && x <= xmax && ymin <= y && y <= ymax;
> 

def point_in_window(x, y, xmin, xmax, ymin, ymax):
    # preconditions
    assert_expr(lambda xmin, xmax, ymin, ymax: xmin<=xmax and ymin <= ymax)
    ...

>       (later in the year, the students will see how to do this with
>       point and window objects)
> 
>    *) a particular parameter is a string with length divisible by 3
> 
> 	double f(... String c ...)
> 	   precondition(length(c) %3 == 0)
> 
>       actually, the students _should_ be asserting that c's length is
>       divisible by 3 and that every 3rd character is a space and that
>       all other characters come from another string, but few of them
>       actually do so and the failure to do this doesn't set them up
>       for a fall in a later lab in which they may be tempted to call
>       "f" without having that final space in place. They also have the
>       option of making "f" work without requiring the final space,
>       which will make their lives easier later, in which case the
>       precondition would be a bit different; either option is fine as
>       long as they get the two labs to function properly together.
> 
>    *) during the execution of the loop-based Fibonacci function, we
>       get the same result we were getting from the slow recursive
>       function, and that we make progress because the integer quantity
>       (n-i) becomes smaller in each loop iteration and cannot be
>       negative (the code is from memory, apologies for errors); the
>       identical logical statements are used in the tail-recursive
>       version of the function too, though of course the loop invariant
>       becomes 
> 
> 	int fib_loop(int n)
> 	   precondition(n > 0)
> 
> 	   int i = 2, fibi = 1, prev = 1
> 	   loop_precondition((n == 1 && i > n && fibi == fib(n)) ||
> 			     (i <= n && fibi == fib(i) && prev == fib(i-1)))
> 	   while (i < n)
> 	      loop_invariant(fibi == fib(i) && prev == fib(i-1))
> 	      loop_progress(n-i)  // currently not checked in our C++ system
> 	      int tmp = prev;
> 	      prev = fibi;
> 	      fibi = tmp + prev;
> 	      i = i+1
> 	   loop_postcondition((n == i && fibi == fib(i)) ||
> 			      (n == 1 && fibi == fib(1)))
> 
> 	   postcondition(fibi == fib(n));
> 	   return fibi
> 
>       Once this function has been tested, it would be nice not to
>       execute the loop invariant and postcondition, as these are
>       exponential-time tests in an otherwise linear function. However,
>       we would still like to verify that the precondition is not
>       violated when the function is used.
> 

What do you think of my instant proposal ?
The lambda stuff is a little ugly, but, well.

And a @return_types(...) decorator could be nice, for instance.

Cheers,
Aurélien.

> 
> >  Cheers,
> >  Aurélien.
> >
> >  > 
> >  > I'd also appreciate any other general recommendations for someone in
> >  > my position.
> >
> >  ps: if checking assertions/invariants (in code) is so important, you
> >  could consider using Eiffel, or even B
> >  (http://en.wikipedia.org/wiki/B-Method) but for this one the tools are unfree.
> 
> I am a great fan of certain things in Eiffel, but I've not looked at
> it recently -- I don't recall it letting me write a function that is
> not part of any class, and thus in shares Java's problem of excessive
> verbiage when one is _not_ writing classes ("static public void
> main"), and (at least locally) it also doesn't seem as "alive" as
> Python, and I don't know much about integration of graphics, though
> this is a lesser concern.
> 
> I'll look more at "B"; I had thought about the Z notation, but our
> goal is to expose students to formal methods without making the entire
> course be about this one topic; having half a dozen ways to say
> "assert" doesn't add a lot of overhead to the labs, but even a subset
> of the tools for "B" may be too much for us to cover and still have
> time to do the other things.
> 
> Thanks again for your thoughts,
> 				Dave Wonnacott
>