Введение в Erlang

Ранее на блоге я публиковал две заметки по языку Erlang — «Обработка списков на Erlang» и «Unit тестирование в Erlang на примере«. Я полагал, что это будет интересно тем, кто интересуется Erlang-ом (обычно им интересуются как языком параллельного и распределенного программирования и я рекомендую посмотреть на этот язык своим студентам на соответствующем курсе). Однако, я не учел, что интересующиеся купят нормальную книгу или, по крайней мере, найдут полноценную серию уроков (от и до), а не будут собирать информацию с разных источников. Поэтому я решил добавить введение в Erlang.

1 Erlang. Операторы. Atoms, Integers, Booleans.

Математические операторы

ТипОписаниеТип данных
+Сложение (addition)Integer | Float
Вычитание (substraction)Integer | Float
*Умножение (multiplication)Integer | Float
/Деление с плавающей запятой (floating point division)Integer | Float
divДеление нацело (integer division)Integer
remОстаток от деления (integer remainder)Integer

Примеры использования математических операторов в консоли erlang:

1> 1 + -1.
0
2> 2/3.
0.6666666666666666
3> 3 div 2.
1
4> 3 rem 2.
1

Атомы (константы)

Атомы это строковые константы типа: red, green, blue или enabled, disabled. Всегда должны начинатся с нижнего регистра (маленькой буквы) и могут включать в себя буквы, цифры, символы «@», «_», «.». Например: testUser, test_user, test.user. В принципе для атомов можно использоват любые символы, если заключать их в одинарные кавычки: ‘Monday’, ‘not ready’, ‘node#1\nnode#2’
Integers (целые)

Определение целых работа с ними классическая:

1> 1.
1
2> 2+3.
5
3> 4-7.
-3

Booleans

Здесь тоже все более-менее привычно за исключением того что это не отдельный тип а просто обычный атом-константа. Вот несколько примеров, которые иллюстрируют особенности erlang:

1> 1==1.
true
2> 1>2.
false
3> a is_boolean(true).
true
5> is_boolean(2+3).
false

ОператорОписание
and Возвращает true если оба аргумента по отдельности вернут true
andalso Возвращает false если первый аргумент был false и не проверяет второй аргумент
or Возвращает true если любой аргумент был true
orelse Возвращает true если первый аргумент был true, без проверки второго элемента
xor Возвращает true если один из аргументов true, а другой false
not Возвращает true если аргумент был false, и наоборот

2 Кортежи и списки в Erlang (Tuples, Lists)

Кортежи

Кортежи встречаются не во многих языках. Это своего рода контейнеры, которые могут содержать другие типы. Их часто сравнивают со структурами в Си, только поля кортежа не имею имени. Несколько примеров:

{1,2,3}.
{a, b,c}.
{}.
{true, false}.
{{1, 2, 3}, {one, two, three}, {"One", "Two", "Three"}}}.

И несколько функций, для работы с кортежами:

1> tuple_size({one, {111, 222}, true, false, 3.1415}).
5
2> element(2, {one, {111, 222}, true, false, 3.1415}).
{111,222}
3> setelement(2, {one, {111, 222}, true, false, 3.1415}, result).
{one,result,true,false,3.1415}
4> {1, 2, 3} == {1, 2, 3}.
true
5> {1, 2, 4} > {1, 2, 3, 5}.
false
6> {0,0,0,0} > {1,1,1}.
true

Списки

Если кортежи используются как структуры, то списки — основная структура данных в Erlang, с их помощью хранятся данные произвольной размерности. Да, в Erlang вы можете поместить в список элементы разных типов.

1> [1,2,3].
[1,2,3]
2> [a, b,c].
[a,b,c]
3> [].
[]
4> [[1, 2, 3], [one, two, three], ["One", "Two", "Three"]].
[[1,2,3],[one,two,three],["One","Two","Three"]]
5> [1, 2] == [1, 2].
true
6> {1, 2, 4} > {1, 2, 3, 5}
true
7> [0,0,0,0] > [1,1,1].
false

Более подробно про списки читайте в статьи «Обработка списков на Erlang«.

3 Erlang. Строки. Работа со списками

Strings (строки)

