Карри (язык программирования) - Curry (programming language)

Эта статья о языке программирования Curry (названном в честь математика и логика). Для математиков и логиков см. Хаскелл Карри. Для техники информатики см. Каррирование.
Карри
Парадигмафункциональный, логика, нестрогая, модульная
РазработаноМайкл Ханус, Серджио Антой и др.
Печатная дисциплинастатический, сильный, предполагаемый
Операционные системыпортативный
Интернет сайтКарри
Основной реализации
PAKCS (с Пролог как цель), mcc (с C как цель), KiCS2 (с Haskell как цель)
Под влиянием
Haskell и Пролог

Карри[1] экспериментальный функционально-логическое программирование язык,[2] на основе Haskell язык. Он объединяет элементы функционального и логического программирования, в том числе программирование в ограничениях интеграция.

Это почти надмножество Haskell, в котором отсутствует поддержка в основном для перегрузки с использованием типовые классы, который некоторые реализации в любом случае предоставляют как расширение языка, например Münster Curry Compiler.[3]

Основы функционально-логического программирования

Базовые концепты

Функциональная программа - это набор функций, определяемых уравнениями или правилами. Функциональное вычисление состоит из замены подвыражений равными (в отношении определений функций) подвыражениями до тех пор, пока больше не перестанут быть возможными замены (или сокращения) и не будет получено значение или нормальная форма. Например, рассмотрим функцию double, определенную как

двойной х = х + х

Выражение "двойной 1»Заменяется на 1+1. Последнее можно заменить на 2 если интерпретировать оператор «+”, Который будет определяться бесконечной системой уравнений, например, 1+1 = 2, 1+2 = 3и т. д. Аналогичным образом можно вычислить вложенные выражения (где заменяемые подвыражения заключены в кавычки):

'двойной (1 + 2)' → '(1 + 2)' + (1 + 2) → 3 + '(1 + 2)' → '3 + 3' → 6

Также существует другой порядок вычисления, если мы заменим аргументы операторов справа налево:

'двойной (1 + 2)' → (1 + 2) + '(1 + 2)' → '(1 + 2)' + 3 → '3 + 3' → 6

В этом случае оба вывода приводят к одному и тому же результату - свойству, известному как слияние. Это следует из фундаментального свойства чистых функциональных языков, называемого ссылочная прозрачность: значение вычисленного результата не зависит от порядка или времени оценки из-за отсутствия побочных эффектов. Это упрощает рассмотрение и сопровождение чисто функциональных программ.

Столько функциональных языков, как Haskell делать, Карри поддерживает определение алгебраические типы данных перечислив их конструкторы. Например, тип логических значений состоит из конструкторов Истинный и Ложь которые объявлены следующим образом:

 данные Bool = Истинный | Ложь

Функции на логических значениях могут быть определены путем сопоставления с образцом, то есть путем предоставления нескольких уравнений для разных значений аргументов:

 нет Истинный = Ложь нет Ложь = Истинный

Принцип замены равных на равные по-прежнему действует при условии, что фактические аргументы имеют требуемую форму, например: 

not '(not False)' → 'not True' → False

Более сложные структуры данных могут быть получены с помощью рекурсивные типы данных. Например, список элементов, где тип элементов произвольный (обозначается переменной типа а), либо пустой список «[]"Или непустой список"х: хз”Состоящий из первого элемента Икс и список хз: 

 данные Список а = [] | а : Список а

Тип «Перечислите»Обычно записывается как [а] и конечные списки x1:x2:...:xn:[] записываются как [x1,x2,...,xn]. Мы можем определять операции с рекурсивными типами с помощью индуктивных определений, в которых сопоставление с образцом поддерживает удобное разделение различных случаев. Например, операция конкатенации «++»В полиморфных списках можно определить следующим образом (необязательное объявление типа в первой строке указывает, что«++”Принимает в качестве входных данных два списка и создает выходной список, в котором все элементы списка имеют один и тот же неуказанный тип):

 (++) :: [а] -> [а] -> [а]  [] ++ ys = ys  (Икс:хз) ++ ys = Икс : хз++ys

Помимо применения для различных задач программирования, операция «++»Также полезен для указания поведения других функций в списках. Например, поведение функции last, которая возвращает последний элемент списка, может быть определено следующим образом: для всех списков xs и элементов e, последний xs = e, если ∃ys:ys++[е] = хз.

На основе этой спецификации можно определить функцию, которая удовлетворяет этой спецификации, используя возможности логического программирования. Подобно языкам логики, языки функциональной логики обеспечивают поиск решений для экзистенциально количественно определенных переменных. В отличие от языков чистой логики, они поддерживают решение уравнений по вложенным функциональным выражениям, так что уравнение типа ys++[е] = [1,2,3] решается путем создания экземпляра ys в списке [1,2] и e к значению 3. В Curry можно определить последнюю операцию следующим образом:

 последний хз | ys++[е] =:= хз = е куда ys,е свободный

