LunarML: až překvapivě kvalitní transpiler z jazyka Standard ML do jazyků Lua a JavaScript

Na tomto místě je možná dobré připomenout, že Standard ML je velmi zajímavým jazykem, který patří (alespoň podle skromného názoru autora tohoto článku) mezi trojici programovacích jazyků, které by měl alespoň rámcově znát každý programátor. Ve skutečnosti se v případě ML jedná o tři doménově specifické jazyky v jednom, protože ML obsahuje sémantická pravidla pro popis algoritmu (výpočtu, vyhodnocení), dále pro popis datových typů a nakonec DSL určený pro popis modulů. Zajímavé (z pohledu výuky) je, že se jednotlivé části ML mohou učit postupně – tedy napřed způsob zápisu algoritmů (kupodivu se zde po poměrně dlouhou dobu obejdeme bez explicitního zápisu typů – jaká to změna oproti mainstreamu), poté se může student naučit typový systém ML (což je stále špička v oboru) a nakonec zbývá systém určený pro popis modulů.

Ovšem to není vše. Samotný ML resp. SML je dobře čitelný a navíc i programový kód, který vznikne transpřekladem z ML do Luy či JavaScriptu, je taktéž poměrně dobře pochopitelný. To si ostatně můžeme velmi snadno ověřit, například zjištěním, jakým způsobem se transformuje (poněkud naivní a neidiomaticky zapsaný) algoritmus výpočtu n-tého prvku Fibonacciho posloupnosti:

(* 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);

Překladem do jazyka Lua vznikne tento zdrojový kód:

  local function fib(n)
    if n == 0 then
      return 0
    elseif n == 1 then
      return 1
    end
    local tmp1 = fib(_Int_sub(n, 1))
    local tmp2 = fib(_Int_sub(n, 2))
    return _Int_add(tmp1, tmp2)
  end

I transpřeklad do JavaScriptu vede k vytvoření čitelného kódu:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp6 = fib(_Int54_sub(n, 1));
   const tmp7 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp6, tmp7);
  }
 };

Transpilery používané v minulosti i v současnosti

Jazyk Standard ML se typicky překládá do nativního kódu, ovšem k dispozici jsou i „interpretační překladače“ umožňující interaktivní zápis deklarací funkcí a typů. LunarML ovšem do této kategorie nepatří, protože se jedná o typický transpřekladač vyžadující na vstupu celý zdrojový kód (to je docela škoda, protože pro výuku se hodí právě „interpretační překladače“).

Problematikou takzvaných transpřekladačů (anglicky transcompilers nebo taktéž poněkud opisně source-to-source compilers) jsme se již na stránkách Rootu zabývali, a to dokonce několikrát. Připomeňme si například projekty ClojureScript (což je transpřekladač z jazyka Clojure do JavaScriptu), popř. projekty lua2js (transpřekladač Lua → opět JavaScript) a Wisp (programovací jazyk podobný Clojure transpřekládaný opět do JavaScriptu).

V předchozích větách byl použit výraz „transpřekladač“, takže si ho alespoň ve stručnosti vysvětlíme. Transpřekladače jsou nástroje sloužící pro překlad algoritmů zapsaných v nějakém zdrojovém programovacím jazyce do zvoleného cílového programovacího jazyka (ovšem nikoli do nativního kódu či do bajtkódu, to je totiž role běžných překladačů – compilers).

Transpřekladače se v informatice používají již po několik desetiletí. Například se stále můžeme setkat s nástroji, které převádí kód z nějakého vyššího programovacího jazyka do Céčka, které je v současnosti s trochou nadsázky chápáno jako „univerzální assembler“. Asi nejznámějším příkladem z této oblasti je nástroj nazvaný web2c, jenž slouží pro transformaci zdrojových kódů TeXu do céčka, ovšem existuje například i mypyc pro překlad z Pythonu do jazyka C. Transpřekladače byly – a to zejména v minulém desetiletí, konkrétně před příchodem ES6 – velmi populární i mezi programátory webových aplikací, a to zejména z toho důvodu, že webové prohlížeče nativně podporují většinou pouze JavaScript, který je tak přirozeně cílovým jazykem transpřekladačů (proto se mu také někdy říká „assembler pro web“, viz též odkazy na konci článku). Určitou revolucí byl v této oblasti právě CoffeeScript. A mnoho vlastností CoffeeScriptu bylo převzato do ES6 (ECMAScript 2015), což způsobilo postupný odklon od CoffeeScriptu.

Z praxe můžeme uvést například následující projekty založené na transpřekladači:

Praktické ukázky využití nástroje LunarML

Repositář nástroje LunarML je dostupný na adrese https://github.com/minoki/LunarML. K dispozici je hned několik možností jeho spuštění. Buď je možné si celý projekt lokálně přeložit (sestavit), nebo si můžete stáhnout předpřipravené binární balíčky se zvolenou verzí LunarML ze stránky https://github.com/minoki/Lu­narML/releases. Pravděpodobně nejjednodušší je ovšem spuštění přes Docker či Podman. Nejdříve je pochopitelně nutné získat příslušný obraz:

$ docker pull ghcr.io/minoki/lunarml:latest

Překlad resp. transpřeklad se provede následujícím způsobem:

$ docker run --rm -v "$(pwd)":/work -w /work ghcr.io/minoki/lunarml:latest lunarml compile název_zdrojového_kódu.sml