Символы в erlang представляются целыми числами, а строки — списками числовых значений ASCII символов. Это связано с тем что erlang пришел из телекома, а там, работа со строками это почти экзотика. Поскольку символы это ASCII, то в 32х разрядной версии для сравнения символа в памяти используется два байта, а в x64 — четыре, что не эффективно, но, насколько я понимаю, эта проблема решается в новых версиях. Разница между атомами, рассмотренными прежде, и строками в том что атомы можно только сравнивать (на манер констант), в то время как со строками можно производить всевозможные операции. Другая разница заключается в объеме памяти, занимаемой эрлангом атомом и строками, а также скорости операции сравнения, — атомы тут, безусловно выигрывают.

Цифровое представление символов можно получить добавив "$" перед символом:

1> $1.
49
2> $1+1.
50
3> $a.
97
4> $a+1.
98

Вот, что представляют из себя строки:

1> "hello".
"hello"
2> "HELLO".
"HELLO"
3> [$H,$e,$l,$l,$o].
"Hello"
4> [$H,$e,108,$l,$n+1].
"Hello"

Обработка списков

Как уже упоминалось разница между кортежами и списками, в первую очередь, в том как они обрабатываются. Кортежи можно разбирать только поэлементно, с то время как списки можно разбивать на списки с «головой» и «хвостом», пока лист не будет пуст. Это очень популярная в эрланге операция и является чем-то типа аналога цикла.

Например, для списка [1, 2, 3], головой будет являться 1, а хвостом 2, 3. Таким образом все эти списки эквивалентны:

[1, 2, 3] == [1 | [2, 3]] == [1 | [2 | [3]]] == [1 | [2 | [3 | []]]]

Вот еще хороший пример, иллюстрирующий то, как работает оператор «|»

1> [First | Rest] = [1,2,3,4,5].
[1,2,3,4,5]
2> First.
1
3> Rest.
[2,3,4,5]

И еще один, отлично иллюстрирующий идею:

sum([]) -> 0;
sum([Head | Tail]) -> Head + sum(Tail).

