Как начать с Reason

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

Большинство статей о Reason показывают, как это работает в ReasonReact. Это имеет смысл, так как Facebook разработал Reason. Однако в этой статье я хотел показать, как Reason сияет как язык вне ReasonReact.

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

reason.svg преобразуется в png с помощью Imagemagic, пиксельный фон с помощью Imagemagick

Почему стоит выбрать причину?

Reason - это функциональный язык, который поощряет неизменность, предоставляет логическую систему статических типов и компилируется в JavaScript. Давайте внимательнее посмотрим:

  1. Reason и OCaml имеют одинаковую семантику. Таким образом, функциональные программные конструкции, доступные в OCaml, такие как сопоставление с образцом и каррирование, напрямую переводятся в Reason.
  2. В Reason почти всегда нет необходимости записывать типы - компилятор определяет типы для вас. Например, компилятор видит this () => {1 + 1} как функцию, которая принимает единицу (без аргументов) и возвращает int.
  3. Большинство конструкций в Reason неизменны. Список неизменен. Массив является изменяемым, но имеет фиксированный размер. Добавление нового элемента в массив возвращает копию массива, расширенного новым элементом. Записи (аналогично объектам JavaScript) являются неизменяемыми.
  4. BuckleScript компилирует Reason вплоть до JavaScript. Вы можете работать с JavaScript в коде Reason и использовать модули Reason в JavaScript.

Reason приносит преимущества языка со строгой типизацией для JavaScript по низкой цене. Вам обязательно следует прочитать раздел «Что и почему» в документации, поскольку он предоставляет больше контекста для языка и его возможностей.

Некоторые ресурсы, которые помогут вам начать

  1. Официальные документы Reason просты и точны
  2. Изучение ReasonML, книги доктора Акселя Раушмайера, исследует Reason более практичным способом
  3. Документация BuckleScript подробно рассказывает о совместимости с JavaScript и OCaml

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

Большая картинка

Этот учебник был вдохновлен Node Schedule, планировщиком для Node.js, который всегда использует один таймер. Вы можете узнать больше о том, как Node Schedule работает здесь.

Сегодня мы собираемся создать планировщик в Reason, который будет всегда использовать один таймер. Мы будем использовать наш планировщик для выполнения повторяющихся заданий. Этот проект достаточно большой, чтобы продемонстрировать некоторые ключевые концепции Reason.

Большая Картина: P

Для этого мы определим два модуля - кучу и планировщик.

Куча - это реализация очереди с приоритетами. Он сохраняет задания в порядке их выполнения. Ключом элемента кучи является время следующего вызова задания.

Планировщик состоит из кучи и отвечает за обновление таймера и выполнение заданий по заданным правилам повторения.

  1. Когда задание выполняется, планировщик удаляет задание из очереди, вычисляет время его следующего вызова и вставляет задание обратно в очередь с его обновленным временем вызова.
  2. Когда добавляется новое задание, планировщик проверяет время следующего вызова корня (заголовок / задание, которое будет выполнено следующим). Если новое задание должно быть выполнено раньше руководителя, планировщик обновляет таймер.

Модуль кучи

API очереди приоритетов определяет:

  1. Вставка нового элемента в очередь с ключом, представляющим его приоритет
  2. Извлечение элемента с наивысшим приоритетом
  3. Размер очереди

Куча выполняет операции вставки и извлечения в порядке O (log (n)), где n - размер очереди.

Примечание: мы поговорим о сложности алгоритма в последнем разделе статьи. Если вас не устраивает сложность алгоритма, вы можете игнорировать последний раздел.

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

Определение типов, используемых модулем кучи

heapElement

heapElement определяет тип записи. Подобно объекту JavaScript, вы можете получить доступ к полям записи по имени. {key: 1, value: "1"} создает значение типа heapElement (int, string).

Heap.t

t ('a,' b) - другой тип записи, представляющий кучу. Это тип возврата нашей функции create и последний параметр, передаваемый всем другим функциям в открытом API нашего модуля кучи.

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

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

Массивы в Reason являются изменяемыми - вы можете обновить значение по определенному индексу. Тем не менее, они имеют фиксированную длину. Для поддержки добавления и извлечения наша куча должна содержать ссылку на массив элементов кучи. Если мы не будем использовать ссылку здесь, нам придется возвращать новую кучу после каждого добавления и извлечения. И модули, которые зависят от кучи, должны отслеживать новую кучу.

