Meddling with the код!

Функции навсякъде

от meddle

В предишната публикация използвахме малко под-множество от даден език за програмиране и си дефинирахме своя имплементация на рекурсия. Нека сега да използваме още по-малко множество.

Представете си… Нямаме числа, низове, операции. Всичко, което имаме е способността да си дефинираме функции (абстракция) и да ги изпълняваме (апликация). Нека започнем от тук и да видим докъде ще стигнем.

В началото беше функцията

С какво разполагаме? Можем да дефинираме функции:

fn (x) -> x end

И да ги изпълняваме:

fn (x) -> x end.(fn (x) -> x end)

Това е всичко.

Но какво ще подаваме на една функция? Единственото, което знаем е, как да дефинираме функция и как да я извикаме с нещо. Но с какво? От примера по-горе виждате, че извикваме функцията с функция. Да. Това е така, защото единствения тип данни, който познаваме е функциите.

Още едно (последно) ограничение : имаме право да си дефинираме функции, които приемат само един, единствен аргумент.

Нека да обобщим:

1. Имаме само един тип данни - функции.
2. Знаем как да си дефинираме функция с един аргумент.
3. Знаем как да извикаме функция. От (1) следва, че функция може да се извика само като и подадем друга функция като аргумент.

За улеснение ще добавим:

4. Можем да си ‘именоваме’ функции за да ги преизползваме:

id = fn(x) -> x end
id.(id)

Добре. Но какво да правим с това, което имаме? Ами можем да си дефинираме няколко предизвикателства и да пробваме да ги изпълним, използвайки само това което имаме.

Нека това са:

1. Да намерим начин да подаваме повече от един аргумент на функция
2. Да си дефинираме най-простия тип - булевия
3. Да си дефинираме числа и операции с тях

Нека започнем.

Повече аргументи

Функцията, която дефинирахме и използвахме по-горе е известна като идентитет или I кобинатор. Тя приема един аргумент и просто го връща. Отсега нататък ще я използваме с името, което и дадохме : id.

Искаме да си дефинираме друг известен комбинатор - К. Това е много проста функция, известна още като ‘Керкенез’ (за повече информация защо, прочетете тази книжка). Интересното при Керкенеза е, че той се дефинира така: K : f(x, y) = x, което значи, че взима два аргумента и просто връща първия.

Всъщност има една техника, чиято цел е да промени логиката на изчисление на функция с множество аргументи, до функция на един аргумент, която връща функция на един аргумент, която връща функция на един аргумент и така нататък, в зависимост от броя на аргументите. Последната функция прави изчислението. Тази техника е известна като ‘шойнфинкелинг’. Нека я разгледаме:

a = fn (x, y, z) -> (x + y) * z end
b = fn (x) ->
      fn (y) ->
        fn (z) -> (x + y) * z end
      end
    end

a.(2, 3, 4)
# 20

b.(2).(3).(4)
# 20

В този пример виждате, че резултатът е един и същ, извикването и дефиницията са леко различни, но важното е, че изчислението се запазва. И да, в този пример си позволихме да излезем от ограниченията си. Всъщност тази техника е била кръстена на изобретателя си Moses Schönfinkel и усъвършенствана от Haskell Curry. Затова и днес не я наричаме ‘шойнфинкелинг’, а ‘къринг’. Сами се сетете защо :)

Важното е, че чрез нея можем да мислим за функции на един аргумент връщащи функции на един аргумент и така нататък, като за функции на множество аргументи. И така можем да си дефинираме Керкенеза:

kestrel = fn (x) -> fn (y) -> x end end

И за упражнението, нека си дефинираме още един комбинатор-птица - ‘Скорецът’, известен още като S комбинаторът. Неговата дефиниция е: S : f(x, y, z) = x(z, (y(z))). Това ще рече, че взима три аргумента: x, функция на два аргумента (поне), на която се подава z като първи и y(z) като втори аргумент. Ето какво представлява:

starling =
  fn (x) ->
    fn (y) ->
      fn (z) ->
        x.(z).(y.(z))
      end
    end
  end

