How do I emulate Lisp (apply) or (curry) in Rust?

Question

I'm porting QuickCheck to Rust, and I've written everything except for_all as I'm not sure what the type signature should be.

I know that in general, for_all will accept a property lambda and a collection of generator lambdas. It will evaluate the generators in order to create a random test case to give the property as input.

It should print +++ OK, passed 100 tests. if the property returns true, otherwise, it should print *** Failed! and print the offending test case values.

Hammock

Answer 1

In Rust, all functions take a fixed number of parameters, so there's no such thing as an equivalent to Lisp's apply in the general case, but macros can provide you with the abstraction you desire. You can write:

macro_rules! for_all {
    ( $tester:expr, $( $generator:expr ),* ) => {
        $tester( $($generator() ),* )
    }
}

Then, for_all!(|a, b| a + b, || 4, || 7) produces 11.

Good luck with your project!

Osy

Thank you for your awesome code! The last thing I need is a way to 1) temporarily store the generated values in some kind of collection 2) apply the tester function to each test case in the collection 3) if any test case fails, print "FAIL!" and print the values in that test case 4) loop steps 1-3 so that 100 test cases are run against the tester, stopping if any test case fails. If none of the 100 test cases failed, print "Ok." Help me Obi Wan Kanobi, you're my only hope. – Hammock

Answer 2

Editor's note: This answer is from a version of Rust prior to 1.0 and contains code that is not syntactically valid in Rust 1.0.

If all you need is a way to define apply, try Rust's macro-by-example syntax extensions:

