Syntéza programu - Program synthesis

v počítačová věda, syntéza programu je úkol postavit a program které prokazatelně uspokojí danou vysokou úroveň formální specifikace. Na rozdíl od ověření programu, program má být spíše konstruován než dán; obě pole však využívají formální důkazní techniky a obě zahrnují přístupy různého stupně automatizace. Na rozdíl od automatické programování techniky, specifikace v syntéze programu obvykle nejsoualgoritmické prohlášení v příslušném logický počet.^[1]

Původ

Během letního institutu symbolické logiky na Cornellově univerzitě v roce 1957 Alonzo Church definoval problém syntetizovat obvod z matematických požadavků.^[2] Přestože se práce týká pouze obvodů, nikoli programů, je považována za jeden z prvních popisů syntézy programů a někteří badatelé syntézu programů označují jako „církevní problém“. V 60. letech podobnou myšlenku „automatického programátoru“ zkoumali vědci v oblasti umělé inteligence.^{[Citace je zapotřebí ]}

Od té doby různé výzkumné komunity zvažovaly problém syntézy programů. Pozoruhodné práce zahrnují 1969 automaty-teoretický přístup od Buči a Landweber,^[3] a díla od Manno a Waldinger (kolem 1980). Vývoj moderního programovací jazyky na vysoké úrovni lze také chápat jako formu syntézy programu.

Vývoj 21. století

Na počátku 21. století došlo k nárůstu praktického zájmu o myšlenku syntézy programů v EU formální ověření komunita a související pole. Armando Solar-Lezama ukázal, že je možné zakódovat problémy se syntézou programů Logická logika a použít algoritmy pro Booleovský problém uspokojivosti automaticky vyhledávat programy.^[4] V roce 2013 navrhli vědci na jednotném rámci pro problémy syntézy programů UPenn, UC Berkeley, a MIT.^[5] Od roku 2014 probíhá každoroční soutěž v syntéze programů, která porovnává různé algoritmy pro syntézu programů v soutěžním případě, Syntax-Guided Synthesis Competition nebo SyGuS-Comp.^[6] Dostupné algoritmy jsou přesto schopné syntetizovat pouze malé programy.

Článek z roku 2015 demonstroval syntézu PHP programy axiomaticky prokázáno, že splňují danou specifikaci, pro účely, jako je kontrola čísla za prvočíslo nebo výpis faktorů čísla.^[7]

Rámec Manny a Waldingera

Pravidla neuzavření řešení (sjednocující náhrady nejsou zobrazeny)

Č	Tvrzení	Cíle	Program	Původ
51	${ displaystyle E [p]}$
52	${ displaystyle F [p]}$
53		${ displaystyle G [p]}$	s
54		${ displaystyle H [p]}$	t
55	${ displaystyle E [{ text {true}}] lor F [{ text {false}}]}$			Vyřešit (51,52)
56		${ displaystyle lnot F [{ text {true}}] land G [{ text {false}}]}$	s	Vyřešit (52,53)
57		${ displaystyle lnot F [{ text {false}}] land G [{ text {true}}]}$	s	Vyřešit (53,52)
58		${ displaystyle G [{ text {true}}] land H [{ text {false}}]}$	p ? s : t	Vyřešit (53,54)

Rámec Manno a Waldinger, publikováno v roce 1980,^[8][9] začíná od uživatele vzorec specifikace prvního řádu. Pro tento vzorec je vytvořen důkaz, čímž se také syntetizuje a funkční program z sjednocující substituce.

Rámec je prezentován v rozložení tabulky, sloupce obsahující:

• Číslo řádku („Nr“) pro referenční účely
• Vzorce které již byly stanoveny, včetně axiomů a předpokladů, („tvrzení“)
• Vzorce, které je třeba ještě ověřit, včetně dodatečných podmínek („Cíle“),^{[poznámka 1]}
• Podmínky označující platnou výstupní hodnotu ("Program")^{[poznámka 2]}
• Odůvodnění aktuálního řádku („Původ“)

Zpočátku se do tabulky zadávají základní znalosti, předběžné podmínky a následné podmínky. Poté se příslušná pravidla ověřování použijí ručně. Rámec byl navržen tak, aby zlepšil lidskou čitelnost přechodných vzorců: na rozdíl od klasické rozlišení, to nevyžaduje doložená normální forma, ale umožňuje uvažovat pomocí vzorců libovolné struktury a obsahujících libovolné spojky ("nelogické řešení "). Důkaz je kompletní, když ${ displaystyle { it {true}}}$ byl odvozen v Cíle sloupec nebo ekvivalentně ${ displaystyle { it {false}}}$ v Tvrzení sloupec. U programů získaných tímto přístupem je zaručeno, že splňují specifikační vzorec, který byl spuštěn; v tomto smyslu jsou správná podle konstrukce.^[10] Zatím jen minimalistický Turing-kompletní, funkční programovací jazyk, skládající se z podmíněných, rekurzivních a aritmetických a dalších operátorů^{[Poznámka 3]} Případové studie prováděné v tomto rámci syntetizují algoritmy pro výpočet např. divize, zbytek,^[11] odmocnina,^[12] sjednocení termínu,^[13] odpovědi na relační databáze dotazy^[14] a několik třídicí algoritmy.^[15][16]