Интересен факт:

starling.(kestrel).(kestrel)

е

id

Забележете че не можем да сравняваме функции. Можем да приемем, че две функции са идентични, ако те връщат еднакъв резултат за всички възможни стойности, които можем да им подадем. Това е трудно доказуемо. И все пак функциите id и starling.(kestrel).(kestrel) са функционално еквивалентни : за всяко y връщат едно и също - y.

Готови сме да си дефинираме първият тип данни.

Булеви стойности

Нека приемем следното:

bool_true  = fn (a) -> fn (b) -> a end end
bool_false = fn (a) -> fn (b) -> b end end

Или си дефинираме двете стойности в множеството от булеви стойности така:

1. TRUE е функция на два аргумента, която винаги връща първия.
2. FALSE е функция на два аргумента, която винаги връща втория.

Можем да дефинираме TRUE и FALSE и така:

bool_true  = kestrel
bool_false = starling.(kestrel)

Първото е ясно защо, а второто:

K(x, y)    = x
S(x, y, z) = x(z, y(z))

=>

S(K, a, b) = K(b, a(b)) = b === FALSE(a, b) = b

Имаме двете булеви стойности. Сега можем да си дефинираме най-простата операция над тях: NOT:

bool_not = fn (p) -> p.(bool_false).(bool_true) end

bool_not.(bool_true)
# bool_true.(bool_false).(bool_true) => bool_false

bool_not.(bool_false)
# bool_false.(bool_false).(bool_true) => bool_true

Лесно е и да се дефинира конюнкция. Нека помислим как:

1. Знаем, че ако подадем на bool_true двата му аргумента, винаги ще върне първия.
2. Знаем, че ако подадем на bool_false двата му аргумента, винаги ще върне втория.
3. Знаем, че AND трябва да е функция на два булеви аргумента; Ако първият е bool_false, AND връща bool_false, няма защо да пробва втория.
4. От (1) и (2) bool_true.(x).(bool_false) е x, а bool_false.(x).(bool_false) е bool_false.
5. От (3) и (4) можем да изведем AND като:

bool_and = fn (a) -> fn (b) -> a.(b).(bool_false) end end

bool_and.(bool_true).(bool_true)
# bool_true.(bool_true).(bool_false) => bool_true

bool_and.(bool_false).(bool_true)
# bool_false.(bool_true).(bool_false) => bool_false

bool_and.(bool_true).(bool_false)
# bool_true.(bool_false).(bool_false) => bool_false

bool_and.(bool_false).(bool_false)
# bool_false.(bool_false).(bool_false) => bool_false

По подобен начин можем да получим и OR:

bool_or = fn (a) -> fn (b) -> a.(bool_true).(b) end end

Имаме логическо отрицание, конюнкция и дизюнкция, а можем и да си дефинираме IF, или по скоро COND. Това е функция на три аргумента. Ако първият е TRUE връщаме втория, ако е FALSE - третия:

bool_cond = fn (a) -> fn (b) -> fn (c) -> a.(b).(c) end end end

Сега ще излезем малко от ограничението си да имаме само един тип данни - функции и ще напишем функция, която връща Elixir-ска булева стойност при подадена функционална булева стойност:

church_to_bool =
  fn (church_bool) ->
    church_bool.(true).(false)
  end

church_to_bool.(bool_true)
# true

church_to_bool.(bool_false)
# false

church_to_bool.(bool_and.(bool_false).(bool_true))
# false

Този начин на представяне на булевите стойности и на операциите над тях чрез функции се нарича булево енкодиране на Чърч и носи името на Alonzo Church, който пръв го е използвал в ламбда смятането. За ламбда смятането и за енкодингите на Чърч ще си говорим още. Да речем в следващата секция, в която ще си дефинираме числа.

Числа и аритметика

Подобно на начина, по който си дефинирахме булеви стойности, ще приемем следното:

1. Приемаме, че 0 е g(f, x) = x.
2. Приемаме, че 1 е g(f, x) = f(x).
3. Приемаме, че 2 е g(f, x) = f(f(x)).
4. Приемаме, че 3 е g(f, x) = f(f(f(x))).

Идеята е, че едно число е функция на два аргумента. При нула връщаме направо втория аргумент. При едно връщаме f(x) : извикваме първия аргумент със стойност втория. При две имаме f(f(x)). И така нататък, n е fⁿ(x).

Това в код изглежда така:

zero  = fn (f) -> fn (x) -> x end end
one   = fn (f) -> fn (x) -> x |> f.() end end
two   = fn (f) -> fn (x) -> x |> f.() |> f.() end end
three = fn (f) -> fn (x) -> x |> f.() |> f.() |> f.() end end

# И така нататък...

Първата ни задача е да си дефинираме функция is_zero(n), която приема число и връща bool_true, само ако числото е нула, а иначе - bool_false. Нека помислим:

1. Числата са функции на два аргумента.
2. Можем да подадем на число две стойности като аргументи и да изследваме поведението му.
3. Ако подадем стойностите g и h, и g бъде извикана един или повече пъти - числото не е нула.
4. От (3) следва, че g, трябва да е функция, която винаги връща bool_false, а h може да е просто bool_true. Ако подадем тези две функции на zero, ще получим втората, h - bool_true, а ако ги подадем на което и да е друго число, резултатът на първата ще бъде върнат - bool_false.

bool_true  = fn (a) -> fn (b) -> a end end
bool_false = fn (a) -> fn (b) -> b end end

is_zero =
  fn (n) ->
    n.(fn (_) -> bool_false end).(bool_true)
  end

is_zero.(zero) |> church_to_bool.()
# true

is_zero.(one) |> church_to_bool.()
# false

Следващата операция, която ще имплементираме е от едно число да получим следващото по големина. Това е функцията succ(n), която при нула, ще върне едно, при едно - две и така нататък. Тъй като числата са функции на два аргумента ако n е fⁿ(x), то n+1 е просто f(fⁿ(x)) или f(n(f, x)). Така и дефинираме succ - функция, която взима числото n, f и x и конструира ново число : f(n(f, x)):

succ =
  fn (n) ->
    fn (f) ->
      fn(x) ->
        f.(n.(f).(x))
      end
    end
  end

succ.(zero)
# f.(x) => one

succ.(two)
# f.( f.(f.(x)) ) => three

four = succ.(three)
five = succ.(four)

Събирането се дефинира по много подобен начин. Конструираме ново число от две числа - m и n, като m(f, n(f, x)) => m(f, fⁿ(x)) => f^m(fⁿ(x)) => f^{m + n}(x):

plus =
  fn (m) ->
    fn (n) ->
      fn (f) ->
        fn(x) ->
          m.(f).(n.(f).(x))
        end
      end
    end
  end

six = plus.(four).(two)

На този етап е добре да излезем за малко от ограниченията си и да напишем функция, която обръща нашите числа в числа от Elixir:

church_to_int =
  fn (n) ->
    n.(&(&1 + 1)).(0)
  end

six |> church_to_int.()
# 6

seven = succ.(six)
seven |> church_to_int.()
# 7

plus.(four).(five) |> church_to_int.()
# 9

twenty = plus.(plus.(four).(five)).(plus.(six).(five))
twenty |> church_to_int.()
# 20

Сега е доста по-лесно да дебъгваме какво получаваме като изпълняваме нашите операции върху числа.

Ще си дефинираме операция pred, която ни дава предното число. Важно е да отбележим, че pred.(zero) == zero.

За да намерим n+1, когато имаме n, ние обвиваме стойността на n ( fⁿ(x) ) в още едно f. За n-1, просто трябва да премахнем едно f от стойността. Това не е лесно. Идеята е да конструираме n като прилагаме f върху x n пъти, но на всяка стъпка помним предния резултат. Накрая ще върнем предния резултат за fⁿ(x), който е точно f^n-1(x).

