Hlavní navigace

ML – funkcionální jazyk s revolučním typovým systémem

8. 2. 2022
Doba čtení: 30 minut

Sdílet

 Autor: Depositphotos
Před neuvěřitelnými 49 lety vznikl první koncept jazyka ML. Jedná se o programovací jazyk, který byl v mnoha ohledech přelomový, a to díky svému typovému systému, jenž byl zkombinovaný s pattern matchingem.

Obsah

1. ML – funkcionální jazyk s revolučním typovým systémem

2. Vznik jazyka Standard ML

3. Od Standard ML k jazykům Caml, OCaml a F#

4. Online varianta jazyka Standard ML

5. Instalace Standard ML z nabízených balíčků

6. Instalace Standard ML ze zdrojových kódů

7. Komentáře

8. Výrazy v jazyku ML

9. Proměnné

10. Základní datové typy jazyka ML

11. Složené datové typy: n-tice a záznamy

12. Seznamy

13. Funkce

14. Rekurzivní funkce

15. Anonymní funkce

16. Pattern matching

17. Obsah druhé části článku

18. Repositář s demonstračními příklady

19. Literatura

20. Odkazy na Internetu

1. ML – funkcionální jazyk s revolučním typovým systémem

V dnešním článku se seznámíme se základními vlastnostmi programovacího jazyka ML neboli Meta Language. Jedná se o funkcionální a modulární jazyk se silným (statickým) typovým systémem a pattern matchingem, jehož počátky můžeme datovat až do roku 1972. Později byl tento jazyk formálně specifikován (je tedy popsán specifikací a nikoli referenční implementací) a začal se nazývat Standard ML, popř. zkráceně pouze SML. ML je zajímavý sám o sobě, ovšem nejenom to – inspiroval totiž autory celé řady dalších programovacích jazyků, ať již se to týká přímých následovníků Caml a OCaml či jazyků, které byly ML silně inspirovány: F#, Haskell, Scala a v neposlední řadě Rust a částečně i Go.

Poznámka: samotný standard, resp. specifikace je relativně krátká v porovnání s tím, o jak mocný jazyk se jedná.

Jazyk ML je inspirativní kromě dalších věcí i díky typovému systému. O typovém systému jazyka ML (a od něj odvozeného OCamlu) se často říká, že se jeho tvůrcům podařilo najít takové řešení, které umožňuje krátký a výstižný zápis algoritmů (což je doménou dynamicky typovaných jazyků), ovšem současně se podařilo zajistit typovou bezpečnost, a to v mnoha případech vyšší, než jaká je očekávána od tradičních staticky typovaných jazyků. Příklady si ukážeme níže a bude z nich patrné, že většina algoritmů implementovaných v ML skutečně nikde neobsahuje explicitně zapsané typové informace – ty jsou totiž odvozeny ze samotného algoritmu. V případě typového systému se vždy jedná o dosažení rovnováhy mezi svobodou programátora a nebezpečím zanesení chyb do programů.

Poznámka: řešení typového systému založené na odvození typů (type inference) se začalo prosazovat i v dalších programovacích jazycích, i když někdy jen v omezené míře. Například v jazyku Go lze deklarovat proměnnou pouze uvedením jejího jména a hodnoty, přičemž typ proměnné je odvozen od této hodnoty. I taková zdánlivá maličkost ovšem „pocitově“ (styl zápisu, rychlost tvorby nového kódu) jazyk Go posouvá do takové míry, že mi už několik vývojářů řeklo „ten jazyk je nakonec vlastně hodně podobný Pythonu“.

Druhou důležitou vlastností jazyka ML je podpora pattern matchingu, s níž se setkáme v navazujících kapitolách a podrobněji si ji popíšeme příště. A konečně nesmíme zapomenout na třetí důležitou vlastnosti ML, jíž je podpora tzv. algebraických datových typů. Touto tématu, které se (kupodivu) jen pomalu dostává do mainstreamových jazyků, se budeme věnovat v samostatném článku.

2. Vznik jazyka Standard ML

Jazyk ML vznikl v univerzitním prostředí ve Velké Británii, takže se jedná o další oblast, v níž vznikl nějaký důležitý koncept v oblasti teorie programovacích jazyků (mezi další takové „líhně“ patřily pochopitelně USA s MIT, Bell Labs, IBM a taktéž kontinentální Evropa s Prologem a pascalskou větví programovacích jazyků). První kroky vedoucí později ke vzniku ML provedla na začátku sedmdesátých let minulého století skupina vědců z laboratoře pro výzkum umělé inteligence z univerzity v Edinburgu. Jak bylo v té době v oblasti AI prakticky nepsaným standardem, používal se převážně programovací jazyk LISP, který byl ovšem doplněný o Prolog, což byla tehdy žhavá novinka, protože Prolog vznikl v roce 1972.

Poznámka: traduje se sice rivalita panující mezi výzkumnými skupinami používajícími LISP se skupinami používajícími Prolog, ale zde je vidět, že je možné využít možností obou konceptuálně odlišných jazyků.

Výše zmíněná skupina pro oblast umělé inteligence pracovala na vývoji systému LCF (Logic For Computable Functions), jenž byl určen pro dokazování teorémů. Tento systém byl naprogramován v LISPu. Poněkud předbíháme, ale na tomto místě je vhodné poznamenat, že ideové stopy LISPu jsou v jazyku ML poměrně dobře patrné. A právě pro potřeby LCF vznikl nový (tehdy vlastně doménově specifický) jazyk ML. To vlastně znamená, že samotný ML byl pouze vedlejším produktem práce na LCF, teprve poději došlo k osamostatnění ML.

