MLton

MLton (uttalas " millton " [1] ) är en plattformsoberoende kompilator som optimerar hela programmet för programmeringsspråket Standard ML (SML). Liksom de flesta andra implementeringar av Standard ML är den skriven i själva Standard ML (med undantag för runtime - systemet skrivet i C ) och distribueras med öppen källkod under en BSD-liknande licens .

Egenskaper

Ger mycket hög prestanda för standard ML- program : på små program släpar den bara något efter C / C++ i hastighet [2] ; på större, på grund av fullständig programoptimering baserad på en global analys av programmets kontrollflöde , kan det överträffa dem. Genererar fristående körbara filer av kompakt storlek. Prestanda i MLton tillhandahålls även med stor användning av SML - abstraktionsmekanismer ( parametrisk polymorfism , högre ordningsfunktioner , funktorer ), vilket gör att språket kan användas både för snabb prototyping och storskalig programmering utan att programmeraren behöver slå till en balans mellan abstraktion och effektivitet. Ökningen av kodhastighet i jämförelse med andra SML-implementationer på olika tester sträcker sig från flera gånger till flera storleksordningar [3] .

Den åtföljs av mycket rik dokumentation, inklusive beskrivningar av knep med icke-trivial användning av språket. På projektets hemsida kan du hitta en nästan komplett lista med länkar till befintlig vetenskaplig och utbildningslitteratur om Standard ML [4] . Överensstämmer ganska strikt med språkdefinitionen och Core Library- specifikationen . Det finns fyra avvikelser från definitionen, som författarna inte planerar att korrigera, utan snarare klassificerar som korrigering av defekter i själva definitionen.

Har en tunn och snabb FFI som ger full tvåvägsinteraktion med C-språket (upp till ömsesidig rekursion ); samt NLFFI ( No-Longer-Foreign Function Interface ) bindningsgeneratorn , låter dig bädda in C-huvudfiler direkt i ett SML-projekt och använda direkta C-funktionsanrop i program på SML [5] .

Stöder många inbyggda plattformar ( x86 , IA-64 , AMD64 , SPARC , ARM , PowerPC / PowerPC64, DEC Alpha , HPPA , S390 ) och olika operativsystem, inklusive olika Unix-liknande system (Debian, Fedora, *BSD) . Under Windows kräver Cygwin eller MinGW (från och med 2014), en inbyggd port ingår i utvecklarnas planer. Har ytterligare back-ends i C , C-- , LLVM ; tidigare inkluderade en back-end till bytecode , men dess stöd avbröts, eftersom det inte blev populärt.

Implementering

MLton ger effektivitet och kompakthet i programmen på grund av:

• defunctorization, det vill säga avveckla SML -moduler till toppnivådefinitioner. Defunctorizern var det första steget i utvecklingen av MLton .
• monomorfisering , vilket gör parametrisk polymorfism "fri". Till skillnad från C++-mallar , på grund av kombinationen med andra optimeringstekniker i MLton, leder detta inte till en lavinliknande koduppsvällning: enligt utvecklarna överstiger ökningen av maskinkod på grund av monomorfisering i MLton inte 30 % [2] .
• aggressiv borttagning av död kod ( typer , funktioner, typkonstruktörer , konstruktörer , värden, funktionsargument, grenar, etc.).
• global analys av kontrollflödet av program och tillämpningen av privata optimeringar baserade på den insamlade specifika informationen, inklusive:
  • funktionssubstitutioner under villkoret av ett visst förhållande mellan storleken på dess kropp och antalet anrop, inklusive närvaron av cykler i den [2] [6] .
  • defunctionalization , som inte bara direkt ökar prestandan för motsvarande sektioner av koden, utan också släpper ytterligare information om kontrolllogiken , som sedan används av efterföljande optimeringspass [7] [2] .
• användning av infödd ( oupppackad och etikettlös, till skillnad från de flesta funktionella språkkompilatorer) representation av primitiva typer och arrayer av dem, såväl som platt (icke-strukturell) representation av stängningar (ML-funktioner) .
• implementering av lång aritmetik (en standardstruktur jämförbar IntInf med en signatur INTEGER ) via GNU Multi-Precision Library .
• platta referenstyper till föränderliga variabler av motsvarande oberoende typer, det vill säga eliminera indirekt adressering och spara minne.
• flera strategier för sophämtning .