fn main() {
    #macro[[#apply[f, [x, ...]], f(x, ...)]];

    fn add(a: int, b: int) -> int { a + b }

    assert (#apply[add, [1, 15]] == 16);
}

The above code is from the Rust test suite.

Sadly, the documentation on syntax extensions is a bit sparse at the moment. The Rust reference manual is probably your best bet--although the example it gives (of apply, no less!) is outdated, so I'm not sure how much of its information can be trusted.

Update:

All that's left is figuring out how to wrap add ... assert in a function with the right type signature that accepts arbitrary generators.

I'm still not sure exactly how you're putting this all together, but here's a function that accepts any function that produces an int:

use std;
import std::rand;

fn assert_even(num_gen: fn() -> int) -> (bool, int) {
    let num = num_gen();
    ret (num % 2 == 0, num);
}

fn main() {
    let rng = rand::mk_rng();

    let gen_even = {|| (rng.next() as int) * 2};

    log(error, assert_even(gen_even));
}

However, working with numbers in Rust is sort of a pain at the moment, and if you want to generalize assert_even to any numeric type you'll have to define interfaces/implementations and then declare assert_even with a bounded generic type:

use std;
import std::rand;

iface is_even { fn is_even() -> bool; }

impl of is_even for int { fn is_even() -> bool { self % 2 == 0 } }

impl of is_even for u32 { fn is_even() -> bool { self % 2u == 0u } }

fn assert_even<T: is_even>(num_gen: fn() -> T) -> (bool, T) {
    let num = num_gen();
    ret (num.is_even(), num);
}

fn main() {
    let rng = rand::mk_rng();

    let gen_even_int = {|| (rng.next() as int) * 2};
    let gen_even_u32 = {|| rng.next() * 2u};

    log(error, assert_even(gen_even_int));
    log(error, assert_even(gen_even_u32));
}

Side note: if you're interested in testing, you should check out Rust's typestate facilities. See the Rust manual here for an example of what typestate does and the ways in which it is capable of enforcing program correctness. The way I understand it, it's basically a more powerful version of Eiffel's design by contract.

Update 2:

for_all accepts a single property (e.g. is_even or divisible_by) and a collection of generator functions. The generators are lambdas which return random values to pass as input to the property, e.g. [gen_int] for is_even or [gen_int, gen_int] for divisible_by. for_all will call the property using the generated values as a test case, printing +++ OK, passed 100 tests if the property returns true for 100 random test cases, or *** Failed! {test_case} if one of the test cases fails.

This complete source file should fully demonstrate the behavior that you're looking for, hopefully (the definition of for_all is near the very bottom):

use std;
import std::rand;
import std::io::println;

iface is_even { fn is_even() -> bool; }

impl of is_even for int { fn is_even() -> bool { self % 2 == 0 } }

fn main() {
    let rng = rand::mk_rng();

                                   // Cast to int here because u32 is lame
    let gen_even = {|| (rng.next() as int) * 2};
    let gen_float = {|| rng.next_float()};

    // Accepts generators that produce types that implement the is_even iface
    fn assert_even<T: is_even>(num_gen: fn() -> T) -> bool {
        let num = num_gen();
        let prop_holds = num.is_even();
        if !prop_holds {
            println(#fmt("Failure: %? is not even", num));
        }
        ret prop_holds;
    }

    fn assert_divisible(num_gen1: fn() -> float,
                        num_gen2: fn() -> float) -> bool {
        let dividend = num_gen1(),
            divisor = num_gen2();
        let prop_holds = dividend / divisor == 0f;
        if !prop_holds {
            println(#fmt("Failure: %? are not divisible", (dividend, divisor)));
        }
        ret prop_holds;
    }

                                        // Begin anonymous closure here
    #macro[[#for_all[prop, [gen, ...]], {||
        let passed_tests = 0;
        let prop_holds = true;
        // Nice iterators and break/continue are still being implemented,
        // so this loop is a bit crude.
        while passed_tests < 100 && prop_holds {
            prop_holds = prop(gen, ...);
            if prop_holds { passed_tests += 1; }
        }
        println(#fmt("Tests passed: %d", passed_tests));
        ret 0;  // Necessary to infer type of #for_all, might be a compiler bug
    }()]];  // Close anonymous closure and self-execute, then close #macro

    #for_all[assert_even, [gen_even]];
    #for_all[assert_divisible, [gen_float, gen_float]];
}

One more thing: the syntax extension mechanism is still fairly unpolished, so it's not possible to import macros from different crates. Until then, the definition of #for_all will have to appear in the file in which it is invoked.

Selfeffacement

that's enormously helpful! All that's left is figuring out how to wrap add ... assert in a function with the right type signature that accepts arbitrary generators. Instead of 1 and 15, functions that generate random numbers (or any type). – Hammock

@Hammock Can you give an example of a for_all invocation, along with the signatures of the functions that you expect to be passing in? – Selfeffacement

Visit wiki.call-cc.org/eggref/4/cluckcheck and find or scroll to "for-all". – Hammock

@Hammock I was editing the post just as you made your last comment, does that answer your question? Checking out your link right now. – Selfeffacement

Cool. Can you rewrite the example so that for_all accepts generators of arbitrary return type? Not just int's, not just numbers, but strings, vectors, etc. And not just unary properties but n-ary properties. – Hammock

@Hammock Do you mean that for_all would accept an arbitrary number of properties to test the generator against, or that the properties should be able to accept an arbitrary number of arguments? – Selfeffacement

for_all accepts a single property (e.g. is_even or divisible_by) and a collection of generator functions. The generators are lambdas which return random values to pass as input to the property, e.g. [gen_int] for is_even or [gen_int, gen_int] for divisible_by. for_all will call the property using the generated values as a test case, printing +++ OK, passed 100 tests if the property returns true for 100 random test cases, or *** Failed! {test_case} if one of the test cases fails. – Hammock

I was really happy to see a working solution until I read that last bit. Macros can't be imported? Sigh. – Hammock

Answer 3

Can you describe precisely what you want? I think what you're asking for is something like this:

fn for_all<A>(test: fn(A) -> bool, generators: &[fn() -> A]) -> bool {
    generators.iter().all(|gen| test(gen()))
}

fn main() {
    let generators: Vec<fn() -> (i32, i32)> = vec![
        || (1, 2),
        || (2, 3),
        || (3, 4),
    ];

    for_all(|(a, b)| a < b, &generators);
}

Lyons

Not quite. I have trouble explaining this. yellosoft.us/quickcheck does it better. If you can reproduce Lisp's (apply) in Rust, I can do the rest. – Hammock