sum([2,3,4] = 2 + sum([3,4])
sum([2,3,4] = 2 + sum([3,4]) = 5 + sum([4]) = 9

Функции для работы со списками

1> lists:max([1,2,5,8,4]).
8
2> lists:sort([2,4,1,3,5]).
[1,2,3,4,5]
3> lists:split(2, [1,2,3,4,5]).
{[1,2],[3,4,5]}
4> lists:sum([1,2,3]).
6
5> lists:zip([1,2,3],[5,6,7]).
[{1,5},{2,6},{3,7}]
6> lists:delete(2,[1,2,3]).
[1,3]
7> lists:last([1,2,4,8,5]).
5
8> lists:member(2,[1,3,2]).
true
9> length([1,2,3]).
3

Для работы со списками также есть два оператора ++ и --. Первый складывает два списка, элементы второго списка добавляются в конец первого, а второй извлекает из первого списка элементы переданные во втором. Проще увидеть это на примере:

1> [1,2,3] -- [2,3].
[1]
2> [1,2,3] -- [3,1].
[2]
3> [1,2,3] ++ [3,1].
[1,2,3,3,1]
4> [1,2,3] ++ [1,3,1].
[1,2,3,1,3,1]

4 Сопоставление с образцом (pattern matching) в Erlang

Сопоставление или pattern matching, это еще один способ присвоения, извлечения значений из списков или кортежей. Работает это так — сравнивается две переменные, если они не эквивалентны по типу или по значению возникнет исключение (ошибка). Если они равны, но отличаются только в переменных, то переменным в левой части выражения будет присвоено соответствующие значения справа. Проще всего это тоже пояснить на примере. Напомню, переменные всегда начинаются с заглавной:

1> {A, B} = {111, 222}.
{111,222}
2> A.
111
3> B.
222
4> [Head|Tail] = [1,2,3,4,5].
[1,2,3,4,5]
5> Head.
1
6> Tail.
[2,3,4,5]
7> {1,2,X} = {1,2,3}.
{1,2,3}
8> X.
3

А вот несколько примеров сопоставления которые не будут работать:

1> [A] = [1,2].
** exception error: no match of right hand side value [1,2]
2> {A, B} = [1,2].
** exception error: no match of right hand side value [1,2]
3> [A, 1] = [1, 2].
** exception error: no match of right hand side value [1,2]
4> 

Знак подчеркивания можно использовать для игнорирования значений в левой части выражения:

1> {A, B, _} = {1, 2, 3}.
{1,2,3}
2> {1, 2, C, _} = {A, B, 3, 4}.
{1,2,3,4}
3> C.
3
4> B.
2
5> A.
1

Функции и модули в Erlang

Функции

Понятно что это такое, понятно для чего они используются. В erlang функции это все. Они вызываются, передаются в качестве аргументов, создаются другими функциями. Давайте определим, для примера, бесполезную функцию считающую произведение двух чисел:

mul(A, B) -> A * B.

В консоли такой синтаксис работать не будет, но можно изощрться создать через лямбда-функцию:

1> F = fun(A, B) -> A * B.
2> F(2, 3).
6

Классический пример факториала:

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

Как видите, сопоставление используется для аргументов функций, и при том очень широко:

calc({multiply, A, B}) -> 
    A * B;
calc({divide, A, B}) -> 
    A / B.

В этом примере можно видеть, как в зависимости от значения константы в кортеже, выполняются разные типы вычислений.

Модули

Код нужно структурировать и организовывать, чтобы не потеряться в хаосе функций, для этого используются модули, — отдельные файлы содержащие своего рода «публичные» и «приватные» функции:

-module (test).
-export ([calc/1]).

calc({multiply, A, B}) -> 
    A * B;
calc({divide, A, B}) -> 
    A / B.

Вначале модуля можно видеть директивы module, export. Если первый определяет имя модуля, который должен совпадать с именем файла, то второй указывает какие функции могут быть использованы снаружи модуля. Синтаксис calc/1 означает что экспортируется ф-ция с одним аргументом. Директива import означает что функции другого модуля должны быть доступны. Модули, также, должны быть скомпилированы перед использованием. Скомпилированный модуль имеет разрешение .beam. Компилируется модуль функцией c():

1> c(test.erl).
{ok,test}

Операции if/then/else/case

Напишем несложную функцию, находящую максимальный элемент массива:

-module(test).
-export([list_max/1]).

list_max([]) -> [];
list_max([Head | Rest]) -> list_max(Head, Rest).
list_max(Head, []) -> Head;
list_max(Head, [NewHead | List]) ->
	if 
		Head > NewHead -> list_max(Head, List);	
  		true -> list_max(NewHead, List)
  	end.
1> c(test.erl).
{ok,test}
2> test:list_max([1,2,3,4,5]).
5

Первое, на что стоит обратить — аналог оператора else отсутствует, вместо этого true -> «что-то там». В остальном более-менее привычно, за исключением того что все время приходится мыслить «рекурсивно». На самом деле, операторы if/then/else/case изначально отсутствовали в языке, все это можно делать при помощи pattern matching, что кстати говоря и считается, более правильным. Вот, тот же пример, иллюстрирующий этот подход:

-module(test).
-export([list_max/1]).

list_max([]) -> [];
list_max([Head | Rest]) -> list_max(Rest, Head).
list_max([], MaxValue) -> MaxValue;
list_max([Head | Rest], MaxValue) when Head > MaxValue -> 
  list_max(Rest, Head);
list_max([Head | Rest], MaxValue) -> list_max(Rest, MaxValue).

А вот пример того как работает case в erlang:

-module(days).
-export([day_of_week/1]).

day_of_week(Day) ->
  case Day of
  	0 -> monday;
  	1 -> tuesday;
  	2 -> wednesday;
  	3 -> thursday;
  	4 -> friday;
  	5 -> saturday;
  	6 -> sunday
  end.

1> c(days.erl).        
{ok,days}
2> days:day_of_week(1).
tuesday

Упражнения

В рамках программы изучения Erlang я делаю упражнения из книги «Erlang programming» Франческо Чезарини и Саймона Томпсона. Оказалось что это на редкость полезное занятие, — теперь синтаксис не кажется таким уж страшным, и решение хоть и простых, но практических задач, придает уверенности в себе. Ниже я приведу условия задачи (уж простите, без перевода) и свой вариант решения (зачастую не оптимальный).

Exercise 3-1: Evaluating Expressions

Write a function sum/1which, given a positive integer N, will return the sum of all the integers between 1 and N.

Example: sum(5) ⇒ 15.

Write a function sum/2which, given two integers N and M, where N =< M, will return the sum of the interval between N and M. If N > M, you want your process to terminate
abnormally.

Example:
sum(1,3) ⇒ 6.
sum(6,6) ⇒ 6.

-module(test3_1).
-export([start/0]).
-import(io).
-import(lists).

listCreate(L, Start, End) ->
  if
	Start < End -> listCreate(L ++ [End], Start, End - 1);
	true -> L
  end.

sum(N) ->
  %Res = listCreate([], 0, N),
  %io:format("~w~n", [Res]),
  lists:sum(listCreate([], 0, N)).

sum(Start, End) ->
  lists:sum(listCreate([], Start, End)).

start() ->  
  io:format("~w~n~w~n", [sum(5), sum(1,3)]).

Exercise 3-2: Creating Lists
Write a function that returns a list of the format [1,2,..,N-1,N].

Example:
create(3) ⇒ [1,2,3].

Write a function that returns a list of the format [N, N-1,..,2,1].

Example:
reverse_create(3) ⇒ [3,2,1].

-module(test3_2).
-export([start/0]).

create(List, 0) -> List;
create(List, N) -> create(List ++ [N], N - 1).
create(N) -> create([], N).

start() ->
  create(3).

Exercise 3-3: Side Effects

Write a function that prints out the integers between 1 and N.
Hint: use io:format("Number:~p~n",[N]).
Write a function that prints out the even integers between 1 and N.
Hint: use guards.

-module (test3_3).
-import (io).
-export ([start/0]).

% implementation with if
print(Max, Cur) ->
  NewCur = Cur + 1,
  if 
    Max > Cur ->
      io:format("Number:~p~n",[NewCur]),
      print(Max, NewCur);
    true -> io:format("Number:~p~n",[NewCur])
  end.

print(Max) ->
  print(Max - 1, 0).

% implementation with guard
print1(Max, Min) when Max > Min ->
  NewCur = Min + 1,
  io:format("Number:~p~n",[NewCur]),
  print1(Max, NewCur);
print1(_, _) -> false.

print1(Max) -> 
  print1(Max, 0).

start() ->
%  print(3).
  print1(3).

Exercise 3-4: Database Handling Using Lists

Write a module db.erlthat creates a database and is able to store, retrieve, and delete
elements in it. The destroy/1function will delete the database. Considering that Erlang
has garbage collection, you do not need to do anything. Had the dbmodule stored
everything on file, however, you would delete the file. We are including the destroy
function to make the interface consistent. You may notuse the listslibrary module,
and you have to implement all the recursive functions yourself.

Hint: use lists and tuples as your main data structures. When testing your program,
remember that Erlang variables are single-assignment:

Interface:

db:new() ⇒ Db.
db:destroy(Db) ⇒ ok.
db:write(Key, Element, Db) ⇒ NewDb.
db:delete(Key, Db) ⇒ NewDb.
db:read(Key, Db) ⇒{ok, Element} | {error, instance}.
db:match(Element, Db) ⇒ [Key1, …, KeyN].

Example:

1> c(db).
{ok,db}
2>  Db = db:new().
[]
3>  Db1 = db:write(francesco, london, Db).
[{francesco,london}]
4> Db2 = db:write(lelle, stockholm, Db1).
[{lelle,stockholm},{francesco,london}]
5> db:read(francesco, Db2).
{ok,london}
6>  Db3 = db:write(joern, stockholm, Db2).
[{joern,stockholm},{lelle,stockholm},{francesco,london}]
7>  db:read(ola, Db3).
{error,instance}
8>  db:match(stockholm, Db3).
[joern,lelle]
9>  Db4 = db:delete(lelle, Db3).
[{joern,stockholm},{francesco,london}]
10> db:match(stockholm, Db4).
[joern]

И мой вариант решения:

-module (test3_4).
-compile(export_all).
-import (io).

new() ->
  [].

destroy(_) ->
  new().

write(Key, Element, Db) ->
  Db ++ [{Key, Element}].

filter(_, [], Result) ->
  Result;
filter(F, [Head | Tail], Result) ->  
  case
    F(Head) of true ->
      filter(F, Tail, Result ++ [Head]);
    false -> 
      filter(F, Tail, Result)
  end.

remove(Key, Db) ->
  filter(fun(X) -> element(1, X) /= Key end, Db, []).

read(Key, Db) ->
  filter(fun(X) -> element(1, X) == Key end, Db, []).

match(Value, Db) -> 
  [Result | _ ] = filter(fun(X) -> element(2, X) == Value end, Db, []),  
  element(1, Result).

test() -> 
  Db = write(key2, value2, write(key1, value1, new())),
  match(value1, Db).

Другой вариант решения:

-module(db).
-export([new/0,destroy/1,write/3,delete/2,read/2,match/2]).

new()->[].

destroy(_)->ok.

write(Key, Element, Db)->[{Key,Element}] ++ Db.

read(Key, []) ->{error, instance};
read(Key, [{Key,Element}|_])->{ok,Element};
read(Key, [{_,_}|T])->read(Key,T).

delete(Key,[])->[];
delete(Key,[{Key,_}|T])->T;
delete(Key,[H|T]) -> [H| delete(Key,T)].

match(Element, [])->[];
match(Element, [{Key,Element}|T])->[Key| match(Element,T)];
match(Element, [{_,_}|T])->match(Element,T).

Упражнения на списки в Erlang

Exercise 3-5: Manipulating Lists

Write a function that, given a list of integers and an integer, will return all integers
smaller than or equal to that integer.

Example:
filter([1,2,3,4,5], 3) ⇒ [1,2,3].

Write a function that, given a list, will reverse the order of the elements.

Example:
reverse([1,2,3]) ⇒ [3,2,1].

Write a function that, given a list of lists, will concatenate them.

Example:
concatenate([[1,2,3], [], [4, five]]) ⇒ [1,2,3,4,five].

Hint: you will have to use a helpfunction and concatenate the lists in several steps.
Write a function that, given a list of nested lists, will return a flat list.

Example:
flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]) ⇒ [1,2,3,4,5,6].

