Войти
| Парадигма | функциональная, логика, нестрогая, модульный |
|---|---|
| Разработан | Майкл Ханус, Серджио Антой и др. |
| Дисциплина набора текста | статический, сильный, выведенный |
| OS | портативный |
| Веб-сайт | Curry |
| Основные реализации | |
| PAKCS (с Prolog в качестве цели), mcc (с C в качестве цели), KiCS2 (с Haskell в качестве цели) | |
| Под влиянием | |
| Haskell и Prolog | |
Curry является экспериментальным языком программирования функциональной логики, основанным на языке Haskell. Он объединяет элементы функционального и логического программирования, включая программирование в ограничениях интеграцию.
Это почти надмножество Haskell, в котором отсутствует поддержка в основном для перегрузки с использованием классов типов, которые некоторые реализации в любом случае предоставляют как языковые расширения, такие как Münster Curry Compiler.
Функциональная программа - это набор функций, определяемых уравнениями или правилами. Функциональное вычисление состоит из замены подвыражений на равные (в отношении определений функций) подвыражения до тех пор, пока больше не станут возможными замены (или сокращения) и не будет получено значение или нормальная форма. Например, рассмотрим функцию double, определенную как
double x = x + x
Выражение «double 1» заменяется на 1 + 1. Последний может быть заменен на 2, если мы интерпретируем оператор «+» как определенный бесконечным набором уравнений, например, 1 + 1 = 2, 1 + 2 = 3. и т. д. Аналогичным образом можно вычислить вложенные выражения (где подвыражения, которые нужно заменить, заключены в кавычки):
'double (1 + 2)' → '(1 + 2)' + (1+ 2) → 3 + '(1 + 2)' → '3 + 3' → 6
Существует также другой порядок вычисления, если мы заменим аргументы операторов справа налево:
'double (1 + 2)' → (1 + 2) + '(1 + 2)' → '(1 + 2)' + 3 → '3 + 3' → 6
В данном случае, оба вывода приводят к одному и тому же результату - свойству, известному как слияние. Это следует из фундаментального свойства чистых функциональных языков, называемого ссылочной прозрачностью : значение вычисленного результата не зависит от порядка или времени оценки из-за отсутствия побочных эффектов. Это упрощает рассмотрение и сопровождение чисто функциональных программ.
Как и многие функциональные языки, такие как Haskell, Curry поддерживает определение алгебраических типов данных путем перечисления их конструкторов. Например, тип логических значений состоит из конструкторов True и False, которые объявляются следующим образом:
data Bool = True | False
Функции на логических значениях могут быть определены путем сопоставления с образцом, т. Е. Путем предоставления нескольких уравнений для разных значений аргументов:
not True = False not False = True
Принцип замены равных на равные все еще действителен при условии что фактические аргументы имеют требуемую форму, например:
not '(not False)' → 'not True' → False
Более сложные структуры данных могут быть получены с помощью рекурсивных данных типы. Например, список элементов, где тип элементов является произвольным (обозначается переменной типа a), представляет собой либо пустой список «», либо непустой список «x: xs. ”Состоящий из первого элемента x и списка xs:
data List a = | a: Список a
Тип «Список a» обычно записывается как [a] и конечные списки x1 : x2 :... : xn : записываются как [x1, x2,..., xn ]. Мы можем определять операции с рекурсивными типами с помощью индуктивных определений, где сопоставление с образцом поддерживает удобное разделение различных случаев. Например, операция конкатенации «++» в полиморфных списках может быть определена следующим образом (необязательное объявление типа в первой строке указывает, что «++» принимает два списка в качестве входных и создает выходной список, где все элементы списка имеют один и тот же неопределенный тип):
(++) :: [a] ->[a] ->[a] ++ ys = ys (x: xs) ++ ys = x: xs ++ ys
Помимо приложения для различных задач программирования, операция «++» также полезна для определения поведения других функций в списках. Например, поведение функции last, которая возвращает последний элемент списка, может быть определено следующим образом: для всех списков xs и элементов e, last xs = e if ∃ys : ys + + [e ] = хз.
На основе этой спецификации можно определить функцию, которая удовлетворяет этой спецификации, используя функции логического программирования. Подобно языкам логики, языки функциональной логики обеспечивают поиск решений для экзистенциально количественно определенных переменных. В отличие от языков чистой логики, они поддерживают решение уравнений над вложенными функциональными выражениями, так что уравнение типа ys ++ [e ] = [1,2,3] решается путем создания экземпляра ys в list [1,2] и e до значения 3. В Curry последнюю операцию можно определить следующим образом:
last xs | ys ++ [e] =: = xs = e где ys, e free
Здесь символ «=: =» используется для эквациональных ограничений, чтобы обеспечить синтаксическое отличие от определяющих уравнений. Точно так же дополнительные переменные (т. Е. Переменные, не встречающиеся в левой части определяющего уравнения) явно объявляются с помощью «where... free», чтобы предоставить некоторые возможности для обнаружения ошибок, вызванных опечатками. Условное уравнение вида l | c = r применимо для редукции, если его условие c было решено. В отличие от чисто функциональных языков, где условия оцениваются только до логического значения, языки функциональной логики поддерживают решение условий путем угадывания значений неизвестных в условии. Сужение, как описано в следующем разделе, используется для решения такого рода условий.
Сужение - это механизм, посредством которого переменная привязана к значению, выбранному из числа альтернатив, налагаемых ограничениями. Каждое возможное значение проверяется в определенном порядке, при этом в каждом случае вызывается остальная часть программы для определения действительности привязки. Сужение - это расширение логического программирования, поскольку оно выполняет аналогичный поиск, но на самом деле может генерировать значения как часть поиска, а не просто ограничиваться их тестированием.
Сужение полезно, потому что оно позволяет рассматривать функцию как отношение: ее значение может вычисляться «в обоих направлениях». Примеры Карри из предыдущего раздела иллюстрируют это.
Как отмечалось в предыдущем разделе, сужение можно рассматривать как сокращение на графе терминов программы, и часто существует множество различных способов (стратегий) для сокращения данного графа терминов. Antoy et al. в 1990-х годах было доказано, что конкретная стратегия сужения, необходимая для сужения, является оптимальной в смысле выполнения ряда сокращений, чтобы получить «нормальную форму», соответствующую решению, которое является минимальным среди разумных и полных стратегий. Необходимое сужение соответствует ленивой стратегии, в отличие от стратегии SLD-разрешения в Prolog.
Правило, определяющее, последнее показанное выше, выражает факт что фактический аргумент должен соответствовать результату сужения выражения ys ++ [e]. Карри может выразить это свойство следующим образом, более кратко:
last (ys ++ [e]) = e
Haskell не допускает такого объявления, поскольку шаблон в левой части содержит определенную функцию (++). Такой узор еще называют функциональным. Функциональные шаблоны включаются объединенными функциональными и логическими функциями Curry и поддерживают краткие определения задач, требующих глубокого сопоставления с образцом в иерархических структурах данных.
Поскольку Curry может решать уравнения, содержащие вызовы функций с неизвестными значениями, его механизм выполнения основан на недетерминированных вычислениях, как и в логическом программировании. Этот механизм поддерживает также определение недетерминированных операций, то есть операций, которые обеспечивают более одного результата для заданного ввода. Архетипом недетерминированных операций является предопределенная инфиксная операция ?, Называемая оператором выбора, которая возвращает один из своих аргументов. Этот оператор определяется следующими правилами:
x? у = х х? y = y
Таким образом, оценка выражения 0? 1 возвращает 0, а также 1. Вычисления с недетерминированными операциями и вычисления со свободными переменными путем сужения имеют одинаковую выразительную силу.
Правила, определяющие ? показать важную особенность Карри: все правила проверяются, чтобы оценить некоторую операцию. Следовательно, можно определить с помощью
insert x ys = x: ys insert x (y: ys) = y: insert x ys
операцию для вставки элемента в список в неопределенной позиции так, чтобы операция perm, определенный как
perm = perm (x: xs) = insert x (perm xs)
возвращает любую перестановку данного входного списка.
Из-за отсутствия побочных эффектов программа функциональной логики может выполняться с различными стратегиями. Для оценки выражений Карри использует вариант необходимой стратегии сужения, который сочетает ленивое вычисление с недетерминированными стратегиями поиска. В отличие от Prolog, в котором для поиска решений используется отслеживание с возвратом, Curry не исправляет конкретную стратегию поиска. Следовательно, существуют реализации Curry, такие как KiCS2, где пользователь может легко выбрать стратегию поиска, например поиск в глубину (с возвратом), поиск в ширину, итеративное углубление или параллельный поиск.
