Haskell

Haskell
Logo.
Dato for første versjon 1990
Paradigmer funksjonell
Forfatter Haskell komité
Utviklere Haskell samfunn
Skrive Sterk , statisk
Dialekter Helium, O'Haskell, Mal Haskell, PolyP
Påvirket av Lisp and Scheme , ISWIM , FP , APL , Hope , SISAL , Miranda , ML , Lazy ML , Orwell , Alfl , Id , Ponder
Implementeringer GHC , Klemmer , Yhc
Operativsystem Multiplatform
Nettsted https://www.haskell.org
Filutvidelse hs og lhs

Haskell er et funksjonelt programmeringsspråk basert på lambda-calculus og kombinatorisk logikk . Navnet kommer fra matematikeren og logikeren Haskell Curry . Den ble opprettet i 1990 av en komité av språkteoriforskere som er interessert i funksjonelle språk og lat evaluering . Den siste standarden er Haskell 2010  : det er en minimal og bærbar versjon av språket designet for pedagogiske og praktiske formål, av hensyn til interoperabilitet mellom språkimplementeringer og som grunnlag for fremtidige utvidelser. Språket fortsetter å utvikle seg i 2020, hovedsakelig med GHC , og utgjør dermed en de facto standard med mange utvidelser.

Historisk

