LunarML: definice a volání různých variant funkcí

Ve všech funkcionálních programovacích jazycích mají funkce stejně plnohodnotný význam, jako jakékoli jiné datové typy. Výjimkou z tohoto pravidla není ani jazyk Standard ML, ve kterém může být typ funkce automaticky odvozen od typů parametrů a návratové hodnoty (opět se zde tedy setkáváme s typovou inferencí). Funkce je v tomto jazyku definována klíčovým slovem fun:

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

Pro zajímavost si připomeňme, 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, v nichž funkce tvoří vlastní kategorii objektů a nejedná se o běžné hodnoty; ostatně pro definici funkce v céčku neexistuje žádné klíčové slovo):

Ukažme si definici nové funkce v jazyku Standard ML, která po svém zavolání zvýší obsah svého parametru o jedničku a vrátí vypočtený výsledek jako novou hodnotu. Funkce se bude jmenovat inc a její parametr bude mít jméno 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 překladač či interpret programovacího jazyka Standard ML zjistil, že se jedná o funkci int → int (čteme: parametr je celé číslo a výsledkem je taktéž celé číslo). Přitom se vychází z těla funkce, tedy z výrazu n+1, což je v jazyku ML i Standard ML striktně součet dvou celých čísel.

Zavolání takové funkce je jednoduché:

int 10;

Pozor si musíte dát především na to, že se používá levá asociativita, což u funkcí volaných bez kulatých závorek povede (resp. může vést) 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 na takzvané kompozici funkcí:

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

První volání je v pořádku (vrátí se trojka), ovšem druhé volání již nikoli:

Elaboration failed: Type clash. Functions of type "int → int" cannot take an
argument of type "int → int": Cannot merge "int" and "int → int".

Definici a zavolání funkce se dvěma parametry jsme si již ukázali v předchozím článku:

(* Definice funkce *)
 
fun add (x, y) = x + y;
 
add(3,4);

V programovacím jazyku Standard 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 klíčovým slovem fn a používá se zde znak šipky =>, nikoli pouze přiřazení =. Příkladem jednoduché anonymní funkce je (opět) 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ů. Zápis bude v tomto případě vypadat následovně:

fn (x, y) => x + y;
 
> val it = fn: int * int → int;

Nyní se podívejme, jak vypadá překlad (resp. transpřeklad) anonymních funkcí v praxi. Necháme si přeložit deklaraci a volání anonymní funkce, která vrátí hodnotu svého parametru zvětšeného o jedničku:

(* Anonymní funkce *)
val result = (fn x => x+1)1;
 
print(Int.toString (result));
print "\n";

LunarML při překladu aplikuje optimalizace, takže ve výsledném kódu uvidíme jen tisk trojky:

local result = gsub(tostring(2), "-", "~")
outputAndFlush(stdOut, result)
outputAndFlush(stdOut, "\n")

Dtto pro JavaScript:

 const tmp13 = 2 .toString();
 const a = _encodeUtf8(tmp13);
 outputAndFlush(stdOut[0], a);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
}

Příklad tedy musíme zkomplikovat, aby se optimalizace nemohly provádět. Například výpočtem parametru ve složitější funkci:

(* Naivní implementace výpočtu Fibonacciho posloupnosti *)
 
fun fib n =
    if n = 0 then 0 else
    if n = 1 then 1 else
    fib (n - 1) + fib (n - 2);
 
 
(* Anonymní funkce *)
val result = (fn x => x+1) (fib 10);
 
print(Int.toString (result));
print "\n";

Výsledek překladu do jazyka Lua:

local function fib(n)
  if n == 0 then
    return 0
  elseif n == 1 then
    return 1
  end
  local tmp = fib(_Int_sub(n, 1))
  local tmp1 = fib(_Int_sub(n, 2))
  return _Int_add(tmp, tmp1)
end
local tmp = fib(10)
local result = _Int_add(tmp, 1)
local result1 = gsub(tostring(result), "-", "~")
outputAndFlush(stdOut, result1)
outputAndFlush(stdOut, "\n")

V JavaScriptu je to podobné:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp15 = fib(_Int54_sub(n, 1));
   const tmp16 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp15, tmp16);
  }
 };
 const tmp13 = fib(10);
 const result = _Int54_add(tmp13, 1);

Dalším příkladem je anonymní funkce se dvěma parametry:

(* Anonymní funkce *)
val result = (fn (x, y) => x+y) (1, 2);
 
print(Int.toString (result));
print "\n";

Ve výsledku transpřekladu můžeme opět vidět aplikaci optimalizací. Jazyk Lua:

local result = gsub(tostring(3), "-", "~")
outputAndFlush(stdOut, result)
outputAndFlush(stdOut, "\n")

A JavaScript:

 const tmp13 = 3 .toString();
 const a = _encodeUtf8(tmp13);
 outputAndFlush(stdOut[0], a);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
}

Použijeme podobný trik s komplikovanějším výpočtem parametrů funkce:

(* Naivní implementace výpočtu Fibonacciho posloupnosti *)
 
fun fib n =
    if n = 0 then 0 else
    if n = 1 then 1 else
    fib (n - 1) + fib (n - 2);
 
 
(* Anonymní funkce *)
val result = (fn (x, y) => x+y) (fib 1, fib 2);
 
print(Int.toString (result));
print "\n";

Výsledek transpřekladu:

local function fib(n)
  if n == 0 then
    return 0
  elseif n == 1 then
    return 1
  end
  local tmp = fib(_Int_sub(n, 1))
  local tmp1 = fib(_Int_sub(n, 2))
  return _Int_add(tmp, tmp1)
end
local tmp = fib(1)
local tmp1 = fib(2)
local result = _Int_add(tmp, tmp1)
local result1 = gsub(tostring(result), "-", "~")
outputAndFlush(stdOut, result1)
outputAndFlush(stdOut, "\n")

Dtto, ale pro JavaScript:

 let fib;
 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp16 = fib(_Int54_sub(n, 1));
   const tmp17 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp16, tmp17);
  }
 };
 const tmp13 = fib(1);
 const tmp14 = fib(2);
 const result = _Int54_add(tmp13, tmp14);

Přímá a nepřímá rekurze

Rekurze, neboli volání nějaké funkce v těle té samé funkce (přímá rekurze) nebo prostřednictvím funkce jiné (takzvaná nepřímá rekurze), představuje jednu ze základních programátorských technik, na kterých je programovací jazyk Standard ML postaven, podobně jako další funkcionální jazyky. Můžeme zde opět spatřovat velkou inspiraci Lispem, ve kterém se rekurze také velmi často používá; ostatně samotné Lispovské příkazy, například apply, map či forall jsou definovány rekurzivně, podobně jako v dalším Lispovsky orientovaném jazyce – ve Scheme. Samotná myšlenka rekurze je však starší než všechny programovací jazyky, protože je hluboce zakořeněna jak v podstatě některých přírodních i umělých jevů či objektů, tak i v matematice, v například v definicích různých algebraických a geometrických struktur.

Definice přímé rekurzivní funkce je v jazyce Standard ML zcela bezproblémová – nejsou zapotřebí žádné dopředné („forward“) deklarace atd. A pochopitelně jsou stále odvozovány popř. hlídány datové typy předávaných parametrů i návratových hodnot:

(* Naivní implementace funkce length *)
 
fun length(x) = if null(x) then 0
                else 1 + length(tl(x));

