When a+b+c does not equal c+b+a

http://ruru.name/entries/when-a-plus-b-plus-c-equals-c-plus-b-plus-a/

by meesterdude • 11 years ago

46 64 11 years ago

ColinWright3• 11 years ago

I thought this was going to be another example of floating point arithmetic "gotchas" similar to this:

  #!/usr/bin/python

  x = 1.
  a = 1.
  while a+x > a:
    x = x/2

  print x

  b = x
  c = x

  print a+b+c == c+b+a
  print (a+b)+c == a+(b+c)

Always interesting when the arithmetic system you use is non-commutative and non-associative.

*Edited to add the non-associative bit)

kuschku• 11 years ago

Which is the case for all vector × vector, vector × matrix and matrix × vector multiplications, for example.

(Taking math at university right now as part of studying compsci, non-commutative rings are annoying)

ColinWright3• 11 years ago

Yes, but at least they are all still associative. (Original comment edited to deal with that).

And non-commutivity is important. You can put on your socks then shoes, but get a different result if you put on your shoes then socks. In general you get different results in rotations if you change the order you do them. Similarly permutations.

Non-commutivity is important, it's just that most people don't expect addition to exhibit it. (And by definition, addition is still commutative in non-commutative rings)

anirudt• 11 years ago

On a first glance at the link, my guess was string concatenation.

rockdoe• 11 years ago

Being able to add timedeltas of a month seems like a spectacularly bad idea.

It's a rails extension.

http://stackoverflow.com/questions/2699902/get-next-previous...

zubspace• 11 years ago

It's actually quite useful, because for us human beings thinking in months is natural. Think about a user setting for some kind of web notification service:

How often do you want to be notified:

* Once per month

* Once each quarter of a year

* Twice a year

It's straightforward if you can add the number of months to the sign up date. You simply need to define the edge conditions. Example in C#:

  The AddMonths method calculates the resulting month and year,
  taking into account leap years and the number of days in a month,
  then adjusts the day part of the resulting DateTime object. If the
  resulting day is not a valid day in the resulting month, the last
  valid day of the resulting month is used.
  For example, March 31st + 1 month = April 30th.

https://msdn.microsoft.com/en-us/library/system.datetime.add...

I think ruby does the same.

jerf2• 11 years ago

In typed languages, I'd suggest a case could be made that once you add a "month" to a time, you should get a different type out that should either support a grossly reduced set of operations, or one that would require formal unpacking to produce a "real" datetime that would once again support normal operations. Months and years are dangerous things. (Days technically aren't constant either, but there's a lot of applications like billing where a leap second won't bother you at all if your month & year code just deal with them.)

mattmalin• 11 years ago

I also imagined floating point arithmetic problems when seeing the title. What is really happening here is that a, b and c may themselves have different values depending on the operation - as adding a month here isn't a fixed number of days as month lengths differ.

The article states it perfectly at the end though: "When doing math that deals with time, specifically different units of time, it can lead to unexpected results if you are not careful with the ordering". I think this can generally be extended to "when doing any math that deals with time, it can lead to unexpected results if you are not careful with everything"!

meesterdude6• 11 years ago

What is really happening here is that a, b and c may themselves have different values depending on the operation - as adding a month here isn't a fixed number of days as month lengths differ.

spot on; very much a human mistake, a false assumption of how things work.

JadeNB3• 11 years ago

"When doing math that deals with time, specifically different units of time, it can lead to unexpected results if you are not careful with the ordering"

