Tail call in multi method?

[bruce li]

Hello, everyone.

I'm currently trying to model an automata using multi-method. So in my code, I have something like:

(defmethod trans :state
     [state]
     ; .......
     (trans ......))))

In the last line, the trans will be called with some different state.

However, it seems that such call still consumes stack and I quickly come to a stack overflow error when the states are reached multiple times.

I'm wondering if there is some ways to optimize the code.

Thanks!

[juan.facorro]

What about recur? 

It's a special form used for tail call optimizations.

Juan

[Jonas]

recur doesn't work well with multimethods:

    (defmulti foo identity)

 

    (defmethod foo 1 [n]

      (recur (dec n)))

 

    (defmethod foo 0 [n]

      :ok)

 

    (foo 1) ;; runs forever

Jonas

[juan.facorro]

You're right, it fails when the call to recur should dispatch to another method.

But as long as you are calling the same implementation it does seem to work:

(ns multi-recur)

(defmulti tail-call #(first %&))

(defmethod tail-call :recur [x n]

  (if (zero? n)

    (println x "Made it to" n)

    (recur x (dec n))))

    

(defmethod tail-call :overflow [x n]

  (if (zero? n)

    (println x "Made it to" n)

    (tail-call x (dec n))))

  

(tail-call :recur 5000)

(tail-call :overflow 5000)

I don't know any work arounds for the situation where there dispatch resolves to another method implementation.

Juan

[Chas Emerick]

`recur` throws control flow to the nearest `loop` head or fn body, and each method is itself a function, so `recur` within a method body will simply jump to the start of the method, _not_ tail-call the multimethod.  e.g.:

=> (defmulti foo type)

#'user/foo

=> (defmethod foo Long

     [x]

     (assert (integer? x) (str "x isn't an integer! " (pr-str x)))

     (recur (str x)))

#<MultiFn clojure.lang.MultiFn@4f0ab3f2>

=> (foo 5)

AssertionError Assert failed: x isn't an integer! "4"

(integer? x)  user/eval1831/fn--1832 (NO_SOURCE_FILE:3)

What you're trying to do is really a special case of mutual recursion: because Clojure's methods are separate functions, calling back through the multimethod (and its dispatch fn) will always consume stack space.  The general solution for this is to use `trampoline`, which will continuously call through functions returned from calling a function until a non-function value is returned.  This would allow you to make your multimethod mutually-recursive, as long as those recursive calls are made by returning a function (that the user of the multimethod would `trampoline` through):

=> (defmethod foo String

     [x]

     (str "got " x "!"))

#<MultiFn clojure.lang.MultiFn@4f0ab3f2>

=> (defmethod foo Long

     [x]

     #(foo (str x)))

#<MultiFn clojure.lang.MultiFn@4f0ab3f2>

=> (foo 5)

#<user$eval1888$fn__1889$fn__1890 user$eval1888$fn__1889$fn__1890@3852fdeb>

=> (trampoline foo 5)

"got 5!"

From an API standpoint, you would presumably name the multimethod itself something like `trans*`, and expose only a helper function `trans` that would implicitly trampoline through any functions returned by `trans*`.  There is a cost associated with trampolining isn't zero, but won't swamp actual work as long as the methods are doing something nontrivial anyway.

Another option you might consider is using agents.  I see your methods already take a single state argument; this would then make it really easy to lift the automata onto an agent (or set of agents).  That state would become the agents' state, and "recursive" calls would become a `send` (or `send-off` if you're doing IO or other blocking things) to the same agent (e.g. `(send *agent* trans)`).  

Cheers,

- Chas

--
http://cemerick.com
[Clojure Programming from O'Reilly](http://www.clojurebook.com)

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Ben Wolfson]

On Mon, Dec 17, 2012 at 9:32 AM, Chas Emerick <ch...@cemerick.com> wrote:
>
> What you're trying to do is really a special case of mutual recursion:
> because Clojure's methods are separate functions, calling back through the
> multimethod (and its dispatch fn) will always consume stack space. The
> general solution for this is to use `trampoline`, which will continuously
> call through functions returned from calling a function until a non-function
> value is returned. This would allow you to make your multimethod
> mutually-recursive, as long as those recursive calls are made by returning a
> function (that the user of the multimethod would `trampoline` through):

Also as long as you don't want to return a function from the multimethod, no?

--
Ben Wolfson
"Human kind has used its intelligence to vary the flavour of drinks,
which may be sweet, aromatic, fermented or spirit-based. ... Family
and social life also offer numerous other occasions to consume drinks
for pleasure." [Larousse, "Drink" entry]

[Chas Emerick]

On Dec 17, 2012, at 12:39 PM, Ben Wolfson wrote:

> On Mon, Dec 17, 2012 at 9:32 AM, Chas Emerick <ch...@cemerick.com> wrote:
>>
>> What you're trying to do is really a special case of mutual recursion:
>> because Clojure's methods are separate functions, calling back through the
>> multimethod (and its dispatch fn) will always consume stack space. The
>> general solution for this is to use `trampoline`, which will continuously
>> call through functions returned from calling a function until a non-function
>> value is returned. This would allow you to make your multimethod
>> mutually-recursive, as long as those recursive calls are made by returning a
>> function (that the user of the multimethod would `trampoline` through):
>
> Also as long as you don't want to return a function from the multimethod, no?

Correct. As noted in the docs for `trampoline`:

...if you want to return a fn as a final value, you must wrap it in some data structure and unpack it after trampoline returns.

I can't say I've ever needed to write mutually-recursive higher-order functions. I can only presume that doing so while needing to meet trampoline's contract for that corner case would be fairly cumbersome.

IIRC, `trampoline` predated functions supporting metadata by some time. If it were written again now, it might specify that metadata should be used to indicate that a function should be called-through, rather than returned as a non-intermediate value. e.g.:

(defn meta-trampoline
([f]
(let [ret (f)]
(if (and (fn? ret) (-> ret meta :trampoline))
(recur ret)
ret)))
([f & args]
(meta-trampoline #(apply f args))))

With this, you can return whatever you want/need to, as long as you mark the self- or mutually-recursive calls with {:trampoline true} metadata:

=> (defmethod foo String
[x]

#(str "I got " x ", you gave me " %))

#<MultiFn clojure.lang.MultiFn@4f0ab3f2>
=> (defmethod foo Long
[x]

^:trampoline #(foo (str x)))
#<MultiFn clojure.lang.MultiFn@4f0ab3f2>
=> (meta-trampoline foo 5)
#<user$eval1992$fn__1993$fn__1994 user$eval1992$fn__1993$fn__1994@7466a008>
=> (*1 6)
"I got 5, you gave me 6"

Cheers,

- Chas

[bruce li]

Very helpful. Thanks so much!

2012/12/18 Chas Emerick <ch...@cemerick.com>