What a Bijection is not

[tonymorris]

On the front page, the definition for bijection is given:

A Bijection is an invertible function that converts back and forth between two different types, with the contract that a round-trip through the Bijection will bring back the original object.

This is not true. At first I thought, this is just a matter of correcting the definition. However, what I saw next were code examples like:

scala> Bijection[Int, String](100)
res2: String = 100

This is when I fell over.

At least I can see that the code has taken this incorrect definition seriously! I have picked myself up now, so let me clarify things.

First, a bijection is always injective and surjective. The code above is not a bijection, because it is not even a surjection. In fact, it is not possible to product a surjection from Int to String, let alone a bijection. However, in this case, there is an injection from Int to String and I expect this is the implementation. Note that this is an injective, non-surjective (and therefore, non-bijective) implementation.

Further, there are open issues such as "integration with Lens" #4. While indeed there is an arrow (homomorphism) from Bijection to Lens[1], since much of what is implemented here are not bijections, then any attempt to implement this transformation will result in "not a lens." It is just asking for even more trouble.

My primary suggestion is that all values of the type Bijection are bijective. This should include the removal of all non-bijective values of the type Bijection. Also, the written definition of bijection requires correction as it is very misleading. Finally, it might be worth considering a project split into "injection" and "surjection."

[1] Example of an implementation here https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/BijectionT.scala#L24

[jonsterling]

+1. This reeks of the cargo cult. “Bijection” is a cool word, but it most certainly does not mean “a function paired with a partial inverse”.

[cocoatomo]

+1

[stew]

I'm not even sure that "injection" and "surjection" would be correct, either. Can you correctly call a partial function surjective?

Perhaps the correct thing is to just not abuse the well defined term "bijection" and use a term which is correct for what is being described, like 'invertable'?

[mariusae]

Programming isn't math, and sometimes we hoist vocabulary that confers similar meanings. For example, what we call a "function" in programming is usually a partial function, so I think it's fine (and not unexpected) that what we call a Bijection is in fact also partial.

[jonsterling]

The precedent set by the abuse of “function” does not excite me about further abuse, especially on a term that is well-understood already by the sort of people who use it, as opposed to function. I think “invertible” carries a bit less technical baggage and would probably suit your purposes better at least than “bijection”.

[johnynek]

I invite anyone who is more interested in type theory than building systems and analyzing data to use another library. This is ultimately practical code.

We should have said: You should write your Bijection correctly, BUT (since the scala type system cannot enforce this rule anyway) if violated, AT LEAST PLEASE make it injective from A -> B.

That said, we are fully aware of the limitations of these words in describing Bijection. In fact, there are a host of other issues that make these far from mathematical functions. For instance, we cannot guarantee that exceptions won't be thrown inside implementations within the scala type system. We can't guarantee there will not be side-effects, etc...

It is certainly far preferable for an implementation to be surjective and injective. Most of the implementations we wrote are surjective and injective. We could easily accomplish this for the poorly chosen example [Int, String] by introducing a type such as StringInt(stringrep: String). Then the Bijection[Int, StringInt] is injective and and surjective. This is just reducing the output set to a range that the function will be a bijection. We did this in a few cases (Array[Byte], GzippedBytes for instance), but the case of Int <=> String is clear enough that we relaxed a bit.

I know there are people who obsess about the deviations of words used in one context and another. Words have meaning, but they also have flexibility. We are their masters, not the other way around.

[eigenvariable]

At the end of the day, this is an objection about nomenclature, not semantics. Assuming that the composition of both functions really is the identity in both directions, a more mathematically precise definition would be "isomorphism" (or just "iso") and instead of "bijection," which is the correct notion of isomorphism in the category of sets (but not necessarily types).

That said, even as a certified theory wanker and pedant, I don't really care about this all that much. What matters is the semantics of the library, and this looks like a useful one.