Typ této funkce je zajímavý – funkce length, kterou jsme právě definovali, totiž bude akceptovat seznam libovolného typu, tj. jedná se o generickou funkci ('a zde značí „any“, i když ve skutečnosti se jedná o zápis znaku alfa):

val length = fn: ∀ 'a . 'a list → int;

Otestování, zda je tato funkce definována korektně, je v praxi snadné. Nejjednodušší je využití online REPLu jazyka Standard ML (SOSML):

length([]);
> val it = 0: int;
 
length([1]);
> val it = 1: int;
 
length([1,2,3,4]);
> val it = 4: int;

(* Funkce accumulate s tail rekurzí *)
 
fun accumulate ([], a) = a
  | accumulate ((_::tail), a) = accumulate(tail, (1 + a));
 
 
(* Funkce pro výpočet délky seznamu *)
fun length lst = accumulate(lst, 0);
 
print(Int.toString(length []));
print "\n";
 
print(Int.toString(length [1, 2, 3]));
print "\n";
 
(* Je možné vypočítat délku seznamu libovolného typu *)
print(Int.toString(length ["foo", "bar", "baz"]));
print "\n";

Automaticky odvozené typy obou funkcí ukazují, že se stále jedná o generické funkce:

val accumulate = fn: ∀ α . α list * int → int;
 
val length = fn: ∀ α . α list → int;

Překlad do jazyka Lua používá příkaz goto a je nerekurzivní (takže rychlý):

  local accumulate = function(_1, a)
    local tmp1, tmp2 = _1, a
    ::cont::
    local _1_1, a1 = tmp1, tmp2
    if _1_1 == nil then
      return a1
    elseif _1_1 ~= nil then
      local tmp3 = _1_1[2]
      tmp1 = tmp3
      tmp2 = _Int_add(1, a1)
      goto cont
    else
      _raise(_Match, "accumulate.sml:3:5")
    end
  end

Překlad do JavaScriptu ukazuje použití programové smyčky:

 const accumulate = function(_1, a) {
  let tmp19 = _1, tmp20 = a;
  for (;;) {
   const _1$1 = tmp19, a1 = tmp20;
   if (_1$1 === null) {
    return a1;
   } else if (! (_1$1 === null)) {
    const tmp21 = _1$1[1];
    [tmp19, tmp20] = [tmp21, _Int54_add(1, a1)];
   } else {
    throw _Match;
   }
  }
 };

Rekurzivní funkce odd i even

V programovacích jazycích OCaml a F# se rekurzivní funkce definují s využitím dvojice klíčových slov let rec, takže je na první pohled patrné, o jaký typ funkce se jedná. V případě jazyka Standard ML, kterému se věnujeme dnes, se klíčové slovo rec nepoužívá, takže se definice běžné funkce vlastně neliší od funkce rekurzivní. Musíme však řešit jiný problém (to ovšem v OCamlu a F# taktéž), a to konkrétně problém vzájemné rekurze, tj. situace, v níž funkce X volá jinou funkci Y a ta zase volá funkci X (popř. je do celého cyklu zavedeno více funkcí). Standard ML provádí plnou typovou kontrolu a navíc i typovou inferenci, takže nemůžeme prostě zapsat:

(* Vzájemná rekurze *)
 
fun is_even(0) = true
  | is_even n = is_odd(n-1);
 
fun is_odd(0) = false
  | is_odd n = is_even(n-1);

V tomto případě překladač při zpracování funkce is_even ještě nezná typové informace o funkci is_odd (vlastně o její existenci vůbec neví), takže vypíše chybové hlášení:

Elaboration failed: Unbound value identifier "is_odd".

Popř. v případě LunarML:

/work/mutual_recursion_.sml:4:18-4:23: error: unknown value name is_odd
  | is_even(n) = is_odd(n-1);
                 ^~~~~~

Jediný korektní způsob zápisu vzájemné nepřímé rekurze vyžaduje společnou deklaraci obou funkcí, které se vzájemně volají. Obě deklarace se spojují – což může být zpočátku poněkud matoucí – s využitím klíčového slova and.Výsledek by měl vypadat následovně:

(* Vzájemná rekurze *)
 
fun is_even 0 = true
  | is_even n = is_odd(n-1)
and is_odd 0 = false
  | is_odd n = is_even(n-1);

Otestujme si tedy překlad následujícího kódu, který dvojici funkcí is_even a is_odd otestuje:

(* Vzájemná rekurze *)
 
fun is_even 0 = true
  | is_even n = is_odd(n-1)
and is_odd 0 = false
  | is_odd n = is_even(n-1);
 
 
fun bool_to_string true  = "true"
  | bool_to_string false = "false";
 
 
fun print_bool b = print (bool_to_string b ^ "\n");
 
print_bool(is_even(42));
print "\n";
 
print_bool(is_even(43));
print "\n";

Překlad do jazyka Lua je přímočarý, protože interpret Luy musí pouze znát jména funkcí:

local is_even, is_odd
is_even = function(n)
  if n == 0 then
    return true
  else
    return is_odd(_Int_sub(n, 1))
  end
end
is_odd = function(n)
  if n == 0 then
    return false
  else
    return is_even(_Int_sub(n, 1))
  end
end
local tmp = is_even(42)
do
  local tmp1
  if tmp then
    tmp1 = "true"
  elseif not tmp then
    tmp1 = "false"
  else
    _raise(_Match, "mutual_recursion.sml:9:5")
  end
  outputAndFlush(stdOut, tmp1 .. "\n")
end
outputAndFlush(stdOut, "\n")
local tmp1 = is_even(43)
do
  local tmp2
  if tmp1 then
    tmp2 = "true"
  elseif not tmp1 then
    tmp2 = "false"
  else
    _raise(_Match, "mutual_recursion.sml:9:5")
  end
  outputAndFlush(stdOut, tmp2 .. "\n")
end
outputAndFlush(stdOut, "\n")

V JavaScriptu je situace zajímavější, protože se zde funkce is_even i is_odd obalují do funkce _wrap:

 is_even = _wrap(function(n) {
  if (n === 0) {
   return [true, true];
  } else {
   return [false, is_odd, [_Int54_sub(n, 1)]];
  }
 });
 is_odd = _wrap(function(n) {
  if (n === 0) {
   return [true, false];
  } else {
   return [false, is_even, [_Int54_sub(n, 1)]];
  }
 });
 const tmp13 = is_even(42);
 {
  let tmp15;
  if (tmp13) {
   tmp15 = Uint8Array.of(116, 114, 117, 101);
  } else if (! tmp13) {
   tmp15 = Uint8Array.of(102, 97, 108, 115, 101);
  } else {
   throw _Match;
  }
  const tmp16 = _String_append(tmp15, Uint8Array.of(10));
  outputAndFlush(stdOut[0], tmp16);
 }
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp14 = is_even(43);
 {
  let tmp15;
  if (tmp14) {
   tmp15 = Uint8Array.of(116, 114, 117, 101);
  } else if (! tmp14) {
   tmp15 = Uint8Array.of(102, 97, 108, 115, 101);
  } else {
   throw _Match;
  }
  const tmp16 = _String_append(tmp15, Uint8Array.of(10));
  outputAndFlush(stdOut[0], tmp16);
 }
 outputAndFlush(stdOut[0], Uint8Array.of(10));
}

Samotný wrapper si podrobně popíšeme příště:

function _wrap(f) {
    const F = function() {
        let result = f.apply(undefined, arguments); // [true, Result] | exists X. [false, MLFunction<Result, X>, X]
        while (!result[0]) {
            const g = result[1];
            if ("_MLTAIL_" in g) {
                result = g._MLTAIL_.apply(undefined, result[2]);
            } else {
                return g.apply(undefined, result[2]);
            }
        }
        return result[1];
    }
    F._MLTAIL_ = f;
    return F;
}

Funkce vyššího řádu

Již v úvodní kapitole jsme si řekli, že ve funkcionálních programovacích jazycích mají funkce stejně plnohodnotný význam, jako jakékoli jiné datové typy. Výjimkou není, jak již ostatně víme, ani programovací jazyk Standard ML, v němž je typ funkce odvozen od typů parametrů a návratové hodnoty. Pokud je ovšem typ funkce plnohodnotným datovým typem, nutně to znamená, že samotná funkce (tedy hodnota) může být předána jako parametr do jiné funkce popř. vrácena jako návratová hodnota (jiné) funkce. Funkcím, které jako svůj parametr akceptují jinou funkci popř. které vrací funkci, se říká funkce vyššího řádu. Takové funkce jsou v jazyku Standard ML plně podporovány a nalezneme je i ve standardní knihovně tohoto jazyka. Podívejme se na asi nejtypičtější prakticky použitelnou funkci vyššího řádu. Jedná se o funkci map, která aplikuje (jinou) funkci na jednotlivé prvky seznamu, přičemž výsledkem bude nový seznam. Funkci map lze realizovat rekurzivně:

(* Implementace funkce map *)
 
fun map f [] = []
  | map f (head::tail) = (f head) :: (map f tail);

V případě, že ve vstupním seznamu existuje alespoň jeden prvek (head), je na něj aplikována funkce f předaná jako parametr a rekurzivně se zavolá map pro zbytek seznamu. Zajímavý je typ funkce map získaný automatickým odvozením:

val map = fn: ∀ 'a 'b . ('a → 'b) → 'a list → 'b list;

Pokusíme se o zjištění způsobu (trans)překladu tohoto zdrojového kódu:

(* Implementace funkce map *)
 
fun map f [] = []
  | map f (head::tail) = (f head) :: (map f tail);
 
fun inc x = x + 1;
 
map inc [1,2,3];

Výsledek v jazyce Lua je poněkud zdlouhavý, protože je nutné simulovat seznamy:

local function map(f)
  return function(a)
    if a == nil then
      return nil
    elseif a ~= nil then
      local tmp = a[1]
      local tmp1 = a[2]
      local tmp2 = f(tmp)
      local tmp3 = map(f)
      local tmp4 = tmp3(tmp1)
      return {tmp2, tmp4}
    else
      _raise(_Match, "map.sml:3:5")
    end
  end
end
local tmp = map(function(x)
  return _Int_add(x, 1)
end)
tmp({1, {2, {3, nil}}})

Výsledek v JavaScriptu:

 let map;
 map = function(f) {
  return function(a) {
   if (a === null) {
    return null;
   } else if (! (a === null)) {
    const tmp1 = a[0];
    const tmp2 = a[1];
    const tmp3 = f(tmp1);
    const tmp4 = map(f);
    const tmp5 = tmp4(tmp2);
    return [tmp3, tmp5];
   } else {
    throw _Match;
   }
  };
 };
 const tmp = map(function(x) {
  return _Int54_add(x, 1);
 });
 tmp(_list([1, 2, 3]));

Curryfikace (currying) a částečně vyhodnocené funkce

„Typically, developers learn new languages by applying what they know about existing languages. But learning a new paradigm is difficult – you must learn to see different solutions to familiar problems.“

V další části dnešního článku si ukážeme, jakým způsobem se v programovacím jazyku Standard ML provádí takzvaná curryfikace (anglicky currying). Pod tímto termínem se v teorii programovacích jazyků (ovšem i obecně v matematice) označuje proces, jímž se transformuje funkce, která má více než jeden parametr, do řady vložených funkcí, přičemž každá z nich má jen jediný parametr. Curryfikaci si můžeme představit jako postupnou transformaci funkce s n parametry na jinak zkonstruovanou funkci s n-1 parametry atd. až rekurzivně dojdeme k funkci s jediným parametrem:

x = f(a,b,c) →
    h = g(a)
    i = h(b)
    x = i(c)

Nebo na jediném řádku:

x = f(a,b,c) → g(a)(b)(c)

To zní sice velmi složitě, ale v praxi je (ve Standard ML, ale i v mnoha dalších programovacích jazycích) proces curryfikace realizován, jak uvidíme v dalším textu, z pohledu programátora automaticky již samotným zápisem funkce s větším množstvím parametrů. To nám umožňuje realizovat částečné vyhodnocení funkce (partial application), konkrétně zavoláním nějaké funkce (například funkce akceptující dva parametry) ve skutečnosti pouze s jediným parametrem.

Jenže vyvstává zde otázka, co má být výsledkem volání takové funkce? Určitě ne výsledek implementované operace, protože nám chybí jeden parametr pro to, aby byl výsledek vypočten a vrácen volajícím kódu. Ovšem můžeme provést částečný výpočet dosazením (jediného) předaného parametru a výsledek – tento částečný výpočet – vrátit. Výsledkem je tedy obecně částečně aplikovaná funkce (tedy například funkce, které byly v předchozím příkladu označeny symboly g a h). Jedná se o jeden ze způsobů, jak programově (za běhu aplikace) vytvářet nové funkce.

Jak tedy vlastně vypadá typ funkce se třemi parametry typu int?

fun add3 x y z = x+y+z;

SOSML vrátí tento řádek, ze kterého je (pokud se naučíte tyto typové informace rozluštit) zřejmé, že se jedná o funkci s jedním parametrem typu int vracející funkci akceptující taktéž parametr typu int vracející funkci opět s dalším parametrem typu int, jejímž výsledkem je výsledný int:

val add3 = fn: int → int → int → int;

Funkce přistupující k symbolům ve svém prostředí (environment)

Zkusme si ukázat, jak je currying interně implementován. Nejprve si ovšem řekneme, že v programovacím jazyku Standard ML je možné vytvářet funkce (ať již anonymní či pojmenované), které budou akceptovat nějaké parametry, ovšem navíc budou přistupovat k „externím“ proměnným dostupným z jejich prostředí (environment). Začneme jednoduchou anonymní funkcí, která akceptuje jediný parametr b, ovšem provádí výpočet a+b, jehož výsledek posléze vrací:

fn b => a + b;

Tuto funkci nelze zpracovat bez toho, aniž by byla v prostředí (environment, viz dále) deklarována proměnná a, na což nás překladač správně upozorní:

Elaboration failed: Unbound value identifier "a".

Proměnnou a však můžeme vytvořit, a to konstrukcí val. V takovém případě je již možné anonymní funkci zapsat, a to bez nahlášení chyby překladačem:

val a = 10;
 
fn b => a + b;

Výsledkem bude hodnota s typem:

val it = fn: int → int;

Po vyhodnocení výrazu jsme sice získali hodnotu typu funkce, ovšem tato hodnota byla pouze meziuložena do speciální proměnné it a bude brzy ztracena vyhodnocením jakéhokoli dalšího výrazu:

it(100);
val it = 110: int;

Nic nám však nebrání si výsledek, tedy funkci, uložit do proměnné, a de facto tak deklarovat pojmenovanou funkci:

val a = 10;
 
val f = fn b => a + b;

Výsledkem je nyní proměnná f s typem:

val f = fn: int → int;

Z tohoto zápisu již víme, že se jedná o funkci s jediným parametrem, kterou lze zavolat:

f(20);
val it = 30: int;

Popř. můžeme vytvořit anonymní funkci a ihned ji zavolat, to vše na jediném řádku:

val a = 10;
 
(fn b => a + b)(20);
val it = 30: int;

Nyní již víme, že funkce mohou využívat hodnoty proměnných, které jsou dostupné z jejich prostředí. Co to konkrétně znamená, se dozvíme později, ale v jednoduchosti se jedná o proměnné s hodnotou a typem známým v době tvorby funkce (může se jednat o globální proměnné, parametry funkce, v jejím rámci je nová funkce definována atd.).

Praktické využití curryfikace

Podívejme se nyní na následující definici funkce adder:

fun adder a = fn b => a + b;
val adder = fn: int → int → int;

Tato funkce je poměrně zajímavá, protože její návratovou hodnotou je další funkce s jediným parametrem b, která provádí výpočet a+b (viz návratový typ fn: int → int → int odvozený a následně i zobrazený překladačem).

Samotná funkce adder je tedy generátorem dalších funkcí, které se budou lišit tím, jaký výsledek počítají, a to na základě parametru a, jenž byl do funkce adder předán ve chvíli generování nových funkcí. Pokusme se takové funkce vytvořit (vygenerovat):

val inc1 = adder 1;
val inc2 = adder 2;

