restrictive or: notes from the dark side

Okay, it’s week four of data structures in Python. In the past few days, I’ve read a lot of terrible code. Here’s a beautiful, horrible, example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# An IntList is one of
# - None, or
# - Pair(int, IntList)
class Pair:
    def __init__(self, first, rest):
        self.first = first
        self.rest = rest

    # standard definitions of __eq__ and __repr__ ...

# A Position is one of
# - an int, representing a list index, or
# - None

# IntList int -> Position
# find the position of the sought element in the list, return None if not found.
def search(l, sought):
    if l == None:
        return None
    rest_result = search(l.rest, sought)
    if (l.first == sought or rest_result) != None:
        if l.first == sought:
            return 0
        else:
            return 1 + rest_result

This code works correctly. It searches a list to find the position of a given element. Notice anything interesting about it?

Take a look at the parentheses in the if line. How do you feel about this code now?

(Spoilers after the jump. Figure out why it works before clicking, and how to avoid this problem.)

Okay, that’s just awful. The intent was to write

1

if (l.first == sought) or (rest_result != None):

instead of

1

if (l.first == sought or rest_result) != None:

… but the student misparenthesized. The student’s code works because if l.first is equal to sought, the or evaluates to True, which is in fact not equal to None, so you wind up in the right place. Otherwise, the or winds up being the value of rest_result, which is then correctly compared to None. Note also that there’s no else case, meaning that the function secretly returns None in the fall-through, which is also correct.

I hope you agree with me that this code is abominable, and we’d like to prevent students from writing it.

What’s the fix? I think the obvious fix is to ensure that or only works on booleans. This is guaranteed by most typed languages in the type system, or by a dynamic check in the implementation of or.

Does Racket have this problem? No, it does not. In the case of Racket, though, it’s because of the notion of “student languages,” an idea to which many people pay lip service but which few people actually carry out.

Anyway: types or language levels FTW. Or, more precisely:

Python FTL!