Not arguing with you, but with the poster: I think that a deeper lesson might be the important realisation that, unlike 'day' or 'hour', 'month' is not a unit of time! (At least, not any more than 'moment' is. (I know, I know, https://en.wikipedia.org/wiki/Moment_(time), but you know what I mean.))

cies2• 11 years ago

unlike 'day' or 'hour', 'month' is not a unit of time!

Not a 'fixed unit' of time. Where I define 'fixed' as being always of the same size (like gram or meter).

My next thought is that day is also not fixed in case of daylight saving and leap seconds. A day has many definitions: astronomical, 24 hours, calendar, etc.

Maybe we can also see this problem with 'hour'; but in that case it would be more contrived.

Bottom line: programming time is hard, be aware of that.

See this post for some common pitfalls:

http://infiniteundo.com/post/25326999628/falsehoods-programm...

mcherm• 11 years ago

Or more accurately, "Doing math that deals with different units of time will inevitably lead to unexpected results."

If you gather 6 different company executives and business requirement authors and ask them all to explain what it means to be "one month and 5 days later" than a given date, I guarantee you will get at least 3 or 4 different answers. No matter WHAT your code implements, it will be unexpected to some users.

As a developer, when I encounter a requirement like this one I feel it is my duty to push back on the requirement. I won't ACCEPT a requirement like "the grace period is a month and five days", and will instead (try to) force those writing the requirements to specify something clear like "the grace period is 35 days" or "the grace period is until 5 days after the same same date in the following month" (still somewhat misleading).

I have been working in software development within big business (banks, mostly) for quite some time now, and I frequently observe that developers -- probably because of the nature of their job -- tend to be good at thinking of something clearly and precisely, while those writing requirements tend to be fuzzy on the specifics but better able to understand the overall picture. Working at the interface between the two, my job is often to get each side to step up to the level of the other.

PeterisP• 11 years ago

The same approach is in legal issues. Words "a month and a five days" shouldn't ever get past a lawyer, you'd get "35 calendar days" or more likely something like "25 business days as defined by XXX; if the notice is submitted past 18:00 then it's treated as if submitted on the next business day"

Dewie32• 11 years ago

The article states it perfectly at the end though: "When doing math that deals with time, specifically different units of time, it can lead to unexpected results if you are not careful with the ordering". I think this can generally be extended to "when doing any math that deals with time, it can lead to unexpected results if you are not careful with everything"!

Another idea: don't dress up things that don't have anything to do with conventional math as conventional math. Using operands who's value depends on the value of the expression evaluation up to this point (I'm guessing left to right) is an aberration.

broken_symlink• 11 years ago

I was thinking quaternions when I saw the title.

ColinWright3• 11 years ago

But adding quaternions is both associative and commutative.

nathanvanfleet• 11 years ago

This was a bit misleading. It's about date handling, which is a complex scenario well outside 1 + 1.

meesterdude6• 11 years ago

I did not intend to mislead; i was thinking more about objects and ruby than mathmatics with the title

Dewie32• 11 years ago

I guess "misleading operator overloading" would be too boring, huh.

Moru• 11 years ago

I was directly thinking dates when I saw the headline :-)

I too have had my share of problems with date handling. One year is not always 52 weeks, A month is never 30 days, most days have 24 hours (but not all of them) and so on...

Not to mention the famous D/M/Y, M/D/Y, Y-M-D ordering problem...

mauricemir2• 11 years ago

Me to I recall fixing a bug with a major uk company BACS transfer tape where the accounts receivable system was instant that you could have more than 365 days in a year.

Which meant that we where unable to collect any Direct debits for 3/4 of year!

meesterdude6• 11 years ago

Maybe worth mentioning: this was a bug that existed for ~2 years before I started on the project. It's easy for this kinda subtlety to slip past review and debugging.

jerf2• 11 years ago

I once worked for a failed startup, where the CEO insisted that we needed to write code to deal with billing people on arbitrary days of the month. I really wanted to do it on just the first of the month unconditionally, because I didn't think this was a good use of our time [1], but I was overridden.

I had a Perl library that was much like the Ruby one, where it could add a month. Having by then caught the unit testing bug, I wrote my billing code, with just a couple lines as the payload, then wrote myself a unit test that simulated a customer joining us on any of the possible 731 days they could do so (365 days in a non-leap year, 366 in a leap year), then ran through two years of billing, validating that we billed them on a day as close as possible to the correct day (i.e., Feb 28th if you were on a 30 cycle), never missing a bill or double-billing.

