Журнал LinuxFormat - перейти на главную

LXF143:erlang

Материал из Linuxformat
(Различия между версиями)
Перейти к: навигация, поиск
(викификация, оформление)
 
 
Строка 1: Строка 1:
: '''''Erlang''''' Язык функ­цио­наль­но­го про­грам­ми­ро­ва­ния [[Категория:Учебники]]
+
: '''''Erlang''''' Язык функ­цио­наль­но­го про­грам­ми­ро­ва­ния
 
+
[[Категория:Учебники]]
 +
[[Категория:Erlang]]
 
{{Цикл/Erlang}}
 
{{Цикл/Erlang}}
  

Текущая версия на 21:18, 10 июля 2014

Erlang Язык функ­цио­наль­но­го про­грам­ми­ро­ва­ния

Содержание

[править] Erlang: Язык для про­цес­сов

Ан­д­рей Уша­ков зна­ко­мит вас с кон­цеп­ци­ей функ­цио­наль­но­го про­грам­ми­ро­ва­ния и од­ним из многочисленных язы­ков на ос­но­ве этой кон­цеп­ци­и.

Функ­цио­наль­ное про­грам­ми­ро­вание зву­чит как ака­де­ми­че­­ская дис­ци­п­ли­на в ВУ­Зе: нечто за­ум­ное и ото­рван­ное от ре­аль­ной жизни. Еще бы не сло­жить­ся та­ко­му впе­чат­лению – сто­ит толь­ко по­смот­реть на язы­ки про­грам­ми­ро­вания из мейн­ст­ри­ма: C, C++, Java, C#, ... И ка­кой из этих язы­ков про­грам­ми­ро­вания функ­цио­наль­ный? Но сто­ит толь­ко при­смот­реть­ся повнима­тельней, как вы уви­ди­те эле­мен­ты функ­цио­наль­но­го про­грам­ми­ро­вания и в этих язы­ках (по крайней ме­ре, в боль­шин­ст­ве). Так, на­при­мер, в функ­цио­наль­ном про­грам­ми­ро­вании есть кон­цеп­ция функ­ций выс­ше­го по­ряд­ка (бо­лее под­роб­но см. да­лее) – это функ­ции, ко­то­рые принима­ют функ­ции в ка­че­­ст­ве па­ра­мет­ра, ли­бо воз­вра­щае­мое зна­чение есть функ­ция. Но по­доб­ные функ­ции выс­ше­го по­ряд­ка у нас встре­ча­ют­ся и в им­пе­ра­тив­ных язы­ках: так, в про­грам­мах на C, C++ мы мо­жем принимать ли­бо воз­вра­щать ука­за­тель на функ­цию; в про­грам­мах на C++, Java, C# мы мо­жем принимать ли­бо воз­вра­щать ин­тер­фейс с одним ме­то­дом, и т. д.

Бо­лее то­го, мно­гие им­пе­ра­тив­ные язы­ки вво­дят эле­мен­ты, под­дер­жи­ваю­щие функ­цио­наль­ное про­грам­ми­ро­вание: на­при­мер, в C# для по­доб­ной под­держ­ки бы­ли вве­де­ны де­ле­га­ты и лям­бды. В на­стоя­щее вре­мя поя­ви­лись и раз­ви­ва­ют­ся функ­цио­наль­ные язы­ки, ко­то­рые мож­но отнести к мейн­ст­ри­му: F#, Scala, ... Дан­ная ста­тья по­свя­ще­на об­зо­ру од­но­го из та­ких функ­цио­наль­ных язы­ков – Erlang, ко­то­рый мож­но опи­сать сле­дую­щей фор­му­лой: функ­цио­наль­ный язык + про­цес­сы.

[править] Эле­мен­ты про­грам­ми­ро­вания

Функ­цио­наль­ное про­грам­ми­ро­вание – очень боль­шая те­ма, ко­то­рой посвящно много книг. Да­вай­те ко­рот­ко рас­смот­рим осо­бен­но­сти, пре­иму­ще­ст­ва и недостат­ки функ­цио­наль­ных язы­ков (же­лаю­щие изу­чить эту те­му бо­лее под­роб­но мо­гут об­ра­тить­ся к со­от­вет­ст­вую­щей ли­те­ра­ту­ре). Что же от­ли­ча­ет функ­цио­наль­ное про­грам­ми­ро­вание от им­пе­ра­тив­но­го (от про­грам­ми­ро­вания, на­при­мер, на язы­ке C)? Глав­ным об­ра­зом то, как трак­ту­ет­ся про­цесс вы­чис­ления: вы­чис­ление есть вы­чис­ление зна­чений функ­ций в ма­те­ма­ти­че­­ском понимании по­следних. А это оз­на­ча­ет сле­дую­щее: зна­чение функ­ции оп­ре­де­ля­ет­ся толь­ко зна­чения­ми пе­ре­дан­ных ей ар­гу­мен­тов, и нет ника­ко­го внешнего со­стояния, от ко­то­ро­го мо­жет за­ви­сеть зна­чение функ­ции.

