Clojure to CL

Well it’s compilers time at long last… and my professor Gordon Novak even has a lisp option for the class as opposed to straight C. Unfortunately for me, his codebase is entirely in Common Lisp and the UTCS hosts don’t have Clojure so I really only have the option of cl.

This is anything but ideal… while cl (specifically GNU Clisp) was my first lisp as with C++ (my first language) it’s the one I’ve written the fewest lines of, and also to my taste the hardest to find documentation of and for due simply to the age of the CL standard.

Clojure is great in that for any symbol say Clojure.core/cons I can just hit up http://Clojuredocs.org/Clojure_core/Clojure.core/cons. See how the symbol implies the URL? Yeah. That’s awesome. Even Python’s docs don’t do that. So I hit that URL and I’ve got both docs and implementation before me. With clisp I have to find a hyperspec mirror and dig through it. Maybe I’ll find some “CL Recipe” page at cs.cmu.edu/Groups/AI/ or probably resort to a library book because at least those have a decent index. Anyway.

So at the moment I have a cute rewindable parser in Clojure that I have to bring over to CL rather than throw it away and this is the story of the port, or at least part I of it.

Moving from Clojure to CL had a bunch of bumps and required a bit of a thought process shift. The three major bumps were packaging, work environment and basic data model.

Packaging

Clojure “features” build-in packaging based on a Java-like file hierarchy (gee wonder why) and therefore out of the box allows for multi-file projects where files relate only by (:require) and (:use) lists that specify dependencies. One thing I forget is just how old the Common Lisp standard is… so old in fact that things like the classpath aren’t really a clear part of the standard. There is a concept of packages and loading packages, but the surrounding details are fuzzy at best. At some point the asdf project rolled around and filled that gap, so a large part of my transition was figuring out how to get asdf and writing a main.lisp file to muck with the asdf search path so that I could load the requisite components.

In this venture, the sample project was bleeding invaluable. The bottom line of asdf is that you create a file foo.asd which says something to the effect of

(in-package :cl-user)
(defpackage :arrdem.foo
    (:use :asdf :cl))
(in-package :arrdem.foo)
(defsystem "arrdem.foo"
    :version "1.0.0-SNAPSHOT"
    :author  "arrdem"
    :depends-on ("other-system")
    :components ((:file "foo")
                 (:file "bar" :depends-on ("foo"))))

so (eval)ing main.lisp loads the asdf library and adds #P"./novak", #P"./trie" and #P"./reid" to the search path then loads the module reid which depends on novak and trie. It’s not the most elegant thing I’ve ever done, and it would be arguably more idiomatic to jam all the code into one file with no namespace separation but I consider saying (novak:peekchar) more idiomatic than just (peekchar) in a file that defines about 300 functions and 50 global variables. \ {“title”:”Depth First Failure”,”date”:”02/01/13”,”body”:”Well for all we say “Third time’s a charm” I managed to fumble a depth-first search question on my third coding interview. Unfortunately I’m seeing a pattern here. As with the Facebook interview which first prompted me to do a “gah DFS” post, I began to do a Clojure implementation for my interviewer(s), switched to python in a panic when no solution came to mind and just stalled in general. So here I am ranting about it after the fact and writing both implementations for my own sanity.

The first question I got asked was “how can I determine the index of some value K in a sorted sequence S?”. The answer to which is patently obvious: do a binary search tree traversal. That is we take the sequence, compare the “middle” value to the desired key and based on the relative values of the two (less than, equal, greater than) a case is evaluated which restricts the search domain and repeats the question on a subset of the problem space or you have reached a terminal case and return a value.

Graphically, this means that for a sequence such as [0 1 2 ... 16] if I want to find the value 5 I perform the following sequence of operations and comparisons.

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16], 9 gt. 5
[0 1 2 3 4 5 6 7 8 - -  -  -  -  -  -  - ], 4 lt. 5
[- - - - - 5 6 7 8 - -  -  -  -  -  -  - ], 6 gt. 5
[- - - - - 5 - - - - -  -  -  -  -  -  - ], 5 is the 6th index

The value - simply means that I and consequently my solution program know that the value for which I am searching cannot exist there due to the lemma of a strictly increasing key set. As long as that lemma holds the BST traverse will eventually find the sought value. This “sliding window” approach can be coded in Python as

def bst_address(value, sequence):
    upper, middle, delta, lower = len(sequence), 0, 0, 0
    while(true):
        delta  = upper - lower // 2
        middle = lower + delta
        if(lower >= upper):
            return -1
        elif(sequence[middle] == value):
            return middle
        elif(sequence[middle] > value):
            upper -= delta
        else:
            # implicitly sequence[middle] < value
            upper += delta

which is all well and good and I know now it that I’m out of the interview, but what’s the idiomatic and obvious way that I could get to this quickly so that the interviewer doesn’t have to suggest the key insight I use upper and lower cursors?

Well, I can simply have implemented this as the literal Clojure translation being

(defn bst_index [col val]
    (loop [left 0
           right (count col)]
        (let [delta  (/ (- right left) 2)
              center (+ left delta)
              cval   (nth col center)]
            (cond
                (<= right left) -1
                (= val cval)    center
                (> val cval)    (recur (+ left delta 1) right)
                (< val cval)    (recur left (- right delta 1))))))

But to be perfectly honest I don’t think that I would have come up with the index-manipulation scheme given any amount of time and the choice that I had made to work in Clojure. Perhaps had I chosen to work in Python or some other more C-like language this solution would have come to mind. However, this is the route that I was about to take before my interviewer pointed out the relatively obvious. However there’s another route, which is to just embrace the subsequenced based approach which seems natural in Clojure which leads to the following recursive solution:

(defn sum-if-not-neg [& args]
  (if (reduce #(and %1 %2)
              (map #(<= 0 %1) args))
      (apply + args)
    -1))

(defn bst-indexof [key col]
  (if (empty? col)
   -1