Hint: use concatenateto solve flatten

Мой вариант решения:

-module (test3_5).
-compile(export_all).
-import (io).

filter([], _Max, Result) -> 
  Result;
filter([Head | Tail], Max, Result) when Head >= Max ->  
  filter(Tail, Max, Result ++ [Head]);
filter([_Head | Tail], Max, Result) ->  
  filter(Tail, Max, Result).
filter(List, Max) -> 
  filter(List, Max, []).

reverse([], Result) ->
  Result;
reverse([Head | Tail], Result) ->
  reverse(Tail, [Head] ++ Result).
reverse(List) ->
  reverse(List, []).

concatenate(L) ->
  concatenate(L, []).
concatenate([], Result) ->
  Result;
concatenate([Head | Tail], Result) ->
  concatenate(Tail, Result ++ Head).

flatten(List) ->
  flatten(List, []).
flatten([], Result) ->
  Result;
flatten([Head | Tail], Result) ->
  flatten(Tail, Result ++ flatten(Head));
flatten(Value, Result) ->
  Result ++ [Value].

test() ->
  filter([1,2,3,4,5],3),
  reverse([1,2,3]),
  concatenate([[1,2,3], [], [4, five]]),
  flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]).

Упражнение по Erlang — Сортировка

Exercise 3-6: Sorting Lists