První varianta ML pro LCF vznikala v období 1973 až 1978. Původně byly zdrojové kódy transpilovány do LISPu a teprve poté překládány do strojového (objektového) kódu. Ovšem kromě technických detailů (jakkoli jsou zajímavé) je důležité, kdo se na vývoji ML podílel a jaké myšlenky zde byly využity. Jednou z inspirací byl jazyk ISWIM (If you See What I Mean) Petera Landina z šedesátých let. Tento jazyk byl založen na lambda kalkulu, podporoval funkce vyššího řádu a používal dynamické typování a lexikální obory platnosti. Peter Landin pro tento projekt vytvořil operátor J. Na vývoji ML se nepřímo podílel i Christopher Strachey, jenž dříve vytvořil jazyk CPL, což je praprapředek céčka (CPL → BCPL → B → C). Mimochodem, právě Christopher Strachey zavedl v IT několik nových termínů, například od něj pochází „syntactic sugar“.

Pro vznik ML byl důležitý i jazyk HOPE s pattern matchingem. Funkce zapsaná v jazyku HOPE se až na několik detailů shoduje s ML:

def fact : num -> num;
--- fact 0 <= 1;
--- fact n <= n*fact(n-1);

V ML se objevilo i automatické odvozování typů, což je technika, která byla shrnuta v roce 1978 pod jménem Hindley-Milner type inference. A ve stejném roce byl ML pro LCF konečně dokončen.

Vzhledem k tomu, že ML byl součástí LCF a nebylo ho možné používat mimo tento systém (proto se taktéž někdy setkáme s označením LCF/ML), objevily se snahy o plné oddělení ML jako samostatného jazyka. Takto vznikl „ML under VAX“ neboli zkráceně „VAX ML“. Jednalo se o samostatně použitelnou variantu ML, která byla naprogramována v Pascalu. Překladač do strojového kódu VAXu byl dokončen v roce 1981. Prakticky právě od této chvíle se začala psát historie skutečně dostupného ML. Ostatně je to patrné i na tom, že o rok později byl jazyk portován do Unixu (stále v Pascalu). Později byl runtime jazyka přepsán do C, ovšem samotný překladač zůstal v Pascalu.

V roce 1983 se autoři programovacího jazyka ML setkali na universitě v Edinburgu s cílem formálně jazyk ML specifikovat. Na rozdíl od například Pythonu měl být tedy jazyk ML založen na formální definici a nikoli na referenční implementaci. Výsledkem tohoto setkání byl popis ML, článek „Compiling a Functional Language“ a zhruba v této době se namísto ML začalo používat označení Standard ML neboli zkráceně SML.

3. Od Standard ML k jazykům Caml, OCaml a F#

Na konci předchozí kapitoly byl zmíněn rok 1983. Z hlediska historie programovacích jazyků se jednalo o zajímavé období, protože se prakticky „všude“ začalo mluvit o objektově orientovaném programování jako o stříbrné kulce, která má vyřešit (skoro) všechny programátorské problémy a současně se předpokládalo, že právě objektově orientované programování bude paradigmatem používaným v budoucnu (což se nakonec ukázal být pravdivý předpoklad, i když nakonec zvítězilo „třídní OOP“ a nikoli koncept posílání zpráv). Ostatně v roce 1983 vzniklo C++, v roce 1989 pak C++2.0. Začátek práce na Javě se datuje do roku 1991, první verze pak byla vydána v roce 1995. A tématu se chytily i další společnosti, takže například vznikly assemblery podporující objektově orientované programování (což v praxi nebyla tak úplně pravda, ale na krabici se to pěkně vyjímalo).

V rámci plánů dalších verzí jazyka ML (přednášky ML-2000) se začalo mluvit o podpoře objektově orientovaného programování i v tomto jazyce. Nejprve v roce 1985 vznikl jazyk Caml (Categorical Abstract Machine Language), jehož poslední verze nabízela OO vrstvu. Na základě zkušeností s Camlem byl v roce 1996 vydán jazyk OCaml (Objective Caml), jenž je používán dodnes. A zapomenout nesmíme na jazyk F#, jenž se taktéž nechal inspirovat jazykem ML. Tomuto velmi zajímavému programovacímu jazyku bude věnován samostatný článek (s vydáním jsem čekal deset let, protože jsem popravdě věřil, že firma Microsoft tento jazyk „zařízne“, podobně jako mnoho dalších technologií).

Poznámka: vývoj důležitých programovacích jazyků se shrnut na tomto grafu.

4. Online varianta jazyka Standard ML

Jazyk Standard ML si můžete prakticky vyzkoušet, a to hned několika způsoby. Nejjednodušší, resp. časově nejméně náročné je použití online verze, pro jejíž zprovoznění postačuje pouze nějaký moderní webový prohlížeč (s JavaScriptem) a není tedy vyžadována instalace klasického interaktivního prostředí a překladače SML. Online verzí jazyka ML v současnosti existuje několik, přičemž jedním z příkladů takového jednoduše pojatého vývojového prostředí je online REPL (Read Eval Print Loop) dostupný na adrese https://sosml.org/ (SOSML). Předností této varianty je fakt, že dlouhotrvající výpočty jsou automaticky ukončeny, čímž je například zajištěno, že se program „zotaví“ z nekonečné rekurze. Použití SOSML je jednoduché – do levého textového pole se zapisují poznámky, výrazy a definice. Po ukončení výrazu či definice středníkem je provedeno jeho vyhodnocení a výsledek se zapíše do pravého textového pole (středník je zde tedy velmi důležitý). Jak příkazy, tak i jejich výsledky jsou barevně odlišeny; navíc je odlišeno a případné hlášení o chybě.

Obrázek 1: Interaktivní webové prostředí SOSML.

Poznámka: demonstrační příklady, které si ukážeme v dalších kapitolách, byly otestovány mj. i právě ve webovém prostředí SOSML.

5. Instalace Standard ML z nabízených balíčků