V předchozím příkladu jsme si nechali vygenerovat dvojici nových funkcí nazvaných inc1 a inc2, jejichž typy odvozené překladačem jsou:

val inc1 = fn: int → int;
val inc2 = fn: int → int;

Jedná se tedy o „běžné“ funkce s jediným parametrem (a pochopitelně i návratovou hodnotou), které lze běžným způsobem zavolat. Použijeme zde interaktivní REPL SOSML:

inc1 10;
val it = 11: int;
 
inc2 10;
val it = 12: int;

Můžeme zde vidět, že každá z těchto funkcí provedla odlišný výpočet, a to z toho důvodu, že si každá funkce pamatuje odlišnou hodnotu a získanou při vytvoření těchto funkcí (ovšem hraje zde roli původní funkce adder). Stále však platí, že se jedná o referenčně transparentní funkce – jejich návratové hodnoty plně závisí pouze na předaném parametru, což mj. umožňuje optimalizace prováděné transpřekladačem LunarML.

To však není vše a právě zde se dostáváme k curryingu. V programovacím jazyce Standard ML je důležité, že zápis funkce adder, který jsme použili výše:

fun adder a = fn b => a + b;
val adder = fn: int → int → int;

…je možné přepsat do zjednodušené podoby:

fun adder a b = a + b;
val adder = fn: int → int → int;

Už z typů obou funkcí je zřejmé, že se jedná o totožnou sémantiku. V případě, že vytvoříme novou funkci (nezávisle na tom, zda funkci anonymní či pojmenovanou) s větším množstvím parametrů (než jeden) a současně parametry nezapíšeme formou n-tice do kulatých závorek, provede překladač currying zcela automaticky.

fun adder(a, b) = a + b;
val adder = fn: int * int → int;

Už z typu funkce vypsaného překladačem je zřejmé, že se jedná o značně odlišnou funkci.

Nyní by již mělo být zřejmé, proč typ funkce add3 z páté kapitoly:

fun add3 x y z = x+y+z;

Vypadá takto:

val add3 = fn: int → int → int → int;

Skutečný počet parametrů funkcí definovaných v jazyce Standard ML

Na celý problém se můžeme podívat i naopak – lze říci, že takto definované funkce s větším počtem parametrů se interně reprezentují funkcí s jediným parametrem, které vrací jinou funkci, která na sebe naváže druhý parametr (a tato funkce popř. vrací další funkci navazující třetí parametr atd.). Můžeme si to vyzkoušet na curryfikované funkci se čtyřmi parametry:

fun foobar x y z w = x + y + z + w;
val foobar = fn: int → int → int → int → int;

Tímto způsobem jsme vlastně mimo jiné získali i generátor generátorů funkcí:

val f1 = foobar(1);
val f1 = fn: int → int → int → int;
 
val f2 = f1(2);
val f2 = fn: int → int → int;
 
val f3 = f2(3);
val f3 = fn: int → int;
 
val f4 = f3(4);
val f4 = 10: int;

Alternativní způsob generování funkcí (různých typů) při použití jednořádkového zápisu:

fun foobar x y z w = x + y + z + w;
val foobar = fn: int → int → int → int → int;
 
val f12 = foobar(1)(2);
val f12 = fn: int → int → int;
 
val f123 = foobar(1)(2)(3);
val f123 = fn: int → int;
 
val f1234 = foobar(1)(2)(3)(4);
val f1234 = 10: int;

Ve skutečnosti ovšem můžeme závorky zcela vynechat a psát pouze:

fun foobar x y z w = x + y + z + w;
val foobar = fn: int → int → int → int → int;
 
val f1 = foobar 1;
val f1 = fn: int → int → int → int;
 
val f2 = f1 2;
val f2 = fn: int → int → int;
 
val f3 = f2 3;
val f3 = fn: int → int;
 
val f4 = f3 4;
val f4 = 10: int;

Ve druhém případě pak:

fun foobar x y z w = x + y + z + w;
val foobar = fn: int → int → int → int → int;
 
val f12 = foobar 1 2;
val f12 = fn: int → int → int;
 
val f123 = foobar 1 2 3;
val f123 = fn: int → int;
 
val f1234 = foobar 1 2 3 4;
val f1234 = 10: int;
 

Ukázky překladu do jazyka Lua a JavaScript zde neuvádím, protože překladač LunarML vše optimalizuje a nevytvoří nadbytečné funkce.

Generování funkcí pro výpočet n-té mocniny

Currying lze využít například pro generování funkcí pro výpočet zvolené n-té mocniny. Budeme přitom vycházet z rekurzivní funkce, která dokáže vypočítat mⁿ pro dvě celočíselné hodnoty m a n. Základní podoba této funkce není nijak složitá ani překvapující:

fun pow m  n  = if n = 0 then 1
                else m * pow m (n-1);

Funkci lze snadno otestovat (pro jednoduchost neuvažujeme zápornou mocninu):

pow 2 8;
val it = 256: int;
 
pow 3 2;
val it = 9: int;

Ve druhém kroku tuto funkci upravíme. Nejprve prohodíme oba parametry, což je sice na první pohled nelogické, ovšem currying (a na něj navázané vytváření částečně vyhodnocených funkcí) vždy „odstraňuje“ (nebo spíše navazuje na prostředí) první parametr, což by v našem případě měla být mocnina a nikoli základ:

fun pow m n = if m = 0 then 1
              else n * pow(m-1) n;

Výsledky (se stejnými vstupními parametry) budou podle očekávání odlišné, protože nyní je prvním parametrem mocnina a druhým parametrem základ:

pow 2 8;
val it = 64: int;
 
pow 3 2;
val it = 8: int;

Třetí úprava spočívá v náhradě podmínky za čitelnější pattern matching:

fun pow 0 n = 1
  | pow m n = n * pow(m-1) n;

Důležitý je typ této funkce:

val pow = fn: int → int → int;

Důležitější však je, že si můžeme nechat vygenerovat částečně vyhodnocené funkce. První pro výpočet druhé mocniny, druhou pro výpočet třetí mocniny:

val square = pow 2;
val square = fn: int → int;
 
val cube = pow 3;
val cube = fn: int → int;

Tyto funkce lze již bez problémů zavolat:

square 10;
val it = 100: int;
 
cube 10;
val it = 1000: int;

Nyní se podívejme na způsob transpřekladu funkce pow do jazyka Lua a JavaScriptu. Nejprve přeložíme tento kód:

(* Currying, verze s neanonymní funkcí *)
 
fun pow m n = if m = 0 then 1
              else n * pow(m-1) n;
 
 
val square = pow 2;
val cube = pow 3;
 
val x = square 10;
val y = cube 10;
 
print(Int.toString (x));
print "\n";
 
print(Int.toString (y));
print "\n";

Lua:

  local function pow(m)
    return function(n)
      if m == 0 then
        return 1
      end
      local tmp = pow(_Int_sub(m, 1))
      local tmp1 = tmp(n)
      return _Int_mul(n, tmp1)
    end
  end
  local square = pow(2)
  local cube = pow(3)
  local x = square(10)
  y = cube(10)

JavaScript:

 pow = function(m) {
  return function(n) {
   if (m === 0) {
    return 1;
   } else {
    const tmp15 = pow(_Int54_sub(m, 1));
    const tmp16 = tmp15(n);
    return _Int54_mul(n, tmp16);
   }
  };
 };
 const square = pow(2);
 const cube = pow(3);
 const x = square(10);
 const y = cube(10);

Pro zajímavost přeložíme i verzi funkce založené na pattern matchingu:

(* Currying, verze s neanonymní funkcí *)
 
fun pow 0 n = 1
  | pow m n = n * pow(m-1) n;
 
 
val square = pow 2;
val cube = pow 3;
 
val x = square 10;
val y = cube 10;
 
print(Int.toString (x));
print "\n";
 
print(Int.toString (y));
print "\n";

