# Fragile Recursion?

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

## Fragile Recursion?

 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?

 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?

 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?

 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?

 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?

 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?

 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?

 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?

 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?

 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.

 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.

 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.

 [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.

 On Thu, Apr 12, 2012 at 10:06 PM, 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:  http://www.inf.puc-rio.br/~roberto/lua/lua5.1-tests.tar.gzRegards,Ignacio
Reply | Threaded
Open this post in threaded view
|

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

 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. ```