Do JavaScriptu:

$ docker run --rm -v "$(pwd)":/work -w /work ghcr.io/minoki/lunarml:latest lunarml compile --nodejs název_zdrojového_kódu.sml

nebo:

$ docker run --rm -v "$(pwd)":/work -w /work ghcr.io/minoki/lunarml:latest lunarml compile --webjs název_zdrojového_kódu.sml

V dnešním článku budou všechny kódy napsané ve Standard ML přeloženy touto verzí LunarML:

$ docker run --rm -v "$(pwd)":/work -w /work ghcr.io/minoki/lunarml:latest lunarml version
 
LunarML version 0.3.0

Samotný transpiler LunarML nabízí několik přepínačů, ze kterých využijeme jen –nodejs popř. –webjs:

Usage:
  /opt/lunarml/lib/lunarml/bin/lunarml [subcommand] [options] file.sml
Subcommands:
  compile               Compile a program.
  check                 Check a program.
  help                  Show this message.
  version               Show version information.
Options:
  -o,--output=file.ext  File name to output.
  --exe                 Produce a standalone script.
  --lib                 Produce a Lua module.
  --lua                 Produce Lua code (targets Lua 5.3+).
  --lua-continuations   Produce Lua code (targets Lua 5.3+ / supports one-shot delimited continuations).
  --luajit              Produce Lua code (targets LuaJIT).
  --nodejs              Produce JavaScript code for Node.js.
  --nodejs-cps          Produce JavaScript code for Node.js (CPS mode).
  --webjs               Produce JavaScript code for Web.
  --webjs-cps           Produce JavaScript code for Web (CPS mode).
  -h,--help             Show this message.
  -v,--version          Show version information.
  --dump                Dump intermediate code.
  --dump-final          Dump final intermediate code.
  -O,--optimize         Try to optimize hard.
  --mlb-path-map=<file> Specify MLB path map.
  --mlb-path-var=<var>=<path>  Specify MLB path variable.
  --default-ann <annotation>   Specify MLB annotations.
  --print-timings       Print compilation times.
  -B<libdir>            Library directory (default: <bindir>/../lib/lunarml).

Čím jiným začít – program, který vytiskne „Hello world“

Popis možností LunarML začneme ve stopách Briana Kernighana a Denise Ritchieho, tedy programem, který vypíše „Hello world“. V SML se zapíše takto:

print "Hello world!\n";

Překlad do jazyka Lua je delší, kvůli definici symbolů použitých později:

local error = error
local getmetatable = getmetatable
local setmetatable = setmetatable
local string = string
local string_format = string.format
local _exn_meta = {}
function _exn_meta:__tostring()
  local traceback = self.traceback
  if traceback then
    traceback = "\n" .. traceback
  else
    traceback = ""
  end
  return string_format("%s: %s%s", self.location or "<no location info>", self.tag[1], traceback)
end
local _Fail_tag = { "Fail" }
local function _raise(x, location)
  local e
  if getmetatable(x) == _exn_meta and location ~= nil then
    local traceback = debug.traceback(nil, 2)
    e = setmetatable({ tag = x.tag, payload = x.payload, location = location, traceback = traceback }, _exn_meta)
  else
    e = x
  end
  error(e, 1)
end
local stdout = _ENV.io.stdout
local Io_tag = {"Io"}
local tmp, tmp1 = stdout:write("Hello world!\n")
if not tmp then
  _raise(setmetatable({tag = Io_tag, payload = {cause = setmetatable({tag = _Fail_tag, payload = tmp1}, _exn_meta), ["function"] = "output", name = "<stdout>"}}, _exn_meta), "text-io.sml:290:43")
else
  stdout:flush()
end

Pokud ovšem odstraníme veškerou „vatu“, celý skript se zkrátí na volání funkce:

local tmp, tmp1 = stdout:write("Hello world!\n")

Překlad do JavaScriptu je ještě delší a kryptičtější:

"use strict";
function _Match_tag() {}
_Match_tag.prototype.__isMLExn = true;
_Match_tag.prototype.name = "Match";
const _Match = new _Match_tag();
function _String_concat(xs) {
    let n = 0;
    let xs0 = xs;
    while (xs0 !== null) {
        const s = xs0[0];
        n += s.length;
        xs0 = xs0[1];
    }
    const a = new Uint8Array(n);
    let m = 0;
    while (xs !== null) {
        const s = xs[0];
        a.set(s, m);
        m += s.length;
        xs = xs[1];
    }
    return a;
}
{
 const Io_tag = function(payload) {
  this.payload = payload;
 };
 Io_tag.prototype.__isMLExn = true;
 Io_tag.prototype.name = "Io";
 const BlockingNotSupported_tag = function() {
 };
 BlockingNotSupported_tag.prototype.__isMLExn = true;
 BlockingNotSupported_tag.prototype.name = "BlockingNotSupported";
 const BlockingNotSupported = new BlockingNotSupported_tag();
 const ClosedStream_tag = function() {
 };
 ClosedStream_tag.prototype.__isMLExn = true;
 ClosedStream_tag.prototype.name = "ClosedStream";
 const ClosedStream = new ClosedStream_tag();
 const NO_BUF = "NO_BUF";
 const closed = [false];
 const tmp = {tag: "SOME", payload: function(slice) {
  if (closed[0]) {
   throw new Io_tag({cause: ClosedStream, "function": Uint8Array.of(119, 114, 105, 116, 101, 86, 101, 99), name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62)});
  } else {
   return slice.length;
  }
 }};
 const tmp1 = {tag: "SOME", payload: function(slice) {
  if (closed[0]) {
   throw new Io_tag({cause: ClosedStream, "function": Uint8Array.of(119, 114, 105, 116, 101, 65, 114, 114), name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62)});
  } else {
   return slice.length;
  }
 }};
 const tmp2 = {tag: "SOME", payload: function(slice) {
  if (closed[0]) {
   throw new Io_tag({cause: ClosedStream, "function": Uint8Array.of(119, 114, 105, 116, 101, 86, 101, 99, 78, 66), name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62)});
  } else {
   return {tag: "SOME", payload: slice.length};
  }
 }};
 const tmp3 = {tag: "SOME", payload: function(slice) {
  if (closed[0]) {
   throw new Io_tag({cause: ClosedStream, "function": Uint8Array.of(119, 114, 105, 116, 101, 65, 114, 114, 78, 66), name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62)});
  } else {
   return {tag: "SOME", payload: slice.length};
  }
 }};
 const tmp4 = {tag: "SOME", payload: function(a) {
  if (closed[0]) {
   throw new Io_tag({cause: ClosedStream, "function": Uint8Array.of(98, 108, 111, 99, 107), name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62)});
  } else {
   return undefined;
  }
 }};
 const tmp5 = {tag: "SOME", payload: function(a) {
  if (closed[0]) {
   throw new Io_tag({cause: ClosedStream, "function": Uint8Array.of(99, 97, 110, 79, 117, 116, 112, 117, 116), name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62)});
  } else {
   return true;
  }
 }};
 const tmp6 = {tag: "NONE"};
 const tmp7 = {tag: "NONE"};
 const tmp8 = {tag: "NONE"};
 const tmp9 = {tag: "NONE"};
 const tmp10 = function(a) {
  closed[0] = true;
  return undefined;
 };
 const tmp11 = {block: tmp4, canOutput: tmp5, chunkSize: 1, close: tmp10, endPos: tmp7, getPos: tmp6, ioDesc: {tag: "NONE"}, name: Uint8Array.of(60, 110, 117, 108, 108, 87, 114, 62), setPos: tmp8, verifyPos: tmp9, writeArr: tmp1, writeArrNB: tmp3, writeVec: tmp, writeVecNB: tmp2};
 const tmp12 = [NO_BUF];
 const tmp13 = [{buffer: [null], buffer_mode: tmp12, writer: tmp11}][0];
 const name = tmp13.writer.name;
 const writeVec = tmp13.writer.writeVec;
 const buffer = tmp13.buffer;
 let tmp14;
 cont: {
  let tmp15 = [Uint8Array.of(72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33, 10), buffer[0]], tmp16 = null;
  for (;;) {
   const _1 = tmp15, ys = tmp16;
   if (_1 === null) {
    tmp14 = ys;
    break cont;
   } else if (! (_1 === null)) {
    const tmp17 = _1[0];
    const tmp18 = _1[1];
    [tmp15, tmp16] = [tmp18, [tmp17, ys]];
   } else {
    throw _Match;
   }
  }
 }
 const content$PRIME = _String_concat(tmp14);
 if (writeVec.tag === "SOME") {
  const writeVec1 = writeVec.payload;
  writeVec1({base: content$PRIME, length: content$PRIME.length, start: 0});
  buffer[0] = null;
 } else if (writeVec.tag === "NONE") {
  throw new Io_tag({cause: BlockingNotSupported, "function": Uint8Array.of(111, 117, 116, 112, 117, 116), name: name});
 } else {
  throw _Match;
 }
}

Pokud v tomto skriptu nemůžete nalézt řetězec Hello world, pak prozradím, že je zakódován tady:

  let tmp15 = [Uint8Array.of(72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33, 10), buffer[0]], tmp16 = null;

Optimalizace generovaného kódu

LunarML sice může vypadat jako typický „školní“ projekt založený na sadě přepisovacích pravidel, ovšem ve skutečnosti je jeho překladač poměrně sofistikovaný a dokáže provádět různé optimalizace vygenerovaného kódu. Ukažme si to na jednoduchém příkladu, ve kterém je definována dvojice celočíselných proměnných a následně je vypočten a zobrazen výsledek jejich součtu:

val a = 1;
val b = 2;
print(Int.toString (a+b));
print "\n";

V kódu přeloženém do jazyka Lua se ovšem vypisuje až výsledek operace, tj. hodnota 3:

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

Totéž platí i pro překlad do JavaScriptu:

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

Ve druhém příkladu bude součet proveden nikoli přímo operátorem +, ale funkcí add. To bude klást na (trans)překladač požadavek složitějších optimalizací:

fun add (x, y) = x + y;
 
val a = 2;
val b = 3;
val c = add(a, b);
print(Int.toString c);
print "\n";

I nyní dojde k optimalizaci a bude se zobrazovat přímo výsledek součtu:

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

a:

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

Překlad dvou variant výpočtu Fibonacciho posloupnosti

Ve funkcionálních programovacích jazycích, mezi které Standard ML patří, se velmi často setkáme s rekurzivními funkcemi, typicky založenými na principu postupného zjednodušování nějakého problému. Například poněkud naivní implementace funkce pro výpočet n-tého prvku Fibonacciho posloupnosti může být zapsána následujícím způsobem (i když ji pravděpodobně nikdo tímto stylem psát nebude):

