Clojure to CL
27 Jan 2013Well 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