trampoline for mutual recursion

769 views
Skip to first unread message

Rich Hickey

unread,
Nov 25, 2008, 9:05:06 AM11/25/08
to Clojure
I've added trampoline to ease the conversion/creation of mutually
recursive algorithms in Clojure.

Trampolines are a well known technique for implementing TCO - instead
of actually making a call in the tail, a function returns the function
to be called, and a controlling loop calls it, thus allowing chained
execution without stack growth.

In order to do this I've made the following changes (SVN 1122):

Added clojure.lang.Fn marker interface, used on all true fns.
Breaking change - fn? now tests for Fn, not IFn (this was frequently
requested)
Added ifn? which will test for anything callable (IFn)
Added trampoline, implements trampoline protocol for TCO

Here's how it works. Normally, if you have mutual recursion (i.e.
which can't be replaced with recur), you can blow the stack:

(declare bar)

(defn foo [n]
(if (pos? n)
(bar (dec n))
:done-foo))

(defn bar [n]
(if (pos? n)
(foo (dec n))
:done-bar))

(foo 1000000)
-> java.lang.StackOverflowError

To convert to a trampoline, simply return closures over your tail
calls, rather than direct calls. This is as simple as prepending #

(declare bar)

(defn foo [n]
(if (pos? n)
#(bar (dec n))
:done-foo))

(defn bar [n]
(if (pos? n)
#(foo (dec n))
:done-bar))

Then make the top-level call via trampoline:

(trampoline #(foo 1000000))
-> :done-foo

Rich

Stephen C. Gilardi

unread,
Nov 25, 2008, 10:42:30 AM11/25/08
to clo...@googlegroups.com

On Nov 25, 2008, at 9:05 AM, Rich Hickey wrote:

I've added trampoline to ease the conversion/creation of mutually recursive algorithms in Clojure.

Very cool! Thanks for enabling that.

In looking over the implementation, I found a small problem: the arg vector precedes the doc string leading to:

user=> (doc trampoline)
-------------------------
clojure.core/trampoline
([f])
  nil
nil

--Steve

Rich Hickey

unread,
Nov 25, 2008, 11:07:29 AM11/25/08
to Clojure


On Nov 25, 10:42 am, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> On Nov 25, 2008, at 9:05 AM, Rich Hickey wrote:
>
> > I've added trampoline to ease the conversion/creation of mutually
> > recursive algorithms in Clojure.
>
> Very cool! Thanks for enabling that.
>
> In looking over the implementation, I found a small problem: the arg
> vector precedes the doc string leading to:
>

Fixed (SVN 1123) - thanks for the report.

I've also added support for passing initial args, so the top-level
call can be:

(trampoline foo 1000000)

Rich

steven...@gmail.com

unread,
Nov 25, 2008, 1:22:14 PM11/25/08
to Clojure
I think this will be very useful. Now if only we can convince Sun to
make it unnecessary...

-- Steve

samppi

unread,
Nov 25, 2008, 2:19:32 PM11/25/08
to Clojure
Yes, this is superb—I was just now trying to figure out a complicated
tree zipper that mutual recursion would make needless. Thanks a lot!

On Nov 25, 11:22 am, "steve...@acm.org" <steven.hu...@gmail.com>
wrote:

jim

unread,
Nov 25, 2008, 5:17:02 PM11/25/08
to Clojure
Very nice. Thanks, Rich.

I had implemented my own version, but it's much nicer to have it in
the language.

Jim

kib2

unread,
Nov 25, 2008, 4:17:32 PM11/25/08
to Clojure
Thanks Rich,

funny, there was a post on trampoline in the Python community today :
http://davywybiral.blogspot.com/2008/11/trampolining-for-recursion.html

dreish

unread,
Nov 26, 2008, 10:28:43 AM11/26/08
to Clojure
Now that you've gone this far, why not do this?

- class clojure.lang.TailCall contains an AFn
- Compiler checks for a tail call position and instead of calling it,
returns new TailCall(AFn)
- In invoke, while returnvalue instanceof TailCall, returnvalue =
returnvalue.fn.invoke(returnvalue)

I confess I don't yet have much familiarity with the compiler; I'm
just reading through it now. Is the above idea workable?

Upside: you could have real TCO tonight, with J2SE 5.

Downside: as soon as they finally get around to putting TCO in the
JVM, it becomes useless cruft.

I would think you could take it back out, though. And who knows when
they'll finally do it? And wouldn't it be better to put TCO workaround
cruft in the compiler, rather than in the language definition, around
which people are already (foolishly, perhaps) starting to build
serious programs?

Rich Hickey

unread,
Nov 26, 2008, 11:14:04 AM11/26/08
to Clojure


On Nov 26, 10:28 am, dreish <dresweng...@dreish.org> wrote:
> Now that you've gone this far, why not do this?
>
> - class clojure.lang.TailCall contains an AFn
> - Compiler checks for a tail call position and instead of calling it,
> returns new TailCall(AFn)
> - In invoke, while returnvalue instanceof TailCall, returnvalue =
> returnvalue.fn.invoke(returnvalue)
>
> I confess I don't yet have much familiarity with the compiler; I'm
> just reading through it now. Is the above idea workable?
>
> Upside: you could have real TCO tonight, with J2SE 5.
>
> Downside: as soon as they finally get around to putting TCO in the
> JVM, it becomes useless cruft.
>
> I would think you could take it back out, though. And who knows when
> they'll finally do it? And wouldn't it be better to put TCO workaround
> cruft in the compiler, rather than in the language definition, around
> which people are already (foolishly, perhaps) starting to build
> serious programs?
>

There's a very simple reason - such built-in trampolines are
incompatible with interoperability. Anyone can build a trampoline
system into their lang to get tail calls and make sure it is used
consistently within lang - but what do those TailCall return values
mean to a Java caller?

Also, in what you've described every invoke turns into a loop, every
tail call allocates etc.

I made a conscious decision here, and it was a pragmatic one. People
using Clojure are pragmatic, not foolish.

The vast majority of tail calls requiring TCO are self-calls handled
by recur.

I'm all for TCO, but trampolines are simplistic TCO and no substitute
for real jumps.

Rich

dreish

unread,
Nov 26, 2008, 1:00:59 PM11/26/08
to Clojure
On Nov 26, 11:14 am, Rich Hickey <richhic...@gmail.com> wrote:
> There's a very simple reason - such built-in trampolines are
> incompatible with interoperability. Anyone can build a trampoline
> system into their lang to get tail calls and make sure it is used
> consistently within lang - but what do those TailCall return values
> mean to a Java caller?

Thanks. I was uneasy enough about performance, without really
understanding how much of a problem it would be, but interop would be
a deal-killer. Guess it's back to waiting.

From http://blogs.sun.com/jrose/entry/tail_calls_in_the_vm I can at
least hope it's not too far away, although it sounds like it'll never
happen for method calls looked up with reflection.

> The vast majority of tail calls requiring TCO are self-calls handled
> by recur.

My favorite thing about recur is that the compiler tells you
immediately if you accidentally put it somewhere other than in a tail
position. You don't have to wait for the stack to overflow in actual
use because your test case was too small. I would hope the keyword
sticks around even if TCO gets added to the JVM.

Chouser

unread,
Nov 26, 2008, 1:44:36 PM11/26/08
to clo...@googlegroups.com
On Wed, Nov 26, 2008 at 1:00 PM, dreish <dresw...@dreish.org> wrote:
>
> My favorite thing about recur is that the compiler tells you
> immediately if you accidentally put it somewhere other than in a tail
> position. You don't have to wait for the stack to overflow in actual
> use because your test case was too small. I would hope the keyword
> sticks around even if TCO gets added to the JVM.

Hear, hear! +1 Can I only vote once? +10

:-)

Hm, maybe a general compile-time assert would be in order, once we
have real tail-call optimization, so that even in the mutual-recursion
case you could get a nice error if you make a mistake like:

(def foo []
(+ 10
(tail-call bar 1 2)))

Although something less ugly might be nice.

--Chouser

Randall R Schulz

unread,
Nov 26, 2008, 1:56:55 PM11/26/08
to clo...@googlegroups.com
Hi,

