MLton

MLton (udtales " millton " [1] ) er en cross -platform fuld-program optimerende compiler til standard ML (SML) programmeringssproget. Som de fleste andre implementeringer af Standard ML er den skrevet i selve Standard ML (med undtagelse af runtime- systemet skrevet i C ) og distribueret open source under en BSD-lignende licens .

Karakteristika

Giver meget høj ydeevne af standard ML- programmer : på små programmer halter den kun lidt efter C / C++ i hastighed [2] ; på større, på grund af fuld programoptimering baseret på en global analyse af programmets kontrolflow , er det i stand til at overgå dem. Genererer selvstændige eksekverbare filer af kompakt størrelse. Ydeevne i MLton leveres selv med stor brug af SML - abstraktionsmekanismer ( parametrisk polymorfi , funktioner af højere orden , funktorer ), som gør det muligt at bruge sproget både til hurtig prototyping og programmering i stor skala uden at programmøren skal slå til en balance mellem abstraktion og effektivitet. Stigningen i kodehastighed sammenlignet med andre SML-implementeringer på forskellige tests varierer fra flere gange til flere størrelsesordener [3] .

Den er ledsaget af meget rig dokumentation, herunder beskrivelser af tricks med ikke-triviel brug af sproget. På projektets hjemmeside kan du finde en næsten komplet liste over links til eksisterende videnskabelig og pædagogisk litteratur om Standard ML [4] . Overholder temmelig strengt sprogdefinitionen og Core Library- specifikationen . Der er fire afvigelser fra definitionen, som forfatterne ikke planlægger at rette, men derimod klassificerer som korrektion af fejl i selve definitionen.

Har en tynd og hurtig FFI , der giver fuld tovejsinteraktion med C-sproget (op til gensidig rekursion ); samt NLFFI ( No-Longer-Foreign Function Interface ) bindingsgeneratoren som giver dig mulighed for at indlejre C-header-filer direkte i et SML-projekt og bruge direkte C- funktionskald i programmer på SML [5] .

Understøtter mange native platforme ( x86 , IA-64 , AMD64 , SPARC , ARM , PowerPC /PowerPC64, DEC Alpha , HPPA , S390 ) og forskellige operativsystemer, herunder forskellige Unix-lignende systemer (Debian, Fedora, *BSD). Under Windows kræver Cygwin eller MinGW (fra 2014), er en indbygget port inkluderet i udviklernes planer. Har yderligere back-ends i C , C-- , LLVM ; tidligere inkluderet en back-end til bytecode , men dens support blev afbrudt, da den ikke vandt popularitet.

Implementering

MLton giver effektivitet og kompakthed af programmer på grund af:

• defunctorization, det vil sige afvikling af SML-moduler til definitioner på øverste niveau. Defunctorizer var det første skridt i udviklingen af ​​MLton .
• monomorfisering , hvilket gør parametrisk polymorfi "fri". I modsætning til C++-skabeloner fører dette på grund af kombinationen med andre optimeringsteknikker i MLton ikke til en lavinelignende kode-bloat: ifølge udviklerne overstiger stigningen i maskinkode på grund af monomorfisering i MLton ikke 30% [2] .
• aggressiv fjernelse af død kode ( typer , funktioner, typekonstruktører , konstruktører , værdier, funktionsargumenter, grene osv.).
• global analyse af programmernes kontrolflow og anvendelsen af ​​private optimeringer baseret på den indsamlede specifikke information, herunder:
  • funktionssubstitutioner under forudsætning af et vist forhold mellem størrelsen af ​​dens krop og antallet af dens kald, herunder tilstedeværelsen af ​​cyklusser i den [2] [6] .
  • defunctionalization , som ikke kun direkte øger ydeevnen af ​​de tilsvarende sektioner af koden, men også frigiver yderligere information om kontrollogikken , som derefter bruges af efterfølgende optimeringspassager [7] [2] .
• brug af indfødt ( uindpakket og tagløs, i modsætning til de fleste funktionelle sprogkompilere) repræsentation af primitive typer og arrays af dem, såvel som flad (ikke-strukturel) repræsentation af lukninger (ML-funktioner) .
• implementering af lang aritmetik (en standardstruktur , der IntInf kan sammenlignes med en signatur INTEGER ) via GNU Multi-Precision Library .
• fladning af referencetyper til foranderlige variabler af de tilsvarende uafhængige typer, det vil sige eliminering af indirekte adressering og lagring af hukommelse.
• flere affaldsindsamlingsstrategier .