Mirandas utgivelse i 1985 utløste en fornyet interesse for dovne evalueringsfunksjonelle språk og førte til en eksplosjon i antall slike eksperimentelle språk, slik at i 1987 var mer enn et dusin tilgjengelig. Miranda var uten tvil den mest populære, men den lukkede proprietære modellen oppmuntret ikke til bidrag og på konferansen Functional Programming Languages ​​and Computer Architecture (FPCA '87) i Portland , Oregon , konkluderte et møte med fremtredende forskere i feltet at det ville være ønskelig å etablere en åpen standard som kan tjene som et felles grunnlag for fremtidig forskning på funksjonelle språk . For dette formålet dannet de en komité hvis oppgave ville være å samle styrkene til datidens prototyper.

Versjoner

Haskell 1.0 til 1.4

Komiteens arbeid fortsatte fra møte til møte og kulminerte i 1990 med definisjonen av Haskell 1.0, etterfulgt av ulike revisjoner for versjon 1.1, 1.2, 1.3 og 1.4.

Haskell 98

Haskell 98- rapporten etablerer en varig standard som alle etterfølgende implementeringer er basert på. En revidert versjon vises ijanuar 2003.

Haskell 2010

Prosessen med å revidere Haskell-standarden, kalt Haskell '(uttales "  Haskell Prime  ") begynte i 2006. Opprinnelig utført med sikte på å publisere en ny versjon av Haskell-standarden, anstrengte innsatsen for å bli på plass på en bærekraftig måte og har nå satt seg et mer begrenset mål: å publisere regelmessig (teoretisk en gang i året) en revisjon av 1998-rapporten som inneholder noen nye funksjoner introdusert siden av GHC og utvilsomt akseptert og brukt av samfunnet. Haskell 2010 la dermed til en definisjon av Haskells grensesnittmekanisme med andre språk (FFI: interface for utenlandske funksjoner ) og fjernet "n + k" -mønstrene fra språket (som tillot skriving :) decrement (n+1) = n. Det formaliserte også en mekanisme for å spesifisere hvilken standard man ønsker å respektere i en gitt kildefil, samt eventuelle utvidelser, som bekrefter den ganske modulære naturen til Haskell brukt i praksis.

Forskningsversjoner

Fra og med 2012 er Haskell trolig det funksjonelle språket som det er forsket på mest forskning på. Flere varianter er utviklet. Parallelliserte versjoner laget ved Laboratory for Computer Science ved Massachusetts Institute of Technology (MIT) og ved University of Glasgow har begge blitt kalt Parallel Haskell. Mer parallelliserte og distribuerte versjoner kalles Distribuert Haskell (tidligere Goffin) og Eden, det er også et forsøk på å bruke Haskell i cloud computing kalt Cloud Haskell. En spekulativ kjøretidsversjon , Eager Haskell og flere objektorienterte versjoner, Haskell ++, O'Haskell og Mondrian har dukket opp. Disse forskjellige forskningsversjonene var ganske ofte basert på GHC og satte ofte sitt preg på denne kompilatoren da eksperimentering viste seg å være vellykket, og inspirerte dermed til den nåværende støtten for tråder og ulike former for kodeparallellisering.

Funksjoner

Det mest interessante funksjonene i Haskell er støtte for rekursive funksjoner , typen slutning , forståelse lister , lat evaluering, og uendelig datastrukturer, godt eksempel på noe som er datatypen strømmen . Disse funksjonene, spesielt når de kombineres, gjør det lettere å skrive og bruke funksjoner og manipulere data. Typesystemet, som har vært gjenstand for mye forskning, er også en av de mest uttrykksfulle og en av de mest tilbøyelige til å implementere, på en statisk måte , mange begrensninger som vanligvis blir verifisert ved kjøretid. Haskell utmerker seg også ved bruk av monader for inngang / utgang og for unntakshåndtering, nødvendig av en av de viktigste spesifikasjonene i språket, nemlig at Haskell er et rent funksjonelt språk, noe som betyr at iboende ingen bivirkninger er tillatt , verken innganger / utganger, eller variable oppgaver eller unntak. De fleste funksjonelle språk oppmuntrer denne stilen, men Haskell pålegger den i en hvilken som helst kode som ikke eksplisitt indikerer ved sin type at den innrømmer bivirkninger og som takket være denne mekanismen forhindrer og begrenser farene.

Kodeeksempler

Faktoriell funksjon (rekursiv)

Den klassiske definisjonen av faktorfunksjonen  :

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

Faktorfunksjon (med produkt)

Den elegante definisjonen av faktorfunksjonen (som bruker Haskell-funksjonen productog listenotasjonen):

fac n = product [1..n]

Faktorfunksjon (uendelig liste)

Det er også mulig å definere en liste over alle faktorene:

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

Den forrige verdien er en uendelig liste, noe som er fullt mulig med lat evaluering . Takket være denne listen kan vi implementere facpå denne måten:

fac n = facs !! n

( !!er en operatør som returnerer det niende elementet i en liste).

Som facser lat evaluert i fac, fac nforårsaker et kall til at bare de første vilkårene blir evaluert facs. Merk at verdien av hvert element av facsblir evaluert bare en gang.

Fibonacci-funksjon (naiv)

En naiv implementering av funksjonen som returnerer det niende tallet i Fibonacci-sekvensen  :

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

Fibonacci-funksjon (uendelig liste)

En funksjon som returnerer den uendelige listen over Fibonacci-tall, også takket være lat evaluering:

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

I motsetning til den naive versjonen, er kompleksiteten i en samtale til fiblineær, og dette takket være memoarisering .

Faktisk, i den forrige versjonen ble verdiene av fib beregnet for hver forespørsel. Dermed fib 4forårsaker en samtale en samtale fib 3og en samtale til den fib 2som kaller seg igjen fib 2, to ganger fib 1og en gang fib 0, etc.

På den annen side, når det gjelder den uendelige listen, fibberegnes hver verdi av bare en gang og lagres deretter i minnet.

Søk etter primtall

Takket være mekanismen for lat evaluering er det også mulig å definere hele (og uendelige) listen over primtall  :

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

Denne algoritmen er imidlertid veldig ineffektiv, og en implementering av Eratosthenes sil gir mye bedre ytelse.

For å gjøre søket mer effektivt, kan vi bekrefte at tallet hvis primality er testet, ikke kan deles med noen av primtallene mindre enn kvadratroten. En implementering i Haskell kan være:

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

Rask sortering (kviksort)

Den raske sorteringsalgoritmen kan skrives i Haskell ved å manipulere lister:

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]

Eller

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

