Haskell

Haskell
Logó.
Az első változat kelte 1990
Paradigmák funkcionális
Szerző Haskelli bizottság
Fejlesztők Haskell közösség
Gépelés Erős , statikus
Nyelvjárások Hélium, O'Haskell, Template Haskell, PolyP
Befolyásolta Lisp és Scheme , ISWIM , FP , APL , Hope , SISAL , Miranda , ML , Lazy ML , Orwell , Alfl , Id , Ponder
Végrehajtások GHC , ölelések , YHC
Operációs rendszer Többplatformos
Weboldal https://www.haskell.org
Fájlkiterjesztés hs és lhs

A Haskell egy funkcionális programozási nyelv, amely lambda-számításon és kombinatorikus logikán alapul . A neve Haskell Curry matematikus és logikus származik . 1990-ben a funkcionális nyelvek és a lusta értékelés iránt érdeklődő nyelvelméleti kutatókból álló bizottság hozta létre . A legújabb szabvány a Haskell 2010  : ez a nyelv minimális és hordozható változata, amelyet oktatási és gyakorlati célokra terveztek, a nyelv megvalósításai közötti interoperabilitás érdekében és a jövőbeni kiterjesztések alapjaként. A nyelv tovább fejlődik 2020-ban, főként a GHC-vel , így de facto szabványt jelent , számos kiterjesztéssel.

Történelmi

Miranda 1985-ös kiadása újból felkeltette az érdeklődést a lusta értékelési funkcionális nyelvek iránt, és robbanáshoz vezetett az ilyen kísérleti nyelvek száma, így 1987-re több mint egy tucat állt rendelkezésre. A Miranda volt messze a legnépszerűbb, de zárt, saját modellje nem ösztönözte a közreműködést, és az Oregonban , Portland- ben megrendezett Funkcionális programozási nyelvek és számítógépes építészet (FPCA '87) konferencián a terület kiemelkedő kutatóinak találkozója arra a következtetésre jutott, hogy kívánatos egy olyan nyílt szabvány létrehozása, amely közös alapként szolgálhat a funkcionális nyelvekkel kapcsolatos jövöbeli kutatásokhoz . Ennek érdekében létrehoztak egy bizottságot, amelynek feladata az akkori prototípusok erősségeinek összegyűjtése lenne.

Verziók

Haskell 1.0–1.4

A bizottság munkája az üléstől az ülésig folytatódott és 1990-ben tetőzött a Haskell 1.0 meghatározásával, majd az 1.1, 1.2, 1.3 és 1.4 változatok különféle átdolgozásával.

Haskell 98

A Haskell 98 jelentés tartós szabványt állít fel, amelyen minden későbbi megvalósítás alapul. A módosított változat itt jelenik meg2003. január.

Haskell 2010

A Haskell szabvány (Haskell néven) (ejtsd: " Haskell Prime  ") felülvizsgálatának folyamata  2006-ban kezdődött. Eredetileg a Haskell szabvány új változatának közzététele céljából folytatták az erőfeszítéseket, amelyek fenntartható módon történtek, és most egy korlátozottabb célt tűzött ki maga elé: rendszeresen (elméletileg évente egyszer) közzétenni az 1998-as jelentés felülvizsgálatát, amely tartalmaz néhány újdonságot, amelyet a GHC vezetett be, és a közösség vitathatatlanul elfogadott és használt. A Haskell 2010 így hozzáadta a Haskell interfész-mechanizmusának definícióját más nyelvekhez (FFI: idegen függvények interfésze ), és eltávolította az „n + k” mintákat a nyelvből (ami lehetővé tette az írást :) decrement (n+1) = n. Formalizálta azt a mechanizmust is, amely meghatározza, hogy az adott forrásfájlban mely szabványokat kívánja betartani, valamint az esetleges kiterjesztéseket, megerősítve ezzel a gyakorlatban használt Haskell meglehetősen moduláris jellegét.

Kutatási verziók

2012-től valószínűleg Haskell az a funkcionális nyelv, amelyen a legtöbb kutatást végezték. Számos változatot fejlesztettek ki. A Massachusettsi Műszaki Intézet (MIT) és a Glasgowi Egyetem Számítástudományi Laboratóriumában és a Glasgowi Egyetemen készített párhuzamos változatokat párhuzamos Haskellnek hívták. A párhuzamosabb és elosztottabb verziók neve Distributed Haskell (korábban Goffin) és Eden, és a Haskell-t felhőalapú számítástechnikában is megpróbálják felhasználni Cloud Haskell néven. Megjelent egy spekulatív futásidejű verzió , az Eager Haskell és számos objektumorientált verzió, a Haskell ++, az O'Haskell és a Mondrian. Ezek a különféle kutatási verziók meglehetősen gyakran a GHC-n alapultak, és gyakran rányomták a bélyegüket erre a fordítóra, amikor a kísérlet sikeresnek bizonyult, ezáltal ösztönözve a szálak és a kódok párhuzamosításának különböző formáit.

Jellemzők

A Haskell legérdekesebb jellemzői a rekurzív függvények támogatása , a típus következtetés , a megértési listák , a lusta értékelés és a végtelen adatstruktúrák, amelyek elsődleges példája az adattípus- áram . Ezek a funkciók, különösen kombinálva, megkönnyítik a funkciók írását és használatát, valamint az adatok manipulálását. A sokféle kutatás tárgyát képező típusrendszer egyben az egyik legkifejezőbb és az egyik legalkalmasabb statikus módon megvalósítani számos olyan korlátozást, amelyet általában futás közben ellenőriznek. Haskell megkülönböztethető a monádok használatával az I / O és a kivételkezelés számára is, amelyet a nyelv egyik legfontosabb sajátossága követel meg, nevezetesen, hogy a Haskell tiszta funkcionális nyelv, ami azt jelenti, hogy eredendően semmilyen mellékhatás nem megengedett , sem bemenetek / kimenetek, sem változó hozzárendelések, sem kivételek. A legtöbb funkcionális nyelv ösztönzi ezt a stílust, de Haskell minden olyan kódban előírja, amely típusa szerint nem kifejezetten jelzi, hogy elfogadja a mellékhatásokat, és amely ennek a mechanizmusnak köszönhetően megakadályozza és körülhatárolja annak veszélyeit.

Kódpéldák

Faktoriális függvény (rekurzív)

A faktoriális függvény klasszikus meghatározása  :

fac n = if n > 0 then n * fac(n - 1) else 1

Faktoriális függvény (termékkel)

A faktoriális függvény elegáns meghatározása (amely a Haskell függvényt productés a listák jelölését használja):

fac n = product [1..n]

Faktoriális függvény (végtelen lista)

Meghatározható az összes tényező listája is:

facs = 1: zipWith (*) facs [1..]

Az előző érték egy végtelen lista, ami lusta értékeléssel teljesen lehetséges . Ennek a listának köszönhetően így tudjuk megvalósítani fac:

fac n = facs !! n

( !!olyan operátor, amely a lista n-edik elemét adja vissza).

Amint facsazt lustán értékeljük fac, a felhívás fac ncsak az első n tag értékelését eredményezi facs. Vegye figyelembe, hogy a (z) elem minden elemének facsértékét csak egyszer értékelik ki.

Fibonacci funkció (naiv)

A funkció naiv megvalósítása, amely visszaadja a Fibonacci-szekvencia n-edik számát  :

fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)