Pro plné využití možností nabízených programovacím jazykem ML (resp. přesněji řečeno Standard ML) již nebude webové uživatelské prostředí dostačující a bude nutné si nainstalovat nějakou vhodnou nativní variantu tohoto jazyka. Většina nejvýznamnějších distribucí Linuxu nabízí nějakou variantu jazyka Standard ML již ve svém standardním repositáři. Konkrétně se jedná o balíčky mlton, smlnj či polyml (pokaždé se jedná o jinou implementaci, to nám však v dnešním článku nemusí vůbec vadit):

  • mlton: Optimizing compiler for Standard ML MLton is a whole-program optimizing compiler for Standard ML. MLton generates standalone executables with excellent runtime performance, is SML 97 compliant, and has a complete basis library. MLton has source-level profiling, a fast C FFI, an interface to the GNU multiprecision library, and lots of useful libraries.
  • smlnj: SML/NJ is an implementation of the Standard ML programming language. Standard ML has many features, including type safety, polymorphism, algebraic data types with pattern matching, higher-order functions, and a sophisticated module system. It is especially well-suited for writing compilers and other language processors.
  • polyml: interpreter and interactive compiler for Standard ML. Poly/ML is an implementation of the Standard ML programming language Standard ML is a general-purpose, modular, type-safe, strict, functional programming language. Poly/ML is SML 97 compliant interpreter and compiler that supports the generation of stand-alone executables with an interactive toplevel (REPL).

Příklady instalace balíčků mlton a polyml na systému Fedora release 34 (Thirty Four):

# dnf install mlton
 
$ mlton
# dnf install polyml
 
$ poly -version
Poly/ML 5.8.2 Release
Poznámka: mlton je překladač, takže pro interaktivní způsob programování se příliš nehodí. V tomto ohledu je lepší použít polyml či smlnj.

6. Instalace Standard ML ze zdrojových kódů

V případě, že žádný podobný balíček v repositáři vaší distribuce nenajdete, bude nutné nainstalovat prostředí i překladač jazyka Standard ML ze zdrojových kódů. Postup není ve skutečnosti příliš složitý (jen časově náročný) a je popsán v navazujících odstavcích, a to pro pro implementace Standard ML of New Jersey a Poly/ML.

Nejprve je nutné stáhnout tarball obsahující zdrojové kódy skriptů a dalších nástrojů určených pro překlad SML:

$ wget http://smlnj.cs.uchicago.edu/dist/working/110.98.1/config.tgz
 
--2020-12-17 20:44:12--  http://smlnj.cs.uchicago.edu/dist/working/110.98.1/config.tgz
Resolving smlnj.cs.uchicago.edu (smlnj.cs.uchicago.edu)... 128.135.164.125
Connecting to smlnj.cs.uchicago.edu (smlnj.cs.uchicago.edu)|128.135.164.125|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 517536 (505K) [application/x-gzip]
Saving to: ‘config.tgz’
 
config.tgz          100%[===================>] 505.41K   920KB/s    in 0.5s
 
2020-12-17 20:44:13 (920 KB/s) - ‘config.tgz’ saved [517536/517536]
Poznámka: jak již jméno a ostatně i velikost staženého tarballu naznačuje, neobsahuje všechny potřebné zdrojové kódy, ale „pouze“ konfigurační a instalační skripty.

Tarball běžným způsobem rozbalíme:

$ tar xvf config.tgz

A spustíme vlastní instalaci:

$ config/install.sh -default 64
 
[scanning (183299-export.cm):driver/(sources.cm):../front-end/(sources.cm):typechecker/(sources.cm):../../back-end/(sources.cm):cxx/(sources.cm):../../views/sources.cm]
[scanning (183299-export.cm):driver/(sources.cm):../front-end/(sources.cm):typechecker/(sources.cm):../../back-end/(sources.cm):cxx/(sources.cm):../util/sources.cm]
[scanning (183299-export.cm):driver/(sources.cm):../front-end/(sources.cm):typechecker/(sources.cm):../../back-end/(sources.cm):sml/sources.cm]
[parsing (183299-export.cm):183299-export.sml]
[creating directory .cm/SKEL]
[compiling (183299-export.cm):183299-export.sml]
[creating directory .cm/GUID]
[creating directory .cm/amd64-unix]
[code: 229, data: 29, env: 39 bytes]
config/install.sh: Installation complete.

Po dokončení předchozího kroku by se měl v podadresáři bin objevit mj. i spustitelný soubor nazvaný sml. Po spuštění tohoto souboru se zobrazí REPL (tedy interaktivní prostředí) jazyka Standard ML:

$ cd bin
 
$ ./sml
 
Standard ML of New Jersey (64-bit) v110.98.1 [built: Thu Dec 17 20:45:35 2021]

Překlad a instalace další implementace jazyka Standard ML, konkrétně projektu Poly/ML, vyžaduje instalaci C++, ovšem celý postup je snazší:

Nejprve stáhneme poslední verzi zdrojových kódů:

$ wget https://github.com/polyml/polyml/archive/refs/tags/v5.9.tar.gz
 
--2022-02-06 04:59:05--  https://github.com/polyml/polyml/archive/refs/tags/v5.9.tar.gz
Resolving github.com (github.com)... 140.82.112.4
Connecting to github.com (github.com)|140.82.112.4|:443... connected.
HTTP request sent, awaiting response... 302 Found
Location: https://codeload.github.com/polyml/polyml/tar.gz/refs/tags/v5.9 [following]
--2022-02-06 04:59:05--  https://codeload.github.com/polyml/polyml/tar.gz/refs/tags/v5.9
Resolving codeload.github.com (codeload.github.com)... 140.82.113.9
Connecting to codeload.github.com (codeload.github.com)|140.82.113.9|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: unspecified [application/x-gzip]
Saving to: ‘v5.9.tar.gz’
 
v5.9.tar.gz             [    <=>  ]   3.59M  5.54MB/s    in 0.6s
 
2022-02-06 04:59:06 (5.54 MB/s) - ‘v5.9.tar.gz’ saved [3764115]

Získaný tarball rozbalíme:

$ tar xvfz v5.9.tar.gz

Provedeme konfiguraci projektu, a to zcela standardním způsobem:

$ cd polyml-5.9/
$ ./configure

Následuje vlastní překlad:

$ make

Nakonec otestujeme, zda je možné interaktivní běhové prostředí spustit a použít:

$ ./poly
Poly/ML 5.9 Release
 
> 6*7;
val it = 42: int

7. Komentáře

Poznámka na úvod: syntaxe jazyka ML, resp. Standard ML může být na první pohled poněkud podivná, zejména pro programátory, kteří pracují s programovacími jazyky patřícími do céčkové větve (tedy například s C, C++, Javou, JavaScriptem či C#). Ovšem v praxi se ukazuje, že syntaxe je tím nejmenším problémem, protože důležitá je především sémantika a na tu se po popisu základních konceptů zaměříme (ostatně například Caml/OCaml dovolují vytvořit si v případě potřeby vlastní syntaxi).

Nyní, když máme k dispozici na výběr mezi webovým rozhraním a řádkovým (terminálovým) rozhraním jazyka SML, si můžeme popsat a ihned také ukázat základní vlastnosti programovacího jazyka ML. Začneme tím nejzákladnějším (a nejméně problematickým) prvkem jazyka, kterým jsou komentáře. Ty se zapisují „Pascalovským“ způsobem mezi dvojici komentářových závorek (* a *), tedy následovně:

(* komentáře *)

Komentáře mohou být v případě potřeby víceřádkové, takže je možné například zakomentovat celý blok s definicí funkce:

(*
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2)
*)
Poznámka: prozatím se netrapte tím, jak zápis funkce vypadá. K tomuto problému se dostaneme později.

Velmi užitečné je, že komentáře mohou (na rozdíl od mnoha céčkových jazyků) obsahovat další komentáře, takže je snadné například zakomentovat část kódu, která obsahuje běžné komentáře:

(*
(* Výpočet Fibonacciho posloupnosti *)
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2)
*)

8. Výrazy v jazyku ML

Nyní si ukažme práci s výrazy. Samotné výrazy (více o nich níže) se zapisují přímo, není zapotřebí je nějakým způsobem speciálně označovat:

výraz
Poznámka: některé varianty jazyka ML vykonají (resp. přesněji řečeno vyhodnotí) výraz až ve chvíli, kdy je za něj zapsán středník:
výraz;

Příklad výrazů s jejich okamžitým vyhodnocením:

> 1;
val it = 1: int
 
> 6*7;
val it = 42: int
 
> "foo";
val it = "foo": string
 
> [1, 2, 3];
val it = [1, 2, 3]: int list
 
> false;
val it = false: bool

Povšimněte si důležité vlastnosti jazyka ML – výsledek vyhodnocení výrazu není tvořen pouze vypočtenou hodnotou, ale vždy obsahuje i informace o typu této hodnoty.

Součástí výrazu může být i volání funkce:

> abs(1-5);
val it = 4: int

Volání funkce s jedním parametrem lze zapsat se závorkami okolo parametru či bez závorek:

> abs(1);
val it = 4: int
 
> abs 1;
val it = 1: int
Poznámka: možná se chtěli autoři ML vyvarovat jednoho (jediného?) problematického rysu LISPu, kterou je nadužívání závorek.

Ovšem pozor je zapotřebí dát u funkcí s více parametry:

> abs(1-5);
val it = 4: int
 
> abs 1-5;
val it = ~4: int

V prvním případě se vrátila hodnota 4, tedy skutečně absolutní hodnota rozdílu 1–5. Ve druhém případě se vrátila hodnota –4, což je výsledek rozdílu mezi absolutní hodnotou 1 a 5.

Poznámka: zde můžeme vidět další (dnes) nestandardní syntaxi jazyka ML – záporné hodnoty se zapisují pomocí znaku „~“.

9. Proměnné

Proměnné, které jsou v jazyce ML vždy silně typované (tj. typ je přiřazen i k proměnné, nikoli k hodnotě) se deklarují s využitím slova val. Opět si ukažme několik příkladů:

> val x = 10;
val x = 10: int
 
> val y = 3.14;
val y = 3.14: real
 
> val z = true;
val z = true: bool
 
> val w = "foobar";
val w = "foobar": string

Zde jsme narazili na první důležitý koncept programovacího jazyka ML. Tento koncept se nazývá odvození typů neboli type inference. Spočívá v tom, že na základě typu hodnoty dokáže ML odvodit i typ proměnné, výrazu nebo parametru či návratové hodnoty funkce. Výše uvedený příklad povede k automatickému odvození typů všech čtyř proměnných, typ se od této chvíle stává součástí metainformace o proměnných.

Totéž platí i pro proměnné, jimž je přiřazen výsledek nějakého složitějšího výrazu:

> val a = 6*7;
val a = 42: int
 
> val b = 10.0 / 4.0;
val b = 2.5: real
 
> val c = 10 div 4;
val c = 2: int

Výsledek posledního výrazu je uložen do speciální proměnné nazvané it:

> 42;
val it = 42: int;

Obsah i typ této proměnné je neustále přepisován:

> 1;
val it = 1: int
 
> it;
val it = 1: int
 
> 1+2;
val it = 3: int
 
> it;
val it = 3: int

10. Základní datové typy jazyka ML

S některými datovými typy, které jsou jazykem ML podporovány, jsme se (vlastně trošku mimochodem) setkali v předchozích kapitolách. Ovšem pro další články o ML je nutné zmínit všechny podporované datové typy.

První datový typ se jmenuje unit, ovšem většinou se mu říká „null type“. Je reprezentován prázdnými kulatými závorkami a technicky se jedná o n-tici bez prvků:

> ();
val it = (): unit
Poznámka: tento datový typ je v praxi velmi užitečný. Podobným typem známým z céčkovské větve jazyků je typ void, jehož jméno ovšem (chybně?) naznačuje, že neexistuje žádný prvek tohoto typu.

Dalším datovým typem je typ bool. Ten již není, na rozdíl od typu unit nijak výjimečný. Obsahuje dvě hodnoty true a false:

