To jest stara wersja strony!
Opis
Spotkania
20090416
20090326
Projekt
Introduction
What is Mercury?
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.
Why Mercury?
Mercury is developed to solve to main problems that appears in another logic programming languages (e.g. Prolog):
Mercury language features
purely declarative: predicates and functions in Mercury do not have non-logical side effects
strongly typed
strongly moded
strong determinism system
module system
supports higher-order programming, with closures, currying, and lambda expressions
Mercury should work on following platforms:
x86 machines running Debian Linux
x86 machines running Microsoft Windows XP
x86 machines running Solaris 9 (SunOS 5.9)
x86_64 machines running Debian Linux
Apple PowerPC machines running Mac
OS 10.3 and above
Mercury interoperability
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:
Microsoft's .NET
Native code
Java
Sprawozdanie
To sprawozdanie zostało napisane w maju 2009 r.
Jak zacząć?
Informacje dotyczące instalacji kompilatora, kompilowania i uruchamiania programów napisanych w Mercurym pod Windows XP
Do pobrania
Aby zacząć pracę z Mercurym i Haskellem należy pobrać następujące pliki:
Instalacja Cygwin
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”.
Instalacja Haskell
Uruchomić instalator Haskell Platform, postępować zgodnie z instrukcjami. Zakładam że Haskell został zainstalowany do folderu „C:\Program Files\Haskell Platform”
Instalacja Mercury
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:
rozpakować archiwum tar.gz np. do katalogu „~/USER_NAME/tymczasowy”,
uruchomić powłokę cygwina,
wywołać komendę
cd tymczasowy
wywołać komendę
cd mercury-compiler-0.13.1
wywołać komendę
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!),
jeśli instalacja odbędzie się pomyślnie, kompilator Mercury zostanie zainstalowany do katalogu „C:/cygwin/usr/local/mercury-0.13.1”
Żeby móc używać kompilatora mercury:
z poziomu linii komend systemu Windows XP należy dodać do ścieżki systemu Windows XP (Panel sterowania → System → zakładka Zaawansowane → przycisk Zmienne środowiskowe → grupa zmienne systemowe, zaznaczyć Path, przycisk Edycja) katalogi „C:/cygwin/usr/local/mercury-0.13.1/bin” oraz „C:/cygwin/bin” (kompilator Mercurego potrzebuje dostępu do kompilatora gcc)
z powłoki cygwina, należy dodać do pliku .bashrc, znajdującego się w katalogu home lub użytkownika („C:/cygwin/home” lub „C:/cygwin/home/USER_NAME”, jeżeli nie ma takiego pliku, należy go utworzyć) linię kodu:
PATH=/usr/local/mercury-0.13.1/bin:$PATH
Kompilowanie i uruchamianie programów w Mercurym
Aby skompilować program w pliku nazwa_pliku_źródłowego.m należy:
albo w linii komend Windows XP kompilator wywołuje się komendą
mercury --make nazwa_pliku_źródłowego
albo w powłoce Cygwin'a kompilator wywołuje się komendą
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.
Hello world!
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 nie będę tutaj szczegółowo omawiał.
% hello.m
:- module hello.
:- 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(R, !IO).
Aby skompilować ten program należy w powłoce cygwina wykonać:
$ mmc --make hello
Porównanie Haskell'a z Mercury'm
Na podstawie „Gentle Introduction to Haskell 98”.
Typy i wartości
W Mercurym wszystkie zmienne muszą zaczynać się z dużej litery (w przeciwieństwie do Haskell'a, gdzie wszystkie typy muszą zaczynać się z dużej litery). Nazwy modułów, typów, predykatów, funkcji itp. zaczynają się z małej litery.
Funkcje, predykaty, tuple, typy są wyrażeniami tak jak typy podstawowe. Mogą one być przekazywane do innych funkcji, predykatów, podobnie jak w Haskellu. Typy, funkcje i predykaty mogą być polimorficzne, również podobnie jak w Haskellu.
Typy użytkownika
Nowy typ deklaruje się za pomocą słów kluczowych „:- type”. Możliwe jest definiowanie typów enumerycznych jak i rekordów. Definicja typu następuje po słowie kluczowym „—>”.
:- type tree
---> empty
; leaf(int)
; branch(tree, tree).
:- type poliTree(T)
---> empty
; leaf(T)
; branch(poliTree(T), poliTree(T)).
:- type employee
---> employee(
name :: string,
age :: int,
department :: string
).
:- type list(T)
---> []
; [T | list(T)].
W Hasekllu typy użytkownika deklaruje się za pomocą słowa kluczowego „data” i listy konstruktorów oddzielonych „|”. Podobnie jak w Mercurym.
data Tree = Empty | Leaf Int | Branch Tree Tree
data PoliTree a = Empty | Leaf a | Branch (PoliTree a) (PoliTree a)
data Employee = Employee {name :: String, age :: Int, department :: String}
data List a = Nil | Cons a (List a)
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 ):
% Field selection for maps.
% Map ^ elem(Key) = map.search(Map, Key).
%
:- func map.elem(K, map(K, V)) = V is semidet.
% Field update for maps.
% (Map ^ elem(Key) := Value) = map.set(Map, Key, Value).
%
:- func 'elem :='(K, map(K, V), V) = map(K, V).
%uzycie:
% inicjalizowanie mapy
X = map.insert(map.insert(map.init, "Mercury", 1), "Haskell", 2),
% zmiana pola
Y = X^elem("Mercury") := 2,
% odczytanie pola
WhoWins = Y ^ elem("Haskell")
Typy równoważne
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
Listy
W Mercurym konstruktorem listy jest „|”, nie jak w Haskellu „:”. Dodatkowo listy nie należą do podstawowej biblioteki Mercurego (trzeba je importować „:- import_module list”)
Czy są w Mercurym List Comprehensions and Arithmetic Sequences? e.g.
Haskell oferuje pewne dodatki syntaktyczne dla list:
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x ]
++ [x]
++ quicksort [y | y <- xs, y>=x]
qsort2 :: Ord a => [a] -> [a]
qsort2 [] = []
qsort2 (x:xs) = qsort2 lesser ++ equal ++ qsort2 greater
where
(lesser,equal,greater) = part x xs ([],[x],[])
part :: Ord a => a -> [a] -> ([a],[a],[a]) -> ([a],[a],[a])
part _ [] (l,e,g) = (l,e,g)
part p (x:xs) (l,e,g)
| x > p = part p xs (l,e,x:g)
| x < p = part p xs (x:l,e,g)
| otherwise = part p xs (l,x:e,g)
niestety brakuje ich w Mercurym (kod ze strony http://en.literateprograms.org/Quicksort_(Mercury)):
:- module quicksort.
:- interface.
:- import_module list, int.
:- func qsort(list(int)) = list(int).
:- mode qsort(in) = out is det.
:- implementation.
%
% quicksort
%
qsort( []) = [].
qsort( [Hd | Tl]) = Result :- (
/* length 1 */
Tl = [] -> Result = [Hd]
;
/* length 2 */
Tl = [Hd2] -> (
Hd =< Hd2 -> Result = [Hd | [Hd2]]
;
Result = [Hd2 | [Hd]]
)
;
/* else */
InputList = [Hd | Tl],
Pivot = list.index0_det( InputList, list.length( InputList) / 2),
pivot_classify( InputList, Pivot, Lows, Mids, Highs),
Result = list.append( list.append( qsort(Lows), Mids), qsort(Highs))
).
%
% classify list elements
%
:- pred pivot_classify( list(int), int, list(int), list(int), list(int)).
:- mode pivot_classify( in, in, out, out, out) is det.
pivot_classify( [], _Pivot, [], [], []).
pivot_classify( [Hd | Tl], Pivot, Lows, Mids, Highs) :-
( Hd < Pivot -> some [Lows0] (
pivot_classify( Tl, Pivot, Lows0, Mids, Highs),
Lows = [Hd | Lows0]
)
;
Hd > Pivot -> some [Highs0] (
pivot_classify( Tl, Pivot, Lows, Mids, Highs0),
Highs = [Hd | Highs0]
)
;
/* else */
some [Mids0] (
pivot_classify( Tl, Pivot, Lows, Mids0, Highs),
Mids = [Hd | Mids0]
)
).
:- end_module quicksort.
Predykaty i funkcje
Składnia:
:- pred is_all_uppercase(string).
:- func strlen(string) = int.
Predykaty i funkcje w Mercurym mogą być również polimorficzne:
:- pred member(T, list(T)).
:- func length(list(T)) = int.
Składnia Haskella jest podobna:
is_all_uppercase :: String -> Bool
is_all_uppercase [] = False
is_all_uppercase (a:[]) = isUpper a
is_all_uppercase (pierwszyZnak:resztaZnakow) = isUpper pierwszyZnak && is_all_uppercase resztaZnakow
length :: [t] -> Int
length [] = 0
length (x:xs) = 1 + lenght xs
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
W Mercurym funkcje i predykaty to również wyrażenia. Predykaty i funkcje jako argumenty mogą przyjmować inne predykaty i funkcje.
Poniżej przedstawione są predykaty i funkcje wyższych rzędów.
:- type foldl_pred(T, U) == pred(T, U, U).
:- type foldl_func(T, U) == (func(T, U) = U).
:- pred p(int) `with_type` foldl_pred(T, U).
:- func f(int) `with_type` foldl_func(T, U).
% co jest równoważne
% :- pred p(int, T, U, U).
% :- pred f(int, T, U) = U.
% lub
% :- pred p(int, foldl_pred(T, U)).
% :- pred f(int, foldl_func(T, U)) = U.
System instancji (ang. instantiatedness)
System instancji 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:
niezwiązany (ang. free), czyli zmiennej nie jest przypisana żadna wartość ani wyrażenie (w Cdeklaracja zmiennej jakiejś klasy bez inicjalizacji np.: ''String lancuch;'' wtedy zmienna //lancuch// byłaby niezwiązana), a dodatkowo zmienna ta nie jest związana z żadną inną zmienną. Wszyscy potomkowie niezwiązanego argumentu (and node) są niezwiązani,
**związany (ang. bound)**, czyli zmiennej jest przypisana jakaś wartość lub wyrażenie (np. w C++ ''String zwiazanyLancuch = "miw";'')
Z ich pomocą można budować bardziej wyszukane stany instancji. Poniżej znajduje się przykład stanu instancji "dbOperationInst" dla typu "dbOperation":
<code>
:- type dbOperation ---> lookup(key, data) ; set(key, data).
:- inst dbOperationInst ---> lookup(ground, free) ; set(ground, ground).
</code>
==== System trybów (ang. mode system)====
System trybów (ang. //mode system//), ogólnie rzecz biorąc, pozwala narzucić **ograniczenie** na zmianę stanu instancji zmiennej. Tryb funkcji lub predykatu jest mapowaniem pomiędzy początkowym stanem instancji argumentów i rezultatu (predykatu lub funkcji), a ich końcowym stanem instancji.
Np. jeżeli chcemy nałożyć ograniczenia na argumenty wejściowe funkcji i jej rezultat, to ograniczenia te możemy zdefiniować w następujący sposób:
<code>
:- mode in(Inst) == Inst >> Inst. /* definicja trybu parametrycznego */
:- mode out(Inst) == free >> Inst. /* definicja trybu parametrycznego */
:- inst listskel ---> []; [free listskel].
:- func length(list(T)) = int. /* deklatacja funkcji */
:- mode length(in(Inst =< listskel)) = out. /* definicja parametrycznie ograniczonego trybu funkcji */
:- mode length(out(Inst =< listskel)) = in. /* definicja parametrycznie ograniczonego trybu funkcji */
</code>
Definicja trybu może zawierać argument parametryczny, w powyższym przykładzie parametrem tym jest „Inst”.
:- 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 */
% definicja predykatu
append(Xs, Ys, Zs) :-
(
Xs = [],
Zs = Ys
;
Xs = [Hd | Tl],
append(Tl, Ys, Zs0),
Zs = [Hd | Zs0]
).
=== Unique insts and modes ===
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 solution ^ 1 solution ^ more than 1 solution ^
^ can't fail | erroneous | det | multi |
^ can fail | 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.
==== 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) - f(x,y) = x/y, f(2/3) = g(3) (g(y) = 2/y) = 2/3
* klauzule (ang. closures) - czyli funkcje, która używają wolnych zmiennych(zmienna, która nie jest związana: Haskell /x -> x y → y jest 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.
* 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) ===
Sum123 = sum([1,2,3])
% binds `Sum123' to a higher-order predicate term of type `pred(int)'.
*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ć:
list.filter((pred(X::in) is semidet :- X \= 2), [1, 2, 3], List)
%lub
list.filter(not_equal(2), [1, 2, 3], List)
%gdzie not_equal jest zdefiniowane nastepujaco
:- pred not_equal(T::in, T::in) is semidet.
not_equal(X, Y) :- X \= Y.
fgh
=== Klauzule (closures) ===
addNumFunction = (func addNumbers(X::in, Y::in) = Sum::out is Det :- Sum = X + Y).
:- func sum2Nums(int::in, int::in) = int::out.
:- func addNumClosure(X::in) = PartialSum::out :-
%PartialSum = call(addNumFunction, X).
PartialSum = sum2Nums(X).
==== Type classes ====
Mercury supports constrained polymorphism in the form of type classes. Type classes allow the programmer to write predicates and functions which operate on variables of any type (or sequence of types) for which a certain set of operations is defined.
==== Existential types ====
Existentially quantified type variables (or simply “existential types” for short) are useful tools for data abstraction. In combination with type classes, they allow you to write code in an “object oriented” style that is similar to the use of interfaces in Java or abstract base classes in C.
Mercury supports existential type quantifiers on predicate and function declarations, and in data type definitions. You can put type class constraints on existentially quantified type variables.
Modules and implementation hiding
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
Extensibility
Referencje
Prezentacja
Materiały