Выразительность.
В Харрисоне и Филде (одна из первых книг про функциональное программирование на русском) рассказывается об интересном факте. Я по памяти, поэтому могу наврать, но не думаю, что сильно ошибусь.
Комбинаторы SKI могут выразить любое лямбда-выражение, есть даже правила преобразования туда и обратно. Беда заключается в том, что длина выражения в базисе SKI будет пропорциональна экспоненте от длины выражения в нотации лямбда-исчисления, O(eN).
Пишем 2+2, получаем N букв SKI. Пишем 2+1+1, получаем 2N букв. Пишем 1+1+1+1, 4N букв.
С этим пытались бороться, добавляя комбинаторы и базис комбинаторов SKIBC-и-ещё-какой-то-я-забыл-какой даёт всего лишь квадратичное увеличение длины.
А суперкомбинаторы, вытягиваемые из самой программы, позволяют записать программу в линейное (от длины программы) количество "букв".
В принципе, SKI, SKIBC+что-то-ещё и суперкомбинаторы можно считать языками программирования с разной выразительной силой.
Надеюсь, это показывает, насколько важной может быть возможность языка. Пусть пример достаточно искусственен (и я могу плохо помнить), но зато он нагляден и бьёт по мозгам получаемыми размерами программ: O(eN), O(N2) и O(N).
Да даже последних двух хватит, если я с первой оценкой неправ.
PS
Я же пытался писать на Эпиграме. Так вот, первое, на что я наткнулся, это на квадратичную сложность программы: для типа data Char = CA | CB ... CZ я пытался выразить равенство, а поскольку Эпиграм разворачивает сравнение с образцом в тотальное сравнение, то для eq a b я получил сперва набор всех ветвей для параметра a, а потом в каждой из них должен было написать результат сравнения со свеми результатами b. Хотя всем известно, что равенство может быть записано линейно от количества конструкторов.
Комбинаторы SKI могут выразить любое лямбда-выражение, есть даже правила преобразования туда и обратно. Беда заключается в том, что длина выражения в базисе SKI будет пропорциональна экспоненте от длины выражения в нотации лямбда-исчисления, O(eN).
Пишем 2+2, получаем N букв SKI. Пишем 2+1+1, получаем 2N букв. Пишем 1+1+1+1, 4N букв.
С этим пытались бороться, добавляя комбинаторы и базис комбинаторов SKIBC-и-ещё-какой-то-я-забыл-какой даёт всего лишь квадратичное увеличение длины.
А суперкомбинаторы, вытягиваемые из самой программы, позволяют записать программу в линейное (от длины программы) количество "букв".
В принципе, SKI, SKIBC+что-то-ещё и суперкомбинаторы можно считать языками программирования с разной выразительной силой.
Надеюсь, это показывает, насколько важной может быть возможность языка. Пусть пример достаточно искусственен (и я могу плохо помнить), но зато он нагляден и бьёт по мозгам получаемыми размерами программ: O(eN), O(N2) и O(N).
Да даже последних двух хватит, если я с первой оценкой неправ.
PS
Я же пытался писать на Эпиграме. Так вот, первое, на что я наткнулся, это на квадратичную сложность программы: для типа data Char = CA | CB ... CZ я пытался выразить равенство, а поскольку Эпиграм разворачивает сравнение с образцом в тотальное сравнение, то для eq a b я получил сперва набор всех ветвей для параметра a, а потом в каждой из них должен было написать результат сравнения со свеми результатами b. Хотя всем известно, что равенство может быть записано линейно от количества конструкторов.