> true;
val it = true: bool
 
> false;
val it = false: bool

Následuje celočíselný typ int, u něhož je zvláštní fakt, že se záporné hodnoty zapisují s tildou a nikoli znakem „-“:

> 42;
val it = 42: int
 
> 0 - 42;
val it = ~42: int

Přetečení může být v některých případech detekováno již v čase překladu (což ovšem není nic překvapujícího):

> 10000000000000000000000000;
poly: : error: Overflow exception raised while converting 10000000000000000000000000 to int
Found near 10000000000000000000000000
Static Errors

Následuje datový typ real, jehož hodnoty jsou interně reprezentovány s využitím systému s plovoucí řádovou čárkou:

> 3.14;
val it = 3.14: real
 
> 0.0 - 3.14;
val it = ~3.14: real

Následují řetězce, neboli typ string:

> "foobar";
val it = "foobar": string

A konečně typ char reprezentující jediný znak:

> #"a";
val it = #"a": char
 
> #"ab";
poly: : error: Conversion exception (Not exactly one character) raised while converting ab to char
Found near #"ab"
Static Errors

U proměnných lze typ specifikovat i explicitně:

val i : int = 10;
val j : real = 10.0;
val k = i;

11. Složené datové typy: n-tice a záznamy

V ML jsou podporovány tři složené datové typy: n-tice, záznamy a seznamy. Nejjednodušší jsou n-tice, které mohou obsahovat prvky libovolných typů. Typ n-tice jako celku je pak odvozen od typů jednotlivých prvků. Speciálním případem je n-tice bez prvků, neboli typ unit zmíněný výše:

> ();
val it = (): unit

Následuje příklad n-tic s větším množstvím prvků. Povšimněte si toho, jak je zapsán datový typ takové n-tice:

> (1,2);
val it = (1, 2): int * int
 
> ("foo", "bar");
val it = ("foo", "bar"): string * string
 
> (1, "foo", 3.14);
val it = (1, "foo", 3.14): int * string * real

Vzhledem k tomu, že n-tice s jediným prvkem nemá praktický význam, není podporována (na rozdíl od Pythonu, kde se však jedná o syntakticky problematický rys jazyka):

> (2);
val it = 2: int

Následují záznamy, v nichž jsou prvky taktéž libovolného typu, ovšem na rozdíl od n-tic jsou tyto prvky pojmenovány:

> {color="silver", make="Toyota", model="Corolla", year=1986};
val it = {color = "silver", make = "Toyota", model = "Corolla", year = 1986}:
   {color: string, make: string, model: string, year: int}

Blíže se s tímto datovým typem seznámíme příště.

12. Seznamy

A konečně, nejdůležitějším složeným datovým typem jsou seznamy (lists). Ty jsou homogenní, tj. všechny prvky seznamů musí být stejného typu:

> [1,2,3];
val it = [1, 2, 3]: int list
 
> ["foo", "bar"];
val it = ["foo", "bar"]: string list

Pokus o vytvoření heterogenního seznamu skončí s chybou:

> [1, "foo"];
poly: : error: Elements in a list have different types.
   Item 1: 1 : int
   Item 2: "foo" : string
   Reason:
      Can't unify int (*In Basis*) with string (*In Basis*)
         (Different type constructors)
Found near [1, "foo"]
Static Errors

Víme již, že speciálním případem n-tice je n-tice bez prvků. I u seznamů se jedná o speciální případ, o čemž se můžeme velmi snadno přesvědčit (viz typ výrazu):

> [];
val it = []: 'a list
 
Poznámka: o speciální případ se zde jedná z toho důvodu, že ML nedokáže z prázdného seznamu odvodit typ prvků. V mnoha programových konstrukcích tak musí předpokládat, že se může jednat o libovolný seznam.

Inspirace LISPem se nezapře v tom, že prázdný seznam je možné zapsat i slovem nil:

> nil;
val it = []: 'a list

Sémantika seznamů je ze značné míry převzata z LISPu, ovšem syntaxe práce s nimi je odlišná. Seznam může být v tomto kontextu definován rekurzivně:

  • buď je seznam prázdný
  • nebo má formu hlava::tělo, kde hlava je první prvek seznamu

To například znamená, že seznam [42] je shodný se seznamem 42::[]:

> [42];
val it = [42]: int list
 
> 42::[];
val it = [42]: int list

Zápis hlava::tělo se používá jak pro konstrukci seznamu, tak i například ve vzorech (patterns), s nimiž se seznámíme později.

Některé důležité funkce pro práci se seznamy:

Funkce Stručný popis
null(x) test na prázdný seznam
length(x) délka seznamu
hd(x) první prvek seznamu
tl(x) tělo seznamu (bez prvního prvku)
nth(x) n-tý prvek seznamu

Navíc je možné operátorem @ spojit dva seznamy. Schválně není pro tento účel použit operátor +, aby nedošlo k jeho zbytečnému několikanásobnému přetížení.

13. Funkce

Ve funkcionálních programovacích jazycích mají funkce stejně plnohodnotný význam, jako jakékoli jiné typy. Výjimkou není ani jazyk ML, v němž je typ funkce odvozen od typů parametrů a návratové hodnoty (automaticky odvozené od použitých výrazů!). Funkce je definována klíčovým slovem fun:

fun <jméno-funkce> <formální-parametry-funkce> = <tělo-funkce>

Pro zajímavost se podívejme, jaká klíčová slova pro definici funkce se používají v těch programovacích jazycích, v nichž je tento koncept použit (vynecháme tedy klasické céčkové jazyky):

Jazyk Klíčové slovo
ML fun
LISP defun
Scheme define
Clojure defn
Python def
JavaScript function
Julia function
Lua function
Pascal function
Go func
Rust fn

Podívejme se nyní na definici jednoduché funkce, která zvýší obsah svého parametru o jedničku a vrátí novou hodnotu. Funkce se bude jmenovat inc a její parametr n:

fun inc n = n + 1;
Poznámka: nejedná se o zápis přiřazení, ale o funkci s parametrem n, jejíž tělo je n+1.

U této funkce je zajímavé především to, že jsme nikde neuvedli typ parametru ani typ návratové hodnoty a přesto jazyk ML zjistil, že se jedná o funkci int → int. Přitom se vychází z těla funkce, tedy z výrazu n+1, což je v jazyku ML striktně součet dvou celých čísel.

Zavolání takové funkce je jednoduché:

int 10;

Pozor si musíte dát na to, že se používá levá asociativita, což u funkcí volaných bez kulatých závorek povede ke špatným výsledkům (chybě při překladu):

f g x znamená (f g) x

Můžete si to ostatně sami otestovat:

(* Kompozice funkcí *)
 
fun inc x = x + 1;
fun double x = x * 2;
 
inc(double 1);
 
inc double 1;

Definice a zavolání funkce se dvěma parametry:

(* Definice funkce *)
 
fun add (x, y) = x + y;
 
add(3,4);
Poznámka: opět se bude jednat o funkci akceptující jako své parametry celá čísla a vracející celé číslo.

14. Rekurzivní funkce

Ve funkcionálních jazycích se velmi často setkáme s rekurzivními funkcemi, typicky založenými na principu postupného zjednodušování problému. Například poněkud naivní implementace funkce pro výpočet délky seznamu může být zapsána takto:

fun length(x) = if null(x) then 0
                else 1 + length(tl(x));

Podobně si můžeme nadefinovat funkci append, která vrací nový seznam vzniklý spojením dvou seznamů x a y. Tedy například:

append([1, 2], [3, 4, 5])
[1, 2, 3, 4, 5]

Na problém implementace této funkce můžeme použít princi postupného zjednodušování problému. Známe totiž dva invarianty:

append([],z) == z
append(a :: y, z) == a :: append(y,z)

Postupně tedy budeme zkracovat první seznam až dojdeme do situace, kdy je tento seznam prázdný. Přímo z těchto podmínek je možné odvodit implementaci funkce append:

fun append(x, y) = if null(x) then y
                   else hd(x) :: append(tl(x), y)
Poznámka: navíc se nám automaticky splnily všechny okrajové podmínky, tedy konkrétně situace, kdy je jeden ze seznamů prázdný.

Při zavolání:

append([1,2], [3,4,5])

dojde k postupnému vykonání fáze navíjení a odvíjení, což si můžeme naznačit graficky:

1 :: append([2], [3,4,5])
1 :: 2 :: append([], [3,4,5])
1 :: 2 :: [3,4,5]
1 :: [2,3,4,5]
[1,2,3,4,5]

Důležitý je i typ nové funkce:

val append = fn: ∀ 'a . 'a list * 'a list → 'a list;

Tento zápis nám říká, že funkce bude akceptovat dva seznamy typu „any“ a výsledkem bude další seznam typu „any“. Typ prvků seznamů sice není určen (ML ho nemá jak odvodit), ovšem je zaručeno, že oba dva vstupní seznamy budou mít stejný typ prvků, jako seznam výsledný:

append([1,2,3], [4,5,6]);
val it = [1, 2, 3, 4, 5, 6]: int list;
 
append(["foo", "bar"], ["baz"]);
val it = ["foo", "bar", "baz"]: string list;
 
append(["foo", "bar"], [4]);
Elaboration failed: Type clash. Functions of type "'a list * 'a list → 'a list" cannot take an argument of type "string list * int list": Cannot merge "int" and "string".
Poznámka: zcela přirozenou cestou jsme tak vytvořili generickou, ovšem typově bezpečnou funkci.

15. Anonymní funkce

V programovacím jazyku ML je možné deklarovat i anonymní funkce. Opět se nejedná o nic překvapivého, zvláště když si uvědomíme, kolik sémantiky (nikoli však syntaxe) bylo převzato z Lispovských jazyků. Anonymní funkce se deklaruje slovem fn a používá se zde znak šipky =>. Příkladem jednoduché anonymní funkce je funkce, která vrátí hodnotu svého parametru zvýšeného o jedničku (jedná se tedy o funkci s parametrem typu int a návratovou hodnotou typu int):

fn x => 1 + x;
 
> val it = fn: int → int;

Pochopitelně je možné vytvořit i anonymní funkce akceptující větší množství parametrů:

fn (x, y) => x + y;
 
> val it = fn: int * int → int;
Poznámka: anonymními funkcemi se budeme podrobněji zabývat ve druhé části miniseriálu o programovacím jazyku ML.

16. Pattern matching

Velmi důležitým konceptem, který byl rozvinut právě v programovacím jazyku ML, je takzvaný pattern matching neboli rozpoznávání vzorů. Ten byl později s menšími či většími úpravami převzat i do dalších programovacích jazyků. Podívejme se na praktické použití této techniky.

Obecný zápis funkce s pattern matchingem vypadá následovně:

fun <jméno> <vzorek> = <tělo/výraz>

Většinou se však používá větší množství vzorků, které jsou spojeny znakem „or“. V takovém případě jsou vzorky postupně procházeny a pokud budou vyhovovat předaným datům, bude příslušná větev funkce vykonána:

fun <jméno> <vzorek> = <tělo/výraz>
 |  <jméno> <vzorek> = <tělo/výraz>
 |  <jméno> <vzorek> = <tělo/výraz>
 |  <jméno> <vzorek> = <tělo/výraz>

O tom, jak vypadá zápis běžné funkce, jsme se dozvěděli ve třinácté kapitole. Příkladem je funkce length:

fun length(x) = if null(x) then 0
                else 1 + length(tl(x));

V této funkci se provede vždy jedna z větví na základě zapsané podmínky (case analysis). Ovšem díky existenci pattern matchingu lze stejnou funkci zapsat odlišně – a to vyjmenováním invariantů:

fun length([]) = 0
  | length(a::x) = 1 + length(x)

