Loops and accumulated data

I’m still trying to wrap my head around Erlang and functional programming, and I am very much stuck with looping. I have some code in a CRC algorithm that I want to write in Erlang. The C code is as follows:

for(i=0; i<8; i++){
    if( x & 0x0001 == 0x0001)
        x = POLY ^ (x >> 1);
    else
        x = x >> 1;
}

if
   X band 16#0001 == 1 ->
         POLY bxor (X bsr 1);
   X band 16#0001 == 0 ->
         X bsr 1
end.

Loops have to be programmed using recursion – take this in small steps:

Suppose you have a function f(X) and you want to call it N times:

One iteration of this loop might be

loop(N, X) -> NextX = f(X), loop(N-1, NextX)

The loop index (N) counts down by one each time, so we have to stop the looping when N gets down to 0 – we
add a new line

loop(0, X) -> X;
loop(N, X) -> loop(N-1, f(X)).

(actually I made two changes here and eliminated the temporary variable NextX.

This calls a fixed function f(X) – so I might want to generalize this:

loop(0, X, _) -> X;
loop(N, X, F) -> loop(N-1, F(X), F).

so now loop(N, X, F) just computes F(F(F(F(X)))) (N times)

Now you put it all together

crc32(X) -> loop(8, X, fun(X) -> if X band 16#0001 == 1 -> ... end)

Look what happened to the for(i=0; i<8>
loop – all this is is an idiom saying “loop 8 times”

I can make something that loops 8 times like this:

loop(0) -> true;
loop(N) -> <<something>> , loop(N-1)

then calling loop(8) with evaluate <<something>> 8 times

the rest of the loop (see earlier) is just concerned with getting the correct variables
in and out of the loop.

/Joe

Thank you very much for walking me through the thought process and explaining the mechanics in such detail. It is all much clearer now, thank you!

I’m very much embarrassed to say this, but I have a syntax problem and I cannot figure out where it is. The code is as follows:

-module(crc16).
-export([calculate/1]).
-export([inner_loop/3]).

%%% CRC16 CCITT Normalized Polynomial
-define(POLYNOMIAL, 16#1021).

inner_loop(0, X, _) -> X;    
inner_loop(N, X, F) -> inner_loop(N-1, F(X), F).

calculate(X) ->
    inner_loop(8, X, fun(X) ->
        if X band 16#0001 == 1 -> ?POLYNOMIAL bxor (X bsr 1);
           X band 16#0001 == 0 -> X bsr 1
        end
        ).

%%% outer_loop() ->
%%% for(i=0; i<256; i++) { 
%%%    // call inner_loop to calculate value
%%%    // add calculated value to crc lookup table at index i
%%% }

The output of the Erlang interpreter is as follows:

38> c(crc16).
./crc16.erl:16: syntax error before: ')'
./crc16.erl:2: function calculate/1 undefined
error

I would greatly appreciate any hints. I’m sure I’ve made a very elementary mistake but I just can’t seem to find it.

Thank you for your time and help!

The error message is very precise it has found an error before ‘)’ – something is missing -
the error is encountered when the parser hits the ‘)’ (thus the diagnostic)

Both fun and if require an end statement. The syntax is

fun(...) ->
   ...
end

if
   ...
end

If you line them up it is clearer

so it should be

loop(8, X, fun(Y) ->
               if
                   ...
               end
           end).

inside the fun I've changed the free variable to Y (otherwise the value of X is
ambiguous - do you mean the X in the fun(X) or the X in calculate(X)?

finally

calculate(X) -> inner_loop(8, X, fun(Y) -> if Y band 16#0001 1 -> ?POLYNOMIAL bxor (Y bsr 1); Y band 16#0001 0 -> Y bsr 1 end end).

This should do the trick

/Joe

Thank you very much for your help. It sure was the “end” for the fun that I missed.

A functionally equivalent module using module-level functions and guards:

-module(crc16).
-export([calculate/1]).

%%% CRC16 CCITT Normalized Polynomial
-define(POLYNOMIAL, 16#1021).

calculate(X) -> calculate(8, X).

calculate(0, X) -> X;
calculate(N, X) when X band 16#0001 == 1 ->
    calculate(N-1, ?POLYNOMIAL bxor (X bsr 1));
calculate(N, X) ->
    calculate(N-1, X bsr 1).

I find that using module-level functions and guards is often more readable than using if statements and anonymous functions. It avoids a lot of syntactical weirdness as well.

Alain,

Thanks for sharing your solution, it is very elegant. I hope eventually I’ll be able to adjust my “gears” to functional thinking.