Důkazní pravidla

Pravidla pro ověřování zahrnují:

• Bez doložky rozlišení (viz tabulka).

Například řádek 55 se získá vyřešením vzorců Assertion ${ displaystyle E}$ od 51 a ${ displaystyle F}$ z 52, které oba sdílejí některé společné podformule ${ displaystyle p}$. Rozpouštědlo se tvoří jako disjunkce ${ displaystyle E}$, s ${ displaystyle p}$ nahrazen ${ displaystyle { it {true}}}$, a ${ displaystyle F}$, s ${ displaystyle p}$ nahrazen ${ displaystyle { it {false}}}$. Toto řešení logicky vyplývá ze spojení ${ displaystyle E}$ a ${ displaystyle F}$. Obecněji, ${ displaystyle E}$ a ${ displaystyle F}$ potřebujete pouze dva unifiable podformule ${ displaystyle p_ {1}}$ a ${ displaystyle p_ {2}}$, v uvedeném pořadí; jejich rozpouštědlo se poté vytvoří z ${ displaystyle E theta}$ a ${ displaystyle F theta}$ jako předtím, kde ${ displaystyle theta}$ je nejobecnější unifikátor z ${ displaystyle p_ {1}}$ a ${ displaystyle p_ {2}}$. Toto pravidlo se zobecňuje řešení doložek.^[17]

Podmínky programu nadřazených vzorců jsou kombinovány, jak je znázorněno v řádku 58, aby vytvořily výstup rezolvence. V obecném případě ${ displaystyle theta}$ se vztahuje i na druhé. Od podformule ${ displaystyle p}$ objeví se ve výstupu, je třeba věnovat pozornost řešení pouze u podformulí odpovídajících vypočitatelný vlastnosti.

• Logické transformace.

Například, ${ displaystyle E land (F lor G)}$ lze transformovat na ${ displaystyle (E land F) lor (E land G)}$) v tvrzeních i v cílech, protože obě jsou rovnocenná.

• Rozdělení spojovacích tvrzení a disjunktivních cílů.

Příklad je uveden v řádcích 11 až 13 níže uvedeného příkladu hračky.

• Strukturální indukce.

Toto pravidlo umožňuje syntézu rekurzivní funkce. Pro danou pre- a postcondition „Dáno ${ displaystyle x}$ takhle ${ displaystyle { textit {pre}} (x)}$, najít ${ displaystyle f (x) = y}$ takhle ${ displaystyle { textit {post}} (x, y)}$"a příslušný uživatel dobře objednávající ${ displaystyle prec}$ domény ${ displaystyle x}$, je vždy zvukové přidat tvrzení “${ displaystyle x ' prec x land { textit {pre}} (x') implikuje { textit {post}} (x ', f (x'))}$".^[18] Řešení pomocí tohoto tvrzení může zavést rekurzivní volání ${ displaystyle f}$ v termínu programu.

