2.0.0 API changes

[billpmurphy]

Some thoughts on API changes that might be nice to have in version 2.0.0; I'm happy to implement some or all of these.

• compare should return a data structure containing the reduction counts instead of writing to stdout. This data structure could have a Debug and/or Display implementation that returns a String that is the same as what compare currently prints.
• It might also make sense to do something similar with the reduction steps for beta. This would probably require splitting beta into two functions, beta (which returns the reduced Term) and beta_verbose (which returns the reduced Term and reduction steps).
• It might be desirable to build the church and scott modules at the same time; the only functionality in those modules that needs to be hidden behind feature gates are the From implementations, as they conflict with each other. There are several ways to achieve this, one way would be to add functions like to_church_int and to_scott_int which can be compiled together, then just modify the From implementations to call these.

Some other non-breaking features that I think would be nice to have, not necessarily in 2.0.0:

• A method is_supercombinator on Term that checks whether a lambda term is a supercombinator, i.e. just a depth-first search to check all the Vars.
• (more speculative) Since it's possible to Church-encode (or Scott-encode, etc) any algebraic data type, there could be a DSL for defining the "shape" of an algebraic datatype and then a function to convert this structure to lambda terms representing its Church-encoded (or Scott-encoded) constructors and accessors.

[ljedrz]

These are some great points! I'll start working on the first three. My current 2.0 branch is 2.0-fix (2.0.0 became a bit messy).

[ljedrz]

I'm done with compare and beta. I agree with the point on From implementations, but I'm not sure how to tackle them. I'm pretty happy with the current state of changes, so I'll merge the 2.0-fix branch and let you have a go at this one.

[billpmurphy]

Thank you for the changes. I'm not quite sure how the From implementations should be handled either. I'll see if I can find a design that I like.

[ljedrz]

After your last change the encoding features are no longer needed; now I'm wondering about the following potential changes and I'd like to hear your opinion on them:

• some functions are duplicated to enable both x.foo() and foo(x) calls; the latter variant is used much more often and it might be a good idea to just drop the former
• it might be a good idea to feature a build without any encodings (like the no_church build originally)
• rename *::numerals::plus to *::numerals::add
• rename *::numerals::pow to *::numerals::exp

[billpmurphy]

Nice, I like the direction of these.

• Completely agree. Which functions did you have in mind? beta, eval, and apply are the ones that jump out to me.
• Completely agree. Perhaps an encoding feature that is enabled by default, and if disabled the church, scott, and parigot modules are not built?
• Completely agree.
• In a lot of languages (such as Rust), exp is used to compute e^n and pow is used to compute m^n. So I think pow is appropriate here.

[ljedrz]

• yes, mostly those 3; their variants aren't exactly equivalent, so they'll need a bit of thought; there's also Term::app, I think it can be dropped as well
• agreed, done
• done
• agreed

[ljedrz]

I re-visited the reduction module and actually Term::apply could be dropped without any breakage and Term::eval doesn't have a reduction::eval equivalent (only a helper _eval function). What remains is the doubled beta. I'm thinking about changing Term::beta to Term::reduce or Term::beta_reduce that works like now and changing reduction::beta to a beta!() macro that utilizes it. What do you think?

In other news, I'm working on introducing the Stump-Fu encoding, also known as the embedded-iterators encoding, but I'm still very open to more 2.0 API changes.

[billpmurphy]

I agree with removing Term::beta and having onlyreduction::beta as either a function or a macro. Besides the cleanup of those functions and Term::app, I don't have any other suggestions at the moment for 2.0 API changes.

Interesting, I hadn't heard of that before. Lots of useful info in that paper!

[ljedrz]

Actually Term::beta and reduction::beta return different things: the former - the reduced statement and the latter - the number of reduction steps. I was thinking about renaming Term::beta to beta_reduce, but there's also Term::beta_verbose that would probably need to become Term::beta_reduce_verbose, which is a bit too verbose for my taste. As for turning reduction::beta into a macro it doesn't quite feel right, as a function is more suited for that purpose.

I'll sleep on it; maybe you have an idea how this could be improved?

[billpmurphy]

So right now we have:

• Term::beta - returns number of reduction steps
• reduction::beta - returns reduced term
• Term::beta_verbose - returns list of intermediate terms
• reduction::beta_verbose - returns list of intermediate terms

I think we can cut this down to:

• reduction::beta - returns reduced term
• reduction::beta_verbose - returns list of intermediate terms

Calling .len() on the output of beta_verbose gives you the number of reduction steps. Alternatively, if you think it's valuable to have a function that just returns the number of reduction steps, there could be a third function for that.

[ljedrz]

The counting version of beta is definitely faster and lighter, so it's better to leave it.

I did some tweaking and the current state is as follows:

• reduction::beta - reduces a Term and returns it
• reduction::beta_verbose - reduces a Term and returns all the reduction steps
• Term::reduce - reduces a Term and returns the reduction count

I agree that keeping the reduction::* variants is the better way - it gives them much better visibility in the docs (and these will probably be the most widely used functions).

As for Term::reduce, the name kind of fits a method; at times one might just want to be interested in reducing a term (without collecting anything) and just do term.reduce(...);, like in reduction tests.