Sounds simple, right?

In my nearly 20 years of coding, this is the single most frustrating bit of code I have ever tried to write and debug. Just absolutely unbelievable. Billing code that worked perfectly, except on months with 30 days joined in a leap year. Billing code that worked perfectly, except if you joined on a 31-day month that was followed by another 31-day month (which is July, but the bug was essentially caused by that problem). And no matter how I beat the code, no matter how I fixed one bug, some other blasted corner case popped out.

Even now as I write this, I say to myself "surely this isn't that hard of a problem"... but it was. It really should have worked, but it didn't.

Calendars are evil.

And, what prompted me to reply, it would have been really easy for any version of this code to ship and not be noticed for a long, long time, if I hadn't written the exhaustive test cases I did. There was code that literally worked in 99.5% of the cases, and would only have broken a couple of times a year, and probably would have been written off as flukes or mysteries.

Should you ever find yourself in a similar situation, I strongly recommend the exhaustive testing approach. You will be stunned what crap you find in your seemingly-simple code for handling dates. This also really solidified my view on the utility of automated/unit testing. You simply can not manually test a 731-element matrix, and I was getting an incredibly rich array of varying failures across that matrix, in billing code, which is very important code.

[1]: This is many years ago, before there were so many great billing services off the shelf available, and we still had a significant challenge to be able to take payments at all. And lest I unhumbly make myself sound wiser than I was/am, I learned a lot about what code is and isn't worth writing at that startup... the hard way. Mercifully I don't feel my gross errors really contributed to the failure in the end... the startup died of one-more-feature-before-we-can-release-itis: https://news.ycombinator.com/item?id=9640335

meesterdude6• 11 years ago

Thank you for this comment! that certainly sounds like a nightmare of edgecases. The first of the month certainly seems like the better way to go!

This was sorta like that - specs would fail some days, but not others. The code worked, but the tests failed seemingly randomly.

jobigoud• 11 years ago

That's interesting because if I understand the bug correctly, it should have failed as soon as you performed the test less than 5 days before the end of the current month. (Except in December and July for which the next month has the same number of days in it.).

meesterdude6• 11 years ago

if i recall, it was a bug that would come and go from our tests depending on when you ran them. Sometimes the math worked out, other times it was off. We knew the code worked, but couldn't figure out why the specs kept failing for it randomly.

thebouv• 11 years ago

Date math, calendars and all that is lumped in there together: my most hated of programming tasks.

Second most hated: anything to do with maps.

Seems like every new client or job I take on, I'm fixing or building a calendar or map.

tim333• 11 years ago

tl;dr

Time.now + 5.days + 1.month == Time.now + 1.month + 5.days

Isn't always true because months have different lengths

bobbyadamson• 11 years ago

Yeah I feel like this article took a really long time to say just this.

bazzargh2• 11 years ago

That expression wouldn't always be true even if months did have the same lengths. Two calls to the clock in the same expression are not guaranteed to return the same time.

In the article, that problem is papered over by using string equality. That makes the problem much less likely (because it only occurs at rollovers of seconds) but it will still happen. Tests like this one - has a subscription expired? - should use inequalities, since that's all that's needed and it won't contain heisenbugs like the above.

Edited to add - just to demonstrate:

   irb(main):045:0> i=0; loop { i=i+1; raise "#{i}" unless Time.now.to_s == Time.now.to_s; }
   RuntimeError: 61473

quesera• 11 years ago

Was hoping for something more surprising. Dates and times are fertile ground.

Rephrased, this problem is that "unit quantity + container quantity yields different results when container quantity varies".

On Feb 26th:

  > Time.now + 1.month + 5.days => Mar 31st
  > Time.now + 5.days + 1.month => Apr 3rd