(* 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);
 
 
print(Int.toString(fib 0));
print "\n";
print(Int.toString(fib 1));
print "\n";
print(Int.toString(fib 10));
print "\n";

Překlad tohoto programu do jazyka Lua je poměrně přímočarý a přitom dobře čitelný:

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

I překlad do JavaScriptu dopadne relativně „dobře“, protože je výsledek v rámci možností čitelný:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp19 = fib(_Int54_sub(n, 1));
   const tmp20 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp19, tmp20);
  }
 };
 
 
 
 const tmp13 = fib(0);
 const tmp14 = toString(tmp13);
 outputAndFlush(stdOut[0], tmp14);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp15 = fib(1);
 const tmp16 = toString(tmp15);
 outputAndFlush(stdOut[0], tmp16);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp17 = fib(10);
 const tmp18 = toString(tmp17);
 outputAndFlush(stdOut[0], tmp18);
 outputAndFlush(stdOut[0], Uint8Array.of(10));

local function _Int_add(x, y)
  -- assert(math_type(x) == "integer")
  -- assert(math_type(y) == "integer")
  local z = x + y
  if y > 0 and z < x then
    _raise(_Overflow, "Int.+")
  elseif y < 0 and z > x then
    _raise(_Overflow, "Int.+")
  else
    return z
  end
end
 
 
 
local function _Int_sub(x, y)
  -- assert(math_type(x) == "integer")
  -- assert(math_type(y) == "integer")
  local z = x - y
  if y < 0 and z < x then
    _raise(_Overflow, "Int.-")
  elseif y > 0 and x < z then
    _raise(_Overflow, "Int.-")
  else
    return z
  end
end

resp. obdoba pro JavaScript:

function _Int54_add(x, y) {
    const z = x + y;
    if ((MIN_INT54 < z && z <= MAX_INT54) || (z === MIN_INT54 && (x & 1) === (y & 1))) {
        return z;
    } else {
        throw _Overflow;
    }
}
 
 
 
function _Int54_sub(x, y) {
    const z = x - y;
    if ((MIN_INT54 < z && z <= MAX_INT54) || (z === MIN_INT54 && (x & 1) === (y & 1))) {
        return z;
    } else {
        throw _Overflow;
    }
}

Výše uvedená implementace funkce fib ve skutečnosti není pro jazyk ML idiomatická – spíše se podobá přímému přepisu z LISPu nebo ze Scheme. Častěji se setkáme s použitím pattern matchingu, kterým se (v tomto případě) určují těla funkce pro různé vstupní podmínky. Díky tomu lze velmi snadno a především přehledně vyjmenovat například všechny mezní podmínky.

Podívejme se tedy na to, jak by se v jazyku SML mohla definovat funkce pro výpočet n-tého členu slavné Fibonacciho posloupnosti. Jedno z možných řešení přímo vychází z jedné varianty matematické definice této posloupnosti (existuje ještě varianta s F₀=0):

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2

Přepis tohoto předpisu bez použití pattern matchingu bude vypadat takto:

(* Implementace výpočtu Fibonacciho posloupnosti s využitím pattern matchingu *)
 
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2);
 
 
print(Int.toString(fib 0));
print "\n";
print(Int.toString(fib 1));
print "\n";
print(Int.toString(fib 10));
print "\n";

Překlad do jazyka Lua odpovídá verzi bez pattern matchingu:

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

Naprosto totéž platí i pro variantu přeloženou do JavaScriptu:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp19 = fib(_Int54_sub(n, 1));
   const tmp20 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp19, tmp20);
  }
 };
 
 
 
 const tmp13 = fib(0);
 const tmp14 = toString(tmp13);
 outputAndFlush(stdOut[0], tmp14);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp15 = fib(1);
 const tmp16 = toString(tmp15);
 outputAndFlush(stdOut[0], tmp16);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp17 = fib(10);
 const tmp18 = toString(tmp17);
 outputAndFlush(stdOut[0], tmp18);
 outputAndFlush(stdOut[0], Uint8Array.of(10));

Komplikovanější varianty výpočtu Fibonacciho posloupnosti

V dalším kroku se pokusíme o to, abychom práci (trans)překladači poněkud znepříjemnili. Namísto výpočtu n-1 a n-2 budeme volat nové uživatelské funkce dec1 a dec2, u kterých si musí překladač odvodit typy a následně jejich volání eliminovat (inliningem):

(* Implementace výpočtu Fibonacciho posloupnosti s využitím pattern matchingu *)
 
fun dec1 x = x - 1;
fun dec2 x = x - 2;
 
 
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (dec1 n) + fib (dec2 n);
 
 
print(Int.toString(fib 0));
print "\n";
print(Int.toString(fib 1));
print "\n";
print(Int.toString(fib 10));
print "\n";

Překladač LunarML skutečně takové optimalizace provede:

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

Varianta pro JavaScript:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp19 = fib(_Int54_sub(n, 1));
   const tmp20 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp19, tmp20);
  }
 };
 
 
 
 const tmp13 = fib(0);
 const tmp14 = toString(tmp13);
 outputAndFlush(stdOut[0], tmp14);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp15 = fib(1);
 const tmp16 = toString(tmp15);
 outputAndFlush(stdOut[0], tmp16);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp17 = fib(10);
 const tmp18 = toString(tmp17);
 outputAndFlush(stdOut[0], tmp18);
 outputAndFlush(stdOut[0], Uint8Array.of(10));