Этот под­ход силь­но от­ли­ча­ет­ся от под­хо­да им­пе­ра­тив­но­го про­грам­ми­ро­вания, в ко­то­ром вы­чис­ление трак­ту­ет­ся как по­сле­до­ва­тель­ность из­менений со­стояния про­грам­мы. И, в от­ли­чие от функ­цио­наль­но­го под­хо­да, вы­чис­ление в им­пе­ра­тив­ном про­грам­ми­ро­вании мо­жет иметь по­боч­ные эф­фек­ты, то есть зна­чение функ­ции, на­при­мер, за­ви­сит уже не толь­ко от зна­чения ар­гу­мен­тов, но и от внешнего со­стояния. По­нят­но, что ес­ли бы в функ­цио­наль­ных язы­ках бы­ли толь­ко вы­чис­ления, не за­ви­ся­щие от внешнего со­стояния, они вряд ли бы когда-ли­бо вы­шли за рам­ки ака­де­ми­че­­ско­­го ин­те­ре­са. Поль­зо­ва­тель­ский ввод и вы­вод, ра­бо­та с фай­ла­ми, с ба­за­ми дан­ных и т. п. – все это вы­чис­ления, за­ви­ся­щие от внешнего со­стояния (и с неко­то­ры­ми по­боч­ны­ми эф­фек­та­ми). И во всех функ­цио­наль­ных язы­ках есть те или иные сред­ст­ва для ра­бо­ты с та­ки­ми вы­чис­ления­ми (так, в Erlang про­сто не все функ­ции яв­ля­ют­ся неза­ви­си­мы­ми от внешнего со­стояния).

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

Те­перь по­го­во­рим о ми­ну­сах. Свя­за­ны они с тем, что функ­цио­наль­ный под­ход бо­лее аб­ст­рак­тен, чем им­пе­ра­тив­ный, и реа­ли­за­ции функ­цио­наль­ных язы­ков вы­ну­ж­де­ны доста­точ­но мно­го де­лать «под ка­по­том», что при­во­дит к до­полнитель­ным рас­хо­дам ре­сур­сов ком­пь­ю­те­ра, в неко­то­рых слу­ча­ях доста­точ­но су­ще­ст­вен­ным. В пер­вую оче­редь это необ­хо­ди­мость на­ли­чия сбор­ки му­со­ра, во вто­рую – под­держ­ка «ленивых» вы­чис­лений.

Сто­ит упо­мя­нуть еще па­ру кон­цеп­ций, ко­то­рые ши­ро­ко ис­поль­зу­ют­ся в функ­цио­наль­ном про­грам­ми­ро­вании: функ­ции выс­ших по­ряд­ков и аноним­ные функ­ции (лям­бда-вы­ра­жения). Функ­ции выс­ше­го по­ряд­ка – это функ­ции, ко­то­рые принима­ют в ка­че­­ст­ве ар­гу­мен­тов од­ну или несколь­ко функ­ций, ли­бо воз­вра­щае­мое зна­чение есть функ­ция. Так, функ­ция, вы­чис­ляю­щая зна­чение оп­ре­де­лен­но­го ин­те­гра­ла, яв­ля­ет­ся при­ме­ром функ­ции выс­ше­го по­ряд­ка, принимаю­щей в ка­че­­ст­ве ар­гу­мен­та дру­гую функ­цию; а функ­ция, воз­вра­щаю­щая функ­цию – ре­шение диф­фе­рен­ци­аль­но­го уравнения яв­ля­ет­ся при­ме­ром функ­ции выс­ше­го по­ряд­ка, воз­вра­щае­мое зна­чение ко­то­рой есть функ­ция. Аноним­ная функ­ция – это функ­ция, оп­ре­де­лен­ная толь­ко в том мес­те, где она ис­поль­зу­ет­ся. По­это­му, со­от­вет­ст­вен­но, аноним­ная функ­ция об­хо­дит­ся без имени и не уча­ст­ву­ет в про­це­ду­ре по­ис­ка функ­ции по имени в мо­мент ком­пи­ля­ции.

[править] Осо­бен­но­сти язы­ка

Рас­смот­рим неко­то­рые эле­мен­ты функ­цио­наль­но­го про­грам­ми­ро­вания при­менитель­но к язы­ку Erlang.

Пе­ре­мен­ные яв­ля­ют­ся на­столь­ко фун­да­мен­таль­ны­ми объ­ек­та­ми, что они при­сут­ст­ву­ют, по­жа­луй, во всех язы­ках. И Erlang в этом плане не ис­клю­чение – пе­ре­мен­ные в нем есть. Erlang яв­ля­ет­ся язы­ком со стро­гой ди­на­ми­че­­ской ти­пи­за­ци­ей. По­это­му при объ­яв­лении пе­ре­мен­ной ее тип не за­да­ет­ся (в от­ли­чие, на­при­мер, от C), а ди­на­ми­че­­ски вы­во­дит­ся во вре­мя вы­полнения. При объ­яв­лении пе­ре­мен­ной очень важ­но, что­бы ее имя на­чи­на­лось с за­глав­ной бу­к­вы – это ее от­ли­ча­ет от дру­гих объ­ек­тов. На­при­мер, SomeVariable – это пе­ре­мен­ная. Зна­чение пе­ре­мен­ной мо­жет быть при­свое­но один и толь­ко один раз, и по­сле при­своения ее зна­чение не мо­жет быть из­менено. Та­ким об­ра­зом, мы всегда зна­ем, в ка­ком мес­те про­грам­мы пе­ре­мен­ная по­лу­чи­ла свое зна­чение, и это очень силь­но уп­ро­ща­ет от­лад­ку.