Lua:

  local function pow(m)
    return function(n)
      if m == 0 then
        return 1
      end
      local tmp = pow(_Int_sub(m, 1))
      local tmp1 = tmp(n)
      return _Int_mul(n, tmp1)
    end
  end
  local square = pow(2)
  local cube = pow(3)
  local x = square(10)
  y = cube(10)

JavaScript:

 pow = function(m) {
  return function(n) {
   if (m === 0) {
    return 1;
   } else {
    const tmp15 = pow(_Int54_sub(m, 1));
    const tmp16 = tmp15(n);
    return _Int54_mul(n, tmp16);
   }
  };
 };
 const square = pow(2);
 const cube = pow(3);
 const x = square(10);
 const y = cube(10);

Chyby vzniklé při překladu a v době běhu programu

Jak bylo velmi správně poznamenáno v diskuzi pod předchozím článkem, vzhledem k tomu, že je nástroj LunarML transpřekladačem, je nutné nějakým způsobem řešit odstínění programátora od cílové platformy, tedy v tomto případě od virtuálního stroje jazyka Lua nebo JavaScriptu. V praxi to znamená, že při vzniku chyby je preferováno, aby byla tato chyba vztažena k původním zdrojovým kódům programu a nikoli ke kódu transpilovanému – ostatně transpilery se používají mj. i z toho důvodu, že se programátor nechce cílovým jazykem či cílovým ekosystémem příliš zabývat (to ovšem nelze zaručit stoprocentně a asi to ani není žádoucí – například je vhodné znát příčinu výjimky atd.). V této kapitole i v kapitolách navazujících si ukážeme, do jaké míry bylo tohoto cíle v případě transpřekladače LunarML dosaženo.

Nejprve si musíme ujasnit, kdy a z jakých příčin vlastně chyby vznikají. Některé chyby mohou být hlášeny už při překladu (pokud se jedná o překládaný jazyk, což Standard ML je) a některé chyby vznikají až při běhu programu. První typ chyb je i v případě použití transpileru pro programátory snadno zvládnutelný, protože tyto chyby jsou vztaženy k původním zdrojovým kódům. Chyby vzniklé při běhu jsou komplikovanější, protože vznikají až v transpilovaném kódu. Těmto chybám se obecně nelze vyhnout, ovšem některé z nich je možné eliminovat – a to tak, že kontroly, aby takové chyby nevznikly, provede již (trans)překladač. A přesně v této oblasti je jazyk Standard ML velmi dobrý – díky silným typovým kontrolám zaručuje, že se například v runtime nikdo nepokusí a součet celého čísla se seznamem atd. (zde se s oblibou cituje Haskell, ovšem SML je mu dosti blízko). Z tohoto pohledu mohou v runtime vznikat dva typy chyb: výjimky (ty lze odchytit) a chyby související s nedostatkem zdrojů (typicky pokus o alokaci příliš velkých bloků paměti, nekonečná rekurze atd.).

Výjimky

V jazyce Standard ML se pracuje i s konceptem výjimek (exception). Výjimky lze v kódu vyhodit s využitím klíčového slova raise a definovat je možné v případě potřeby i vlastní typ výjimky. Ukažme si to na jednoduchém příkladu, konkrétně na funkci car, která vrací první prvek seznamu předaného do funkce. Ovšem v případě, že je seznam prázdný, dojde k vyhození výjimky typu Empty:

(* Vrácení prvního prvku ze seznamu *)
 
fun car [] = raise Empty
  | car (x::y) = x;
 
 
car [];
car [1];
car [1,2];
car [1,2,3];
car ["foo", "bar"];

Výsledky (i s vyhozenou výjimkou):

Uncaught SML exception: Empty
val it = 1: int;
val it = 1: int;
val it = 1: int;
val it = "foo": string;

Ve skutečnosti je však velmi snadné přidat si do aplikací vlastní nový typ výjimky. Postačuje použít tento zápis:

exception Nomatch;

Přitom exception je další klíčové slovo a Nomatch je nový typ výjimky. Tuto výjimku můžeme použít ve funkci nazvané member, která testuje, zda v nějakém seznamu existuje prvek a. Pokud je seznam prázdný (a to po rekurzivním sestupu), vyhodí se právě výjimka Nomatch:

fun member(a, []) = raise Nomatch
 |  member(a, b::y) = if a == b then b::y
                      else member(a, y);

Zachytávání výjimek vypadá syntakticky následovně:

<epxression1> handle <exception_name> => <expression2>

To znamená, že můžeme psát například:

fun check(a,x) = member(a, x) handle Nomatch =>
   (print("error!"); []);

Nahrazení výjimek datovými typy

V programovacích jazycích odvozených od ML (do této skupiny spadá i Rust, který byl ML inspirován) se velmi často setkáme s tím, že se namísto spoléhání na koncept výjimek chybové stavy reprezentují vhodným datovým typem. Nejjednodušší je použití generického typu reprezentujícího volitelnou hodnotu (optional). Například realizaci funkce pro výpočet podílu můžeme naprogramovat následovně:

fun divide x 0 = NONE
  | divide x y = SOME(x div y);

Otestování, jak se s výsledkem této operace pracuje:

fun to_string NONE = "NONE"
  | to_string (SOME n) = Int.toString n
 
 
val x = divide 10 5;
print(to_string (x));
print "\n";
 
val y = divide 10 0;
print(to_string (y));
print "\n";

datatype 'a result = Ok of 'a | Err of string

Podrobnosti si ukážeme v navazujícím článku, který je celý věnován problematice uživatelských datových typů.

Nicméně se vraťme k naší implementaci založené na zpracování typu optional. Převod na řetězec se (trans)přeloží následujícím způsobem:

Lua:

local to_string = function(a)
  if a.tag == "NONE" then
    return "NONE"
  elseif a.tag == "SOME" then
    local n = a.payload
    local result = gsub(tostring(n), "-", "~")
    return result
  else
    _raise(_Match, "exc_1.sml:5:5")
  end
end

JavaScript:

 const to_string = function(a) {
  if (a.tag === "NONE") {
   return Uint8Array.of(78, 79, 78, 69);
  } else if (a.tag === "SOME") {
   const n = a.payload;
   if (n >= 0) {
    const tmp15 = n.toString();
    return _encodeUtf8(tmp15);
   } else {
    const tmp15 = (- n).toString();
    return _encodeUtf8("~" + tmp15);
   }
  } else {
   throw _Match;
  }
 };

Při spuštění transpilované verze nedojde k žádné runtime výjimce:

$ lua exc_1.lua
 
2
NONE

Práce s výjimkami v LunarML

V této kapitole nás bude zajímat chování programu, ve kterém se s výjimkami nijak explicitně nepracuje, ale (běhové) výjimky v něm mohou vzniknou. Pokud taková výjimka při běhu programu skutečně vznikne, „vybublá“ až na nejvyšší úroveň a poté bude program ukončen:

fun divide x y = x div y;
 
 
val x = divide 10 5;
print(Int.toString(x));
print "\n";
 
val y = divide 10 0;
print(Int.toString(y));
print "\n";

Výsledek si ověříme na variantě transpilované do jazyka Lua:

$ lua exc_2.lua
 
2
lua: Int.div: Div
stack traceback:
        exc_2.lua:41: in local '_Int_div'
        exc_2.lua:117: in main chunk
        [C]: in ?

Toto obecně není ideální chování – vše, co se uživatel (a nepřímo i programátor) dozvěděl, je informace o tom, na kterém místě v transpilovaném kódu byla výjimka vyhozena. A navíc nemá tato oblast kódu už nic společného s původní funkcí (kvůli provedeným optimalizacím):

local function _Int_div(x, y)
  -- assert(math_type(x) == "integer")
  -- assert(math_type(y) == "integer")
  if y == 0 then
    _raise(_Div, "Int.div")
  elseif x == math_mininteger and y == -1 then
    _raise(_Overflow, "Int.div")
  end
  return x // y
end