Metoden för optimering som tillämpas i MLton skiljer sig slående från den traditionella [2] . Konventionella språkkompilatorer med stöd för enheter av högre ordning utför optimeringar direkt på den AST som erhålls efter grammatikanalys och typinferens , varefter de utför stängningskonvertering lågnivåoptimeringar. I MLton ser arbetsflödet ut så här på ett förenklat sätt. Först utförs defunctorization och monomorphization , som ett resultat av vilket koden presenteras på ett mellanspråk med ett avsevärt förenklat typsystem jämfört med SML , men med stöd för högre ordningsfunktioner . Detta följs av defunktionalisering och kod i ett första ordningens mellanspråk som endast består av toppnivådefinitioner ( SSA ). Och först då, på den resulterande platta koden , tillämpas mer traditionella optimeringar (ersätter svansrekursion med platt iteration, konstant fortplantning , borttagning av död kod , val av representation, etc.), såväl som platt stängningsrepresentation . En sådan kedja ger en vinst för både användare av kompilatorn och dess utvecklare:

• prestandaförluster från användningen av ML- abstraktionsmekanismer elimineras helt, vilket gör att du kan använda språket till dess fulla potential.
• global kontrollflödesanalys skiljer sig från andra optimeringsalgoritmer, vilket gör den förra mer produktiv och den senare mycket lättare att implementera.

Totalt använder MLton åtta mellanspråk [8] , inklusive de som bryter mot säkerheten för prestandas skull (till skillnad från till exempel TILT-kompilatorn [9] , som inte äventyrar säkerheten förrän själva maskinkoden), och flera dussin pass.

Tillägg

MLton erbjuder ett antal icke-standardiserade bibliotek:

• portar för många karakteristiska SML/NJ- bibliotek inklusive:
  • MLRISC [10] är ett omdirigeringsramverk skrivet i SML för att utveckla optimerande back-ends för högnivåspråkkompilatorer för olika hårdvaruplattformar. Låter dig kapsla in back-end-funktionalitet, vilket gör det lättare att återanvända resten av kompilatorimplementeringskoden.
  • fortsatt implementering .
  • Modul Unsafe- osäkra funktioner, inklusive att skriva ordlekar (behövs oftast för FFI ).
• Tunna trådar ger ett plattformsoberoende men högpresterande gränssnitt till operativsystemtrådar.
• En port för det inbäddade språket Concurrent ML (CML) . MLton tillhandahåller grundläggande CML-funktioner som i princip efterliknar beteendet hos SML/NJ, men använder sina egna "tunna" strömmar istället för fortsättningar ; den implementerar dock inte ett trådsäkert omslag över Core Library och de reaktiva motsvarigheterna till funktionaliteten hos modulerna IOoch OS.
• "World save and restore" - förmågan att dumpa hela programmets tillstånd till en fil med efterföljande återställning.
• MLBasis är SML :s eget modulhanteringssystem , mer avancerat än CMSML /NJ . Tillsammans med en automatisk omvandlare från format .cmtill .mlb.

och mycket mer [11] .

Det finns experimentella tillägg till själva MLton:

• Multi-MLton är en kompilator för skalbara flerkärniga plattformar [12] . Låter dig kombinera MLtons funktioner med distribuerad datoranvändning (säkra premisser , förutsägelser, transaktioner, etc.). De felsökta elementen i Multi-MLton är planerade att slås samman med MLton.

Historia, filosofi, utvecklare

I april 1997 utvecklade Stephen Weeks en  defunktorizer för SML/NJ , som omedelbart visade en hastighetsökning på 2 till 6 gånger . I augusti samma år utvecklades en optimeringskompilator, som vid den tiden hette . I oktober implementerades en monomorphizer. Under de följande och ett halvt åren blev den en helt oberoende kompilator och döptes om till MLton, vars första release ägde rum i mars 1999 . År 2005 visade MLton utmärkt programprestanda [3] . smlcsmlc

Redan från början har utvecklingen genomförts med betoning på prestanda genom global programoptimering. [13]

Utvecklarna av MLton dikterar läsningen av namnet på deras kompilator som " millton ", i analogi med ordet " mill " ( engelska  mill ) [1] vilket förmodligen skämtsamt betyder " malning ML-program ", vilket återspeglar användningen av aggressiv transformation och förfiningstekniker program.

