[erlang-questions] General advice on FP (& Erlang)

Håkan Stenholm <>
Sat Aug 11 23:43:51 CEST 2007


Milen Georgiev Dzhumerov wrote:
> Hi all,
>
> I've got a couple of questions. I'm probably not the first person who 
> is struggling to switch to a functional mindset. So, hopefully, any 
> replies to my questions will help other people too!
>
> The way I got started is by reading the "Programming Erlang" book by 
> Joe (great book btw). As I was reading the book, everything seemed so 
> obvious and easy but when I'm trying to do something myself - I just 
> can't. I always go back to my "shared state" mind and don't seem to be 
> able come up with a design and a plan on how to implement it.
>
> So, what are you guys (who get FP) suggesting I do? I think the 
> problem comes from having C hardwired into my brain and I can't get it 
> out.
>
> And I definitely have got to ask this - how are we supposed to mutate 
> state? Using processes? Function calls? I just can't wrap my head 
> around how some C code is going to be translated.
C style loops (for/while) are replaced by recursive functions (, lists:map/foldl/foreach calls 
or list comprehensions which hide most of the recursive boilerplate code) e.g.:

list_sum(L) ->
     list_sum(L, 0). % set intial value of sum accumulator

% base case of recursion ("loop condition = false"), nothing more to do, return the accumulator value
% Note: it is possible to have more than one base case, this may occur if more than one list
%       is processed at the same time, if some MaxNumberOfListElementsToProcess is supplied ... etc
list_sum([], Sum) ->   
    Sum;
% process a single list element in each recursive call (invocation of list_sum/2)
% "action of loop when loop condition = true"
list_sum([V|R], Sum) -> 
    NewSum = Sum + V,
    list_sum(R, NewSum). % process the rest

There are several important properties here:
* Variabels are constant inside the scoop of the function clause that they 
  are defined in, they are basically local names for elements on the stack
* Each function invocation creates a new set of variables on the stack - or in 
  other words each call gets a new copy of the values passed to it (remember that 
  erlang acts as call by value).

example:                                               

list_sum([1,2])		calls     list_sum([1,2], 0)	stack = [1,2]
list_sum([1,2], 0)	calls     list_sum([2], 1)	stack = [1,2] 0     [1,2]
list_sum([2], 1)	calls     list_sum([], 3)	stack = [2] 1        [1,2] 0     [1,2]
list_sum([], 3)         returns 3     unwind the stack and return 3 from list_sum/1

Note: the code above is actually tail recursive - nothing needs to be calculated after 
      a recursive call has been done in any of the clauses in lists_sum/2, which means 
      that the stack will not be used, the internal beam code will work like a 
      regular C loop. Compare this to the code below which doesn't use a accumulator, 
      which must use the stack to keep track of all the invocations of list_sum/2 to be
      able to do the + operation when the base case is reached.

list_sum([]) ->
  0;
list_sum([V|R], Sum) -> 
  V + list_sum(R).


Using lists:foldl/3, which hides most of the recursive stuff:

list_sum(L) ->
  F = fun(V, Sum) -> % a fun that is essentially the same thing as a C loop body
        V + Sum
      end,
  lists:foldl(F, 0, L).

========================

So mutable state is achieved by passing new values to the next function call, this could
in some cases even be a series of mutually recursive functions like:

foo1(...) ->
  case ... of
    ... -> foo2(...);
    ... -> foo3(...)
  end.


foo2(...) ->
  ...
  foo1(...).


foo3(...) ->
  ...
  foo1(...).

This is useful for things like processing parse trees or implementing state machines 
where each state matches a function.

Also note that code like foo([E|R], ...) -> ... [f(E) | foo(R, ...)] often avoids the need
to explicitly keep track of state, as the new state (the new list) is created when each call to
foo(...) returns and assembles a updated list, in each stack unwind step.


>
> Let's take a simple example. I'm writing a network app in Erlang which 
> accepts "messages" on a socket, where a "message" is defined as 
> length:content. If I was to do this in C, I would have a function 
> which gets called every time bytes arrive on the socket and then 
> depending on which state I'm in, I'm either going to append the bytes 
> to a length buffer and when I reach the ":" character, I'll change the 
> state and start appending to the content buffer (while decrementing 
> the number of bytes still left to be read).
> Now all of this depends on having access to mutable buffers (& a 
> counter) outside the scope of the functions - at this point I'm lost 
> on how to do it in Erlang. How would guys start solving this problem? 
> Obviously, the more experience you have, the less thinking you're 
> going to put into this and the solution is going to come up naturally, 
> but what about people who haven't had any real world experience with FP?
>
> Thanks,
> Milen
> ------------------------------------------------------------------------
>
> _______________________________________________
> erlang-questions mailing list
> 
> http://www.erlang.org/mailman/listinfo/erlang-questions




More information about the erlang-questions mailing list