...

IIRC, #month is a Rails-ism, not part of Ruby.

unmagnet• 11 years ago

Definitely happens with natural language judgementalistically.

mauricemir2• 11 years ago

yes your point is? Date math is not the same as arithmetic

meesterdude6• 11 years ago

and arithmetic is not the same thing as sending + to different objects in ruby :)

wz1000• 11 years ago

It really depends on how you expect '+' to behave.

When seeing '+', I immediately think of a semigroup operation. I would expect it to be associative but not necessarily commutative.

monochromatic2• 11 years ago

Is it even associative? I don't use Ruby, but it seems like this might not even be defined:

    5.days + 1.month

IceyEC2• 11 years ago

5.days + 1.month => 1 month and 5 days

amelius• 11 years ago

Operator overloading sucks. Especially when the expected properties such as commutativity do not hold.

JoeAltmaier• 11 years ago

Agreed. Operator overloading of arithmetic is used as the tutorial example with complex numbers. But its utility starts and ends there.

I overload conversions of type, to simplify argument passing. Maybe I shouldn't even do that.

jacquesm• 11 years ago

Vectors, Matrices count too I think.

agentultra3• 11 years ago

There are some exceptions. For geometric primitives such as matrix addition I might allow it. For complex container types like a "month," it's definitely a show-stopper.

codygman• 11 years ago

what are some specific disadvantages of operator overloading in the instance of subtracting or adding months together?

rhpistole• 11 years ago

Operator overloading always looks like a clean solution, but complexity finds a way to leak through.

Avoid it, unless you're really overloading things that always behave.

DannoHung4• 11 years ago

Is it really overloading that's the problem here? Even if you used method names to do this, you'd still have to deal with the fact that the operation being performed is non-commutative.

I don't know that there is a way of expressing such a restriction even if you were using dependent types in such a way as to prevent shooting yourself in the foot here. Possibly you could not implement the month or year span elements altogether and only allow addition of days or seconds?

erdeszt2• 11 years ago

But nested method calls don't imply commutativity while addition does. So the code is misleading.

noobie• 11 years ago

I had a physics teacher that used to tell us:

    vache + mouton = la honte

which translates to

    cow + sheep = shame

point being, if you add up things that don't match, i.e. do not have the same unit/dimension, you should expect some weird mistakes.

lucb1e• 11 years ago

So if I sign up in February I get 28 days to enjoy the service; if I sign up in March I get 31? That seems like the fundamental problem here.

cies2• 11 years ago

It all stems from that `+` in Ruby is not something mathematical. It is merely a method that needs to be defined on the expression that it follows:

    Time.now.+(1.month).+(5.days)

Or:

    Time.now.send(:"+", 1.month).send(:"+", 5.days)

`Time.now` evaluates to an object of the class `Time`, which implements the method `+`.

If you are looking for a language basis itself more on "laws" then on "message passing", I found this is Haskell.

In Haskell `+` is a function that need to be implemented for all types in the `Num` type-class. `+` can only add two `Num`s of the same type (and evaluates to a value of that specific type), thus explicit conversion is needed. See the docs here:

http://hackage.haskell.org/package/base-4.8.0.0/docs/Prelude...

dsugarman• 11 years ago

Tldr; a month is not a constant amount of days, it depends on the month of the year

M2Ys4U• 11 years ago

And the year the month is in.

jbert• 11 years ago

A related one which I found is A + B - B != A

In pretty much the same case, where A==some time and B == 1 month

This came up in calculations for monthly subscriptions, trying to reach back in time to work out pro-rata charges for changing subscription details part way through a month.

rmah• 11 years ago

Hah, you think normal date math is bad, try dealing with the various calendars used in finance. US 30/360, Euro 30/360, Actual/365, Actual/360, etc, etc. That stuff will make you tear your hair out.

When a+b+c does not equal c+b+a

Related Stories