Wishful Coding

Didn't you ever wish your computer understood you?

How reify works, and how to write a custom type

Yesterday I had the idea of lazy sequences that can go in both directions. I dropped into #clojure on irc.freenode.net to ask someone about it.

Given the fact that Clojure-in-Clojure is possible, it is thus possible to define lazy seqs. Would it also be possible to define a lazy seq where the 0th element is actually in the middle of an infinite lazy seq extending in both ways? so like (iterate inc) with negative number included :)
I found Chris Houser(Author of Joy of Clojure) interested, and willing to help me along.

so... how shall we proceed? You want to see my code or should I try to drop hints or ask leading questions?
I went for the later one, and had a great learning experience. Near then end Paul deGrandis chimed in to recommend Joy of Clojure. I'm convinced!

Joy of Clojure has an awesome section on proxy, reify, defprotocol, and defrecord. I reference it often to judge if I'm abusing something
At the point you're at in Clojure (based on what I follow in here), you'd get a lot of mileage out of it.

Bellow You'll find a grep'd-over version of the log with most of the background noise canceled. The full log is at http://clojure-log.n01se.net/date/2010-09-24.html

The final code for my version

(ns biseq)

(defprotocol Spinnable (spin [_]))

(defn biseq [start fwd bwd]
  (reify
    clojure.lang.ISeq
    (first [this] start)
    (next [this] (biseq (fwd start) fwd bwd))
    (more [this] (.next this))
    (seq [this] this)
    Spinnable
    (spin [this] (biseq start bwd fwd))))

(extend-type clojure.lang.LazySeq
  Spinnable
  (spin [this] (spin (seq this))))

(defn spin [seq]
  (.spin seq))

(let [s (biseq 0 inc dec)]
  (println (take 10 s))
  (println (take 10 (spin s)))
  (println (take 20 ((fn f [s]
                       (lazy-seq (cons
                                   (first s)
                                   (f (rest (if (zero? (rem (first s) 5))
                                              (spin s)
                                              s)))))) s))))