Fibonacci függvény (végtelen lista)

Egy olyan funkció, amely visszaadja a Fibonacci-számok végtelen listáját, a lusta értékelésnek is köszönhetően:

fibs = 0 : 1 : (zipWith (+) fibs (tail fibs)) fib n = fibs !! n

A naiv verzióval ellentétben a hívás bonyolultsága fiblineáris, és ez a memoázásnak köszönhető .

Valójában az előző verzióban a fib értékeket kiszámították minden egyes kéréshez. Így hívás fib 4okoz a hívást fib 3, és a hívás fib 2, hogy hívják magukat újra fib 2, két alkalommal fib 1, egyszer fib 0, stb

Másrészt a végtelen lista esetén az egyes értékeket fibcsak egyszer számítják ki, majd tárolják a memóriában.

Prímszámok keresése

A lusta értékelés mechanizmusának köszönhetően meg lehet határozni a prímszámok teljes (és végtelen) listáját is  :

primes = remDivs [2..] where remDivs (x:xs) = x: remDivs [n | n <- xs, (mod n x) /= 0]

Ez az algoritmus azonban nagyon nem hatékony, és az Eratosthenes szita megvalósítása sokkal jobb teljesítményt tesz lehetővé.

A keresés hatékonyabbá tétele érdekében ellenőrizhetjük, hogy az a szám, amelynek elsődlegességét tesztelik, nem osztható a négyzetgyökénél kisebb prímszámok egyikével sem. A Haskellben megvalósítás lehet:

prem = 2:[a | a <- [3,5..], (all (/= 0) (map (\x -> mod a x) (takeWhile (<= truncate(sqrt (fromIntegral a::Float))) prem))) ]

Gyors rendezés (quicksort)

A gyors rendezési algoritmus a listák manipulálásával írható Haskell-be:

qsort [] = [] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x where elts_lt_x = [y | y <- xs, y < x] elts_greq_x = [y | y <- xs, y >= x]

Vagy

qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

A listás másolatok és összefűzések miatt ez a kód a fordítótól függően lassú lehet. Javulás az, hogy az összehasonlító tesztet csak egyszer kell elvégezni:

qSort :: (Ord a) => [a] -> [a] qSort [] = [] qSort (mid:xs) = qSort inf ++eg++ qSort sup where (inf, eg, sup) = sep xs ([],[mid],[]) where sep [] tuple = tuple sep (y:ys) (i,e,s) | (y < mid) = sep ys (y:i,e,s) | (y == mid) = sep ys (i,y:e,s) | otherwise = sep ys (i,e,y:s)

Ezeknek a naiv, gyors rendezésű megvalósításoknak az a hátránya, hogy egy rendezett lista esetében összetettségűek (O (N²)) .

Végrehajtások

A következő megvalósítások mind kompatibilisek (vagy csaknem kompatibilisek) a Haskell 98 szabvánnyal, és ingyenes licencek alatt kerülnek terjesztésre. A Haskell összes megvalósítása jelenleg ingyenes szoftver .

  • GHC . A Glasgow Haskell Compiler natív módon fordítja le a kódot számos architektúrán, és C.-ben is fordítja. A GHC valószínűleg a legnépszerűbb a Haskell-fordítók közül, és tartalmaz néhány nagyon hasznos könyvtárat (például az OpenGL-hez való kötéseket), amelyek csak GHC-vel működnek.
  • Az Hugs egy bytecode tolmács . Gyors összeállítást és ésszerű végrehajtási sebességet kínál. Egyszerű grafikus könyvtárral is rendelkezik. Az ölelések jól alkalmazzák Haskell megtanulását, de nem szabad feltételezni, hogy az ölelések egyszerűsített megvalósítás. Ez a leginkább hordozható és legkönnyebb Haskell megvalósításai közül.
  • Az nhc98 egy másik bájtkódértelmező, de a bájtkód gyorsabban fut, mint az öleléseknél. Az Nhc98 a minimális memóriafelhasználásra összpontosít, és régebbi gépek számára ajánlott választás.
  • A HBC egy másik natív fordító. Egy ideje nem fejlesztették, de mégis használható.

Néhány Haskell-siker

Mivel a nem eljárásjogi szempontból a Haskell jelentősen csökkentheti a hibakeresési igényeket: a kijelentések (egy Haskell-program csak utasításokat tartalmaz ) függetlenek egymástól, a programozónak nem kell gondoskodnia semmilyen árvízszabályozásról, sőt az állítások sorrendjéről vagy kontextusáról sem; Ezért nem meglepő, hogy a projekteket Haskellben hajtják végre, mielőtt más nyelveken elérhetővé válnának. A leghíresebb példák:

  • Írja át a Facebook spam-ellenes rendszerét, a Sigma -t Haskellel, és cserélje le a korábban használt saját nyelvet, az FXL-t. A Sigma másodpercenként több mint egymillió kérelmet dolgoz fel.
  • Pandoc , parancssori dokumentumkonvertáló szoftver.
  • Xmonad , ablakkezelő .
  • Darcs , decentralizált verziókezelő szoftver .
  • Pugs , a Perl 6 implementációja, amelyet jóval a Parrot virtuális gépen alapuló nyelvi változat hivatalos kiadása előtt tettek elérhetővé .
  • az nget program , lehetővé téve egy Usenet-hírcsoport összes képének összegyűjtését - például a csillagászatról -, amelynek első verzióját Haskell-ben kódolták (a portolás megkönnyítésére aztán C ++ nyelvű verziót fejlesztettek ki).

A Haskellhez hasonló nyelvek

  • A Concurrent Clean, amely támogatást nyújt a grafikus felhasználói felület és CAL (Quarks Framework) létrehozásához, amely Java virtuális gépen alapul, és integrációra szolgál Java API kiterjesztésként.
  • a Haskell oktatási változatát Gofer néven Mark Jones fejlesztette ki, és végül a HUGS, a Haskell felhasználói Gofer rendszere váltotta fel.
  • Az ML nyelvek szintén meglehetősen közel állnak Haskellhez, a funkcionális programozás és a statikus tipizálás közös filozófiájával. Az Ocaml a legnépszerűbb képviselője ennek a nyelvcsaládnak, amely Franciaországban ismert az előkészítő osztályban és az egyetemen tanított. Franciaországban így sokkal gyakoroltabb marad, mint Haskell .
  • Noha a PureScript szigorú nyelv, a Haskellhez való szintaktikai hasonlóság néhány különbség ellenére is nyilvánvaló.
  • DAML, a Glasgow Haskell Compiler alapú intelligens szerződéses nyelv .

Hivatkozások

  1. http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29
  2. (hu-USA) „  Spam elleni küzdelem Haskell-lel  ” , a Facebook Engineering-en ,2015. június 26(megtekintés : 2020. május 28. )
  3. "  Purescript / dokumentáció  " , a GitHub (elérhető 11 augusztus 2020 ) .

Lásd is

Kapcsolódó cikkek

Külső linkek