Tímto zápisem vlastně popisujeme, že pro prázdný seznam je délka rovna nule a pro seznam skládající se z hlavy a těla je délka tohoto seznamu rovna délce těla + 1.

Existují však i zajímavější vzorky. Například funkci car vracející hlavu seznamu (první prvek) lze zapsat opět vyjmenováním invarianty:

fun car(x::y) = x;

V tomto případě ML rozezná, že nejsou pokryty všechny možné varianty:

> val car = fn: ∀ 'a . 'a list → 'a;
 
WARN: Pattern matching is not exhaustive.
Poznámka: nejprve si povšimněte typu funkce (generická funkce, ovšem hlídající správné typy) a taktéž varování, ke kterému se hned dostaneme (a které není radno ignorovat).

To, zda tato funkce pracuje podle očekávání, si můžeme snadno ověřit:

car([1,2,3]);
> val it = 1: int;
 
car(["foo", "bar"]);
> val it = "foo": string;
 
car(["first"]);
> val it = "first": string;
 
car([]);
Uncaught SML exception: Match

Obrázek 2: Otestování funkce ve webovém prostředí.

Na posledním příkladu je patrné, že ML měl pravdu – kód funkce nepokrývá všechny okrajové podmínky. Náprava je snadná, protože stačí přidat vzorek pro prázdný seznam na vstupu:

fun car([]) = 0
  | car(x::y) = x;
> val car = fn: int list → int;
 
car([1,2,3]);
> val it = 1: int;
 
car([]);
> val it = 0: int;

Nebo ještě lépe – vyhodíme výjimku (viz navazující článek):

fun car nil = raise Empty
  | car(x::y) = x;
> val car = fn: ∀ 'a . 'a list → 'a;
 
car([1,2,3]);
> val it = 1: int;
 
car([]);
Uncaught SML exception: Empty
Poznámka: na těchto jednoduchých příkladech to sice není tak patrné, ale spojením pattern matchingu se silným typovým systémem vzniká velmi bezpečný programovací jazyk, zejména pokud programátor skutečně reaguje na všechna varování vypisovaná při analýze jeho zdrojového kódu.

17. Obsah druhé části článku

Ve druhé části článku (resp. celého miniseriálu) o programovacím jazyku ML se zaměříme především na podrobnější popis typového systému tohoto jazyka a taktéž na složitější funkce, které používají pattern matching.

18. Repositář s demonstračními příklady

Všechny výše popsané demonstrační příklady byly uloženy do repositáře dostupného na adrese https://github.com/tisnik/ml-examples/. V tabulce umístěné pod tímto odstavcem jsou uvedeny odkazy na tyto příklady:

# Příklad Popis příkladu Cesta
1 01_simple_comments.ml jednořádkový komentář https://github.com/tisnik/ml-examples/tree/master/arti­cle01/01_simple_comments.ml
2 02_block_comment.ml víceřádkový (blokový) komentář https://github.com/tisnik/ml-examples/tree/master/arti­cle01/02_block_comment.ml
3 03_nested_comments.ml vnořené komentáře https://github.com/tisnik/ml-examples/tree/master/arti­cle01/03_nested_comments.ml
4 04_expressions.ml jednoduché výrazy https://github.com/tisnik/ml-examples/tree/master/arti­cle01/04_expressions.ml
5 05_function_call.ml volání funkce https://github.com/tisnik/ml-examples/tree/master/arti­cle01/05_function_call.ml
6 06_function_call_wo_parenthesis.ml volání funkce s jedním parametrem bez použití závorek https://github.com/tisnik/ml-examples/tree/master/arti­cle01/06_function_call_wo_pa­renthesis.ml
7 07_function_call_wo_parenthesis.ml problematický rys zkráceného volání funkce https://github.com/tisnik/ml-examples/tree/master/arti­cle01/07_function_call_wo_pa­renthesis.ml
8 08_variables.ml proměnné https://github.com/tisnik/ml-examples/tree/master/arti­cle01/08_variables.ml
9 09_variables_from_expressions.ml proměnné inicializované vyhodnocením složitějšího výrazu https://github.com/tisnik/ml-examples/tree/master/arti­cle01/09_variables_from_ex­pressions.ml
10 10_elementary_data_types.ml základní datové typy jazyka ML https://github.com/tisnik/ml-examples/tree/master/arti­cle01/10_elementary_data_ty­pes.ml
11 11_tuples.ml n-tice https://github.com/tisnik/ml-examples/tree/master/arti­cle01/11_tuples.ml
12 12_records.ml záznamy https://github.com/tisnik/ml-examples/tree/master/arti­cle01/12_records.ml
13 13_empty_list.ml zápis prázdného seznamu https://github.com/tisnik/ml-examples/tree/master/arti­cle01/13_empty_list.ml
14 14_list.ml seznamy https://github.com/tisnik/ml-examples/tree/master/arti­cle01/14_list.ml
15 15_function.ml deklarace funkce https://github.com/tisnik/ml-examples/tree/master/arti­cle01/15_function.ml
16 16_add.ml funkce se dvěma parametry https://github.com/tisnik/ml-examples/tree/master/arti­cle01/16_add.ml
17 17_composition.ml pokus o kompozici funkcí https://github.com/tisnik/ml-examples/tree/master/arti­cle01/17_composition.ml
18 18_length_function.ml definice funkce length https://github.com/tisnik/ml-examples/tree/master/arti­cle01/18_length_function.ml
19 19_append_function.ml definice funkce append https://github.com/tisnik/ml-examples/tree/master/arti­cle01/19_append_function.ml
20 20_reverse_function.ml definice funkce reverse https://github.com/tisnik/ml-examples/tree/master/arti­cle01/20_reverse_function­.ml

19. Literatura

