Friday, July 18, 2008

No state updating: functional language

The programming model of command language is state machine. Such as in C, every variable is a state, one of the most common statements are assigning new value to a variable, that is, state updating. But in functional programming language, there is no state updating, how to program without state updating? Let's begin with a simple example of bank account management system.


struct account
{
char *name;
int remain;
struct account *next;
};

#define OP_NOP 0
#define OP_WITHDRAW 1
#define OP_DEPOSIT 2
#define OP_PRINT 3
#define OP_EXIT 4

void deposit(struct account *account, int val)
{
account->remain += val;
}

void withdraw(struct account *account, int val)
{
account->remain -= val;
}

int main(int argc, char *argv[])
{
struct account *accounts = NULL;
char *name;
int op = OP_NOP, val;

while (op != OP_EXIT) {
op = read_operation();
case OP_WITHDRAW:
case OP_DEPOSIT:
name = read_name();
account = list_find(accounts, name);
val = read_val();
if (op == OP_WITHDRAW)
withdraw(account, val);
else
deposit(account, val);
break;
case OP_NEW:
name = read_name();
account = malloc(sizeof(struct account));
account->name = name;
account->remain = 0;
list_add(&accounts, account);
break;
case OP_PRINT:
/* a macro to iterate every element of list */
list_for_each(accounts, account) {
printf("Name: %s\tRemain: %d\n", account->name, account->remain);
}
break;
case OP_EXIT:
break;
}
}
return 0;
}


In erlang, a functional programming language:


-module(bank).
-export([service/1]).

deposit(Account, Val) ->
{Name, Remain} = Account,
{Name, Remain + Val}.

withdraw(Account, Val) ->
{Name, Remain} = Account,
{Name, Remain - Val}.

print_account({Name, Remain}) ->
io:format("Name: ~s Remain: ~B~n", [Name, Remain]).

service(Accounts) ->
{ok, [Operation|_]} = io:fread("Operation: ", "~a"),
if
Operation == deposit; Operation == withdraw ->
{ok, [Name|_]} = io:fread("Name: ", "~s"),
{ok, [Val|_]} = io:fread("Val: ", "~d"),
case lists:keysearch(Name, 1, Accounts) of
false ->
io:format("Error: no such account.~n"),
NewAccounts = Accounts;
{value, Account} ->
case Operation of
deposit ->
NewAccount = deposit(Account, Val);
withdraw ->
NewAccount = withdraw(Account, Val)
end,
NewAccounts = lists:keyreplace(Name, 1, Accounts,
NewAccount)
end,
service(NewAccounts);
Operation == new ->
{ok, [Name|_]} = io:fread("Name: ", "~s"),
case lists:keymember(Name, 1, Accounts) of
true ->
NewAccounts = Accounts,
io:format("Error: account already exist.~n");
false ->
NewAccounts = [{Name, 0} | Accounts]
end,
service(NewAccounts);
Operation == print ->
lists:foreach(fun print_account/1, Accounts),
service(Accounts);
Operation == exit ->
ok;
true ->
io:format("Error: unknown operation~n"),
service(Accounts)
end.


Notes:
  • In functional programming language, instead of updating object (value) in-place, every time a new object (value) is constructed. In example above, in C, deposit() change account->remain directly, while in erlang, a new account is constructed and returned.
  • If data of program is organized in a hierarchical way, to change the data in leaf, in command language, only the leaf is changed in place; in functional language, all data structure from that leaf to root will be reconstructed. In example above, in C, during deposit operation, only the corresponding account object is changed in-place, while in erlang, both corresponding account object and the whole account list will be re-constructed. With the help of carefully designed implementation, althought the performance of that in functional language is wrose, it is not so bad as it appears.
  • In functional programming language, instead of updating the binding of variable name to new value directly, a new scope is constructed and in the new scope, same variable name is binded to a new value. In example above, during "new" operation, accounts may be bind to a new value, in erlang, a new scope is constructed by "recursing", that is, the new constructed account list is bind to Accounts in a new scope. Thanks to the "tail recursing" optimization, the performance is not so bad.
Questions:
  • How to shared objects in functional programming language? Such as in a database system, the cached database table should be shared between service threads.

1 comment:

Aya said...

You write very well.