Prvním krokem ke korektnějšímu chování je definice vlastního typu výjimky s využitím klíčového slova exception. Dělení nulou je poté pattern matchingem ošetřeno v první variantě funkce divide:

exception DivideByZero;
 
fun divide x 0 = raise DivideByZero
  | divide x y = x div y;
 
 
val x = divide 10 5;
print(Int.toString(x));
print "\n";
 
val y = divide 10 0;
print(Int.toString(y));
print "\n";

Chování takto upraveného programu v runtime sice stále není ideální, ovšem minimálně se dozvíme typ výjimky:

$ lua exc_3.lua
 
2
lua: exc_3.sml:3:18: DivideByZero
stack traceback:
        exc_3.lua:102: in main chunk
        [C]: in ?

Ovšem navíc můžeme k výjimce přidat i zprávu (popř. další hodnoty). Výjimka se stále definuje klíčovým slovem exception, nyní ovšem s přidanou informací o typu přiřazené hodnoty. V našem případě se bude jednat o zprávu, tedy o řetězec:

exception DivideByZero of string;
 
fun divide x 0 = raise DivideByZero ("divide " ^ Int.toString(x) ^ " by zero")
  | divide x y = x div y;
 
 
val x = divide 10 5;
print(Int.toString(x));
print "\n";
 
val y = divide 10 0;
print(Int.toString(y));
print "\n";

Opět se podívejme na způsob chování takto upraveného programu v runtime:

$ lua exc_4.lua
2
lua: exc_4.sml:3:18: DivideByZero
stack traceback:
        exc_4.lua:121: in local 'tmp'
        exc_4.lua:134: in main chunk
        [C]: in ?

Nezbývá nám tedy nic jiného, než výjimku explicitně zachytit, a to konstrukcí založenou na klíčovém slovu handle. Při vzniku výjimky se vypíše zpráva (nyní již plná zpráva s informacemi o tom, jaká hodnota je vlastně dělena nulou) a vrátí se zvolená hodnota 0. Zpracování výjimky je totiž součástí výrazu, dokonce výrazu, který musí vracet hodnotu typu int (nelze tedy vrátit int nebo string, to by musel typ y vypadat odlišně):

exception DivideByZero of string;
 
fun divide x 0 = raise DivideByZero ("divide " ^ Int.toString(x) ^ " by zero")
  | divide x y = x div y;
 
 
val x = divide 10 5;
print(Int.toString(x));
print "\n";
 
 
val y = (divide 10 0) handle DivideByZero msg => ((print msg); 0);
print(Int.toString(y));
print "\n";

Ověření chování programu:

$ lua exc_5.lua
2
divide 10 by zero
0

Jak vlastně vypadají kódy vzniklé překladem ze Standard ML?

Lua:

  local DivideByZero_tag = {"DivideByZero"}
  local divide = function(x)
    return function(y1)
      if y1 == 0 then
        local tmp = gsub(tostring(x), "-", "~")
        _raise(setmetatable({tag = DivideByZero_tag, payload = "divide " .. tmp .. " by zero"}, _exn_meta), "exc_5.sml:3:18")
      else
        return _Int_div(x, y1)
      end
    end
  end
  local tmp = divide(10)
  local x = tmp(5)
  local tmp1 = gsub(tostring(x), "-", "~")
  outputAndFlush(stdOut, tmp1)
  outputAndFlush(stdOut, "\n")
  local status, exn = pcall(function()
    local tmp2 = divide(10)
    return tmp2(0)
  end)
  if not status then
    if __exn_instanceof(exn, DivideByZero_tag) then
    else
      _raise(exn, nil)
    end
    outputAndFlush(stdOut, exn.payload)
    y = 0
  else
    y = exn
  end
end

Funkce divide tedy vrací novou funkci, která provádí test hodnoty svého jediného parametru (u původní funkce se jedná o dělitele). Pracuje se zde s identifikátorem DivideByZero_tag.

Varianta přeložená do JavaScriptu je komplikovanější, ovšem základ je prakticky totožný: divide vrací novou jednoparametrickou funkci (parametrem je původní dělitel):

 const DivideByZero_tag = function(payload) {
  this.payload = payload;
 };
 DivideByZero_tag.prototype.__isMLExn = true;
 DivideByZero_tag.prototype.name = "DivideByZero";
 const divide = function(x1) {
  return function(y1) {
   if (y1 === 0) {
    const tmp16 = toString(x1);
    throw new DivideByZero_tag(_String_append(_String_append(Uint8Array.of(100, 105, 118, 105, 100, 101, 32), tmp16), Uint8Array.of(32, 98, 121, 32, 122, 101, 114, 111)));
   } else {
    return _Int54_div(x1, y1);
   }
  };
 };
 const tmp13 = divide(10);
 const x = tmp13(5);
 const tmp14 = toString(x);
 outputAndFlush(stdOut[0], tmp14);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 let y;
 cont: {
  try {
   const tmp16 = divide(10);
   y = tmp16(0);
   break cont;
  } catch (exn) {
   if (exn instanceof DivideByZero_tag) {
    const tmp16 = exn.payload;
    outputAndFlush(stdOut[0], tmp16);
    y = 0;
    break cont;
   } else {
    throw exn;
   }
  }
 }

Jedna z největších zbraní jazyka Standard ML: uživatelské (rekurzivní) datové typy

Prozatím jsme si v tomto seriálu do značné míry vystačili se základními datovými typy programovacího jazyka ML (resp. Standard ML). Ovšem velká síla Standard ML spočívá v možnosti deklarace nových datových typů. Podporován je takzvaný algebraický typový systém (který byl dále rozšířen v jazyce OCaml). Obecně platí, že operace nad různými datovými typy jsou prováděny s využitím pattern matchingu, přičemž stojí za povšimnutí, že konstrukce hodnoty určitého datového typu vypadá po syntaktické stránce prakticky stejně, jako dekonstrukce hodnoty na její prvky v bloku match. To je poměrně typický rys pattern matchingu, který byl do určité míry přejat i do dalších programovacích jazyků, které dnes pattern matching podporují (do jisté míry ho nalezneme například v Clojure apod.).

Datové typy mohou obsahovat i rekurzi, tj. popis skutečnosti, že „tato datová složka je stejného typu, jaký právě definujeme“. To sice může na první pohled vypadat jako naprostá zbytečnost, ale v navazujícím článku si ukážeme jeden praktický příklad, který by byl bez této vlastnosti Standard ML realizovatelný poměrně komplikovaným způsobem. Ostatně v IT se s rekurzivními datovými strukturami setkáme doslova „na každém kroku“.

Příklad rekurzivního typu:

datatype expression =
      Plus of expression * expression        (* a + b *)
    | Minus of expression * expression       (* a - b *)
    | Times of expression * expression       (* a * b *)
    | Divide of expression * expression      (* a / b *)
    | Var of string
;

Od jednoduchých datových typů k rekurzivním datovým typům

Datovými typy se budeme podrobněji zabývat v navazujícím článku, ovšem již dnes si můžeme ve stručnosti ukázat nějaké vlastnosti typového systému Standard ML. Začněme datovým typem, který se nazývá disjunktní zobrazení. Obsahuje pouze výčet jmen. Tento datový typ použijeme pro reprezentaci základních osmi barev v barvové paletě:

datatype basic_color =
    Black
  | Red
  | Green
  | Yellow
  | Blue
  | Magenta
  | Cyan
  | White
;

V případě potřeby ovšem můžeme celou definici datového typu zapsat i na jediný řádek:

datatype basic_color = Black | Red | Green | Yellow | Blue | Magenta | Cyan | White;

V dalším textu budeme postupně budovat datový typ, který bude možné využít pro uložení barvy v jakékoli reprezentaci. První verze tohoto typu bude obsahovat jen jedinou možnost – již výše definovaný typ basic_color:

datatype color =
    BasicColor of basic_color;

Postupně budeme přidávat i další možnosti.

