0xDEADBEEF

RSS
««« »»»

Syntéza datových struktur a programů

21. 6. 2018

Generalized data structure synthesis stojí za přečtení. Prezentuje nástroj Cozy, který - jak říká název článku - umí syntetizovat datové struktury operace nad nimi, které jsou nejen korektní, ale také efektivní. Nechci opakovat, co už shrnul Adrian Colyer, přečtěte si to, teď hned, je to důležité pro následující odstavce.

Jde o perfektní doplněk k Out of the Tar Pit a možná chybějící článek nutný k tomu, aby vize načrtnutá v tar pit paperu (pokud nechcete číst, tady jsem ho kdysi shrnul).

Autor tar pit paperu mluví o esenciální a vedlejší komplexitě, přičemž ta esenciální je ta důležitá, jde o nutnou složitost problému nebo domény, chcete-li. Vedlejší komplexita nemá žádnou hodnotu pro uživatele, jen je někdy nutná pro dosažení efektivity a dostatečného výkonu. Esenci musíme nějak vyjádřit a vedlejší složitostí bychom se měli vyhnout.

Na tom není nic kontroverzního, ale teď jak toho dosáhnout. V tar pit paperu se mluví o logickém a funkcionálním programování, deklarativním stylu a relačním datovém modelu.

A tady do hry vstupuje Cozy - nadefinuji nezbytný stav bez ohledu na efektivní reprezentaci, tak jak o něm přemýšlejí uživatelé, deklarativně popíšu operace nad ním, jako v tar pit utopii a Cozy, nebo nějaký jeho pokročilý potomek, z této kostry syntetizuje její efektivnější verzi - efektivní datové struktury specializované pro dané operace a efektivní kód. Z esenciálního popisu vygeneruje všechnu vedlejší komplexitu a odvozený stav.


Heuristiky a strategie prohledávání stavového prostoru, můžou být pochopitelně rozšířeny strojovým učením.

píše k47 (@kaja47, k47)