Как да започнете с Причината

В тази статия ще изградим планировчик в Reason. По пътя ще видим как някои от основните характеристики на Reason си взаимодействат помежду си и го правят отлично прилягащ за този проект. Можете да намерите всичко, което покриваме тук, в хранилището.

Повечето статии за Reason показват как работи в ReasonReact. Това има смисъл, тъй като Facebook разработи Reason. В тази статия обаче исках да покажа как Reason свети като език извън ReasonReact.

Тази статия предполага, че имате основно до средно разбиране на JavaScript. Някои познания с функционалното програмиране също не биха навредили.

reason.svg превърнат в png с Imagemagic, пикселиран фон с Imagemagick

Защо да изберем Причината?

Причината е функционален език, който насърчава неизменяемостта, осигурява изведена система от статичен тип и се компилира до JavaScript. Нека разгледаме по-отблизо:

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

Причината носи предимствата на силно въведен език на JavaScript на ниска цена. Определено трябва да прочетете раздела Какво и защо в документацията, тъй като тя предоставя повече контекст на езика и неговите характеристики.

Някои ресурси, които да ви помогнат да започнете

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

В тази статия ще проучим как различните понятия в Причината, като модули, изявления, променливи връзки и неизменяемост, работят заедно. Всеки път, когато въведа нова концепция или синтаксис, ще правя връзка към свързаните документи и статии.

Голямата картина

Този урок е вдъхновен от Node Schedule, планировчик за Node.js, който използва един таймер по всяко време. Можете да научите повече за това как работи График на възлите тук.

Днес ще създадем планировчик в Reason, който използва един таймер по всяко време. Ще използваме нашия планировчик, за да изпълняваме повтарящи се задачи. Този проект е достатъчно голям, за да демонстрира някои от ключовите концепции в Reason.

Голямата картина: P

За да постигнем това, ще дефинираме два модула - Heap и Scheduler.

Heap е изпълнение на опашка с приоритет. Той поддържа задачите в реда, в който следва да бъдат изпълнени. Ключът на елемента от куп е следващото време за извикване на заданието.

Scheduler е съставен от куп и отговаря за актуализирането на таймера и изпълнението на заданията по зададените правила за повторение.

  1. Когато задачата се изпълни, планировникът ще премахне задачата от опашката, изчислява следващото си време на извикване и вмъква задачата обратно на опашката с актуализираното си време на извикване.
  2. Когато се добави нова задача, планиращият проверява следващото време на извикване на root (head / заданието, което ще бъде изпълнено следващото). Ако новата задача трябва да се изпълни преди главата, планировникът актуализира таймера.

Куча модул

API на приоритетна опашка определя:

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

Heap извършва операции за вмъкване и извличане в ред O (log (n)), където n е размерът на опашката.

Забележка: Ще говорим за сложността на алгоритъма в последния раздел на статията. Ако не сте доволни от сложността на алгоритъма, можете да игнорирате последния раздел.

Ако не сте удобни със структурата на данните на Heap или се нуждаете от опресняване, препоръчвам да изгледате следната лекция от курса на MIT OCW 6006. В останалата част от този раздел ще приложим псевдокода, описан в бележките от 6006.

Дефиниране на типовете, използвани от модула за купуване

heapElement

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

Heap.t

t ('a,' b) е друг тип запис и представлява Купата. Това е типът връщане на нашата функция за създаване и последният параметър, предаден на всички останали функции в публичния API на нашия хепа модул.

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

Това е първият път, когато виждаме ref. ref е начинът на Разум за поддържане на мутации. Можете да имате реф на стойност и да я актуализирате, за да посочи нова стойност, като използвате оператора: =.

Масивите в Причината са сменяеми - Можете да актуализирате стойност в конкретен индекс. Те обаче имат фиксирана дължина. За да подпомогнем добавянето и извличането, нашата купчина трябва да се позове на масив от купчини елементи. Ако тук не използваме справка, ще трябва да връщаме нова купа след всяко добавяне и извличане. И модулите, които зависят от грамадата, трябва да следят новата купчина.