Как да пазим на всяка стъпка както текущия, така и предния резултат? Ами с наредена двойка, разбира се! Но ние не знаем как да си дефинираме наредени двойки, използвайки само функции…

Точно затова е време да научим как да правим това. Приемаме, че дефинираме наредена двойка така:

pair =
  fn (a) ->
    fn (b) ->
      fn (c) -> c.(a).(b) end
    end
  end

Можем да дефинираме извличането на първия елемент и извличането на втория елемент така:

first =
  fn (p) ->
    g = fn (x) -> fn (y) -> x end end
    p.(g)
  end

second =
  fn (p) ->
    g = fn (x) -> fn (y) -> y end end
    p.(g)
  end

first.(pair.(one).(two)) |> church_to_int.()
# 1
second.(pair.(one).(two)) |> church_to_int.()
# 2

Идеята е проста - функцията, която създава наредена двойка очаква 3 аргумента, но ние я извикваме с два - елементите на двойката. Третия аргумент е функция на два аргумента, на която подаваме лявата стойност на двойката като първи аргумент и дясната - като втори. По този начин като подадем правилната функция, можем да прочетем правилния елемент. Интересен факт е, че функцията, която подаваме във first, за да вземем първия елемент на двойката е всъщност bool_true, а тази, която подаваме в second е bool_false. Една и съща функция може да има множество роли, в зависимост от типа данни с който работи/представлява. Спомнете си, че комбинаторът К е също bool_true.

Да се върнем към операцията pred. Нека първо да си дефинираме случая, в който подаваме нула:

zero_case = pair.(zero).(zero)

А това е случаят в който подаваме нещо различно от нула:

main_step =
  fn (p) ->
    pair.(second.(p)).(succ.(second.(p)))
  end

При подадена двойка от числа, правим нова двойка, с първи елемент вторият елемент на подадената двойка и втори, вторият елемент, увеличен с едно.

• Както знаем, самото число е функция на два аргумента, която прилага толкова копия на първия върху втория, колкото е числото.
• Функцията main_step очаква наредена двойка от числа и създава нова двойка от числа така : (n, m) -> (m, m+1).
• Ако започнем от наредена двойка нули : (0, 0) прилагайки main_step веднъж, ще получим (0, 1), два пъти : (1, 2), три пъти : (2, 3), n пъти : (n-1, n).

Сега ако вземем първия елемент на тази двойка ще получим n-1. Ако имаме числото n (функция на два аргумента) и го извикаме така n.(main_step).(zero_case), от дефиницията на числото n : main_step ще се приложи върху zero_case точно n пъти. Ако вземем първия елемент на получения резултат, получаваме точно n-1:

pred =
  fn (n) ->
    first.(n.(main_step).(zero_case))
  end

# И така:

pred.(zero) # =>
first.(zero.(main_step).(zero_case)) # =>
first.((fn (f) -> fn (x) -> x end end).(main_step).(zero_case)) # =>
first.(zero_case) # =>
zero

pred.(two) # =>
first.(two.(main_step).(zero_case)) # =>
first.((fn (f) -> fn (x) -> f.(f.(x)) end end).(main_step).(zero_case)) # =>
first.(main_step.(main_step.(zero_case))) # =>
first.(main_step.(pair.(second.(zero_case)).(succ.(second.(zero_case))))) # =>
first.(main_step.(pair.(zero).(one))) # =>
first.(pair.(second.(pair.(zero).(one))).(succ.(second.(pair.(zero).(one))))) # =>
first.(pair.(one).(succ.(one))) # =>
one

Сега можем да си дефинираме изваждане лесно. Ако искаме да извадим m от n, просто трябва да изпълним pred m пъти върху n:

minus =
  fn (n) ->
    fn(m) ->
      m.(pred).(n)
    end
  end

minus.(seven).(three) |> church_to_int.()
# 4

Отново използваме свойството на нашите числа, че са функции на два аргумента, които прилагат първия си върху втория си аргумент, толкова пъти, колкото е числовата им стойност.

