We interrupt the irregularly scheduled philosophical posts for some programming memes:
Over the last few days, the Internet has divided itself over what the value of the expression 8÷2(2+2) should be. Some say it should be evaluated as (8÷2)×(2+2) = 16. Some say it should be evaluated as 8÷(2×(2+2)) = 1.
At the risk of belaboring the obvious, the core dispute here is not really mathematical. There is not some sequence of mathematical operations that produces some number, where mathematicians disagree about what number it produces. Instead, this is a dispute about mathematical notation: what sequence of mathematical operations the expression corresponds to the way it’s written. Specifically, it is a dispute about whether multiplication written as juxtaposition (how “2” is written right next to “(2+2)”) has strictly higher precedence than division. It is closer to a linguistic or typographical dispute than a purely mathematical one, and the correct answer to the dispute is that whoever wrote the expression that way should learn to write math better.
This debate is not even new. The internet had fun arguing over 48÷2(9+3) and 6÷2(1+2), which are functionally identical ambiguous expressions, eight years ago. I don’t know why the debate is resurging now and why we still haven’t gotten tired of it.
But life is short, so since we’re here anyway, let’s make some additional memes.
Asking the computer
Some of my coworkers had the idea to ask some programming languages what the answer was. The results were underwhelming.
$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17)
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 8/2(2+2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'int' object is not callable$ cat meme.c
#include <stdio.h>
int main() {
printf("%d\n", 8/2(2+2));
}
$ gcc meme.c
meme.c: In function ‘main’:
meme.c:3:19: error: called object is not a function or function pointer
printf("%d\n", 8/2(2+2));$ node
> 8/2(2+2)
TypeError: 2 is not a functionI will note right away that we are using / instead of
÷ in these snippets. This changes the expression, but I
think the two operators have similar connotations of precedence and
nobody uses the ÷ sign after grade school anyway, so I think this
replacement doesn’t affect the dispute too much.
By the way, you can ask these programming languages and many more to
evaluate 8/2*(2+2) and they will happily do it, almost
certainly arriving at the answer 16 (or 16.0),
because division and multiplication have the same precedence and are
evaluated left-to-right. However, I think this ends up being a different
dispute completely. The core dispute is not how division’s precedence
compares to multiplication, but how it compares to juxtaposition, which
might have different precedence properties even though it represents the
same mathematical operation as the multiplication sign.
Anyway, not willing to give up, I tried to see if Haskell could give us an answer:1
$ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help
Loaded GHCi configuration from /home/akriloth/.ghci
λ> 8/2(2+2)
<interactive>:1:1: error:
• Non type-variable argument in the constraint: Num (t -> a)
(Use FlexibleContexts to permit this)
• When checking the inferred type
it :: forall t a. (Num (t -> a), Num t, Fractional a) => aDown the Haskell rabbit hole
It doesn’t work right away, but the compiler suggests a compiler flag, which we can try:
λ> :set -XFlexibleContexts
λ> 8/2(2+2)
<interactive>:3:1: error:
• Could not deduce (Num t0)
from the context: (Num (t -> a), Num t, Fractional a)
bound by the inferred type for ‘it’:
(Num (t -> a), Num t, Fractional a) => a
at <interactive>:3:1-8
The type variable ‘t0’ is ambiguous
• In the ambiguity check for the inferred type for ‘it’
To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
When checking the inferred type
it :: forall t a. (Num (t -> a), Num t, Fractional a) => aA second compiler flag? We can try again:
λ> :set -XAllowAmbiguousTypes
λ> 8/2(2+2)
<interactive>:5:1: error:
• No instance for (Num (t0 -> a0)) arising from a use of ‘it’
(maybe you haven't applied a function to enough arguments?)
• In a stmt of an interactive GHCi command: print itThis gets at the essence of why Haskell can’t evaluate the
expression, and how we might go about making it work. What is the type
of an integer literal like 2 in Haskell?
λ> :t 2
2 :: Num t => tThe integer literal can actually be of any type that is an instance
of the typeclass Num. If you’re more used to
object-oriented programming languages, you can think of a typeclass as
like an interface; it declares the types of some operations,2 and any types that are instances of
the typeclass must provide concrete implementations of those operations
with matching types. So it’s actually not impossible that an integer
literal could be a function; all we would need is for the type of a
function to be an instance of Num. It just isn’t, yet, and
that’s what Haskell is ultimately complaining about, above.
Let’s make it one. I’m also going to start writing things in a Haskell source file to make things neater. (This should go without saying, but don’t use this code in production.)
{-# LANGUAGE FlexibleInstances #-}
instance Num a => Num (a -> a) where
fromInteger x = (fromInteger x *)
main = print (8/2(2+2))There are actually several more functions that one should define to
make a type a proper instance of Num, which Haskell would
warn us about if our code managed to compile, but the only function we
need to define to get Haskell to treat numeric literals as our type is
fromInteger. The type of fromInteger is
Num a => Integer -> a: for any type that’s an
instance of Num, it converts that type to
Integer, which is Haskell’s concrete built-in
arbitrary-precision integer type.
So, what we’re doing concretely above is telling Haskell how to
convert an Integer to a function of type
a -> a, where a is any type that’s an
instance of the typeclass Num. A function of type
a -> a is a function that takes in one argument of type
a and returns one value of type a. To do this,
we convert x from an Integer to a value of
type a, and then partially apply the multiplication
function * to it, which produces a function that will
multiply its argument by the value we’ve already provided. Because type
inference is magic, everything works.
Just kidding:
$ ghc meme.hs
[1 of 1] Compiling Main ( meme.hs, meme.o )
meme.hs:5:8: error:
• Ambiguous type variable ‘a0’ arising from a use of ‘print’
prevents the constraint ‘(Show a0)’ from being solved.
Probable fix: use a type annotation to specify what ‘a0’ should be.
These potential instances exist:
instance Show Ordering -- Defined in ‘GHC.Show’
instance Show Integer -- Defined in ‘GHC.Show’
instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
...plus 22 others
...plus six instances involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the expression: print (8 / 2 (2 + 2))
In an equation for ‘main’: main = print (8 / 2 (2 + 2))
meme.hs:5:15: error:
• Ambiguous type variable ‘a0’ arising from the literal ‘8’
prevents the constraint ‘(Num a0)’ from being solved.
Probable fix: use a type annotation to specify what ‘a0’ should be.
These potential instances exist:
instance Num Integer -- Defined in ‘GHC.Num’
instance Num a => Num (a -> a) -- Defined at meme.hs:2:10
instance Num Double -- Defined in ‘GHC.Float’
...plus three others
...plus one instance involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the first argument of ‘(/)’, namely ‘8’
In the first argument of ‘print’, namely ‘(8 / 2 (2 + 2))’
In the expression: print (8 / 2 (2 + 2))
meme.hs:5:15: error:
• Ambiguous type variable ‘a0’ arising from a use of ‘/’
prevents the constraint ‘(Fractional a0)’ from being solved.
Probable fix: use a type annotation to specify what ‘a0’ should be.
These potential instances exist:
instance Fractional Double -- Defined in ‘GHC.Float’
instance Fractional Float -- Defined in ‘GHC.Float’
...plus one instance involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the first argument of ‘print’, namely ‘(8 / 2 (2 + 2))’
In the expression: print (8 / 2 (2 + 2))
In an equation for ‘main’: main = print (8 / 2 (2 + 2))
meme.hs:5:17: error:
• Ambiguous type variables ‘a0’, ‘t0’ arising from the literal ‘2’
prevents the constraint ‘(Num (t0 -> a0))’ from being solved.
(maybe you haven't applied a function to enough arguments?)
Probable fix: use a type annotation to specify what ‘a0’, ‘t0’ should be.
These potential instance exist:
instance Num a => Num (a -> a) -- Defined at meme.hs:2:10
• In the expression: 2
In the second argument of ‘(/)’, namely ‘2 (2 + 2)’
In the first argument of ‘print’, namely ‘(8 / 2 (2 + 2))’
meme.hs:5:19: error:
• Ambiguous type variable ‘t0’ arising from a use of ‘+’
prevents the constraint ‘(Num t0)’ from being solved.
Probable fix: use a type annotation to specify what ‘t0’ should be.
These potential instances exist:
instance Num Integer -- Defined in ‘GHC.Num’
instance Num a => Num (a -> a) -- Defined at meme.hs:2:10
instance Num Double -- Defined in ‘GHC.Float’
...plus three others
...plus one instance involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the first argument of ‘2’, namely ‘(2 + 2)’
In the second argument of ‘(/)’, namely ‘2 (2 + 2)’
In the first argument of ‘print’, namely ‘(8 / 2 (2 + 2))’The issue here is actually fairly subtle. When Haskell tries to
figure out which instance to use to make 2 a function, the
instance we declared instance Num a => Num (a -> a)
is only considered as an option if Haskell explicitly knows that the
input and output type of the function it wants are identical. In the
code we wrote, it doesn’t know this: it only knows that the input type
is the type of 2 + 2, which could be any type that’s an
instance of Num, and the output type is something that can
fill in the blank in the expression print (8 / _), which
could be any type that’s an instance of the two typeclasses
Show and Fractional (required for
print and /, respectively). It doesn’t even
matter if the input and output have the same typeclass constraints.
Haskell needs to identify the concrete type of both the input and the
output and see that they’re equal in order to choose the instance we
wrote. Since it can’t, it errors out saying it couldn’t find an
instance.
This error is pointed out by the most important part of the dozens of lines in the error above, which also suggests a fix:
• Ambiguous type variables ‘a0’, ‘t0’ arising from the literal ‘2’
prevents the constraint ‘(Num (t0 -> a0))’ from being solved.
(maybe you haven't applied a function to enough arguments?)
Probable fix: use a type annotation to specify what ‘a0’, ‘t0’ should be.And indeed, we can make it compile by explicitly annotating the type
of the 2 that we want to be a function:
{-# LANGUAGE FlexibleInstances #-}
instance Num a => Num (a -> a) where
fromInteger x = (fromInteger x *)
main = print (8/(2 :: Double -> Double)(2+2))This compiles (with a warning), and it’s an established way of
achieving this3. But it feels like cheating; we had
to insert a random type annotation in the middle of our expression,
which feels a bit like inserting the *.
Fortunately, there is a different approach that works, a “trick” using the equality constraint:
{-# LANGUAGE GADTs #-}
instance (a ~ b, Num b) => Num (a -> b) where
fromInteger x = (fromInteger x *)
main = print (8/2(2+2))The equality constraint is the a ~ b part, which states
that a and b must be the same type (and which
we need to enable a totally different language extension to make Haskell
support). The difference between this instance and the previous one is
that this instance will always be chosen whenever Haskell needs to find
a Num instance for a function type. Only after
Haskell has decided to use the instance does it check that the
constraints are satisfied. In contrast, with the old
Num a => Num (a -> a) instance, Haskell checks that
the input and output types are equal before deciding to use it,
and this check fails. For further reading, you can consult this SO
question on the equality constraint and the post it links to, or
this post
on Equality Constraints, which abuses integer literals in a
different way.
With this change, we can finally figure out what Haskell thinks the value of the original mathematical expression is:
$ ghc meme.hs
$ ./meme
1.0Voilà! Juxtaposition binds more tightly than division.
A proper implementation
Don’t like warnings? Want to be extra faithful to the original
problem and use the obelus for division? You only need to declare six
functions to be a full-fledged instance of Num, and Unicode
mathematical operators are perfectly legitimate infix operators in
Haskell, so we have you covered.
{-# LANGUAGE GADTs #-}
instance (a ~ b, Num b) => Num (a -> b) where
(fromInteger x) y = fromInteger x * y
(a + b) c = a c + b c
(a - b) c = a c - b c
(a * b) c = a (b c)
(abs a) b = abs (a b) * signum b
(signum a) b = signum (a b) * abs b
(÷) = (/)
main = print (8÷2(2+2))Want all that in impeccable point-free style? It makes more sense for some of the functions than for others, but whatever floats your boat:
{-# LANGUAGE GADTs #-}
import Control.Applicative (liftA2, (<*>))
instance (a ~ b, Num b) => Num (a -> b) where
fromInteger = (*) . fromInteger
(+) = liftA2 (+)
(-) = liftA2 (-)
(*) = (.)
abs = (<*> signum) . (((*) . abs) .)
signum = (<*> abs) . (((*) . signum) .)
(÷) = (/)
main = print (8÷2(2+2))Of course, the downside is that many nonsensical expressions now typecheck and give nonsensical results:
λ> (+4) (+9) 2
19Bonus round: Scala
All we need to do is tell Scala it can implicitly convert any
Int into a function that multiplies its argument by that
Int.
import scala.language.implicitConversions
object Meme extends App {
implicit def int2mul(x: Int) = (y: Int) => x * y
println(8/2(2+2))
}$ scalac Meme.scala
$ scala Meme
1Unfortunately, I don’t know enough about other programming languages to give more examples.