При­сваи­вая зна­чение пе­ре­мен­ной, мы ис­поль­зу­ем опе­ра­тор = (на­при­мер, SomeVariable = 1). Но этот опе­ра­тор не яв­ля­ет­ся опе­ра­то­ром при­своения (что очень неожи­дан­но для че­ло­ве­ка, имею­ще­го опыт про­грам­ми­ро­вания на им­пе­ра­тив­ных язы­ках вроде C): это опе­ра­то­р со­от­вет­ст­вия [pattern matching]. При вы­чис­лении вы­ра­жения Left = Right про­ис­хо­дит про­вер­ка, со­от­вет­ст­ву­ют ли Left и Right друг дру­гу. Left и Right бу­дут со­от­вет­ст­во­вать друг дру­гу в сле­дую­щих слу­ча­ях:

  • Left и Right име­ют од­но и то­же зна­чение од­но­го и то­го же ти­па. На­при­мер, 1 = 1.

 * Объ­яв­ля­ет­ся пе­ре­мен­ная Left. В этом слу­чае, т. к. пе­ре­мен­ная Left ника­ко­го зна­чения не име­ет, ей при­сваи­ва­ет­ся зна­че­ние Right.

Опе­ра­ция со­от­вет­ст­вия по­яв­ля­ет­ся не толь­ко при ис­поль­зо­вании опе­ра­то­ра =. В лю­бом мес­те про­грам­мы, где воз­мож­но по­яв­ление опе­ран­дов Left и Right, бу­дет про­ис­хо­дить про­вер­ка на их со­от­вет­ст­вие. На­при­мер, пусть у нас есть сле­дую­щее объ­яв­ление функ­ции (бо­лее под­роб­но о функ­ци­ях см. да­лее):

f(0) -> true;
f(Number) -> f(Number-1).

В пер­вой стро­ке со­дер­жит­ся кон­кре­ти­зи­рую­щий ва­ри­ант функ­ции f(). При вы­зо­ве функ­ции бу­дет про­ис­хо­дить по­иск в по­ряд­ке объ­яв­ления ва­ри­ан­тов. При этом за­дан­ное зна­чение па­ра­мет­ра бу­дет про­ве­рять­ся на со­от­вет­ст­вие зна­чению, оп­ре­де­лен­но­му в ва­ри­ан­те. Так, на­при­мер, вы­зов f(0) при­ве­дет к вы­зо­ву пер­во­го ва­ри­ан­та, а вы­зов f(1) – к вы­зо­ву вто­ро­го, причем па­ра­мет­ру Number бу­дет при­свое­но зна­чение 1.

Что бу­дет, ес­ли при про­вер­ке двух опе­ран­дов Left и Right вы­­явится, что они не со­от­вет­ст­ву­ют друг дру­гу? Ес­ли мы ис­поль­зо­ва­ли опе­ра­тор =, то по­лу­чим ошиб­ку вре­мени вы­полнения. Ес­ли это бы­ло, на­при­мер, при про­смот­ре оче­ред­но­го ва­ри­ан­та объ­яв­ления функ­ции, то по­иск пе­рей­дет к сле­дую­ще­му ва­ри­ан­ту.

[править] Ти­пы дан­ных

Да­вай­те по­го­во­рим те­перь о ти­пах дан­ных Erlang. Наи­бо­лее оче­вид­ные ти­пы – это це­лые и дей­ст­ви­тель­ные чис­ла (бы­ло бы стран­но, ес­ли бы их не бы­ло в язы­ке про­грам­ми­ро­вания). Дру­гой, чуть менее оче­вид­ный тип дан­ных – это ато­мы. Ана­лог ато­мов – кон­стан­ты, но, в от­ли­чие от кон­стант, ато­мы не со­дер­жат свя­зан­ных с ними зна­чений. Объ­яв­ление ато­мов всегда на­чи­на­ет­ся с ма­лень­кой бу­к­вы: на­при­мер, atom_sample.

