How to make an anonymous recursive function?

[Helmar]

It's not nice to always write something like:

var q func(p [][]byte);
q = func(p [][]byte) {
...
q(...);
...
};

Is there a better way?

Regards,
-Helmar

[Helmar]

Hi,

sorry for moving this topic a little bit up: but I now think it's a
major issue with a language to provide anonymous functions and not to
provide access to recursion. That workaround by using a variable name
is not fine at all if the variable content is intended to be changed
in a bounding function (or even in the recursive function itself -
this would be probably a complicated to trace error that could occur
in case of a go-routine).

I'd recommend a "pseudo"-function that is called recurse() to
implement a recursive call to the function (even to named functions).
It would even help optimizers to work out optimizations that are
possible with recursive calls. Also it makes debugging easier in the
possibility to quickly rename say foo() to _foo() where still all
recursive calls remain to what they where intended.

Regards,
-Helmar

[smosher]

You seem to be asking for an anonymous, unbound, recursive function.
Does *any* language support that?

On Nov 16, 5:48 am, Helmar <hel...@gmail.com> wrote:

[Friedemann Altrock]

JavaScript!

other(function (a, b){
return a+b==0?1:arguments.callee(a-1,b-1);
});
--
Regards
Friedemann Altrock

[Helmar]

Hi,

On Nov 16, 7:42 am, smosher <dark.nowh...@gmail.com> wrote:
> You seem to be asking for an anonymous, unbound, recursive function.
> Does *any* language support that?

yes, Forth for example. http://maschenwerk.de/DPANS/dpans6.htm#6.1.2120
You could have this for a :NONAME http://maschenwerk.de/DPANS/dpans6.htm#6.2.0455
for example. Well, that "noname" is dynamically generated in some
cases ;)
Well, and I ask for an anonymous recursive function. That's just an
anonymous function that utilized recursive calls.

Regards,
-Helmar

[Helmar]

Might be, I've to be more concrete about what problems I do have with
that "anonymous recursive funcs":

// pd.Pages() returns an array with references to the pages of the
PDF.
func (pd *PdfReaderT) Pages() [][]byte {
if pd.pages != nil {
return pd.pages
}
pages := pd.Dic(pd.Dic(pd.Trailer["/Root"])["/Pages"]);
pd.pages = make([][]byte, pd.Num(pages["/Count"]));
cp := 0;
done := make(map[string]int);

var q func(p [][]byte);
q = func(p [][]byte) {

for k := range p {
if _, wrong := done[string(p[k])]; !wrong {
done[string(p[k])] = 1;
if kids, ok := pd.Dic(p[k])["/Kids"]; ok {
q(pd.Arr(kids))
} else {
pd.pages[cp] = p[k];
cp++;
}
} else {
panic("Bad Page-Tree!")
}
}
};
q(pd.Arr(pages["/Kids"]));
return pd.pages;
}

You can see the complete code at http://code.google.com/p/pdfreader/source/browse/

Here for very good reason I declared something called "done" - this is
a recursion stopper. I did not want to make this global to the package
since other instances eg. from go-routines should be able to use this
function. So to keep scope and allocation together I had to make a
local function. And it had to be recursive. I'm not simply a little
bit angry about the syntax, but also about the needed "q(pd.Arr
(kids))" to achieve recursion. Would I have something that changes q -
eg. when starting different go-routines, this would cause mess at it's
best. This would not be needed if introducing a pseudo function called
recurse().

Regards,
-Helmar

[Krzysiek Goj]

On 16 Lis, 12:42, smosher <dark.nowh...@gmail.com> wrote:
> You seem to be asking for an anonymous, unbound, recursive function.
> Does *any* language support that?

It can be done using Y combinator in some languages.

WARNING: Y combinators are evil brain twisters, prepare for some
serious mental pain.
http://en.wikipedia.org/wiki/Y_combinator
http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html

It's more about CS theory and torturing your language's type system
than having any practical value,
but still, it would be interesting to see if one can implement Y
combinator in Go.

[Ben Tilly]

