Why does multiplication only short circuit on one side

Question

I was messing around with fix and after messing around with it I came across some weird behavior, namely that 0 * undefined is *** Exception: Prelude.undefined and undefined * 0 is 0. Which also means that fix (0 *) is *** Exception: <<loop>> and fix (* 0) is 0.

After playing around with it it seems like the reason is because it is non-trivial to make it short circuit in both directions, as that doesn't really make much sense, without some sort of weird parallel computation and start with the first non-bottom returned.

Is this kind of thing seen in other places (reflexive functions that aren't reflexive for bottom values), and is it something I can safely rely on? Also is there a practical way to make both (0 *) and (* 0) evaluate to zero regardless of the value passed in.

Platonism

WHAT? That is awesome! – Dairen

This is exactly the point that makes denotational semantics not completely equivalent to operational semantics, i.e. not fully abstract. The former can represent a function f with f undefined 0 = 0 and f 0 undefined = 0 while the latter cannot. Language implementations follow operational semantics, thus making it impossible to define such an f without some trickery. – Fennell

Answer 1

Your reasoning is correct. There is an unamb package providing tools for the sort of parallel computation you refer to. In fact, it offers Data.Unamb.pmult, which tries, in parallel, to check whether each operand is 1 or 0, and if so immediately produces a result. This parallel approach is likely to be much slower in most cases for simple arithmetic!

The short-circuiting of (*) occurs only in GHC version 7.10. It came about as a result of changes to the implementation of the Integer type in that GHC version. That extra laziness was generally seen as a performance bug (as it interferes with strictness analysis and can even lead to space leaks in theory), so it will be removed in GHC 8.0.

Cannes

Seems like 7.10 had several surprising "features". :/ – Empery

Can you explain the performance bug part. Surely if you KNOW one of the values is 0 it makes no sense from a performance standpoint to evaluate it as well. Can't you just toss it into the abyss at that point? – Platonism

@semicolon, GHC uses strictness analysis (specifically, a version it calls demand analysis) to figure out when a value will always or never be evaluated. Knowing either of these is tremendously useful for optimization. Sometimes (e.g., with &&) users expect and rely on short-circuit behavior. In many other situations, the savings in unusual circumstances don't begin to pay for the losses in other ones. – Cannes

@Cannes Ah I see. So if it is always needed it can be executed whenever GHC feels like executing it and also there won't be any unnecessary thunk accumulation? – Platonism

@semicolon, something like that, yeah. I don't know too many details, but GHC can use this, for instance, to (effectively) replace foldl by foldl' in many cases, because it might as well just perform an operation if it knows it will have to eventually. And if it sees that something never gets used, it can avoid allocating space for it as well. – Cannes

Answer 2

Take the following for example

(if expensiveTest1 then 0 else 2) * (if expensiveTest2 then 0 else 2)

You have to choose a side to evaluate. If expensiveTest2 is an infinite loop, you will never be able to tell whether the right side is 0 or not, so you can't tell whether or not to short circuit the right side, so you never get to look at the left side. You can't check if both sides are 0 at once.

As for whether you can rely on short circuiting to act in a certain way, just keep in mind that undefined and error acts exactly like an infinite loop as long as you don't use IO. Therefore, you can test short circuiting and laziness using undefined and error. In general, short circuiting behavior varies from function to function. (There are also different levels of laziness. undefined and Just undefined may give different results.)

See this for more details.

Dairen

Answer 3

Actually, it seems that fix (* 0) == 0 only works for Integer, if you run fix (* 0) :: Double or fix (* 0) :: Int, you still get ***Exception <<loop>>

That's because in instance Num Integer, (*) is defined as (*) = timesInteger

timesInteger is defined in Data.Integer

-- | Multiply two 'Integer's
timesInteger :: Integer -> Integer -> Integer
timesInteger _       (S# 0#) = S# 0#
timesInteger (S# 0#) _       = S# 0#
timesInteger x       (S# 1#) = x
timesInteger (S# 1#) y       = y
timesInteger x      (S# -1#) = negateInteger x
timesInteger (S# -1#) y      = negateInteger y
timesInteger (S# x#) (S# y#)
  = case mulIntMayOflo# x# y# of
    0# -> S# (x# *# y#)
    _  -> timesInt2Integer x# y#
timesInteger x@(S# _) y      = timesInteger y x
-- no S# as first arg from here on
timesInteger (Jp# x) (Jp# y) = Jp# (timesBigNat x y)
timesInteger (Jp# x) (Jn# y) = Jn# (timesBigNat x y)
timesInteger (Jp# x) (S# y#)
  | isTrue# (y# >=# 0#) = Jp# (timesBigNatWord x (int2Word# y#))
  | True       = Jn# (timesBigNatWord x (int2Word# (negateInt# y#)))
timesInteger (Jn# x) (Jn# y) = Jp# (timesBigNat x y)
timesInteger (Jn# x) (Jp# y) = Jn# (timesBigNat x y)
timesInteger (Jn# x) (S# y#)
  | isTrue# (y# >=# 0#) = Jn# (timesBigNatWord x (int2Word# y#))
  | True       = Jp# (timesBigNatWord x (int2Word# (negateInt# y#)))

Look at the above code, if you run (* 0) x, then timesInteger _ (S# 0#) would match so that x would not be evaluated, while if you run (0 *) x, then when checking whether timesInteger _ (S# 0#) matches, x would be evaluated and cause infinite loop

We can use below code to test it:

module Test where
import Data.Function(fix)

-- fix (0 ~*) == 0
-- fix (~* 0) == ***Exception<<loop>>
(~*) :: (Num a, Eq a) => a -> a -> a
0 ~* _ = 0
_ ~* 0 = 0
x ~* y = x ~* y

-- fix (0 *~) == ***Exception<<loop>>
-- fix (*~ 0) == 0
(*~) :: (Num a, Eq a) => a -> a -> a
_ *~ 0 = 0
0 *~ _ = 0
x *~ y = x *~ y

There is something even more interesting, in GHCI:

*Test> let x = fix (* 0) 
*Test> x 
0
*Test> x :: Double 
*** Exception: <<loop>>
*Test>  

Kunin

Eh, that last is just the combo of NoMonomorphismRestriction with defaulting. The rest of your answer is great detective work. – Cannes

@Cannes While you are right that it makes perfect sense, I still think it is a pretty interesting. If you were a really bad person you could return any arbitrary Num a => a but make it fail when used as anything other than an Integer. By just doing fix (* 0) + retVal. – Platonism