Den tilgang til optimering, der anvendes i MLton, er slående forskellig fra den traditionelle [2] . Konventionelle sprogkompilere med understøttelse af højere ordens entiteter udfører optimeringer direkte på AST'en opnået efter grammatikparsing og typeinferens , hvorefter de udfører lukningskonvertering optimeringer på lavt niveau. I MLton ser arbejdsgangen sådan ud på en forenklet måde. Først udføres defunctorization og monomorphization , som et resultat af hvilket koden præsenteres i et mellemsprog med et væsentligt forenklet typesystem sammenlignet med SML , men med understøttelse af højere-ordens funktioner . Dette efterfølges af defunktionalisering og kode i et førsteordens mellemsprog, der kun består af definitioner på øverste niveau ( SSA ). Og først derefter, på den resulterende flade kode , anvendes mere traditionelle optimeringer (erstatning af halerekursion med flad iteration, konstant udbredelse , fjernelse af død kode , valg af repræsentation osv.), samt flad lukningsrepræsentation . En sådan kæde giver en gevinst for både brugere af compileren og dens udviklere:

• ydeevnetab fra brugen af ​​ML - abstraktionsmekanismer er fuldstændig elimineret, hvilket giver dig mulighed for at bruge sproget til dets fulde potentiale.
• global kontrolflowanalyse skiller sig ud fra andre optimeringsalgoritmer, hvilket gør førstnævnte mere produktive og sidstnævnte meget nemmere at implementere.

I alt bruger MLton otte mellemsprog [8] , inklusive dem, der krænker sikkerheden af ​​hensyn til ydeevnen (i modsætning til f.eks. TILT-kompileren [9] , som ikke kompromitterer sikkerheden før selve maskinkoden), og flere dusin gennemløb.

Udvidelser

MLton tilbyder en række ikke-standardbiblioteker:

• porte i mange karakteristiske SML/NJ- biblioteker herunder:
  • MLRISC [10] er en omdirigeringsramme skrevet i SML til udvikling af optimering af back-ends til sprogkompilere på højt niveau til forskellige hardwareplatforme. Giver dig mulighed for at indkapsle backend-funktionalitet, hvilket gør det nemmere at genbruge resten af ​​compilerimplementeringskoden.
  • fortsættelse af implementeringen .
  • Modul Unsafe- usikre funktioner, herunder indtastning af ordspil (for det meste nødvendigt for FFI ).
• Tynde tråde giver en platformsuafhængig, men højtydende grænseflade til operativsystemtråde.
• En port af det indlejrede sprog for Concurrent ML (CML) . MLton leverer grundlæggende CML-funktionalitet, der grundlæggende efterligner adfærden for SML/NJ, men bruger sine egne "tynde" strømme i stedet for fortsættelser ; den implementerer dog ikke en trådsikker indpakning over Core Library og de reaktive ækvivalenter til funktionaliteten af ​​modulerne IOog OS.
• "Verdensgem og gendan" - evnen til at dumpe hele programmets tilstand til en fil med efterfølgende gendannelse.
• MLBasis er SMLs egetCM modulstyringssystem , mere avanceret end SML/NJ . Ledsaget af en automatisk konverter fra format .cmtil .mlb.

og meget mere [11] .

Der er eksperimentelle udvidelser til selve MLton:

• Multi-MLton er en compiler til skalerbare multi-core platforme [12] . Giver dig mulighed for at kombinere MLtons muligheder med distribueret databehandling (sikker forudsætning , forudsigelse, transaktioner osv.). De debuggede elementer i Multi-MLton er planlagt til at blive fusioneret med MLton.

Historie, filosofi, udviklere

I april 1997 udviklede Stephen Weeks en  defunktorizer til SML/NJ , som straks viste en hastighedsforøgelse på 2 til 6 gange . I august samme år blev der udviklet en optimeringskompiler, som på det tidspunkt hed . I oktober blev en monomorphizer implementeret. I løbet af det næste halvandet år blev det en fuldstændig uafhængig compiler og blev omdøbt til MLton, hvis første udgivelse fandt sted i marts 1999 . I 2005 viste MLton fremragende programydelse [3] . smlcsmlc

Helt fra begyndelsen blev der udviklet med vægt på ydeevne gennem global programoptimering. [13]