On Mon, Nov 16, 2009 at 5:58 AM, Krzysiek Goj <krzysz...@gmail.com> wrote:
> On 16 Lis, 12:42, smosher <dark.nowh...@gmail.com> wrote:
>> You seem to be asking for an anonymous, unbound, recursive function.
>> Does *any* language support that?
>
> It can be done using Y combinator in some languages.
>
> WARNING: Y combinators are evil brain twisters, prepare for some
> serious mental pain.
> http://en.wikipedia.org/wiki/Y_combinator
> http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html

My favorite explanation of the Y-combinator is the one I did in
JavaScript. See
http://www.mail-archive.com/bost...@mail.pm.org/msg02716.html for
details.

> It's more about CS theory and torturing your language's type system
> than having any practical value,
> but still, it would be interesting to see if one can implement Y
> combinator in Go.

I started this post planning to say, "Of course you can, here is how
you do it." I quickly moved to saying, "The type system causes
serious pain but here is how to do it." And then I wound up at, "You
can't do it."

If I'm right that you can't do it, then I learned something and I'm
quite surprised. I thought that anonymous functions and closures is
enough to do the Y-combinator and apparently it isn't.

The problem is that the Y-combinator requires you to have a function
that can accept itself as an argument. But what type will that
function have? The type signature has to include itself in the type
signature, but there is no way that I know of to define a recursive
type.

Illustrating it with a simpler case, one of the intermediate forms
that I showed on the way to the Y-combinator is

// No assignment this time.
function (builder, n) {
return builder(builder, n);
}(
function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
},
5
);

Let's focus on this piece of the JavaScript:

function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
}

Now try to write it in Go:

func (recurse ..., n int) int {
if 0 == n {
return 1;
}
else {
return recurse(recurse, n - 1);
}
}

But here is the challenge. The ... bit has to wind up being the type
signature for the overall function! So if we expand that type
definition we get

func (recurse ..., n int) int
func (recurse func (..., int) int, n int) int
func (recurse func (func (..., int) int, int) int, n int) int
.
.
.

and we can never write out the recursive type definition.

There may be a way around this with the reflect package. But even if
there is the pain of putting types on higher order functions is enough
that I don't expect those techniques to ever be popular in Go.

Cheers,
Ben

[Russ Cox]

On Mon, Nov 16, 2009 at 02:48, Helmar <hel...@gmail.com> wrote:
> It's not nice to always write something like:
>
> var q func(p [][]byte);
> q = func(p [][]byte) {
>  ...
>  q(...);
>  ...
> };
>
> Is there a better way?

No, but this seems perfectly fine.
Once you learn this solution, you also know how to
solve the more general case of mutually recursive func
literals, so it's a better thing to learn than a special
case for singly recursive literals.

We've written >100k lines of Go code and it has come
up maybe once. That kind of frequency doesn't suggest
that a language change is warranted.

Russ

[dga]

On Nov 16, 1:56 pm, Ben Tilly <bti...@gmail.com> wrote:
> > It can be done using Y combinator in some languages.
>

> I started this post planning to say, "Of course you can, here is how
> you do it."  I quickly moved to saying, "The type system causes
> serious pain but here is how to do it."  And then I wound up at, "You
> can't do it."
>

...

> The problem is that the Y-combinator requires you to have a function
> that can accept itself as an argument.  But what type will that
> function have?  The type signature has to include itself in the type
> signature, but there is no way that I know of to define a recursive
> type.

Sure you can: You just box the function so that you don't need a
recursive type declaration. And forgive the shoe manufacturer pun:

func rebox(r interface{}, n int) int {
if 0 == n {
return(1);
}
else {
reunbox := r.(func(r interface{}, n int) int);
return (n * reunbox(r, n-1));
}
return 1; /* Notreached */
}

func return_3(r interface{}, n int) int {
return 3;
}

func main() {
fmt.Printf("Reboxing: %d\n", rebox(rebox, 5));
fmt.Printf("Reboxing with return_3: %d\n", rebox(return_3, 5));
}

-Dave

[jqb]

On Nov 16, 4:28 am, Helmar <hel...@gmail.com> wrote:
> Hi,
>
> sorry for moving this topic a little bit up: but I now think it's a
> major issue with a language to provide anonymous functions and not to
> provide access to recursion. That workaround by using a variable name
> is not fine at all if the variable content is intended to be changed
> in a bounding function (or even in the recursive function itself -
> this would be probably a complicated to trace error that could occur
> in case of a go-routine).