Сега можем да си дефинираме и умножение:

mult =
  fn (n) ->
    fn (m) ->
      m.(plus.(n)).(zero)
    end
  end

mult_without_plus =
  fn (n) ->
    fn (m) ->
      fn (f) ->
        n.(m.(f))
      end
    end
  end

one_hundred = mult.(twenty).(five)
one_hundred |> church_to_int.()
# 100

Нека помислим, как бихме могли да сравняваме числа. Да си дефинираме операция, която проверява дали две числа са равни:

num_eq =
  fn (n) ->
    fn (m) ->
      # bool_and.(is_zero.(minus.(n).(m))).(is_zero.(minus.(m).(n)))
      bool_and.(is_zero.((n).(pred).(m))).(is_zero.((m).(pred).(n)))
    end
  end

num_eq.(one_hundred).(one_hundred) |> church_to_bool.()
# true

Използваме is_zero и изваждане. Ако извадим n от m и получим нула - числата са равни. Тъй като нямаме негативни числа ако извадим по-голямо число от по-малко, ще си получим нула (pred.(zero) == zero) и num_eq ще ги определи като равни. Именно затова ползваме bool_and за да извадим както n от m, така и m от n. Ако и при двете изваждания получим нула - със сигурност числата са равни.

Нека си дефинираме и по-голямо и по-малко:

num_gt =
  fn (n) ->
    fn (m) ->
      bool_and.(is_zero.((n).(pred).(m))).(bool_not.(is_zero.((m).(pred).(n))))
    end
  end

num_lt =
  fn (n) ->
    fn (m) ->
      bool_and.(is_zero.((m).(pred).(n))).(bool_not.(is_zero.((n).(pred).(m))))
    end
  end

num_gt.(two).(one) |> church_to_bool.()
# true
num_gt.(two).(three) |> church_to_bool.()
# false
num_lt.(two).(three) |> church_to_bool.()
# true
num_lt.(four).(three) |> church_to_bool.()
# false

Тъй като pred ще върне нула, ако при (n).(pred).(m), ако n е по-голямо или равно на m, просто трябва да проверим че не е нула при (m).(pred).(n). Така получаваме стриктно по-голямо. Подобно работи и стриктно по-малкото. Още по-лесно дефинираме не-стриктните проверки:

num_gt_eq =
  fn (n) ->
    fn (m) ->
      is_zero.((n).(pred).(m))
    end
  end

num_lt_eq =
  fn (n) ->
    fn (m) ->
      is_zero.((m).(pred).(n))
    end
  end

num_gt_eq.(two).(one) |> church_to_bool.()
# true
num_gt_eq.(two).(two) |> church_to_bool.()
# true
num_gt_eq.(two).(three) |> church_to_bool.()
# false
num_lt_eq.(two).(three) |> church_to_bool.()
# true
num_lt_eq.(three).(three) |> church_to_bool.()
# true
num_lt_eq.(four).(three) |> church_to_bool.()
# false

Вече можем да сравняваме нашите числа, да ги вадим, събираме и умножаваме. Да дефинираме изваждането беше по-трудоемко от другите операции, трябваше да използваме наредени двойки за да успеем. Дойде ред да дефинираме делене на числа. Задачата ни няма да е лека, защото идеята при делението е нещо такова:

a / b =
  if a >= b do
    1 + (a - b) / b
  else
    0
  end

Имаме всички операции от горната формула, но операцията ‘делене’ се използва рекурсивно. Разбира се, можем да използваме Y комбинатора:

y = fn (h) ->
  (fn (f) ->
    f.(f)
  end).(fn (g) ->
    h.(fn (x) -> g.(g).(x) end)
  end)
end

Сега можем да си дефинираме divide функция така:

divide =
  fn (n) ->
    fn (m) ->
      y.(fn (divide1) ->
        fn (current) ->
          num_gt_eq.(current).(m).(
            fn (_) -> succ.(divide1.(minus.(current).(m))) end
          ).(
            fn (_) -> zero end
          ).(zero)
        end
      end).(n)
    end
  end