Исключение EmptyQueue

Исключение можно расширить с помощью новых конструкторов. Мы будем вызывать исключение EmptyQueue позже в функциях extract и head модуля heap.

Исключения - все одного типа, exn. Тип exn - это особый случай в системе типов OCaml. Он аналогичен вариантным типам, с которыми мы столкнулись в главе 6 «Варианты», за исключением того, что он является открытым, что означает, что он не определен полностью ни в одном месте. - RealWorldOcaml

Подпись

Подпись кучи

По умолчанию все привязки (назначения переменных) в модуле доступны везде, даже за пределами модуля, в котором они определены. Сигнатура - это механизм, с помощью которого вы можете скрыть специфичную для реализации логику и определить API для модуля. Вы можете определить сигнатуру в файле с тем же именем, что и модуль, заканчивающийся суффиксом .rei. Например, вы можете определить сигнатуру для Heap.re в файле Heap.rei.

Здесь мы представляем определение heapElement, чтобы пользователи модуля Heap могли использовать значение, возвращаемое head и extract. Но мы не предоставляем определение для нашего типа кучи. Это делает абстрактный тип, который гарантирует, что только функции в модуле Heap могут использовать кучу и преобразовывать ее.

Инициализатор кучи

Каждая функция, кроме create, принимает в качестве аргумента кучу. create берет функцию сравнения и создает пустой Heap.t, который может использоваться другими функциями в модуле Heap.

Вспомогательные функции

Вспомогательные функции

parent - это функция, которая принимает один аргумент - index. Он возвращает None, когда индекс равен 0. index 0 указывает на корень дерева, а корень дерева не имеет родителя.

left и right возвращают индекс левого и правого дочернего узла.

swap принимает два индекса a и b и очередь массива. Затем он меняет значения в индексе a и b очереди.

key просто возвращает ключевое поле heapElement по указанному индексу в очереди.

size возвращает длину очереди

Добавлять

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

исправить

let rec позволяет нам определять рекурсивные функции. С помощью rec вы можете ссылаться на имя функции внутри тела функции.

Мы определили ключ как функцию, которая принимает в качестве аргументов очередь и индекс. С объявлением let key = key (очередь) мы создаем теневой ключ, частично применяя вспомогательную функциональную клавишу, которую мы определили ранее.

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

Предоставленные вами аргументы доступны для возвращаемой функции. Поскольку очередь исправлена ​​в fix_up, мы частично применяем ее к функции ключа, чтобы сделать наш код более СУХИМЫМ.