Try

var func_1 func(p [][]byte);
func_1 = func(p [][]byte) {
...
func_1(...);
}

q := func1;
...
q = something_else;

[Ben Tilly]

On Mon, Nov 16, 2009 at 10:01 PM, dga <dave.a...@gmail.com> wrote:
> On Nov 16, 1:56 pm, Ben Tilly <bti...@gmail.com> wrote:

[...]

>> The problem is that the Y-combinator requires you to have a function
>> that can accept itself as an argument.  But what type will that
>> function have?  The type signature has to include itself in the type
>> signature, but there is no way that I know of to define a recursive
>> type.
>
> Sure you can:  You just box the function so that you don't need a
> recursive type declaration.  And forgive the shoe manufacturer pun:
>
> func rebox(r interface{}, n int) int {
>  if 0 == n {
>    return(1);
>  }
>  else {
>    reunbox := r.(func(r interface{}, n int) int);
>    return (n * reunbox(r, n-1));
>  }
>  return 1; /* Notreached */
> }
>
> func return_3(r interface{}, n int) int {
>  return 3;
> }
>
> func main() {
>  fmt.Printf("Reboxing: %d\n", rebox(rebox, 5));
>  fmt.Printf("Reboxing with return_3: %d\n", rebox(return_3, 5));
> }

Huh? That works. It lets you do an end run around the type system.
And clearly you can use that to do the Y-combinator. But what happens
if unboxing fails? Let's throw in:

fmt.Printf("Reboxing with int: %d\n", rebox(5, 5));

at the end of main() to get that. Then the result I get is:

ben-tillys-macbook-pro:go-euler btilly$ ./6.out
Reboxing: 120
Reboxing with return_3: 15
interface is int, not func(interface { }, int) (int)
throw: interface conversion

panic PC=0x2beee8
throw+0x3e /Users/btilly/go/src/pkg/runtime/runtime.c:74
throw(0x35767, 0x0)
runtime·ifaceE2T+0x56 /Users/btilly/go/src/pkg/runtime/iface.c:262
runtime·ifaceE2T(0x54a20, 0x0, 0x48e10, 0x0)
main·rebox+0x3f /Users/btilly/go-euler/anon_recurse.go:10
main·rebox(0x48e10, 0x0, 0x5, 0x0, 0x5, ...)
main·main+0x127 /Users/btilly/go-euler/anon_recurse.go:23
main·main()
mainstart+0xf /Users/btilly/go/src/pkg/runtime/amd64/asm.s:55
mainstart()
goexit /Users/btilly/go/src/pkg/runtime/proc.c:135
goexit()

Which tells me two things.

1. The type system can be subverted.

2. Even though it isn't user visible, there does seem to be an
exception system available somewhere internally.

Cheers,
Ben

[Russ Cox]

> 1. The type system can be subverted.

I don't know why you'd say that: you tried and
the program caught you and aborted.

> 2. Even though it isn't user visible, there does seem to be an
> exception system available somewhere internally.

Being able to print a stack trace is not the same thing
as having exceptions.

By the way, you can express the type of the Y combinator:

type F func(F) F

but it's not very useful in that form.

Russ

[dga]

On Nov 17, 1:33 am, Ben Tilly <bti...@gmail.com> wrote:

> On Mon, Nov 16, 2009 at 10:01 PM, dga <dave.ander...@gmail.com> wrote:
>
> > Sure you can:  You just box the function so that you don't need a
> > recursive type declaration.
>

> > func rebox(r interface{}, n int) int {

> > ...

> >    reunbox := r.(func(r interface{}, n int) int);
>

> Huh?  That works.  It lets you do an end run around the type system.
> And clearly you can use that to do the Y-combinator.  But what happens
> if unboxing fails?  Let's throw in:

Completely agreed. I was just showing a way to implement a Y-
combinator in Go, no more, no less. But not a type-safe y-
combinator. If you want to do that.... (which, I admit, I should have
done the first time!):

type reboxer func(r reboxer, n int) int;

func rebox(r reboxer, n int) int {

if 0 == n {
return(1);
}

return (n * r(r, n-1));
}

Your example then fails to compile with a pleasant error message:

play.go:40: cannot use 5 (type int) as type reboxer

Three cheers for recursive type definitions. :)

