OCaml

OCaml

Парадигма	Мультипарадигма : функциональная , императивная , модульная , [1] объектно-ориентированная
Семья	ML
Разработано	Ксавье Лерой , Жером Вуйон, Дамьен Долигес , Дидье Реми, Аскандер Суарес
Разработчик	INRIA
Впервые появился	1996 ; 25 лет назад ( 1996 )
Стабильный выпуск	4.12.0  / 24 февраля 2021 г . ; 13 дней назад ( 24 февраля 2021 г. )
Печатная дисциплина	Предполагаемый , статический , прочный , структурный
Язык реализации	OCaml, C
Платформа	IA-32 , x86-64 , питание , SPARC , ARM 32-64
Операционные системы	Кроссплатформенность : Unix , macOS , Windows
Лицензия	LGPLv2.1
Расширения имени файла	.ml, .mli
Интернет сайт	ocaml .org
Под влиянием
C , Caml , Modula-3 , Паскаль , Стандартный ML
Под влиянием
ATS , Coq , Elm , F # , F * , Haxe , Opa , Rust , Scala
Objective Caml в Викиучебнике

OCaml ( / oʊ к æ м əl / OH- КАМ -əl , ранее цель Caml ) является универсальным , мульти-парадигма языка программирования , который расширяет Ca диалекте ML с объектно-ориентированных функциями. OCaml был создан в 1996 году Ксавье Лерой , Жеромом Вуйоном, Дамьеном Долигесом , Дидье Реми, Аскандером Суаресом и другими.

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

Аббревиатура CAML первоначально расшифровывалась как язык категориальных абстрактных машин , но OCaml опускает эту абстрактную машину . ^[2] OCaml - это бесплатный программный проект с открытым исходным кодом, управляемый и в основном поддерживаемый Французским институтом исследований в области компьютерных наук и автоматизации (INRIA). В начале 2000-х годов элементы OCaml были приняты многими языками, особенно F # и Scala .

Философия [ править ]

Языки, производные от ML , наиболее известны своими системами статических типов и компиляторами вывода типов . OCaml объединяет функциональное , императивное и объектно-ориентированное программирование в систему типов, подобную ML. Таким образом, программистам не нужно хорошо знать парадигму чисто функционального языка, чтобы использовать OCaml.

Требуя от программиста работы в рамках ограничений своей системы статических типов, OCaml устраняет многие связанные с типами проблемы времени выполнения, связанные с динамически типизированными языками. Кроме того, компилятор определения типа OCaml значительно снижает потребность в ручных аннотациях типов, которые требуются для большинства языков со статической типизацией. Например, тип данных переменных и сигнатуру функций обычно не нужно объявлять явно, как это делается в таких языках, как Java и C #., потому что они могут быть выведены из операторов и других функций, которые применяются к переменным и другим значениям в коде. Эффективное использование системы типов OCaml может потребовать от программиста некоторой сложности, но эта дисциплина вознаграждается надежным и высокопроизводительным программным обеспечением.

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

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

Ксавье Лерой заявил, что «OCaml обеспечивает не менее 50% производительности достойного компилятора C» ^[3], хотя прямое сравнение невозможно. Некоторые функции в стандартной библиотеке OCaml реализованы с помощью более быстрых алгоритмов, чем эквивалентные функции в стандартных библиотеках других языков. Например, реализация объединения наборов в стандартной библиотеке OCaml теоретически асимптотически быстрее, чем эквивалентная функция в стандартных библиотеках императивных языков (например, C ++, Java), поскольку реализация OCaml использует неизменность наборов для повторного использования частей ввода. устанавливает в выводе (см. постоянную структуру данных ).

Особенности [ править ]

OCaml включает систему статических типов , вывод типов , параметрический полиморфизм , хвостовую рекурсию , сопоставление с образцом , лексические замыкания первого класса , функторы (параметрические модули) , обработку исключений и автоматическую сборку мусора с возрастающим поколением .