On Tuesday 25 November 2008 06:05, Rich Hickey wrote:
> I've added trampoline to ease the conversion/creation of mutually
> recursive algorithms in Clojure.
>

> ...

Clojure's new trampolines for mutually recursive functions has caught
the attention of the Scala folks. There's a nice thread going on in the
Scala-Debate list beginning with one user's mention of this new
capability in Clojure. Two people there (one of them being Martin
Odersky, the head architect of the Scala language) showed a comparable
solution written in Scala.

Check it out:
- Subject: "Tail calls via trampolining and an explicit instruction"
- <http://dir.gmane.org/gmane.comp.lang.scala.debate>
- <http://www.nabble.com/Scala---Debate-f30218.html>
<http://www.nabble.com/Tail-calls-via-trampolining-and-an-explicit-instruction-td20702915.html>


Randall Schulz

Mark Volkmann

unread,
Nov 26, 2008, 3:22:30 PM11/26/08
to clo...@googlegroups.com
On Tue, Nov 25, 2008 at 8:05 AM, Rich Hickey <richh...@gmail.com> wrote:

big snip

> To convert to a trampoline, simply return closures over your tail
> calls, rather than direct calls. This is as simple as prepending #
>
> (declare bar)
>
> (defn foo [n]
> (if (pos? n)
> #(bar (dec n))

I'm curious about this syntax. I thought if #(function-name args)
creates a closure then I can put one in a variable and execute it
later. I entered this in a REPL.

(def myClosure #(prn "Hello"))

How can I execute the closure in myClosure now?

--
R. Mark Volkmann
Object Computing, Inc.

Chouser

unread,
Nov 26, 2008, 3:26:58 PM11/26/08
to clo...@googlegroups.com
On Wed, Nov 26, 2008 at 3:22 PM, Mark Volkmann
<r.mark....@gmail.com> wrote:
>
> I'm curious about this syntax. I thought if #(function-name args)
> creates a closure then I can put one in a variable and execute it
> laterI entered this in a REPL.

>
> (def myClosure #(prn "Hello"))
>
> How can I execute the closure in myClosure now?

user=> (myClosure)
"Hello"

or now,

user=> (trampoline myClosure)
"Hello"

--Chouser

Stephen C. Gilardi

unread,
Nov 26, 2008, 3:27:37 PM11/26/08
to clo...@googlegroups.com

On Nov 26, 2008, at 3:22 PM, Mark Volkmann wrote:

I entered this in a REPL.

(def myClosure #(prn "Hello"))

How can I execute the closure in myClosure now?

Clojure
user=> (def myClosure #(prn "Hello"))
#'user/myClosure
user=> (myClosure)
"Hello"
nil
user=> 

--Steve

lpetit

unread,
Nov 26, 2008, 4:32:58 PM11/26/08
to Clojure
On 25 nov, 15:05, Rich Hickey <richhic...@gmail.com> wrote:

> To convert to a trampoline, simply return closures over your tail
> calls, rather than direct calls. This is as simple as prepending #

I've maybe missed something, but will this work if one wants to make
the final return value of the tail call a closure ?
Will the closure not be called by the trampoline ?
(Maybe I've missed something regarding the explanation on Fn / IFn,
not clear to me)

If I'm right, then should there be some "marker" to wrap the returned
closure in, that will be checked by the trampoline for this special
case, which will then unwrap the closure and return it as the final
returned value ?

HTH,

--
Laurent

Stephen C. Gilardi

unread,
Nov 26, 2008, 4:38:50 PM11/26/08
to clo...@googlegroups.com

On Nov 26, 2008, at 4:32 PM, lpetit wrote:

I've maybe missed something, but will this work if one wants to make
the final return value of the tail call a closure ?

Along the same lines of this being a manual way to do TCO, that issue will need to be handled manually as well. Here's what (doc trampoline) has to say about it:

user=> (doc trampoline)
-------------------------
clojure.core/trampoline
([f] [f & args])
  trampoline can be used to convert algorithms requiring mutual
  recursion without stack consumption. Calls f with supplied args, if
  any. If f returns a fn, calls that fn with no arguments, and
  continues to repeat, until the return value is not a fn, then
  returns that non-fn value. Note that 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.
nil

--Steve

André Thieme

unread,
Nov 26, 2008, 5:40:35 PM11/26/08
to Clojure


On 26 Nov., 21:26, Chouser <chou...@gmail.com> wrote:
> On Wed, Nov 26, 2008 at 3:22 PM, Mark Volkmann
>
> <r.mark.volkm...@gmail.com> wrote:
>
> > I'm curious about this syntax. I thought if #(function-name args)
> > creates a closure then I can put one in a variable and execute it
> > laterI entered this in a REPL.
>
> > (def myClosure #(prn "Hello"))
>
> > How can I execute the closure in myClosure now?

Hello Mark, maybe something got mixed up here:
#(prn "Hello") looks like an ordinary anonymous function to me,
and not like a closure.
Well, it depends on how we want to define “closure”.
I think the definition should include that it must be a function
(be it a named or anon one) that closes over some lexical
environment. In my opinion this environment should not be the
trivial one: the empty one.
We could do this, but in that case every function would be a
closure. So from that I would say that the given example was
not for a closure.

Maybe a simple accumulator could work here:
user> (let [acc (ref 0)]
(defn make-accumulator [n]
(dosync (ref-set acc n))
(fn [i]
(dosync (alter acc + i)))))
#'user/make-accumulator

So, here make-accumulator is a closure.
It closes over acc.
And the anon function that is returned by
make-accumulator is also a closure, as it
also closes over acc.

Mark Volkmann

unread,
Nov 26, 2008, 5:51:55 PM11/26/08
to clo...@googlegroups.com

Thanks! In the meantime I came up with an even simpler example that
demonstrates capturing a parameter and a local variable in a closure.

(defn greet-closure [name]
(let [salutation "Hello"]
#(println salutation name)))
(def my-closure (greet-closure "Mark"))
(my-closure)

outputs "Hello Mark"

Robert Pfeiffer

unread,
Nov 27, 2008, 5:21:12 AM11/27/08
to Clojure
On 26 Nov., 22:38, "Stephen C. Gilardi" <squee...@mac.com> wrote:

>    [..] Note that 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.

If you want to return sets, keywords, maps, or everything that
implements the fn interface this is also an issue. Does trampolining
on keywords make sense?

Robert Pfeiffer

Meikel Brandmeyer

unread,
Nov 27, 2008, 7:06:34 AM11/27/08
to Clojure
Hi,

On 26 Nov., 23:40, André Thieme <splendidl...@googlemail.com> wrote:
> Maybe a simple accumulator could work here:
> user> (let [acc (ref 0)]
>         (defn make-accumulator [n]
>           (dosync (ref-set acc n))
>           (fn [i]
>             (dosync (alter acc + i)))))
> #'user/make-accumulator
>
> So, here make-accumulator is a closure.
> It closes over acc.
> And the anon function that is returned by
> make-accumulator is also a closure, as it
> also closes over acc.

Maybe I have a wrong understanding of "closure", but
as far as I understand, every function definition in
Clojure - be it defn or #() - finally translates to (fn ...).
And fn creates a closure. In fact #(prn "Hello") closes
over the var "prn". Consider the following example:

(ns foo.bar)

(def my-closure #(prn "Hello"))

(ns yoyo.dyne
(:refer-clojure
:exclude (prn)))

(defn prn [x] (clojure.core/prn (str "Modified: " x)))

(foo.bar/my-closure)

According to my understanding the output should
be "Hello".

I think the closure is never "empty". It refers to the
environment used at the closure's creation time.
Whether this environment is accessed or not, is not
very interesting, I think.

Ok. Maybe there are gc issues, so one might want
to optimise this. But a closure which, does not
access the environment at all... What would this
look like and which use would it have?

Sincerely
Meikel

Stephen C. Gilardi

unread,
Nov 27, 2008, 7:13:39 AM11/27/08
to clo...@googlegroups.com

On Nov 27, 2008, at 5:21 AM, Robert Pfeiffer wrote:

If you want to return sets, keywords, maps, or everything that
implements the fn interface this is also an issue. Does trampolining
on keywords make sense?

The svn revision that introduced trampoline also introduced a "marker" interface "fn" that distinguishes "things ultimately produced by fn" and "thinks that can be called". The former are the only things that are trampolined. It also changed the behavior if fn? and introduced ifn? that know about the difference. Here's an example:

Clojure
user=> (fn? :hi)
false
user=> (fn? #(print "hi"))
true

user=> (ifn? :hi)
true
user=> (ifn? #(print "hi"))
true
user=> 

See also:


--Steve

Stephen C. Gilardi

unread,
Nov 27, 2008, 7:16:20 AM11/27/08
to clo...@googlegroups.com

On Nov 27, 2008, at 7:13 AM, Stephen C. Gilardi wrote:

> interface "fn" that distinguishes

The interface is "clojure.lang.Fn".

--Steve

lpetit

unread,
Nov 27, 2008, 7:58:36 AM11/27/08
to Clojure
Thank you for the answer.

Could trampoline benefit for being enhanced by allowing an explicit
"escaping" for a return value of type function (that could also work
for other return types, but would not be necessary for the common
case).

Something like these :

- common usage : as usual
user=> (def myClosure #(prn "Hello"))
#'user/myClosure
user=> (trampoline myClosure)
"Hello"

- explicit escape via a "noboing" (or "stop" or "return" any name you
like) call (works for any return type) :
user=> (def myClosure (noboing #(prn "Hello")))
#'user/myClosure
user=> (trampoline myClosure)
#'user/myClosure

And it could be implemented as :
public final class org.clojure.lang.NoBoingWrapper {
public final Object returnInstance;
public NoBoingWrapper(Object returnInstance)
{ this.returnInstance = returnInstance; }
}

(defn noboing [returnInstance] (org.clojure.lang.NoBoingWrapper.
returnInstance))

and the modification of trampoline along these lines :
(defn trampoline [f]
(let [ret (f)]
(cond f
(fn? ret) (recur ret)
(instance? org.clojure.lang.NoBoingWrapper f) (.returnInstance
f)
else ret)))


HTH,

--
Laurent

lpetit

unread,
Nov 27, 2008, 8:37:18 AM11/27/08
to Clojure
On Nov 27, 1:58 pm, lpetit <laurent.pe...@gmail.com> wrote:
> and the modification of trampoline along these lines :
> (defn trampoline [f]
>   (let [ret (f)]
>      (cond f
>        (fn? ret) (recur ret)
>        (instance? org.clojure.lang.NoBoingWrapper f) (.returnInstance
> f)
>        else ret)))

Mmm might read (cond ret , and also (instance?
org.clojure.lang.NoBoingWrapper ret) (.returnInstance ret) of course,

--
Laurent

Rich Hickey

unread,
Nov 27, 2008, 12:09:09 PM11/27/08
to Clojure
I considered that, and it's still a possibility, but I don't want
people thinking they need to call (trampoline-return x) all the time.
The only time you need to wrap the return value is when the result is
an actual fn.

But it is nice to do the unwrapping in trampoline itself.

My thinking is that such mutually-recursive state machines are
designed of-a-piece, so any wrapping protocol would be local, and I
wanted to minimize the amount of cruft one would have to add to use a
trampoline.

Rich

jim

unread,
Nov 27, 2008, 12:20:19 PM11/27/08
to Clojure
Rich,

I'm currently working on some code where I'm implementing state
machines where each state is a function. To move to another state,
the current state returns the function of the next state and
trampoline runs the machine through to completion. My next step is to
have each state return a value in addition to the function for the
next state, and the result from running the state machine will be a
list of values from each state. Writing a specific trampoline to
extract the list of return values and call the next state function in
a lazy manner is easy to implement.

As you say, this is an of-a-piece design, so I would vote that
trampoline itself should be kept cruft-free.

My $.02

Jim

lpetit

unread,
Nov 27, 2008, 5:39:28 PM11/27/08
to Clojure
On 27 nov, 18:09, Rich Hickey <richhic...@gmail.com> wrote:
> > > (defn trampoline [f]
> > >   (let [ret (f)]
> > >      (cond f
> > >        (fn? ret) (recur ret)
> > >        (instance? org.clojure.lang.NoBoingWrapper f) (.returnInstance
> > > f)
> > >        else ret)))
> I considered that, and it's still a possibility, but I don't want
> people thinking they need to call (trampoline-return x) all the time.
> The only time you need to wrap the return value is when the result is
> an actual fn.

Well, actually the above implementation allows to not use (trampoline-
return) for all common cases, and would just be a standard work-around
in the fn-as-value returning case. Isn't it more a matter of where to
put the focus on the documentation.

Let's try a modified version of trampoline doc with (trampoline-
return) explanation added :
"
trampoline can be used to convert algorithms requiring mutual
recursion without stack consumption. Calls f with supplied args, if
any. If f returns a fn, calls that fn with no arguments, and
continues to repeat, until the return value is not a fn, then
returns that non-fn value. Note that if you want to return a fn as
a
final value, wrap it in a call to trampoline-return (or wrap your
fn in some data structure of your own, and unpack it manually after
trampoline returns).
"

> But it is nice to do the unwrapping in trampoline itself.
Yes, there is just one special case, why not provide a standard way to
handle it ?

André Thieme

unread,
Nov 28, 2008, 4:56:33 PM11/28/08
to Clojure
On 27 Nov., 13:06, Meikel Brandmeyer <m...@kotka.de> wrote:

Hello.

> Maybe I have a wrong understanding of "closure", but
> as far as I understand, every function definition in
> Clojure - be it defn or #() - finally translates to (fn ...).
> And fn creates a closure.

Well, from my experience I can say that a lot of people
think that “anon function = closure”, which would be
fn in Clojure or lambda in Common Lisp.
This however is not generally correct. In my previous
posting I gave an example of how a named function
became a closure.


> In fact #(prn "Hello") closes
> over the var "prn". Consider the following example:
>
> (ns foo.bar)
>
> (def my-closure #(prn "Hello"))

Inside the namespace foo.bar the function
clojure.core/prn is visible. I think that when you
define my-closure the compiler inserts the hard
address of clojure.core/prn to know where to jump
when called. There is nothing variable bound.
It is the same as if you did that while being in
the clojure.core namespace. “prn” is globally
visible, it is a special variable, not a lexical
one. Your my-closure captures the empty lexical
environment which I would explicitly like to
exclude from a definition of “closure”.


> (ns yoyo.dyne
>   (:refer-clojure
>     :exclude (prn)))
>
> (defn prn [x] (clojure.core/prn (str "Modified: " x)))
>
> (foo.bar/my-closure)
>
> According to my understanding the output should
> be "Hello".

I agree. Having the namespace foo.bar did not
change anything important here, we could have done
the same inside user or clojure.core.
While you said (defn my-clojure ...) you accessed
something from the global namespace.
When someone sees the isolatedcode of a closure this
person would have to ask: “What is this variable x??
I can not see it's definition”, as in:

(fn [n] (+ n x))

x may be a global variable, in which this anon
function would not be a closure. Or this fn is
embedded inside a let or fn or whatever, where
x is lexically visible and the fn implicitly
“inherits” it.


> I think the closure is never "empty". It refers to the
> environment used at the closure's creation time.
> Whether this environment is accessed or not, is not
> very interesting, I think.

As I see it we had examples where the lexical
environment was empty.
Global capture is no magic, but the whole reason for
having global vars.
But even in the case we would ignore that: I would still
vote against calling these guys closures, simply as in
my opinion any definition is not qualified, which implies
that *all* functions are closures. It makes not much sense
to invent this special word and confuse thousands of
people with it who are eager to learn what closures really
are, when they are in the end nothing but functions.

Meikel Brandmeyer

unread,
Nov 28, 2008, 5:29:19 PM11/28/08
to clo...@googlegroups.com
Hi André,

Am 28.11.2008 um 22:56 schrieb André Thieme:
>> Maybe I have a wrong understanding of "closure", but
>> as far as I understand, every function definition in
>> Clojure - be it defn or #() - finally translates to (fn ...).
>> And fn creates a closure.

I tooled myself up and looked up the definition of "closure"
on Wikipedia. It seems that the definition says "one or more
bound variables". I still don't see why the "empty" environment
should that much of a special case. Why not just say:
"a closure keeps its environment". Why should it matter
whether its empty or not?

> Well, from my experience I can say that a lot of people
> think that “anon function = closure”, which would be
> fn in Clojure or lambda in Common Lisp.
> This however is not generally correct. In my previous
> posting I gave an example of how a named function
> became a closure.

There is no thing like a named function. defn expands
to (def ... (fn ...)). So an anonymous function is assigned
to a Var which has a name.

anon function != closure. This happens to be a feature
of Clojure, that it turns functions into closures.

Consider the GCC C extension for inner functions:

struct some_thing
do_something(int x)
{
int
do_more()
{
return x + 1;
}

return call_with_fun_pointer(do_more);
}

do_more could be considered an "anonymous"
function since it is only available inside do_something.
But it is not a closure. Suppose call_with_fun_pointer
stores away the pointer and returns.

Calling do_more later on is invalid, because the
stack was unwound and x doesn't exist anymore.
This is exactly, what a closure prevents.

But the whole issue is only a misunderstanding on
my side about what a closure is, and some philosophical
point, whether the empty environment is a special
case or not...

Sincerely
Meikel

André Thieme

unread,
Nov 28, 2008, 11:40:39 PM11/28/08
to Clojure
On 28 Nov., 23:29, Meikel Brandmeyer <m...@kotka.de> wrote:
> Hi André,
>
> Am 28.11.2008 um 22:56 schrieb André Thieme:
>
> >> Maybe I have a wrong understanding of "closure", but
> >> as far as I understand, every function definition in
> >> Clojure - be it defn or #() - finally translates to (fn ...).
> >> And fn creates a closure.
>
> I tooled myself up and looked up the definition of "closure"
> on Wikipedia. It seems that the definition says "one or more
> bound variables". I still don't see why the "empty" environment
> should that much of a special case. Why not just say:
> "a closure keeps its environment". Why should it matter
> whether its empty or not?

Because then having the word “closure” would be pointless.
We could go without it, or invent other words and use them
instead. In all programming languages all functions are always
closures without exception, if we won’t care.
However, if we take the definition of Wikipedia, then it really
makes sense, because you communicate to other programmers that
something is a specific function, with specific properties.
Wikipedia says:
“...a closure may occur when a function is defined within another
function, and the inner function refers to local variables of
the outer function.”
I agree with it.
I only stress the point more, that these local variables should
exist :-)
(instead of being the empty set, as in the example of Mark)


> > Well, from my experience I can say that a lot of people
> > think that “anon function = closure”, which would be
> > fn in Clojure or lambda in Common Lisp.
> > This however is not generally correct. In my previous
> > posting I gave an example of how a named function
> > became a closure.
>
> There is no thing like a named function. defn expands
> to (def ... (fn ...)). So an anonymous function is assigned
> to a Var which has a name.

defn is an abstraction to abstract these details away.
A macro like defn allows us to really have named functions,
it’s a new concept.
Of course, under the hood everything is just zeros and ones.
We know that and we can always switch the perspective from
which we look at things.


> anon function != closure.

This is nearly correct. Often anon functions are not closures.
But in some cases they can be.


> This happens to be a feature
> of Clojure, that it turns functions into closures.

It’s probably a different definition that we use for the
word “closure”. You define it as “function object”.
I define it as “function object that captures at least
one lexical variable of it’s environment”.



> Consider the GCC C extension for inner functions:
>
> struct some_thing
> do_something(int x)
> {
>      int
>      do_more()
>      {
>          return x + 1;
>      }
>
>      return call_with_fun_pointer(do_more);
>
> }
>
> do_more could be considered an "anonymous"
> function since it is only available inside do_something.
> But it is not a closure. Suppose call_with_fun_pointer
> stores away the pointer and returns.
>
> Calling do_more later on is invalid, because the
> stack was unwound and x doesn't exist anymore.
> This is exactly, what a closure prevents.

Yes.
My addition now is: do_something is also not a closure.

Closures are in the end lightweight objects.
So, we have minimal oop here.
Reply all
Reply to author
Forward
0 new messages