;(0  1  2  3  4  5  6  7  8  9)
;(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
;(0 -1 -2 -3 -4 -5 -4 -3 -2 -1 0 -1 -2 -3 -4 -5 -4 -3 -2 -1)

and chousers version

(defprotocol Spinnable
  (spin [this] "Return a seq walking the opposite direction as this"))

(defn iter-bi [x f b]
  (reify
    Spinnable
    (spin [_] (iter-bi x b f))
    clojure.lang.ISeq
    (first [_] x)
    (more [_] (iter-bi (f x) f b))
    (next [this] (rest this))   ; same as rest since all iter-bi's are infinite seqs
    (seq [this] this)
    (equiv [_ _] false)))       ; cheater!

(extend-type clojure.lang.LazySeq
  Spinnable
  (spin [this] (spin (seq this))))

(->> (iter-bi 0 inc dec)
     (drop 4)
     spin
     (take 10))
;=> (5 4 3 2 1 0 -1 -2 -3 -4)

fliebel: Given the fact that Clojure-in-Clojure is possible, it is thus possible to define lazy seqs. Would it also be possible to define a lazy seq where the 0th element is actually in the middle of an infinite lazy seq extending in both ways? so like (iterate inc) with negative number included :)
chouser: ISeq only provides an API for walking forwards. You'd need a different interface for walking the other direction.
fliebel: Hrm :( that means I'll be unable to use with with existing functions, right?
chouser: well, what existing function do you intend to call to get item before 'first'?
fliebel: Dunno‚ I mean, if I'm not using ISeq, I can’t even use first, right?
chouser: well, your theoretical bidirectional lazy seq could implement ISeq for going forward
fliebel: Oh wait, Java, so I can implement ISeq and add my own interface and fns for going the other way.
fliebel: How about this‚ you define a lazy seq like iterate but with 2 fns, for going in either direction. then you call spin on it to change which direction you're seqing over :)
chouser: hm, interesting.
fliebel: So, what Clojure bits do I need to implement that?
chouser: a deftype and ... a function?
fliebel: *looks up deftype*
chouser: actually, just a deftype would do, though it's not quite as pretty.
fliebel: I don't think I get it.
chouser: (rseq (rest (drop 10 (IterBi. 0 inc dec)))) ;=> (5 4 3 2 1 0 -1 -2 -3 -4 -5 ...)
chouser: so that's what you wanted, right? interesting idea.
fliebel: I understand how I can do without the fn, but I don't understand deftype.
chouser: actually, you don't need deftype either. you could use reify or proxy if you prefer, and a normal function.
fliebel: I never worked with those 1.2 things before. So it's going to be a lot of learning :)
chouser: so... how shall we proceed? You want to see my code or should I try to drop hints or ask leading questions?
fliebel: the later one :) extended with my guessing and reading
fliebel: So I basically need to look up the ISeq interface and overwrite a few methods?
chouser: ok, so how would you use deftype or reify to implement an ISeq that just repeats the same value over and over
fliebel: Where can I find the ISeq interface?
fliebel: I guess it'd be (reify clojure.lang.ISeq (first [this] 1)) but that fails
fliebel: Do I need to implement all of them? Or can I just use a concrete subclass of ISeq?
chouser: just implement the ones you need for now. What happens when you call 'first' on your reify there?
fliebel: I get java.lang.AbstractMethodError when defining it, because ISeq is an abstract interface.
chouser: are you sure that's why?
fliebel: Hm, first works, but just defining it fails.
chouser: Ah, repl evaluates
chouser: yep, and after E is P
fliebel: ?
chouser: REPL
fliebel: ah
chouser: and printing a seq means walking it an printing each of the items. we're not ready for that.
fliebel: I see
chouser: so, (first ...) works. what about (next ...)?
fliebel: let me try..
fliebel: What about more and cons?
chouser: ignore them for now.
fliebel: yea, but not doing second on it still gives me the error.
chouser: it's a shame it doesn't tell you the specific method it's trying to call that fails.
fliebel: It doesn't even give a line or file.
chouser: right, so use (.printStackTrace *e)
fliebel: But seq isn't in ISeq, or is that up in Seqable?
chouser: Yea, but you can put it under ISeq in your reify
fliebel: I know, but I need to know it’s interface.
fliebel: right‚ Now I made it return a list. It prints that and *then* gives the same error.
chouser: yeah. so that final error is it calling equiv. not sure why
fliebel: hm, Do we need to fix that?
chouser: probably not
fliebel: (reify clojure.lang.ISeq (first [this] 1) (next [this] this) (seq [this] (list 1 2 3)))
chouser: do you have an ISeq handy already for your 'seq' to return?
fliebel: this?
chouser: what happens when you try it?
fliebel: I guess it'll print a lot of 1s
fliebel: okay, it does :)
chouser: good job!
fliebel: but take 10 doesn't work yet
chouser: take is calling your (unimplemented) rest method
fliebel: I keep forgetting the difference between next and rest. There aren’t any docstrings on ISeq :(
chouser: the difference between more (called by clojure.core/rest) and next only matters when being very careful about nearly vs. complete laziness.
ohpauleez: new rest is almost always what you want, except when you don't
chouser: that is, we don't really care much. So what happens if your 'more' is the same as your 'next'?
fliebel: Works :)
chouser: congrats!
fliebel: I know how to reverse it :D
chouser: :-P
chouser: ok, but you want to apply a function instead of just repeating, right? how would you do that?
fliebel: Hey, my ISeq doesn't implement clojure.lang.Reversible
chouser: hm, what are going to do about that?
fliebel: I don't think reify allows me to define multiple ancestors :(
fliebel: I would not have led you astray
fliebel: Can I nest reifies? :P
chouser: yes, but that's not what you want here.
fliebel: Nope :(
chouser: according to the deftype docs, "Each spec consists of..."?
fliebel: ah...
fliebel: I added clojure.lang.Reversible (rev [this] this)
fliebel: (. rev (rseq)) what is this?
chouser: ancient syntax. the same as (.rseq rev)
fliebel: lol
fliebel: Can we go somewhat more down the inheritance tree to find something that covers the basics? Or do we need everything customized anyway?
chouser: reify doesn't let you inherit from anything but pure interfaces.
fliebel: So what is next?
fliebel: I'm now struggling with where to keep state and how to modify things without an endless recursion.
chouser: yep. hint: fn args are state

== diner & work pause ==

fliebel: sure :) I nearly got it working :)
chouser: ok, back. That's great. what have you got?
fliebel:
(ns biseq)

(defprotocol Spinnable (spin [_]))

(defn biseq [start fwd bwd]
  (reify
    clojure.lang.ISeq
    (first [this] start)
    (next [this] (biseq (fwd start) fwd bwd))
    (more [this] (.next this))
    (seq [this] this)
    Spinnable
    (spin [this] (biseq start bwd fwd))))

(extend-type clojure.lang.LazySeq
  Spinnable
  (spin [this] (spin (seq this))))

(defn spin [seq]
  (.spin seq))

(let [s (biseq 0 inc dec)]
  (println (take 10 s))
  (println (take 10 (spin s)))
  (println (take 20 ((fn f [s]
                       (lazy-seq (cons
                                   (first s)
                                   (f (rest (if (zero? (rem (first s) 5))
                                              (spin s)
                                              s)))))) s))))
;(0  1  2  3  4  5  6  7  8  9)
;(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
;(0 -1 -2 -3 -4 -5 -4 -3 -2 -1 0 -1 -2 -3 -4 -5 -4 -3 -2 -1)
chouser: nice!
fliebel: thanks :) You're a good teacher :)
chouser: I think that's the same as what I have. but you said "nearly"?
fliebel: The problem I had was that first was defined as the first of this, but I couldn't do (first this) of course.
chouser: if you want to "check" your answer:
(defprotocol Spinnable
  (spin [this] "Return a seq walking the opposite direction as this"))