divide.(twenty).(two) |> church_to_int.()
# 10
divide.(twenty).(three) |> church_to_int.()
# 6
divide.(twenty).(four) |> church_to_int.()
# 5

Описахме същото като псевдокода за деление по-горе : divide приема два аргумента - числата n и m и връща цялата част от резултата при делението n / m. Подаваме n за начален current. Ако current е по голям или равен на m добавяме 1 към резултата от извикването на divide със current - m и m. Ако не - нула. Всичко това е имплементирано само с функции.

Функцията за връщане на остатък при делене е много подобна:

remainder =
  fn (n) ->
    fn (m) ->
      y.(fn (remainder1) ->
        fn (current) ->
          num_gt_eq.(current).(m).(
            fn (_) -> remainder1.(minus.(current).(m)) end
          ).(
            fn (_) -> current end
          ).(zero)
        end
      end).(n)
    end
  end


remainder.(twenty).(two) |> church_to_int.()
# 0
remainder.(twenty).(three) |> church_to_int.()
# 2
remainder.(twenty).(seven) |> church_to_int.()
# 6

Накрая просто връщаме current, вместо броя на деленията.

Нека сега дефинираме вдигане на степен:

power =
  fn (n) ->
    fn (m) ->
      m.(n)
    end
  end

power.(two).(three) |> church_to_int.()
# 8

Тази операция е доста по-проста от предните две и ви я оставяме да си я обясните сами!

Нека да завършим с нещо забавно. В предната публикация се опитахме да дефинираме факториел само с анонимни функции и числата от Elixir. Сега ще си го дефинираме само чрез анонимни функции и нищо друго. Имаме всички операции нужни за факториел, както и рекурсията, чрез Y комбинатора. Нека си припомним дефиницията до която стигнахме:

proto_factorial = fn g ->
  fn
    0 -> 1
    n -> n * g.(n - 1)
  end
end

factorial = y.(proto_factorial)

Нека да напишем това с нашите операции над нашия тип числа:

proto_factorial = fn g ->
  fn (n) ->
    is_zero.(n).(fn (_) -> one end).(
      fn (_) ->
        mult.(n).(g.(pred.(n)))
      end
    ).(zero)
  end
end

factorial = y.(proto_factorial)

factorial.(five) |> church_to_int.()
# 120

Ако използвате тази функция даже за факториел от десет, ще почакате. Както и ако делите големи числа. Тези числа са доста не-оптимизирани и служат да докажем, че използвайки само анонимни функции на един аргумент, можем да си дефинираме числа и операциите с тях. Разбира се анонимните функции на един аргумент са това, което ни дава ламбда смятането. Нетипизираното ламбда смятане е един от най-простите езици за програмиране, с който на теория можете да напишете всяка програма, която можете да напишете и на друг език, например Elixir. И това е доста интересно. Ламбда смятането е в основата на модерното функционално програмиране и е много важна теория, с която ние ще се занимаваме и занапред. Числата, които дефинирахме са известни като ‘числа на Чърч’. Имат и версии поддържащи отрицателни числа.

Интересни книжки по темата

Моят съмишленик в любовта към функционалното програмиране, Филип ми препоръча да слагам връзки към интересни книжки по темите по които пиша. Затова добавям тази секция към публикацията и ще го правя занапред.

Ако темата ви беше интересна, разгледайте следните книги:

• To Mock a Mockingbird - Заигравка с комбинатори. От тази книжка идват имената на птици при комбинаторите.
• Types and Programming Languages - Теми от тази книга ще разглеждаме и занапред. Говори се за типизирани езици, но има глава и за нетипизираното ламбда смятане.
• Understanding Computation - Съдържа подобни упражнения на тези, с които се занимавахме тук, на Ruby.

Код

• Кодът от тази публикация можете да намерите тук.
• Markdown source-ът на тази публикация можете на намерите тук. Ако искате да добавите/поправите нещо, pull request-и ще бъдат посрещнати с радост!