OCaml примечателен расширением вывода типов в стиле ML на объектную систему в языке общего назначения. Это позволяет создавать структурные подтипы , когда типы объектов совместимы, если их сигнатуры методов совместимы, независимо от их объявленного наследования (необычная функция в статически типизированных языках).

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

Дистрибутив OCaml содержит:

• Инструменты лексического анализа и синтаксического анализа , называемые ocamllex и ocamlyacc
• Отладчик , поддерживающий переход назад для исследования ошибок
• Генератор документации
• Профайлер - для измерения производительности
• Множество универсальных библиотек

Компилятор собственного кода доступен для многих платформ, включая Unix , Microsoft Windows и Apple macOS . Переносимость достигается за счет поддержки генерации собственного кода для основных архитектур: IA-32 , X86-64 (AMD64), Power , SPARC , ARM и ARM64 . ^[4]

Байт-код OCaml и программы с машинным кодом могут быть написаны в многопоточном стиле с упреждающим переключением контекста. Однако, поскольку сборщик мусора системы INRIA OCaml (который является единственной доступной в настоящее время полной реализацией языка) не предназначен для параллелизма, симметричная многопроцессорная обработка не поддерживается. ^[5] Потоки OCaml в одном процессе выполняются только с разделением времени. Однако существует несколько библиотек для распределенных вычислений, таких как Functory и ocamlnet / Plasma .

Среда разработки [ править ]

С 2011 года в среду разработки OCaml было добавлено множество новых инструментов и библиотек:

• Инструменты разработки
  • opam - это менеджер пакетов для OCaml, разработанный OCamlPro .
  • Merlin предоставляет IDE-подобную функциональность для нескольких редакторов, включая возврат типа, переход к определению и автозаполнение.
  • Dune - это составная сборочная система для OCaml.
  • OCamlformat - это средство автоматического форматирования для OCaml.
• Веб-сайты:
  • OCaml.org - это основной сайт для этого языка.
  • Обсуждение.ocaml.org - это экземпляр Discourse, который служит основным сайтом обсуждений для OCaml.
• Альтернативные компиляторы для OCaml:
  • js_of_ocaml, разработанный командой Ocsigen , представляет собой оптимизирующий компилятор от OCaml до JavaScript .
  • BuckleScript , который также нацелен на JavaScript , с упором на создание удобочитаемого идиоматического вывода JavaScript.
  • ocamlcc - это компилятор от OCaml до C, дополняющий компилятор машинного кода для неподдерживаемых платформ.
  • OCamlJava, разработанный INRIA, представляет собой компилятор OCaml для виртуальной машины Java (JVM).
  • OCaPic, разработанный Lip6, представляет собой компилятор OCaml для микроконтроллеров PIC .

Примеры кода [ править ]

Фрагменты кода OCaml легче всего изучить, введя их на верхний уровень . Это интерактивный сеанс OCaml, который печатает предполагаемые типы результирующих или определенных выражений. Верхний уровень OCaml запускается простым выполнением программы OCaml:

$ ocaml  Objective Caml версии 3.09.0 #

После этого можно ввести код в ответ на подсказку «#». Например, чтобы вычислить 1 + 2 * 3:

# 1 + 2 * 3 ;; -: int = 7

OCaml определяет тип выражения как «int» ( целое число с машинной точностью ) и возвращает результат «7».

Привет, мир [ править ]

Следующая программа "hello.ml":

print_endline  "Привет, мир!"

может быть скомпилирован в исполняемый файл байт-кода:

$ ocamlc hello.ml -o привет

или скомпилирован в оптимизированный исполняемый файл с машинным кодом:

$ ocamlopt hello.ml -o привет

и выполнено:

$ ./hello Привет, мир! $

Первый аргумент ocamlc, «hello.ml», указывает исходный файл для компиляции, а флаг «-o hello» указывает выходной файл. ^[6]

Суммирование списка целых чисел [ править ]

Списки - один из основных типов данных в OCaml. В следующем примере кода определяется рекурсивная функция sum, которая принимает один аргумент, целые числа , который должен быть списком целых чисел. Обратите внимание на ключевое слово, recкоторое означает, что функция рекурсивна. Функция рекурсивно выполняет итерацию по заданному списку целых чисел и предоставляет сумму элементов. Оператор match имеет сходство с элементом switch в языке C , хотя и носит гораздо более общий характер.

