Fragile Recursion?

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Fragile Recursion?

Tim Hill
I'm sure this has been discussed before, but I would be interested in others thoughts and/or comments. Since in Lua all functions are really anonymous, recursion seems to be fragile. Consider this code:

function fact(n)
        if n == 0 then return 1 end
        return n * fact(n-1)
end

fact1 = fact; fact = nil
fact1(10)

This breaks (of course), since the function tries to call fact() instead of fact1() when it recurses. Of course the obvious answer is "well dont do that!" but if i'm creating library routines for use by others I don't like having to publish lots of "do and dont" caveats; it's too fragile.

I can only think of two solutions, and I don't really like either:
1. Extend the language with some kind of magic "self" name so that the function can reference itself regardless of where it is stored (a kind of function-level "this" pointer I guess). I can almost SEE Roberto getting mad at such an idea (I know I would), and besides it doesnt help with mutually-recursive functions.

2. Wrap the function in a closure that contains a reference to itself and recurse using the closure. Something like this:

do
        local function f1(n)
                if n == 0 then return 1 end
                return n * f1(n-1)
        end
        fact = f1
end

This works but it takes the performance hit of the closure just to get the recursion.

Comments anyone? Am I missing something obvious here?

--Tim


Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Miles Bader-2
Tim Hill <[hidden email]> writes:

> 2. Wrap the function in a closure that contains a reference to
> itself and recurse using the closure. Something like this:
>
> local function f1(n)
> if n == 0 then return 1 end
> return n * f1(n-1)
> end
> fact = f1
>
> This works but it takes the performance hit of the closure just to
> get the recursion.

It doesn't seem like much of a "performance hit", as a closure is only
created once, when the function is defined.

I certainly wouldn't worry about it...

-miles

--
"Suppose we've chosen the wrong god. Every time we go to church we're
just making him madder and madder." -- Homer Simpson

Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Alex Queiroz
In reply to this post by Tim Hill
Hallo,

On Tue, Apr 10, 2012 at 9:22 AM, Tim Hill <[hidden email]> wrote:

>
> 2. Wrap the function in a closure that contains a reference to itself and recurse using the closure. Something like this:
>
> do
>        local function f1(n)
>                if n == 0 then return 1 end
>                return n * f1(n-1)
>        end
>        fact = f1
> end
>

The closure itself has its scope, so I'd do like this:

function f1(n)
   local function real_f1(y)
      if y == 0 then return 1 end
      return y * real_f1(y - 1)
   end
   return real_f1(n)
end

Cheers,
--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Luiz Henrique de Figueiredo
In reply to this post by Tim Hill
> Since in Lua all functions are really anonymous, recursion seems to be fragile.

This has nothing to do with recursion. It's a consequence of dynamic binding.
Consider this:

        function hello()
                print"Hello world"
        end

        print=nil
        hello() -- error!

Is there anything to be fixed in this code??

If you want to force static binding, you can do it with

        do
                local print=print
                function hello()
                        print"Hello world"
                end
        end

Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

martinwguy
In reply to this post by Miles Bader-2
On 10 April 2012 09:29, Miles Bader <[hidden email]> wrote:

> Tim Hill <[hidden email]> writes:
>> 2. Wrap the function in a closure that contains a reference to
>> itself and recurse using the closure. Something like this:
>>
>>       local function f1(n)
>>               if n == 0 then return 1 end
>>               return n * f1(n-1)
>>       end
>>       fact = f1
>>
>> This works but it takes the performance hit of the closure just to
>> get the recursion.
>
> It doesn't seem like much of a "performance hit", as a closure is only
> created once, when the function is defined.

...and you save the global table lookup of "fact" in the recursion,
which turns out to be faster.

    M

Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

GrayFace
In reply to this post by Tim Hill
do...end has nothing to do with a closure. A closure is an 'instance' of function, thus it's created once in any of your examples. In the first case it doesn't contain any upvalues in Lua 5.1, while it does in 5.2. In short, the 2) is faster.

I'd do it this way:

local function fact(n)
        if n == 0 then return 1 end
        return n * fact(n-1)
end
_G.fact = fact


--
Best regards,
Sergey Rozhenko                 mailto:[hidden email]


Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Miles Bader-2
GrayFace <[hidden email]> writes:
> do...end has nothing to do with a closure. A closure is an 'instance'
> of function, thus it's created once in any of your examples. In the
> first case it doesn't contain any upvalues in Lua 5.1, while it does
> in 5.2.

It contains an upvalue in both 5.1 and 5.2:  the recursive reference
to the local (in the file) definition of "fact".

-mjiles

--
Genealogy, n. An account of one's descent from an ancestor who did not
particularly care to trace his own.

Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Wim Couwenberg
In reply to this post by GrayFace
> _G.fact = fact

In Lua 5.2 make that _ENV.fact = fact.  It avoids the silly _G
convention *and* saves yet another table lookup.  :-)

Bye,
Wim

Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Tim Hill

Thanks for the replies everyone. Yes, aware that "do .. end" isnt directly related to closures, it was of course designed to make the local variable private to the closure so that the recursion was no longer fragile.

I still think there might be some value in a distinguished variable that held the "current" function so that at least directly recursive functions could be written in a more robust manner.

--Tim


On Apr 10, 2012, at 1:47 PM, Wim Couwenberg wrote:

>> _G.fact = fact
>
> In Lua 5.2 make that _ENV.fact = fact.  It avoids the silly _G
> convention *and* saves yet another table lookup.  :-)
>
> Bye,
> Wim
>


Reply | Threaded
Open this post in threaded view
|

Re: Fragile Recursion?

Miles Bader-2
Tim Hill <[hidden email]> writes:
> Thanks for the replies everyone. Yes, aware that "do .. end" isnt
> directly related to closures, it was of course designed to make the
> local variable private to the closure so that the recursion was no
> longer fragile.
>
> I still think there might be some value in a distinguished variable
> that held the "current" function so that at least directly recursive
> functions could be written in a more robust manner.

I'm not sure how that's really going to make things "more robust" --
there's nothing particularly "fragile" about the current system...

-miles

--
Cat, n. A soft, indestructible automaton provided by nature to be kicked when
things go wrong in the domestic circle.

Reply | Threaded
Open this post in threaded view
|

json4lua problem, anyone can help me? thanks.

hei.minglei
In reply to this post by Tim Hill

I port json4lua to vxworks, sometimes it raise exception( the probability is about 1/200).

But the point is the excepion seems strange, according to its literal meaning, the exception is impossible.

-----------------
[string "lua/json.lua"]:375: Unexpected character at Line 1 character 61: , (44)
 when reading object (' or " or } or , expected)
Context:
["hi", "b"]], "method": "echo", "id": "d7c2e97e150660aba61def
                              ^
stack traceback:
        [C]: in function 'error'
        [string "lua/json.lua"]:375: in function 'next_token'
        [string "lua/json.lua"]:513: in function <[string "lua/json.lua"]:511>
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        [string "lua/json.lua"]:531: in function 'decode'
        [string "lua/json/rpcserver.lua"]:71: in function 'serve'
        jsonrpc.lua:46: in main chunk


---------------

When I use the same test code in windows, it never happen. Is this problem caused by OS porting or any other?

thanks.
--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail is solely property of the sender's organization. This mail communication is confidential. Recipients named above are obligated to maintain secrecy and are not permitted to disclose the contents of this communication to others.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the originator of the message. Any views expressed in this message are those of the individual sender.
This message has been scanned for viruses and Spam by ZTE Anti-Spam system.
Reply | Threaded
Open this post in threaded view
|

Re: json4lua problem, anyone can help me? thanks.

Ignacio Burgueño
Can you post the json that fails to decode?


Reply | Threaded
Open this post in threaded view
|

答复: Re: json4lua problem, anyone can help me? thanks.

hei.minglei


[hidden email] wrote on 2012-04-13 00:48:51:

> Can you post the json that fails to decode?


It seems that character 'c' is valid, so the exception has confilcting information.
ps. This exception never happend in windows version.

----------another except----------------
[string "lua/json.lua"]:375: Unexpected character at Line 1 character 78: c (
99) when reading double quoted string
Context:
thod": "echo", "id": "9c956962c52ea9fc94e6e63f33eaef910ebea53
                              ^
stack traceback:
        [C]: in function 'error'
        [string "lua/json.lua"]:375: in function 'next_token'
        [string "lua/json.lua"]:390: in function <[string "lua/json.lua"]:386>
        (tail call): ?
        (tail call): ?
        [string "lua/json.lua"]:525: in function <[string "lua/json.lua"]:511>
        (tail call): ?
--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail is solely property of the sender's organization. This mail communication is confidential. Recipients named above are obligated to maintain secrecy and are not permitted to disclose the contents of this communication to others.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the originator of the message. Any views expressed in this message are those of the individual sender.
This message has been scanned for viruses and Spam by ZTE Anti-Spam system.
Reply | Threaded
Open this post in threaded view
|

Re: 答复: Re: json4lua problem, anyone can help me? thanks.

Ignacio Burgueño

On Thu, Apr 12, 2012 at 10:06 PM, <[hidden email]> wrote:


[hidden email] wrote on 2012-04-13 00:48:51:


> Can you post the json that fails to decode?


It seems that character 'c' is valid, so the exception has confilcting information.
ps. This exception never happend in windows version.


It seems that bug is related to the vxworks port. You can try to run the test suite for Lua 5.1 to see if your build of Lua is behaving properly. 
The tests are here: 


Regards,
Ignacio
Reply | Threaded
Open this post in threaded view
|

答复: Re: json4lua problem, anyone can help me? thanks.

hei.minglei
In reply to this post by Ignacio Burgueño

I have solve this problem, it has nothing to do with json4lua lib.
Actually, it is a lua porting problem in VxWorks. Vxworks task does not deal with floating point correctly unless it was created by taskSpawn with flag VX_FP_TASK.

Hope this help.

[hidden email] wrote on 2012-04-13 00:48:51:

> Can you post the json that fails to decode?

--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail is solely property of the sender's organization. This mail communication is confidential. Recipients named above are obligated to maintain secrecy and are not permitted to disclose the contents of this communication to others.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the originator of the message. Any views expressed in this message are those of the individual sender.
This message has been scanned for viruses and Spam by ZTE Anti-Spam system.