Můj první erlang modul

13.4.2007 17:56 | Přečteno: 2113× | erlang | | poslední úprava: 16.4.2007 11:15

Nedávno jsem narazil na úžasný nový (pro mě), průmyslově ověřený funkcionální jazyk. Jmenuje se Erlang. Jeho vlastnosti mě přiměly říct wow! Posuďte sami. Za pozornost stojí například distributed (no on je to taky tak trochu komplet OS co se dokáže tvářit, že jede jako by jeden homogenní OS na heterogenním HW) a Hot code upgrade (viz example 14), nebo "Mnesia is a nice example of the power of Erlang: in how many languages could you write a fully-featured industrial-strength distributed DBMS in less than 20,000 lines of code?"

Napsal jsem, že je pro mě nový, ale on tak zas nový není, vznikl už kolem roku 1987 a stále se vyvíjí (4 release v roce 2006 a od začátku 2007 už stihl dva další - teda jedná se spíš o upgrade nadstaveb a nástrojů jako OTB). Má velmi lehké thready, například na AMD Athlon XP 2200+ má režii na vytvoření vlákna, přijetí zprávy a odeslání zprávy 2,1 us (včetně ukončení vlákna a garbage collectingu, testováno na 100 mil. vláknech, na samotnou zprávu padne asi 0,4 us)

Tak jsem si řekl, že si ho trošku ošahám. Jedna z prvních věcí, co mě zajímala (mimo jiné), byla existence nějakého dokumentačního systému. A měl ho tam, edoc. Takže jsem si napsal takový jednoduchý modulek a zkusil si ho v edocu zdokumentovat. Zároveň jsem si to chtěl troško o benchmarkovat a proto jsem si udělal takový malý generátor permutací. Tady je:

%% @copyright 2007 Hynek Vychodil
%% @author Hynek Vychodil <pichi@nekde.top>
%%   [http://www.abclinuxu.cz/blog/Pichi]
%% @version 0.0.1
%% @end
%% =====================================================================
%% @doc perms - Permutation generator
%%
%% This module provides "simply" permutation generator with state support.
%%
%% == Usage ==
%%```
%%> perms:perms([a,b,c]).
%%[[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]
%%> perms:foreach(fun(P)->io:format("~p~n",[P]) end, [a,b,c]).
%%[a,b,c]
%%[a,c,b]
%%[b,a,c]
%%[b,c,a]
%%[c,a,b]
%%[c,b,a]
%%ok
%%> perms:foldl(fun(_,N)->N+1 end, 0, lists:seq(1,10)).
%%3628800
%%> perms:map(fun(P)->lists:flatten(io_lib:write(P)) end, [a,b,c]).
%%["[a,b,c]","[a,c,b]","[b,a,c]","[b,c,a]","[c,a,b]","[c,b,a]"]
%%> {_,FS} = perms:first([a,b,c]).
%%{[a,b,c],[{[b],[]},{[c],[b]},{[a,b,c],[]}]}
%%> perms:next(FS).
%%{[a,c,b],[{[c],[]},{[a,c],[]},{[b,c],[a]}]}
%%> perms:next([{[c],[]},{[a,c],[]},{[b,c],[a]}]).
%%{[b,a,c],[{[a],[]},{[c],[a]},{[b,c],[a]}]}
%%> perms:nextState([{[a],[]},{[b],[a]},{[c],[b,a]}]). % e.g. last state -> [c,b,a]   
%%'$end_of_table'
%%> perms:perm([{[a],[]},{[b],[a]},{[c],[b,a]}]). % see above
%%[c,b,a]
%%'''

-module(perms).
-export([first/1, next/1, perms/1, foreach/2, map/2, foldl/3, foldr/3]).
-export([firstState/1, perm/1, nextState/1]).
-import(lists, [reverse/1, reverse/2]).

%% @spec (list()) -> {L::list(), State::state()}
%% @type state() = [stack_entry()] | '$end_of_table'
%% 		stack_entry() = { Todo::list(), Done::list() }.
%%	State is stack emulation of standard permutation generators
%%
%% @doc Makes first permutation (same as original `L') and `State' for next permutation.
%% @see next/1
first(L) -> next(firstState(L)).
%% @spec (state()) -> {P::list(), S2::state()}
%% @doc Makes permutation `P' from current `S' {@type state()} and next `S2' {@type state()}.
next(S) -> {perm(S), nextState(S)}.

%% @spec (list()) -> State::state()
%% @doc Makes first `State' ({@type state()}) for permutation of `L'.
%%
%% {@link perm/1} from this state makes original `L'.
firstState(L) -> firstState(L, []).

firstState([], Result) -> Result;
firstState([_|Rest] = L, Result) ->
	firstState(Rest, [{L, []}|Result]).

%% @spec (state()) -> P::list()
%% @doc Makes permutation `P' from current `State'.
%% @see firstState/1
%% @see nextState/1
%% @end
%perm('$end_of_table') -> throw(beyond_end);
perm(State) -> perm(State, []).

perm([], Perm) -> Perm;
perm([{[H|_], _}|RestOfState], Perm) ->
	perm(RestOfState, [H|Perm]).

%% @spec (State::state()) -> Next::state()
%% @doc Makes `Next' {@type state()} from current `State'.
%% @end
%nextState('$end_of_table') -> throw(beyond_end);
nextState([]) -> '$end_of_table';
nextState([{[_], _}|State]) ->
	nextState(State);
nextState([{[H|[_|TT]=T], Rest}|State]) ->
	firstState(reverse(Rest, [H|TT]), [{T, [H|Rest]}|State]).

%% @spec (list()) -> Permutations::list()
%% @doc Returns {@type list()} containing all `L''s permutations.
perms(L) -> perms(firstState(L), []).

perms('$end_of_table', Res) -> reverse(Res);
perms(State, Res) ->
	{P, NS} = next(State),
	perms(NS, [P|Res]).

%% @spec (F, list()) -> ok
%% 	F = (P::list()) -> any()
%% @doc Call `F' for each permutation `P' of `L'.
foreach(F,L) -> foreachState(F, firstState(L)).

foreachState(_, '$end_of_table') -> ok;
foreachState(F, State) ->
	{P, NS} = next(State),
	F(P),
	foreachState(F, NS).

%% @spec (F, list()) -> Result::list()
%%	F = (P::list()) -> Res
%%	Result = [Res]
%% @doc Makes `Result' {@type list()} of `Res' results from calling `F' on each permutations `P' of `L'.
map(F, L) -> map(F, firstState(L), []).

map(_, '$end_of_table', Res) -> reverse(Res);
map(F, State, Res) ->
	{P, NS} = next(State),
	map(F, NS, [F(P)|Res]).
%% @spec (F, Acc0, list()) -> Acc
%%	F = (P::list(), AccIn) -> AccOut
%% @doc Folds permutations of `L'. Calls `F' on each permutation of `L'. `Acc0' is passed as `AccIn' to firts `F' call
%% and each `AccOut' is passed to next `F' call.
%% Last `F' call result is returned as `Acc'.
foldl(F, Acc0, L) -> foldlState(F, Acc0, firstState(L)).

foldlState(_, Acc, '$end_of_table') -> Acc;
foldlState(F, Acc, S) ->
	{P, NS} = next(S),
	foldlState(F, F(P, Acc), NS).

%% @spec (F, Acc0, list()) -> Acc
%%	F = (P::list(), AccIn) -> AccOut
%% @doc Same as {@link foldl/3} but in reverse order.
foldr(F, Acc0, L) -> foldl(F, Acc0, reverse(L)).

Nic moc složitého, že? A přitom vygenerování 3 628 800 permutací desetiprvkové množiny a zavolání nějaké drobné funkce pro každou už tomu dá trošku zapotit, a taky že jo: cca 4,3 us na výše uvedeném Athlonu. Nic moc proti Alghoritm-Permute a 0,6 us (nejrychlejší = "call back" použití) na stejném stroji, ale to je psané přímo v C a vlastně nevím jestli jsem zvolil zrovna vhodný algoritmus. Snad mi vyjde čas zkusit totéž nativně v perlu, případně pythonu.

A tady je ta slíbená dokumentace:

Module perms

perms - Permutation generator.

Copyright © 2007 Hynek Vychodil

• Description
• Data Types
• Function Index
• Function Details

Version: 0.0.1

Authors: Hynek Vychodil (pichi@nekde.top) [web site: http://www.abclinuxu.cz/blog/Pichi].

Description

perms - Permutation generator

This module provides "simply" permutation generator with state support.

Usage

 > perms:perms([a,b,c]).
 [[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]
 > perms:foreach(fun(P)->io:format("~p~n",[P]) end, [a,b,c]).
 [a,b,c]
 [a,c,b]
 [b,a,c]
 [b,c,a]
 [c,a,b]
 [c,b,a]
 ok
 > perms:foldl(fun(_,N)->N+1 end, 0, lists:seq(1,10)).
 3628800
 > perms:map(fun(P)->lists:flatten(io_lib:write(P)) end, [a,b,c]).
 ["[a,b,c]","[a,c,b]","[b,a,c]","[b,c,a]","[c,a,b]","[c,b,a]"]
 > {_,FS} = perms:first([a,b,c]).
 {[a,b,c],[{[b],[]},{[c],[b]},{[a,b,c],[]}]}
 > perms:next(FS).
 {[a,c,b],[{[c],[]},{[a,c],[]},{[b,c],[a]}]}
 > perms:next([{[c],[]},{[a,c],[]},{[b,c],[a]}]).
 {[b,a,c],[{[a],[]},{[c],[a]},{[b,c],[a]}]}
 > perms:nextState([{[a],[]},{[b],[a]},{[c],[b,a]}]). % e.g. last state -> [c,b,a]
 '$end_of_table'
 > perms:perm([{[a],[]},{[b],[a]},{[c],[b,a]}]). % see above
 [c,b,a]

Data Types

state()

state() = [stack_entry()] | '$end_of_table'

• stack_entry() = {Todo::list(), Done::list()}

State is stack emulation of standard permutation generators

Function Index

first/1	Makes first permutation (same as original L) and State for next permutation.
firstState/1	Makes first State (state()) for permutation of L.
foldl/3	Folds permutations of L.
foldr/3	Same as foldl/3 but in reverse order.
foreach/2	Call F for each permutation P of L.
map/2	Makes Result list() of Res results from calling F on each permutations P of L.
next/1	Makes permutation P from current S state() and next S2 state().
nextState/1	Makes Next state() from current State.
perm/1	Makes permutation P from current State.
perms/1	Returns list() containing all L's permutations.

Function Details

first/1

first(L::list()) -> {L::list(), State::state()}

Makes first permutation (same as original L) and State for next permutation.

See also: next/1.

firstState/1

firstState(L::list()) -> State::state()

Makes first State (state()) for permutation of L.

perm/1 from this state makes original L.

foldl/3

foldl(F, Acc0, L::list()) -> Acc

• F = (P::list(), AccIn) -> AccOut

Folds permutations of L. Calls F on each permutation of L. Acc0 is passed as AccIn to firts F call and each AccOut is passed to next F call. Last F call result is returned as Acc.

foldr/3

foldr(F, Acc0, L::list()) -> Acc

• F = (P::list(), AccIn) -> AccOut

Same as foldl/3 but in reverse order.

foreach/2

foreach(F, L::list()) -> ok

• F = (P::list()) -> any()

Call F for each permutation P of L.

map/2

map(F, L::list()) -> Result::list()

• F = (P::list()) -> Res
• Result = [Res]

Makes Result list() of Res results from calling F on each permutations P of L.

next/1

next(S::state()) -> {P::list(), S2::state()}

Makes permutation P from current S state() and next S2 state().

nextState/1

nextState(State::state()) -> Next::state()

Makes Next state() from current State.

perm/1

perm(State::state()) -> P::list()

Makes permutation P from current State.

See also: firstState/1, nextState/1.

perms/1

perms(L::list()) -> Permutations::list()

Returns list() containing all L's permutations.

Celkem to ujde a ještě se to nechá formátovat CSS a kvůli Abíčku jsem musel vyhodit nějaké ty atributy kolem tabulky. Kdyby jste si chtěli někdo obenchmarkovat thready a zprávy u sebe, tak ještě zdrojáky testů co jsem dělal

Erlang vlákna

-module(ring).
-export([start/1, start/2, server/1, child/1]).

child(Parent) ->
	receive
		0 ->
			Parent ! done;
		N ->
			Child = spawn(?MODULE, child, [Parent]),
			Child ! N-1
	end.

start(N) -> start(N, 10000).

start(N, Timeout) ->
	process_flag(trap_exit, true),
	Parent = spawn_link(?MODULE, server, [Timeout]),
	statistics(wall_clock),
	Child = spawn(?MODULE, child, [Parent]),
	Child ! N,
	receive
		{'EXIT', Parent, ok} ->
			{_, T} = statistics(wall_clock),
			T/N/1000;
		{'EXIT', Parent, Reason} -> Reason
	end.

server(Timeout) ->
	receive
		done ->
			exit(ok)
		after
			Timeout ->
				exit(timeout)
	end.

Usage:

> c(ring).
{ok,ring}
> ring:start(pocet_opakovani)
trvání jednoho v sec. nebo atom timeout pokud na to nestačilo 10s
> ring:start(pocet_opakovani, timeout_v_ms)
trvání jednoho v sec. nebo atom timeout pokud na to nestačil zadaný timeout

Erlang zprávy - pingpong

-module(pingperf).
-export([start/1, pong/1]).

pong(P) ->
	receive
		ping ->
			P ! pong,
			pong(P)
	end.

ping(P, 0) -> exit(P, kill);
ping(P, N) ->
	P ! ping,
	receive
		pong ->
			ping(P, N-1)
	end.

start(N) ->
	statistics(wall_clock),
	PONG = spawn(?MODULE, pong, [self()]),
	ping(PONG, N),
	{_, T} = statistics(wall_clock),
	T/N/2000.

Usage:

> c(pingperf).
{ok,ring}
> ring:start(pocet_opakovani)
trvání zaslání jedné zprávy v sec.

Update:

Když už máme ten funkcionální jazyk, tak jde perms pěkně přepsat pomocí map (a taky nikam nespěchá, když chce vrátit všechny permutace )

--- perms.erl.old	2007-04-16 11:05:12.000000000 +0200
+++ perms.erl	2007-04-16 11:04:42.000000000 +0200
@@ -87,12 +87,8 @@
 
 %% @spec (list()) -> Permutations::list()
 %% @doc Returns {@type list()} containing all `L''s permutations.
-perms(L) -> perms(firstState(L), []).
-
-perms('$end_of_table', Res) -> reverse(Res);
-perms(State, Res) ->
-	{P, NS} = next(State),
-	perms(NS, [P|Res]).
+perms(L) -> map(fun identity/1, L).
+identity(P) -> P.
 
 %% @spec (F, list()) -> ok
 %% 	F = (P::list()) -> any()

       

Komentáře

[deda.jabko]

krucis, krucis.... erlang vypada fakt cool... skoda, ze musim delat hafo jinych veci a nemuzu se misto toho naucit novy jazyk ;-]...

je to jenom muj pocit nebo se ten jazyk tezce inspiroval prologem? ...nicmene s podporou sekvencniho zpracovani to muze byt docela divocina...

[Kyosuke]

Pro seznámení doporučuju skvělý, jedinečný, neopakovatelný „Erlang:The Movie“ (Trošku ve stylu Montyho Pythona - autoři na něj dodnes neradi vzpomínají )

[Hynek (Pichi) Vychodil]

Ten film je dobrej, s chutí jsem ho zhlédl a celkem mě potěšilo, že jsem všemu rozuměl. Holt ta moje angličtina už není tak hrozná

[Kyosuke]

Von je hlavně úplně děsnej , právě takovýhle lidi by měli držet v laboratořích a v řetězech (s volnýma rukama na klávesnici), páč tam budou užitečnější než při dělání PR. (-Ahoj, Michale! -Ahoj, Roberte! -Ahoj, Hynku! -Ahoj, Michale a Hynku! Ahoj, Jakube! -Ahoj všichni! )

[Martin]

Jo, tak zrovna u téhle části jsem si fakt nebyl jistý, jestli je to míněno vážně nebo je to zoufalý pokus o humor Jdu si to pustit ještě jednou

[Hynek (Pichi) Vychodil]

To nebyl až tak pokus o humor jako demonstrace síly erlnagu. Já jsem si celou tu dobu té šaškárny s opravou schopnosti dělat konferenční hovor říkal proč sakra zavolal a nechal odložené sluchátko. No a na závěr bum ho, on ten hovor stále běžel se starým kódem, prostě tam v jednu chvíli běžely dvě verze stejného modulu, ten starý s chybou na hovoru, který nevyužívá tu konferenční feature, no a pak druhý co to měl už opravené. Až se ukončí všechny procesy, co ten modul používají, tak se teprve starý kód zahodí. No ono je to krapet složitější, protože on ten sám proces dokonce může přejít na nový kód (stačí zavolat uvnitř toho modulu funkci přes modul:foo místo jen foo a bum a běží v nové verzi, typicky se tak píšou loop smyčky serveru viz níže).

Samoupgradující server:

loop(State) -> receive
     Msg -> NewState = do_some(State, Msg), ?MODULE:loop(NewState)
end.

Server s upgrade on demand:

loop(State) -> receive
     upgrade -> ?MODULE:loop(State);
     Msg -> NewState = do_some(State, Msg), loop(NewState)
end.

Pokud ten server má zpracovávat řádově stovky tisíc requestů za sekundu tak ten druhej kód bude o chlup rychlejší, ale zas musíš při upgrade zaslat ten signál.

[Martin]

Mě pobavila ta konverzace ve stylu Monty Pythona, proti erlangu samotnému (ani proti tomu, na co chtěli autoři poukázat) samozřejmě nenamítám nic

[Martin]

Moc hezké. Když jsem si onehdá řekl, že se pro rozptýlení pustím do nějakého funkcionálního jazyka, tak jsem si vybral Scheme a Haskell. Na Erlang se rád podrobněji mrknu, až se zkamarádím s výše uvedenými Jen teď řeším problém, do kterého se pustit dřív

[deda.jabko]

scheme ja dobra volba... a nejlip se ho naucite, kdyz si napisete vlastni intepretr.... (se kterym pak muzete oslnovat slecny ;-])

[Martin]

Netřeba vykat

Jj, taky mám pocit, že bude první na řadě Scheme. Sice mě ze začátku mátly ty řeči o praktické nepoužitelnosti (v porovnání s Lispem), ale Scheme na mě na první pohled působil jaksi, hmm... kompaktněji Zlé funkcionální jazyky by se sice osypaly při pomyšlení na možnost přiřazení, ale na to teď nehledím Zatím jsem nepoznal jazyk, který by byl víc sexy než libovolný dialekt Lispu A ty závorky, mmmmm...

Interpret možná přijde na řadu malinko později, jestli tím oslním svou slečnu, to sice nevím, ale zkusit to můžu (od mě jako od Matfyzáka už zažila mnohé ).

[Kyosuke]

Interpret možná přijde na řadu malinko později, jestli tím oslním svou slečnu, to sice nevím, ale zkusit to můžu (od mě jako od Matfyzáka už zažila mnohé ).

Největší frajeřina by byla dát jí ho k narozeninám...tím samozřejmě myslím napsat ho tak kompaktní, aby se – napsaný polevou – vešel na horní stranu dortu.

[Marek Bernát]

horní stranu dortu

Len tak odhadom, v hornej časti torty je zhruba 10^20 molekúl, takže mám pocit, že by sa tam vo vhodnom tvare vošiel aj interpreter Common Lispu :-P Hoci s CL jeden nikdy nevie

[Martin]

To je nápad! To bych do konce příštího ledna mohl stihnout

[Hynek (Pichi) Vychodil]

Scheme a Haskel se mi líbí, protože jsou přece jen modernější. Jenomže já potřebuji právě některé vlastnosti erlangu, hlavně ty tenké vlákna, zasílání zpráv, škálovatelnost, vždyť on to není jen jazyk, ale OS. Taky je možné, že toho prostě o Scheme a Haskelu málo vím a pak bych byl rád, kdyby mě někdo vyvedl z nevědomosti.

[Tom.š Ze.le.in]

Mimochodem, Scheme dostává své pověsti jazyka pro experimenty a existuje pokus o implementaci Erlangových vymožeností - Termite. O tom, že Erlang je vyzrálejší a prověřenější se samozřejmě nemá cenu hádat.

[Hynek (Pichi) Vychodil]

Migrace je dost podstatná feature, nicméně vyzrálost taky. No nic, budeme termite sledovat

[deda.jabko]

nenechte se zmast... scheme je z roku 1975...

koncept programovaci jazyk == operacni system == neco uzasneho je tu uz delsi dobu a ma sve kouzlo -- at uz ve smalltalk, jvm nebo kombinace unixove jadro+shell

jedna vec me, ale stale vrta v hlave... jak maji udelane ty hotupdaty... malinko tusim jednu fintu z pH (kazde vlakno ma svoji verzi pameti), ale jak to maji v praxi implementovane...

[Hynek (Pichi) Vychodil]

No spíš bych řekl, že využívají toho, že něco jako stav vůbec neexistuje. Pak je něco jako verze paměti moc netrápí, prostě jen funkce a její parametry. I přiřazení je přiřazení v matematickém smyslu i když záleží na pořadí (to jen kvůli jednoduššímu kompilátoru). Tím se spousta věcí zjednodušuje, takže je spíš něco jako centrální slovník modulů (přeložených binárek) s různými verzemi (konkrétně tři) a prostě se ta funkce jen zavolá přímo do té binárky, dokud se volá foo, tak to všechno běhá uvnitř té binárky snad i včetně imported funkcí (přímé adresy do verze jiného modulu, která byla v okamžiku natažení volajícího modulu, ale tím si nejsem jistý, možná, že to rovnou sahá po aktuální verzi) a v okamžiku požadavku na module:foo se koukne do aktuálního slovníku (je to o chlup pomalejší) a skočí na nejnovější verzi (trošku to připomíná Debian a jeho větve ). Problém může nastat pokud by ta hloubka 3 verze zpět nestačila. Jenže ty funkce jsou celkem malé a pokud uděláš velké moduly, tak ti to celé pěkně samo migruje na novější kód. No apk je tam funkce, co ti zjistí jestli běžíš ve staré verzi kódu. Samozřejmě třeba migrace na novou verzi jádra a init modulu a dalších systémových věcí je trochu těžší, ale jak často měníš jádro, že Asi jako jádro Linuxu, ale to pak nečekáš, že to samo přemigruje.

To by se ale chtělo kouknout přímo do implementace BEAMu, případně jádra, kompilátoru a loaderu. Zdrojáky jsou k dispozici

[Hynek (Pichi) Vychodil]

s/pokud uděláš velké moduly/pokud neděláš velké moduly/

[deda.jabko]

diky za osvetleni, kdyz tady nekdo hodil link na termite, tak me to uz trochu zacalo zapalovat.... vyporadat se stavem, tak ze vlastne neexistuje... a redukovat to na to, ze jediny stav jsou "mailboxy", kam chodi zpravy mezi vlaknama a u tech je zarucene, ze jsou na pocatku vlakna vzdycky prazdne... hm... panove co to vymysleli budou asi hodne chytri...