Curry (programovací jazyk) - Curry (programming language)

tento článek příliš spoléhá na Reference na primární zdroje. Vylepšete to přidáním sekundární nebo terciární zdroje. (Července 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Kari^[1] je experimentální funkční logické programování Jazyk,^[2] založeno na Haskell Jazyk. Spojuje prvky funkčního a logického programování, včetně programování omezení integrace.

Je to téměř nadmnožina Haskellu, postrádá podporu hlavně pro přetížení pomocí tříd typu, které některé implementace stejně poskytují jako rozšíření jazyka, jako je například Münster Curry Compiler.^[3]

Základy programování funkční logiky

Základní pojmy

Funkční program je sada funkcí definovaných rovnicemi nebo pravidly. Funkční výpočet spočívá v nahrazení subexpresí stejnými (s ohledem na definice funkcí) subexpresemi, dokud nejsou možné další nahrazení (nebo redukce) a nezíská se hodnota nebo normální forma. Zvažte například funkci double definovanou pomocí

dvojité x = x + x

Výraz "dvojitý 1“Nahrazuje 1+1. Ten může být nahrazen 2 pokud interpretujeme operátor “+„Definováno nekonečnou sadou rovnic, např. 1+1 = 2, 1+2 = 3Podobným způsobem lze vyhodnotit vnořené výrazy (kde jsou citovány dílčí výrazy, které mají být nahrazeny):

'double (1 + 2)' → '(1 + 2)' + (1 + 2) → 3 + '(1 + 2)' → '3 + 3' → 6

Existuje také další pořadí vyhodnocení, pokud nahradíme argumenty operátorů zprava doleva:

'double (1 + 2)' → (1 + 2) + '(1 + 2)' → '(1 + 2)' + 3 → '3 + 3' → 6

V tomto případě vedou obě derivace ke stejnému výsledku, vlastnosti známé jako soutok. To vyplývá ze základní vlastnosti čistě funkčních jazyků, nazývané referenční transparentnost: hodnota vypočítaného výsledku nezávisí na pořadí nebo době vyhodnocení kvůli absenci vedlejších účinků. To zjednodušuje úvahy a údržbu čistě funkčních programů.

Stejně jako mnoho funkčních jazyků Haskell Curry podporuje definici algebraické datové typy výčtem jejich konstruktorů. Například typ booleovských hodnot se skládá z konstruktorů Skutečný a Nepravdivé které jsou deklarovány takto:

 data Boole = Skutečný | Nepravdivé

Funkce na booleovské úrovni lze definovat porovnáváním vzorů, tj. Poskytnutím několika rovnic pro různé hodnoty argumentů:

 ne Skutečný = Nepravdivé ne Nepravdivé = Skutečný

Princip nahrazování rovných rovnými je stále platný za předpokladu, že skutečné argumenty mají požadovanou formu, např .:

ne „(není False)“ → „není True“ → False

Složitější datové struktury lze získat pomocí rekurzivní datové typy. Například seznam prvků, kde je typ prvků libovolný (označený proměnnou typu A), je buď prázdný seznam “[]„Nebo neprázdný seznam“x: xs“Skládající se z prvního prvku X a seznam xs:

 data Seznam A = [] | A : Seznam A

Typ "Seznam a“Se obvykle píše jako [A] a konečné seznamy x1:x2:...:xn:[] jsou psány jako [x1,x2,...,xn]. Můžeme definovat operace na rekurzivních typech indukčními definicemi, kde porovnávání vzorů podporuje pohodlné oddělení různých případů. Například operace zřetězení „++„Na polymorfních seznamech lze definovat následovně (volitelná deklarace typu v prvním řádku určuje, že„++”Bere dva seznamy jako vstup a vytváří výstupní seznam, kde jsou všechny prvky seznamu stejného neurčeného typu):

 (++) :: [A] -> [A] -> [A]  [] ++ ys = ys  (X:xs) ++ ys = X : xs++ys

Kromě své aplikace pro různé programovací úkoly, operace “++„Je také užitečné určit chování ostatních funkcí v seznamech. Například chování funkce last, která poskytuje poslední prvek seznamu, lze určit takto: pro všechny seznamy xs a prvky e, poslední xs = e if ∃ys:ys++[E] = xs.

Na základě této specifikace lze pomocí funkce logického programování definovat funkci, která splňuje tuto specifikaci. Podobně jako u logických jazyků poskytují funkční logické jazyky hledání řešení pro existenciálně kvantifikované proměnné. Na rozdíl od čistých logických jazyků podporují řešení rovnic přes vnořené funkční výrazy, takže rovnice jako ys++[E] = [1,2,3] je vyřešen vytvořením instance ys do seznamu [1,2] a e na hodnotu 3. V Curry lze definovat operaci jako poslední takto:

 poslední xs | ys++[E] =:= xs = E kde ys,E volný, uvolnit

Zde symbol „=:=„Se používá pro rovnicová omezení za účelem syntaktického rozlišení od definování rovnic. Podobně jsou extra proměnné (tj. Proměnné, které se nevyskytují na levé straně definující rovnice) výslovně deklarovány „kde ... zdarma„Za účelem poskytnutí některých příležitostí k detekci chyb způsobených překlepy. Podmíněná rovnice tvaru l | C = r je použitelné pro redukci, pokud byla jeho podmínka c vyřešena. Na rozdíl od čistě funkčních jazyků, kde se podmínky vyhodnocují pouze na booleovskou hodnotu, podporují funkční logické jazyky řešení podmínek hádáním hodnot pro neznámé v podmínce. K vyřešení tohoto druhu podmínek se používá zúžení, jak je popsáno v následující části.

Zúžení

Zúžení je mechanismus, kterým je proměnná vázaný na hodnotu vybranou z alternativ uložených omezeními. Každá možná hodnota je vyzkoušena v určitém pořadí, přičemž zbývající část programu je vyvolána v každém případě, aby se určila platnost vazby. Zúžení je rozšíření logického programování v tom, že provádí podobné vyhledávání, ale ve skutečnosti může generovat hodnoty jako součást hledání, a ne jen na jejich testování.

Zúžení je užitečné, protože umožňuje funkci považovat za relaci: její hodnotu lze vypočítat „v obou směrech“. Ilustrují to příklady Curry z předchozí části.

Jak je uvedeno v předchozí části, zúžení lze na grafu termínů programu považovat za redukci a často existuje mnoho různých způsobů (strategií) ke zmenšení grafu daného výrazu. Antoy a kol.^[4] v 90. letech prokázal, že zvláštní zužující se strategie, potřeba zúžení, je optimální ve smyslu provedení řady redukcí, abychom se dostali do „normální formy“ odpovídající řešení, které je mezi zdravými a úplnými strategiemi minimální. Potřebné zúžení odpovídá líné strategii, na rozdíl od SLD rozlišení strategie Prolog.

Funkční vzory

Pravidlo definující poslední výše uvedeno vyjadřuje skutečnost, že skutečný argument musí odpovídat výsledku zúžení výrazu ys ++ [e]. Curry může tuto vlastnost vyjádřit také následujícím výstižnějším způsobem:

 poslední (ys++[E]) = E

Haskell takové prohlášení neumožňuje, protože vzor na levé straně obsahuje definovanou funkci (++). Takový vzor se také nazývá funkční vzor.^[5] Funkční vzory umožňují kombinované funkční a logické funkce Curry a podporují stručné definice úkolů vyžadujících hluboké porovnávání vzorů v hierarchických datových strukturách.

Nedeterminismus

Protože Curry je schopen řešit rovnice obsahující volání funkcí s neznámými hodnotami, je jeho mechanismus provádění založen na nedeterministických výpočtech, podobně jako v logickém programování. Tento mechanismus podporuje také definici nedeterministické operace, tj. operace, které pro daný vstup přinášejí více než jeden výsledek. Archetyp nedeterministických operací je předdefinovaná operace infix ?, volala výběr operátor, který vrací jeden ze svých argumentů. Tento operátor je definován následujícími pravidly:

 X ? y = x x? y = y

Tedy hodnocení výrazu 0 ? 1 se vrací 0 stejně jako 1. Výpočet s nedeterministickými operacemi a výpočet s volnými proměnnými zúžením má stejnou expresivní sílu.^[6]

Pravidla definující ? ukázat důležitou vlastnost Curry: všechna pravidla jsou vyzkoušena, aby bylo možné vyhodnotit nějakou operaci. Proto lze definovat pomocí

 vložit X ys     = X : ys vložit X (y:ys) = y : vložit X ys

operace pro vložení prvku do seznamu na neurčitou pozici tak, aby operace perm definován

 perm []     = [] perm (X:xs) = vložit X (perm xs)

vrátí jakoukoli permutaci daného vstupního seznamu.

Strategie

Kvůli absenci vedlejších účinků lze funkční logický program provádět s různými strategiemi. K vyhodnocení výrazů používá Curry variantu potřeba zúžení strategie, která kombinuje líné hodnocení s nedeterministickými vyhledávacími strategiemi. Na rozdíl od Prologu, který k hledání řešení využívá zpětný chod, Curry neopravuje konkrétní vyhledávací strategii. Proto existují implementace Curryho typu KiCS2, kde si uživatel může snadno vybrat strategii vyhledávání, jako hloubkové vyhledávání (zpětné sledování), vyhledávání na šířku, iterativní prohlubování nebo paralelní vyhledávání.

Reference

externí odkazy

• Kari - Domovská stránka Curryho
• Smap - Webové spouštěcí prostředí pro Curry a Haskell s různými ukázkovými programy
• MCC - Münster Curry Compiler, který používá C jako cíl
• PAKCS Hlavní implementace Curry s WWW rozhraním, které využívá Prolog jako cíl
• KiCS2 Kari implementace, která používá Haskell jako cíl
• Curry Mailing List
• Domovská stránka Michaela Hanuse
• Čistě funkční líné nedeterministické programování (Fischer, Kiselyov, Shan, 2009), Transformace funkčních logických programů na monadické funkční programy (Braßel, Fischer, Hanus, Reck, 2010) o modelování líného nedeterministického (logického) programování (jako v Curry) v čistě funkčním jazyce (Haskell ); takový přístup by mohl dát programátorovi větší flexibilitu při kontrole strategií, které jsou - v případě Curryho - integrovány.