Of course, in the example given above, the "bijection" between "Int" and "String" isn't even technically an isomorphism, since the coercion from String to Int isn't a total function. To this I say: the functions given are isomorphisms, but between Int and a subset of the type String. Since Scala's type system doesn't (yet?) have refinement types, it's only reasonable to tolerate a certain amount of imprecision, the same way that Haskell programmers tolerate the use of the word "monad" even though Haskell's type system isn't sophisticated enough to statically verify that the monad laws hold for any given instance of that type class.

[seanparsons]

@johnynek That whole first line honestly is either offensive or misguided, that's not the reason for the issue and starting from that kind of tack isn't constructive at all.

If the instances do satisfy the laws of a bijection then by default that's much more useful as you can trust that composition isn't going to get you in trouble for example. A contrived example would be that composed you have A -> C from A -> B and B -> C, it can be the case that A -> C would be a bijection, but as A -> B isn't bijective and throws an exception in some cases then you can't rely on that.

[jonsterling]

Mr. Boykin, this is not about whether it is reasonable to allow partial or impure functions; that's a totally different argument. This is entirely a matter of semantics, which I do not say lightly, but rather hold as extremely important: we can all agree that it is better to have consistent terms that everyone has agreed upon, than to do the exact opposite of that. That point being taken as an axiom, we can see clearly (and with very little room for disagreement) that it would be better for this library to be named something different, or for its contents to be more limited than they currently are, should its name remain the same.

I'm not particularly interested in arguing with the sort of person who does not place value in using words for the things they are universally agreed upon to denote, as opposed to doing the opposite and reclaiming words for different purposes in a way that can only confuse and perplex.

With that in mind, I hope you will follow our advice! I'm sure anyone here would be happy to answer any questions you might have in the process.

Wishing you the best,
Jon

On Jan 9, 2013, at 11:33 AM, "P. Oscar Boykin" notifications@github.com wrote:

I invite anyone who is more interested in type theory than building systems and analyzing data to use another library. This is ultimately practical code.

We should have said: You should write your Bijection correctly, BUT (since the scala type system cannot enforce this rule anyway) if violated, AT LEAST PLEASE make it injective from A -> B.

That said, we are fully aware of the limitations of these words in describing Bijection. In fact, there are a host of other issues that make these far from mathematical functions. For instance, we cannot guarantee that exceptions won't be thrown inside implementations within the scala type system. We can't guarantee there will not be side-effects, etc...

It is certainly far preferable for an implementation to be surjective and injective. Most of the implementations we wrote are surjective and injective. We could easily accomplish this for the poorly chosen example [Int, String] by introducing a type such as StringInt(stringrep: String). Then the Bijection[Int, StringInt] is injective and and surjective. This is just reducing the output set to a range that the function will be a bijection. We did this in a few cases (Array[Byte], GzippedBytes for instance), but the case of Int <=> String is clear enough that we relaxed a bit.

I know there are people who obsess about the deviations of words used in one context and another. Words have meaning, but they also have flexibility. We are their masters, not the other way around.

—
Reply to this email directly or view it on GitHub.

[johnynek]

@seanparsons I didn't mean to offend, but I believe there are people who are honestly more interested in purity than practicality.

@jonsterling I'm not particularly interested in arguing at all.