Příklad je uveden v Manně, Waldinger (1980), s. 108-111, kde je syntetizován algoritmus pro výpočet kvocientu a zbytku dvou daných celých čísel pomocí pořadí ${ displaystyle (n ', d') prec (n, d)}$ definován ${ displaystyle 0 leq n '$ (str. 110).

Murray ukázal, že tato pravidla jsou kompletní pro logika prvního řádu.^[19]V roce 1986 Manna a Waldinger přidali zobecněné E-rozlišení a paramodulace pravidla pro řešení rovnosti;^[20] později se tato pravidla ukázala jako neúplná (ale přesto zvuk ).^[21]

Příklad

Příklad syntézy maximální funkce

Č	Tvrzení	Cíle	Program	Původ
1	${ displaystyle A = A}$			Axiom
2	${ displaystyle A leq A}$			Axiom
3	${ displaystyle A leq B lor B leq A}$			Axiom
10		${ Displaystyle x leq M land y leq M land (x = M lor y = M)}$	M	Specifikace
11		${ Displaystyle (x leq M land y leq M land x = M) lor (x leq M land y leq M land y = M)}$	M	Distr (10)
12		${ Displaystyle x leq M land y leq M land x = M}$	M	Split (11)
13		${ displaystyle x leq M land y leq M land y = M}$	M	Split (11)
14		${ Displaystyle x leq x land y leq x}$	X	Vyřešit (12,1)
15		${ displaystyle y leq x}$	X	Vyřešit (14,2)
16		${ displaystyle lnot (x leq y)}$	X	Vyřešit (15,3)
17		${ displaystyle x leq y land y leq y}$	y	Vyřešit (13,1)
18		${ displaystyle x leq y}$	y	Vyřešit (17,2)
19		${ displaystyle { textit {true}}}$	x ? y : X	Vyřešit (18,16)

Jako příklad hračky je funkční program pro výpočet maxima ${ displaystyle M}$ dvou čísel ${ displaystyle x}$ a ${ displaystyle y}$ lze odvodit následovně.^{[Citace je zapotřebí ]}

Počínaje popisem požadavku "Maximum je větší nebo rovno jakémukoli danému číslu a je jedním z daných čísel", vzorec prvního řádu ${ displaystyle forall X forall Y existuje M: X leq M land Y leq M land (X = M lor Y = M)}$ je získán jako jeho formální překlad. Tento vzorec je třeba prokázat. Zpětně Skolemizace,^{[poznámka 4]} získá se specifikace v řádku 10, velká a malá písmena označující proměnnou a Skolemova konstanta, resp.

Po použití pravidla transformace pro distribuční právo v řádku 11 je cílem důkazu disjunkce, a proto jej lze rozdělit na dva případy, viz. linky 12 a 13.

Pokud jde o první případ, řešení řádku 12 s axiomem v řádku 1 vede k instance proměnné programu ${ displaystyle M}$ v řádku 14. Intuitivně poslední spojka řádku 12 předepisuje hodnotu, která ${ displaystyle M}$ musí v tomto případě vzít. Formálně se na řádky 12 a 1 použije pravidlo nečlenské rezoluce zobrazené na řádku 57 výše

• p je běžnou instancí x = x z A = A a x = M, získané syntakticky sjednocující druhé vzorce,
• F[p] bytost skutečný ∧ x = x, získané od instance řádek 1 (vhodně polstrovaný, aby se vytvořil kontext F [⋅] kolem p viditelné) a
• G[p] bytost x ≤ x ∧ y ≤ x ∧ x = x, získané z instančního řádku 12,

poddajný${ displaystyle lnot (}$skutečný ∧ Nepravdivé) ∧ (x ≤ x ∧ y ≤ x ∧ skutečný${ displaystyle)}$, což zjednodušuje na ${ Displaystyle x leq x land y leq x}$.

Podobným způsobem získá řádek 14 řádek 15 a poté řádek 16 podle rozlišení. Také druhý případ, ${ displaystyle x leq M land y leq M land y = M}$ v řádku 13, je zpracováno podobně, čímž se nakonec získá řádek 18.

V posledním kroku jsou oba případy (tj. Řádky 16 a 18) spojeny pomocí pravidla rozlišení z řádku 58; aby bylo toto pravidlo použitelné, byl nutný přípravný krok 15 → 16. Řádek 18 lze intuitivně číst jako „pro případ ${ displaystyle x leq y}$, výstup ${ displaystyle y}$ je platný (s ohledem na původní specifikaci), zatímco řádek 15 říká „pro případ ${ displaystyle y leq x}$, výstup ${ displaystyle x}$ je platný; krok 15 → 16 stanovil, že oba případy 16 a 18 se vzájemně doplňují.^{[poznámka 5]} Protože řada 16 a 18 přichází s programovým termínem, a podmíněný výraz výsledky ve sloupci programu. Od cíle vzorec ${ displaystyle { textit {true}}}$ byl odvozen, je proveden důkaz a sloupec programu „${ displaystyle { textit {true}}}$"řádek obsahuje program.

Tento postup vytvoří pouze jeden operátor ve tvaru p? S: t převzatém z řádku 58. Toto není programovací jazyk, protože to není Turing Complete. Neexistují žádné příkazy, např. PŘIŘAZENÍ IF / ELSE, FOR / WHILE nebo rekurzivní programy, které jsou potřebné k dokončení jazyka Turing Complete. Mělo by být takto označeno: způsob vytvoření jediného logického operátoru, nikoli způsob vytváření programů obecně. Možná by bylo možné použít „Operator Synthesis“. Metoda výroby kola není metodou výroby automobilu.^{[Citace je zapotřebí ]}

Viz také

• Induktivní programování
• Metaprogramování
• Automatické programování
• Odvození programu
• Programování v přirozeném jazyce
• Reaktivní syntéza
• Formální ověření

Poznámky

Reference

• Zohar Manna, Richard Waldinger (1975). "Znalosti a uvažování v syntéze programu". Umělá inteligence. 6 (2): 175–208. doi:10.1016/0004-3702(75)90008-9.
• Jonathan Traugott (1986). "Deduktivní syntéza třídicích programů". Sborník z mezinárodní konference o automatizovaném odpočtu. LNCS. 230. Springer. 641–660.