På grunn av listekopier og sammenkoblinger kan denne koden være treg, avhengig av kompilatoren. En forbedring er å utføre sammenligningstesten bare en gang:

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)

Imidlertid har disse naive implementeringene av rask sort ulempen med å være av en kompleksitet (O (N²)) når det gjelder en sortert liste.

Implementeringer

Følgende implementeringer er alle kompatible (eller nesten kompatible) med Haskell 98-standarden, og distribueres under gratis lisenser. Alle Haskell-implementeringer er for øyeblikket gratis programvare .

  • GHC . Glasgow Haskell Compiler samler koden naturlig på mange arkitekturer, og kompilerer også i C. GHC er sannsynligvis den mest populære av Haskell-kompilatorene, og den inneholder noen veldig nyttige biblioteker (f.eks. Bindinger for OpenGL ) som bare fungerer med GHC.
  • Hugs er en bytecode- tolk . Det gir rask kompilering og rimelig kjøringshastighet. Den har også et enkelt grafikkbibliotek. Hugs egner seg godt til å lære Haskell, men det skal ikke antas at Hugs er en forenklet implementering. Det er den mest bærbare og letteste av Haskells implementeringer.
  • nhc98 er en annen bytecode-tolk, men bytecode går raskere enn med Hugs. Nhc98 fokuserer på minimal minnebruk, og det er et anbefalt valg for eldre maskiner.
  • HBC er en annen innfødt kompilator. Det har ikke blitt utviklet på en stund, men det er fortsatt brukbart.

Noen Haskell-suksesser

Fordi ikke-prosessuelt kan Haskell redusere feilsøkingsbehovet betydelig: utsagn (et Haskell-program inkluderer kun utsagn) som uavhengige av hverandre, trenger ikke programmereren å ta seg av noen flomkontroll eller til og med sekvensen eller konteksten av utsagnene; Det kommer derfor ikke som noen overraskelse at prosjekter blir utført i Haskell før de er tilgjengelige på andre språk. De mest kjente eksemplene er:

  • Omskriving av Facebooks anti-spam-system, Sigma , med Haskell, som erstatter det tidligere brukte proprietære språket, FXL. Sigma behandler over en million forespørsler per sekund.
  • Pandoc , programvare for konvertering av dokumentdokumenter.
  • Xmonad , vindusbehandler .
  • Darcs , desentralisert programvare for versjonsadministrasjon .
  • Pugs , en implementering av Perl 6 gjort tilgjengelig lenge før den offisielle utgivelsen av språkversjonen basert på den virtuelle Parrot -maskinen .
  • nget- programmet , som gjør det mulig å samle alle bildene fra en Usenet-nyhetsgruppe - for eksempel av astronomi - hvis første versjon ble kodet i Haskell (en versjon på C ++ språk ble deretter utviklet for å lette portering).

Språk som ligner på Haskell

  • Concurrent Clean, som tilbyr støtte for opprettelse av GUIer samt CAL (Quarks Framework) som er basert på Java VM og er ment å integreres som en Java API-utvidelse.
  • en pedagogisk versjon av Haskell, kalt Gofer, ble utviklet av Mark Jones, og ble til slutt erstattet av HUGS, Haskell User's Gofer System.
  • ML- språk er også ganske nær Haskell, med sin vanlige filosofi om funksjonell programmering og statisk skriving. Ocaml er den mest populære representanten for denne språkfamilien, kjent i Frankrike for sin undervisning i forberedende klasse og på universitetet. I Frankrike forblir det således mye mer praktisert enn Haskell .
  • Selv om PureScript er et strengt språk, er dens syntaktiske likhet med Haskell tydelig til tross for noen få forskjeller.
  • DAML, et smart kontraktspråk basert på Glasgow Haskell Compiler .

Referanser

  1. http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29
  2. (no-US) “  Fighting spam with Haskell  ” , på Facebook Engineering ,26. juni 2015(åpnet 28. mai 2020 )
  3. "  Purescript / documentation  " , på GitHub (åpnet 11. august 2020 ) .

Se også

Relaterte artikler

Eksterne linker