To jest stara wersja strony!
Michał Kołodziej, kolodziej.michal@gmail.com
Read on the Mercury language. Describe concepts, examples, compare to Prolog and Haskell.
From: „Mercury Language Reference”, introduction:
Mercury is a new general-purpose programming language, designed and implemented by a small group of researchers at the University of Melbourne, Australia. Mercury is based on the paradigm of purely declarative programming, and was designed to be useful for the development of large and robust “real-world” applications. It improves on existing logic programming languages by providing increased productivity, reliability and efficiency, and by avoiding the need for non-logical program constructs. Mercury provides the traditional logic programming syntax, but also allows the syntactic convenience of user-defined functions, smoothly integrating logic and functional programming into a single paradigm.
Mercury requires programmers to supply type, mode and determinism declarations for the predicates and functions they write. The compiler checks these declarations, and rejects the program if it cannot prove that every predicate or function satisfies its declarations. This improves reliability, since many kinds of errors simply cannot happen in successfully compiled Mercury programs. It also improves productivity, since the compiler pinpoints many errors that would otherwise require manual debugging to locate. The fact that declarations are checked by the compiler makes them much more useful than comments to anyone who has to maintain the program. The compiler also exploits the guaranteed correctness of the declarations for significantly improving the efficiency of the code it generates.
To facilitate programming-in-the-large, to allow separate compilation, and to support encapsulation, Mercury has a simple module system. Mercury's standard library has a variety of pre-defined modules for common programming tasks — see the Mercury Library Reference Manual.
Mercury is developed to solve to main problems that appears in another logic programming languages (e.g. Prolog):
Mercury should work on following platforms:
The Mercury implementation compiles to a wide variety of target languages on a wide variety of platforms. Target language back-ends include:
Mature:
Alpha- or beta-release quality:
To sprawozdanie zostało napisane w maju 2009 r.
Informacje dotyczące instalacji kompilatora, kompilowania i uruchamiania programów napisanych w Mercurym pod Windows XP
Aby zacząć pracę z Mercurym i Haskellem należy pobrać następujące pliki:
Należy uruchomić instalator Cygwina (setup.exe). Postępować zgodnie ze wskazówkami i zainstalować pakiety opisane w poprzedniej sekcji. W dalszej części zakładał będę, że Cygwin został zainstalowany w katalogu „C:/cygwin”, natomiast katalog domowy użytkownika jest „C:\cygwin\home\USER_NAME”.
Uruchomić instalator Haskell Platform, postępować zgodnie z instrukcjami. Zakładam że Haskell został zainstalowany do folderu „C:\Program Files\Haskell Platform”
Szczegółowe informacje o instalacji z kodu źródłowego można znaleźć w archiwum kompilatora, w pliku README. Poniżej przedstawione zostały kroki potrzebne do typowej instalacji kompilatora:
cd tymczasowy
cd mercury-compiler-0.13.1
sh configure && make && make install
ja użylem
sh configure --disable-most-grades && make && make install
w celu przyśpieszenia instalacji. (Krok ten może potrwać na prawdę długo!),
Żeby móc używać kompilatora mercury:
PATH=/usr/local/mercury-0.13.1/bin:$PATH
Aby skompilować program w pliku nazwa_pliku_źródłowego.m należy:
mercury --make nazwa_pliku_źródłowego
mmc --make nazwa_pliku_źródłowego
Zostanie utworzony plik wykonywalny nazwa_pliku_źródłowego.exe. Do jego uruchomienia potrzebna jest biblioteka cygwin1.dll, którą należy skopiować z katalogu bin Cygwina („C:/cygwin/bin/cygwin1.dll”), do katalogu w którym znajduje się plik wykonywalny.
W tej części przedstawię oraz porównam podstawowe elementy języków Mercury i Haskell. W poprzednich częściach przedstawiłem narzędzia potrzebne do pracy z językami, teraz zaczniemy od stworzenia możliwie najprostszego programu, który może zostać uruchomiony pod Windows'em
Poniżej jest pokazany program w Mercurym, który umożliwia interakcyjną pracę ze światem zewnętrznym. Tak się składa, że ten prosty program wykorzystuje pewne bardziej zaawansowane koncepcje języka mercury, których później zostaną omówione.
% helloWorld.m
%-----------------------%
% KOMPILACJA:
% > mercury helloWorld
%
:- module helloWorld.
/* wieloliniowy komentaz
blokowy
*/
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module char, list, string.
main(!IO) :-
io.write_string("Hello, World!\n", !IO),
io.read_char(_, !IO).
:- end_module helloWorld.
Aby skompilować ten program należy w powłoce cygwina wykonać:
$ mmc --make helloWorld
lub w powłoce Windows
mercury helloWorld
Program drukujący powitanie, w Haskell, wygląda następująco:
-- file: hello.hs module Main where main :: IO () main = do putStrLn "Hello World!" getLine; return ()
Aby skompilować i stworzyć plik wykonawczy należy użyć polecenia:
ghc -o helloNazwaPlikuWykonywalnego hello.hs
Aby stworzyć plik wykonawczy plik z kodem musi zawierać moduł „Main” oraz funkcję main.
W Mercurym wszystkie zmienne muszą zaczynać się z dużej litery. Nazwy modułów, typów, predykatów, funkcji itp. zaczynają się z małej litery.
Funkcje, predykaty, tople, typy są wyrażeniami tak jak typy podstawowe. Mogą one być przekazywane do innych funkcji, predykatów. Typy, funkcje i predykaty mogą być polimorficzne. W poniższej tabeli przedstawiłem podstawowe typy dostępne w obu językach:
| Mercury | Haskell | |
|---|---|---|
| Typy podstawowe | ||
| Liczba całkowita | integer | Int |
| Znak | char | Char |
| Łańcuch znaków | string | String lub [Char] |
| Liczba zmiennoprzecinkowa | float | Double |
| Predykaty | pred, pred(T), … | N/A |
| Funkcje | func = int, func(T) = T, … | nazwaFunkcji :: Int → Int |
| Listy | list(int), list(T) | [Int], [a] |
| Krotki | {}, {T}, {T1, T2}, … | (), (T), (Int, a),… |
W Mercury nowy typ deklaruje się za pomocą słów kluczowych „:- type”. Możliwe jest definiowanie typów wyliczeniowych jak i rekordów. Definicja typu następuje po słowie kluczowym „—>”.
% typyUzytkownika.m
:- module typyUzytkownika.
:- interface.
:- import_module io, string, int.
:- pred main(io::di, io::uo) is det.
:- type tree
---> empty
; node(int, tree, tree).
:- type poliTree(T)
---> empty
; leaf(T)
; branch(poliTree(T), poliTree(T)).
:- type employee
---> employee(
name :: string,
age :: int,
department :: string
).
:- type newInt == int.
:- implementation.
main(!IO) :-
io.write_string("Test tree type\n", !IO),
Tree = node(1, node(2, node(4, empty, empty), node(8, empty, empty)), node(16, empty, empty)),
PoliTree = branch(branch(leaf("listek"), leaf("zielony listek")), leaf("czerwony listek")),
Pracownik1 = employee("Michal", 25, "software testing"),
Pracownik2 = Pracownik1 ^ addYears := 2,
printTree(Tree, !IO),
printPoliTree(PoliTree, !IO),
printEmployee(Pracownik1, !IO),
printEmployee(Pracownik2, !IO),
io.read_char(_, !IO).
:- pred printTree(tree::in, io.state::di, io.state::uo) is det.
printTree(empty, !IO).
printTree(node(Val, L, R), !IO) :-
io.write_int(Val, !IO),
printTree(L, !IO),
io.write_string(" ", !IO),
printTree(R, !IO),
io.nl(!IO).
:- pred printPoliTree(poliTree(T)::in, io.state::di, io.state::uo) is det.
printPoliTree(empty, !IO).
printPoliTree(leaf(T), !IO) :-
io.write(T, !IO),
io.write_string(" ", !IO).
printPoliTree(branch(L, R), !IO) :-
printPoliTree(L, !IO),
printPoliTree(R, !IO),
io.nl(!IO).
:- pred printEmployee(employee::in, io.state::di, io.state::uo) is det.
printEmployee(employee(N, A, D), !IO) :-
io.write_string(N, !IO),
io.write_string(", ", !IO),
io.write_int(A, !IO),
io.write_string(", ", !IO),
io.write_string(D, !IO),
io.nl(!IO).
%
% user supplied field access functions
%
:- func employee ^ getYears = int.
%:- mode in ^ in = out is det.
employee(_, Years, _) ^ getYears = Years.
:- func (employee ^ addYears := int) = employee.
%:- mode (in ^ in := in) = out is det.
(employee(Name, Age, Dep) ^ addYears := Years) = employee(Name, Age + Years, Dep).
:- end_module typyUzytkownika.
W Hasekllu typy użytkownika deklaruje się za pomocą słowa kluczowego „data” i listy konstruktorów oddzielonych „|”. Podobnie jak w Mercurym.
module Main where data Tree = Empty | Node Int Tree Tree deriving (Show) data PoliTree a = EmptyPoli | Leaf a | Branch (PoliTree a) (PoliTree a) deriving (Show) data Employee = Employee { name :: String , age :: Int , department :: String } deriving (Show) -- funkcja main main = do let mytree = Node 1 (Node 2 (Node 4 Empty Empty) (Node 8 Empty Empty)) (Node 16 Empty Empty) poliTree = Branch (Branch (Leaf "listek") (Leaf "zielony listek")) (Leaf "czerwony listek") pracownik1 = Employee "Michal" 25 "software testing" pracownik2 = pracownik1 { age = 26 } putStrLn (show poliTree ++ "\n") putStrLn (show mytree ++ "\n") putStrLn (show pracownik1 ++ "\n") putStrLn (show pracownik2 ++ "\n") getLine
W Mercurym istnieją dodatki syntaktyczne umożliwiające manipulacje polami rekordów (Haskell również wspiera tą funkcjonalność, jednak nie można tworzyć własnych funkcji 
):
Mercury podobnie jak Haskell wspiera definiowanie typów równoważnych. Typy równoważne są definiowane po słowie kluczowym „==”:
:- type newInt == int.
Składnia Haskella:
type NewInt = Int
W Mercurym konstruktorem listy jest „|”, nie jak w Haskellu „:”. Dodatkowo listy nie należą do podstawowej biblioteki Mercurego (trzeba je importować „:- import_module list”)
Bardzo przydatną funkcją w Haskell'u są ang. list comprehansions. Ich użyteczność można zobaczyć na poniższym przykładzie:
Przykładowa implementacja algorytmu quicksort z użyciem list comprehansions w Haskell
niestety brakuje ich w Mercurym (kod ze strony http://en.literateprograms.org/Quicksort_(Mercury)):
Mercury jest ściśle typowanym językiem, dlatego, warto zwrócić uwagę na deklarację typów (po słowach kluczowych „func” albo „pred”) oraz trybów and. mode (po słowie kluczowym „mode”). Deklaracje te nie zawsze są potrzebne, gdyż język posiada wbudowany system wykrywania typów i trybów funkcji i predykatów (ang. type inference). W Mercurym funkcje i predykaty to również wyrażenia. Predykaty i funkcje jako argumenty mogą przyjmować inne predykaty i funkcje.
Predykaty i funkcje w Mercury'm wyglądają następująco:
member2(ElementToMatch, [ElementToMatch | _]).
member2(ElementToMatch, [_ | Xs]) :-
member2(ElementToMatch, Xs).
my_length([]) = 0.
my_length([_ | Xs]) = 1 + my_length(Xs).
:- func testLength = string.
testLength = String :-
List = [1, 2, 3, 4, 5],
String = string.format("List [%s] my_length is %i\n",[s(intListToString(List)), i(my_length(List))]).
sum(List, Sum) :-
Sum = sum2(List, 0).
:- func sum2(list(int), int) = int.
sum2([], SumStart) = SumStart.
sum2([H | Tl], PartialSum) = sum2(Tl, PartialSum + H).
:- func testSumWith2 = string.
testSumWith2 = String :-
List = [1, 2, 3, 4, 5],
sum(List, Sum),
String = string.format("Sum of list [%s] is %i\n",[s(intListToString(List)), i(Sum)]).
Haskell jest również ściśle typowanym językiem, jednak bardzo często deklaracje typu nie są wymagane, ponieważ kompilator w wielu przypadkach jest w stanie na podstawie kontekstu wygenerować odpowiednią deklarację funkcji.
Funkcje w Haskell'u wyglądają następująco:
isListMember :: Eq a => a -> [a] -> Bool isListMember element [] = False isListMember element (listH:listT) | element == listH = True | otherwise = isListMember element listT listLenght :: [a] -> Int listLenght [] = 0 listLenght (_:t) = 1 + listLenght t listSum :: Num a => [a] -> a listSum [] = 0 listSum (h:t) = h + listSum t
System instancji jest specyficzny dla języka Mercury, w Haskell'u nie ma swojego odpowiednika. Pozwala zdefiniować stan instancji danego typu.
Każdy typ jest opisany za pomocą drzewa. Drzewo to składa się z konstruktorów typu (or node) i argumentów tych konstruktorów (and node). System instancji pozwala na opis argumentów konstruktorów (and node) danego typu.
 |
| Typ i instancja |
Podstawowymi blokami budującymi system instancji w Merkurym są stany:
:- pred append(list(T), list(T), list(T)). /* deklatacja predykatu */ :- mode append(in, in, out) is det. /* definicja trybu predykatu */ :- mode append(in, out, in) is semidet. /* definicja trybu predykatu */ :- mode append(out, in, in) is semidet. /* definicja trybu predykatu */ :- mode append(out, out, in) is multi. /* deklatacja predykatu */
Poniżej jest przykład wykorzystujący tryby i stany instancji zdefiniowane przez użytkownika:
%systemTrybow.m
:- module systemTrybow.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- interface.
%%%GROUP Interfejs
:- import_module io.
:- pred main(io::di, io::uo) is det.
%%%END_GROUP
:- implementation.
:- import_module list, int, string, map, solutions.
%%%GROUP Typy
:- type myMaybe(T) ---> null; just(T).
:- type dbOperation ---> lookup(int, myMaybe(customer)) ; set(int, myMaybe(customer)).
:- type customer --->
customer(
name :: string,
age :: int,
description :: string
).
%%%END_GROUP
%%%GROUP Tryby
:- inst maybeDataUnboundInst ---> null; just(free).
:- inst dbOperationInst ---> lookup(ground, maybeDataUnboundInst) ; set(ground, ground).
:- inst my_listskel ---> []; [free | my_listskel].
:- mode my_in(Inst) == Inst >> Inst. /* definicja trybu parametrycznego */
:- mode my_out(Inst) == free >> Inst. /* definicja trybu parametrycznego */
% unique output
:- mode my_uo == free >> unique.
% unique input
:- mode my_ui == unique >> unique.
% destructive input
:- mode my_di == unique >> dead.
%%%END_GROUP
%%%GROUP Przykladowe funkcje i predykaty
main(!IO) :-
io.write_string("Test system trybow\n", !IO),
Data:map(int, customer) = map.init,
io.write_string("jakas funkcja", !IO),
io.nl(!IO),
io.read_char(_, !IO).
:- func myDB(dbOperation, dbOperation, map(int, customer)) = map(int, customer).
:- mode myDB(in(dbOperationInst), out, in) = out is det.
myDB(lookup(Id, _), Result, Map) = NewMap :-
(if
Customer1 = Map ^ elem(Id)
then
Result = lookup(Id, just(Customer1))
else
Result = lookup(Id, null)
),
NewMap = Map.
myDB(set(Id, MaybeCust), Result, Map) = NewMap :-
(
MaybeCust = just(Customer),
solutions((pred(T::out) is nondet :- map.insert(Map, Id, Customer, T)), Solutions),
(if
Solutions = [H|_]
then
Result = set(Id, just(Customer)),
NewMap = H
else
NewMap = Map,
Result = set(Id, null)
)
;
MaybeCust = null,
NewMap = Map,
Result = set(Id, null)
).
:- pred saveCustomerToDB(customer::in, map(int, customer)::in, string::out, map(int, customer)::out) is det.
saveCustomerToDB(Customer, Map, String, MapOut) :-
DBReq = set(1, just(Customer)),
MapOut = myDB(DBReq, DBRes, Map),
(
if DBRes = set(_, just(_))
then String = "Success! Customer saved"
else String = "Fail! Can't save customer"
).
:- pred getCustomerWithId(int::in, map(int, customer)::in, string::out, map(int, customer)::out) is det.
getCustomerWithId(Id, Map, String, MapOut) :-
DBReq = lookup(1, null),
MapOut = myDB(DBReq, DBRes, Map),
(
if DBRes = lookup(Id, just(_))
then String = string.format("Customer with id: %i saved!", [i(Id)])
else String = string.format("Can't save with id: %i!", [i(Id)])
).
:- pred myappend(list(T), list(T), list(T)). /* deklatacja predykatu */
:- mode myappend(in, in, out) is det. /* definicja trybu predykatu */
:- mode myappend(in, out, in) is semidet. /* definicja trybu predykatu */
:- mode myappend(out, in, in) is nondet. /* definicja trybu predykatu */
:- mode myappend(out, out, in) is multi. /* deklatacja predykatu */
% definicja predykatu
myappend(Xs, Ys, Zs) :-
(
Xs = [],
Zs = Ys
;
Xs = [Hd | Tl],
myappend(Tl, Ys, Zs0),
Zs = [Hd | Zs0]
).
%:- func usingAppend string.
%%%END_GROUP
=== Unikalne tryby i stany instancji === Deklaracje trybów mogą również opisywać tak zwane „tryby unikatowe”. Tryby unikatowe w Mercury'm są podobne do „typów liniowych” występujących w niektórych funkcjonalnych językach programowania jak na przykład Clean. Można za ich pomocą oznaczyć zmienną jako taką do której istnieje tylko jedno odniesienie. Tryby unikatowe są używane do optymalizacji kompilowanego kodu (np. destrukcyjne przypisanie jednego elementu tablicy, zamiast kopiowanie całej tablicy żeby zmienić element) oraz jako mechanizm, który jest używany przez Mercury'ego w celu stworzenia deklaratywnych operacji I/O. Wbudowane stany unikatowych instancji:
* unique - takie same jak ground z tym, że istnieje dodatkowe ograniczenie mówiące że istnieje tylko jedno odwołanie do odpowiadającej wartości wyrażenia * unique(...) - pozwala na budowanie drzewa * dead - nie ma żadnego odniesienia do odpowiadającej wartości wyrażenia
% unique output
:- mode uo == free >> unique.
% unique input
:- mode ui == unique >> unique.
% destructive input
:- mode di == unique >> dead.
==== Determinizm ==== Dla każdego trybu (mode) funkcji i predykatu w Mercury'm, definiujemy ile udanych rozwiązań może posiadać ten tryb, oraz czy znalezienie pierwszego rozwiązania może nie powieść się, czy też nie. W zależności od możliwości niepowodzenia znalezienia rozwiązania oraz ilości możliwych rozwiązań, w tabeli poniżej zostały przedstawione wszystkie możliwe kategorie determinizmu. | ^ 0 rozwiązań ^ 1 rozwiązanie ^ więcej niż 1 rozwiązanie ^ ^ nie może zawieźć | erroneous | det | multi | ^ może zawieźć | failure | semidet | nondet | Ze względu na wiedzę kompilatora na temat ilości rozwiązań danej procedury poniżej przedstawione zostało drzewo zależności pomiędzy poszczególnymi kategoriami determinizmu:
erroneous
/ \
failure det
\ / \
semidet multi
\ /
nondet
Składnia determinizmu w Mercurym jest przedstawiona na przykładzie poniżej:
:- pred append(list(T), list(T), list(T)).
:- mode append(in, in, out) is det.
:- mode append(out, out, in) is multi.
:- mode append(in, in, in) is semidet.
:- func length(list(T)) = int.
:- mode length(in) = out is det.
:- mode length(in(list_skel)) = out is det.
:- mode length(in) = in is semidet.
% lub
:- pred append2(list(T)::in, list(T)::in, list(T)::out) is det.
:- func length2(list(T)) = int
% co jest domyslnie traktowane przez komilator jak length3
:- func length3(list(T)::in) = int::out is det.
Pełny przykład z deklaracjami funkcji i predykatów mających różne kategorie determinizmu jest poniżej:
% determinizm.m
:- module determinizm.
:- interface.
:- import_module io, list, int.
:- pred main(io, io).
:- mode main(di, uo) is cc_multi.
:- pred my_append(list(T), list(T), list(T)).
:- mode my_append(in, in, out) is det.
:- mode my_append(out, out, in) is multi.
:- mode my_append(in, in, in) is semidet.
:- func my_length(list(T)) = int.
:- mode my_length(in) = out is det.
:- mode my_length(in) = in is semidet.
:- implementation.
:- import_module solutions /* for solutions */, require /* for error */.
main -->
io__nl.
:- pred my_multi_or_nondet_pred(list(T), T).
:- mode my_multi_or_nondet_pred(in, out) is semidet.
my_multi_or_nondet_pred(X, Y) :-
Y = list.head(X).
my_append(Xs, Ys, Zs) :-
(
Xs = [],
Zs = Ys
;
Xs = [Hd | Tl],
append(Tl, Ys, Zs0),
Zs = [Hd | Zs0]
).
%
% my_length - funkcja do obliczania dlugosci listy
%
my_length(Xs) = N :-
my_length(Xs, N).
%
% my_length - predykat do obliczania dlugosci listy
%
:- pred my_length(list(_T), int).
:- mode my_length(in, out) is det.
:- mode my_length(in, in) is semidet.
% XXX The current mode checker can't handle this mode
%:- mode list.length(input_list_skel, out) is det.
my_length(L, N) :-
my_length_2(L, 0, N).
:- pred my_length_2(list(T), int, int).
:- mode my_length_2(in, in, out) is det.
:- mode my_length_2(in, in, in) is semidet.
%
% my_length_2 predykat pomocniczy do bliczania dlugosci listy
%
% arg 1 - lista elementow
% arg 2 - startowa slugosc listy
% arg 3 - calkowita dlugosc listy
my_length_2([], N, N).
my_length_2([_ | L1], N0, N) :-
N1 = N0 + 1,
my_length_2(L1, N1, N).
:- pred loop(int::in) is erroneous.
loop(X) :- loop(X).
:- pred deterministicPred1 is det.
deterministicPred1.
:- pred failingPred is failure.
failingPred :- fail.
:- pred deterministicPred2(T, T).
:- mode deterministicPred2(in, out) is det.
deterministicPred2(A, B) :-
( goal_that_should_never_fail(A, B0) ->
B = B0
;
error("goal_that_should_never_fail failed!")
).
:- pred goal_that_should_never_fail(T::in, T::out) is det.
goal_that_should_never_fail(X, Y) :-
Y = X.
:- end_module determinizm.
=== Niedeterministyczne obliczenia w Haskell'u === Składnia Haskell'a nie wspiera różnych kategorii determinizmu, jednak dzięki leniwości języka jest możliwe zaimplementowanie niedeterministycznych funkcji. Przykład poniżej ilustruje funkcje obliczenia, którym w Mercury odpowiadałby determinizm multi:
--BacktrackingInHaskell.hs -- na podstawie artykulu "Monads in 15 minutes: Backtracking and Maybe" -- z "Random Hacks Technology and Other Fun Stuff" -- url: http://www.randomhacks.net/articles/2007/03/12/monads-in-15-minutes module Main where -- Ukrywamy standardowe wersje operatorow -- aby zaimplementowac je samemu import Prelude hiding ((>>=), return) type Choice a = [a] -- Pobieramy jeden element z listy, zapisujac -- punkt nawrotu do pozniejszego uzycia. choose :: [a] -> Choice a choose xs = xs -- Kozystajac z tego ze Haskell jest leniwym jezykiem, mozemy pracowac z -- nieskonczonymi strukturami danych oraz jedynie obliczac te z nich ktore sa -- nam aktualnie potrzebne, wpisujac w ghci: -- -- > take 3 (choose [1..]) -- -- otrzymamy rezultat: -- [1,2,3] -- generator przykladowej listy par pair456 :: Int -> Choice (Int,Int) pair456 x = choose [(x,4), (x,5), (x,6)] -- uzywajac naszego generatora par w polaczeniu z lista daje nam kilka mozliwosci: -- > map pair456 (choose [1,2,3]) -- [[(1,4),(1,5),(1,6)], -- [(2,4),(2,5),(2,6)], -- [(3,4),(3,5),(3,6)]] join :: Choice (Choice a) -> Choice a join choices = concat choices -- poprawiamy wynik generacji par w polaczeniu z lista: -- > join (map pair456 (choose [1,2,3])) -- [(1,4),(1,5),(1,6), -- (2,4),(2,5),(2,6), -- (3,4),(3,5),(3,6)] -- funkja tworzaca kombinacje mozliwych rozwiazan (>>=) :: Choice a -> (a -> Choice b) -> Choice b choices >>= f = join (map f choices) -- funkcja przenoszaca element do kombinacji rozwiazan return :: a -> Choice a return x = choose [x] -- przykladowy generator wszystkich kombinacji rozwiazan makePairs :: Choice (Int,Int) makePairs = choose [1,2,3] >>= (\x -> choose [4,5,6] >>= (\y -> return (x,y))) -- > makePairs -- [(1,4),(1,5),(1,6), -- (2,4),(2,5),(2,6), -- (3,4),(3,5),(3,6)] -- generator wszystkich rozwiazan, ulepszona wersja makePairs' :: Choice (Int,Int) makePairs' = do x <- choose [1,2,3] y <- choose [4,5,6] return (x,y) -- > makePairs' -- [(1,4),(1,5),(1,6), -- (2,4),(2,5),(2,6), -- (3,4),(3,5),(3,6)] -- W naszej monadzie nie znalezienie rozwiazania moze byc przedstawione -- jako wybor pomiedzy 0 iloscia opcji -- dlatego definiujemy "zero" dla naszej monady. -- Reprezentuje to nie znalezienie rozwiazania. mzero :: Choice a mzero = choose [] -- "predykat" narzucajacy ograniczenia na rozwiazenie -- moze zawiezc, albo zwrocic cos przydatnego guard :: Bool -> Choice () guard True = return () guard False = mzero -- PODSUMOWUJAC! -- funkcja znajdujaca wiele rozwiazan w zaleznosci od zbioru mozliwosci -- i ograniczen jest ponizej: solveConstraint = do x <- choose [1,2,3] -- kombinacja rozwiazan y <- choose [4,5,6] -- kombinacja rozwiazan guard (x*y == 8) -- ograniczenia narzucone na rozwiazanie return (x,y) -- wynik: -- > take 1 solveConstraint -- [(2,4)] main = putStrLn (show solveConstraint)
==== Funkcje i predykaty wyższych rzędów ==== Mercury pozwala na programowanie funkcji i predykatów wyższych rzędów, w szczególności dostępne są: * zwijanie (ang. currying) * klauzule (ang. closures) * funkcje anonimowe (ang. lambda abstractions) np. Haskell f x = (\y -> x + y) Weźmy następujący predykat w Mercurym:
:- pred sum(list(int), int).
:- mode sum(in, out) is det.
Możemy go użyć w następujący sposób:
:- func scalar_product(int, list(int)) = list(int).
:- mode scalar_product(in, in) = out is det.
X = (func(Num::in, List::in) = (NewList::out) is det
:- NewList = scalar_product(Num, List)),
sum(X, 2).
=== Zwijanie (currying) === f(x,y) = x/y, f(2/3) = g(3) (g(y) = 2/y) = 2/3 Fragment programu w Mercury wykorzystujący zwijanie:
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zwijanie (currying)
%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- func testSum123 = string.
testSum123 = String :-
% binds `Sum123' to a higher-order predicate term of type `pred(int)'.
Sum123Lambda = sum([1,2,3]),
String1 = string.format("Type of sum123Lambda is: %s\n",[s(getTypeName(Sum123Lambda))]),
call(Sum123Lambda, Result),
String2 = string.format("Value of sum123Lambda is: %i\n",[i(Result)]),
String = String1 ++ String2.
%blabla
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- func testZwijanie = string is det.
testZwijanie = String :-
% *Ograniczenia* nie można używać nazw operacji wbudowanych w język, np. zamiast
% list.filter(\=(2), [1, 2, 3], List)
%należy użyć:
FilteredListLambda1 = list.filter((pred(X::in) is semidet :- X \= 2), [1, 2, 3]),
String11 = string.format("FilteredListLambda1 typ: %s\n",[s(getTypeName(FilteredListLambda1))]),
call(FilteredListLambda1, Lambda1Result),
String12 = string.format("FilteredListLambda1 when called returns %s\n",[s(intListToString(Lambda1Result))]),
% lub
FilteredListLambda2 = list.filter(not_equal(2), [1,2,3]),
call(FilteredListLambda2, Lambda2Result),
String2 = string.format("First list elem is %s\n",[s(intListToString(Lambda2Result))]),
String = String11 ++ String12 ++ String2.
% gdzie my_not_equal jest zdefiniowane nastepujaco
:- pred not_equal(T::in, T::in) is semidet.
not_equal(X, Y) :- X \= Y.
W Haskell jest łatwiej:
--currying scalarProduct :: Num a => a -> [a] -> [a] scalarProduct mult vect = map (mult *) vect partialScalarProduct = scalarProduct 3 test_callingPartialScalarProduct = intListToString $ partialScalarProduct [1, 2, 3] test_filteredList :: (Num a, Show a) => [a] -> String test_filteredList = show . filter (/= 2) test_filteredList2 :: (Integral a, Show a) => [a] -> String test_filteredList2 xs = concat [show x ++ " " | x <- xs, (x `mod` 2 == 0)]
=== Klauzule (closures) === Czyli funkcje, która używają wolnych zmiennych(zmienna, która nie jest związana: Haskell /x -> x y y jest tutaj wolną zmienną), „otaczające” jakąś przestrzeń leksykalną, np. Haskell f x = (\y -> x + y) w tym przypadku f zwraca klauzulę, ponieważ zmienna x, która jest przypisana na zewnątrz lambda abstrakcji, jest używana wewnątrz niej. Fragment programu w Mercury, używający klauzul:
:- func sumWithClosure(int) = (func(int) = int). :- mode sumWithClosure(in) = out(func(in) = out is det) is det. sumWithClosure(X) = Func :- Func = (func(Y) = Bla :- Bla = add2Ints(X, Y)). :- func add2Ints(int, int) = int. add2Ints(X, Y) = X + Y.
W tym przypadku w Haskell'u też jest łatwiej:
--closures addClosure x = (\y -> x + y) test_addClosure = show (addClosure 2 3)
=== Program === Mercury:
%predykaty_i_funkcje.m
:- module predykaty_i_funkcje.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- interface.
:- import_module io, list, int.
:- pred main(io::di, io::uo) is det.
:- pred member2(T::in, list(T)::in) is semidet.
:- func my_length(list(T)) = int.
:- pred sum(list(int), int).
:- mode sum(in, out) is det.
:- func scalar_product(int, list(int)) = list(int).
:- mode scalar_product(in, in) = out is det.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
:- implementation.
:- import_module string, type_desc.
%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%% main %%%%%%
main(!IO) :-
io.write_string("Test predykaty i funkcje\n", !IO),
io.write_string(testMemberPred(4, [1, 2, 3, 4, 5]), !IO),
io.write_string(testScalar_product, !IO),
io.write_string(testSumWith2, !IO),
io.write_string(testLength, !IO),
io.write_string(testSum123, !IO),
io.write_string(testZwijanie, !IO),
io.write_string(testKlauzule, !IO),
io.read_char(_, !IO).
%%%%%%%%%%%%%%%%%%%%%%%%%
member2(ElementToMatch, [ElementToMatch | _]).
member2(ElementToMatch, [_ | Xs]) :-
member2(ElementToMatch, Xs).
:- func intListToString(list(int)) = string.
intListToString(ListOfInts) = String :-
FoldlFunction = (func(Elem, Acc) = NewAcc :- NewAcc = Acc ++ " " ++ string.int_to_string(Elem)),
String = list.foldl(FoldlFunction, ListOfInts, "").
:- func testMemberPred(int, list(int)) = string.
testMemberPred(Element, List) = OutString :-
(if member2(Element, List)
then
OutString = string.format("Element %i is member of list %s\n", [i(Element), s(intListToString(List))])
else
OutString = string.format("Element %i is not member of list %s\n", [i(Element), s(intListToString(List))])
).
%%%%%%%%%%%%%%%%%%%%
scalar_product(Multiplier, Vector) = Fun :-
Fun = list.map((func(X) = Y :- Y = Multiplier * X), Vector).
:- func testScalar_product = string.
testScalar_product = String :-
Vector = [1, 2, 3],
Multi = 3,
VectStr = intListToString(Vector),
MultiVectStr = intListToString(scalar_product(Multi, Vector)),
String = string.format("Vector [%s] multiplied by <%i> is [%s]\n",[s(VectStr), i(Multi), s(MultiVectStr)]).
%%%%%%%%%%%%%%%%%%%%%
:- func testLambda = string.
testLambda = String :-
ScalarProdLambda = (func(Num::in, List::in) = (NewList::out) is det
:- NewList = scalar_product(Num, List)),
Vector = [1, 2, 3],
Multi = 3,
VectStr = intListToString(Vector),
MultiVectStr = intListToString(apply(ScalarProdLambda, Multi, Vector)),
String = string.format("Lambda: Vector [%s] multiplied by <%i> is [%s]\n",[s(VectStr), i(Multi), s(MultiVectStr)]).
%%%%%%%%%%%%%%%%%%%%%%
my_length([]) = 0.
my_length([_ | Xs]) = 1 + my_length(Xs).
:- func testLength = string.
testLength = String :-
List = [1, 2, 3, 4, 5],
String = string.format("List [%s] my_length is %i\n",[s(intListToString(List)), i(my_length(List))]).
%%%%%%%%%%%%%%%%%%%%%%%
sum(List, Sum) :-
Sum = sum2(List, 0).
:- func sum2(list(int), int) = int.
sum2([], SumStart) = SumStart.
sum2([H | Tl], PartialSum) = sum2(Tl, PartialSum + H).
:- func testSumWith2 = string.
testSumWith2 = String :-
List = [1, 2, 3, 4, 5],
sum(List, Sum),
String = string.format("Sum of list [%s] is %i\n",[s(intListToString(List)), i(Sum)]).
%%%%%%%%%%%%%%%%%%%%%%%
:- func getTypeName(T) = string.
getTypeName(TypeClause) = NameString :-
NameString = type_name(type_of(TypeClause)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zwijanie (currying)
%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- func testSum123 = string.
testSum123 = String :-
% binds `Sum123' to a higher-order predicate term of type `pred(int)'.
Sum123Lambda = sum([1,2,3]),
String1 = string.format("Type of sum123Lambda is: %s\n",[s(getTypeName(Sum123Lambda))]),
call(Sum123Lambda, Result),
String2 = string.format("Value of sum123Lambda is: %i\n",[i(Result)]),
String = String1 ++ String2.
%blabla
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- func testZwijanie = string is det.
testZwijanie = String :-
% *Ograniczenia* nie można używać nazw operacji wbudowanych w język, np. zamiast
% list.filter(\=(2), [1, 2, 3], List)
%należy użyć:
FilteredListLambda1 = list.filter((pred(X::in) is semidet :- X \= 2), [1, 2, 3]),
String11 = string.format("FilteredListLambda1 typ: %s\n",[s(getTypeName(FilteredListLambda1))]),
call(FilteredListLambda1, Lambda1Result),
String12 = string.format("FilteredListLambda1 when called returns %s\n",[s(intListToString(Lambda1Result))]),
% lub
FilteredListLambda2 = list.filter(not_equal(2), [1,2,3]),
call(FilteredListLambda2, Lambda2Result),
String2 = string.format("First list elem is %s\n",[s(intListToString(Lambda2Result))]),
String = String11 ++ String12 ++ String2.
% gdzie my_not_equal jest zdefiniowane nastepujaco
:- pred not_equal(T::in, T::in) is semidet.
not_equal(X, Y) :- X \= Y.
%%%%%%%%%%%%%%%%%%%%%%%%
% Klauzule (closures)
%%%%%%%%%%%%%%%%%%%%%%%%
:- func testKlauzule = string.
testKlauzule = String :-
AddNumFunction = (func(X::in, Y::in) = (Sum::out) is det :- Sum = X + Y),
Sum1 = apply(AddNumFunction, 1, 2),
PartSum = sumWithClosure(3),
String1 = string.int_to_string(Sum1),
String2 = getTypeName(PartSum),
String3 = string.int_to_string(apply(PartSum,2)),
String = String1 ++ ", " ++ String2 ++ ", " ++ String3 ++ "\n".
:- func sumWithClosure(int) = (func(int) = int).
:- mode sumWithClosure(in) = out(func(in) = out is det) is det.
sumWithClosure(X) = Func :-
Func = (func(Y) = Bla :- Bla = add2Ints(X, Y)).
:- func add2Ints(int, int) = int.
add2Ints(X, Y) = X + Y.
:- end_module predykaty_i_funkcje.
Haskell:
--PredykatyFunkcje.hs -- w "Fun with functional dependencies", Thomas Hallgren (2001) -- http://www.cs.chalmers.se/~hallgren/Papers/wm01.html -- jest opisane jak zbudowac predykat w Haskell'u module Main where isListMember :: Eq a => a -> [a] -> Bool isListMember element [] = False isListMember element (listH:listT) | element == listH = True | otherwise = isListMember element listT listLenght :: [a] -> Int listLenght [] = 0 listLenght (_:t) = 1 + listLenght t listSum :: Num a => [a] -> a listSum [] = 0 listSum (h:t) = h + listSum t scalarProduct :: Num a => a -> [a] -> [a] scalarProduct mult vect = map (mult *) vect intListToString :: [Int] -> String intListToString ints = foldl (\acc elem -> acc ++ (show elem) ++ " ") " " ints --currying partialScalarProduct = scalarProduct 3 test_callingPartialScalarProduct = intListToString $ partialScalarProduct [1, 2, 3] test_filteredList :: (Num a, Show a) => [a] -> String test_filteredList = show . filter (/= 2) test_filteredList2 :: (Integral a, Show a) => [a] -> String test_filteredList2 xs = concat [show x ++ " " | x <- xs, (x `mod` 2 == 0)] --closures addClosure x = (\y -> x + y) test_addClosure = show (addClosure 2 3) main = do putStrLn "Test PredykatyFunkcje" putStrLn "Czy element 2 nalezy do listy [1, 2, 3, 4]?" putStrLn ("\t" ++ show (isListMember 2 [1, 2, 3, 4])) putStrLn ("Dludosc listy [1, 2, 3, 4] wynosi" ++ show (listLenght [1, 2, 3, 4])) putStrLn ("Wektor [1, 2, 3, 4] pomnozony przez 3 wynosi " ++ intListToString (scalarProduct 3 [1, 2, 3, 4])) putStrLn test_callingPartialScalarProduct putStrLn $ test_filteredList [1, 2, 3, 4, 5] putStrLn (test_filteredList2 [1, 2, 3, 4, 5]) putStrLn test_addClosure
==== Moduły i ukrywanie implementacji ==== Merkury wspiera modularny sposób budowania programów, pozwala również na ukrywanie szczegółów implementacyjnych. Poniżej przedstawiono przykładowy moduł:
:- module ModuleName.
:- interface.
% moduly importowane
:- include_module ModuleToInclude.
%
% przedmioty eksportowane prze modul
%
:- implementation.
% prywatne moduly potrzebne do implementacji
:- include_module PrivateModuleToInclude.
%
% szczegoly implementacji
%
:- end_module ModuleName.
Każdy moduł zaczyna się od deklaracji
:- module ModuleName.
gdzie „ModuleName” to nazwa modułu. Deklaracja interfejsu modułu zaczyna się od:
:- interface.
Sekcja ta specyfikuje, które przedmioty są eksportowane przez ten moduł. Deklaracja części implementacyjnej modułu jest następująca:
:- implementation.
Sekcja ta zawiera implementację wszystkich przedmiotów. Sekcja ta jest prywatna dla modułu. Koniec modułu jest oznaczany deklaracją:
:- end_module ModuleName.
gdzie „ModuleName” to nazwa modułu. Aby importować moduły umieszczone w oddzielnych plikach należy posłużyć się deklaracją:
:- include_module Module.Module1, Module2, ModuleN
Nazwy tych plików muszą być związane z nazwą modułu, dla przykładu jeżeli importujemy moduł o nazwie „Module.Module1” to plik zawierający ten moduł musi mieć nazwę „Module.Module1.m”. Nazwy modułów muszą być pełne (ang. fully qualified). Każda deklaracja w module rodzicu jest widoczna w module dziecku, ale nie na odwrót. ==== Type classes ==== Merkury wspiera ograniczony polimorfizm za pomocą klas typów (ang. type classes). Klasy typów pozwalają pisać predykaty i funkcje, które operują na zmiennych dowolnego typu, dla których pewien zbiór operacji jest zdefiniowany. Klasy typów są podobne do interfejsów w Javie, a w Haskell'u do Type Classes. Przykład klasy typu w Mercury'm:
:- typeclass point(T) where [
% coords(Point, X, Y):
% X and Y are the cartesian coordinates of Point
pred coords(T, float, float),
mode coords(in, out, out) is det,
% translate(Point, X_Offset, Y_Offset) = NewPoint:
% NewPoint is Point translated X_Offset units in the X direction
% and Y_Offset units in the Y direction
func translate(T, float, float) = T
].
Liczba parametrów klasy typów jest nie ograniczona:
:- typeclass a(T1, T2) where [...].
:- type coordinate
---> coordinate(
float, % X coordinate
float % Y coordinate
).
:- instance point(coordinate) where [
pred(coords/3) is coordinate_coords,
func(translate/3) is coordinate_translate
].
:- pred coordinate_coords(coordinate, float, float).
:- mode coordinate_coords(in, out, out) is det.
coordinate_coords(coordinate(X, Y), X, Y).
:- func coordinate_translate(coordinate, float, float) = coordinate.
coordinate_translate(coordinate(X, Y), Dx, Dy) = coordinate(X + Dx, Y + Dy).
:- type rgb
---> rgb(
int,
int,
int
).
:- type coloured_coordinate
---> coloured_coordinate(
float,
float,
rgb
).
:- instance point(coloured_coordinate) where [
pred(coords/3) is coloured_coordinate_coords,
func(translate/3) is coloured_coordinate_translate
].
:- pred coloured_coordinate_coords(coloured_coordinate, float, float).
:- mode coloured_coordinate_coords(in, out, out) is det.
coloured_coordinate_coords(coloured_coordinate(X, Y, _), X, Y).
:- func coloured_coordinate_translate(coloured_coordinate, float, float)
= coloured_coordinate.
coloured_coordinate_translate(coloured_coordinate(X, Y, Colour), Dx, Dy)
= coloured_coordinate(X + Dx, Y + Dy, Colour).
=== Ograniczenia klas typów dla funkcji i predykatów ===
:- pred distance(P1, P2, float) <= (point(P1), point(P2)).
:- mode distance(in, in, out) is det.
distance(A, B, Distance) :-
coords(A, Xa, Ya),
coords(B, Xb, Yb),
XDist = Xa - Xb,
YDist = Ya - Yb,
Distance = sqrt(XDist*XDist + YDist*YDist).
=== Ograniczenia typu klasy przez typy klasy ===
:- typeclass ring(T) where [
func zero = (T::out) is det, % '+' identity
func one = (T::out) is det, % '*' identity
func plus(T::in, T::in) = (T::out) is det, % '+'/2 (forward mode)
func mult(T::in, T::in) = (T::out) is det, % '*'/2 (forward mode)
func negative(T::in) = (T::out) is det % '-'/1 (forward mode)
].
:- typeclass euclidean(T) <= ring(T) where [
func div(T::in, T::in) = (T::out) is det,
func mod(T::in, T::in) = (T::out) is det
].
:- typeclass portrayable(T) where [
pred portray(T::in, io.state::di, io.state::uo) is det
].
:- instance portrayable(list(T)) <= portrayable(T) where [
pred(portray/3) is portray_list
].
:- pred portray_list(list(T), io.state, io.state) <= portrayable(T).
:- mode portray_list(in, di, uo) is det.
portray_list([], !IO).
portray_list([X | Xs], !IO) :-
portray(X, !IO),
io.write_char(' ', !IO),
portray_list(Xs, !IO).
=== Zależności funkcyjne === Zależności funkcyjne są dostępne w Haskell'u za pomocą rozszerzeń języka. Zależności funkcyjne są używanie w celu ograniczenia parametrów klas typów. Pozwalają one na stwierdzenie, że dla wieloparametrowej klasy typu, jeden z typów parametrów może być zdeterminowany na podstawie innych. Dla przykładu determinowany parametr, może być zwracanym typem przez metodę, ale nie typem argumentów tej metody.
data Vector = Vector Int Int deriving (Eq, Show) data Matrix = Matrix Vector Vector deriving (Eq, Show) class Mult a b c | a b -> c where (*) :: a -> b -> c instance Mult Matrix Matrix Matrix where {- ... -} instance Mult Matrix Vector Vector where {- ... -}
W Mercury'm można to zapisać w następujący sposób:
:- type vector
---> vector(
int,
int
).
:- type matrix
---> matrix(
vector,
vector
).
:- typeclass mult(A, B, C) <= (A, B -> C) where [
func multiply(A, B) = C
]
:- instance mult(matrix, matrix, matrix) where [
multiply/2 is matrixMultiply
]
==== Existential types ==== Egzystencjalnie kwalifikowane zmienne typów (w skrócie egzystencjalne typy) są przydatnymi narzędziami dla abstrakcji typów. W połączeniu z klasami typów, pozwalają one pisać kod w obiektowym stylu, podobnym do tego używanego w Javie lub Cpp. Mercury pozwala na egzystencjalne kwalifikatory dla funkcji, predykatów i typów. Można używać ograniczeń klas typów dla egzystencjalnie kwalifikowalnych zmiennych typów. === Existentially typed predicates and functions ===
% Here the type variables `T1' and `T2' are existentially quantified.
:- some [T1, T2] func bar(int, list(T1), set(T2)) = pair(T1, T2).
% Here the type variable 'T1, T2' are existentially quantified,
% but the type variables 'T3' and 'T4' are universally quantified.
:- some [T2] pred foo(T1, T2, T2, T3).
/* przyklady uzycia */
:- some [T] pred e_bar(T, T, func(T) = int).
:- mode e_bar(out, out, out(func(in) = out is det)).
e_bar(2, 3, (func(X) = X * X)).
% ok (T = int)
:- func call_e_bar = int.
call_e_bar = F(X) + F(Y) :- e_bar(X, Y, F).
% ok
% returns 13 (= 2*2 + 3*3)
=== Existentially typed types === The standard library module „univ” provides an abstract type named „univ” which can hold values of any type. You can form heterogeneous containers (containers that can hold values of different types at the same time) by using data structures that contain univs, e.g. „list(univ)”. The interface to „univ” includes the following:
% "univ" is a type which can hold any value.
:- type univ.
% The function univ/1 takes a value of any type and constructs
% a "univ" containing that value (the type will be stored along
% with the value)
:- func univ(T) = univ.
% The function univ_value/1 takes a `univ' argument and extracts
% the value contained in the `univ' (together with its type).
% This is the inverse of the function univ/1.
:- some [T] func univ_value(univ) = T.
The `univ' type in the standard library is in fact a simple example of an existentially typed data type. It could be implemented as follows:
:- implementation.
:- type univ ---> some [T] mkuniv(T).
univ(X) = 'new mkuniv'(X).
univ_value(mkuniv(X)) = X.
=== Existentially typed type classes constraints === bla bla ===== Cechy języków Haskell i Mercury ===== Sztandarowe cechy języków, standardowe biblioteki, narzędzia programistyczne ==== Purity ==== ==== Laiziness - Strictness ==== ==== Type system ==== ==== Module system ==== ==== Standard librarnies ==== ==== Tools, extensions ==== ==== Extensibility ==== ===== Referencje ===== ====== Prezentacja ====== ====== Materiały ======
