На всякий случай разобью на части и начну с азов, что бы можно было пропустить.Есть такая штука -- алгоритм. Все знают, что это такое, но рассказать почему-то стесняются.
Однажды Алан Тьюринг предложил: представьте себе бесконечную ленту, разбитую на ячейки. В каждой ячейке записана некая буква. По ленте движется головка, читает их и понимает, куда дальше двигаться. Вот эта штука способна исполнить любой алгоритм. Если язык программирования (ЯП) ей эквивалентен, его называют тьюринг-полным. Если программа на ЯП представляет набор команд типа "открой файл", "найди пятый символ", "удали", такая программа считается императивной. Писать её просто, но она соответствует той бесконечной ленте, а потому целиком укладывается только в головах тьюрингов. Нет способа строго доказать, что произвольная программа не содержит ошибок. В результате случается то, о чём так любит писать тутошний Фрактал.
Алонзо Чёрч посмотрел на это дело и говорит: тысячи лет люди умеют доказывать теорему Пифагора. Если записать алгоритм математическими функциями, мы сможем доказать её корректность. И придумал лямбда-исчисление, из которого выросли функциональные языки (ФЯ). Беда в том, что его понимают от силы 1000 человек на Шарике и ещё 1000000 умеют важно надувать щёки по этому поводу. В результате программы на ФЯ почти не содержат ошибок, поскольку их почти нет.
Андрей Андреевич Марков (младший) изучил опыт коллег и заметил, что если требуется заменить "а" на "б", достаточно представить себе абстрактный исполнитель, который исполнит "а" -> "б". Последовательность подобных замен может представить любой алгоритм. Это называется нормальный алгоритм Маркова (НАМ), но распространения, как нас учит тезис Чёрча-Тьюринга, не получило. Правда, в некоторых языках встречаются конструкции:
match 4 with
4 -> 5
| 5 -> 6;;
