Erlang article #1 on programming.reddit.com

Joe Armstrong (TN/EAB) joe.armstrong@REDACTED
Mon Aug 21 11:05:23 CEST 2006


No really :-) - loops are implemented by applying the good old "last
call optimisation"

This is as old as the hills - in compiling a function based language you
compile a
function call as follows:

	1) push the address of the next instruction to be executed after
the
	   function call onto the stack.
	2) transfer control to the start of the new function

When a function returns it executes a RET instruction, this expects a
return address
on the top of the stack. It pops the stack and jumps to this address.

Now suppose the next instruction to be executed is a RET instruction
all this does is pop the return address stack and jump to the popped
address.

In this case we can omit the code that pushes a return address and jumps
into the code
and replace it with a simple jump into the code since the function
itself will return
to the correct place when it executes a RET instruction.  

Now I don't know exactly who pointed this out, I might have been Knuth
but I am unsure
five minutes Googling did not turn up the answer.

<< anybody know this ???? - a change to show your erudition, or Googling
skills 
   [[ apparently Google is writing nasty letters to dictionaries who use
the
      word Googling as a verb - so go on
	{{ meta - disclaimer, not my Employers point of view (had the
say that)
	  "sue me" }} ]] >>
:-> >>

This was certainly well-know (or at least I knew it :-) way before the
term
tail-recursion was mentioned.

As regards loops in FPL - only the very pure disallow loops in their
languages. There is a language based on category theory
(I forget the name, << another chance to show your erudition >>)
which allowed loops but only if it could be proven at compile time that 
the loops terminate.

So loops indexed by a integer that was decremented by one at each step
and
terminated at zero, and which were started off at a large positive
integer
were possibly ok - otherwise you're in trouble. Amazingly it was said to
be
possible to write non-trivial programs in this language, but nobody said
it was easy,
just possible.

/Joe
      	
	
> -----Original Message-----
> From: owner-erlang-questions@REDACTED 
> [mailto:owner-erlang-questions@REDACTED] On Behalf Of Rick Pettit
> Sent: den 17 augusti 2006 22:06
> To: Logan, Martin
> Cc: Ryan Rawson; Joel Reymont; Yariv Sadan; erlangquestions
> Subject: Re: Erlang article #1 on programming.reddit.com
> 
> On Thu, Aug 17, 2006 at 02:43:34PM -0500, Logan, Martin wrote:
> > Rick, you are correct but technically the process loops in 
> Erlang are 
> > implemented via tail recursion.
> 
> Then I am technically correct as well (I mentioned 
> tail-recursion below, though it should come as no surprise 
> what happens if you "loop forever" using non-tail recursive calls :-)
> 
> > I think this is where the misunderstanding came about.  Procedural 
> > looping structures such as "for", "while", "do while", and 
> "foreach" 
> > are the sorts of looping constructs that would severely 
> damage Erlang as a language, IMHO.
> 
> Procedural looping constructs in a non-procedural language 
> doesn't make much sense, which is why I'm not worried about 
> someone trying to add them.
> 
> -Rick
> 
> > Cheers,
> > Martin
> > 
> > -----Original Message-----
> > From: owner-erlang-questions@REDACTED 
> > [mailto:owner-erlang-questions@REDACTED] On Behalf Of Rick Pettit
> > Sent: Thursday, August 17, 2006 1:50 PM
> > To: Ryan Rawson
> > Cc: Joel Reymont; Yariv Sadan; erlangquestions
> > Subject: Re: Erlang article #1 on programming.reddit.com
> > 
> > On Thu, Aug 17, 2006 at 11:30:19AM -0700, Ryan Rawson wrote:
> > > Surely you jest?
> > > 
> > > You'd have to break Erlang to insert loops.  First off you'd have 
> > > variables that need to be changed.  That substantiably 
> breaks Erlang 
> > > imho.
> > 
> > Not sure I understand you here. I have recently been using Joe 
> > Armstrong's robust TCP server, for example, and in that 
> there is the 
> > notion of a "controller" loop for synchronizing operations among 
> > multiple socket handlers.
> > 
> > For "simple servers" (i.e. those not requiring a behaviour like
> > gen_server)
> > I see tail-recursive server loop constructs all the time.
> > 
> > Single assignment isn't a problem considering each new iteration 
> > through the loop allows for new local variable bindings, etc.
> > 
> > > If you want to loop, you probably want to map or fold.  
> If you need 
> > > to loop you might want to use gen_server instead, or at the last 
> > > resort use a tail recursive call.
> > 
> > What do you think goes on behind the scenes in a map, fold, or even 
> > gen_server?
> > 
> > You might be surprised to find that there is a server loop in a 
> > gen_server (it is what passes the state to gen_server 
> callbacks, and 
> > it is what the gen_server callbacks return the state to).
> > 
> > Perhaps I misunderstand you.
> > 
> > -Rick
> > 
> > > On 8/17/06, Joel Reymont <joelr1@REDACTED> wrote:
> > > >
> > > >On Aug 17, 2006, at 5:53 PM, Ryan Rawson wrote:
> > > >
> > > >> I beg of all of you - no for loops.  No looping of any kind!
> > > >
> > > >What's wrong with looping?
> > > >
> > > >--
> > > >http://wagerlabs.com/
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> 



More information about the erlang-questions mailing list