Изключение на EmptyQueue

изключение може да бъде разширено с нови конструктори. Ще издигнем изключението EmptyQueue по-късно в функциите за извличане и заглавие в модула за купуване.

Изключения са всички от един и същи тип, exn. Типът exn е нещо като специален случай в системата от типа OCaml. Той е подобен на типовете варианти, които срещахме в Глава 6, Варианти, с изключение на това, че е отворен, което означава, че не е напълно дефиниран на нито едно място. - RealWorldOcaml

Подпис

Heap подпис

По подразбиране всички връзки (присвояване на променливи) в модул са достъпни навсякъде, дори извън модула, където са дефинирани. подпис е механизмът, чрез който можете да скриете специфичната логика за изпълнение и да определите API за модул. Можете да определите подпис във файл със същото име като модула, завършващ с суфикс .rei. Например можете да определите подписа за Heap.re във файла Heap.rei.

Тук излагаме дефиницията на heapElement, така че потребителите на модула Heap да могат да използват стойността, върната с глава и извлечение. Но ние не предоставяме определението за нашия тип купища. Това прави t абстрактен тип, който гарантира, че само функциите в модула Heap могат да консумират грамада и да я трансформират.

Heap инициализатор

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

Помощни функции

Помощни функции

parent е функция, която взема един аргумент - индекс. Той връща None, когато индексът е 0. индекс 0 показва корена на дървото, а коренът на дърво няма родител.

ляво и дясно връщат индекса на лявото и дясното дете на възел.

swap отнема два индекса a и b и опашка за масив. След това разменя стойностите в индекса a и b на опашката.

key просто връща ключовото поле на heapElement в посочения индекс на опашката.

size връща дължината на опашката

Добави

добавянето е една от основните функции, които изложихме в подписа heap. Необходима е стойност и ключ, представляващ приоритета на стойността, която да вмъкнете в опашката. Ще използваме тази функция по-късно в модула Scheduler, за да добавим нови задачи към нашата опашка за изпълнение.

поправям

Нека rec ни позволява да определим рекурсивни функции. С rec можете да се обърнете към името на функцията вътре в функционалното тяло.

Ние дефинирахме ключа като функция, която приема опашка и индекс като аргументи. С декларацията let key = key (опашка) ние засенчваме ключ, като частично прилагаме функционалния клавиш за помощник, който дефинирахме по-рано.

Когато предоставите подмножество от аргументи на функция, тя връща нова функция, която приема останалите аргументи като вход - това е известно като currying.

Аргументите, които сте предоставили, са достъпни за върнатата функция. Тъй като опашката е фиксирана в fix_up, ние частично я прилагаме към ключовата функция, за да направим нашия код по-сух.