Здесь символ «=:=”Используется для эквациональных ограничений, чтобы обеспечить синтаксическое отличие от определяющих уравнений. Точно так же дополнительные переменные (т. Е. Переменные, не встречающиеся в левой части определяющего уравнения) явно объявляются как «где ... бесплатно”, Чтобы предоставить некоторые возможности для обнаружения ошибок, вызванных опечатками. Условное уравнение вида l | c = r применимо для редукции, если его условие c было решено. В отличие от чисто функциональных языков, где условия оцениваются только до логического значения, языки функциональной логики поддерживают решение условий путем угадывания значений неизвестных в условии. Сужение, как описано в следующем разделе, используется для решения такого рода условий.

Сужение

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

Сужение полезно, потому что оно позволяет рассматривать функцию как отношение: ее значение может быть вычислено «в обоих направлениях». Примеры Карри из предыдущего раздела иллюстрируют это.

Как отмечалось в предыдущем разделе, сужение можно рассматривать как сокращение на графике терминов программы, и часто существует много разных способов (стратегии), чтобы сократить данный граф терминов. Antoy et al.[4] доказали в 1990-х, что конкретная стратегия сужения, необходимо сужение, является оптимальным в смысле выполнения ряда редукций для перехода к «нормальной форме», соответствующей решению, которое является минимальным среди разумных и полных стратегий. Необходимое сужение соответствует ленивой стратегии, в отличие от SLD-разрешение стратегия Пролог.

Функциональные шаблоны

Правило, определяющее последний показанный выше выражает тот факт, что фактический аргумент должен соответствовать результату сужения выражения ys ++ [e]. Карри может выразить это свойство более кратко:

 последний (ys++[е]) = е

Haskell не допускает такого объявления, так как образец в левой части содержит определенную функцию (++). Такой узор еще называют функциональный образец.[5] Функциональные шаблоны становятся возможными благодаря комбинированным функциональным и логическим возможностям Curry и поддерживают краткие определения задач, требующих глубокого сопоставления с образцом в иерархических структурах данных.

Недетерминизм

Поскольку Curry может решать уравнения, содержащие вызовы функций с неизвестными значениями, механизм его выполнения основан на недетерминированных вычислениях, как и в логическом программировании. Этот механизм поддерживает также определение недетерминированные операции, то есть операции, которые дают более одного результата для данного ввода. Архетип недетерминированных операций - это предопределенная инфиксная операция. ?, называется выбор оператор, который возвращает один из своих аргументов. Этот оператор определяется следующими правилами:

 Икс ? у = х х? у = у

Таким образом, оценка выражения 0 ? 1 возвращается 0 а также 1. Вычисления с недетерминированными операциями и вычисления со свободными переменными путем сужения имеют одинаковую выразительную силу.[6]

Правила, определяющие ? показать важную особенность Карри: все правила проверяются, чтобы оценить некоторую операцию. Следовательно, можно определить как

 вставлять Икс ys     = Икс : ys вставлять Икс (у:ys) = у : вставлять Икс ys

операция для вставки элемента в список в неопределенной позиции, чтобы операция пермь определяется

 пермь []     = [] пермь (Икс:хз) = вставлять Икс (пермь хз)

возвращает любую перестановку данного входного списка.

Стратегии

Из-за отсутствия побочных эффектов программа функциональной логики может выполняться с разными стратегиями. Для оценки выражений Карри использует вариант необходимо сужение стратегия, сочетающая ленивая оценка с недетерминированными стратегиями поиска. В отличие от Prolog, в котором для поиска решений используется отслеживание с возвратом, Curry не исправляет конкретную стратегию поиска. Следовательно, есть реализации Карри, например KiCS2, где пользователь может легко выбрать стратегию поиска, например поиск в глубину (возврат), поиск в ширину, итеративное углубление или параллельный поиск.

Рекомендации

  1. ^ Майкл Ханус (ред.). «Карри: действительно интегрированный язык функциональной логики».CS1 maint: дополнительный текст: список авторов (связь)
  2. ^ Серджио Антой и Майкл Ханус (2010). «Функционально-логическое программирование». Коммуникации ACM. ACM. 53 (4): 74–85. Дои:10.1145/1721654.1721675.
  3. ^ Компилятор Münster Curry
  4. ^ Серджио Антой, Рашид Эшахед и Майкл Ханус (2007). «Необходимая стратегия сужения». Журнал ACM. ACM. 47 (4): 776–822. Дои:10.1145/347476.347484. ISSN  0004-5411.
  5. ^ Антой Серджио, Ханус Майкл (2006). «Декларативное программирование с использованием шаблонов функций». Конспект лекций по информатике. 3901: 6–22. Дои:10.1007/11680093_2. ISBN  978-3-540-32654-0.
  6. ^ Антой Серджио, Ханус Майкл (2006). «Перекрывающиеся правила и логические переменные в программах функциональной логики». Конспект лекций по информатике. 4079: 87–101. Дои:10.1007/11799573_9. ISBN  978-3-540-36635-5.

внешняя ссылка