Udviklerne af MLton dikterer læsningen af ​​navnet på deres compiler som " millton ", analogt med ordet " mill " ( engelsk  mill ) [1] hvilket sandsynligvis i spøg betyder " maling ML-programmer ", hvilket afspejler brugen af ​​aggressiv transformation og raffineringsteknikker programmer.

MLton-projektet drives af fire personer:

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

Talrige andre mennesker ydede også betydelige bidrag [14] .

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

MLton-udviklerne er aktive medlemmer af det efterfølgende ML -råd . I 2014 blev to af dem tildelt prisen "NSF CISE Research Infrastructure (CRI)" [17] " for positionering af MLton til næste generations sprogforskning ".

Kritik og sammenligning med alternativer

MLton sikrer ydelsen af ​​programmer på C / C++- niveau , uanset hvilken programmeringsstil der bruges .

Ulemper stammer direkte fra anvendelsen af ​​global analyse og flere transformationstrin:

• betydelige tids- og hukommelsesomkostninger til arbejdet. For eksempel tager det 5 til 10 minutter at kompilere indbygget kode (mere end 140 tusind linjer i SML) på en 1,6 GHz processor og kræver mere end 500 MB RAM [18] .
• manglende mulighed for særskilt kompilering.
• mangel på REPL -tilstand , hvilket er typisk for de fleste implementeringer af Standard ML .

Sammenligning med OKaml

Både OCaml og MLton producerer højhastighedsprogrammer [19] , der ofte konkurrerer med C- og C++-programmer, er blevet porteret til mange platforme (selvom listen ikke er identisk) og kommer med omfattende dokumentation. Dette gør spørgsmålet om deres forskelle relevant [20] :

• MLton har i øjeblikket ikke en indbygget Windows -port . OCaml kører på egen hånd og genererer programmer, der kører under Windows, men debuggeren virker kun under Unix-lignende , fordi den bruger fork().
• OCaml kommer med et enestående niveau af IDE - udvikling (for eksempel giver debuggeren dig mulighed for at spore kode ikke kun fremad, men også bagud). MLton har ikke et grafisk miljø og arbejder fra kommandolinjen, men det giver nogle ekstra udviklerværktøjer (for eksempel en kodestørrelse og hastighedsprofiler). MLton understøtter ikke REPL -tilstand, men det tillader udlæsning af resultatet af typeslutning til en separat fil .
• OCaml har to compilere med en enkelt back-end for hver - til native kode og til bytecode - hvoraf den første kompilerer hurtigt, og den anden er meget hurtig. MLton har mange back-ends, og uanset hvilken du vælger, kompilerer den meget langsomt.
• OCaml afslører ikke modulomfang og monomorfiserer ikke . Som en konsekvens producerer den effektiv kode overvejende til programmer skrevet i en imperativ stil og uden brug af polymorfi . For programmer, der gør stor brug af funktionelle idiomer , kan det resultere i betydelige præstationsomkostninger. Portering af kodestykker mellem moduler kan også have en betydelig indflydelse på effektiviteten. I modsætning hertil genererer MLton, på grund af de kompileringsstrategier, den bruger, altid den mest effektive kode, hvilket væsentligt reducerer behovet for manuel optimering. Der er en separat defunctorizer for OCaml [21] .
• OCaml bruger næsten altid indpakket repræsentation af primitive og strukturtyper og mærket heltalsrepræsentation: den mest signifikante bit bruges til at skelne mellem heltal og pointere, så den maksimale værdi af heltal på en 32-bit platform er begrænset til 31 bit , eller implementeret på en indpakket måde. MLton bruger en indbygget repræsentation af alle primitive og simple strukturtyper og udjævner referencer til variable variable .
• Den eksterne sproggrænseflade i MLton er tyndere og mere effektiv end i OCaml, som i høj grad er relateret til det foregående punkt. Når du forbinder OCaml-kode med C-kode, skal du manuelt skrive indpakningen som et sæt proxy-funktioner og få adgang til denne indpakning, og ikke direkte til biblioteket [22] . MLton leverer en NLFFI- bindingsgenerator .

Også bemærkelsesværdigt her er nogle forskelle mellem compilere, tæt forbundet med forskelle mellem sprogene selv:

• Begge bærer implementeringen af ​​Lex / Yacc (henholdsvis ocamllex / ocamlyacc og MLLex / MLYacc). Derudover har OCaml en parametrisk parser CamlpX , som giver dig mulighed for at ændre sprogets syntaks i et meget bredt område og er et praktisk værktøj til at udvikle indlejrede sprog . MLton giver ikke noget lignende.
• OCaml-økosystemet er bedre udviklet: en hel del biblioteker er blevet akkumuleret for OCaml, og OCaml -fællesskabet er meget større end Standard ML -fællesskabet . Der er væsentligt færre biblioteker til Standard ML , men implementeringen af ​​FFI og NLFFI i MLton gør det nemt at give tovejsinteraktion med C-biblioteker.
• OCaml har en politik med ét modul pr. fil, og viden om denne bruges af compileren til at understøtte programmering i stor skala . Standard ML dikterer ikke en sådan regel, og MLton leverer sit eget SML-modulstyringssystem - MLBasis .

Se også

• Standard ML og andre implementeringer (inklusive SML/NJ )*
• ML modul sprog
• Samtidig ML
• Optimering af compiler
• Lukningstransformation
• OKaml

Noter

1. ↑ 1 2 "MLton" Udtal . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
2. ↑ 1 2 3 4 5 uger - Compilation af hele programmet i MLton, 2006 .
3. ↑ 12 MLton ydeevne . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
4. ↑ Referencer . Hentet 10. december 2014. Arkiveret fra originalen 14. december 2014. (ubestemt)
5. ↑ No-Langer-Foreign, 2001 .
6. ↑ Inline . Hentet 21. november 2014. Arkiveret fra originalen 29. november 2014. (ubestemt)
7. ↑ Bekræft . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
8. ↑ MLtons mellemsprog . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
9. ↑ TILT (TIL-Two) compiler Arkiveret fra originalen den 9. maj 2008.
10. ↑ MLRISC . Hentet 18. november 2014. Arkiveret fra originalen 23. september 2015. (ubestemt)
11. ↑ MLtons udvidelser . Dato for adgang: 13. november 2014. Arkiveret fra originalen 2. januar 2015. (ubestemt)
12. ↑ Multi-MLton . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
13. ↑ MLton historie . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
14. ↑ MLton Credits . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
15. ↑ Google Summer of Code 2013 (GSoC/GCI Archive) . Hentet 14. september 2016. Arkiveret fra originalen 23. juni 2016. (ubestemt)
16. ↑ MLton i Google Summer of Code 2013 (på MLton-siden) . Hentet 14. september 2016. Arkiveret fra originalen 23. september 2016. (ubestemt)
17. ↑ MLton compiler side .
18. ↑ Ulemper ved MLton . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
19. ↑ The Breakfast Post. SML og OCaml: Så hvorfor var OCaml hurtigere?  (engelsk) . Hentet 16. september 2016. Arkiveret fra originalen 21. september 2016.
20. ↑ Sammenligning af MLton og OCaml . Hentet 13. november 2014. Arkiveret fra originalen 13. november 2014. (ubestemt)
21. ↑ The Caml Hump: ocamldefun (downlink) . Beregn Statique des Applications de Modules Parametres. Julien Signoles. JFLA 2003. (2010). Dato for adgang: 10. december 2014. Arkiveret fra originalen 4. november 2015.  (ubestemt)  — Defunctorizer for OCaml
22. ↑ Chailloux, Manoury, Pagano, "Udvikling med OCaml", 2007 .

Links

• MLton compiler  side .
• Sammenligning af MLton og OCaml
• Stephen Weeks. Compilation af hele programmet i MLton (  (engelsk) ). - 2006. Arkiveret den 29. juni 2007.
• Jens Olsson, Andreas Rossberg. Sammenligning af Standard ML og OCaml  (engelsk) (2009).
• Matthias Blume. Ikke-længere-udenlandsk: At lære en ML-kompiler at tale C "natively" (  (engelsk) ). - Elsevier Science BV, 2001. Arkiveret fra originalen den 4. april 2005.
• Matthew Fluet, Riccardo Pucella. Phantom Types and Subtyping (  (engelsk) ). - IFIP International Conference on Theoretical Computer Science, 2002.
• Zhong Shao, Andrew W. Appel. Rumeffektive lukkerepræsentationer (  (eng.) ). — Lisp og funktionel programmering, 2006.
• Chailloux, Manoury, Pagano. Udvikling af applikationer med mål Caml  (neopr.) . - 2007. - S. 349-370, kapitel 11. Interaktion med C-sproget.