Haskell

Haskell
Logo.
Data pierwszej wersji 1990
Paradygmaty funkcjonalny
Autor Komitet Haskella
Deweloperzy Społeczność Haskella
Pisanie na maszynie Mocny , statyczny
Dialekty Hel, O'Haskell, Szablon Haskell, PolyP
Wpływem Lisp i Schemat , ISWIM , FP , APL , Hope , SISAL , Miranda , ML , Lazy ML , Orwell , Alfl , Id , Ponder
Realizacje GHC , Uściski , Yhc
System operacyjny Wieloplatformowy
Stronie internetowej https://www.haskell.org
Rozszerzenie pliku hs i lhs

Haskell to funkcjonalny język programowania oparty na rachunku lambda i logice kombinatorycznej . Jego nazwa pochodzi od matematyka i logika Haskella Curry'ego . Został stworzony w 1990 roku przez komitet badaczy teorii języka zainteresowanych językami funkcjonalnymi i leniwą oceną . Najnowszym standardem jest Haskell 2010  : jest to minimalna i przenośna wersja języka zaprojektowana do celów edukacyjnych i praktycznych, ze względu na interoperacyjność między implementacjami języka oraz jako podstawa dla przyszłych rozszerzeń. Język nadal ewoluuje w 2020 roku, głównie z GHC , stanowiąc tym samym de facto standard z wieloma rozszerzeniami.

Historyczny