Сле­дую­щие два ти­па дан­ных яв­ля­ют­ся фун­да­мен­таль­ны­ми в боль­шин­ст­ве (ес­ли не во всех) функ­цио­наль­ных язы­ков про­грам­ми­ро­вания: это кор­те­жи и спи­ски. Кор­теж [Tuple] – это кон­тейнер для хранения объ­ек­тов раз­ных ти­пов. Его ана­ло­гом яв­ля­ют­ся, на­при­мер, струк­ту­ры язы­ка C, но, в от­ли­чие от струк­тур, по­ля кор­те­жа не име­ют имени. Доступ к ним мож­но осу­ще­ст­вить ли­бо по ин­дек­су по­ля, ли­бо с ис­поль­зо­ванием опе­ра­ции со­от­вет­ст­вия. На­при­мер, мы объ­ яв­ля­ем сле­дую­щий кор­теж: TupleSample = {1, atom_sample}. Тогда доступ к пер­во­му по­лю осу­ще­ст­в­ля­ет­ся сле­дую­щим об­ра­зом: element(1, TupleSample), а для досту­па к пер­во­му по­лю че­рез опе­ра­цию со­от­вет­ст­вия мы ис­поль­зу­ем сле­дую­щий син­так­сис: {First, Second} = TupleSample, по­сле че­го пе­ре­мен­ная First со­дер­жит зна­чение из пер­во­го по­ля кор­те­жа TupleSample. Спи­сок – это кон­тейнер для хранения объ­ек­тов од­но­го ти­па. Ана­ло­га­ми спи­ска яв­ля­ют­ся, на­при­мер, мас­си­вы язы­ка C, класс ArrayList язы­ка Java. Спи­сок объ­яв­ля­ет­ся сле­дую­щим об­ра­зом: [Element1, Element2, ...], на­при­мер, [1, 2, 3]. Су­ще­ст­ву­ет спе­ци­аль­ный син­так­сис для досту­па к го­лов­но­му и хво­сто­во­му эле­мен­там спи­ска че­рез опе­ра­цию со­ответ­ст­вия: [Head | Other] и [Other | Tail], где Other – остав­шая­ся часть спи­ска. Для соз­дания спи­сков так­же су­ще­ст­ву­ет спе­ци­аль­ная ме­то­ди­ка, ана­ло­гов ко­то­рой в им­пе­ра­тив­ных язы­ках про­грам­ми­ро­вания нет – List Comprehensions. Не уг­луб­ля­ясь во все воз­мож­но­сти это­го мощ­но­го ме­ха­низ­ма, про­сто при­ве­дем па­ру при­ме­ров.

  • Ге­не­ра­ция спи­ска квад­ра­тов чи­сел от 1 до 10: [N*N | | N <- lists:seq(1, 10)].
  • Ге­не­ра­ция спи­ска квад­ра­тов чи­сел от 1 до 10 толь­ко для чет­ных чи­сел: [N*N | | N <- lists:seq(1, 10), N rem 2 == 0].

А как же стро­ки, спро­си­те вы. Не­у­же­ли в Erlang сде­ла­ли шаг на­зад в от­но­шении ра­бо­ты со стро­ко­вы­ми дан­ны­ми? В Erlang от­дель­но­го ти­па дан­ных для строк нет: стро­ки пред­став­ля­ют­ся в ви­де спи­сков це­лых чи­сел. Но су­ще­ст­ву­ет «син­так­си­че­­ский са­хар» для ра­бо­ты со стро­ка­ми, по­зво­ляю­щий за­пи­сы­вать стро­ко­вые дан­ные в при­выч­ном ви­де. На­при­мер, ли­те­рал “123” син­так­си­че­­ски кор­рек­тен и со­от­вет­ст­ву­ет зна­чению [49, 50, 51]. К со­жа­лению, в при­выч­ном для нас ви­де мо­гут быть за­пи­са­ны стро­ки толь­ко в ко­ди­ров­ке Latin-1 (ISO-8859‑1). По­это­му в дру­ги­х ко­ди­ров­ках необ­хо­ди­мо ра­бо­тать на­пря­мую с дан­ны­ми в спи­сках.

По­ми­мо пе­ре­чис­лен­ных здесь ти­пов дан­ных, в язы­ке Erlang су­ще­ст­ву­ют и дру­гие ти­пы. Наи­бо­лее ин­те­рес­ный и зна­чи­мый из них – это тип дво­ич­ных дан­ных. Но уг­луб­лять­ся в эти ти­пы дан­ных мы не бу­дем.

[править] Функ­ции

По­жа­луй, по­следнее и са­мое важ­ное, что сле­ду­ет рас­ска­зать об Erlang – это объ­яв­ление функ­ций. В са­мом про­стом слу­чае, функ­ция объ­яв­ля­ет­ся обыч­ным об­ра­зом: имя функ­ции (оно долж­но на­чи­нать­ся с ма­лень­кой бу­к­вы), по­сле ко­то­ро­го сле­ду­ет спи­сок ар­гу­мен­тов (че­рез за­пя­тую) в скоб­ках (для объ­яв­ления ар­гу­мен­тов дей­ст­ву­ют те же пра­ви­ла име­но­вания, что и для пе­ре­мен­ных), а за ним сле­ду­ет те­ло функ­ции. На­при­мер, объ­яв­ление функ­ции, вы­чис­ляю­щей квад­рат сво­его ар­гу­мен­та, бу­дет вы­гля­деть так:

square(Number) -> Number*Number.

Функ­ции (сиг­на­ту­ры функ­ций, ес­ли быть бо­лее точ­ным) раз­ли­ча­ют­ся не толь­ко по имени, но и по чис­лу ар­гу­мен­тов, ко­то­рые они принима­ют (ар­ность функ­ции). По­это­му мы мо­жем иметь две или бо­лее функ­ции с оди­на­ко­вым именем, но раз­ным чис­лом ар­гу­мен­тов.

Но на этом воз­мож­но­сти оп­ре­де­ления функ­ции не за­кан­чи­ва­ют­ся. Мы мо­жем оп­ре­де­лить два и бо­лее ва­ри­ан­та од­ной и той же функ­ции. При вы­зо­ве функ­ции бу­дет про­ис­хо­дить по­сле­до­ва­тель­ный про­смотр всех объ­яв­лен­ных ва­ри­ан­тов (в по­ряд­ке их объ­яв­ления) и по­иск пер­во­го под­хо­дя­ще­го. Ка­кой ва­ри­ант бу­дет под­хо­дя­щим, за­ви­сит от пе­ре­дан­ных ар­гу­мен­тов. Ес­ли же не бу­дет най­де­но ни од­но­го под­хо­дя­ще­го ва­ри­ан­та, мы по­лу­чим ошиб­ку вре­мени вы­полнения.

Бла­го­да­ря ка­ким ме­ханиз­мам ва­ри­ан­ты функ­ции бу­дут от­ли­чать­ся друг от дру­га? Та­ких ме­ханиз­мов два: опе­ра­ция со­от­вет­ст­вия и ох­ран­ные вы­ра­жения [guards]. Ме­ханизм со­от­вет­ст­вия дей­ст­ву­ет сле­дую­щим об­ра­зом: при объ­яв­лении ва­ри­ан­та функ­ции для од­но­го или несколь­ких ар­гу­мен­тов мы вме­сто са­мих ар­гу­мен­тов за­да­ем ка­кие-ли­бо зна­чения. И при по­ис­ке под­хо­дя­ще­го ва­ри­ан­та эти зна­чения бу­дут сравнивать­ся со зна­чения­ми ар­гу­мен­тов, а ес­ли ме­ж­ду ними бу­дет со­от­вет­ст­вие, то бу­дет вы­бран этот ва­ри­ант функ­ции. На­при­мер, мы мо­жем объ­я­вить функ­цию для вы­чис­ления фак­то­риа­ла сле­дую­щим об­ра­зом:

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

Дру­гой ме­ханизм – это ох­ран­ные вы­ра­жения. Ох­ран­ное вы­ра­жение – это ло­ги­че­­ское вы­ра­жение с ар­гу­мен­та­ми функ­ции. Ес­ли при по­ис­ке под­хо­дя­ще­го ва­ри­ан­та ох­ран­ное вы­ра­жение ис­тин­но, то вы­би­ра­ет­ся этот ва­ри­ант. Ох­ран­ное вы­ра­жение объ­яв­ля­ет­ся при по­мо­щи клю­че­во­го сло­ва when. На­при­мер, функ­цию для вы­чис­ления фак­то­риа­ла мы мо­жем объ­я­вить при по­мо­щи ох­ран­но­го вы­ра­жения сле­дую­щим об­ра­зом:

factorial(N) when N == 0 or N == 1 -> 1;
factorial(N) -> N*factorial(N-1).

По­нят­но, что при объ­яв­лении функ­ции у нас мо­гут быть ва­ри­ан­ты, ис­поль­зую­щие со­от­вет­ст­вие, или ис­поль­зую­щие ох­ран­ные вы­ра­жения, или ис­поль­зую­щие и то, и дру­гое.

С функ­ция­ми свя­за­но еще од­но фун­да­мен­таль­ное по­ня­тие – хво­сто­вая ре­кур­сия. Ес­ли при вы­полнении функ­ции по­следней опе­ра­ци­ей бу­дет вы­зов са­мой се­бя (с те­ми же ли­бо с дру­ги­ми ар­гу­мен­та­ми), то этот вы­зов бу­дет не ре­кур­сив­ным (этот вы­зов бу­дет пред­став­лять со­бой про­стой пе­ре­ход на на­ча­ло функ­ции). Ес­ли же вы­зов са­мой се­бя бу­дет рас­по­ла­гать­ся где-то внут­ри те­ла (не бу­дет по­следней опе­ра­ци­ей), то это бу­дет обыч­ный ре­кур­сив­ный вы­зов. Так, на­при­мер, в функ­ции factorial() бу­дет хво­сто­вая ре­кур­сия, а в функ­ции factorial2() – нет:

factorial(N) when N == 0 or N == 1 -> 1;
factorial(N) -> N*factorial(N-1).
factorial2(N) when N == 0 or N == 1 -> 1;
factorial2(N) 
	 N*factorial(N-1),
	 log(N).