(defn iter-bi [x f b]
  (reify
    Spinnable
    (spin [_] (iter-bi x b f))
    clojure.lang.ISeq
    (first [_] x)
    (more [_] (iter-bi (f x) f b))
    (next [this] (rest this))   ; same as rest since all iter-bi's are infinite seqs
    (seq [this] this)
    (equiv [_ _] false)))       ; cheater!

(extend-type clojure.lang.LazySeq
  Spinnable
  (spin [this] (spin (seq this))))

(->> (iter-bi 0 inc dec)
     (drop 4)
     spin
     (take 10))
;=> (5 4 3 2 1 0 -1 -2 -3 -4)
fliebel: this is your version?
chouser: yep
fliebel: very close :) Only you have equiv defined and next uses more. Does it matter if you use (.more method call) or rest?
chouser: not really. yours is probably faster
but duplicates half a line of code. :-)
fliebel: yea... :(
chouser: so take your pick. what you've got is good.
fliebel: One problem I have is that drop 5 returns a lazy seq which I can't reverse.
chouser: yeah, you see how I work around that in my example?
fliebel: rest, I used seq to do the job
chouser: oh! smart!
chouser: interesting -- I hadn't considered that, and wouldn't have been sure it would work. nicely done.
fliebel: I wasn’t sure it would work, but seq is magic you know...
fliebel: One thing I haven't figured out yet is how to make a seq that goes 1 2 3 4 5 4 3 2 1, so changes direction in the middle.
chouser: ((fn f [s] (lazy-seq (cons (first s) (f (rest (if (zero? (rem (first s) 5)) (rseq (seq s)) s)))))) (iter-bi 1 inc dec))
fliebel: I'm going to try and understand :)
chouser: BTW, I wanted to call attention to my comment on rseq. I think we're abusing it here and probably ought to define a new protocol instead. (defprotocol Spinnable (spin [_])) or something.
fliebel: Okay. that simple?
chouser: yep
fliebel: So now in reify I replace reversible with spinnable?
chouser: there, now you don't have to call seq manually on lazy-seqs:
(defprotocol Spinnable
  (spin [this] "Return a seq walking the opposite direction as this"))

(defn iter-bi [x f b]
  (reify
    Spinnable
    (spin [_] (iter-bi x b f))
    clojure.lang.ISeq
    (first [_] x)
    (more [_] (iter-bi (f x) f b))
    (next [this] (rest this))   ; same as rest since all iter-bi's are infinite seqs
    (seq [this] this)
    (equiv [_ _] false)))       ; cheater!

(extend-type clojure.lang.LazySeq
  Spinnable
  (spin [this] (spin (seq this))))

(->> (iter-bi 0 inc dec)
     (drop 4)
     spin
     (take 10))
;=> (5 4 3 2 1 0 -1 -2 -3 -4)
fliebel: What? You can just add behavior to existing types? Am I in #ruby?
chouser: nope. in clojure we do it without monkey patching or adapter classes. :-)
chouser: I mean "nope" you're not in #ruby. Of course you can write new functions that take existing classes as args that then do their own thing with them.
fliebel: But you just added extra behavior to LazySeq, right?
dnolen: it's a properly namespaced extension tho. It's not visible to other namespaces.
chouser: it certainly looks like I did. In this case we could have written spin like: (defn spin [x] (if (instance? LazySeq x) ...))) right?
fliebel: I think so...
chouser: it's our function, we just defined it with defprotocol which allows us to add new cases on the fly
fliebel: yay
chouser: essentially. Except then rhickey sprinkled it with magic dust to make it very fast.
fliebel: :)
chouser: it's good to know not everyone knows about this yet -- it's my topic at Strange Loop
fliebel: oh, I feel special now :)
chouser: good I'm glad! But... why?
fliebel: Because I know something not everyone knows ;)
chouser: ah, good!
fliebel: Except that I'm not o sure yet what exactly you just said. Only that it's magic and fast. Two things I like especially.
chouser: Here are the basics: http://clojure.org/datatypes
fliebel: I tried to read that this morning, but maybe with my new knowledge I can understand it.
ohpauleez: Joy of Clojure has an awesome section on proxy, reify, defprotocol, and defrecord. I reference it often to judge if I'm abusing something
chouser: thanks. didn't want to say it myself. :-)
ohpauleez: At the point you're at in Clojure (based on what I follow in here), you'd get a lot of mileage out of it.
ohpauleez: and the biggest problem I had in clojure was deciding, "when"
fliebel: “when”?
ohpauleez: Joy of Clojure it helped me a lot with that
ohpauleez: In Clojure, you have this whole array of functionality. Take concurrency
we all have that little chart burned in our brains by now
we know vars and atoms and agents
but when should I be using promises over futures, or when am I abusing a future and should really be using an agent
when should I use protocols and not some other small hack
fliebel: right… I have that problem a lot indeed
ohpauleez: Joy of Clojure is structured by answering when, and for me, that pulled it all together.
chouser: that's very encouraging, thanks.
fliebel: wow, under 10 there is a whole set of "when to use … "
Pepijn de Vos