MLton

MLton (vyslovuje se " millton " [1] ) je multiplatformní plně programový optimalizační kompilátor pro programovací jazyk Standard ML (SML). Stejně jako většina ostatních implementací Standard ML je napsán v samotném Standard ML (s výjimkou běhového systému napsaného v C ) a distribuován jako open source pod licencí ve stylu BSD .

Charakteristika

Poskytuje velmi vysoký výkon standardních ML programů : na malých programech jen mírně zaostává za C / C++ v rychlosti [2] ; na větších je díky celoprogramové optimalizaci na základě globální analýzy řídicího toku programu schopen je překonat. Generuje samostatné spustitelné soubory kompaktní velikosti. Výkon v MLton je poskytován i při intenzivním použití abstrakčních mechanismů SML ( parametrický polymorfismus , funkce vyššího řádu , funktory ), což umožňuje použití jazyka jak pro rychlé prototypování , tak pro rozsáhlé programování bez nutnosti zásahu programátora. rovnováha mezi abstrakcí a efektivitou. Zvýšení rychlosti kódu ve srovnání s jinými implementacemi SML na různých testech se pohybuje od několikanásobku až po několik řádů [3] .

Je doprovázena velmi bohatou dokumentací včetně popisů triků s netriviálním použitím jazyka. Na stránkách projektu lze nalézt téměř kompletní seznam odkazů na existující vědeckou a vzdělávací literaturu o Standardu ML [4] . Docela striktně vyhovuje definici jazyka a specifikaci základní knihovny . Existují čtyři odchylky od Definice, které autoři neplánují opravit, ale spíše je klasifikují jako opravu vad v samotné Definici.

Má tenký a rychlý FFI , který poskytuje plnou obousměrnou interakci s jazykem C (až do vzájemné rekurze ); stejně jako generátor vazeb NLFFI ( No-Longer-Foreign Function Interface ) který umožňuje vkládat hlavičkové soubory C přímo do projektu SML a používat přímá volání funkcí C v programech na SML [5] .

Podporuje mnoho nativních platforem ( x86 , IA-64 , AMD64 , SPARC , ARM , PowerPC / PowerPC64, DEC Alpha , HPPA , S390 ) a různé operační systémy, včetně různých systémů podobných Unixu (Debian, Fedora, *BSD) . Pod Windows vyžaduje Cygwin nebo MinGW (od roku 2014), nativní port je součástí plánů vývojářů. Má další back-endy v C , C-- , LLVM ; dříve zahrnoval back-end bytecode , ale jeho podpora byla ukončena, protože nezískal popularitu.

Implementace

MLton poskytuje efektivitu a kompaktnost programů díky:

• defunktorizace, tedy odvíjení modulů SML na definice nejvyšší úrovně. Defunktorizátor byl prvním krokem ve vývoji MLton .
• monomorfizace , čímž je parametrický polymorfismus "svobodný". Na rozdíl od šablon C++ , díky kombinaci s dalšími optimalizačními technikami v MLton, to nevede k lavinovému nafouknutí kódu: podle vývojářů nárůst strojového kódu v důsledku monomorfizace v MLton nepřesahuje 30 % [2] .
• agresivní odstraňování mrtvého kódu ( typy , funkce, konstruktory typů , konstruktory , hodnoty, argumenty funkcí, větve atd.).
• globální analýza řídicího toku programů a aplikace soukromých optimalizací na základě shromážděných specifických informací, včetně:
  • substituce funkcí za podmínky určitého poměru mezi velikostí jeho těla a počtem jeho volání, včetně přítomnosti cyklů v něm [2] [6] .
  • defunkcionalizace , která nejen přímo zvyšuje výkon odpovídajících sekcí kódu, ale také uvolňuje další informace o řídicí logice , které jsou následně využívány při následných optimalizačních průchodech [7] [2] .
• použití nativní ( unwrapped a tagless, na rozdíl od většiny kompilátorů funkcionálních jazyků) reprezentace primitivních typů a jejich polí , stejně jako plochá (nestrukturální) reprezentace uzávěrů (ML funkce) .
• implementace dlouhé aritmetiky (standardní struktura IntInf srovnatelná s podpisem INTEGER ) prostřednictvím knihovny GNU Multi-Precision Library .
• zploštění referenčních typů na proměnlivé proměnné odpovídajících nezávislých typů, to znamená eliminaci nepřímého adresování a úsporu paměti.
• více strategií sběru odpadu .