MLton-projektet drivs av fyra personer:

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

Många andra människor gjorde också betydande bidrag [14] .

2013 var MLton-projektet en del av programmet Google Summer of Code [15] [16] .

MLton-utvecklarna är aktiva medlemmar i det efterträdande ML- rådet . År 2014 tilldelades två av dem utmärkelsen "NSF CISE Research Infrastructure (CRI)" [17] " för att ha placerat MLton för nästa generations språkforskning ".

Kritik och jämförelse med alternativ

MLton säkerställer prestanda för program på C / C++- nivå , oavsett vilken programmeringsstil som används .

Nackdelarna härrör direkt från tillämpningen av global analys och flera transformationssteg:

• betydande tids- och minneskostnader för arbetet. Till exempel tar det 5 till 10 minuter att kompilera inbyggd kod (mer än 140 tusen rader i SML) på en 1,6 GHz-processor och kräver mer än 500 MB RAM [18] .
• bristande möjlighet till separat sammanställning.
• avsaknad av REPL- läge , vilket är typiskt för de flesta implementeringar av Standard ML .

Jämförelse med OCaml

Både OCaml och MLton producerar höghastighetsprogram [19] som ofta konkurrerar med C- och C++-program, har porterats till många plattformar (även om listan inte är identisk) och kommer med omfattande dokumentation. Detta gör frågan om deras skillnader relevant [20] :

• MLton har för närvarande inte en inbyggd Windows -port . OCaml körs på egen hand och genererar program som körs under Windows, men felsökaren fungerar bara under Unix-liknande eftersom den använder fork().
• OCaml kommer med en enastående nivå av IDE- utveckling (till exempel låter debuggern dig spåra kod inte bara framåt utan också bakåt). MLton har ingen grafisk miljö och fungerar från kommandoraden, men det tillhandahåller några ytterligare utvecklarverktyg (till exempel en kodstorlek och hastighetsprofilerare). MLton stöder inte REPL- läge, men det tillåter utmatning av resultatet av typinferens till en separat fil .
• OCaml har två kompilatorer med en enda back-end för varje - till ursprunglig kod och till bytekod - varav den första kompileras snabbt och den andra är mycket snabb. MLton har många back-ends, och oavsett vilken du väljer så kompileras den väldigt långsamt.
• Ocaml exponerar inte modulomfång och monomorfiserar inte . Som en konsekvens producerar den effektiv kod främst för program skrivna i en imperativ stil och utan användning av polymorfism . För program som använder mycket funktionella idiom kan det resultera i betydande prestandakostnader. Portering av kodavsnitt mellan moduler kan också ha en betydande inverkan på effektiviteten. Däremot genererar MLton, på grund av kompileringsstrategierna den använder, alltid den mest effektiva koden, vilket avsevärt minskar behovet av manuell optimering. Det finns en separat defunctorizer för OCaml [21] .
• OKaml använder nästan alltid lindad representation av primitiva och strukturtyper och märkt heltalsrepresentation: den mest signifikanta biten används för att skilja mellan heltal och pekare, så det maximala värdet av heltal på en 32-bitars plattform är begränsat till 31 bitar , eller implementeras på ett inslaget sätt. MLton använder en inbyggd representation av alla primitiva och enkla strukturtyper och plattar ut referenser till föränderliga variabler .
• Det externa språkgränssnittet i MLton är tunnare och mer effektivt än i OCaml, vilket till stor del är relaterat till föregående punkt. När du länkar OCaml-kod med C-kod måste du manuellt skriva omslaget som en uppsättning proxyfunktioner och komma åt detta omslag, och inte direkt till biblioteket [22] . MLton tillhandahåller en NLFFI- bindningsgenerator .

Också anmärkningsvärt här är några skillnader mellan kompilatorer, nära relaterade till skillnader mellan språken själva:

• Båda bär implementeringen av Lex / Yacc (respektive ocamllex / ocamlyacc och MLLex / MLYacc). Dessutom har OCaml en parametrisk parser CamlpX , som låter dig ändra syntaxen för språket inom ett mycket brett spektrum och är ett bekvämt verktyg för att utveckla inbäddningsbara språk . MLton tillhandahåller inget liknande.
• OCaml-ekosystemet är bättre utvecklat: en hel del bibliotek har ackumulerats för OCaml, och OCaml -gemenskapen är mycket större än Standard ML -gemenskapen . Det finns betydligt färre bibliotek för Standard ML , men implementeringen av FFI och NLFFI i MLton gör det enkelt att tillhandahålla tvåvägsinteraktion med C-bibliotek.
• OCaml har en policy för en modul per fil, och kunskapen om detta används av kompilatorn för att stödja storskalig programmering . Standard ML dikterar inte en sådan regel, och MLton tillhandahåller sitt eget SML- modulhanteringssystem - MLBasis .

Se även

• Standard ML och andra implementeringar (inklusive SML/NJ )*
• ML-modulspråk
• Samtidigt ML
• Optimerar kompilatorn
• Stängningstransformation
• OCaml

Anteckningar

1. ↑ 1 2 "MLton" uttala . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
2. ↑ 1 2 3 4 5 veckor - Helprogramsammanställning i MLton, 2006 .
3. ↑ 12 MLton prestanda . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
4. ↑ Hänvisar till . Hämtad 10 december 2014. Arkiverad från originalet 14 december 2014. (obestämd)
5. ↑ No-Long-Foreign, 2001 .
6. ↑ Inline . Hämtad 21 november 2014. Arkiverad från originalet 29 november 2014. (obestämd)
7. ↑ Contify . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
8. ↑ MLtons mellanspråk . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
9. ↑ TILT (TIL-Two) kompilator Arkiverad från originalet den 9 maj 2008.
10. ↑ MLRISC . Hämtad 18 november 2014. Arkiverad från originalet 23 september 2015. (obestämd)
11. ↑ MLtons tillägg . Tillträdesdatum: 13 november 2014. Arkiverad från originalet 2 januari 2015. (obestämd)
12. ↑ Multi-MLton . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
13. ↑ MLton Historia . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
14. ↑ MLton Credits . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
15. ↑ Google Summer of Code 2013 (GSoC/GCI Archive) . Hämtad 14 september 2016. Arkiverad från originalet 23 juni 2016. (obestämd)
16. ↑ MLton i Google Summer of Code 2013 (på MLton-sidan) . Hämtad 14 september 2016. Arkiverad från originalet 23 september 2016. (obestämd)
17. ↑ MLton kompilatorsida .
18. ↑ MLton Nackdelar . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
19. ↑ Frukostposten. SML och OCaml: Så varför var OCaml snabbare?  (engelska) . Hämtad 16 september 2016. Arkiverad från originalet 21 september 2016.
20. ↑ Jämförelse av MLton och OCaml . Hämtad 13 november 2014. Arkiverad från originalet 13 november 2014. (obestämd)
21. ↑ The Caml Hump: ocamldefun (nedlänk) . Beräkna Statique des Applications de Modules Parametrar. Julien Signoles. JFLA 2003. (2010). Tillträdesdatum: 10 december 2014. Arkiverad från originalet den 4 november 2015.  (obestämd)  — Defunctorizer för OCaml
22. ↑ Chailloux, Manoury, Pagano, "Utvecklas med OCaml", 2007 .

Länkar

• MLtons  kompilatorsida .
• Jämförelse av MLton och OCaml
• Stephen Weeks. Helprogramskompilering i MLton (  (engelska) ). - 2006. Arkiverad den 29 juni 2007.
• Jens Olsson, Andreas Rossberg. Jämförelse av Standard ML och OCaml  (engelska) (2009).
• Matthias Blume. No-Long-Foreign: Att lära en ML-kompilator att tala C "infödd" (  (engelska) ). - Elsevier Science BV, 2001. Arkiverad från originalet den 4 april 2005.
• Matthew Fluet, Riccardo Pucella. Fantomtyper och undertypning (  (engelska) ). - IFIP International Conference on Theoretical Computer Science, 2002.
• Zhong Shao, Andrew W. Appel. Rymdeffektiva stängningsrepresentationer (  (eng.) ). — Lisp och funktionell programmering, 2006.
• Chailloux, Manoury, Pagano. Utveckla applikationer med mål Caml  (neopr.) . - 2007. - S. 349-370, kapitel 11. Interaktion med C-språket.