OCaml ( / oʊ ˈ k æ m əl / oh- KAM -əl , ранее Objective Caml ) — это высокоуровневый многопарадигмальный язык программирования общего назначения , который расширяет диалект Caml ML объектно -ориентированными функциями. OCaml был создан в 1996 году Ксавье Леруа , Жеромом Вуйоном, Дэмиеном Долигезом , Дидье Реми, Аскандером Суаресом и другими.
Набор инструментов OCaml включает в себя интерактивный интерпретатор верхнего уровня , компилятор байт-кода , оптимизирующий компилятор собственного кода , обратимый отладчик и менеджер пакетов (OPAM). OCaml изначально был разработан в контексте автоматического доказательства теорем и используется в программном обеспечении для статического анализа и формальных методов . Помимо этих областей, он нашел применение в системном программировании , веб-разработке и конкретных финансовых утилитах, а также в других областях приложений.
Аббревиатура CAML изначально обозначала категориальный абстрактный машинный язык , но в OCaml эта абстрактная машина отсутствует . [5] OCaml — это бесплатный программный проект с открытым исходным кодом, управляемый и поддерживаемый Французским институтом исследований в области компьютерных наук и автоматизации (Inria). В начале 2000-х годов элементы OCaml были приняты во многих языках, особенно в F# и Scala .
Языки, производные от машинного обучения , наиболее известны своими системами статических типов и компиляторами , определяющими типы . OCaml объединяет функциональное , императивное и объектно-ориентированное программирование в рамках системы типов, подобной ML. Таким образом, для использования OCaml программистам не обязательно хорошо разбираться в чисто функциональной парадигме языка.
Требуя от программиста работать в рамках ограничений своей системы статических типов, OCaml устраняет многие проблемы времени выполнения , связанные с типами, связанные с динамически типизированными языками. Кроме того, компилятор OCaml, определяющий тип, значительно снижает потребность в аннотациях типов вручную, которые требуются в большинстве статически типизированных языков. Например, типы данных переменных и сигнатуры функций обычно не нужно объявлять явно, как это делается в таких языках, как Java и C# , поскольку их можно вывести из операторов и других функций, которые применяются к переменным и другим значениям. в коде. Эффективное использование системы типов OCaml может потребовать от программиста некоторой сноровки, но эта дисциплина вознаграждается надежным и высокопроизводительным программным обеспечением.
OCaml, пожалуй, больше всего отличается от других языков, возникших в академических кругах, своим упором на производительность. Его система статических типов предотвращает несоответствие типов во время выполнения и, таким образом, исключает проверки типов и безопасности во время выполнения, которые нагружают производительность динамически типизированных языков, в то же время гарантируя безопасность во время выполнения, за исключением случаев, когда проверка границ массива отключена или когда используются некоторые небезопасные по типу функции, такие как сериализация . . Они настолько редки, что избежать их на практике вполне возможно.
Помимо накладных расходов на проверку типов, функциональные языки программирования, как правило, сложно скомпилировать в эффективный код машинного языка из-за таких проблем, как проблема funarg . Наряду со стандартными оптимизациями циклов, регистров и инструкций, оптимизирующий компилятор OCaml использует методы статического анализа программы для оптимизации упаковки значений и распределения замыканий , помогая максимизировать производительность результирующего кода, даже если в нем широко используются конструкции функционального программирования.
Ксавье Лерой заявил, что «OCaml обеспечивает как минимум 50% производительности приличного компилятора C» [6] , хотя прямое сравнение невозможно. Некоторые функции стандартной библиотеки OCaml реализованы с использованием более быстрых алгоритмов, чем эквивалентные функции в стандартных библиотеках других языков. Например, реализация объединения множеств в стандартной библиотеке OCaml теоретически асимптотически быстрее, чем эквивалентная функция в стандартных библиотеках императивных языков (например, C++, Java), поскольку реализация OCaml может использовать неизменяемость множеств для повторного использования частей. входные данные задаются на выходе (см. постоянную структуру данных ).
В период с 1970-х по 1980-е годы Робин Милнер , британский ученый-компьютерщик и лауреат премии Тьюринга , работал в Лаборатории основ компьютерных наук Эдинбургского университета . [7] [8] Милнер и другие работали над средствами доказательства теорем , которые исторически были разработаны в таких языках, как Лисп . Милнер неоднократно сталкивался с проблемой, что лица, доказывающие теоремы, пытались утверждать, что доказательство действительно , путем объединения недоказательств. [8] В результате он продолжил разработку метаязыка для своей «Логики для вычислимых функций» , языка, который позволял автору создавать действительные доказательства только с помощью своей системы полиморфных типов. [9] ML был превращен в компилятор , чтобы упростить использование LCF на разных машинах, а к 1980-м годам превратился в полноценную собственную систему. [9] ML в конечном итоге послужил основой для создания OCaml.
В начале 1980-х годов произошли некоторые события, которые побудили команду Formel из INRIA заинтересоваться языком ML. Лука Карделли , профессор-исследователь Оксфордского университета , использовал свою Функциональную абстрактную машину для разработки более быстрой реализации ML, а Робин Милнер предложил новое определение ML, чтобы избежать расхождений между различными реализациями. Одновременно Пьер-Луи Кюрьен, старший научный сотрудник Парижского университета Дидро , разработал исчисление категориальных комбинаторов и связал его с лямбда-исчислением , что привело к определению категориальной абстрактной машины (КАМ). Ги Кузино, исследователь из Парижского университета Дидро, признал, что это можно применить в качестве метода компиляции для машинного обучения. [10]
Первоначально Caml был спроектирован и разработан командой Formel компании INRIA под руководством Жерара Юэ . Первая реализация Caml была создана в 1987 году и развивалась до 1992 года. Хотя ее возглавляли Аскандер Суарес, Пьер Вайс и Мишель Мони продолжили разработку после его ухода в 1988 году. [10]
Цитируется Ги Кузино, который вспоминает, что его опыт реализации языков программирования изначально был очень ограниченным и что существовало множество недостатков, за которые он несет ответственность. Несмотря на это, он считает, что «Аскандер, Пьер и Мишель проделали неплохую работу». [10]
Между 1990 и 1991 годами Ксавье Лерой разработал новую реализацию Caml на основе интерпретатора байт-кода , написанного на C. В дополнение к этому Дэмиен Долигез написал для этой реализации систему управления памятью, также известную как последовательный сборщик мусора . [9] Эта новая реализация, известная как Caml Light , заменила старую реализацию Caml и работала на небольших настольных компьютерах. [10] В последующие годы появились такие библиотеки, как инструменты синтаксической манипуляции Мишеля Мони, которые способствовали использованию Caml в образовательных и исследовательских группах. [9]
В 1995 году Ксавье Лерой выпустил Caml Special Light, который представлял собой улучшенную версию Caml. [10] К компилятору байт-кода был добавлен оптимизирующий компилятор собственного кода, который значительно увеличил производительность до уровня, сравнимого с уровнями основных языков, таких как C++ . [9] [10] Кроме того, Лерой разработал систему модулей высокого уровня, вдохновленную системой модулей Standard ML, которая предоставляла мощные возможности для абстракции и параметризации и упрощала создание крупномасштабных программ. [9]
Дидье Реми и Жером Вуйон разработали выразительную систему типов для объектов и классов, которая была интегрирована в Caml Special Light. Это привело к появлению языка Objective Caml, впервые выпущенного в 1996 году и впоследствии переименованного в OCaml в 2011 году. Эта объектная система, в частности, поддерживала многие распространенные объектно-ориентированные идиомы статически типобезопасным способом, в то время как те же идиомы вызывали несостоятельность или требовали проверки времени выполнения на таких языках, как C++ или Java . В 2000 году Жак Гарриг расширил Objective Caml множеством новых функций, таких как полиморфные методы, варианты, а также помеченные и необязательные аргументы. [9] [10]
В течение последних двух десятилетий постепенно добавлялись языковые улучшения для поддержки растущих коммерческих и академических баз кода OCaml. [9] В выпуске OCaml 4.0 в 2012 году были добавлены обобщенные алгебраические типы данных (GADT) и первоклассные модули для повышения гибкости языка. [9] Выпуск OCaml 5.0.0 в 2022 году [11] представляет собой полную переработку среды выполнения языка, в которой удалена глобальная блокировка GC и добавлены обработчики эффектов через продолжения с разделителями . Эти изменения обеспечивают поддержку параллелизма с общей памятью и параллелизма с цветовой слепотой соответственно.
Разработка OCaml продолжалась внутри команды Cristal в INRIA до 2005 года, когда ее сменила команда Gallium. [12] Впоследствии в 2019 году на смену Gallium пришла команда Cambium. [13] [14] По состоянию на 2023 год насчитывается 23 основных разработчика дистрибутива компилятора из различных организаций [15] и 41 разработчик более широкого инструментария OCaml. и экосистема упаковки. [16]
OCaml имеет систему статических типов , вывод типов , параметрический полиморфизм , хвостовую рекурсию , сопоставление с образцом , первоклассные лексические замыкания , функторы (параметрические модули) , обработку исключений , обработку эффектов и инкрементную поколенческую автоматическую сборку мусора .
OCaml примечателен тем, что расширяет вывод типов в стиле ML на объектную систему на языке общего назначения. Это допускает структурное подтипирование , при котором типы объектов совместимы, если их сигнатуры методов совместимы, независимо от их объявленного наследования (необычная функция для статически типизированных языков).
Предоставляется внешний интерфейс функций для связи с примитивами C, включая языковую поддержку эффективных числовых массивов в форматах , совместимых как с C, так и с Fortran . OCaml также поддерживает создание библиотек функций OCaml, которые можно связать с основной программой на C, чтобы библиотеку OCaml можно было распространять среди программистов C, которые не имеют знаний или не имеют установки OCaml.
Дистрибутив OCaml содержит:
Компилятор собственного кода доступен для многих платформ, включая Unix , Microsoft Windows и Apple macOS . Переносимость достигается за счет встроенной поддержки генерации кода для основных архитектур:
Компилятор байт-кода поддерживает работу на любой 32- или 64-битной архитектуре, когда генерация собственного кода недоступна, и требуется только компилятор C.
Программы с байт-кодом OCaml и собственным кодом могут быть написаны в многопоточном стиле с упреждающим переключением контекста. Потоки OCaml в одном домене [18] выполняются только с разделением времени. Однако программа OCaml может содержать несколько доменов. Существует несколько библиотек для распределенных вычислений, таких как Functory и ocamlnet/Plasma.
С 2011 года в среду разработки OCaml было добавлено множество новых инструментов и библиотек: [19]
Фрагменты кода OCaml легче всего изучать, вводя их в REPL верхнего уровня . Это интерактивный сеанс OCaml, который печатает предполагаемые типы результирующих или определенных выражений. [20] Верхний уровень OCaml запускается простым выполнением программы OCaml:
$ ocaml Objective Caml версии 3.09.0 #Затем код можно будет ввести в строке «#». Например, чтобы вычислить 1+2*3:
# 1 + 2 * 3 ;; - : целое = 7 OCaml определяет тип выражения как «int» ( целое число машинной точности ) и выдает результат «7».
Следующая программа «hello.ml»:
print_endline «Привет, мир!»можно скомпилировать в исполняемый файл с байт-кодом:
$ ocamlc hello.ml -о привет
или скомпилировать в оптимизированный исполняемый файл собственного кода:
$ ocamlopt hello.ml -o привет
и выполнил:
$ ./привет, привет, мир! $Первый аргумент ocamlc, «hello.ml», указывает исходный файл для компиляции, а флаг «-o hello» указывает выходной файл. [21]
Конструктор optionтипа в OCaml, аналогичный типу Maybeв Haskell , дополняет заданный тип данных, чтобы либо возвращать Someзначение данного типа данных, либо возвращать None. [22] Используется для выражения того, что значение может присутствовать или отсутствовать.
# Около 42 ;; - : int option = Some 42 # None ;; - : ' опция = Нет _ Это пример функции, которая либо извлекает int из опции, если она есть внутри, и преобразует ее в строку, либо, если нет, возвращает пустую строку:
пусть извлекает o = сопоставляет o с | Некоторые i -> string_of_int i | Нет -> "" ;;# экстракт ( около 42 );; - : string = "42" # извлечь Нет ;; - : строка = ""Списки — один из фундаментальных типов данных в OCaml. В следующем примере кода определяется рекурсивная функция sum , которая принимает один аргумент, целые числа , который должен быть списком целых чисел. Обратите внимание на ключевое слово rec, которое означает, что функция рекурсивная. Функция рекурсивно перебирает заданный список целых чисел и вычисляет сумму элементов. Оператор match имеет сходство с элементом переключателя C , хотя он гораздо более общий.
пусть Rec sum целые числа = (* Ключевое слово Rec означает «рекурсивный». *) сопоставляет целые числа с | [] -> 0 (* Выход 0, если целые числа — это пустой список []. *) | first :: rest -> first + sum rest ;; (* Рекурсивный вызов, если целые числа — непустой список; first — это первый элемент списка, а rest — список остальных элементов, возможно []. *) # сумма [ 1 ; 2 ; 3 ; 4 ; 5 ];; - : целое = 15Другой способ — использовать стандартную функцию сгиба , работающую со списками.
пусть суммируются целые числа = List . fold_left ( аккумулятор веселья x -> аккумулятор + x ) 0 целых чисел ;; # сумма [ 1 ; 2 ; 3 ; 4 ; 5 ];; - : целое = 15Поскольку анонимная функция — это просто применение оператора +, ее можно сократить до:
пусть суммируются целые числа = List . fold_left (+) 0 целых чиселБолее того, аргумент списка можно опустить, воспользовавшись частичным применением :
пусть сумма = Список . сгиб_влево (+) 0OCaml позволяет кратко выражать рекурсивные алгоритмы. В следующем примере кода реализуется алгоритм, аналогичный быстрой сортировке , который сортирует список по возрастанию.
пусть запись qsort = функция | [] -> [] | Pivot :: Rest -> let is_less x = x < Pivot in let left , right = List . раздел is_less rest в qsort left @ [ Pivot ] @ qsort rightИли используя частичное применение оператора >=.
пусть запись qsort = функция | [] -> [] | поворот :: rest -> let is_less = (>=) поворот в let left , right = List . раздел is_less rest в qsort left @ [ Pivot ] @ qsort rightСледующая программа вычисляет наименьшее количество людей в комнате, для которых вероятность совершенно уникальных дней рождения составляет менее 50% (задача о днях рождения , где для 1 человека вероятность равна 365/365 (или 100%), для 2 364/365, для 3 это 364/365×363/365 и т. д.) (ответ = 23).
пусть год_размер = 365 .пусть запись дня рождения_парадокса пробные люди = пусть пробный = ( размер_года -. плавающие люди ) /. размер_года *. проблема , если проблема < 0 . 5, затем Printf . printf "ответ = %d \n " ( люди + 1 ) else Birthday_paradox prob ( люди + 1 ) ;;день рождения_парадокс 1 . 0 1Следующий код определяет кодировку Чёрча натуральных чисел с преемником (succ) и сложением (add). Числа Чёрча n— это функция высшего порядка , которая принимает функцию fи значение xи применяется точно fко времени. Чтобы преобразовать число Чёрча из функционального значения в строку, мы передаем ему функцию, которая добавляет строку к входным данным и константной строке .xn"S""0"
пусть ноль f x = x пусть succ n f x = f ( n f x ) пусть один = ноль успеха пусть два = успех ( ноль успеха ) пусть добавляют n1 n2 f x = n1 f ( n2 f x ) пусть to_string n = n ( fun k -> "S" ^ k ) "0" let _ = to_string ( добавьте ( succ два ) два ) Множество библиотек доступны напрямую из OCaml. Например, в OCaml есть встроенная библиотека для арифметических операций произвольной точности . Поскольку функция факториала растет очень быстро, она быстро переполняет числа машинной точности (обычно 32- или 64-битные). Таким образом, факториал является подходящим кандидатом для арифметики произвольной точности.
В OCaml модуль Num (теперь замененный модулем ZArith) обеспечивает арифметику произвольной точности и может быть загружен в работающий верхний уровень с помощью:
# # используйте "topfind" ;; # # требуется "номер" ;; # открыть Num ;;Затем функцию факториала можно записать с использованием числовых операторов произвольной точности =/ , */ и -/ :
# let Rec fact n = if n =/ Int 0 then Int 1 else n */ fact ( n -/ Int 1 );; вал факт : Num . число -> Число . num = < весело >Эта функция может вычислять гораздо большие факториалы, например 120!:
# string_of_num ( факт ( Int 120 ));; - : string = "6689502913449127057588118054090372586752746333138029810295671352301633 55724496298936687416527198498130815763789321409 055253440858940812185989 8481114389650005964960521256960000000000000000000000000000"Следующая программа визуализирует вращающийся треугольник в 2D с использованием OpenGL :
let () = игнорировать ( Glut . init Sys . argv ); Перенасыщение . initDisplayMode ~ double_buffer : true () ; игнорировать ( Glut . createWindow ~ title : «Демо OpenGL» ); пусть угол t = 10 . *. т *. t в let render () = GlClear . очистить [ ` цвет ]; ГлМат . load_identity () ; ГлМат . поворот ~ угол : ( угол ( Sys . время () ) ~ z : 1 . () ; GlDraw . начинается ` треугольники ; Список . итер GlDraw . вершина2 [- 1 ., - 1 .; 0. , 1 .; 1 ., - 1 .]; GlDraw . заканчивается () ; Перенасыщение . swapBuffers () в GlMat . режим ` modelview ; Перенасыщение . displayFunc ~ cb : рендеринг ; Перенасыщение . IdleFunc ~ cb :( Некоторое перенасыщение . postRedisplay ); Перенасыщение . основной цикл ()Требуются привязки LablGL к OpenGL. Затем программу можно скомпилировать в байт-код с помощью:
$ ocamlc -I +lablGL lablglut.cma lablgl.cma simple.ml -o simple
или в собственный код с помощью:
$ ocamlopt -I +lablGL lablglut.cmxa lablgl.cmxa simple.ml -o simple
или, проще говоря, с помощью команды сборки ocamlfind
$ ocamlfind opt simple.ml -package lablgl.glut -linkpkg -o simple
и запустите:
$ ./простой
В OCaml можно разрабатывать гораздо более сложные и высокопроизводительные 2D- и 3D-графические программы. Благодаря использованию OpenGL и OCaml полученные программы могут быть кроссплатформенными, компилируясь без каких-либо изменений на многих основных платформах.
Следующий код вычисляет последовательность Фибоначчи для введенного числа n . Он использует хвостовую рекурсию и сопоставление с образцом.
let fib n = let Rec fib_aux m a b = сопоставить m с | 0 -> а | _ -> fib_aux ( m - 1 ) b ( a + b ) в fib_aux n 0 1Функции могут принимать функции в качестве входных данных и возвращать функции в качестве результата. Например, если применить дважды к функции f, получится функция, которая дважды применяет f к своему аргументу.
пусть дважды ( f : ' a -> ' a ) = fun ( x : ' a ) -> f ( f x );; пусть inc ( x : int ) : int = x + 1 ;; пусть add2 = дважды вкл ;; let inc_str ( x : string ) : string = x ^ " " ^ x ;; пусть add_str = дважды ( inc_str );; # add2 98 ;; - : int = 100 # add_str "Тест" ;; - : string = "Тест Тест Тест Тест" Функция дважды использует переменную типа 'a , чтобы указать, что ее можно применять к любой функции f , отображающей тип 'a в себя, а не только к функциям int->int . В частности, дважды можно применить даже к самому себе.
# пусть четыре раза f = ( дважды дважды ) f ;; val fourtimes : ( ' a -> ' a ) -> ' a -> ' a = < fun > # let add4 = fourtimes inc ;; val add4 : int -> int = < fun > # add4 98 ;; - : целое = 102 MetaOCaml [23] — это многоэтапное программное расширение OCaml, позволяющее инкрементную компиляцию нового машинного кода во время выполнения. В некоторых случаях значительное ускорение возможно при использовании многоэтапного программирования, поскольку более подробная информация о данных для обработки доступна во время выполнения, чем во время обычной компиляции, поэтому инкрементальный компилятор может оптимизировать многие случаи проверки условий и т. д.
В качестве примера: если во время компиляции известно, что какая-то степенная функция требуется часто, но значение известно только во время выполнения, в MetaOCaml можно использовать двухэтапную степенную функцию:x -> x^nn
пусть записываемая мощность n x = если n = 0 , то .< 1 >. иначе , если даже n, то sqr ( power ( n / 2 ) x ) else .<.~ x *. .~( степень ( n - 1 ) x )>.Как только nэто станет известно во время выполнения, можно создать специализированную и очень быструю степенную функцию:
.< fun x -> .~( power 5 .< x >.)>.Результат:
весело x_1 -> ( x_1 * пусть y_3 = пусть y_2 = ( x_1 * 1 ) в ( y_2 * y_2 ) в ( y_3 * y_3 ))Новая функция автоматически компилируется.
genfft.По крайней мере, несколько десятков компаний в той или иной степени используют OCaml. [30] Яркие примеры включают:
