Ейдзіро Суміі, Університет Токіо, 2005
- Що це?
- Makefile проєкту MinCaml
- Головна програма
- Синтаксис і типи MinCaml
- Політика компіляції
- Лексичний аналіз
- Парсер
- Вивід типів
- K-нормалізація
- α-конверсія
- β-редукція
- Редукція вкладених let
- Inline експансія
- Згортка констант
- Елімінація необов'язкових дефініцій
- Конверсія вкладених функцій
- Генерація байткоду і компіляція бінарного коду
- Оптимізація безпосередніх операндів
- Алокація регістрів
- Генерація асемблерного коду
Цей документ є підручником з описом MinCaml, компілятора підмножини мови програмування ML. Компілятор MinCaml розроблено в дослідницькому програмному проекті «Красивий компілятор ML у Японії» з метою популяризації простої та потужної мови програмування ML і розриву негативної спіралі «Я не використовую ML, тому що я не знаю ML». Він реалізований на мета мові ML під назвою Objective Caml. Оскільки цей підручник передбачає певний досвід програмування ML як передумову, будь ласка, спочатку подивіться «Programmin in ML» Роберта Харпера.
[Застереження: цей підручник англійською мовою є попереднім перекладом японської версії та все ще може мати багато недоліків, як технічно, так і лінгвістично. Академічна стаття більш повна.]
[Оновлення від 17 вересня 2008 р.: тепер підтримується PowerPC (на додаток до SPARC), завдяки пані Масуко та професору Асаї з університету Очаномідзу. Ви повинні виконати ./to_ppc або ./to_sparc перед make.]
[Ще одне оновлення від 17 вересня 2008 р.: розподільник регістрів тепер використовує простіший алгоритм. У попередніх версіях відсутнє зворотне відстеження (ToSpill і NoSpill).]
[Оновлення від 27 серпня 2012 р.: тепер підтримується x86 із SSE2 (Pentium 4 або новіша версія). Будь ласка, виконайте ./to_x86 перед make.]
Після завантаження компілятора MinCaml перегляньте його Makefile. Тут описано, як скомпілювати сам MinCaml.
Makefile MinCaml використовує зручний інструмент під назвою OCamlMakefile (рядок містить OCamlMakefile внизу). Просто перерахувавши файли, необхідні для MinCaml у рядку SOURCES = ..., ви можете створити байт-код інтерпретатор min-caml, виконавши команду "make byte-code". Подібним чином ви можете отримати нативний код min-caml.opt за допомогою "make native-code". Крім того, "make top" створює інтерактивне середовище OCaml верхнього рівня min-caml.top, де за замовчуванням завантажуються модулі MinCaml. Це зручно для дебага та експериментів.
Makefile MinCaml також має функцію автоматичного тестування. Помістіть код ML "program-name.ml" у каталог test, напишіть назву програми в рядку TESTS = ... і запустіть "make do_test". Потім результат, створений OCaml (назва-програми.ans) і результат (назва-програми.res) збірки, згенерованої MinCaml (назва-програми.s), автоматично порівнюються, а їх різниця виводиться в "назва-програми.cmp". Зазвичай він порожній, тому що не повинно бути ніякої різниці, поки компіляція та виконання вдалися.
Вам потрібне середовище SPARC з компілятором gcc і асемблером для виконання скомпільованої програми. Однак це не обов'язково для простого створення збірки SPARC.
Далі подивіться на основну програму MinCaml main.ml. Виконання компілятора починається з його низу let () = ....
По-перше, ми обробляємо параметри за допомогою стандартної бібліотеки Arg OCaml. Параметр -inline вказує максимальний розмір функцій, які будуть вбудовані, а -iter визначає максимальну кількість оптимізацій для ітерації. (Деталі будуть пояснені пізніше.)
Інші аргументи командного рядка вважаються іменами програм, які збираються. Функція Main.file генерує збірку SPARC "назва-програми.s" із джерела ML «назва-програми.ml».
Для налагодження та експериментів також надається функція Main.string, яка компілює рядковий аргумент і відображає результат у стандартному виводі.
Ядром main.ml є функція Main.lexbuf. За наявності аргументу буфера він застосовується в такому порядку: лексичний аналіз (Lexer.token), аналіз (Parser.exp), визначення типу (Typing.f), K-нормалізація (KNormal.f), α-перетворення (Alpha.f). ), оптимізації (iter), перетворення закриття (Closure.f), генерація коду віртуальної машини (Virtual.f), 13-розрядна негайна оптимізація SPARC (Simm13.f), розподіл реєстрів (RegAlloc.f) і генерація складання (Emit) .f).
Функція оптимізації iter повторює наступні п’ять оптимізацій, доки її результат не перестане змінюватися або кількість ітерацій не досягне верхньої межі, визначеної -iter: β-зменшення (Beta.f), зменшення вкладеного let (Assoc.f), вбудоване розширення (Inline.f), постійне згортання (ConstFold.f) і видалення непотрібних визначень (Elim.f).
Незабаром ми пояснимо подробиці цих перекладів і оптимізацій.
MinCaml є підмножиною ML. За винятком деяких деталей, таких як пріоритет і круглі дужки, він має такий синтаксис.
e ::= вирази
| c — константи
| op(e1, ..., en) — примітивні операції
| if e1 then e2 else e3 — умовні гілки
| let x = e1 in e2 — визначеннях змінних
| x — змінних
| let rec x y1 ... yn = e1 in e2 — визначення функції e2 (взаємно рекурсивні)
| e e1 ... en — функціональні програми
| (e1, ..., en) — створення кортежу
| let (x1,..., xn) = e1 in e2 — читання з кортежів
| Array.create e1 e2 — створення масиву
| e1.(e2) — читання з масивів
| e1.(e2) <- e3 — запис в масиви
Він виражається як тип даних ML Syntax.t у модулі syntax.ml. Вирази (такі як let і let rec), що визначають нові змінні, також включають їх типи, які не показані вище. Ці типи виражаються Type.t, визначеним у type.ml.
T ::= типи
| π — примітивні типи
| T1 -> ... -> Tn -> T — типи функцій
| T1 * ... * Tn — типів кортежів
| T array — типи масивів
| α — змінні типу α
Останні «змінні типу» будуть використані для визначення типу.
До речі, компілятор MinCaml не підтримує автоматично так зване часткове застосування функцій каррі. Тобто кожна функція потребує всіх аргументів одночасно. Якщо ви бажаєте часткового застосування, вам потрібно визначити проміжну функцію вручну, наприклад let rec f_123 x = f 123 x у f_123. (Якщо ви знаєте мову Scheme, вона схожа в цьому відношенні.)
Також немає «посилальних комірок», необхідних для імперативного програмування, але їх можна замінити масивами лише з одним елементом. Зокрема, ref e можна замінити на Array.create 1 e, !e на e.(0), а e1 := e2 на e1.(0) <- e2.
Загалом компіляція означає переклад програм з мови високого рівня на мову нижчого рівня. Наприклад, наведена нижче функція MinCaml, яка обчислює найбільший спільний дільник двох невід'ємних цілих чисел,
let rec gcd m n =
if m = 0 then n else
if m <= n then gcd m (n - m) else
gcd n (m - n)
компілюється в наступну збірку SPARC.
gcd.7:
cmp %i2, 0
bne be_else.18
nop
mov %i3, %i2
retl
nop
be_else.18:
cmp %i2, %i3
bg ble_else.19
nop
sub %i3, %i2, %i3
b gcd.7
nop
ble_else.19:
sub %i2, %i3, %o5
mov %i3, %i2
mov %o5, %i3
b gcd.7
nop
На перший погляд, між двома мовами існує величезна прірва. Компілятор MinCaml усуває цю прогалину, визначаючи відповідні проміжні мови та застосовуючи прості переклади один за іншим. Основні п’ять прогалин між складанням MinCaml і SPARC:
Типи. MinCaml має типи та перевірку типів, але збірка не має такого механізму. Вкладені вирази. У MinCaml ви можете писати скільки завгодно складні вирази, наприклад 1+2-(3+(4-5)), але збірка може виконувати лише одну операцію за однією інструкцією. Визначення вкладених функцій. У MinCaml ви можете визначити функцію всередині іншої функції, наприклад
let rec make_adder x =
let rec adder y = x + y in
adder in (make_adder 3) 7
але збірка має лише "мітки" верхнього рівня.
MinCaml має такі структури даних, як кортежі та масиви, а асемблер або машинні кода — ні. У MinCaml ви можете використовувати скільки завгодно змінних, але лише обмежена кількість регістрів може використовуватися в асемблері. Щоб подолати ці прогалини, MinCaml застосовує такі перетворення, як
Вивід типів К-нормалізація Конверсія функцій Генерація коду віртуальної машини Алокація регістрів
в такому порядку. Далі ми пояснимо ці переклади та оптимізацію.
Якщо дивитися з комп’ютера, то навіть програми ML – це лише послідовності символів. Наприклад, попередня програма gcd виглядає так:
l e t r e c g c d m n = ...
Оскільки ми не можемо нічого зробити з таким рядком, як він є, ми спочатку розділяємо його на лексеми, такі як:
let rec gcd m n = ...
Цей процес називається лексичним аналізом.
Хоча існує багато методів лексичного аналізу, ми тут використовуємо інструмент під назвою ocamllex, який розроблено для лексичного аналізу в OCaml. Файл lexer.mll. Ми залишаємо деталі ocamllex у його посібнику та пояснюємо лише основні моменти. Ми записуємо список правил, таких як
| "-"? digit+
{ INT(int_of_string (Lexing.lexeme lexbuf))}
у синтаксисі, подібному до шаблону, що означає, що "якщо
рядок збігається з регулярним виразом '-'? digit+,
поверніть маркер INT." Тип даних токенів (наприклад, INT)
визначається в parser.mly, який пояснюється далі. Фразу
Lexing.lexeme lexbuf можна розглядати як «магічне заклинання»,
що означає рядок, що аналізується.
Тепер, коли виконується лексичний аналіз, замість рядків, як
1 2 3 - 4 5 6 + 7 8 9
ми маємо такі послідовності токенів, як
123 - 456 + 789.
Однак ми все ще не можемо виконати будь-яку високорівневу обробку такої плоскої послідовності, як вище. Наприклад, ми маємо розпізнати «123-456+789» як «(123-456)+789», а не «123-(456+789)». З точки зору типу даних Syntax.t, визначеного в syntax.ml, нам потрібне дерево розбору на зразок:
Add (Sub (Int 123, Int 456), Int 789)
Цей процес перекладу послідовності токенів у дерево аналізу називається синтаксичним аналізом. Компілятор MinCaml використовує інструмент під назвою ocamlyacc для реалізації синтаксичного аналізу у файлі parser.mly.
Вміст parser.mly більш-менш схожий на вміст lexer.mll. У ньому наведено список відповідності шаблонів із послідовностей токенів для розбору дерев, наприклад:
| exp PLUS exp { Add($1, $3) }
$1 і $3 означають перший і третій синтаксичні елементи (обидва в цьому випадку є exp).
Це визначення синтаксису майже таке ж, як і раніше описані вирази e, але один момент потребує обережності. У ML застосування функції позначається лише послідовністю виразів. Отже, якщо ви пишете x - y, незрозуміло, чи ви віднімаєте ціле число y від цілого числа x, чи застосовуєте функцію x до аргументу -y! Таким чином, ми відрізняємо прості вирази simple_exp, які можуть бути аргументами функції без додаткових дужок, від загальних виразів exp. Наприклад, оскільки -y не є простим_виразом, попередній вираз, як відомо, є цілим відніманням, а не застосуванням функції.
parser.mly також визначає пріоритет різних синтаксичних і бінарних операторів, а також тип даних токенів, згаданих у lexer.mll.
До речі, щоразу, коли потрібен тип змінної (як у let), він надається новою, невизначеною змінною типу Var(ref None) на даний момент. Цей момент буде пояснено далі в висновку типу.
Як і в звичайному ML, MinCaml визначає типи змінних і функцій, навіть якщо вони не записані в програмі. Ця функція називається виведенням типу. Виведення типу загалом дуже корисне для програм із поліморфними функціями та функціями вищого порядку зокрема (хоча сам MinCaml є мономорфним, як зазначено синтаксисом типів).
Основою виведення типу в MinCaml є функція Typing.g. Ця функція приймає середовище типу env (відображення імен змінних у їхні типи) і вираз e та повертає виведений тип e. Він також перевіряє типи підвиразів. Якщо знайдено змінну невизначеного типу, вона замінюється на відповідний тип. Ця перевірка та підстановка реалізуються функцією Typing.unify.
Наприклад, у випадку цілочисельного додавання e1 + e2 (або Add(e1,e2) у термінах Syntax.t), ми спочатку визначаємо тип підвиразу e1 за допомогою g env e1, який перевіряється на int за допомогою unify. Те саме для e2. Потім ми повертаємо int як тип усього виразу.
Трохи складнішим випадком є застосування функції e e1 ... en, де e — функція, а від e1 до en — її аргументи. У цьому випадку тип функції можна визначити за допомогою g env e, а типи аргументів — за допомогою g env e1 до g env en, але тип результату – ні. Таким чином, ми створюємо нову невизначену змінну типу t і викликаємо unify, щоб g env e дорівнював типу функції від g env e1, ..., g env en до t. Потім ми повертаємо t як тип усього виразу.
Коли вводиться нова змінна, як у let і let rec, середовище типу env розширюється. І навпаки, коли з’являється змінна x, її тип визначається пошуком env. Однак, коли змінна не знайдена в середовищі типу, вона розглядається як зовнішня змінна, їй призначається нова невизначена змінна типу та додається до спеціального середовища типу extenv для зовнішніх змінних. Ця функція є специфічною для MinCaml і недоступна у звичайному ML. Завдяки цьому зовнішні змінні можна використовувати без оголошення.
Функція Typing.unify рекурсивно перевіряє, чи є два дані типи рівними, і, якщо один із типів є невизначеною змінною типу Type.var(ref None), замінює її іншим типом, щоб вони стали рівними. Однак перед цією заміною перевіряється, чи з’являється змінна типу всередині іншого типу. Цей процес називається перевіркою виникнення. Це необхідно для того, щоб отриманий тип не мав циклу. Наприклад, якщо ми об'єднаємо змінну типу α (без перевірки) із функціональним типом int->α, результатом буде нескінченний тип, наприклад int->int->int->..., оскільки α = int->α ! Щоб запобігти таким випадкам, необхідна перевірка, навіть якщо спочатку це може здатися загадковим.
Після завершення визначення типу (чи через помилку типу, чи через звичайне завершення) Typing.deref_typ замінює всі змінні типу їхнім вмістом для спрощення. Змінні типу, які ще не визначені, за бажанням замінюються на int. Ця функція також властива MinCaml.
Ми вже сказали, що «компіляція — це подолання розривів між мовою високого рівня та мовою низького рівня», однією з яких є «вкладені вирази». Наприклад, ML (як і більшість мов) може відразу обчислювати значення таких виразів, як a + b + c - d, але звичайний асемблер а не має таких інструкцій.
Ця прогалина подолана трансформацією під назвою K-нормалізація, яка визначає кожен проміжний результат обчислення як змінну. (Назва K-нормалізація походить від компілятора під назвою ML Kit.) Наприклад, попередній вираз можна перекласти так:
let tmp1 = a + b in
let tmp2 = tmp1 + c in
tmp2 - d
У MinCaml KNormal.g є ядром K-нормалізації, а KNormal.t є типом даних K-нормалізованих виразів (так звані K-нормальні форми). KNormal.g приймає вираз перед K-нормалізацією з типом середовища env і повертає вираз після K-нормалізації в парі з його типом. (Типи передаються лише для анотування визначень змінних у let і не є центральними для суті K-нормалізації.)
Наприклад, у випадку e1 + e2, e1 спочатку K-нормалізується g env e1, результат якого прив'язується let до змінної x. Тоді e2 також K-нормалізується за допомогою g env e2, результат якого прив’язаний за допомогою let до змінної y, а вираз x + y повертається з типом int.
Щоб вставити такий let, ми використовуємо допоміжну функцію під назвою insert_let. Вона приймає вираз e, створює нову змінну x і повертає вираз let x = e in ... (хоча, якщо e є змінною в першу чергу, insert_let використовує цю змінну як x і не вставляє let насправді). Вона також використовує функцію «продовження» k, застосовує її до x і використовує її результат для виразу після in (тіло «...» вище).
До речі, окрім K-нормалізації, KNormal.g також перетворює логічні значення true та false у цілі числа 1 та 0. Крім того, порівняння та умовні розгалуження переводяться у комбіновані форми, як if e1 <= e2 then e3 else e4 з окремих такі форми, як e1 <= e2 і якщо e, то e1, інакше e2. Цей переклад заповнює одну з прогалин між MinCaml і звичайною збіркою, де порівняння та розгалуження поєднуються. Якщо умова e не є порівнянням, вона перекладається на порівняння, якщо e <> 0, тоді e1 else e2. Крім того, перекладаючи if (не e) then e1 else e2 на if e then e2 else e1 тощо, усі булеві вирази та умовні розгалуження опиняються в будь-якій із двох форм
if e1 = e2, then e3, else e4
і
if e1 <= e2, then e3, else e4.
Це перетворення відрізняється від K-нормалізації, але реалізовано разом із KNormal.g лише тому, що їх розділення вимагає додаткової роботи для визначення проміжного типу даних.
Крім того, використання зовнішніх змінних обмежується викликами зовнішніх функцій (KNormal.ExtFunApp) або посиланнями на зовнішні масиви (KNormal.ExtArray), оскільки вони необхідні й достатні для більшості програм. Це обмеження також реалізується разом з K-нормалізація.
Тепер, коли K-нормалізація завершена, ми переходимо до оптимізацій, але перед ними виконуємо α-перетворення, яке присвоює різні імена різним змінним. Це перетворення є необхідним, оскільки різні змінні з однаковими іменами ускладнюють різні процеси. Наприклад, він перетворює вираз let x = 123 in let x = 456 in x + x в наступний вираз: let x1 = 123 у let x2 = 456 у x2 + x2.
α-перетворення реалізовано в Alpha.g. Воно бере неперекладений вираз e з відображенням env з неперекладених імен змінних на перекладені імена змінних і повертає перекладений вираз. Наприклад, у випадку виразу let x = e1 in e2 ми спочатку транслюємо e1, створюємо нову змінну x', додаємо до env відображення x у x' і транслюємо e2. Цей процес також подібний у випадках let rec і LetTuple, хоча вони можуть здаватися більш складними.
До речі, зовнішні змінні не α-перетворюються, оскільки вони не зареєстровані в env (див. функцію Alpha.find). Така поведінка є навмисною: зв'язування (лінкінг) не працюватиме, якщо змінити назви зовнішніх змінних.
Почнемо з прикладу: якщо існує такий вираз, як let x = y in x + y, очевидно, що x дорівнює y, тому ми можемо замінити весь вираз let на y + y. Такий переклад називається β-редукцією K-нормальних форм. (Термін β-редукція походить від іншої системи під назвою λ-числення, окремим випадком якої є наша.) Це не завжди необхідно у звичайних програмах, але іноді ефективне після інших оптимізацій.
У MinCaml функція Beta.g є ядром β-редукції. Вона приймає вираз e із відображенням env зі змінних на еквівалентні змінні по змісту та повертає β-редукований вираз. Знову ж таки, важливим випадком є x = e1 in e2, де ми спочатку β-редукуємл e1 і, якщо результатом є змінна y, додаємо до env відображення з x на y перед наступною β-редукцією e2. І якщо ми зустрічаємо змінну x, ми шукаємо в env і замінюємо x на змінну y. Оскільки змінні з’являються скрізь у K-нормальних формах, функція find визначена та використовується для цієї заміни.
Далі, з метою покращення вигляду виразів, ми зводимо вкладений let від let x = (let y = e1 in e2) in e3 до let y = e1 в let x = e2 in e3. Ця «редукція» не впливає (прямо) на ефективність програм, скомпільованих MinCaml, але полегшує вам розуміння проміжного коду під час налагодження та експериментів.
Цю трансформацію реалізує Assoc.f. Для виразів у формі let x = e1 in e2 ми спочатку зводимо e1 до e1' і e2 до e2' шляхом рекурсії. Тоді, якщо e1' схоже на let ... в e, ми повертаємо вираз let ... в let x = e in e2'. Реалізація трохи складна, але проста, коли вона закінчена. (assoc.ml містить лише 21 рядок.)
Найефективнішою є наступна оптимізація: вбудоване розширення. Вона замінює виклики невеликих функцій їхніми тілами. MinCaml реалізує це у функції Inline.g.
По-перше, у випадку визначення функції, let rec f x1 ... xn = e in ..., ми обчислюємо розмір тіла e функції f за допомогою Inline.size. Якщо цей розмір менший за цілочисельне посилання Inline.threshold, ми додаємо відповідність від імені функції f до формальних аргументів x1, ..., xn і тіла e у відображенні env. Тоді, у випадку виклику функції f y1 ... yn, ми шукаємо формальні аргументи x1, ..., xn тіла f із відображення env і повертаємо e із заміною x1, ..., xn через y1, ..., yn.
Однак, оскільки вбудовані вирази є копіями тіл функцій, їхні змінні можуть бути продубльовані, а отже, повинні бути знову α-перетеворені. Випадково чи ні, попередній процес «заміни формальних аргументів фактичними аргументами» може бути здійснений Alpha.g разом із α-перетворенням, просто використовуючи відповідність від x1, ..., xn до y1, ..., yn (замість порожнього відображення) як початкове відображення env.
Коли функції вбудовані, багато операцій мають аргументи, значення яких уже відомі, наприклад, x + y, let x = 3, let y = 7, x + y. Константне згортання виконує такі обчислення під час компіляції та замінює їх константами на зразок «10». MinCaml реалізує це у функції ConstFold.g.
ConstFold.g приймає вираз e із відображенням env зі змінних на їхні значення та повертає вираз після постійного згортання. Наприклад, враховуючи ціле додавання x + y, перевіряється, чи є значення x і y цілими константами. Якщо так, він обчислює та негайно повертає результат. І навпаки, дане визначення змінної let x = e у ..., воно додає до env відображення від x до e. Цей процес подібний не лише для цілих чисел, а й для чисел із плаваючою комою та кортежів.
Після постійного згортання ми часто знаходимо невикористані визначення змінних (та визначення функцій), як-от x і y, у let x = 3 in let y = 7 in 10. MinCaml видаляє їх за допомогою Elim.f.
Загалом, якщо e1 не має побічного ефекту і x не відображається в e2, ми можемо замінити нехай x = e1 в e2 просто на e2. Наявність «побічних ефектів» перевіряє Elim.effect, а поява змінних перевіряє KNormal.fv. Однак, оскільки неможливо вирішити, чи має вираз реальний побічний ефект, ми розглядаємо будь-який запис у масиви та будь-який виклик функцій як можливі побічні ефекти.
До речі, функція KNormal.fv названа на честь терміна вільні змінні. Наприклад, вираз let x = 3 у x + y має дві змінні x і y, де x називається зв’язаною змінною, оскільки вона визначена як (або зв’язана з) цілим числом 3, тоді як y називається вільною, оскільки вона не зв’язана.
Інша прогалина, яка все ще залишається між MinCaml і асемблером, це «визначення вкладених функцій», які згладжуються перетворенням замикання. Це один із найважливіших процесів під час компіляції функціональних мов.
Це зведення визначень вкладених функцій включає прості випадки та важкі випадки. Наприклад,
let rec quad x =
let rec dbl x = x + x in
dbl (dbl x) in
quad 123
можна сплющити як
let rec dbl x = x + x in
let rec quad x = dbl (dbl x) in
quad 123
просто перемістивши визначення функції. Однак подібна маніпуляція перетворить
let rec make_adder x = let rec adder y = x + y in adder in (make_adder 3) 7
в безглузду програму
let rec adder y = x + y in let rec make_adder x = adder in (make_adder 3) 7.
Це тому, що функція dbl не має вільної змінної, а adder має вільну змінну x.
Таким чином, щоб звести визначення функцій із вільними змінними, ми повинні обробляти не лише тіла функцій, як-от суматор, але й значення їхніх вільних змінних, як-от x, разом. Це як
let rec adder x y = x + y in
let rec make_adder x = (adder, x) in
let (f, fv) = make_adder 3 in
f fv 7
у псевдокоді стилю ML. По-перше, функція adder приймає значення вільної змінної x як аргумент. Потім, коли функція adder повертається як значення, її тіло поєднується зі значенням її вільної змінної, наприклад (adder, x). Ця пара називається замиканням функції. Під час виклику функції суматора її тіло f і значення fv її вільної змінної витягуються та надаються як аргументи.
Перетворення закриття стає складним, коли йдеться про те, «які функції потребують закриття, а які функції можна викликати звичайними способами». Найпростішим рішенням є створення замикань для всіх функцій, але воно надто неефективне.
Таким чином, перетворення замикання Closure.g MinCaml бере відомий набір функцій, які, як відомо, «не мають вільних змінних і можуть бути викликані звичайними способами», і перетворює вираз замиканням. (Він також приймає тип середовища env на додаток до виразу та відомого.)
Результати перетворення замикання представлені в типі даних Closure.t. Він схожий на KNormal.t K-нормальних форм, але має MakeCls створення замикання та функцію верхнього рівня, встановлену на верхній рівень, замість визначень вкладених функцій. Крім того, замість загальних викликів функцій він має виклики функцій AppCls на основі закриття та виклики функцій верхнього рівня AppDir, які не використовують закриття. Крім того, у наступних процесах тип даних Id.l імен функцій (міток) верхнього рівня відрізняються від типу даних Id.t імен змінних. Зауважте, що AppCls використовує змінні, а AppDir — мітки. Це тому, що замикання прив’язані до змінних (за допомогою MakeCls), тоді як функції верхнього рівня викликаються через мітки.
У випадку загального виклику функції x y1 ... yn, Closure.g перевіряє, чи належить функція x до відомого набору. Якщо так, повертається AppDir. Якщо ні, він повертає AppCls.
Визначення функцій, наприклад let rec x y1 ... yn = e1 в e2, обробляються наступним чином. Спочатку ми припускаємо, що функція x не має вільної змінної, додаємо її до відомої та замикаємо її тіло e1. Тоді, якщо x справді не має вільної змінної, продовжуйте процес і перетворюйте e2 замиканням. В іншому випадку ми перемотуємо значення встановленого відомого та посилального верхнього рівня та повторюємо перетворення закриття e1. Нарешті, якщо x ніколи не з’являється в e2 як змінна (а не як мітка), ми усуваємо генерацію закриття MakeCls.
Остання частина може потребувати доопрацювання. Навіть якщо x не має вільної змінної, якщо вона повертається як значення на зразок let rec x y1 ... yn = ... в x, її закриття має бути згенеровано. Це тому, що користувач, який отримує x як значення, взагалі не знає, чи є у нього вільна змінна чи ні, і тому в будь-якому випадку повинен використовувати AppCls (а не AppDir), щоб викликати функцію через її закриття. У цьому випадку ми не усуваємо MakeCls, оскільки x відображається в e2 як змінна. Однак, якщо x просто викликається як функція, наприклад let rec x y = ... in x 123, вона відображається лише як мітка в AppDir (а не як змінна), тому ми виключаємо MakeCls.
Після перетворення вкладених функцій ми згенеруємо SPARC асемблер. Однак, оскільки згенерувати асемблер SPARC надто складно без підготовки, ми спочатку згенеруємо код віртуальної машини, подібний до асемблеру SPARC. Його основні «віртуальні» аспекти:
Нескінченна кількість змінних (замість кінцевої кількості регістрів) Вирази if-then-else і виклики функцій замість розгалужень і переходів Цей віртуальний проміжний асемблер визначено у sparcAsm.ml. SparcAsm.exp відповідає кожній інструкції SPARC (крім if). Послідовність інструкцій SparcAsm.t є або Ans, яка повертає значення в кінці функції, або визначенням змінної Let. Інші інструкції «Forget», «Save» та «Restore» будуть пояснені пізніше.
Virtual.f, Virtual.h і Virtual.g — це три функції, які перетворюють програми, перетворені за допомогою конверсії вкладених функцій, у код віртуальної машини. Virtual.f перекладає всю програму (список функцій верхнього рівня та вираз основної процедури), Virtual.h перекладає кожну функцію верхнього рівня, а Virtual.g перекладає вираз. Сенс цих перекладів полягає в тому, щоб зробити явним доступ до пам’яті для створення, читання та запису в закриття, кортежі та масиви. Такі структури даних, як замикання, кортежі та масиви, розміщуються в області пам’яті, що називається купою, адреса якої запам’ятовується в спеціальному регістрі SparcAsm.reg_hp.
Наприклад, у випадку читання масиву Closure.Get зміщення зсувається відповідно до розміру елемента, який потрібно завантажити. У створенні кортежу Closure.Tuple кожен елемент зберігається з вирівняними числами з плаваючою комою (8 байт), а початкова адреса використовується як значення кортежу. Створення закриття Closure.MakeCls зберігає адресу (мітку) тіла функції зі значеннями її вільних змінних, також піклуючись про вирівнювання, і використовує початкову адресу як значення закриття. Відповідно, на початку кожної функції верхнього рівня ми завантажуємо значення вільних змінних із закриття. У цьому процесі ми припускаємо, що кожна програма на основі закриття функції (AppCls) встановлює адресу закриття для реєстрації SparcAsm.reg_cl.
До речі, оскільки збірка SPARC не підтримує миттєві числа з плаваючою комою, нам потрібно створити постійну таблицю в пам’яті. Для цього Virtual.g записує константи з плаваючою комою в глобальну змінну Virtual.data, які включені Virtual.f у всю програму SparcAsm.Prog.
В асемблері SPARC більшість цілочисельних операцій можуть приймати ціле число в межах 13 бітів (не менше ніж -4096 і менше ніж 4096) як другий операнд. Оптимізація за допомогою цієї функції реалізована в Simm13.g і Simm13.g'. Вони подібні до постійного згортання та видалення непотрібних визначень, за винятком того, що цільовою мовою є віртуальна збірка SPARC, а константи обмежені 13-бітними цілими числами.
[Оновлення від 17 вересня 2008 р.: алокатор регістрів тепер використовує простіший алгоритм. Він пропускає відстеження (ToSpill і NoSpill), пояснене нижче.]
Найскладнішим процесом у компіляторі MinCaml є алокація регістрів, який реалізує нескінченну кількість змінних за допомогою кінцевої кількості регістрів.
По-перше, як умова виклику функцій, ми призначаємо аргументи від першого регістра до останнього. (Компілятор MinCaml не підтримує занадто багато аргументів, які не вміщуються в регістри. Їх мають обробляти програмісти, наприклад, за допомогою кортежів.) Ми встановлюємо значення, що повертаються, до першого регістру. Вони обробляються в RegAlloc.h, який виділяє регістри в кожній функції верхнього рівня.
Після цього ми розподіляємо резисти в тілах функцій і основній програмі. RegAlloc.g приймає послідовність інструкцій із відображенням regenv (від змінних до регістрів), що представляє поточне призначення регістру, і повертає послідовність інструкцій після виділення регістру. Основна політика розподілу реєстрів полягає в тому, щоб «уникати регістрів, яким призначаються живі змінні (що ще будуть використані).» SparcAsm.fv обчислює «змінні, які ще потрібно використовувати». Однак, при розподілі регістрів в e1 Let(x, e1, e2), не тільки e1, але також і «продовжувана» послідовність інструкцій e2 повинна бути врахована для обчислення «змінних, які будуть використані». З цієї причини RegAlloc.g і RegAlloc.g', які розподіляють регістри у виразах, також беруть послідовність інструкцій, що все ще триває, cont і використовують її для обчислення живих змінних.
Але іноді ми не можемо виділити жоден регістр, який не працює, оскільки кількість змінних є нескінченною, а кількість регістрів – ні. У цьому випадку ми повинні зберегти поточне значення деякого регістра в пам'яті. Цей процес називається розливом регістра. На відміну від імперативних мов, у функціональних мовах значення змінної не змінюється після її визначення. Тому краще зберегти його якомога раніше (якщо взагалі буде), щоб звільнити кімнату.
Таким чином, коли змінну x потрібно зберегти, RegAlloc.g повертає значення типу даних ToSpill, що представляє цю потребу, і таким чином повертається до визначення x, щоб вставити віртуальну інструкцію Save. Крім того, оскільки ми хочемо видалити x із набору «живих змінних» у точці, де x розливається, ми вставляємо віртуальну інструкцію Forget to exclude x із набору вільних змінних. З цією метою ToSpill зберігає не лише (список) розповсюджених змінних, але й послідовність інструкцій e, у яку було вставлено Forget. Таким чином, після збереження x ми повторюємо виділення регістру для e.
Збереження необхідно не тільки при розливі резистерів, але і при виклику функцій. MinCaml використовує так звану угоду про збереження виклику, тому кожен виклик функції знищує значення регістрів. Тому нам потрібно зберегти значення всіх регістрів, які живуть на цей момент. Ось чому ToSpill містить список розлитих змінних.
Якщо збереження непотрібне, ми повертаємо виділену регістром послідовність інструкцій e' (з новим regenv) у значенні іншого типу даних NoSpill.
Рано чи пізно буде використано розлиту змінну, і в цьому випадку RegAlloc.g' (функція, яка виділяє регістри у виразах) викликає виключення, оскільки не може знайти змінну в regenv. Цей виняток обробляється функцією RegAlloc.g'_and_restore, де вставляється віртуальна інструкція Restore, яка відновлює значення змінної з пам'яті в регістр.
При розподілі регістрів ми не тільки «уникаємо живих регістрів», але й намагаємося «зменшити непотрібне переміщення в майбутньому». Це називається націлюванням на регістр або об’єднанням регістрів. Наприклад, якщо визначена змінна буде другим аргументом виклику функції, ми намагаємося розмістити її у другому регістрі. Для іншого прикладу ми намагаємося виділити змінну, яка буде повернена як результат функції в першому регістрі. Вони реалізовані в RegAlloc.target. Для цього RegAlloc.g і RegAlloc.g' також беруть регістр dest, де буде встановлено результат обчислення.
Нарешті ми підійшли до фінального етапу: генерація асемблера для gcc. Оскільки ми вже завершили найскладнішу частину (а саме алокація регістрів), ми можемо просто вивести SparcAsm.t як справжній асемблер SPARC без особливих труднощів.
Звичайно, однак, ми повинні реалізувати віртуальні інструкції. Умовні вирази реалізуються порівняннями та розгалуженнями. Збереження та відновлення реалізовано за допомогою збереження та завантаження шляхом обчислення встановленого стекового набору вже збережених змінних і списку стекової карти розташування змінних стеку. Виклики функцій прості, можливо, за винятком (дещо хитрої) функції Emit.shuffle для розташування аргументів у порядку регістрів.
Єдиним нетривіальним, важливим процесом у цьому модулі є оптимізація хвостового виклику. Він реалізує виклики функцій (кінцеві виклики), які після цього нічого не мають і не повертаються, за допомогою простих інструкцій переходу замість викликів. Завдяки цій оптимізації рекурсивні функції, такі як gcd, компілюються в той самий код, що й цикли. Для цього функція Emit.g, яка генерує збірку для послідовностей інструкцій, а також функція Emit.g', яка генерує збірку для кожної інструкції, приймає значення типу даних Emit.dest, яке представляє, чи ми знаходимося в хвістовій позиції. Якщо dest дорівнює Tail, ми виконуємо кінцевий виклик іншої функції за допомогою інструкції переходу або встановлюємо результат обчислення в перший регістр і повертаємо за допомогою інструкції ret SPARC. Якщо dest є NonTail(x), ми встановлюємо результат обчислення на x.
Нарешті, ми реалізуємо основну процедуру stub.c, яка виділяє пам'ять в купі та стеку викликів функцій, реалізовуємо зовнішні функції libmincaml.S, необхідні для тестових програм, а потім отримуємо компілятор MinCaml, який працює!