-Dave

[Ben Tilly]

On Mon, Nov 16, 2009 at 10:51 PM, Russ Cox <r...@golang.org> wrote:
>> 1. The type system can be subverted.
>
> I don't know why you'd say that: you tried and
> the program caught you and aborted.

I expected the type system to catch the mistake at compile time, not run time.

>> 2. Even though it isn't user visible, there does seem to be an
>> exception system available somewhere internally.
>
> Being able to print a stack trace is not the same thing
> as having exceptions.

Good point.

> By the way, you can express the type of the Y combinator:
>
>        type F func(F) F
>
> but it's not very useful in that form.

That makes sense.

Ben

[Ben Tilly]

With that I can demonstrate a full working example of the classic
Y-combinator in Go:

package main

import "fmt"

type recurseInt func (recurseInt) (func (int) int)

func main () {
fmt.Printf(
"Y-combinator 5! is %d\n",
func (builder recurseInt) (func (int) int) {
return func (n int) int {
return builder(builder)(n);
}
}(
func (recurse recurseInt) (func (int) int) {
return func (n int) int {
if 0 == n {
return 1;
}
return n * recurse(recurse)(n-1);
};
}
)(
5
)
);
}

Incidentally I miss the ability to end a function in an if/else with
all branches ending in returns. I naturally want to write:

if condition() {
return foo;
}
else {
return bar;
}

but that is a syntax error. Instead it should be

if condition() {
return foo;
}
return bar;

Cheers,
Ben

[Ian Lance Taylor]

Ben Tilly <bti...@gmail.com> writes:

> On Mon, Nov 16, 2009 at 10:51 PM, Russ Cox <r...@golang.org> wrote:
>>> 1. The type system can be subverted.
>>
>> I don't know why you'd say that: you tried and
>> the program caught you and aborted.
>
> I expected the type system to catch the mistake at compile time, not run time.

It would require a decent amount of analysis for the compiler to catch
this error at compile time, and a whole lot more analysis for the
compiler to catch it across a package boundary. And it would always
be possible to write a program which should fail but which the
compiler could not catch. So given the fast compilation goal, it
seems to make sense to only catch these errors at run time.

(A generics implementation would make it easier to express the
constraints which would let this general class of errors be caught at
compile time, though there would still be errors which were only
caught at runtime.)

Ian

[Ben Tilly]

On Tue, Nov 17, 2009 at 6:56 AM, Ian Lance Taylor <ia...@google.com> wrote:
> Ben Tilly <bti...@gmail.com> writes:
>
>> On Mon, Nov 16, 2009 at 10:51 PM, Russ Cox <r...@golang.org> wrote:
>>>> 1. The type system can be subverted.
>>>
>>> I don't know why you'd say that: you tried and
>>> the program caught you and aborted.
>>
>> I expected the type system to catch the mistake at compile time, not run time.
>
> It would require a decent amount of analysis for the compiler to catch
> this error at compile time, and a whole lot more analysis for the
> compiler to catch it across a package boundary.  And it would always
> be possible to write a program which should fail but which the
> compiler could not catch.  So given the fast compilation goal, it
> seems to make sense to only catch these errors at run time.

I don't understand. It seems to me that you can just disallow the
operation r.(func(r interface{}, n int) int) when r is not obviously
known to have a type that can be cast to func(r interface{}, n int)
int. So, for instance, you couldn't do that if r had type
interface{}, but could if it had type func(r int, n int).

This restriction would admittedly be a PITA upon occasion. But if
you're going to have a type system, why allow people to do end runs
around it?

> (A generics implementation would make it easier to express the
> constraints which would let this general class of errors be caught at
> compile time, though there would still be errors which were only
> caught at runtime.)

:-)

Cheers,
Ben

[Russ Cox]