Implement the following sort algorithms over lists:

Quicksort

The head of the list is taken as the pivot; the list is then split according to those
elements smaller than the pivot and the rest. These two lists are then recursively
sorted by quicksort, and joined together, with the pivot between them.

Надо сказать, это очень инетересное упражнение и заставило прилично вникнуть и понять синтаксис и работу erlang. Допускаю, что решение не самое оптимальное, и можно написать вариант быстрее, но мне кажется, что код очень легко читается, воспринимается и позволяет сразу увидеть суть алгоритма:

-module (test_3_6_qsort).
-compile(export_all).
-import (io).

qsort([]) ->
	[];

qsort([H | T]) ->	
	{Lesser, Bigger} = filter(H, T, {[], []}),
    qsort(Lesser) ++ [H] ++ qsort(Bigger).

filter(_, [], {Lesser, Bigger}) ->	
	{Lesser, Bigger};

filter(H, [Cur | T], {Lesser, Bigger}) ->  
    if
        H > Cur ->
            filter(H, T, {Lesser ++ [Cur], Bigger});
        true ->
            filter(H, T, {Lesser, Bigger ++ [Cur]})
    end.

test() ->    
	qsort([4,1,200,5,9,7,8,55,11,441]).

PS. Текст статьи я в значительной части заимствовал у Шереметова, но авторские права, насколько я понимаю, соблюдены.

Добавить комментарий