Вы можете использовать when <условие>, чтобы указать дополнительные условия в сопоставлении с образцом. Привязки значений в этом случае доступны выражению, следующему, когда (в нашем примере p_ind доступен в сравнении (ключ (индекс), ключ (p_ind)). Только когда условие выполнено, мы выполняем соответствующий оператор после =>.

Добавлять

add объединяет новый элемент в конец очереди. Если новый элемент имеет более высокий приоритет, чем его родитель, он нарушает свойство max heap. fix_up - это рекурсивная функция, которая восстанавливает свойство max heap, перемещая новый элемент вверх по дереву (попарно меняя его с родителем), пока он не достигнет корня дерева или его приоритет не станет ниже его родителя.

fix_last является просто оболочкой для fix_up и вызывает его с индексом последнего элемента в очереди.

heap.queue ^ - это то, как мы получаем доступ к ссылкам на значения.

[||] - синтаксис литерала массива для пустого массива.

экстракт

extract удаляет элемент с наивысшим приоритетом (в нашем случае элемент с наименьшим ключом) из очереди и возвращает его. extract удаляет заголовок очереди, сначала поменяв его местами с последним элементом в массиве. Это вводит единственное нарушение свойства max heap в корне / начале очереди.

Как описано в лекции, heapify - также известная как sift-down - устраняет одно нарушение. Предполагая, что левое и правое поддеревья узла n удовлетворяют свойству max heap, вызов heapify для n исправляет нарушение.

Каждый раз, когда вызывается heapify, он находит индекс max_priority_index элемента с наивысшим приоритетом между heapElements в index, left (index) и right (index). Если max_priority_index не равен индексу, мы знаем, что все еще есть нарушение свойства max heap. Мы меняем элементы в индексе и max_priority_index, чтобы исправить нарушение в индексе. Мы рекурсивно вызываем heapify с max_priority_index, чтобы исправить возможное нарушение, которое мы можем создать, меняя местами два элемента.

heapify

index - это int, представляющий корень поддерева, которое нарушает свойство max heap, но его поддеревья удовлетворяют свойству. сравнить это функция сравнения, определенная с кучей. Очередь - это массив, содержащий элементы кучи.

Операторы if в Reason, как и другие выражения, оцениваются как значения. Здесь операторы if оцениваются как int, представляющий, какой индекс был меньше в сравнении.

экстракт

шаблон извлечения совпадает с очередью (массив не ссылка).

[| head |] соответствует массиву только с одним элементом.

Когда очередь пуста [||], мы вызываем исключение EmptyQueue, которое мы определили ранее. Но почему? Почему бы нам не вернуть None? Ну, это вопрос предпочтений. Я предпочитаю вызывать исключение, потому что, когда я использую эту функцию, я получу heapElement, а не опцию (heapElement). Это спасает меня от сопоставления с возвращаемым значением экстракта. Предостережение заключается в том, что вы должны быть осторожны при использовании этой функции, следя за тем, чтобы очередь никогда не была пустой.

Когда у нас более одного элемента, мы меняем местами первый и последний элемент очереди, удаляем последний элемент и вызываем heapify для первого элемента (корень дерева).

тестирование

Мы используем bs-jest - привязки BuckleScript для Jest - для написания тестов. Jest - это среда тестирования, созданная Facebook, которая поставляется со встроенной библиотекой макетов и отчетами о покрытии кода.

  1. https://github.com/glennsl/bs-jest
  2. https://facebook.github.io/jest/docs/en/getting-started.html

Следуйте инструкциям в bs-jest, чтобы настроить Jest.

Обязательно добавьте @ glennsl / bs-jest в bs-dev-dependencies в вашем bsconfig.json. В противном случае BuckleScript не найдет модуль Jest, и ваша сборка не удастся.

Если вы пишете свои тестовые случаи в каталоге, отличном от src, вы должны указать его в источниках в bsconfig.json, чтобы компилятор BuckleScript мог их забрать.

Тестирование синхронных функций

Установив модуль Heap и установив Jest, мы готовы написать наш первый тестовый пример.

Чтобы протестировать наш модуль кучи, мы сделаем сортировку кучи.

  1. создать кучу
  2. вставлять элементы в кучу
  3. используйте операцию извлечения, чтобы удалить элементы в порядке возрастания
Проверка кучи

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

Мы используем let {value: e1} = для деструктурирования значения, возвращаемого извлечением, и создания псевдонима e1 для значения - теперь e1 привязан к полю значения значения, возвращаемого извлечением.

С помощью оператора |> pipe мы можем создать составную функцию и сразу применить полученную функцию к входу. Здесь мы просто передаем результат вызова ожидаемого с (e1, ..., e9) в функцию toEqual.

Модуль планировщика

Планировщик использует модуль Heap для ведения списка повторяющихся заданий, отсортированных по времени их следующего вызова.

Давайте определим типы, используемые в модуле планировщика

повторение

рецидив является типом Variant. Любое значение типа повторения может быть секундой, минутой или часом. Во-вторых, Минута и Час являются конструкторами для повторения. Вы можете вызвать конструктор как обычную функцию и получить значение типа Variant. В нашем случае, если вы вызываете Second с int, вы получаете значение типа recurrence. Вы можете сопоставить это значение с параметром Second (number_of_seconds), чтобы получить доступ к аргументу, который был передан конструктору Second.

работа

задание является типом записи. Период имеет тип повторения и указывает задержку между каждым выполнением задания. invoke - это функция, которая принимает единицу (без аргумента) и возвращает единицу (без результата). invoke - это функция, которая выполняется при выполнении задания.

Scheduler.t

t является типом записи, представляющим планировщик. Планировщик удерживает очередь заданий, отсортированных по времени их следующего вызова. timer_id ссылается на timerId для первого задания в очереди - задание, которое будет вызвано первым.

Interop

Вы можете вызывать функции JavaScript изнутри Reason. Есть разные способы сделать это:

  1. Вы можете использовать привязки BuckleScript, если они доступны, такие как Js.log и Js.Global.setTimeout
  2. объявить внешний, такой как [@ bs.val] external setTimeout
  3. выполнить сырой код JavaScript с помощью [% raw ...]

Привязки для большинства функций JavaScript предоставляются BuckleScript. Например, Js.Date.getTime принимает Js.Date.t - значение даты - и возвращает количество миллисекунд с начала эпохи. Js.Date.getTime - это привязка для метода getTime объекта JavaScript Date. Js.Date.getTime возвращает значение с плавающей точкой.

Использование привязок в виде бэкскрипта точно так же, как использование пользовательских модулей. Вы можете прочитать больше о доступных привязках здесь. В оставшейся части этого раздела мы сосредоточимся на внешних и [% raw ...].

внешний

С внешним вы можете связать переменную с функцией JavaScript. Здесь, например, мы связываем переменную setTimeout с глобальной функцией JavaScript setTimeout.

определение setTimeout и clearTimeout в документах BuckleScript

setTimeout возвращает float, идентификатор, который мы можем передать clearTimeout для отмены таймера. Единственная функция, которая использует значение, возвращаемое setTimeout, это clearTimeout. Таким образом, мы можем определить значение, возвращаемое setTimeout, чтобы иметь абстрактный тип. Это гарантирует, что только значение, возвращаемое setTimeout, может быть передано в clearTimeout.

[% сырой…]

new Date.getTime () в JavaScript возвращает целое число. Числа в JavaScript имеют длину 64 бита. int в Reason только 32-битные. Это проблема!

В Reason мы можем работать с возвращаемым значением нового Date.getTime (), ожидая, что оно будет Float. На самом деле это ожидаемый тип возвращаемого значения Js.Date.getTime, предоставляемый BuckleScript.

Вместо этого, давайте используем [% raw ...] и создаем абстрактный тип, долго похожий на то, что мы сделали для setTimeout. При этом мы скрываем реализацию долго. Наш код Reason может передавать значения типа long вокруг, но он не может реально работать с ними. Для этого мы определяем набор вспомогательных привязок, которые принимают значения типа long и делегируют вычисления необработанным выражениям JavaScript.

работа со значениями JavaScript

Мы можем определить выражение JavaScript с помощью [% raw ...]. Здесь мы определяем абстрактный тип long и набор функций, которые потребляют и возвращают значения типа long. Тип всех выражений указывается в привязках let.

time_now возвращает количество миллисекунд с начала эпохи.

Мы используем sum для вычисления следующего времени вызова задания, передавая результат time_now и int, представляющие, сколько миллисекунд с этого момента должно быть выполнено задание.

Мы можем вычислить, как долго с этого момента будет вызываться задание, вычитая время вызова задания из time_now. Результат вычитания передается в setTimeout.

has_higher_priority сравнивает два времени вызова. Это функция сравнения, которую мы используем для инициализации нашей кучи.

мольба

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

  1. извлечь первое задание из очереди
  2. рассчитать время следующего вызова (новый ключ для задания)
  3. вставить задание обратно в очередь с его обновленным ключом
  4. посмотрите на начало очереди, чтобы найти задание, которое должно быть выполнено следующим, и
  5. создать новый таймер для этой работы
помощники

wait принимает период - значение типа повторения - и возвращает целое число, представляющее, сколько миллисекунд должно пройти задание, прежде чем оно будет снова выполнено. Мы передаем значение, возвращаемое ожиданием, в setTimeout.

next_invocation вычисляет время следующего вызова задания. time_now возвращает длинное значение. sum принимает значение long и int и возвращает значение long. sum добавляет два числа, вызывая оператор JavaScript + для своих аргументов.

Вызывая работу

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

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

Затем мы продолжаем создавать новый таймер для задания в начале очереди (следующее задание, которое должно быть выполнено после этого вызова). Мы обновляем ссылку на timer_id, чтобы она указала на новый timerId.

Наконец, мы вызываем поле invoke задания для выполнения указанной задачи.

Добавить новую работу

добавление новой работы

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

Более интересный случай, когда очередь не пуста! У нас может быть две ситуации здесь. Либо глава очереди имеет ключ больше, чем время следующего вызова задания, либо нет.

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

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

Тестирование асинхронных функций

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

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

Теперь давайте напишем контрольный пример, чтобы убедиться, что при добавлении задания в планировщик оно вызывается в соответствии с правилом повторения.

Для этого мы будем

  1. добавить задание в планировщик, который будет выполняться каждую секунду. Это задание увеличивает счетчик ref (int).
  2. создать обещание, которое будет решено после 4 с
  3. вернуть обещание Jest.assertion, которое ожидает увеличения счетчика в 4 раза.
Планировщик испытаний добавить

Мы можем использовать testPromise для проверки обещаний. testPromise ожидает Js.Promise.t (Jest.assertion). Посмотрите на последнюю строку контрольного примера.

Scheduler.Second (1) указывает, что мы хотим, чтобы наша работа выполнялась каждую секунду.

counter - это ссылка, и каждый раз, когда вызывается invoke, он увеличивается.

Обещание - это Js.Promise.t, который будет разрешен после 4 с. Обратите внимание, что мы ожидаем 4.1s, чтобы убедиться, что последний вызов invoke завершил выполнение. В противном случае мы могли бы выполнить обещание, только если счетчик увеличился только в три раза.

Вы можете использовать |> для цепочки обещаний. В нашем примере, обещание разрешится со значением счетчика через 4 с. Это значение предоставляется в качестве числа функции, переданной в Js.Promise.then_.

оптимизировать

Мы реализовали наши модули Heap и Scheduler аналогично тому, что мы сделали бы в JavaScript. При этом мы снизили производительность функций, работающих в куче, таких как add и extract для O (n).

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

Я создал версию Heap и Dynamic Array, если вы заинтересованы в реализации, однако я думаю, что это выходит за рамки этой статьи. Поэтому сейчас мы сосредоточимся на оптимизации планировщика, вызывая операции, которые стоят O (n) реже.

В планировщике есть два места, где мы вызываем Heap.add и Heap.extract - при добавлении нового задания и при выполнении задания.

Мы не можем помочь Scheduler.add, но мы можем исправить производительность Scheduler.execute. Функция execute не нуждается в вызове extract или add, поскольку размер нашей очереди до и после выполнения должен быть одинаковым.

Давайте введем новую функцию в нашу подпись кучи. lower_root_priority уменьшает приоритет корня кучи. Мы можем использовать эту новую функцию для обновления корневого ключа до следующего времени его вызова без предварительного извлечения заголовка очереди и добавления его обратно с обновленным временем вызова.

выполнить оптимизировано

lower_root_priority принимает новый приоритет для корня, проверяет, чтобы убедиться, что новый приоритет меньше текущего приоритета корня, и делегирует фактическую работу вспомогательной функции update_priority.

уменьшить приоритет корня

update_priority может уменьшить или увеличить приоритет любого элемента в куче в O (log (n)). Он проверяет, нарушает ли новый приоритет свойство max heap по отношению к дочерним элементам узла или его родительскому элементу. Когда мы увеличиваем приоритет узла, мы можем нарушать свойство max heap узла по отношению к его родителю, и поэтому мы исправляем fix_up. Когда мы уменьшаем приоритет узла, мы можем нарушать свойство max heap по отношению к его дочерним элементам, поэтому мы вызываем heapify, чтобы исправить возможное нарушение.

уменьшить приоритет

Следующие шаги

Эта статья - далеко не полный обзор возможностей Reason. Мы видели много языковых конструкций, но не исследовали их подробно. Есть также функции, которые были исключены, такие как функторы и объекты. Я настоятельно рекомендую вам прочитать документацию или Изучение ReasonML и функционального программирования, чтобы узнать, что вам доступно, прежде чем переходить к кодированию.

Полный исходный код того, что мы рассмотрели сегодня, доступен в основной ветке https://github.com/Artris/reason-scheduler.

Если вы хотите попрактиковаться, я рекомендую вам добавить функцию удаления в планировщик. В частности, расширить подпись планировщика с

  • введите jobId и
  • let remove = (t, jobId) => единица

Я также рекомендую вам добавить контрольные примеры для функций, представленных в сигнатуре модулей Heap и Scheduler.

Контрольные примеры для всех функций в модуле Heap и Scheduler, а также реализация функции удаления доступны в ветви решений.

приписывание

Я хотел бы поблагодарить сообщество Reason / BuckleScript за предоставление подробной документации. И доктор Аксель Раушмайер за книгу «Изучение ReasonML» и множество интересных статей о Reason.

Фрагменты кода были созданы с использованием carbon.now.sh.

Я также хотел бы поблагодарить Грейс, Сами, Фримена и Preetpal, которые помогли рецензировать эту статью.