Podobné optimalizace by se měly provést i v případě, že funkce dec2 závisí na dříve definované funkci dec1:

(* Implementace výpočtu Fibonacciho posloupnosti s využitím pattern matchingu *)
 
fun dec1 x = x - 1;
fun dec2 x = dec1 (dec1 x);
 
 
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (dec1 n) + fib (dec2 n);
 
 
print(Int.toString(fib 0));
print "\n";
print(Int.toString(fib 1));
print "\n";
print(Int.toString(fib 10));
print "\n";

Překlad s optimalizacemi do jazyka Lua:

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

Překlad s optimalizacemi do JavaScriptu:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp19 = fib(_Int54_sub(n, 1));
   const tmp20 = fib(_Int54_sub(_Int54_sub(n, 1), 1));
   return _Int54_add(tmp19, tmp20);
  }
 };
 
 
 
 const tmp13 = fib(0);
 const tmp14 = toString(tmp13);
 outputAndFlush(stdOut[0], tmp14);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp15 = fib(1);
 const tmp16 = toString(tmp15);
 outputAndFlush(stdOut[0], tmp16);
 outputAndFlush(stdOut[0], Uint8Array.of(10));
 const tmp17 = fib(10);
 const tmp18 = toString(tmp17);
 outputAndFlush(stdOut[0], tmp18);
 outputAndFlush(stdOut[0], Uint8Array.of(10));

Za jakých okolností již LunarML nedokáže provést úplnou optimalizaci?

Mohlo by se zdát, že možnosti „inliningu“, který transpřekladač LunarML provádí, nejsou prakticky omezené. Ovšem není tomu tak, což si ukážeme na příkladu, ve kterém se nejdříve vypočtou dva prvky Fibonacciho posloupnosti, které se mají následně sečíst. Je to tedy opačný postup, než jaký byl ukázaný v předchozí kapitole – tam jsme volali pomocné funkce z funkce pro výpočet Fibonacciho posloupnosti, zde je tomu naopak:

(* 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);
 
 
fun add (x, y) = x + y;
 
val a = fib 10;
val b = fib 20;
val c = add(a, b);
print(Int.toString c);
print "\n";

Překlad ze Standard ML do jazyka Lua ukazuje, že se fib stále volá:

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 a = fib(10)
local b = fib(20)
local c = _Int_add(a, b)
local result = gsub(tostring(c), "-", "~")
outputAndFlush(stdOut, result)
outputAndFlush(stdOut, "\n")

Totéž platí i pro překlad do JavaScriptu:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp14 = fib(_Int54_sub(n, 1));
   const tmp15 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp14, tmp15);
  }
 };
 
 
 
 const a = fib(10);
 const b = fib(20);
 const c = _Int54_add(a, b);
 let tmp13;
 if (c >= 0) {
  const tmp14 = c.toString();
  tmp13 = _encodeUtf8(tmp14);
 } else {
  const tmp14 = (- c).toString();
  tmp13 = _encodeUtf8("~" + tmp14);
 }
 outputAndFlush(stdOut[0], tmp13);
 outputAndFlush(stdOut[0], Uint8Array.of(10));

Nepatrně složitější výpočet součtu realizovaný funkcí add3 ukazuje, že inlining se provede pro tuto funkci, ovšem nikoli pro složitější funkci fib:

(* 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);
 
 
fun add3 (x, y, z) = x + y + z;
 
val a = fib 1;
val b = fib 2;
val c = fib 3;
val d = add3(a, b, c);
print(Int.toString d);
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 a = fib(1)
local b = fib(2)
local c = fib(3)
local d = _Int_add(_Int_add(a, b), c)
local result = gsub(tostring(d), "-", "~")
outputAndFlush(stdOut, result)
outputAndFlush(stdOut, "\n")

Výsledek překladu do JavaScriptu:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp14 = fib(_Int54_sub(n, 1));
   const tmp15 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp14, tmp15);
  }
 };
 
 
 
 const a = fib(1);
 const b = fib(2);
 const c = fib(3);
 const d = _Int54_add(_Int54_add(a, b), c);
 let tmp13;
 if (d >= 0) {
  const tmp14 = d.toString();
  tmp13 = _encodeUtf8(tmp14);
 } else {
  const tmp14 = (- d).toString();
  tmp13 = _encodeUtf8("~" + tmp14);
 }
 outputAndFlush(stdOut[0], tmp13);
 outputAndFlush(stdOut[0], Uint8Array.of(10));

Připomeňme si, že ve Standard ML lze využívat jazykovou konstrukci let in umožňující definici lokálních symbolů. Otázkou je, zda použití této konstrukce nějakým způsobem vylepší výsledek transpřekladu:

(* 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);
 
 
(* Realizace funkce pro součet tří celočíselných hodnot *)
fun add3 (x, y, z) = x + y + z;
 
let
    val a = fib 1
    val b = fib 2
    val c = fib 3
    val d = add3(a, b, c)
in
    print(Int.toString d);
    print "\n"
end;

Ve skutečnosti je výsledek zcela totožný s výsledkem překladu předchozího příkladu:

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 a = fib(1)
local b = fib(2)
local c = fib(3)
local d = _Int_add(_Int_add(a, b), c)