Perhaps the point that has been lost here is that in a few cases are injectiions (Numbers to String and Numbers to Array[Byte], I don't remember if there are any other incorrect examples in this code). In those cases, I believed the types were obvious enough for people to understand the limitations.

Generally these instances (way more than half, I believe) are bijections [Int, java.lang.Integer], [List[Int], java.util.List[Int]], and many, many more.

Let's have a data driven discussion: if you are unhappy with this code, and feel the need to engage in discussing this code, let's make a count of the number of Bijection[A, B] implementations are actually injections, and how many are true bijections. It sounds like some people are upset that this number is not zero. I will accept a number greater than zero.

Pull requests are, in my opinion, the best way to engage here. Add value to the library or ignore it.

If someone wants to introduce an Injection type, that would be fine. But we can't lose the plumbing we've got (implicit resolution of most obvious injections, ability to connect them and ability use them with Builder to work on collections).

[sritchie]

@jonsterling, I'm completely with you on this one. Professor Boykin is out of line. Unfortunately, the misunderstanding extends deeper than the definition of bijection.

I'd like to go back to the initial example:

scala> Bijection[Int, String](100)
res2: String = 100

As a member of the knitting community, I find the use of String here both confusing and inaccurate. Am I to understand that this library gives scala the power to materialize abstract concepts like Int into physical fiber?

The cup of ignorance overfloweth.

[eigenvariable]

@seanparsons FWIW, as someone who is interested in both type theory and systems, and who has helped design and implement both professionally, I don't find @johnynek's comments offensive.

@jonsterling I think you're failing to consider something here, which I tried to point out in my comment above, but perhaps not clearly enough. Let me try again.

As you know, every injection f from A to B induces a bijection from A to the image of f (which is, by definition, a subset of B). We all agree that the coercion from Int to String (call it i2s), is an injection, and therefore induces a bijection between Int and the image of i2s; call this image String'.

My point is that, while the conversion from String to Int (call it s2i) is a partial function, if we restrict its domain s2i to String', then s2i is both a bijection and the inverse of i2s.

What this means is that the functions that implement Bijection[Int, String] are in fact bijections, they just aren't bijections between the set of values in Int and the set of values in String; they're bijections between the set of values in Int and the set String'.

Scala's type system isn't sophisticated enough to easily and naturally specify String' as a subtype of String (although, as an aside, I believe that refinement types would probably be the right way to do this, just in case anyone out there wants to make Scala's type system even more complex than it already is). So what the authors of the Bijection library have done is something that is perfectly reasonable, both in theory and in practice: they use the type String as a proxy for String', leaving it up to the consumer of this library to Be Careful not to try to convert strings like "hello world" into Int. This is exactly the same approach taken by the "monad" type class in Haskell: not all type constructors in the "monad" type class actually satisfy the monad laws, so it's up to the consumers of that type class to Be Careful and check the monad laws by hand.

[jedws]

@eignevariable Please see Shapeless and/or Scalaz for ways to tag a naked type (eg. String) with a qualifier (such as say NumericInt). That way you can actually make sure that the type system captures the correct subset of Strings that qualify.

Then, you can use a String => Option[String @@ NumericInt] as well as the Int => String @@ NumericInt. This first function is sufficient to prove that the initial string is of the right type.

[krishnanraman]

Speaking as a humble math major, one of the big reasons you'd want bijections is because you get a ton of equinumerous proofs for free. The machinery is the standard way to prove for eg, that two sets as diverse as R & R^2, have identical cardinality. If you don't care for equinumerousity, then why bother with all this ? K&R were both applied mathematicians & they probably realized, as do most newbie C programmers, that atoi(sprintf(x)) == x, has a bijective feel to it. Yet they didn't put atoi & sprintf into a Bijection struct or somesuch. A hotchpotch of casting functions do not a bijection make. Forget evil strings like "foo" or "123.45", I can't even do long=>string=>int, on completely valid longs in your own Bijection library, because of numeric overflow when the long tries to become an int. Then why call it bijection, when you can't even freely move around the codomains ? Give it another name & move on.

[tac-tics]

A better name for this would be a "cast" or "coercion".

As others have argued, "bijection" is a poor choice of words. In the example above, Int's toString method is an injection, but not a surjection.

You don't need to know any math, though. A bijection is just a function that preserves information in both directions. The problem here is that the example preserves information in the Int -> String direction, but not in the String -> Int direction.

For those arguing that "different people use different words differently," please choose your words carefully. The term bijection is around 130 years old, and being a technical word, it has always meant a very specific thing (that is not capture by this package). The terms "coercion" or "cast" are less technical, and are more familiar to programmers. They make much better candidates.

[johnynek]

@jedws That's a good approach. So far we handled this with classes like Base64String.

https://github.com/twitter/bijection/blob/develop/bijection-core/src/main/scala/com/twitter/bijection/BinaryBijections.scala#L46