Přístup k optimalizaci aplikovaný v MLton se nápadně liší od tradičního [2] . Konvenční jazykové kompilátory s podporou pro entity vyššího řádu provádějí optimalizace přímo na AST získaném po analýze gramatiky a odvození typu , načež provádějí uzavírací konverzi nízkoúrovňové optimalizace. V MLton vypadá pracovní postup zjednodušeně takto. Nejprve se provede defunktorizace a monomorfizace , v důsledku čehož je kód prezentován v intermediálním jazyce s výrazně zjednodušeným typovým systémem oproti SML , ale s podporou funkcí vyššího řádu . Následuje defunkcionalizace a kódování v mezijazyku prvního řádu sestávajícího pouze z definic nejvyšší úrovně ( SSA ). A teprve poté se na výsledný plochý kód použijí tradičnější optimalizace (nahrazení koncové rekurze plochou iterací, konstantní šíření , odstranění mrtvého kódu , výběr reprezentace atd.), stejně jako reprezentace plochého uzavření . Takový řetězec přináší výhru jak uživatelům kompilátoru, tak jeho vývojářům:

• Ztráty výkonu z použití ML abstrakčních mechanismů jsou zcela eliminovány, což umožňuje využít jazyk naplno.
• Analýza globálního řídicího toku se odlišuje od ostatních optimalizačních algoritmů, takže první algoritmus je produktivnější a druhý je mnohem snazší implementovat.

Celkem MLton používá osm přechodných jazyků [8] , včetně těch, které narušují zabezpečení kvůli výkonu (na rozdíl například od kompilátoru TILT [9] , který neohrožuje zabezpečení až do samotného strojového kódu) a několik desítek průchodů.

Rozšíření

MLton nabízí řadu nestandardních knihoven:

• porty mnoha charakteristických SML/NJ knihoven včetně:
  • MLRISC [10] je přesměrovací rámec napsaný v SML pro vývoj optimalizačních back-endů pro překladače jazyků na vysoké úrovni pro různé hardwarové platformy. Umožňuje zapouzdřit funkčnost back-endu, což usnadňuje opětovné použití zbytku implementačního kódu kompilátoru.
  • pokračování implementace .
  • Modul Unsafe- nebezpečné funkce, včetně slovních hříček (většinou potřebné pro FFI ).
• Tenká vlákna poskytují platformě nezávislé, ale vysoce výkonné rozhraní pro vlákna operačního systému.
• Port vnořitelného jazyka Concurrent ML (CML) . MLton poskytuje základní funkcionalitu CML, která v podstatě napodobuje chování SML/NJ, ale místo pokračování používá vlastní „tenké“ proudy ; neimplementuje však nit-safe wrapper nad Core Library a reaktivními ekvivalenty funkčnosti modulů IOa OS.
• "World save and restore" - možnost výpisu celého stavu programu do souboru s následnou obnovou.
• MLBasis je vlastní systém správy modulů SMLCM , pokročilejší než systém SML/NJ . Doplněno automatickým převodníkem z formátu .cmdo .mlb.

a mnohem více [11] .

Existují experimentální rozšíření samotného MLton:

• Multi-MLton je kompilátor pro škálovatelné vícejádrové platformy [12] . Umožňuje kombinovat schopnosti MLton s distribuovanými výpočty (safe premise , predikce, transakce atd.). Odladěné prvky Multi-MLton se plánují sloučit s MLton.

Historie, filozofie, vývojáři

V dubnu 1997 Stephen Weeks vyvinul  defunktorizer pro SML/NJ , který okamžitě ukázal zvýšení rychlosti 2 až 6 krát . V srpnu téhož roku byl vyvinut optimalizační kompilátor, který se v té době jmenoval smlc. V říjnu byl implementován monomorfizátor. Během dalšího roku a půl se smlcstal zcela nezávislým kompilátorem a byl přejmenován na MLton, jehož první vydání proběhlo v březnu 1999 . V roce 2005 MLton vykazoval vynikající výkon programu [3] .

Vývoj byl od počátku veden s důrazem na výkon prostřednictvím globální optimalizace programu. [13]

Vývojáři MLton diktují čtení názvu svého kompilátoru jako „ milton “, analogicky se slovem „ mlýn “ ( anglicky  mlýn ) [1] pravděpodobně v žertu znamená „ mlecí ML programy “, což odráží použití agresivní transformace a programy rafinačních technik