Dále se pokusme definovat funkci, která převede barvu ze základní palety osmi barev na tři složky RGB. Tyto složky můžeme reprezentovat trojicí celočíselných hodnot a samotný převod lze realizovat funkcí (nazvěme ji basic_color_to_rgb) s pattern matchingem. Prozatím se pokusme v pattern matcheru zapsat jen jedinou barvu:

fun basic_color_to_rgb Black   = (0,   0,   0)
;

Ovšem překladač vypíše varování, že nejsou pokryty všechny možnosti (Rust by naproti tomu překlad zcela odmítl – což je dobře):

WARN: Pattern matching is not exhaustive.

Doplnění dalších variant je snadné:

fun basic_color_to_rgb Black   = (0,   0,   0)
  | basic_color_to_rgb Red     = (255, 0,   0)
  | basic_color_to_rgb Green   = (0,   255, 0)
  | basic_color_to_rgb Yellow  = (255, 255, 0)
  | basic_color_to_rgb Blue    = (0,   0,   255)
  | basic_color_to_rgb Magenta = (255, 0,   255)
  | basic_color_to_rgb Cyan    = (0,   255, 255)
  | basic_color_to_rgb White   = (255, 255, 255)
  ;

Typ color ovšem můžeme dále rozšířit, například o možnost specifikace intenzity barvy (brightness) a zejména pak o možnost definice nové barvy mixováním dvou jiných barev – a právě zde narazíme na rekurzi v definici typu. Realizace v LunarML je poměrně přímočará a asi i dobře čitelná (reálná hodnota při mixování nabývá hodnoty 0.0 až 1.0, což odpovídá 0% první barvy a 100% barvy druhé resp. druhou limitní hodnotou je 100% první barvy a 0% barvy druhé):

datatype basic_color =
    Black
  | Red
  | Green
  | Yellow
  | Blue
  | Magenta
  | Cyan
  | White
 
 
 
;datatype brightness =
    Dark
  | Bright
;
 
 
 
datatype color =
    BasicColor of basic_color * brightness
  | Mix of real * color * color
;

Příloha: Makefile pro transpřeklad všech dnes ukázaných demonstračních příkladů

Všechny minule i dnes použité demonstrační příklady byly přeloženy z jazyka Standard ML do jazyků Lua a JavaScript následujícím souborem Makefile:

programs := \
        accumulate.lua \
        add_1.lua \
        add_2.lua \
        add_3.lua \
        add_4.lua \
        add_5.lua \
        anonymous_add_1.lua \
        anonymous_add_2.lua \
        anonymous_inc_1.lua \
        anonymous_inc_2.lua \
        colors_1.lua \
        colors_2.lua \
        colors_3.lua \
        colors_4.lua \
        colors_5.lua \
        colors_6.lua \
        exc_1.lua \
        exc_2.lua \
        exc_3.lua \
        exc_4.lua \
        exc_5.lua \
        exists.lua \
        fibonacci_func_call_1.lua \
        fibonacci_func_call_2.lua \
        fibonacci_naive.lua \
        fibonacci_pattern_matching.lua \
        hello.lua \
        length.lua \
        map.lua \
        mutual_recursion.lua \
        pipe.lua \
        pow_curry_1.lua \
        pow_curry_2.lua \
        some_none.lua \
        some_none_2.lua \
        string_join.lua \
        sum_int.lua \
        sum_real.lua \
        tuples.lua \
        accumulate.js \
        add_1.js \
        add_2.js \
        add_3.js \
        add_4.js \
        add_5.js \
        anonymous_add_1.js \
        anonymous_add_2.js \
        anonymous_inc_1.js \
        anonymous_inc_2.js \
        colors_1.js \
        colors_2.js \
        colors_3.js \
        colors_4.js \
        colors_5.js \
        colors_6.js \
        exc_1.js \
        exc_2.js \
        exc_3.js \
        exc_4.js \
        exc_5.js \
        exists.js \
        fibonacci_func_call_1.js \
        fibonacci_func_call_2.js \
        fibonacci_naive.js \
        fibonacci_pattern_matching.js \
        hello.js \
        length.js \
        map.js \
        mutual_recursion.js \
        pipe.js \
        pow_curry_1.js \
        pow_curry_2.js \
        some_none.js \
        some_none_2.js \
        string_join.js \
        sum_int.js \
        sum_real.js \
        tuples.js
 
 
all: $(programs)
 
clean:
        rm -f *.lua
 
.PHONY: all clean
 
%.lua: %.sml
        docker run -v work1:/work -w /work ghcr.io/minoki/lunarml:latest lunarml compile $<
 
%.js: %.sml
        docker run -v work1:/work -w /work ghcr.io/minoki/lunarml:latest lunarml compile --webjs $<

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

Všechny výše popsané demonstrační příklady (a to jak zdrojové kódy v SML, tak i výsledek transpřekladu do jazyků Lua a JavaScript) 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, a to včetně příkladů, které byly popsány <a>v předchozím článku:

Literatura

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
19. Types and Programming Languages
    https://i.warosu.org/data/sci/im­g/0163/64/1725651701869705­.pdf
20. Purely Functional Data Structures (Chris Okasaki)
    https://www.cs.cmu.edu/~rwh/stu­dents/okasaki.pdf

Předchozí články o jazyku ML/SML i o jazycích OCaml a F#

Jak již bylo napsáno v úvodu dnešního článku, na stránkách Roota jsme se již seznámili jak se základními koncepty jazyka ML/Standard ML, tak i s jazyky OCaml a F#, které z původního ML vychází:

1. ML – funkcionální jazyk s revolučním typovým systémem
   https://www.root.cz/clanky/ml-funkcionalni-jazyk-s-revolucnim-typovym-systemem/
2. Funkce a typový systém programovacího jazyka ML
   https://www.root.cz/clanky/funkce-a-typovy-system-programovaciho-jazyka-ml/
3. Curryfikace (currying), výjimky a vlastní operátory v jazyku ML
   https://www.root.cz/clanky/curryfikace-currying-vyjimky-a-vlastni-operatory-v-jazyku-ml/
4. Funkcionální programovací jazyk F#
   https://www.root.cz/clanky/fun­kcionalni-programovaci-jazyk-f/
5. Programovací jazyk OCaml
   https://www.root.cz/clanky/pro­gramovaci-jazyk-ocaml/
6. Programovací jazyk F#: proměnné, funkce a datové typy
   https://www.root.cz/clanky/pro­gramovaci-jazyk-f-promenne-funkce-a-datove-typy/
7. Proměnné, funkce a datové typy v jazyku OCaml
   https://www.root.cz/clanky/promenne-funkce-a-datove-typy-v-jazyku-ocaml/
8. Rekurze a pattern matching v programovacím jazyku F#
   https://www.root.cz/clanky/rekurze-a-pattern-matching-v-programovacim-jazyku-f/
9. Práce se seznamy v jazyce F#
   https://www.root.cz/clanky/prace-se-seznamy-v-jazyce-f/
10. Programovací jazyk OCaml: rekurze, pattern matching a práce se seznamy
    https://www.root.cz/clanky/pro­gramovaci-jazyk-ocaml-rekurze-pattern-matching-a-prace-se-seznamy/
11. Datové typy Option, Result a Array v programovacím jazyku F#
    https://www.root.cz/clanky/datove-typy-option-result-a-array-v-programovacim-jazyku-f/
12. Datové typy Option, Result a Array v programovacím jazyku OCaml
    https://www.root.cz/clanky/datove-typy-option-result-a-array-v-programovacim-jazyku-ocaml/
13. Operátory v programovacím jazyku OCaml
    https://www.root.cz/clanky/operatory-v-programovacim-jazyku-ocaml/
14. Operátory v programovacím jazyku F#
    https://www.root.cz/clanky/operatory-v-programovacim-jazyku-f/
15. Definice uživatelských datových typů v jazyku F#
    https://www.root.cz/clanky/definice-uzivatelskych-datovych-typu-v-jazyku-f/