let  rec  sum  inteers  =  (* Ключевое слово rec означает «рекурсивный». *)  соответствует  целым числам  с  |  []  ->  0  (* Возвращаем 0, если целые числа - пустой  список []. *)  |  first  ::  rest  ->  first  +  sum  rest ;;  (* Рекурсивный вызов, если целые числа - это  непустой список; first - это первый  элемент списка, а rest - это  список остальных элементов, возможно []. *)

 #  сумма  [ 1 ; 2 ; 3 ; 4 ; 5 ] ;;  -  :  int  =  15

Другой способ - использовать стандартную функцию сворачивания, которая работает со списками.

пусть  сумма  целых чисел  =  Список . fold_left  ( забавный  аккумулятор  x  ->  аккумулятор  +  x )  0  целых чисел ;;

 #  сумма  [ 1 ; 2 ; 3 ; 4 ; 5 ] ;;  -  :  int  =  15

Поскольку анонимная функция - это просто приложение оператора +, ее можно сократить до:

пусть  сумма  целых чисел  =  Список . fold_left  (+)  0  целых чисел

Кроме того, можно опустить аргумент списка, используя частичное приложение :

пусть  сумма  =  Список . fold_left  (+)  0

Быстрая сортировка [ править ]

OCaml позволяет лаконично выражать рекурсивные алгоритмы. В следующем примере кода реализуется алгоритм, аналогичный быстрой сортировке, который сортирует список в порядке возрастания.

 пусть  rec  qsort  =  function  |  []  ->  []  |  pivot  ::  rest  ->  let  is_less  x  =  x  <  pivot  in  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 .let  rec  birthday_paradox  prob  people  =  let  prob  =  ( year_size  -.  float  people )  /.  год_размер  *.  Пробы  в  если  вероишь  <  0 . 5,  затем  Printf . printf  "answer =% d \ n "  ( people + 1 )  else  birthday_paradox  prob  ( people + 1 ) ;;день рождения_парадокс  1 . 0  1

Церковные цифры [ править ]

Следующий код определяет кодировку Church из натуральных чисел , с преемником (Succ) и добавлением (ADD). Церковь , позиция nявляется функцией высшего порядка , которая принимает функцию fи значение xи применяется fк xточно nраз. Чтобы преобразовать число Чёрча из функционального значения в строку, мы передаем ему функцию, которая добавляет строку "S"к его входу и константной строке "0".

let  zero  f  x  =  x let  succ  n  f  x  =  f  ( n  f  x ) let  one  =  succ  zero let  two  =  succ  ( succ  zero ) let  add  n1  n2  f  x  =  n1  f  ( n2  f  x ) let  to_string  n  =  n  ( весело  k  ->  "S"  ^  k)  "0" let  _  =  to_string  ( добавить  ( succ  two )  два )

Факториальная функция произвольной точности (библиотеки) [ править ]

Различные библиотеки доступны напрямую из OCaml. Например, в OCaml есть встроенная библиотека для арифметики произвольной точности . Поскольку факториальная функция растет очень быстро, она быстро выходит за пределы чисел машинной точности (обычно 32- или 64-битных). Таким образом, факториал является подходящим кандидатом для арифметики произвольной точности.

В OCaml модуль Num (теперь замененный модулем ZArith) обеспечивает арифметику произвольной точности и может быть загружен в работающий верхний уровень, используя:

#  # ##use "topfind";; #require "num";; open Num;;

Затем факториальную функцию можно записать с использованием числовых операторов произвольной точности = / , * / и - /  :

#  let  rec  fact  n  =  if  n  = /  Int  0  then  Int  1  else  n  * /  fact ( n  - /  Int  1 ) ;; val  факт  :  Num . число  ->  Число . число  =  < веселье >

Эта функция может вычислять факториалы гораздо большего размера, например 120 !:

#  string_of_num  ( fact  ( Int  120 )) ;; -  :  string  = "6689502913449127057588118054090372586752746333138029810295671352301633 55724496298936687416527198498130815763789321409055253440858940812185989 8481114389651200000000569649640000000000000000

Треугольник (графика) [ править ]

Следующая программа визуализирует вращающийся треугольник в 2D с помощью OpenGL :

let  ()  =  игнорировать  ( Glut . init  Sys . argv );  Перенасыщение . initDisplayMode  ~ двойной_буфер : истина  () ;  игнорировать  ( Glut . createWindow  ~ title : "OpenGL Demo" );  пусть  угол  t  =  10 .  *.  т  *.  t  в  let  render  ()  =  GlClear . ясно  [  ` цвет ];  GlMat . load_identity  () ;  GlMat . поворот  ~ угол :  ( угол  ( Sys . время  () ))  ~ г : 1 .  () ;  GlDraw . начинается  ` треугольники ;  Список . iter  GlDraw . вершина2  [- 1. ,  - 1 .;  0. ,  1 .;  1. ,  - 1. ]; GlDraw . заканчивается  () ;  Перенасыщение . swapBuffers  ()  в  GlMat . режим  ` modelview ;  Перенасыщение . displayFunc  ~ cb : render ;  Перенасыщение . idleFunc  ~ центибар :( Некоторые  Перенасыщение . postRedisplay );  Перенасыщение . mainLoop  ()

Привязки LablGL к OpenGL обязательны. Затем программа может быть скомпилирована в байт-код с помощью:

 $ ocamlc -I + lablGL lablglut.cma lablgl.cma simple.ml -o simple

или в собственный код с помощью:

 $ ocamlopt -I + lablGL lablglut.cmxa lablgl.cmxa simple.ml -o простой

или, проще говоря, с помощью команды сборки ocamlfind

 $ ocamlfind opt simple.ml -package lablgl.glut -linkpkg -o simple

и запустите:

 $ ./simple

В OCaml можно разрабатывать гораздо более сложные и высокопроизводительные графические программы в 2D и 3D. Благодаря использованию OpenGL и OCaml полученные программы могут быть кроссплатформенными и компилироваться без каких-либо изменений на многих основных платформах.

Последовательность Фибоначчи [ править ]

Следующий код вычисляет последовательность Фибоначчи введенного числа n . Он использует хвостовую рекурсию и сопоставление с образцом.

пусть  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 ) ;; let  inc  ( x  :  int )  :  int  =  x  +  1 ;; пусть  ADD2  =  дважды  вкл ;; пусть  inc_str  ( x  :  строка )  :  строка  =  x  ^ ""  ^  x ;; пусть  add_str  =  дважды ( inc_str ) ;;

 #  add2  98 ;;  -  :  int  =  100 # add_str "Test" ;; - : string = "Test Test Test Test"        

Функция дважды использует переменную типа '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 ;; - : int =                      102

Производные языки [ править ]

MetaOCaml [ править ]

MetaOCaml ^[7] - это многоступенчатое программное расширение OCaml, позволяющее выполнять инкрементную компиляцию нового машинного кода во время выполнения. При некоторых обстоятельствах возможно значительное ускорение при использовании многоступенчатого программирования, потому что более подробная информация о данных для обработки доступна во время выполнения, чем в обычное время компиляции, поэтому инкрементный компилятор может оптимизировать многие случаи проверки условий и т. Д.

В качестве примера: если во время компиляции известно, что какая-то функция мощности требуется часто, но значение известно только во время выполнения, в MetaOCaml можно использовать двухэтапную функцию мощности:x -> x^nn

 let  rec  power  n  x  =  if  n  =  0  then  . < 1 >.  иначе,  если  даже  n,  то  sqr  ( power  ( n / 2 )  x )  else  . <. ~ x  *.  . ~ ( мощность  ( n  -  1 )  x )>.

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

 . < веселье  x  ->  . ~ ( степень  5.  < x >.)>.

Результат:

 весело  x_1  ->  ( x_1  *  let  y_3  =  let  y_2  =  ( x_1  *  1 )  in  ( y_2  *  y_2 )  in  ( y_3  *  y_3 ))

Новая функция компилируется автоматически.

Другие производные языки [ править ]

• AtomCaml предоставляет примитив синхронизации для атомарного (транзакционного) выполнения кода.
• Эмили (2006) - это подмножество OCaml 3.08, в котором используется верификатор правил проектирования для обеспечения соблюдения принципов безопасности модели объектных возможностей .
• F # - это язык .NET Framework, основанный на OCaml.
• Fresh OCaml упрощает работу с именами и привязками.
• GCaml добавляет к OCaml экстенсиональный полиморфизм, что позволяет осуществлять перегрузку и маршалинг с безопасным типом.
• JoCaml объединяет конструкции для разработки параллельных и распределенных программ.
• OCamlDuce расширяет OCaml такими функциями, как выражения XML и типы регулярных выражений.
• OCamlP3l - это система параллельного программирования , основанная на OCaml и языке P3L.
• Хотя это не совсем отдельный язык, Reason - это альтернативный синтаксис OCaml и набор инструментов для OCaml, созданный в Facebook .

Программное обеспечение, написанное на OCaml [ править ]

• 0install , многоплатформенный менеджер пакетов.
• Coccinelle , утилита для преобразования в исходный код на C программ.
• Coq , формальная система управления доказательствами .
• FFTW , библиотека для вычисления дискретных преобразований Фурье . Программа OCaml с именем genfft.
• Веб-версия Facebook Messenger . ^[8]
• Flow, статический анализатор, созданный в Facebook, который определяет и проверяет статические типы для JavaScript . ^[9]
• Owl Scientific Computing , специализированная система для научных и инженерных вычислений.
• Frama-C , фреймворк для анализа программ на C.
• GeneWeb , бесплатное мультиплатформенное генеалогическое программное обеспечение с открытым исходным кодом.
• Hack язык программирования компилятор, созданный на Facebook, простираясь PHP со статическими типами.
• Haxe язык программирования компилятор.
• HOL Light , официальный помощник по проверке.
• Infer, статический анализатор, созданный в Facebook для Java , C, C ++ и Objective-C , используемый для обнаружения ошибок в приложениях iOS и Android . ^[10]
• Lexifi Apropos , система для моделирования сложных производных.
• MirageOS , среда программирования unikernel, написанная на чистом OCaml.
• MLdonkey , приложение для однорангового обмена файлами, основанное на сети EDonkey .
• Ocsigen , веб-фреймворк OCaml .
• Opa , бесплатный язык программирования с открытым исходным кодом для веб-разработки.
• pyre-check, средство проверки типов для Python, созданное в Facebook. ^[11]
• Tezos , платформа смарт-контрактов с самовосстановлением , использующая XTZ в качестве собственной валюты.
• Unison , синхронизации файлов программа для синхронизации файлов между двумя каталогами.
• Эталонный интерпретатор для WebAssembly , байт - кода низкого уровня, предназначенного для выполнения внутри веб-браузеров . ^[12]
• Xen Cloud Platform (XCP), готовое решение виртуализации для гипервизора Xen .

Пользователи [ править ]

Несколько десятков компаний в той или иной степени используют OCaml. ^[13] Известные примеры включают:

• Bloomberg LP , которая создала BuckleScript , серверную часть компилятора OCaml, ориентированную на JavaScript. ^[14]
• Citrix Systems , которая использует OCaml в XenServer (в 2018 году был переименован в Citrix Hypervisor).
• Facebook , который разработал Flow, Hack, Infer, Pfff и Reason в OCaml.
• Jane Street Capital , торговая фирма, которая с самого начала приняла OCaml в качестве предпочтительного языка. ^[15]
• MEDIT, Франция , использует OCaml для биоформатики. ^[16]

Ссылки [ править ]

Внешние ссылки [ править ]

В Викиучебнике есть книга по теме: OCaml.

• Официальный веб-сайт
• Руководство по OCaml
• Менеджер пакетов OCaml
• Реальный мир OCaml