I'd love half the energy of this thread on pull requests.

[djspiewak]

"Bijection" is absolutely a terrible word choice. I think the main reason everyone is jumping on this is it smacks of partial-understanding that is being needlessly proliferated. I know this would particularly annoy @tonymorris. "Coercion" is a far, far better term for what is happening here. It reflects the lossy, ill-defined nature of the typeclass.

More importantly though, we should probably all bear in mind the fact that this code is not just poorly named, but actively dangerous. Imagine if I had something like this in my codebase:

implicit def string2Int(str: String) = str.toInt

12 + "42"      // because…JavaScript!

Do you really think that would get past the code reviewers? We look at the above and (rightly) consider it terrible for a good reason: it is fraught with pitfalls and encourages extremely bad code. It is the classic case of a tool which makes a highly specific case easy while dramatically inhibiting the common cases.

Writing an implicit "Bijection" typeclass which does this same thing is marginally less terrible, but only because the compiler won't be auto-magically swapping between the types in question. When you provide such a typeclass, you are effectively making the assertion that the above function could be written and would be totally valid. In other words, someone could with total validity write the following function:

implicit def coerce[A, B](a: A)(implicit bi: Bijection[A, B]): B = bi(a)

Given an instance of Bijection[String, Int], we have re-derived the implicit String => Int function from above, which is (I hope) uncontroversially terrible. The point here is that there is nothing wrong with the coerce function, aside from some flexible best-practices. The problem is in the fact that an instance of Bijection[String, Int] exists at all.

Code aesthetics aside, this sort of thing is just asking for trouble for the same reason that an implicit String => Int is asking for trouble. It's bad naming, bad code, and an extremely poor example for those looking to correctly use the Scala language.

[b]

Call it idempotent.

[tonymorris]

This is not happening.

[djspiewak]

Call it idempotent.

Except it's not. Idempotency is defined as \forall a . f(a) = f(f(a)). Bijection doesn't even have the types necessary to make that work.

[johnynek]

@djspiewak You are right that the Long <=> String Bijection should be changed Long <=> LongString, etc.. or using the approach that of: #41 (comment) Pull request?

[isomorphisms]

with the contract that a round-trip through the Bijection will bring back the original object.

It sounds like you are talking about Involutions. http://math.stackexchange.com/questions/85854/whats-the-name-for-the-property-of-a-function-f-that-means-ffx-x

Also, bijections are not necessarily between different types. f(x)=x+1 is a bijection from Int → Int or Float → Float for example.

[sorenmacbeth]

I've submitted a pull request #43 that I think will clear up a lot of the confusion and objections pointed out here.

[jedws]

@johnynek submitted PR #44 that contains working tag support, not complete (ha, not complete! doesn't pass tests, I'll fix that…) yet but proves the approach

[johnynek]

Let's talk more at NEScala! http://nescala.org/2013/talks#42

[odf]

For what it's worth, I tend to understand the fact that most "functions" in programming are really partial functions as a result of the limitations of conventional type systems, which are not typically capable of expressing the true domains of functions, or, if they are, do not make it particularly easy or convenient. In the same vein, I would be quite happy as a mathematician to accept a function as bijective as long as it were a true bijection between its actual domain and its actual image (or in other words, if it were injective), with the understanding that the given type signature does not necessarily specify either one accurately, and provided that the actual domain and image are either obvious or well documented.

Whether this is also acceptable to the Scala community is of course a matter of language culture, which I do not pretend to have any deeper knowledge of. A more accurate name would be InjectivePartialFunctionWithAnInverseProvided, but that seems somewhat verbose.

[jedws]

see Haskell Lens library's Prism http://hackage.haskell.org/packages/archive/lens/3.7.1.2/doc/html/Control-Lens-Prism.html

"It may help to think of this as a Iso that can be partial in one direction."

[johnynek]

I've merged Jed's patch. If someone wants to take a minute to improve the readme, that would be a great pull req.

Also, if there are any remaining issues beyond the String issues that Jed fixed (I know several, but a second pair of eyes would be great), please make a pull req on those.

Public thanks to Jed: your contribution is the kind of thing I hope for when I work on github projects.

[alexy]

Perhaps it can just be called seesaw ?

[tonymorris]

I really want to be clear about the motivation for this bug point.

The issue of naming is highly irrelevant. This is not about the misappropriation of a name. It may be called wibbley-doo and the problems of this bug report remain.

I assert, as things currently stood at the time of writing (and I do not know about now), there is a forced choice:

• The library continues on as-is, resulting in endless significant bugs in practice. Being acutely familiar with how much some people like to brag that they "ship real-world code", I think this particular choice should be considered carefully.
• The library removes all non-bijective bijections and perhaps introduces bijective bijections that are not yet implemented so as to give rise to composition and most importantly, code that works in practice. This would be my choice at least for the short-term. As for the (non-bijective) left-invertible functions, they can be written on another data type, then we will get composition and absence of bugs (neither of which we have now). However, there are some functions in this library that do not belong at all.
• The restrictions are loosened on what it means for these functions. However doing so means we do not have a library beyond, "a re-implementation of existing library functions in a different namespace."

I have no position on which choice to make of the above three, but you must choose one.

At the time of writing this bug report, I thought it would be enough to point out, "hey, almost of these are not bijective and this is going to bite you in the arse in production." I expected a carefully considered response that examined those practical implications and replied accordingly. I made this assumption because I think the consequences are rather obvious. You only need to come up with one or two parametric library functions and it is game over.

Perhaps it is a worthwhile exercise to write this client code out and observe the consequences.

Sorry for the rant and I hope not to stir the nest again.

[sritchie]

@tonymorris, I think this would all be easier to digest if you implemented your ideas and submitted them as a pull request. Can we move this discussion over to that pull req when you send it over?

I'm interested in these points and look forward to seeing how they affect the code.

Sam Ritchie
703.662.1337
@sritchie

On Friday, January 11, 2013 at 3:51 PM, tonymorris wrote:

I really want to be clear about the motivation for this bug point.
The issue of naming is highly irrelevant. This is not about the misappropriation of a name. It may be called wibbley-doo and the problems of this bug report remain.
I assert, as things currently stood at the time of writing (and I do not know about now), there is a forced choice:
The library continues on as-is, resulting in endless significant bugs in practice. Being acutely familiar with how much some people like to brag that they "ship real-world code", I think this particular choice should be considered carefully.
The library removes all non-bijective bijections and perhaps introduces bijective bijections that are not yet implemented so as to give rise to composition and most importantly, code that works in practice. This would be my choice at least for the short-term. As for the (non-bijective) left-invertible functions, they can be written on another data type, then we will get composition and absence of bugs (neither of which we have now). However, there are some functions in this library that do not belong at all.
The restrictions are loosened on what it means for these functions. However doing so means we do not have a library beyond, "a re-implementation of existing library functions in a different namespace."

I have no position on which choice to make of the above three, but you must choose one.
At the time of writing this bug report, I thought it would be enough to point out, "hey, almost of these are not bijective and this is going to bite you in the arse in production." I expected a carefully considered response that examined those practical implications and replied accordingly. I made this assumption because I think the consequences are rather obvious. You only need to come up with one or two parametric library functions and it is game over.
Perhaps it is a worthwhile exercise to write this client code out and observe the consequences.
Sorry for the rant and I hope not to stir the nest again.

—
Reply to this email directly or view it on GitHub (#41 (comment)).

[sritchie]

Closing this, unless you guys have more comments.

[johnynek]

For those interested in the code, we have adopted three solutions to the issues here:

1. remove any non-bijective implementations of the Bijection trait (these were a few concerned with serialization, which is obviously not bijective).
2. Jed's A @@ Rep[B] solution.
3. add an Injection trait which is A => B, B => Option[A].

If you see any remaining bugs, please make a pull req.

Thanks.

[jedws]

Good stuff!