16. Definice uživatelských datových typů v jazyku OCaml
    https://www.root.cz/clanky/definice-uzivatelskych-datovych-typu-v-jazyku-ocaml/
17. Rekurzivní datové typy v jazyku OCaml
    https://www.root.cz/clanky/rekurzivni-datove-typy-v-jazyku-ocaml/
18. Řídicí konstrukce v programovacím jazyku OCaml
    https://www.root.cz/clanky/ridici-konstrukce-v-programovacim-jazyku-ocaml/
19. LunarML: až překvapivě kvalitní transpiler z jazyka Standard ML do jazyků Lua a JavaScript
    https://www.root.cz/clanky/lunarml-az-prekvapive-kvalitni-transpiler-z-jazyka-standard-ml-do-jazyku-lua-a-javascript/

Odkazy na Internetu

1. LunarML documentation
   https://lunarml.readthedoc­s.io/en/latest/index.html
2. Standard ML of New Jersey
   https://www.smlnj.org/
3. Programming Languages: Standard ML – 1 (a navazující videa)
   https://www.youtube.com/wat­ch?v=2sqjUWGGzTo
4. 6 Excellent Free Books to Learn Standard ML
   https://www.linuxlinks.com/excellent-free-books-learn-standard-ml/
5. SOSML: The Online Interpreter for Standard ML
   https://sosml.org/
6. ML (Computer program language)
   https://www.barnesandnoble­.com/b/books/other-programming-languages/ml-computer-program-language/_/N-29Z8q8Zvy7
7. Strong Typing
   https://perl.plover.com/y­ak/typing/notes.html
8. What to know before debating type systems
   http://blogs.perl.org/user­s/ovid/2010/08/what-to-know-before-debating-type-systems.html
9. Types, and Why You Should Care (Youtube)
   https://www.youtube.com/wat­ch?v=0arFPIQatCU
10. DynamicTyping (Martin Fowler)
    https://www.martinfowler.com/bli­ki/DynamicTyping.html
11. DomainSpecificLanguage (Martin Fowler)
    https://www.martinfowler.com/bli­ki/DomainSpecificLanguage­.html
12. Language Workbenches: The Killer-App for Domain Specific Languages?
    https://www.martinfowler.com/ar­ticles/languageWorkbench.html
13. Effective ML (Youtube)
    https://www.youtube.com/watch?v=-J8YyfrSwTk
14. Why OCaml (Youtube)
    https://www.youtube.com/wat­ch?v=v1CmGbOGb2I
15. CSE 341: Functions and patterns
    https://courses.cs.washin­gton.edu/courses/cse341/04wi/lec­tures/03-ml-functions.html
16. Comparing Objective Caml and Standard ML
    http://adam.chlipala.net/mlcomp/
17. 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
18. Cheat Sheets (pro OCaml)
    https://www.ocaml.org/doc­s/cheat_sheets.html
19. Syllabus (FAS CS51)
    https://cs51.io/college/syllabus/
20. Abstraction and Design In Computation
    http://book.cs51.io/
21. Learn X in Y minutes Where X=Standard ML
    https://learnxinyminutes.com/doc­s/standard-ml/
22. CSE307 Online – Summer 2018: Principles of Programing Languages course
    https://www3.cs.stonybrook­.edu/~pfodor/courses/summer/cse307­.html
23. CSE307 Principles of Programming Languages course: SML part 1
    https://www.youtube.com/wat­ch?v=p1n0_PsM6hw
24. CSE 307 – Principles of Programming Languages – SML
    https://www3.cs.stonybrook­.edu/~pfodor/courses/summer/CSE307/L01_SML­.pdf
25. SML, Some Basic Examples
    https://cs.fit.edu/~ryan/sml/in­tro.html
26. History of programming languages
    https://devskiller.com/history-of-programming-languages/
27. History of programming languages (Wikipedia)
    https://en.wikipedia.org/wi­ki/History_of_programming_lan­guages
28. 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/
29. The Evolution Of Programming Languages
    https://www.i-programmer.info/news/98-languages/8809-the-evolution-of-programming-languages.html
30. Evoluce programovacích jazyků
    https://ccrma.stanford.edu/cou­rses/250a-fall-2005/docs/ComputerLanguagesChart.png
31. Poly/ML Homepage
    https://polyml.org/
32. PolyConf 16: A brief history of F# / Rachel Reese
    https://www.youtube.com/wat­ch?v=cbDjpi727aY
33. Programovací jazyk Clojure 18: základní techniky optimalizace aplikací
    https://www.root.cz/clanky/pro­gramovaci-jazyk-clojure-18-zakladni-techniky-optimalizace-aplikaci/
34. Moscow ML Language Overview
    https://itu.dk/people/ses­toft/mosml/mosmlref.pdf
35. ForLoops
    http://mlton.org/ForLoops
36. Funkcionální dobrodružství v JavaScriptu
    https://blog.kolman.cz/2015/12/fun­kcionalni-dobrodruzstvi-v-javascriptu.html
37. Recenze knihy Functional Thinking (Paradigm over syntax)
    https://www.root.cz/clanky/recenze-knihy-functional-thinking-paradigm-over-syntax/
38. Currying
    https://sw-samuraj.cz/2011/02/currying/
39. Používání funkcí v F#
    https://docs.microsoft.com/cs-cz/dotnet/fsharp/tutorials/using-functions
40. Funkce vyššího řádu
    http://naucte-se.haskell.cz/funkce-vyssiho-radu
41. Currying (Wikipedia)
    https://en.wikipedia.org/wi­ki/Currying
42. Currying (Haskell wiki)
    https://wiki.haskell.org/Currying
43. Haskell Curry
    https://en.wikipedia.org/wi­ki/Haskell_Curry
44. Moses Schönfinkel
    https://en.wikipedia.org/wi­ki/Moses_Sch%C3%B6nfinkel
45. Fibonacci sequence
    https://en.wikipedia.org/wi­ki/Fibonacci_sequence
46. Moonscript: jazyk inspirovaný CoffeeScriptem určený pro ekosystém jazyka Lua
    https://www.root.cz/clanky/moonscript-jazyk-inspirovany-coffeescriptem-urceny-pro-ekosystem-jazyka-lua/
47. Moonscript: jazyk inspirovaný CoffeeScriptem určený pro ekosystém jazyka Lua (2)
    https://www.root.cz/clanky/moonscript-jazyk-inspirovany-coffeescriptem-urceny-pro-ekosystem-jazyka-lua-2/
48. Moonscript: jazyk inspirovaný CoffeeScriptem určený pro ekosystém jazyka Lua (dokončení)
    https://www.root.cz/clanky/moonscript-jazyk-inspirovany-coffeescriptem-urceny-pro-ekosystem-jazyka-lua-dokonceni/
49. Programovací jazyk Lua v roli skriptovacího jazyka pro WWW stránky
    https://www.root.cz/clanky/pro­gramovaci-jazyk-lua-v-roli-skriptovaciho-jazyka-pro-www-stranky/
50. Transcrypt: technologie umožňující použití Pythonu v prohlížeči
    https://www.root.cz/clanky/transcrypt-technologie-umoznujici-pouziti-pythonu-v-prohlizeci/
51. GopherJS: transpřekladač z jazyka Go do JavaScriptu
    https://www.root.cz/clanky/gopherjs-transprekladac-z-jazyka-go-do-javascriptu/
52. Rychlost CPythonu 3.11 a 3.12 v porovnání s JIT a AOT překladači
    https://www.root.cz/clanky/rychlost-cpythonu-3–11-a-3–12-v-porovnani-s-jit-a-aot-prekladaci-pythonu/
53. Seriál F# a OCaml
    https://www.root.cz/serialy/f-a-ocaml/
54. Haskell or Standard ML for beginners?
    https://stackoverflow.com/qu­estions/810409/haskell-or-standard-ml-for-beginners#813646
55. Awesome transpilers
    https://github.com/milahu/awesome-transpilers