Bounded-Error Log

theoretical and applied randomness by betaveros

Multiplication by Juxtaposition

Evaluating 8÷2(2+2) in Haskell (and some other languages)

2019-08-04 (2653 words) filed under CS

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 function

I 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) => a

Down 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) => a

A 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 it

This 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?

The 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.)

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:

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:

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.0

Voilà! 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.

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:

Of course, the downside is that many nonsensical expressions now typecheck and give nonsensical results:

Bonus 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.

$ scalac Meme.scala
$ scala Meme
1

Unfortunately, I don’t know enough about other programming languages to give more examples.

  1. If you’re following along at home, I got the prompt by putting :set prompt "λ> " in ~/.ghci. See What I Wish I Knew When Learning Haskell on GHCi.

    Also, I’m using GHC, the Glasgow Haskell Compiler, and I refer to it as Haskell just to keep things simple. This may be considered technically incorrect since there are other Haskell implementations and I’m using lots of GHC extensions that aren’t part of the Haskell specification, but GHC is very canonical.↩

  2. Typically these operations are functions, but they don’t have to be. For example, the Bounded typeclass defines “operations” of the following two types:

    Learn You a Haskell describes these as “polymorphic constants”. They are constants of type a, which differ depending on the type.

    The word “operation” is from the Haskell spec.↩

  3. “Is there a way to overload juxtaposition in ghc?”, 2015.↩

(note: the commenting setup here is experimental and I may not check my comments often; if you want to tell me something instead of the world, email me!)