7 Jun
2013
7 Jun
'13
10:52 p.m.
It was thus said that the Great ben once stated:
On 6/7/2013 9:20 PM, Dave McGuire wrote:
I have a friend that *hates* recursion, and if he had his way, would fire
any programmer that used it [1][2]. And yes, excessive stack usage is a
problem.
But it really depends upon the langauge. For instance, in Lua [3], state
machines are really easy to write with mutual recursion:
function read(info)
-- read data
if error then
return nak(info)
end
if done then
return true -- done with protocol
end
return ack(info)
end
function nak(info)
-- send nack
if naks > 15 then
return false -- abort protocol
end
return read(info)
end
function ack(info)
-- send ack
return read(info)
end
(I have a TFTP server written in this style). It's easy to see the flow,
but yes, it looks like this would blow out the stack big time. But because
Lua has "tail call optimizations", the underlying code is more like:
function read(info)
-- read data
if error then
goto nak(info)
end
if done then
return true
end
goto ack(info)
end
So the only stack that's consumed is the initial call into the state
machine. Here's another example of recusion:
function echo(socket)
local clientaddr,data = socket:receive()
socket:sendto(clientaddr,data)
return echo(socket)
end
A simple echo client, and again, because Lua supports tail call
optimization, this is the same as:
function echo(socket)
while true do
local clientaddr,data = socket:receive()
socket:sendto(clientaddr,data)
end
end
A trivial example, but it's how a lot of functional langauges implement
loops. Whether I use loops or recursive loops in Lua depends on if I need
the equivilent if "continue" in the loop or not (Lua does not have a
"continue" statement).
-spc
[1] I'd call him a greybeard, but a) he's younger than I am, and b) I'm
not *that* old myself.
[2] Also, to him, the use of git is a fireable offense. But then again,
he told me point blank he's a micromanaging asshole, and git doesn't
allow him enough control over the development process.
[3] Lua was first release in 1993, so it's probably on topic.
What do you see as the biggest obstacles for
adopting the FP
abstractions in "everyday programming thought"? I assume unlearning
previously-learned ways of approaching problems? (iterators vs.
recursion, etc)?
I have no problems with iteration or subroutines, so why do we need
recursion? That is not to say for a quick and dirty program I'll use it if
need be, but the problem with general recursion is stack overflow and how
do you handle that? And do say get more memory, then you get fix the
firmware for the latest hardware* - http://pdp2011.sytse.net/wordpress/ -
as this is a problem in defining a problem that needs to be addressed in
computer science - program limits,not newer or bigger is better.