Poznámka: v této kapitole jsou uvedeny nejenom knihy o jazyku ML, resp. Standard ML, ale i knihy o programovacím jazyku OCaml, který ze Standard ML ze značné míry vychází.
  1. ML for the Working Programmer
    https://www.cl.cam.ac.uk/~lp15/MLbo­ok/pub-details.html
  2. Elements of ML Programming, 2nd Edition (ML97)
    http://infolab.stanford.e­du/~ullman/emlp.html
  3. A tour of Standard ML
    https://saityi.github.io/sml-tour/tour/welcome
  4. The History of Standard ML
    https://smlfamily.github.i­o/history/SML-history.pdf
  5. The Standard ML Basis Library
    https://smlfamily.github.io/Basis/
  6. Programming in Standard ML
    http://www.cs.cmu.edu/~rwh/is­ml/book.pdf
  7. Programming in Standard ML '97: A Tutorial Introduction
    http://www.lfcs.inf.ed.ac­.uk/reports/97/ECS-LFCS-97–364/
  8. Programming in Standard ML '97: An On-line Tutorial
    https://homepages.inf.ed.ac­.uk/stg/NOTES/
  9. The OCaml system release 4.13
    https://ocaml.org/releases/4­.13/htmlman/index.html
  10. Real World OCaml: Functional programming for the masses
    https://dev.realworldocaml.org/
  11. OCaml from the Very Beginning
    http://ocaml-book.com/
  12. OCaml from the Very Beginning: More OCaml : Algorithms, Methods & Diversions
    http://ocaml-book.com/more-ocaml-algorithms-methods-diversions/
  13. Unix system programming in OCaml
    http://ocaml.github.io/ocamlunix/
  14. OCaml for Scientists
    https://www.ffconsultancy­.com/products/ocaml_for_sci­entists/index.html
  15. Using, Understanding, and Unraveling The OCaml Language
    https://caml.inria.fr/pub/docs/u3-ocaml/
  16. Developing Applications With objective Caml
    https://caml.inria.fr/pub/docs/oreilly-book/index.html
  17. Introduction to Objective Caml
    http://courses.cms.caltech­.edu/cs134/cs134b/book.pdf
  18. How to Think Like a (Functional) Programmer
    https://greenteapress.com/thin­kocaml/index.html

20. Odkazy na Internetu

  1. Standard ML of New Jersey
    https://www.smlnj.org/
  2. Programming Languages: Standard ML – 1 (a navazující videa)
    https://www.youtube.com/wat­ch?v=2sqjUWGGzTo
  3. 6 Excellent Free Books to Learn Standard ML
    https://www.linuxlinks.com/excellent-free-books-learn-standard-ml/
  4. SOSML: The Online Interpreter for Standard ML
    https://sosml.org/
  5. ML (Computer program language)
    https://www.barnesandnoble­.com/b/books/other-programming-languages/ml-computer-program-language/_/N-29Z8q8Zvy7
  6. Strong Typing
    https://perl.plover.com/y­ak/typing/notes.html
  7. What to know before debating type systems
    http://blogs.perl.org/user­s/ovid/2010/08/what-to-know-before-debating-type-systems.html
  8. Types, and Why You Should Care (Youtube)
    https://www.youtube.com/wat­ch?v=0arFPIQatCU
  9. DynamicTyping (Martin Fowler)
    https://www.martinfowler.com/bli­ki/DynamicTyping.html
  10. DomainSpecificLanguage (Martin Fowler)
    https://www.martinfowler.com/bli­ki/DomainSpecificLanguage­.html
  11. Language Workbenches: The Killer-App for Domain Specific Languages?
    https://www.martinfowler.com/ar­ticles/languageWorkbench.html
  12. Effective ML (Youtube)
    https://www.youtube.com/watch?v=-J8YyfrSwTk
  13. Why OCaml (Youtube)
    https://www.youtube.com/wat­ch?v=v1CmGbOGb2I
  14. CSE 341: Functions and patterns
    https://courses.cs.washin­gton.edu/courses/cse341/04wi/lec­tures/03-ml-functions.html
  15. Comparing Objective Caml and Standard ML
    http://adam.chlipala.net/mlcomp/
  16. What are the key differences between Standard ML and OCaml?
    https://www.quora.com/What-are-the-key-differences-between-Standard-ML-and-OCaml?share=1
  17. Cheat Sheets (pro OCaml)
    https://www.ocaml.org/doc­s/cheat_sheets.html
  18. Syllabus (FAS CS51)
    https://cs51.io/college/syllabus/
  19. Abstraction and Design In Computation
    http://book.cs51.io/
  20. Learn X in Y minutes Where X=Standard ML
    https://learnxinyminutes.com/doc­s/standard-ml/
  21. CSE307 Online – Summer 2018: Principles of Programing Languages course
    https://www3.cs.stonybrook­.edu/~pfodor/courses/summer/cse307­.html
  22. CSE307 Principles of Programming Languages course: SML part 1
    https://www.youtube.com/wat­ch?v=p1n0_PsM6hw
  23. CSE 307 – Principles of Programming Languages – SML
    https://www3.cs.stonybrook­.edu/~pfodor/courses/summer/CSE307/L01_SML­.pdf
  24. SML, Some Basic Examples
    https://cs.fit.edu/~ryan/sml/in­tro.html
  25. History of programming languages
    https://devskiller.com/history-of-programming-languages/
  26. History of programming languages (Wikipedia)
    https://en.wikipedia.org/wi­ki/History_of_programming_lan­guages
  27. Jemný úvod do rozsáhlého světa jazyků LISP a Scheme
    https://www.root.cz/clanky/jemny-uvod-do-rozsahleho-sveta-jazyku-lisp-a-scheme/
  28. The Evolution Of Programming Languages
    https://www.i-programmer.info/news/98-languages/8809-the-evolution-of-programming-languages.html
  29. Evoluce programovacích jazyků
    https://ccrma.stanford.edu/cou­rses/250a-fall-2005/docs/ComputerLanguagesChart.png
  30. Poly/ML Homepage
    https://polyml.org/
  31. PolyConf 16: A brief history of F# / Rachel Reese
    https://www.youtube.com/wat­ch?v=cbDjpi727aY

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.