Projekt MLton řídí čtyři lidé:

• Stephen Weeks __  _
• Henry Chaitin __  _
• Matthew Fluet _  _
• Suresh Jagannathan _  _

Významně přispěla i řada dalších lidí [14] .

V roce 2013 byl projekt MLton součástí programu Google Summer of Code [15] [16] .

Vývojáři MLton jsou aktivními členy nástupnické rady ML . V roce 2014 byly dva z nich oceněny cenou „NSF CISE Research Infrastructure (CRI)“ [17] „ za umístění MLton pro jazykový výzkum nové generace “.

Kritika a srovnání s alternativami

MLton zajišťuje výkon programů na úrovni C / C++ bez ohledu na použitý styl programování .

Nevýhody vyplývají přímo z aplikace globální analýzy a více kroků transformace:

• značné časové a paměťové náklady na práci. Například kompilace nativního kódu (více než 140 tisíc řádků v SML) na 1,6 GHz procesoru trvá 5 až 10 minut a vyžaduje více než 500 MB RAM [18] .
• nedostatek možnosti samostatné kompilace.
• nedostatek režimu REPL , který je typický pro většinu implementací Standard ML .

Srovnání s OCaml

OCaml i MLton produkují vysokorychlostní programy [19] , které často soupeří s programy C a C++, byly portovány na mnoho platforem (ačkoli seznam není totožný) a přicházejí s rozsáhlou dokumentací. Proto je otázka jejich rozdílů relevantní [20] :

• MLton aktuálně nemá nativní port Windows . OCaml běží sám o sobě a generuje programy, které běží pod Windows, ale debugger funguje pouze pod Unixem, protože používá fork().
• OCaml přichází s vynikající úrovní vývoje IDE (například ladicí program vám umožňuje sledovat kód nejen dopředu, ale i dozadu). MLton nemá grafické prostředí a pracuje z příkazového řádku, ale poskytuje některé další vývojářské nástroje (například profilovač velikosti kódu a rychlosti). MLton nepodporuje režim REPL , ale umožňuje výstup výsledku odvození typu do samostatného souboru .
• OCaml má dva kompilátory s jediným back-endem pro každý - pro nativní kód a pro bytecode - z nichž první se zkompiluje rychle a druhý je velmi rychlý. MLton má mnoho back-endů a bez ohledu na to, který si vyberete, kompiluje se velmi pomalu.
• OCaml nevystavuje rozsahy modulů a nemonomorfizuje . V důsledku toho vytváří efektivní kód převážně pro programy napsané v imperativním stylu a bez použití polymorfismu . U programů, které intenzivně využívají funkční idiomy , to může vést ke značné režii výkonu. Portování fragmentů kódu mezi moduly může mít také významný dopad na efektivitu. Naproti tomu MLton díky kompilačním strategiím, které používá, vždy generuje nejefektivnější kód, čímž výrazně snižuje potřebu ruční optimalizace. Pro OCaml existuje samostatný defunktorizátor [21] .
• OCaml téměř vždy používá zabalenou reprezentaci primitivních a strukturních typů a reprezentaci označených celých čísel: nejvýznamnější bit se používá k rozlišení mezi celými čísly a ukazateli, takže maximální hodnota celých čísel na 32bitové platformě je omezena na 31 bitů , nebo implementované v zabaleném způsobu. MLton používá nativní reprezentaci všech primitivních a jednoduchých typů struktur a sloučí odkazy na proměnné proměnné .
• Externí jazykové rozhraní v MLton je tenčí a efektivnější než v OCaml, což do značné míry souvisí s předchozím bodem. Při propojování kódu OCaml s kódem C je třeba ručně zapsat obal jako sadu funkcí proxy a přistupovat k tomuto obalu, nikoli přímo do knihovny [22] . MLton poskytuje generátor vazeb NLFFI .

Za zmínku stojí také některé rozdíly mezi kompilátory, které úzce souvisejí s rozdíly mezi samotnými jazyky:

• Oba nesou implementaci Lex / Yacc (respektive ocamllex / ocamlyacc a MLLex / MLYacc). Kromě toho má OCaml parametrický analyzátor CamlpX , který umožňuje měnit syntaxi jazyka ve velmi širokém rozsahu a je pohodlným nástrojem pro vývoj vložitelných jazyků . MLton nic podobného neposkytuje.
• Ekosystém OCaml je vyvinut lépe: pro OCaml se nashromáždilo poměrně dost knihoven a komunita OCaml je mnohem větší než komunita Standard ML . Pro Standard ML je podstatně méně knihoven , ale implementace FFI a NLFFI v MLton usnadňuje obousměrnou interakci s knihovnami C.
• OCaml má politiku jednoho modulu na soubor a tuto znalost využívá kompilátor k podpoře rozsáhlého programování . Standardní ML takové pravidlo nenařizuje a MLton poskytuje svůj vlastní systém správy modulů SML - MLBasis .

Viz také

• Standardní ML a další implementace (včetně SML/NJ )*
• Jazyk modulu ML
• Souběžné ML
• Optimalizace kompilátoru
• Transformace uzavření
• OCaml

Poznámky

1. ↑ 1 2 „MLton“ Vyslovte . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
2. ↑ 1 2 3 4 5 týdnů – Kompilace celého programu v MLton, 2006 .
3. ↑ Výkon 12 MLton . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
4. ↑ Reference . Získáno 10. prosince 2014. Archivováno z originálu 14. prosince 2014. (neurčitý)
5. ↑ No-Longer-Foreign, 2001 .
6. ↑ Inline . Získáno 21. listopadu 2014. Archivováno z originálu 29. listopadu 2014. (neurčitý)
7. ↑ Potvrdit . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
8. ↑ Středně pokročilé jazyky MLton . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
9. ↑ Kompilátor TILT (TIL-Two) Archivováno z originálu 9. května 2008.
10. ↑ MLRISC . Získáno 18. listopadu 2014. Archivováno z originálu dne 23. září 2015. (neurčitý)
11. ↑ Rozšíření MLton . Datum přístupu: 13. listopadu 2014. Archivováno z originálu 2. ledna 2015. (neurčitý)
12. ↑ Multi-MLton . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
13. ↑ Historie MLton . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
14. ↑ Kredity MLton . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
15. ↑ Google Summer of Code 2013 (archiv GSoC/GCI) . Získáno 14. září 2016. Archivováno z originálu 23. června 2016. (neurčitý)
16. ↑ MLton v Google Summer of Code 2013 (na stránce MLton) . Získáno 14. září 2016. Archivováno z originálu 23. září 2016. (neurčitý)
17. ↑ Stránka kompilátoru MLton .
18. ↑ Nevýhody MLton . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
19. ↑ The Breakfast Post. SML a OCaml: Proč byl tedy OCaml rychlejší?  (anglicky) . Získáno 16. září 2016. Archivováno z originálu 21. září 2016.
20. ↑ Srovnání MLton a OCaml . Získáno 13. listopadu 2014. Archivováno z originálu 13. listopadu 2014. (neurčitý)
21. ↑ The Caml Hump: ocamldefun (sestupný odkaz) . Statistický výpočet parametrů aplikací modulů. Julien Signoles. JFLA 2003. (2010). Datum přístupu: 10. prosince 2014. Archivováno z originálu 4. listopadu 2015.  (neurčitý)  — Defunktorizátor pro OCaml
22. ↑ Chailloux, Manoury, Pagano, „Developing with OCaml“, 2007 .

Odkazy

•  Stránka kompilátoru MLton .
• Srovnání MLton a OCaml
• Stephen Weeks. Kompilace celého programu v MLton (  (anglicky) ). - 2006. Archivováno 29. června 2007.
• Jens Olsson, Andreas Rossberg. Srovnání standardních ML a OCaml  (anglicky) (2009).
• Matyáš Blume. No-Longer-Foreign: Výuka kompilátoru ML mluvit C „nativně“ (  (anglicky) ). - Elsevier Science BV, 2001. Archivováno z originálu 4. dubna 2005.
• Matthew Fluet, Riccardo Pucella. Fantomové typy a podtypování (  (anglicky) ). - Mezinárodní konference o teoretické informatice IFIP, 2002.
• Zhong Shao, Andrew W. Appel. Prostorově efektivní reprezentace uzavření (  (ang.) ). — Lisp a funkční programování, 2006.
• Chailloux, Manoury, Pagano. Vývoj aplikací s Objective  Caml (neopr.) . - 2007. - S. 349-370, Kapitola 11. Interakce s jazykem C.