Хво­сто­вая ре­кур­сия важ­на тем, что она по­зво­ля­ет ор­ганизо­вать цикл (конеч­ный или бес­конеч­ный) и не при­во­дит к за­полнению сте­ка (ко­то­рое возника­ет при обыч­ном ре­кур­сив­ном вы­зо­ве).

[править] При­мер

Хва­тит тео­рии – да­вай­те ре­шим про­стую за­да­чу для де­мон­ст­ра­ции неко­то­рых кон­цеп­ций, из­ло­жен­ных вы­ше. В ка­че­­ст­ве при­ме­ра возь­мем за­да­чу но­мер 17 с про­ек­та Project Euler (http://projecteuler.net/index.php?section=problems&id=17). Ус­ло­вие этой за­да­чи зву­чит сле­дую­щим об­ра­зом:

Ес­ли чис­ла от 1 до 5 за­пи­сать анг­лий­ски­ми сло­ва­ми (one, two, three, four, five), то бу­дет ис­поль­зо­ва­но 3 + 3 + 5 + 4 + 4 = 19 букв. Ес­ли все чис­ло от 1 до 1000 вклю­чи­тель­но за­пи­сать анг­лий­ски­ми сло­ва­ми то сколь­ко бу­дет ис­поль­зо­ва­но букв?

При­ме­чание: Про­бе­лы и де­фи­сы при под­сче­те не учи­ты­вать. На­при­мер, 342 (three hundred and forty-two) со­дер­жит 23 бу­к­вы, 115 (one hundred and fifteen) – 20 букв. Ис­поль­зо­вание сою­за “and” со­от­вет­ст­ву­ет бри­тан­ско­му ва­ри­ан­ту.

На­шей за­да­чей бу­дет на­пи­сать про­грам­му, ко­то­рая счи­та­ет ко­ли­че­­ст­во букв, необ­хо­ди­мое для за­пи­си анг­лий­ски­ми сло­ва­ми чи­сел от 1 до N, при усло­вии, что N не пре­вы­ша­ет 1000. По пра­ви­лам бри­тан­ско­го ва­ри­ан­та анг­лий­ско­го язы­ка, ме­ж­ду сот­ня­ми и де­сят­ка­ми (ес­ли та­ко­вые есть) ста­вит­ся ар­тикль “and” (на­при­мер, чис­лу 115 со­от­вет­ст­ву­ет стро­ка one hundred and fifteen). По­это­му для удоб­ст­ва мы раз­де­лим об­ра­бот­ку де­сят­ков и со­тен в на­шей про­грам­ме. Ме­тод less_hundred/4 об­ра­ба­ты­ва­ет чис­ла, ко­то­рые мень­ше 100. В этом ме­то­де мы под­счи­ты­ва­ем ко­ли­че­­ст­во сим­во­лов, необ­хо­ди­мых для за­пи­си чис­ла, мень­ше­го 100, анг­лий­ски­ми сло­ва­ми:

less_hundred(Number, _, _, _) when Number >= 100 -> erlang:error(badarg);
less_hundred(Number, From0To9, _, _) when Number =< 9 ->
	 length(lists:nth(Number+1, From0To9));
less_hundred(Number, _, From10To19, _) when (Number > 9) and (Number < 20) ->
	 length(lists:nth(Number-9, From10To19));
less_hundred(Number, From0To9, _, OtherTens) ->
	 length(lists:nth((Number div 10)-1, OtherTens)) +
length(lists:nth((Number rem 10)+1, From0To9)).

Об­ра­ти­те вни­ма­ние, как мы оп­ре­де­ля­ем не­сколь­ко ва­ри­ан­тов функ­ции less_hundred/4 при по­мо­щи ох­ран­ных вы­ра­же­ний.

Сле­дую­щий шаг – об­ра­бот­ка чи­сел, не пре­вы­шаю­щих 1000. Для это­го слу­жит ме­тод parse_number/4:

parse_number(1000, _, _, _) -> length(“one” ++ “thousand”);
parse_number(Number, From0To9, From10To19, OtherTens) when Number >= 100 ->
LessHundred = less_hundred(Number rem 100, From0To9, From10To19, OtherTens),
	 if
		 LessHundred == 0 ->
length(lists:nth((Number div 100)+1, From0To9)) + length(“hundred”);
		 LessHundred /= 0 -> length(lists:nth((Number div 100)+1, From0To9)) + length(“hundred” ++ “and”) + LessHundred
	 end;
parse_number(Number, From0To9, From10To19, OtherTens) ->
	 less_hundred(Number rem 100, From0To9, From10To19, OtherTens).

Об­ра­ти­те внимание, что при оп­ре­де­лении несколь­ких ва­ри­ан­тов функ­ции parse_number/4 мы ис­поль­зу­ем как ме­ханизм со­от­вет­ст­вия, так и ох­ран­ные вы­ра­жения. Сле­ду­ет ска­зать, что в дан­ном ме­то­де мы при­ме­ня­ем кон­ст­рук­цию, ко­то­рую в об­зо­ре не об­су­ж­да­ли – кон­ст­рук­цию if. Эта кон­ст­рук­ция со­сто­ит из по­сле­до­ва­тель­но­сти пар вы­ра­жений (раз­де­лен­ных опе­ра­то­ром ->) и воз­вра­ща­ет неко­то­рое зна­чение. Воз­вра­щае­мое зна­чение оп­ре­де­ля­ет­ся сле­дую­щим об­ра­зом: по­сле­до­ва­тель­но про­смат­ри­ва­ют­ся па­ры вы­ра­жений, в ка­ж­дой па­ре вы­чис­ля­ет­ся зна­чение пер­во­го вы­ра­жения, и ес­ли зна­чение пер­во­го вы­ра­жения рав­но true, то зна­чение вто­ро­го вы­ра­жения ста­но­вит­ся воз­вра­щае­мым (ли­бо бу­дет бро­ше­на ошиб­ка вре­мени вы­полнения, ес­ли по­иск за­вер­шит­ся не успеш­но).

Ос­та­лось сде­лать со­всем не­мно­го – об­ра­бо­тать все чис­ла от 1 до не­ко­то­ро­го мак­си­маль­но чис­ла (не пре­вы­шаю­ще­го 1000).

parse_numbers(MaxNumber, From0To9, From10To19, OtherTens) ->
	 parse_numbers(MaxNumber, 1, 0, From0To9, From10To19, OtherTens).
parse_numbers(MaxNumber, CurrentNumber, LetterCount, _, _, _)
	 when CurrentNumber > MaxNumber -> LetterCount;
parse_numbers(MaxNumber, CurrentNumber, LetterCount, From0To9, From10To19, OtherTens) ->
	 parse_numbers(MaxNumber, CurrentNumber + 1, LetterCount + parse_number(CurrentNumber, From0To9, From10To19, OtherTens), From0To9, From10To19, OtherTens).

Для та­кой об­ра­бот­ки мы вво­дим две функ­ции: parse_number/4 и parse_number/6. Эти функ­ции яв­ля­ют­ся раз­ны­ми за счет то­го, что у них раз­ное ко­ли­че­­ст­во ар­гу­мен­тов (раз­ная ар­ность) – это ва­ри­ант пе­ре­груз­ки функ­ций в Erlang. Про эти функ­ции сле­ду­ет за­ме­тить сле­дую­щее: parse_number/4 яв­ля­ет­ся ин­тер­фейс­ной функ­ци­ей к parse_number/6, а parse_number/6, со­от­вет­ст­вен­но, функ­ци­ей реа­ли­за­ции. Это удоб­ный и ши­ро­ко при­ме­няе­мый в Erlang под­ход, когда функ­ция с мень­шим чис­лом ар­гу­мен­тов объ­яв­ля­ет­ся для удоб­ст­ва ис­поль­зо­вания, а функ­ция с тем же са­мым именем и боль­шим чис­лом ар­гу­мен­тов вы­пол­ня­ет всю ра­бо­ту (по­доб­ные при­ме­ры ин­тер­фейс­ных объ­ек­тов и объ­ек­тов реа­ли­за­ций мож­но лег­ко най­ти в им­пе­ра­тив­ных язы­ках).

Ну и, на­ко­нец, экс­пор­ти­руе­мая функ­ция, для взаи­мо­дей­ст­вия с на­шей функ­цио­наль­но­стью (solve/1):

solve(MaxNumber) when MaxNumber > 1000 -> erlang:error(badarg);
solve(MaxNumber) ->
	 From0To9 = [“”, “one”, “two”, “three”, “four”, “five”, “six”, “seven”, “eight”, “nine”],
	 From10To19 = [“ten”, “eleven”, “twelve”, “thirteen”, “fourteen”, “fifteen”, “sixteen”, “seventeen”, “eighteen”, “nineteen”],
	 OtherTens = [“twenty”, “thirty”, “forty”, “fifty”, “sixty”, “seventy”, “eighty”, “ninety”],
	 parse_numbers(MaxNumber, From0To9, From10To19, OtherTens).

Ос­та­лось толь­ко при­вес­ти объ­яв­ле­ния мо­ду­ля и экс­пор­ти­руе­мых функ­ций:

-module(problem_017).
-export([solve/1]).

Вот и все ре­шение за­да­чи. За­пуска­ем в кон­со­ли сре­ду вы­полнения (за­пуском ис­пол­няе­мо­го фай­ла erl; на­де­юсь, пу­ти у вас на­строе­ны), в кон­со­ли Erlang за­пуска­ем сна­ча­ла ком­пи­ля­цию с(problem_017)., а по­том и вы­полнение на­шей про­грам­мы problem_017:solve(1000), и по­лу­ча­ем сле­дую­щий ре­зуль­тат: 21124. Ес­ли зай­ти на сайт про­ек­та Project Euler, в раз­дел за­да­чи но­мер 17, то мож­но убе­дить­ся, что это пра­виль­ный от­вет (http://projecteuler.net/index.php?section=problems&id=17).

O мно­го­за­дач­но­сти и взаи­мо­дей­ст­вии ме­ж­ду про­цес­са­ми мы по­го­во­рим в сле­дую­щей час­ти это­го учеб­ни­ка.

[править] Дру­гие функ­цио­наль­ные язы­ки

  • Scala – муль­ти­па­ра­диг­маль­ный язык, спро­ек­ти­ро­ван­ный крат­ким и ти­по­бе­зо­пас­ным для про­сто­го и бы­ст­ро­го про­грам­ми­ро­вания. В нем со­че­та­ют­ся воз­мож­но­сти функ­цио­наль­но­го и объ­ект­но-ори­ен­ти­ро­ван­но­го под­хо­дов. Ос­нов­ной це­лью раз­ра­бот­ки был язык, об­ла­даю­щий хо­ро­шей под­держ­кой ком­понент­но­го ПО.
  • Haskell – стан­дар­ти­зо­ван­ный чис­тый функ­цио­наль­ный язык про­грам­ми­ро­вания об­ще­го на­зна­чения. Яв­ля­ет­ся одним из са­мых рас­про­стра­нен­ных язы­ков с под­держ­кой от­ло­жен­ных вы­чис­лений.
  • Lisp – се­мей­ст­во язы­ков про­грам­ми­ро­вания, дан­ные в ко­то­рых пред­став­ля­ют­ся сис­те­ма­ми линей­ных спи­сков сим­во­лов. Язык яв­ля­ет­ся функ­цио­наль­ным, но мно­гие поздние вер­сии об­ла­да­ют так­же чер­та­ми им­пе­ра­тив­но­сти; к то­му же, имея пол­но­цен­ные сред­ст­ва сим­воль­ной об­ра­бот­ки, ста­но­вит­ся воз­мож­ным реа­ли­зо­вать объ­ект­но-ори­ен­ти­ро­ван­ность. Наи­бо­лее по­пу­ляр­ные в на­ши дни диа­лек­ты язы­ка Lisp – это Common Lisp и Scheme.
  • ML – се­мей­ст­во стро­гих язы­ков функ­цио­наль­но­го про­грам­ми­ро­вания с раз­ви­той по­ли­морф­ной сис­те­мой ти­пов и па­ра­мет­ри­зуе­мы­ми мо­ду­ля­ми. Это не чис­то функ­цио­наль­ные язы­ки, так как вклю­ча­ют и им­пе­ра­тив­ные ин­ст­рук­ции. ML пре­по­да­ет­ся во мно­гих за­пад­ных универ­си­те­тах (в неко­то­рых да­же как пер­вый язык про­грам­ми­ро­вания).
  • Miranda – функ­цио­наль­ный язык про­грам­ми­ро­вания, имею­щий стро­гую по­ли­морф­ную сис­те­му ти­пов и под­дер­жи­ваю­щий ти­пы дан­ных поль­зо­ва­те­ля. Как и язык ML, пре­по­да­ет­ся во мно­гих универ­си­те­тах.
  • OCaml – со­вре­мен­ный объ­ект­но-ори­ен­ти­ро­ван­ный язык функ­цио­наль­но­го про­грам­ми­ро­вания об­ще­го на­зна­чения, ко­то­рый был раз­ра­бо­тан с уче­том безо­пас­но­сти ис­полнения и на­деж­но­сти про­грамм. Язык OCaml под­дер­жи­ва­ет функ­цио­наль­ную, им­пе­ра­тив­ную и объ­ект­но-ори­ен­ти­ро­ван­ную па­ра­диг­мы про­грам­ми­ро­вания.
  • F# – функ­цио­наль­ный язык про­грам­ми­ро­вания об­ще­го на­зна­чения. Струк­ту­ра F# во мно­гом схо­жа со струк­ту­рой Ocaml, с той лишь разницей, что язык F# реа­ли­зо­ван по­верх биб­лио­тек и сре­ды ис­полнения .NET.

[править] По­лез­ные ссыл­ки и кни­ги

  • http://www.erlang.org/ – глав­ный сайт (с до­ку­мен­та­ци­ей и ис­ход­ным ко­дом сре­ды).
  • http://www.trapexit.org/ – сайт Erlang-со­об­ще­ст­ва (фо­рум, ви­ки, ре­ше­ния, учеб­ные по­со­бия, спра­воч­ные ма­те­риа­лы).
  • http://erlanger.ru/ – сайт рус­ско­го Erlang-сооб­ще­ст­ва.
  • http://groups.google.com/group/erlang-russian – рус­ское Erlang-со­об­ще­ст­во на Google.
  • http://www.tryerlang.org/ – он­лайн-ин­тер­пре­та­тор Erlang.
  • Martin Logan, Eric Merritt, and Richard Carlsson “Erlang and OTP in Action”.
  • Francesco Cesarini, Simon Thompson “Erlang Programming A Concurrent Approach to Software Development”.
  • Joe Armstrong “Programming Erlang: Software for a Concurrent World”.
Персональные инструменты
купить
подписаться
Яндекс.Метрика