Pull to refresh

Функциональное программирование на CoffeeScript с библиотекой f_context

Reading time 5 min
Views 4.5K
Тем, кто сталкивался с функциональными языками программирования наверняка знакома такая конструкция:
  fact(0) -> 1
  fact(N) -> N * fact(N - 1)

Это один из классических примеров ФП — вычисление факториала.
Теперь это можно делать и на CoffeeScript с библиотекой f_context, просто оборачивая код в f_context ->, например:
  f_context ->
    fact(0) -> 1
    fact(N) -> N * fact(N - 1)


Как это работает
Посмотреть больше примеров

Что умеет библиотека


Модули
Pattern Matching
Destructuring
Guards
Переменная _ и матчинг одинаковых аргументов

Примеры из реальной жизни


Модульность:

По умолчанию f_context возвращает сгенерированный модуль, т.о. его можно положить в какую-то переменную:
examples = f_context ->

  f_range(I) ->
    f_range(I, 0, [])

  f_range(I, I, Accum) -> Accum
  f_range(I, Iterator, Accum) ->
    f_range(I, Iterator + 1, [Accum..., Iterator])

examples.f_range(10) #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Успользуя директиву module можно сразу положить модуль в глобальное пространство,
например window или global:
f_context ->

  module("examples")

  f_range(I) ->
    f_range(I, 0, [])

  f_range(I, I, Accum) -> Accum
  f_range(I, Iterator, Accum) ->
    f_range(I, Iterator + 1, [Accum..., Iterator])

examples.f_range(10) #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


Pattern Matching

что это и зачем оно нужно
Пример:
  matching_example_1("foo") -> "foo matches"
  matching_example_1("bar") -> "bar matches"
  matching_example_1(1) -> "1 matches"
  matching_example_1(true) -> "true matches"
  matching_example_1(Str) -> "nothing matches, argument: #{Str}"

Результат:
  matching_example_1("foo") #returns "foo matches"
  matching_example_1("bar") #returns "bar matches"
  matching_example_1(1) #returns "1 matches"
  matching_example_1(true) #returns "true matches"
  matching_example_1("baz") #returns "nothing matches, argument: baz"



Destructuring

что это и зачем оно нужно
Примеры:
  test_destruct_1([Head, Tail...]) -> {Head, Tail}
  test_destruct_1_1([Head, Head1, Tail...]) -> {Head, Head1, Tail}


  test_destruct_2([Head..., Last]) -> {Head, Last}
  test_destruct_2_1([Head..., Last, Last1]) -> {Head, Last, Last1}


  test_destruct_3([Head, Middle..., Last]) -> {Head, Middle, Last}
  test_destruct_3_1([Head, Head2, Middle..., Last, Last2]) -> {Head, Head2, Middle, Last, Last2}

Результат:
  test_destruct_1([1,2,3]) #returns {Head: 1, Tail: [2,3]}
  test_destruct_1_1([1,2,3,4]) #returns {Head: 1, Head1: 2, Tail: [3,4]}

  test_destruct_2([1,2,3]) #returns {Head: [1,2], Last: 3}
  test_destruct_2_1([1,2,3,4]) #returns {Head: [1,2], Last: 3, Last1: 4}

  test_destruct_3([1,2,3,4]) #returns {Head: 1, Middle: [2,3], Last: 4}
  test_destruct_3_1([1,2,3,4,5,6]) #returns {Head: 1, Head2: 2, Middle: [3,4], Last: 5, Last2: 6}



Guards

что это и зачем оно нужно
Гварды задаются через директиву where(%condition%).
В гвардах можно задавать более гибкое сравнение. Пример вычисления ряда Фибоначчи:
  #без гвардов
  fibonacci_range(Count) ->
    fibonacci_range(Count, 0, [])

  fibonacci_range(Count, Count, Accum) -> Accum

  fibonacci_range(Count, 0, Accum) ->
    fibonacci_range(Count, 1, [Accum..., 0])

  fibonacci_range(Count, 1, Accum) ->
    fibonacci_range(Count, 2, [Accum..., 1])

  fibonacci_range(Count, Iterator, [AccumHead..., A, B]) ->
    fibonacci_range(Count, Iterator + 1, [AccumHead..., A, B, A + B])

  #с гвардами
  fibonacci_range(Count) ->
    fibonacci_range(Count, 0, [])

  fibonacci_range(Count, Count, Accum) -> Accum

  fibonacci_range(Count, Iterator, Accum) where(Iterator is 0 or Iterator is 1) ->
    fibonacci_range(Count, Iterator + 1, [Accum..., Iterator])

  fibonacci_range(Count, Iterator, [AccumHead..., A, B]) ->
    fibonacci_range(Count, Iterator + 1, [AccumHead..., A, B, A + B])



Переменная _ и матчинг одинаковых аргументов