Можете да използвате when , за да укажете допълнителни условия при съвпадение на модел. Връзките на стойности в случая са достъпни за израза след това, когато (в нашия пример p_ind е наличен в сравнение (ключ (индекс), ключ (p_ind)). Само когато условието е изпълнено, ние изпълняваме свързания оператор след =>.

добави

добавете свързване на нов елемент в края на опашката. Ако новият елемент има по-висок приоритет от своя родител, той нарушава свойството max heap. fix_up е рекурсивна функция, която възстановява свойството max heap чрез преместване на новия елемент нагоре в дървото (двойно разменяне с неговия родител), докато достигне корена на дървото или приоритетът му е по-нисък от неговия родител.

fix_last е просто увиване около fix_up и го извиква с индекса на последния елемент от опашката.

heap.queue ^ е как осъществяваме достъп до референтните стойности.

[||] е синтаксисът на буквален масив за празен масив.

Екстракт

extraction премахва елемента от най-високия приоритет (в нашия случай елементът с най-малкия ключ) от опашката и го връща. extractor премахва главата на опашката, като първо я замества с последния елемент в масива. Това въвежда единично нарушение на свойството max heap в корена / главата на опашката.

Както е описано в лекцията, натрупването - също известно като пресяване - отстранява едно нарушение. Ако приемем, че левите и десните подредове на възел n удовлетворяват свойството max heap, извикването hepify on n поправя нарушението.

Всеки път, когато се извиква преустановяване, той намира индекса max_priority_index на елемента с най-висок приоритет между heapElements в индекса, вляво (индекс) и вдясно (индекс). Ако max_priority_index не е равен на индекса, знаем, че все още има нарушение на свойството max heap. Разменяме елементите в индекса и max_priority_index, за да отстраним нарушението в индекса. Ние рекурсивно се обаждаме надпис с max_priority_index, за да коригираме възможното нарушение, което бихме могли да създадем чрез размяна на двата елемента.

heapify

index е инт, представляващ корен на поддърво, който нарушава свойството max heap, но неговите подтипове удовлетворяват свойството. сравнение е функцията за сравнение, определена с грамадата. queue е масив, който съдържа елементите на купчината.

ако изразите в Reason като другите изрази оценяват на стойност. Тук операторите if оценяват до int, който представлява кой индекс е бил по-малък в сравнение.

екстракт

шаблон за извличане съвпада с опашката (масивът не е референцията).

[| head |] съвпада само с масив с един елемент.

Когато опашката е празна [||], ние повдигаме изключението EmptyQueue, което дефинирахме по-рано. Но защо? Защо вместо това не върнем None? Ами това е въпрос на предпочитание. Предпочитам да издигна изключение, защото когато използвам тази функция, ще получа heapElement, а не опция (heapElement). Това ми спестява съвпадение на образец спрямо върнатата стойност на екстракта. Предпочитанието е, че трябва да внимавате, когато използвате тази функция, като се уверите, че опашката никога не е празна.

Когато имаме повече от един елемент, разменяме първия и последния елемент от опашката, премахваме последния елемент и извикваме hepify на първия елемент (коренът на дървото).

Тестване

Ние използваме 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-зависимости във вашия bsconfig.json. В противен случай BuckleScript няма да намери модула Jest и изграждането ви ще се провали.

Ако пишете тестовите си случаи в директория, различна от src, трябва да го посочите в източниците в bsconfig.json за компилатора BuckleScript, за да ги вземете.

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

С инсталиран модул Heap и инсталиран Jest, ние сме готови да напишем първия си тестов случай.

За да тестваме нашия модул Heap, ще направим сортиране на купчина.

  1. създайте грамада
  2. вмъкнете елементи в грамадата
  3. използвайте операцията за извличане, за да премахнете елементите във възходящ ред
Тест за сортиране на купчина

open Jest отваря модула, за да можем да се позоваваме на връзките, налични в модула Jest, без да ги предварително с Jest. Например, вместо да пишем Jest.expect, можем просто да пишем очакваме.

Използваме let {value: e1} =, за да унищожим стойността, върната чрез екстракт, и да създадем псевдоним e1 за стойност - e1 вече е обвързан с полето на стойността на стойността, върната чрез екстракт.

С |> тръбния оператор можем да създадем композитна функция и да приложим получената функция веднага на вход. Тук просто предаваме резултата от повикване на очаквайте с (e1, ..., e9) към функцията toEqual.

Модул за планиране

Scheduler използва модула Heap, за да поддържа списък на повтарящи се задачи, сортирани по следващото време на извикване.

Да определим типовете, използвани в модула Scheduler

повтаряне

рецидивите са тип Вариант. Всяка стойност от типа на повторение може да бъде или секунда, минута или час. Второ, минута и час са конструкторите за повторението. Можете да извикате конструктор като нормална функция и да получите обратно стойност от типа Variant. В нашия случай, ако извикате Second с int, получавате обратно стойност на рецидивиране на типа. Можете да нагласите тази стойност с Second (number_of_seconds), за да получите достъп до аргумента, предаден на втория конструктор.

работа

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

Scheduler.t

t е тип запис, представляващ планиращия. Планировчик се задържа на опашка от задания, подредени по време на следващото им време за извикване. timer_id препраща timerId за първата задача от опашката - заданието, която ще бъде извикана първо.

Interop

Можете да извиквате JavaScript функции от Reason. Има различни начини за това:

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

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

Използването на връзки на bucklescript е точно същото като използването на дефинирани от потребителя модули. Можете да прочетете повече за наличните връзки тук. В останалата част от този раздел ще се съсредоточим върху външните и [% сурови ...].

външен

С външен можете да свържете променлива към функция на JavaScript. Тук например свързваме променливата setTimeout към глобалната функция setTimeout на JavaScript.

дефиниция setTimeout и clearTimeout в документи на BuckleScript

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

[% сурово…]

нов Date.getTime () в JavaScript връща цяло число. Числата в JavaScript са дълги 64 бита. int в Причината са дълги само 32 бита. Това е проблем!

В Reason можем да работим с върнатата стойност на нов Date.getTime (), като очакваме да бъде Float. Това всъщност е очакваният тип връщане на Js.Date.getTime, предоставен от BuckleScript.

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

работа със JavaScript стойности

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

time_now връща броя на милисекундите от епохата.

Използваме сума, за да изчислим следващото време за извикване на дадена задача, като предадем резултата от time_now и int, представляващ колко милисекунди от сега заданието трябва да бъде изпълнено.

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

has_higher_priority сравнява две времена на извикване. Това е функцията за сравнение, която използваме за инициализиране на нашата Heap.

призоваване

Във всеки момент имаме само един таймер, който изтича, когато трябва да се изпълни първата задача от опашката. Когато таймерът изтече, трябва да направим малко почистване. Когато таймерът изтече, би трябвало

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

изчакването отнема период - стойност на рецидивиране на типа - и връща int, представляващ колко мили секунди дадена задача трябва да изчака, преди да бъде изпълнена отново. Предаваме стойността, върната с изчакване, към setTimeout.

next_invocation изчислява следващото време за извикване на работа. time_now връща дълга стойност. сумата взема дълга и int стойност и връща дълга стойност. sum добавя двата номера, като се обажда на JavaScript + оператора на своите аргументи.

Извикване на работа

Execute е рекурсивна функция, която е отговорна за изпълнението на работата и извършването на почистването. Той улавя програмиста при затваряне и връща функция, която може да бъде извикана, когато таймерът изтече.

В първите три реда премахваме заданието с най-висок приоритет (най-нисък ключ или най-близко време за извикване) и го вмъкваме обратно в опашката със следващото време за извикване.

След това продължаваме да създаваме нов таймер за задачата в главата на опашката (следващата задача, която трябва да бъде изпълнена след това извикване). Ние актуализираме референцията timer_id, за да сочи към новия timerId.

Накрая извикваме полето за извикване на задачата за изпълнение на зададената задача.

Добавете нова работа

добавяне на нова работа

Когато опашката е празна, добавянето на нова задача е просто. Ние създаваме таймер, който изтича в следващото време на извикване на заданието.

По-интересният случай е, когато опашката не е празна! Тук можем да имаме две ситуации. Или главата на опашката има ключ, по-голям от следващото време за извикване на заданието, или не.

Първият случай е, когато главата на опашката има ключ, по-малък или равен на следващото време на извикване на заданието. Това е случаят, когато новата задача трябва да бъде изпълнена преди текущия таймер. В този случай трябва да отменим таймера, като се обадим на clearTimeout с timer_id и да създадем нов таймер, който ще изтече в следващото време на извикване на новата задача.

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

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

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

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

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

За да направим това ще го направим

  1. добавете задача към планиращия да се изпълнява всяка секунда. Тази работа увеличава ref (int) брояч.
  2. създайте обещание, което се разрешава след 4s
  3. върнете обещание от Jest.assertion, което очаква броячът да бъде увеличен 4 пъти.
Добавяне на тестов график

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

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

броячът е ref и всеки извикване при извикване се увеличава.

обещанието е Js.Promise.t, което ще бъде разрешено след 4s. Забележете, че чакаме 4.1 секунди, за да се уверим, че последното извикване на извикването е приключило. В противен случай можем да разрешим обещанието, когато увеличихме брояча само три пъти.

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

оптимизирам

Ние внедрихме нашите Heap и Scheduler модули, подобни на това, което бихме направили в JavaScript. По този начин ние намалихме работата на функциите, работещи на купчината, като добавяне и извличане в O (n).

Знаем, че Array в Reason има фиксирана дължина. Всеки път, когато добавим нова работа или изтрием такава, размерът на нашия масив ще се променя и следователно ще се създаде ново копие. Можем да поправим това, като създадем модул за динамичен масив, който реализира удвояване на таблицата.

Създадох версия на Heap и Dynamic Array, ако се интересувате от внедряването, но мисля, че това ще е извън обхвата на тази статия. Затова засега се фокусираме върху оптимизирането на Scheduler, като извикваме операции, които струват O (n) по-рядко.

Има две места в Scheduler, където наричаме Heap.add и Heap.extract - при добавяне на нова работа и при изпълнение на работа.

Не можем да помогнем на Scheduler.add, но можем да оправим изпълнението на Scheduler.execute. Функцията за изпълнение не е необходимо да извиква извличане или добавяне, тъй като размерът на нашата опашка преди и след изпълнението трябва да е еднакъв.

Нека въведем нова функция в нашия Heap подпис. smanjenje_root_priority намалява приоритета на корена на Heap. Можем да използваме тази нова функция, за да актуализираме коренния ключ до следващото му време на извикване, без първо да извадим главата на опашката и да я добавим обратно с актуализираното си време на извикване.

изпълнява оптимизиран

drop_root_priority взема новия приоритет за root, проверява дали новият приоритет е по-малък от текущия приоритет на root и делегира действителната работа на помощната функция update_priority.

намаляване на приоритета на корен

update_priority може да намали или увеличи приоритета на всеки елемент в Heap in O (log (n)). Той проверява дали новият приоритет нарушава свойството max heap по отношение на децата на възел или неговия родител. Когато увеличим приоритета на възел, може да нарушим свойството max heap на възела по отношение на неговия родител и така ние fix_up. Когато намалим приоритета на даден възел, може да нарушим свойството max heap по отношение на неговите деца и затова призоваваме hepify да отстраним възможното нарушение.

намаляване на приоритета

Следващи стъпки

Тази статия далеч не е пълен преглед на характеристиките на Reason. Видяхме много от езиковите конструкции, но не сме ги проучили подробно. Има и функции, които са останали, като функтори и обекти. Горещо ви препоръчвам да прочетете документацията или Exploring ReasonML и функционалното програмиране, за да знаете какво е достъпно за вас, преди да преминете към кодиране.

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

Ако искате да практикувате, препоръчвам ви да добавите функционалност за премахване към планировчика. По-конкретно, разширете подписа на Scheduler с

  • тип работаId и
  • нека премахнете = (t, jobId) => единица

Насърчавам ви също да добавите тестови случаи за функциите, разкрити в подписа на модулите Heap и Scheduler.

Тестовите случаи за всички функции в модула Heap и Scheduler, както и реализация за функционалността за премахване, са достъпни в клона с решения.

приписване

Искам да благодаря на общността Reason / BuckleScript за предоставяне на подробна документация. И д-р Аксел Раушмайер за книга за изследване на ReasonML и много интересни статии за Reason.

Кодови фрагменти бяха генерирани с помощта на carbon.now.sh.

Искам също така да благодаря на Грейс, Сами, Фрийман и Преетпал, които помогнаха за преразглеждането на тази статия.