Mirandy uwolnienie w 1985 roku wywołał ponowne zainteresowanie w ewaluacji leniwy języków funkcyjnych i doprowadził do eksplozji liczby tych językach doświadczalnych, tak że przez 1987 więcej niż tuzin były dostępne. Miranda był zdecydowanie najbardziej popularne, ale jego zamknięta zastrzeżony wzór nie zachęcają składek i na Programowanie funkcyjne Języki i Computer Architecture (FPCA '87) konferencji w Portland , Oregon , spotkanie wybitnych naukowców w dziedzinie stwierdziła, że byłoby pożądane byłoby ustanowienie otwartego standardu, który mógłby służyć jako wspólna podstawa dla przyszłych badań nad językami funkcjonalnymi . W tym celu utworzyli komitet, którego zadaniem miało być połączenie sił ówczesnych prototypów.

Wersje

Haskella 1,0 do 1,4

Prace komitetu trwały od spotkań do spotkań i zakończyły się w 1990 roku definicją Haskella 1.0, po której nastąpiły różne poprawki dla wersji 1.1, 1.2, 1.3 i 1.4.

Haskella 98

Raport Haskella 98 ustanawia trwały standard, na którym opierają się wszystkie kolejne implementacje. Zmieniona wersja pojawia się wstyczeń 2003.

Haskella 2010

Proces rewizji standardu Haskell, nazwanego Haskell '(czyt. "  Haskell Prime  ") rozpoczął się w 2006 roku. Początkowo podjęty w celu opublikowania nowej wersji standardu Haskella, starano się wprowadzić w zrównoważony sposób i postawił sobie teraz bardziej ograniczony cel: regularne publikowanie (teoretycznie raz w roku) rewizji raportu z 1998 roku, uwzględniającego pewne nowe funkcje wprowadzone od tego czasu przez GHC i bezsprzecznie akceptowane i wykorzystywane przez społeczność. Haskell 2010 dodał więc definicję mechanizmu interfejsu Haskella z innymi językami (FFI: interfejs funkcji obcych ) i usunął wzorce „n+k” z języka (co pozwalało na pisanie:) decrement (n+1) = n. Sformalizował również mechanizm określania, jaki standard chcemy respektować w danym pliku źródłowym, a także wszelkie rozszerzenia, potwierdzając dość modułową naturę Haskella stosowanego w praktyce.

Wersje badawcze

Od 2012 r. Haskell jest prawdopodobnie językiem funkcjonalnym, nad którym podjęto najwięcej badań. Opracowano kilka wariantów. Wersje zrównoleglone wykonane w Laboratorium Informatyki w Massachusetts Institute of Technology (MIT) oraz na Uniwersytecie w Glasgow zostały nazwane Parallel Haskell. Bardziej zrównoleglone i rozproszone wersje nazywają się Distributed Haskell (dawniej Goffin) i Eden, istnieje również próba wykorzystania Haskella w chmurze obliczeniowej o nazwie Cloud Haskell. Pojawiła się spekulacyjna wersja środowiska uruchomieniowego Eager Haskell oraz kilka wersji obiektowych Haskell ++, O'Haskell i Mondrian. Te różne wersje badawcze były dość często oparte na GHC i często pozostawiały ślad na tym kompilatorze, gdy eksperymenty okazały się skuteczne, inspirując w ten sposób obecne wsparcie dla wątków i różnych form zrównoleglania kodu.

funkcje

Najciekawsze cechy Haskella to obsługa funkcji rekurencyjnych , wnioskowanie o typie , listy ze zrozumieniem , leniwa ocena i nieskończone struktury danych , czego najlepszym przykładem jest typ danych stream . Te cechy, zwłaszcza w połączeniu, ułatwiają pisanie i używanie funkcji oraz manipulowanie danymi. System typów, który był przedmiotem wielu badań, jest również jednym z najbardziej wyrazistych i jednym z najłatwiejszych do implementacji, w sposób statyczny , wielu ograniczeń, które są zwykle weryfikowane w czasie wykonywania. Haskell wyróżnia się również wykorzystaniem monad do obsługi wejścia/wyjścia oraz obsługi wyjątków, wymuszonych jedną z najważniejszych cech charakterystycznych języka, a mianowicie tym, że Haskell jest językiem czysto funkcjonalnym, co oznacza, że ​​z natury nie są dozwolone żadne skutki uboczne , ani wejścia/wyjścia, ani przypisania zmiennych, ani wyjątki. Większość języków funkcjonalnych zachęca do tego stylu, ale Haskell narzuca go w każdym kodzie, który nie wskazuje jednoznacznie swoim typem, że dopuszcza skutki uboczne i który dzięki temu mechanizmowi zapobiega i ogranicza jego niebezpieczeństwa.

Przykłady kodu

Funkcja silnia (rekurencyjna)

Klasyczna definicja funkcji silni  :

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

Funkcja czynnikowa (z produktem)

Elegancka definicja funkcji silni (która wykorzystuje funkcję Haskella producti notację listową):

fac n = product [1..n]

Funkcja silnia (lista nieskończona)

Możliwe jest również zdefiniowanie listy wszystkich silni:

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

Poprzednia wartość jest nieskończoną listą, co jest całkiem możliwe przy leniwej ocenie . Dzięki tej liście możemy zrealizować facw ten sposób:

fac n = facs !! n

( !!jest operatorem zwracającym n-ty element listy).

Jak facsjest leniwie oceniane w fac, wywołanie to fac npowoduje, że oceniane jest tylko pierwsze n warunków facs. Zauważ, że wartość każdego elementu facsjest oceniana tylko raz.

Funkcja Fibonacciego (naiwna)

Naiwna implementacja funkcji zwracającej n-tą liczbę ciągu Fibonacciego  :

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

Funkcja Fibonacciego (lista nieskończona)

Funkcja zwracająca nieskończoną listę liczb Fibonacciego, również dzięki leniwej ocenie:

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

W przeciwieństwie do wersji naiwnej złożoność wywołania fibjest liniowa, a to dzięki memoisation .

Rzeczywiście, w poprzedniej wersji wartości fib były obliczane dla każdego żądania. W ten sposób wywołanie fib 4powoduje wywołanie fib 3i fib 2ponowne wywołanie tego wywołania fib 2, dwa razy fib 1i jeden raz fib 0, itd.

Z kolei w przypadku listy nieskończonej każda wartość fibjest obliczana tylko raz, a następnie zapisywana w pamięci.

Szukaj liczb pierwszych

Dzięki mechanizmowi leniwego obliczania możliwe jest również zdefiniowanie całej (i nieskończonej) listy liczb pierwszych  :

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

Algorytm ten jest jednak bardzo nieefektywny, a zastosowanie sita Eratostenesa pozwala na znacznie lepszą wydajność.

Aby wyszukiwanie było bardziej wydajne, możemy sprawdzić, czy liczba, której pierwszorzędność jest testowana, nie jest podzielna przez żadną z liczb pierwszych mniejszych od jej pierwiastka kwadratowego. Implementacja w Haskell może być:

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

Szybkie sortowanie (szybkie sortowanie)

Algorytm szybkiego sortowania można napisać w Haskell, manipulując listami:

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]

Lub

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

Ze względu na kopie list i konkatenacje ten kod może być powolny, w zależności od kompilatora. Udoskonalenie polega na wykonaniu testu porównawczego tylko raz:

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)