a:

 fib = function(n) {
  if (n === 0) {
   return 0;
  } else if (n === 1) {
   return 1;
  } else {
   const tmp14 = fib(_Int54_sub(n, 1));
   const tmp15 = fib(_Int54_sub(n, 2));
   return _Int54_add(tmp14, tmp15);
  }
 };
 
 
 
 const a = fib(1);
 const b = fib(2);
 const c = fib(3);
 const d = _Int54_add(_Int54_add(a, b), c);

Výpočet délky seznamu a způsob reprezentace seznamu v jazycích Lua a JavaScript

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 SML postaven, podobně jako další funkcionální jazyky. Můžeme zde 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 v jazyce ML je 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 bude akceptovat seznam libovolného typu, tj. jedná se o generickou funkci ('a zde značí „any“):

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

Otestování je snadné; provést ho můžeme například v online REPLu SOSML:

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

Výše uvedená implementace funkce length není pro jazyk ML idiomatická – spíše se podobá přímému přepisu z LISPu nebo ze Scheme. Častěji se setkáme s použitím pattern matchingu, kterým se (v tomto případě) určují těla funkce pro různé vstupní podmínky. Díky tomu lze velmi snadno a především přehledně vyjmenovat například všechny mezní podmínky. Pro funkci length je zde jediná mezní podmínka a tou je předání prázdného seznamu (další možnost je jen jedna – předal se neprázdný seznam; jiná možnost díky typovému systému není povolena):

(* Implementace funkce length založená na pattern matchingu *)
 
fun length([]) = 0
  | length(lst) = 1 + length(tl(lst));

Vzhledem k tomu, že v hlavičce funkce je jediný parametr (v obou případech), můžeme vynechat kulaté závorky:

(* Implementace funkce length založená na pattern matchingu *)
 
fun length [] = 0
  | length lst = 1 + length(tl(lst));

Předchozí použití pattern matchingu ovšem ani zdaleka neukazuje všechny možnosti programovacího jazyka ML v této oblasti. Díky existenci operátoru :: (zápis připojení prvku k seznamu, obdoba cons z LISPu/Clojure) můžeme přímo ve druhé větvi specifikovat, že pokud se na vstupu objeví seznam s hlavičkou a tělem (tedy má alespoň jeden prvek), má se provést tato větev a funkce length se má rekurzivně volat s tělem seznamu (které už může být prázdné):

(* Implementace funkce length založená na pattern matchingu *)
 
fun length([]) = 0
  | length(head::tail) = 1 + length(tail);

Vzhledem k tomu, že se hodnota hlavičky seznamu (jeho prvního prvku) nikde nepoužívá, lze zápis ještě více zjednodušit náhradou identifikátoru za podtržítko:

(* Implementace funkce length založená na pattern matchingu *)
 
fun length([]) = 0
  | length(_::tail) = 1 + length(tail);

Pro otestování způsobu (trans)překladu použijeme tento demonstrační příklad:

(* Implementace funkce length založená na pattern matchingu *)
 
fun length([]) = 0
  | length(head::tail) = 1 + length(tail);
 
 
val l1 = length([]);
val l2 = length([1]);
val l3 = length([1,2,3,4]);

Překlad do jazyka Lua naznačuje, jak jsou reprezentovány seznamy: jedná se o tabulky se dvěma prvky, přičemž druhým prvkem je buď další tabulka nebo hodnota nil (poznáváte zde LISP?):

  local function length(a)
    if a == nil then
      return 0
    elseif a ~= nil then
      local tmp = length(a[2])
      return _Int_add(1, tmp)
    else
      _raise(_Match, "length.sml:3:5")
    end
  end
 
 
 
  local l1 = length(nil)
  local l2 = length({1, nil})
  l3 = length({1, {2, {3, {4, nil}}}})

V JavaScriptu jsou seznamy konstruovány pomocnou funkcí (tedy jako pole se dvěma prvky):

function _list(a) {
    let x = null;
    for (let i = a.length - 1; i >= 0; --i) {
        x = [a[i], x];
    }
    return x;
}

A použity jsou takto:

 length = function(a) {
  if (a === null) {
   return 0;
  } else if (! (a === null)) {
   const tmp16 = length(a[1]);
   return _Int54_add(1, tmp16);
  } else {
   throw _Match;
  }
 };
 
 
 
 const l1 = length(null);
 const l2 = length(_list([1]));
 const l3 = length(_list([1, 2, 3, 4]));

Automatické určení typů parametrů funkce i její návratové hodnoty: typová inference

Pokusme se nyní definovat funkci, která provede součet hodnot prvků seznamu. Funkci ihned otestujeme:

(* Výpočet součtu prvků v seznamu *)
 
fun sum([]) = 0
  | sum(x::y) = x + sum y;
 
 
val y = sum([1,2,3]);
 
print(Int.toString(y));
print "\n";

V předchozím zdrojovém kódu jsme nikde explicitně neuvedli typy, takže si je LunarML musí odvodit sám automaticky (použije tedy technologii typové inference):

local function sum(a)
  if a == nil then
    return 0
  elseif a ~= nil then
    local tmp = a[1]
    local tmp1 = sum(a[2])
    return _Int_add(tmp, tmp1)
  else
    _raise(_Match, "sum_int.sml:3:5")
  end
end
 
 
 
local y = sum({1, {2, {3, nil}}})

Varianta pro JavaScript:

 sum = function(a) {
  if (a === null) {
   return 0;
  } else if (! (a === null)) {
   const tmp14 = a[0];
   const tmp15 = sum(a[1]);
   return _Int54_add(tmp14, tmp15);
  } else {
   throw _Match;
  }
 };
 
 
 
 const y = sum(_list([1, 2, 3]));

V obou případech se došlo tedy k odvození, že vstupem funkce sum je seznam obsahující celá čísla a výsledek je taktéž celé číslo. V obou výsledných kódech je to hlídáno operací (funkcí) součtu.

Explicitní určení typů

Vraťme se opět k funkci sum, kterou jsme definovali následovně:

(* Výpočet součtu prvků v seznamu *)
 
fun sum([]) = 0
  | sum(x::y) = x + sum y;

U takto definované funkce je odvozen datový typ v podobě:

val sum = fn: int list → int;

Což znamená, že je funkce použitelná pouze pro seznamy celých čísel.

Alternativně je možné náhradou 0 za 0.0 dosáhnout toho, že funkce bude použitelná pro seznamy reálných čísel (ovšem již ne čísel celých):

(* Výpočet součtu prvků v seznamu *)
 
fun sum([]) = 0.0
  | sum(x::y) = x + sum y;
 
 
sum([1.1, 2.2, 3.3]);

Typ můžeme specifikovat i explicitně, například u parametru (a klidně i v jediné větvi):

(* Výpočet součtu prvků v seznamu *)
 
fun sum([] : real list) = 0.0
  | sum(x::y) = x + sum y;
 
 
val y = sum([1.0, 2.0, 3.0]);
 
print(Real.toString(y));
print "\n";

Jak budou v posledním případě vypadat výsledky transpřekladu? Varianta v jazyce Lua ukazuje, že se používá běžná operace součtu, která v tomto jazyku platí pouze pro numerické hodnoty (s plovoucí řádovou čárkou):

local function sum(a)
  if a == nil then
    return 0.0
  elseif a ~= nil then
    local tmp = a[1]
    local tmp1 = sum(a[2])
    return tmp + tmp1
  else
    _raise(_Match, "sum_real.sml:3:5")
  end
end
local tmp = 1.0
local tmp1 = 2.0
local y = sum({tmp, {tmp1, {3.0, nil}}})

I varianta přeložená do JavaScriptu má podobné vlastnosti, protože i v tomto jazyku se pracuje s hodnotami s plovoucí řádovou čárkou:

 sum = function(a) {
  if (a === null) {
   return 0.0;
  } else if (! (a === null)) {
   const tmp16 = a[0];
   const tmp17 = sum(a[1]);
   return tmp16 + tmp17;
  } else {
   throw _Match;
  }
 };
 const tmp13 = 1.0;
 const tmp14 = 2.0;
 const y = sum(_list([tmp13, tmp14, 3.0]));

Realizace operace spojení řetězců předaných v seznamu

Spojení dvou řetězců je možné v jazyce Standard ML provést operátorem ^, takže je snadné napsat rekurzivní podobu funkce, která spojí všechny řetězce předané v seznamu. Stále přitom používáme stejný základ – pattern matching, rozdělení seznamu na hlavu a tělo a rekurzi:

(* Spojení řetězců předaných v seznamu *)
 
fun join([] : string list) = ""
  | join(x::y) = x ^ join y;
 
 
val x = join(["foo", " ", "bar", " ", "baz"]);
 
print x;
print "\n";

V jazyce Lua se pro spojení řetězců pro nepoužívá operátor ^, ale operátor .. (dvě tečky), takže transpřeklad do tohoto jazyka dopadl následovně:

local function join(a)
  if a == nil then
    return ""
  elseif a ~= nil then
    local tmp = a[1]
    local tmp1 = join(a[2])
    return tmp .. tmp1
  else
    _raise(_Match, "string_join.sml:3:5")
  end
end

Realizace v JavaScriptu dopadne následovně:

 join = function(a) {
  if (a === null) {
   return Uint8Array.of();
  } else if (! (a === null)) {
   const tmp13 = a[0];
   const tmp14 = join(a[1]);
   return _String_append(tmp13, tmp14);
  } else {
   throw _Match;
  }
 };

Pokud si nyní říkáte, jak je možné, že se v obou kódech liší indexy druhého prvku – je to proto, že jazyk Lua implicitně indexuje prvky tabulek od jedničky, nikoli od nuly.

Typ option

Na závěr se musíme zmínit o velmi užitečném datovém typu nazvaném option (ten jsme si již popsali v seriálu o Rustu). Tento datový typ se používá například ve chvílích, kdy je zapotřebí reprezentovat neznámou hodnotu, chybovou hodnotu (ovšem bez vyvolání výjimky), vytvořit funkci s volitelnými parametry či vytvořit typově bezpečnou obdobu odkazu typu null (null samo o sobě je v IT zlo :-). Typ option si můžeme představit jako unii se dvěma hodnotami NONE a SOME, přičemž hodnota SOME je kontejnerem pro jinou hodnotu, například výsledek výpočtu.

Poměrně typickým příkladem je funkce pro dělení, která ve chvíli, kdy je dělitel nulový, vrátí hodnotu NONE a při nenulovém děliteli pak hodnotu SOME, která obaluje vypočtený podíl:

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

Příklad volání z REPLu:

divide(10, 5);
divide(10, 0);

Typ funkce je vypočten typovou inferencí:

val divide = fn: int * int → int option;

A vypočtené výsledky:

val it = SOME 2: int option;
val it = NONE: int option;

V praxi je nutné rozlišit mezi konkrétní hodnotou a NONE další realizací pattern matchingu, což je ukázáno u funkce to_string realizující převod SOME(int)/NONE na řetězec. Celý skript tedy může vypadat následovně:

(* Použití typu option *)
 
fun divide(x, 0) = NONE
  | divide(x, y) = SOME(x div y);
 
 
fun to_string NONE = "NONE"
  | to_string (SOME n) = Int.toString n
 
 
val x = divide(10, 5);
val y = divide(10, 0);
 
print(to_string(x));
print "\n";
 
print(to_string(y));
print "\n";

Způsob překladu do jazyka Lua (ovšem bez funkce pro výpočet podílu – ta je opět optimalizována na konstantu):

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, "some_none.sml:7:5")
  end
