Daniel's Blog

It rained in Sunriver on New Year’s Eve, and it continued to rain for the next couple of days. So, instead of going skiing as planned, to the dismay of my family and friends, I spent the majority of those days working on the third language for homework 3. It was quite the language, too - the homework has three problems, each of which has a solution independent of the others. I invite you to join me in my descent into madness as we construct another language.

Let’s take a look at the three homework problems. The first two are related, but are solved using a different technique:

18
19
20
21
22
23
24
25
26
27
28
29
30

1. Given an array A of n numbers, a query x, and a number k,
   find the k numbers in A that are closest (in value) to x.
   For example:

   find([4,1,3,2,7,4], 5.2, 2)	returns   [4,4]
   find([4,1,3,2,7,4], 6.5, 3)	returns   [4,7,4]
   find([5,3,4,1,6,3], 3.5, 2)	returns   [3,4]


   Filename: closest_unsorted.py
   Must run in O(n) time. 
   The elements in the returned list must be in the original order.
   In case two numbers are equally close to x, choose the earlier one.

This problem requires us to find the k numbers closest to some query (which I will call n) from a list xs. The list isn’t sorted, and the problem must run in linear time. Sorting the list would require the standard $O(n\log n)$ time. [note: The $n$ in this expression is not the same as the query n, but rather the length of the list. In fact, I have not yet assigned the length of the input xs to any variable. If we say that $m$ is a number that denotes that length, the proper expression for the complexity is $O(m \log m)$. ] Thus, we have to take another route, which should already be familiar: quickselect. Using quickselect, we can find the kth closest number, and then collect all the numbers that are closer than the kth closest number. So, we need a language that:

• Supports quickselect (and thus, list partitioning and recursion).
• Supports iteration, multiple times. [note: Why would we need to iterate multiple times? Note that we could have a list of numbers that are all the same, [1,1,1,1,1]. Then, we'll need to know how many of the numbers equally close as the kth element we need to include, which will require another pass through the list. ]

That’s a good start. Let’s take a look at the second problem:

33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

2. [WILL BE GRADED]
   Now what if the input array is sorted? Can you do it faster?

   find([1,2,3,4,4,7], 5.2, 2) returns   [4,4]
   find([1,2,3,4,4,7], 6.5, 3) returns   [4,4,7]

   Filename: closest_sorted.py
   Must run in O(logn + k) time.
   The elements in the returned list must be in the original order.

   Note: in case two numbers are equally close to x, choose the smaller one:
   find([1,2,3,4,4,6,6], 5, 3) returns   [4,4,6]
   find([1,2,3,4,4,5,6], 4, 5) returns   [2,3,4,4,5]

   Hint: you can use Python's bisect.bisect for binary search.

This problem really is easier. We have to find the position of the closest element, and then try expand towards either the left or right, depending on which end is better. This expansion will take several steps, and will likely require a way to “look” at a given part of the list. So let’s add two more rules. We need a language that also:

• Supports looping control flow, such as while.
• Allows for a “view” into the list [note: We could, of course, simply use list indexing. But then, we'd just be making a simple imperative language, and that's boring. So let's play around with our design a little, and experimentally add such a "list view" component. ] (like an abstraction over indexing).

This is shaping up to be a fun language. Let’s take a look at the last problem:

50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

3. For a given array A of n *distinct* numbers, find all triples (x,y,z) 
   s.t. x + y = z. (x, y, z are distinct numbers)

   e.g.,
   
   find([1, 4, 2, 3, 5]) returns [(1,3,4), (1,2,3), (1,4,5), (2,3,5)]

   Note that:
   1) no duplicates in the input array
   2) you can choose any arbitrary order for triples in the returned list.

   Filename: xyz.py
   Must run in O(n^2) time.

   Hint: you can use any built-in sort in Python.