> I don't understand.  It seems to me that you can just disallow the
> operation r.(func(r interface{}, n int) int) when r is not obviously
> known to have a type that can be cast to func(r interface{}, n int)
> int.  So, for instance, you couldn't do that if r had type
> interface{}, but could if it had type func(r int, n int).

func f(r int, n int) { }
var r interface {} = f
var x = r.(func(r int, n int))

is perfectly valid.

The only reason the .(T) syntax exists is to do a dynamic
check, one that the compiler cannot verify statically.
If r has type interface{}, it might have any dynamic type at all.

Russ

[Ian Lance Taylor]

Ben Tilly <bti...@gmail.com> writes:

> On Tue, Nov 17, 2009 at 6:56 AM, Ian Lance Taylor <ia...@google.com> wrote:
>> Ben Tilly <bti...@gmail.com> writes:
>>
>>> On Mon, Nov 16, 2009 at 10:51 PM, Russ Cox <r...@golang.org> wrote:
>>>>> 1. The type system can be subverted.
>>>>
>>>> I don't know why you'd say that: you tried and
>>>> the program caught you and aborted.
>>>
>>> I expected the type system to catch the mistake at compile time, not run time.
>>
>> It would require a decent amount of analysis for the compiler to catch
>> this error at compile time, and a whole lot more analysis for the
>> compiler to catch it across a package boundary.  And it would always
>> be possible to write a program which should fail but which the
>> compiler could not catch.  So given the fast compilation goal, it
>> seems to make sense to only catch these errors at run time.
>
> I don't understand. It seems to me that you can just disallow the
> operation r.(func(r interface{}, n int) int) when r is not obviously
> known to have a type that can be cast to func(r interface{}, n int)
> int. So, for instance, you couldn't do that if r had type
> interface{}, but could if it had type func(r int, n int).

We already do that check at compile time when possible based on the
static type. Didn't your test case use interface{}? The analysis I
was referring to was figuring out the dynamic type of an interface
type.

Ian

[anid...@gmail.com]

I have a similar solution for a simple Fibonacci generator:

func main() {

var fibonacci func(int) int

fibonacci = func (n int) int {

if n == 0 {

return 0

} else if n == 1 {

return 1

} else {

return fibonacci(n - 1) + fibonacci(n - 2)

}

}

fmt.Println("Fibonacci (30) =>", fibonacci(30))

} 

This seems to be the most simple way to do a anonymous recursive function in Go.

Regards,

Anindya Chatterjee

[Francesc Campoy Flores]

You could also pass the function to itself and define a recursive function type:

http://play.golang.org/p/bYn0yGE-sL

More for fun that for production though, this is not the most readable code ever.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--

Francesc Campoy

http://twitter.com/francesc

[Francesc Campoy Flores]

And just because you should always use early return:

http://play.golang.org/p/cbiM9icWr8

[Miguel Pignatelli]

Yes, but you should return the result ;-)

http://play.golang.org/p/h-VYDrY7Ov

M;

> <mailto:golang-nuts...@googlegroups.com>.

> For more options, visit https://groups.google.com/d/optout.
>
>
>
>
> --
> --
> Francesc Campoy

> http://twitter.com/francesc <http://twitter.com/francesc>
>
>
>
>
> --
> --
> Francesc Campoy
> http://twitter.com/francesc <http://twitter.com/francesc>

>
> --
> You received this message because you are subscribed to the Google
> Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to golang-nuts...@googlegroups.com

> <mailto:golang-nuts...@googlegroups.com>.

[Frank Solomon]

This approach makes "nested" recursion possible:

https://github.com/fbsolo/ProjectEuler/blob/master/main.go

- Frank

>         <mailto:golang-nuts+unsub...@googlegroups.com>.

>         For more options, visit https://groups.google.com/d/optout.
>
>
>
>
>     --
>     --
>     Francesc Campoy
>     http://twitter.com/francesc <http://twitter.com/francesc>
>
>
>
>
> --
> --
> Francesc Campoy
> http://twitter.com/francesc <http://twitter.com/francesc>
>
> --
> You received this message because you are subscribed to the Google
> Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to golang-nuts...@googlegroups.com

> <mailto:golang-nuts+unsub...@googlegroups.com>.