end
 
 
 
local x = {tag = "SOME", payload = 2}
local y = {tag = "NONE"}
local tmp = to_string(x)

Dtto, nyní ovšem překlad do JavaScriptu:

 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;
  }
 };
 
 
 
 const x = {tag: "SOME", payload: 2};
 const y = {tag: "NONE"};
 const tmp13 = to_string(x);

Vynucení zavolání funkce divide a zpracování hodnoty SOME/NONE

V dnešním posledním demonstračním příkladu si „vynutíme“ výpočet podílu s výsledkem SOME(int)/NONE. Použijeme již známý trik – oba parametry jsou vypočteny funkcí fib, která není transpřekladačem optimalizována na konstantu. Upravený zdrojový kód vypadá takto:

(* Použití typu option *)
 
fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2);
 
 
fun divide(x, 0) = NONE
  | divide(x, y) = SOME(x div y);
 
 
fun to_string NONE = "NONE"
  | to_string (SOME n) = Int.toString n;
 
 
let
    val a = fib 0
    val b = fib 1
    val c = fib 2
    val x = divide(c, b)
    val y = divide(a, a)
in
    print(to_string(x));
    print "\n";
 
    print(to_string(y));
    print "\n";
end;

Překlad tohoto příkladu do jazyka Lua dopadne takto (vynechávám nepodstatné detaily):

  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
 
 
 
  to_string = function(a1)
    if a1.tag == "NONE" then
      return "NONE"
    elseif a1.tag == "SOME" then
      local n = a1.payload
      local result = gsub(tostring(n), "-", "~")
      return result
    else
      _raise(_Match, "some_none_2.sml:13:5")
    end
  end
 
 
 
  a = fib(0)
  local b = fib(1)
  local c = fib(2)
  if b == 0 then
    x = {tag = "NONE"}
  else
    x = {tag = "SOME", payload = _Int_div(c, b)}
  end
