2
\$\begingroup\$

I'm trying to learn Functional Programming and I picked Erlang because I will have to use it eventually. In the meantime, I'm trying to build a simple lexer to stumble upon problems and solve them along the way.

I'm aware that Erlang has leex and yeec but this code is just for illustration purposes and teach me the "FP way".

So I would appreciate if someone would give a cursory glance at my initial attempt and tell me their suggestions.

The code below is a simple tokenizer that splits expressions in the form "<number> + <number>" into a list of tokens. The general direction I took to solve this problem is as follows:

The tokenize/2 funtion is called recursively on a successively shrinking portion of text. When the text is empty, it returns the lexed tokens.

The tokenize/2 function first builds a list of functions, each of which, when applied to a portion of text, returns an {ok, {Type, Token}, Text} tuple representing the outcome of the match, the token and the remaining, non matched, portion of the input string.

The tokenize/2 function then maps the list of functions, with the expectations that, at each stage, only one match will occur. A HasMatched predicate is built to extract the single match from the list, if any. If a match has indeed been found, the recursive call is made to the function, with arguments being the remaining potion of the text and the new token appended to the list of resulting tokens.

-module(tokenizer).
-export([tokenize/1]).

-include_lib("eunit/include/eunit.hrl").

% tokenize an input string
tokenize(String) -> tokenize_ignore_ws(String).

tokenize_ignore_ws(String) ->
    {R, Tokens} = tokenize(String, []),
    {R, lists:filter(
        fun
            ({ws, _}) -> false
            ; (_) -> true
        end
        , Tokens
    )}
.

tokenize([], Tokens) -> {ok, Tokens};
tokenize(String, Tokens) ->
    Patterns = [
        fun(S) -> match(number, "[0-9]+", S) end,
        fun(S) -> match(op, "\\+", S) end,
        fun(S) -> match(ws, "\\s+", S) end
    ],
    Matches = lists:map(fun(P) -> P(String) end, Patterns),
    HasMatched = fun({error, _, _}) -> false; (_) -> true end,
    Match = lists_single_or_default(HasMatched, Matches),
    case Match of
        {ok, Token, Text} ->
            tokenize(Text, Tokens ++ [Token]);
        null ->
            {error, Tokens}
    end
.

% The match/3 function applies the specified Regex to the input String.
% If the match is successful, the function returns the tuple: 
% {ok, {Type, Token}, Text} where
% - Token is the matched portion of the input String and
% - Text is the remaining portion of the input String.
%
% If the match fails, the function returns the tuple:
% {error, null, String}
%
match(Type, Regex, String) ->
    case re:run(String, Regex, [anchored]) of
        {match, Captures} ->
            {0, Length } = lists:last(Captures),
            Token = string:left(String, Length),
            Text = string:substr(String, Length + 1),
            {ok, {Type, Token}, Text}
        ; nomatch -> {error, null, String}
    end
.

%% Lists Helper Functions
lists_single(Pred, L) ->
    case lists_single_or_default(Pred, L) of
        null -> error;
        X -> X
    end
.
lists_single_or_default(Pred, L) ->
    R = lists:filter(Pred, L),
    case length(R) of
        0 -> null;
        1 -> lists:nth(1, R);
        _ -> error
    end
.

% EUnit

tokenize_number_test() ->
    {ok, [{Type, Token}]} = tokenize("123"),
    ?assert(Type =:= number),
    ?assert(Token =:= "123")
.
tokenize_op_plus_test() ->
    {ok, [{Type, Token}]} = tokenize("+"),
    ?assert(Type =:= op),
    ?assert(Token =:= "+")
.
tokenize_empty_expression_test() ->
    {ok, []} = tokenize("")
.
tokenize_expression_test() ->
    {ok, Tokens} = tokenize("123+456"),
    [
        {number, "123"},
        {op, "+"},
        {number, "456"}
    ] = Tokens

For instance, in the code above, I felt the need to declare a lists_single_or_default/2 function. That's because I'm coming from a C# background. Is there some proper FP way to make the calling code more maintainable/readable with an alternative way?

Another thing I'm interested about is to add {Row, Column} information to each token so as to give more meaningful error messages while tokenizing and, eventually, while parsing later on. For this, I think I will need to carry this information in the {Type, Token, {Row, Column}} tuple that represents a token. But I feel that adding more and more state to the Token will make the code more and more difficult to read and maintain.

I'm aware that FP makes extensive use of recursion. For instance, the canonical way to implement the Fibbonacci suite is as follows:

fac(0) -> 1;
fac(1) -> 1;
fac(N) -> N * fac(N - 1).

However, I have searched about potential for stack overflows while running recursive functions and I found that most functional programming languages make use of Tail Call Optimization in order to reuse the last stack frame while possible.

It seems, unfortunately, that the canonical implementation of the Fibonaci suite shown above does not lend itself to being optimized that way. Is there a way to inspect the stack in Erlang and, in the context of my tokenize/2 method, is is possible to use another algorithm that does not involve recursion ? Is there a way to adapt my algorithm so that is lends itself to being optimized ?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.