Jednak te naiwne implementacje szybkiego sortowania mają tę wadę, że są złożonością (O (N²)) w przypadku posortowanej listy.

Realizacje

Wszystkie poniższe implementacje są kompatybilne (lub prawie kompatybilne) ze standardem Haskell 98 i są rozpowszechniane na wolnych licencjach. Wszystkie implementacje Haskella są obecnie wolnym oprogramowaniem .

  • GHC . Glasgow Haskell Compiler kompiluje kod natywnie na wielu architekturach, a także kompiluje w C. GHC jest prawdopodobnie najpopularniejszym z kompilatorów Haskella i zawiera kilka bardzo przydatnych bibliotek (np. wiązania dla OpenGL ), które działają tylko z GHC.
  • Hugs to interpreter kodu bajtowego . Oferuje szybką kompilację i rozsądną szybkość wykonywania. Posiada również prostą bibliotekę graficzną. Uściski dobrze nadają się do nauki Haskella, ale nie należy zakładać, że Uściski to uproszczona implementacja. Jest to najbardziej przenośna i najlżejsza z implementacji Haskella.
  • nhc98 to kolejny interpreter kodu bajtowego, ale kod bajtowy działa szybciej niż w przypadku Hugs. Nhc98 skupia się na minimalnym zużyciu pamięci i jest zalecanym wyborem dla starszych komputerów.
  • HBC to kolejny natywny kompilator. Od pewnego czasu nie jest rozwijany, ale nadal nadaje się do użytku.

Niektóre sukcesy Haskella

Ponieważ nie jest to procedura proceduralna, Haskell może znacznie ograniczyć potrzeby debugowania: instrukcje (program Haskella zawiera tylko instrukcje) są od siebie niezależne, programista nie musi zajmować się żadną kontrolą zalania, ani nawet kolejnością lub kontekstem instrukcji; Nic więc dziwnego, że projekty są realizowane w Haskell, zanim będą dostępne w innych językach. Najbardziej znane przykłady to:

  • Przepisanie systemu antyspamowego Facebooka, Sigma , za pomocą Haskella, zastępując poprzednio używany, zastrzeżony język FXL. Sigma przetwarza ponad milion żądań na sekundę.
  • Pandoc , oprogramowanie do konwersji dokumentów z wiersza poleceń.
  • Xmonad , menedżer okien .
  • Darcs , zdecentralizowane oprogramowanie do zarządzania wersjami .
  • Pugs , implementacja Perla 6 udostępniona na długo przed oficjalnym wydaniem wersji językowej opartej na maszynie wirtualnej Parrot .
  • program nget , umożliwiający zbieranie wszystkich obrazów grupy dyskusyjnej Usenet - na przykład astronomii - którego pierwsza wersja została zakodowana w Haskell ( następnie opracowano wersję w języku C++, aby ułatwić portowanie).

Języki podobne do Haskella

  • Concurrent Clean, który oferuje wsparcie dla tworzenia GUI oraz CAL (Quarks Framework), który jest oparty na Java VM i jest przeznaczony do integracji jako rozszerzenie Java API.
  • edukacyjna wersja Haskella, zwana Gofer, została opracowana przez Marka Jonesa i ostatecznie została zastąpiona przez HUGS, Haskell User's Gofer System.
  • Języki ML są również dość bliskie Haskellowi, dzięki ich wspólnej filozofii programowania funkcjonalnego i statycznego typowania. Ocaml jest najpopularniejszym przedstawicielem tej rodziny języków, znanym we Francji z nauczania w klasie przygotowawczej i na uniwersytecie. We Francji jest to zatem znacznie bardziej praktykowane niż Haskell .
  • Chociaż PureScript jest językiem ścisłym, jego syntaktyczne podobieństwo do Haskella jest oczywiste pomimo kilku różnic.
  • DAML, inteligentny język kontraktów oparty na kompilatorze Glasgow Haskell Compiler .

Bibliografia

  1. http://en.literateprograms.org/Sieve_of_Eratostenes_%28Haskell%29
  2. (en-US) „  Walka ze spamem za pomocą Haskella  ” , na Facebook Engineering ,26 czerwca 2015(dostęp 28 maja 2020 r. )
  3. „  Purescript/documentation  ” , na GitHub (dostęp 11 sierpnia 2020 r . ) .

Zobacz również

Powiązane artykuły

Linki zewnętrzne