Obsah
1. ML – funkcionální jazyk s revolučním typovým systémem
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ů
10. Základní datové typy jazyka ML
11. Složené datové typy: n-tice a záznamy
18. Repositář s demonstračními příklady
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.
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ů.
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.
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í).
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.
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
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]
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
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) *)
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
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
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.
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
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
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;
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);
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)
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".
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;
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.
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
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:
19. Literatura
- ML for the Working Programmer
https://www.cl.cam.ac.uk/~lp15/MLbook/pub-details.html - Elements of ML Programming, 2nd Edition (ML97)
http://infolab.stanford.edu/~ullman/emlp.html - A tour of Standard ML
https://saityi.github.io/sml-tour/tour/welcome - The History of Standard ML
https://smlfamily.github.io/history/SML-history.pdf - The Standard ML Basis Library
https://smlfamily.github.io/Basis/ - Programming in Standard ML
http://www.cs.cmu.edu/~rwh/isml/book.pdf - Programming in Standard ML '97: A Tutorial Introduction
http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97–364/ - Programming in Standard ML '97: An On-line Tutorial
https://homepages.inf.ed.ac.uk/stg/NOTES/ - The OCaml system release 4.13
https://ocaml.org/releases/4.13/htmlman/index.html - Real World OCaml: Functional programming for the masses
https://dev.realworldocaml.org/ - OCaml from the Very Beginning
http://ocaml-book.com/ - OCaml from the Very Beginning: More OCaml : Algorithms, Methods & Diversions
http://ocaml-book.com/more-ocaml-algorithms-methods-diversions/ - Unix system programming in OCaml
http://ocaml.github.io/ocamlunix/ - OCaml for Scientists
https://www.ffconsultancy.com/products/ocaml_for_scientists/index.html - Using, Understanding, and Unraveling The OCaml Language
https://caml.inria.fr/pub/docs/u3-ocaml/ - Developing Applications With objective Caml
https://caml.inria.fr/pub/docs/oreilly-book/index.html - Introduction to Objective Caml
http://courses.cms.caltech.edu/cs134/cs134b/book.pdf - How to Think Like a (Functional) Programmer
https://greenteapress.com/thinkocaml/index.html
20. Odkazy na Internetu
- Standard ML of New Jersey
https://www.smlnj.org/ - Programming Languages: Standard ML – 1 (a navazující videa)
https://www.youtube.com/watch?v=2sqjUWGGzTo - 6 Excellent Free Books to Learn Standard ML
https://www.linuxlinks.com/excellent-free-books-learn-standard-ml/ - SOSML: The Online Interpreter for Standard ML
https://sosml.org/ - ML (Computer program language)
https://www.barnesandnoble.com/b/books/other-programming-languages/ml-computer-program-language/_/N-29Z8q8Zvy7 - Strong Typing
https://perl.plover.com/yak/typing/notes.html - What to know before debating type systems
http://blogs.perl.org/users/ovid/2010/08/what-to-know-before-debating-type-systems.html - Types, and Why You Should Care (Youtube)
https://www.youtube.com/watch?v=0arFPIQatCU - DynamicTyping (Martin Fowler)
https://www.martinfowler.com/bliki/DynamicTyping.html - DomainSpecificLanguage (Martin Fowler)
https://www.martinfowler.com/bliki/DomainSpecificLanguage.html - Language Workbenches: The Killer-App for Domain Specific Languages?
https://www.martinfowler.com/articles/languageWorkbench.html - Effective ML (Youtube)
https://www.youtube.com/watch?v=-J8YyfrSwTk - Why OCaml (Youtube)
https://www.youtube.com/watch?v=v1CmGbOGb2I - CSE 341: Functions and patterns
https://courses.cs.washington.edu/courses/cse341/04wi/lectures/03-ml-functions.html - Comparing Objective Caml and Standard ML
http://adam.chlipala.net/mlcomp/ - 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 - Cheat Sheets (pro OCaml)
https://www.ocaml.org/docs/cheat_sheets.html - Syllabus (FAS CS51)
https://cs51.io/college/syllabus/ - Abstraction and Design In Computation
http://book.cs51.io/ - Learn X in Y minutes Where X=Standard ML
https://learnxinyminutes.com/docs/standard-ml/ - CSE307 Online – Summer 2018: Principles of Programing Languages course
https://www3.cs.stonybrook.edu/~pfodor/courses/summer/cse307.html - CSE307 Principles of Programming Languages course: SML part 1
https://www.youtube.com/watch?v=p1n0_PsM6hw - CSE 307 – Principles of Programming Languages – SML
https://www3.cs.stonybrook.edu/~pfodor/courses/summer/CSE307/L01_SML.pdf - SML, Some Basic Examples
https://cs.fit.edu/~ryan/sml/intro.html - History of programming languages
https://devskiller.com/history-of-programming-languages/ - History of programming languages (Wikipedia)
https://en.wikipedia.org/wiki/History_of_programming_languages - 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/ - The Evolution Of Programming Languages
https://www.i-programmer.info/news/98-languages/8809-the-evolution-of-programming-languages.html - Evoluce programovacích jazyků
https://ccrma.stanford.edu/courses/250a-fall-2005/docs/ComputerLanguagesChart.png - Poly/ML Homepage
https://polyml.org/ - PolyConf 16: A brief history of F# / Rachel Reese
https://www.youtube.com/watch?v=cbDjpi727aY
ČLÁNKY DO MAILU