ML (programozási nyelv)
ML | |
Paradigma | |
Megjelent | 1973 |
Tervező | Robin Milner |
Fejlesztő | Robin Milner |
Hatással volt rá | ISWIM |
Az ML (Meta Language) egy általános célú funkcionális programozási nyelv. A polimorf Hindley–Milner típusrendszer használatáról ismert, amely automatikusan típusokat rendel a legtöbb kifejezéshez anélkül, hogy kifejezett típushozzárendelést igényelne, és biztosítja a típusbiztonságot – hivatalosan bebizonyították, hogy a jól megírt ML program nem okoz futásidejű hibákat. Az ML biztosítja a mintafelismerést a függvényargumentumok, a szemétgyűjtés, az imperatív programozás, az érték szerinti paraméterátadás és a függvényátalakítások (currying) számára. Gyakran használják a programozási nyelvek kutatásában, és egyike azon kevés nyelveknek, amelyeket formális szemantika segítségével teljesen meg lehet határozni és ellenőrizni. Típusai és mintafelismerése alkalmassá teszik arra, hogy más formális nyelvekhez is alkalmasak legyenek, például fordítók írásához, automatikus tételbizonyításhoz és formális ellenőrzéshez.
Áttekintés
Az ML jellegzetességei közé tartoznak az érték szerinti hívások (call-by-value) kiértékelési stratégiái, az elsőosztályú függvények, automatikus memóriakezelés szemétgyűjtés útján, paraméteres polimorfizmus, statikus tipizálás, típuskövetkeztetés, kompozit adattípusok, mintafelismerés, kivételkezelés. Az ML statikus hatóköröket használ.
Az ML nem nevezhető pusztán funkcionális nyelvnek, mert bár ösztönzi a funkcionális programozást, mégis megengedi a mellékhatásokat (mint például a Lisp, de különbözik a tisztán funkcionális nyelvektől, mint a Haskell). A legtöbb programozási nyelvhez hasonlóan az ML is mohó kiértékelést alkalmaz, ami azt jelenti, hogy minden alkifejezést kiértékel, bár lusta kiértékelés is elérhető bezárások (closure) használatával. Így végtelen csatornák használhatók, akárcsak Haskellben, bár kifejezésük közvetett.
Az ML-nek szembetűnő előnyeit vannak a nyelvek tervezésében és kezelésében (fordítók, elemzők, tételbizonyítások), bár ez egy általános célú nyelv, amelyet használnak például a bioinformatikában és a pénzügyi rendszerekben is.
Az ML-t Robin Milner és mások fejlesztették ki az 1970-es évek elején az Edinburgh-i Egyetemen,[1] szintaxisát az ISWIM ihlette. Történelmileg az ML-t úgy tervezték, hogy bizonyítási taktikát dolgozzon ki az LCF tételbizonyítóban (amelynek pplambda nyelve – az elsőrendű logikai számítás és az egyszerűen tipizált polimorf lambda-számítás kombinációja – volt az ML metanyelve).
Ma több nyelv van az ML családban; a három legkiemelkedőbb a Standard ML (SML), az OCaml és az F#. Az ML ötletei számos más nyelvet is befolyásoltak, például Haskell, Cyclone, Nemerle, ATS és Elm.[2]
Példák
A következő példák a Standard ML szintaxisát használják. Más ML dialektusok, például az OCaml és az F#, kis mértékben különböznek egymástól.
Faktoriális
A faktoriális függvény tiszta ML-ként kifejezve:
fun fac (0 : int) : int = 1 | fac (n : int) : int = n * fac (n - 1)
Ez rekurzív függvényre bomlik, egyetlen végződéssel. Hasonló a matematikai tankönyvek faktoriálisának leírásához. Az ML kód hasonló a matematikai kifejezésekhez szintaxisában és funkciójában.
A megadott definíció egy része opcionális, és a típusokat írja le. Az E : t jelentése, hogy az E kifejezés típusa t. Például az n paraméter egész szám (int), és a fac (n : int) szintén az. A fac függvény tehát egész számot fogad el bevitelként, és egész számot térít vissza. A típuskövetkeztetésnek köszönhetően ez elhanyagolható, a példa pedig a következőképpen írható:
fun fac 0 = 1 | fac n = n * fac (n - 1)
Ez a függvény a mintafelismerésre is támaszkodik, amely az ML fontos része. Megjegyzendő, hogy a függvény paraméterei nem feltétlenül kell zárójelben legyenek, elég őket szóközökkel elválasztani. Ha a függvény paramétere 0, az eredmény 1 lesz. Minden más esetben a második sor fut. Ez rekurzív, és addig hajtja végre a függvényt, amíg el nem éri az alapesetet.
Nincsen garancia arra, hogy a faktoriális függvény ezen megvalósítása befejeződik, mert egy negatív paraméter végtelen hívásláncot eredményez. Egy robusztusabb kivitelezés ellenőrzi, hogy a paraméter negatív-e:
fun fact n = let fun fac 0 = 1 | fac n = n * fac (n - 1) in if (n < 0) then raise Domain else fac n end
A problémás eset (amikor n negatív) az ML kivételrendszerének használatát mutatja be.
A funkció tovább javítható a belső ciklus szubrutinként való átírásával, ezáltal a hívási verem nem növekedik a hívások számával. Ezt úgy érhetjük el, hogy egy akkumulátor paramétert helyezünk a belső ciklusba:
fun fact n = let fun fac 0 acc = acc | fac n acc = fac (n - 1) (n * acc) in if (n < 0) then raise Domain else fac n 1 end
Lista megfordítása
A következő függvény megfordítja a lista elemeit, vagyis egy új listát ad vissza, amelynek elemei fordított sorrendben vannak az eredeti listához képest.
fun reverse [] = [] | reverse (x :: xs) = (reverse xs) @ [x]
Ez a fordított megvalósítás, bár helytálló és érthető, nem hatékony, mivel négyzetes időkomplexitást igényel. A függvény átírható lineáris időigényűre:
fun 'a reverse xs : 'a list = List.foldl (op ::) [] xs
Ez a függvény a paraméter-polimorfizmus figyelemre méltó példája; bármely típusú elemek lehetnek a listában elfogadhat, és hasonló típusú elemeket térít vissza.
Modulok
A modulok az ML rendszerei nagy programok és könyvtárak felépítéséhez. A modul egy aláírásfájlból és egy vagy több struktúrafájlból áll. Az aláírásfájl meghatározza a kivitelezendő API-t (mint például egy C header vagy Java class fájl), a struktúra pedig implementálja az aláírásokat (mint ahogy egy C forrásfájl vagy Java osztályfájl). Például a következők meghatároznak egy Arithmetic aláírást egy Rational implementációt:
signature ARITH = sig type t val zero : t val succ : t -> t val sum : t * t -> t end
structure Rational : ARITH = struct datatype t = Rat of int * int val zero = Rat (0, 1) fun succ (Rat (a, b)) = Rat (a + b, b) fun sum (Rat (a, b), Rat (c, d)) = Rat (a * d + c * b , b * d) end
Ezeket a "use" paranccsal importálják az értelmezőprogramba. Az interakció csupán az aláírásfájlon keresztül megengedett, például nem hozható létre direkt egy Rat adatobjektum e kódon keresztül. A structure blokk kívülről elrejti az implementáció minden részletét.
Az ML standard könyvtárai modulokként vannak implementálva.
Jegyzetek
- ↑ Gordon: From LCF to HOL: a short history, 1996. (Hozzáférés: 2007. október 11.)
- ↑ Tate, Bruce A.. 3. Elm, Seven More Languages in Seven Weeks, Book version: P1.0-November 2014, The Pragmatic Programmers, LLC, 97, 101. o. (2014. augusztus 20.). ISBN 978-1-941222-15-7 „On page 101, Elm creator Evan Czaplicki says: 'I tend to say "Elm is an ML-family language" to get at the shared heritage of all these languages.' ["these languages" is referring to Haskell, OCaml, SML, and F#.]”
Fordítás
Ez a szócikk részben vagy egészben a ML (programming language) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
További irodalom
- The Definition of Standard ML, Robin Milner, Mads Tofte, Robert Harper, MIT Press 1990; (revised edition adds author David MacQueen), MIT Press 1997, ISBN 0-262-63181-4.
- Commentary on Standard ML, Robin Milner, Mads Tofte, MIT Press 1997, ISBN 0-262-63137-7.
- ML for the Working Programmer, Lawrence Paulson, Cambridge University Press 1991, 1996, ISBN 0-521-57050-6.
- Harper, Robert. Programming in Standard ML. Carnegie Mellon University (2011)
- Elements of ML Programming, Jeffrey D. Ullman, Prentice-Hall 1994, 1998, ISBN 0-13-790387-1.
Külső hivatkozások
- New Jersey standard ML, másik népszerű megvalósítás
- F#, egy ML megvalósítás a Microsoft segítségével NET Framework
- MLton, egy egész program, amely optimalizálja a Standard ML fordítót
- Successor-ML vagy sML
- CakeML, az ML read-eval-print ciklusváltozata, hivatalosan ellenőrzött futással és fordítással az assemblerhez