end
 
 
 
local y
if a == 0 then
  y = {tag = "NONE"}
else
  y = {tag = "SOME", payload = _Int_div(a, a)}
end
local tmp = to_string(x)

Varianta překladu do JavaScriptu:

 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 to_string = function(a1) {
  if (a1.tag === "NONE") {
   return Uint8Array.of(78, 79, 78, 69);
  } else if (a1.tag === "SOME") {
   const n = a1.payload;
   if (n >= 0) {
    const tmp15 = n.toString();
    return _encodeUtf8(tmp15);
   } else {
    const tmp15 = (- n).toString();
    return _encodeUtf8("~" + tmp15);
   }
  } else {
   throw _Match;
  }
 };
 
 
 
 const a = fib(0);
 const b = fib(1);
 const c = fib(2);
 let x;
 if (b === 0) {
  x = {tag: "NONE"};
 } else {
  x = {tag: "SOME", payload: _Int54_div(c, b)};
 }
 let y;
 if (a === 0) {
  y = {tag: "NONE"};
 } else {
  y = {tag: "SOME", payload: _Int54_div(a, a)};
 }
 const tmp13 = to_string(x);

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

Všechny 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 \
        exists.lua \
        fibonacci_func_call_1.lua \
        fibonacci_func_call_2.lua \
        fibonacci_naive.lua \
        fibonacci_pattern_matching.lua \
        hello.lua \
        length.lua \
        mutual_recursion.lua \
        pipe.lua \
        some_none.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 \
        exists.js \
        fibonacci_func_call_1.js \
        fibonacci_func_call_2.js \
        fibonacci_naive.js \
        fibonacci_pattern_matching.js \
        hello.js \
        length.js \
        mutual_recursion.js \
        pipe.js \
        some_none.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 $<

Příloha B: online varianta jazyka Standard ML

Překlad resp. transpřeklad jazyka Standard ML není jediná možnost, jak si tento v několika ohledech revoluční jazyk můžete v současnosti prakticky vyzkoušet. Nejjednodušší resp. časově nejméně náročné je použití online verze tohoto jazyka, pro jejíž zprovoznění postačuje pouze nějaký moderní webový prohlížeč (s JavaScriptem, jaká to ironie) 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 či špatně napsaných programových smyček.

Použití SOSML je v praxi až triviálně 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 ihned provedeno 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 (můžeme si tedy nechat vyhodnotit více výrazů, například více volání stejné funkce s různými parametry); navíc je barevně odlišeno i případné hlášení o chybě.

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

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 jazyka Lua) 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:

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

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/

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