This problem requires more iterations of a list. We have several “cursors” [note: I always make the language before I write the post, since a lot of design decisions change mid-implementation. I realize now that "cursors" would've been a better name for this language feature, but alas, it is too late. ] looking into the list, and depending if the values at each of the cursors add up, we do or do not add a new tuple to a list. So, two more requirements:

• The “cursors” must be able to interact.
• The language can represent tuples. [note: We could, of course, hack some other way to return a list of tuples, but it turns out tuples are pretty simple to implement, and help make for nicer programming in our language. ]

I think we’ve gathered what we want from the homework. Let’s move on to the language!

As is now usual, let’s envision a solution to the problems in our language. There are actually quite a lot of functions to look at, so let’s see them one by one. First, let’s look at qselect.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function qselect(xs, k, c) {
    if xs == [] {
        return 0;
    }

    traverser bisector(list: xs, span: (0,len(xs)));
    traverser pivot(list: xs, random: true);

    let pivotE = pop!(pivot);
    let (leftList, rightList) = bisect!(bisector, (x) -> c(x) < c(pivotE));
    
    if k > len(leftList) + 1 {
        return qselect(rightList, k - len(leftList) - 1, c);
    } elsif k == len(leftList) + 1 {
        return pivotE;
    } else {
        return qselect(leftList, k, c);
    }
}

After the early return, the first interesting part of the language is the use of what I have decided to call a list traverser. The list traverser is a generalization of a list index. Whenever we use a list index variable, we generally use the following operations:

• Initialize: we set the list index to some initial value, such as 0.
• Step: If we’re walking the list from left to right, we increment the index. If we’re walking the list from right to left, we decrement the index.
• Validity Check: We check if the index is still valid (that is, we haven’t gone past the edge of the list).
• Access: Get the element the cursor is pointing to.

A traverser declaration [note: A fun fact is that we've just rediscovered C++ iterators. C++ containers and their iterators provide us with the operations I described: We can initialize an iterator like auto it = list.begin(). We can step the iterator using it++. We can check its validity using it != list.end(), and access what it's pointing to using *it. While C++ uses templates and inheritance for this, we define a language feature specifically for lists. ] describes these operations. The declartion for the bisector traverser creates a “cursor” over the list xs, that goes between the 0th and last elements of xs. The declaration for the pivot traverser creates a “cursor” over the list xs that jumps around random locations in the list.

The next interesting part of the language is a traverser macro. This thing, that looks like a function call (but isn’t), performs an operation on the cursor. For instance, pop! removes the element at the cursor from the list, whereas bisect! categorizes the remaining elements in the cursor’s list into two lists, using a boolean-returning lambda (written in Java syntax).

Note that this implementation of qselect takes a function c, which it uses to judge the actual value of the number. This is because our qselect won’t be finding the smallest number, but the number with the smallest difference with n. n will be factored in via the function.

Next up, let’s take a look at the function that uses qselect, closestUnsorted:

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

function closestUnsorted(xs, k, n) {
    let min = qselect(list(xs), k, (x) -> abs(x - n));
    let out = [];
    let countEqual = k;

    traverser iter(list: xs, span: (0, len(xs)));
    while valid!(iter) {
        if abs(at!(iter)-n) < abs(min-n) {
            let countEqual = countEqual - 1;
        }
        step!(iter);
    }

    traverser iter(list: xs, span: (0, len(xs)));
    while valid!(iter) {
        if abs(at!(iter)-n) == abs(min-n) and countEqual > 0 {
            let countEqual = countEqual - 1;
            let out = out + [at!(iter)];
        } elsif abs(at!(iter)-n) < abs(min-n) {
            let out = out + [at!(iter)];
        }
        step!(iter);
    }

    return out;
}

Like we discussed, it finds the kth closest element (calling it min), and counts how many elements that are equal need to be included, by setting the number to k at first, and subtracting 1 for every number it encounters that’s closer than min. Notice that we use the valid! and step! macros, which implement the operations we described above. Notice that the user doesn’t deal with adding and subtracting numbers, and doing comparisons. All they have to do is ask “am I still good to iterate?”

Next, let’s take a look at closestSorted, which will require more traverser macros.

48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

function closestSorted(xs, k, n) {
    let start = bisect(xs, n);
    let counter = 0;
    traverser left(list: xs, span: (0, start), reverse: true);
    traverser right(list: xs, span: (start, len(xs)));

    while counter != k and canstep!(left) and valid!(right) {
        if abs(at!(left, 1) - n) < abs(at!(right) - n) {
            step!(left);
        } else {
            step!(right);
        }
        let counter = counter + 1;
    }

    while counter != k and (canstep!(left) or valid!(right)) {
        if canstep!(left) { step!(left); }
        else { step!(right); }
        let counter = counter + 1;
    }

    return subset!(left, right);
}

The first new macro is canstep!. This macro just verifies that the traverser can make another step. We need this for the “reverse” iterator, which indicates the lower bound of the range of numbers we want to return, because subset! (which itself is just Python’s slice, like xs[a:b]), uses an inclusive bottom index, and thus, we can’t afford to step it before knowing that we can, and that it’s a better choice after the step.

Similarly, we have the at!(t, i) macro, which looks at the traverser t, with offset i.

We have two loops. The first loop runs as long as we can expand the range in both directions, and picks the better direction at each iteration. The second loop runs as long as we still want more numbers, but have already hit the edge of the list on the left or on the right.

Finally, let’s look at the solution to xyz:

72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

sorted function xyz(xs, k) {
    traverser x(list: xs, span: (0,len(xs)));
    let dest = [];

    while valid!(x) {
        traverser z(list: xs, span: (pos!(x)+2,len(xs)));
        traverser y(list: xs, span: (pos!(x)+1,pos!(z)));

        while valid!(y) and valid!(z) {
            if at!(x) + at!(y) == at!(z) {
                let dest = dest + [(at!(x), at!(y), at!(z))];
                step!(z);
            } elsif at!(x) + at!(y) > at!(z) {
                step!(z);
            } else {
                step!(y);
            }
        }

        step!(x);
    }

    return dest;
}

I won’t go in depth, but notice that the expression in the span part of the traverser declaration can access another traverser. We treat as a feature the fact that this expression isn’t immediately evaluated at the place of the traverser declaration. Rather, every time that a comparison for a traverser operation is performed, this expression is re-evaluated. This allows us to put dynamic bounds on traversers y and z, one of which must not exceed the other.

Note also a new keyword that was just used: sorted. This is a harmless little language feature that automatically calls .sort() on the first argument of the function.

This is more than enough to work with. Let’s move on to the implementation.

Again, let’s not go too far into the details of implementing the language from scratch. Instead, let’s take a look into specific parts of the language that deserve attention.

Our previous language was, indeed, a respite from complexity. Translation was straightforward, and the resulting expressions and statements were plugged straight into a handwritten AST. We cannot get away with this here; the language is powerful enough to implement three list-based problems, which comes at the cost of increased complexity.

We need, once again, to generate temporary variables. We also need to keep track of which variables are traversers, and the properties of these traversers, throughout each function of the language. We thus fall back to using Control.Monad.State:

198

type Translator = State (Map.Map String ValidTraverserData, [Py.PyStmt], Int)

There’s one part of the state tuple that we haven’t yet explained: the list of statements.

Recall that our translation function for expressions in the first homework had the type:

translateExpr :: Expr -> Translator ([Py.PyStmt], Py.PyExpr)

We then had to use do-notation, and explicitly concatenate lists of emitted statements. In this language, I took an alternative route: I made the statements part of the state. They are thus implicitly generated and stored in the monad, and expression generators don’t have to worry about concatenating them. When the program is ready to use the generated statements (say, when an if-statement needs to use the statements emitted by the condition expression), we retrieve them from the monad:

228
229
230
231
232
233
234

collectStatements :: Translator a -> Translator ([Py.PyStmt], a)
collectStatements t = do
    modify (first $ const [])
    a <- t
    ss <- gets $ \(_, ss, _) -> ss
    modify (first $ const [])
    return (ss, a)

I should note, for transparency, that there’s a bug in my use of this function. When I compile if-statements, I accidentally place statements generated by the condition into the body of the if. This bug doesn’t manifest in the solutions to the homework problems, and so I decided not to spend any more time on fixing it.

We declare two separate types that hold traverser data. The first is a kind of “draft” type, TraverserData:

184
185
186
187
188
189
190

data TraverserBounds = Range Py.PyExpr Py.PyExpr | Random

data TraverserData = TraverserData
    { list :: Maybe String
    , bounds :: Maybe TraverserBounds 
    , rev :: Bool
    }

This record holds all possible configurations of a traverser that occur as the program is iterating through the various key: value pairs in the declaration. For instance, at the very beginning of processing a traverser declaration, our program will use a “default” TraverserData, with all fields set to Nothing or their default value. This value will then be modified by the first key/value pair, changing, for instance, the list that the traverser operates on. This new modified TraverserData will then be modified by the next key/value pair, and so on. Doing this with every key/value pair (called an option in the below snippet) is effectively a foldl operation.

378
379
380
381
382
383
384
385
386
387

applyOption :: TraverserData -> (String, Py.PyExpr) -> Maybe TraverserData
applyOption td ("list", Py.Var s) =
    return $ td { list = Just s }
applyOption td ("span", Py.TupleLiteral [f, t]) =
    return $ td { bounds = Just $ Range f t }
applyOption td ("random", Py.BoolLiteral True) =
    return $ td { bounds = Just Random }
applyOption td ("reverse", Py.BoolLiteral b) =
    return $ td { rev = b }
applyOption td _ = Nothing

The data may not have all the required fields until the very end, and its type reflects that: Maybe String here, Maybe TraverserBounds there. We don’t want to deal with unwrapping the Maybe a values every time we use the traverser, especially if we’ve done so before. So, we define a ValidTraverserData record that does not have Maybe arguments, and thus, has all the required data. At the end of a traverser declaration, we attempt to translate a TraverserData into a ValidTraverserData, invoking fail if we can’t, and storing the ValidTraverserData into the state otherwise:

408
409
410
411
412
413
414
415
416
417
418
419
420

translateStmt (Traverser s os) =
    foldlM applyOption defaultTraverser <$> mapM translateOption os >>= saveTraverser 
    where
        saveTraverser :: Maybe TraverserData -> Translator Py.PyStmt
        saveTraverser (Just (td@TraverserData { list = Just l, bounds = Just bs})) =
            putTraverser s vtd $> translateInitialBounds s vtd
            where
                vtd = ValidTraverserData
                    { validList = l
                    , validBounds = bs
                    , validRev = rev td
                    }
        saveTraverser Nothing = fail "Invalid traverser (!)"

Then, every time we retrieve a traverser from the state, define a lookup monadic operation like this:

240
241
242
243
244

requireTraverser :: String -> Translator ValidTraverserData
requireTraverser s = gets (\(m, _, _) -> Map.lookup s m) >>= handleMaybe
    where
        handleMaybe Nothing = fail "Invalid traverser"
        handleMaybe (Just vtd) = return vtd

I didn’t call them macros for no reason. Clearly, we don’t want to generate code that calls functions only to increment an index. [note: In fact, there's no easy way to do this at all. Python's integers (if we choose to represent our traversers using integers), are immutable. Furthermore, unlike C++, where passing by reference allows a function to change its parameters "outside" the call, Python offers no way to reassign a different value to a variable given to a function.

For an example use of C++'s pass-by-reference mechanic, consider std::swap: it's a function, but it modifies the two variables given to it. There's no way to generically implement such a function in Python. ] We also can’t allow arbitrary expressions to serve as traversers: our translator keeps some context about which variables are traversers, what their bounds are, and how they behave. Thus, calls to traverser macros are very much macros: they operate on AST nodes, and require that their first argument is a variable, named like the traverser. We use the requireTraverser monadic operation to get the traverser associated with the given variable name, and then perform the operation as intended. The at!(t) operation is straightforward:

317
318
319

translateExpr (TraverserCall "at" [Var s]) = do
    l <- validList <$> requireTraverser s
    return $ Py.Access (Py.Var l) [Py.Var s]

The at!(t,i) is less so, since it deals with the intricacies of accessing the list at either a positive of negative offset, depending on the direction of the traverser. We implement a function to properly generate an expression for the offset:

246
247
248
249

traverserIncrement :: Bool -> Py.PyExpr -> Py.PyExpr -> Py.PyExpr
traverserIncrement rev by e =
    Py.BinOp op e (Py.BinOp Py.Multiply by (Py.IntLiteral 1))
    where op = if rev then Py.Subtract else Py.Add

We then implement at!(t,i) as follows:

320
321
322
323

translateExpr (TraverserCall "at" [Var s, IntLiteral i]) = do
    vtd <- requireTraverser s
    return $ Py.Access (Py.Var $ validList vtd)
        [traverserIncrement (validRev vtd) (Py.IntLiteral i) (Py.Var s)]

The most complicated macro is bisect!. It must be able to step the traverser, and also return a tuple of two lists that the bisection yields. We also prefer that it didn’t pollute the environment with extra variables. To achieve this, we want bisect! to be a function call. We want this function to implement the iteration and list construction.

bisect!, by definition, takes a lambda. This lambda, in our language, is declared in the lexical scope in which bisect! is called. Thus, to guarantee correct translation, we must do one of two things:

1. Translate 1-to-1, and create a lambda, passing it to a fixed bisect function declared elsewhere.
2. Translate to a nested function declaration, inlining the lambda. [note: Inlining, in this case, means replacing a call to a function with the function's body. We do this to prevent the overhead of calling a function, which typically involves pushing on a stack and other extraneous work. If our function is simple, like a simple comparison, it doesn't make sense to spend the effort calling it. ]

Since I quite like the idea of inlining a lambda, let’s settle for that. To do this, we pull a fresh temporary variable and declare a function, into which we place the traverser iteration code, as well as the body of the lambda, with the variable substituted for the list access expression. Here’s the code: [note: Reading the lexical scope is one thing, but modifying it is another. To prevent accidental changes to the variables outside a nested function, Python assumes that variables assigned inside the function body are local to the function. Thus, to make sure changing our variable (the traverser index) has an effect outside the function (as it should) we must include the nonlocal keyword, telling Python that we're not declaring a new, local variable, but mutating the old one. ]

342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363

translateExpr (TraverserCall "bisect" [Var s, Lambda [x] e]) = do
    vtd <- requireTraverser s
    newTemp <- freshTemp
    lambdaExpr <- translateExpr e
    let access = Py.Access (Py.Var $ validList vtd) [Py.Var s]
    let translated = substituteVariable x access lambdaExpr
    let append s = Py.FunctionCall (Py.Member (Py.Var s) "append") [ access ]
    let bisectStmt = Py.FunctionDef newTemp []
         [ Py.Nonlocal [s]
         , Py.Assign (Py.VarPat "l") (Py.ListLiteral [])
         , Py.Assign (Py.VarPat "r") (Py.ListLiteral [])
         , Py.While (traverserValid (Py.Var s) vtd)
            [ Py.IfElse translated
                [ Py.Standalone $ append "l" ]
                []
                (Just [ Py.Standalone $ append "r" ])
            , traverserStep s vtd
            ]
         , Py.Return $ Py.TupleLiteral [Py.Var "l", Py.Var "r"]
         ]
    emitStatement bisectStmt
    return $ Py.FunctionCall (Py.Var newTemp) []

Let’s see what the compiler spits out:

from bisect import bisect
import random
def qselect(xs,k,c):
    if xs==[]:
        return 0
    bisector = 0
    pivot = random.randrange(len(xs))
    pivotE = xs.pop(pivot)
    def temp1():
        nonlocal bisector
        l = []
        r = []
        while bisector<len(xs):
            if c(xs[bisector])<c(pivotE):
                l.append(xs[bisector])
            else:
                r.append(xs[bisector])
            bisector = bisector+1
        return (l, r)
    (leftList,rightList) = temp1()
    if k>len(leftList)+1:
        return qselect(rightList, k-len(leftList)-1, c)
    elif k==len(leftList)+1:
        return pivotE
    else:
        return qselect(leftList, k, c)
def closestUnsorted(xs,k,n):
    min = qselect(list(xs), k, (lambda x: abs(x-n)))
    out = []
    countEqual = k
    iter = 0
    while iter<len(xs):
        if abs(xs[iter]-n)<abs(min-n):
            countEqual = countEqual-1
        iter = iter+1
        0
    iter = 0
    while iter<len(xs):
        if abs(xs[iter]-n)==abs(min-n) and countEqual>0:
            countEqual = countEqual-1
            out = out+[xs[iter]]
        elif abs(xs[iter]-n)<abs(min-n):
            out = out+[xs[iter]]
        iter = iter+1
        0
    return out
def closestSorted(xs,k,n):
    start = bisect(xs, n)
    counter = 0
    left = start
    right = start
    while counter!=k and left-1*1>=0 and right<len(xs):
        if abs(xs[left-1*1]-n)<abs(xs[right]-n):
            left = left-1
            0
        else:
            right = right+1
            0
        counter = counter+1
    while counter!=k and (left-1*1>=0 or right<len(xs)):
        if left-1*1>=0:
            left = left-1
            0
        else:
            right = right+1
            0
        counter = counter+1
    return xs[(left):(right)]
def xyz(xs,k):
    xs.sort()
    x = 0
    dest = []
    while x<len(xs):
        z = x+2
        y = x+1
        while y<z and z<len(xs):
            if xs[x]+xs[y]==xs[z]:
                dest = dest+[(xs[x], xs[y], xs[z])]
                z = z+1
                0
            elif xs[x]+xs[y]>xs[z]:
                z = z+1
                0
            else:
                y = y+1
                0
        x = x+1
        0
    return dest

Observe that the generated code just uses indices, +, -, and various comparison operators. Our traverser is an example of a zero cost abstraction, a feature that, conceptually, operates at a higher level, making us no longer worry about adding, subtracting, and comparing numbers, while, in the final output, not damaging the performance of safety of the code. Also observe the various 0 standalone statements. This is an issue with the translator: traverser macros may not always yield an expression, but the type of translateExpr and translateStmt effectively requires one. Thus, when a macro doesn’t generate anything useful, we give it the placeholder expression 0.

That concludes this third post in the series. I hope to see you in the next one!