Переменная _ служит для «сбрасывания» аргументов, в случае если их значение не важно, но важно количество аргументов
Пример реализации функции all:
f_all([Head, List...], F) ->
  f_all(List, F, F(Head))

f_all(_, _, false) -> false
f_all([], _, _) -> true

f_all([Head, List...], F, Memo) ->
  f_all(List, F, F(Head))

Если задать одинаковые названия аргументов, то автоматически будет проведено их сравнение.
Пример реализации функции range:
f_range(I) ->
  f_range(I, 0, [])

f_range(I, I, Accum) -> Accum
f_range(I, Iterator, Accum) ->
  f_range(I, Iterator + 1, [Accum..., Iterator])



Примеры из жизни

Порой реализовать тот или иной алгоритм гораздо удобнее с помощью рекурсии.
Например, функции reduce и quick sort в функциональном стиле:
f_context ->
  f_reduce(List, F) ->
    f_reduce(List, F, 0)

  f_reduce([], _, Memo) -> Memo

  f_reduce([X, List...], F, Memo) ->
    f_reduce(List, F, F(X, Memo))

f_context ->
  f_qsort([]) -> []
  f_qsort([Pivot, Rest...]) ->
    [
      f_qsort((X for X in Rest when X < Pivot))...,
      Pivot,
      f_qsort((Y for Y in Rest when Y >= Pivot))...
    ]

на мой взляд проще и понятнее своих императивных аналогов.


Как это работает


Вернемся к самому первому в этой статье примеру — вычисление факториала.
  fact(0) -> 1
  fact(N) -> N * fact(N - 1)

В CoffeeScript это является абсолютно валидной конструкцией.

Пример посложнее, подсчет количества элементов в списке в функциональном стиле:
  count(List) ->
    count(List, 0)

  count([], Iterator) -> Iterator
  count([Head, List...], Iterator) ->
    count(List, Iterator + 1)

И это тоже валидный CoffeeScript код.
Таким образом мы можем писать в привычном для функциональных языков стиле прямо на coffee, без надобности использовать прекомпилятор.

Для наглядности дальше буду рассказывать на примере все того же факториала. Итак,
этот код:
  fact(0) -> 1
  fact(N) -> N * fact(N - 1)

странслируется в js следующим образом:
  fact(0)(function() {
    return 1;
  });
  fact(N)(function() {
    return N * fact(N - 1);
  });

Его даже можно исполнить, но с ошибками «ReferenceError», про то что fact и N не объявлены.
Можно завернуть этот код в функцию-обертку, таким образом чтобы он передавался в качестве аргумента
  function_wrapper ->
    fact(0) -> 1
    fact(N) -> N * fact(N - 1)

в js получим следующее:
function_wrapper(function() {
    fact(0)(function() {
      return 1;
    });
    fact(N)(function() {
      return N * fact(N - 1);
    });
});

Теперь function_wrapper может проанализировать функцию, передаваемую ей в
аргументе и передать в нее все недостающие переменные. Примерно вот так:
var function_wrapper = function(fn){

  var fn_body = fn.toString().replace(/function.*\{([\s\S]+)\}$/ig, "$1");

  var new_function = Function.apply(null, fn_body, /*именованные аргументы*/ 'fact', 'N');

  var fact_stub = function(){
    return function(){};
  };

  // маркируем N как переменную
  var N_stub = function(){};
  N_stub.type = "variable";
  N_stub.name = "N";

  new_function(fact_stub, N_stub)

}

Теперь код выполняется уже без ошибок, но пока ничего не делает.
Дальше дело за fact_stub, которая тоже может проанализировать свои аргументы и
сгенерировать свою локальную ветвь текущей функции. Для факториала это будет выглядеть примерно вот так:

После того как дерево парсинга построено, можно легко сгеренировать модуль и создать его через все тот же Function.apply
Тело модуля должно получиться вот таким:
var f_fact_local_0 = function(){
  return 1;
};
var f_fact_local_1 = function(N){
  return N * f_fact(N - 1);
};
var f_fact = function(){
  if(arguments[0] === 0){
    return f_fact_local_0();
  }
  return f_fact_local_1(arguments[0]);

};
return {
  f_fact: f_fact
};


На деле все немного сложнее, но здесь я постарался изложить базовые принципы работы.
Если статья не понятна — пишите, постараюсь исправить.

Сама библиотека лежит вот здесь: github.com/nogizhopaboroda/f_context

Любые комментарии приветствуются. Как и feature-request'ы.
Only registered users can participate in poll. Log in, please.
Понятна ли статья?
54.9% Понятна 28
25.49% Не понятна 13
33.33% О чем это вообще? 17
51 users voted. 21 users abstained.
Tags:
Hubs:
+10
Comments 25
Comments Comments 25

Articles