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

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) 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. (Březen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek je napsán jako manuál nebo průvodce. Prosím pomozte přepište tento článek z popisného, neutrální hlediskoa odstranit rady nebo pokyny. (Únor 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Září 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

ATS

Paradigma	multi-paradigma: funkční, rozkazovací způsob
Navrhl	Hongwei Xi na Bostonská univerzita
Stabilní uvolnění	ATS2-0.4.2[1] / 14. listopadu 2020; Před 24 dny (2020-11-14)
Psací disciplína	statický
Licence	GPLv3
Přípony názvu souboru	.sats, .dats, klobouky.
webová stránka	http://www.ats-lang.org/
Ovlivněno
Závislé ML, ML, OCaml, C ++

ATS (Aplikovaný systém typů) je programovací jazyk určený ke sjednocení programování s formální specifikací. ATS má podporu pro kombinování dokazování věty s praktickým programováním pomocí pokročilých systémy typu.^[2] Minulá verze Srovnávací hra pro počítačový jazyk prokázal, že výkonnost ATS je srovnatelná s výkonností ATS C a C ++ programovací jazyky.^[3] Pomocí ověřování věty a přísné kontroly typu může kompilátor zjistit a dokázat, že jeho implementované funkce nejsou náchylné k chybám, jako je dělení nulou, úniky paměti, přetečení zásobníku a další formy poškození paměti ověřením aritmetika ukazatele a počítání referencí před sestavením programu. Navíc pomocí integrovaného systému ověřování teorémů ATS (ATS / LF) může programátor využít statické konstrukce, které jsou propleteny s operativním kódem, aby dokázal, že funkce dosahuje své specifikace.

Dějiny

ATS je odvozen převážně z ML a OCaml programovací jazyky. Starší jazyk, Závislé ML, od stejného autora, byla začleněna do jazyka.

Poslední verze ATS1 (Anairiats) byla vydána jako v0.2.12 dne 2015-01-20.^[4] První verze ATS2 (Postiats) byla vydána v září 2013.^[5]

Věta dokazující

Primárním zaměřením ATS je podpora dokazování věty v kombinaci s praktickým programováním.^[2] Pomocí dokazování věty lze například dokázat, že implementovaná funkce neprodukuje úniky paměti. Zabraňuje také dalším chybám, které by jinak mohly být nalezeny pouze během testování. Zahrnuje systém podobný těm z důkazní asistenti jejichž cílem je obvykle pouze ověřit matematické důkazy - kromě toho, že ATS využívá tuto schopnost k prokázání, že implementace jejích funkcí fungují správně, a vytváří očekávaný výstup.

Jako jednoduchý příklad může ve funkci používající dělení programátor dokázat, že dělitel se nikdy nebude rovnat nule, čímž zabrání a dělení nulou chyba. Řekněme, že dělitel „X“ byl vypočítán jako 5násobek délky seznamu „A“. Lze dokázat, že v případě neprázdného seznamu je „X“ nenulové, protože „X“ je součinem dvou nenulových čísel (5 a délka „A“). Praktičtějším příkladem by bylo prokázat se počítání referencí že počet zachování na přiděleném bloku paměti se počítá správně pro každý ukazatel. Pak lze vědět a doslova dokázat, že objekt nebude předčasně uvolněn, a to úniky paměti nenastane.

Výhodou systému ATS je, že jelikož se všechny věty dokazují striktně v kompilátoru, nemá to žádný vliv na rychlost spustitelného programu. Kód ATS je často těžší sestavit než standardně C kód, ale jakmile to zkompiluje, programátor si může být jistý, že běží správně do míry určené jejich důkazy (za předpokladu, že kompilátor a runtime systém jsou správné).

V ATS jsou důkazy oddělené od implementace, takže je možné implementovat funkci bez jejího prokázání, pokud si to programátor přeje.

Reprezentace dat

Podle autora (Hongwei Xi) je účinnost ATS^[6] je do značné míry způsobeno způsobem, jakým jsou údaje reprezentovány v jazyce a optimalizace koncového volání (které jsou obecně důležité pro účinnost funkčních programovacích jazyků). Data mohou být uložena v plochém nebo nebaleném zobrazení, nikoli v krabicovém zobrazení.

Věta Proving: Úvodní případ

Propozice

dataprop vyjadřuje predikáty tak jako algebraické typy.

Predikáty v pseudokódu poněkud podobné zdroji ATS (platný zdroj ATS viz níže):

 FAKT (n, r) iff    fakt (n) = r MUL (n, m, prod) iff    n * m = prod FACT (n, r) = FACT (0, 1) | FACT (n, r) iff FACT (n-1, r1) a MUL (n, r1, r) // pro n> 0 // vyjadřuje fakt (n) = r iff  r = n * r1 a r1 = fakt (n-1)

V kódu ATS:

 dataprop SKUTEČNOST (int, int) =   | FACTbas (0, 1)             // základní případ: SKUTEČNOST(0, 1)   | {n:int | n > 0} {r,R1:int} // induktivní případ     FACTind (n, r) z (SKUTEČNOST (n-1, R1), MUL (n, R1, r))

kde FACT (int, int) je typ důkazu

Příklad

Nekurkový rekurzivní faktoriál s propozicí nebo "Teorém "prokazování stavby dataprop.

Vyhodnocení fact1 (n-1) vrátí pár (proof_n_minus_1 | result_of_n_minus_1), který se použije při výpočtu fact1 (n). Důkazy vyjadřují predikáty tvrzení.

Část 1 (algoritmus a návrhy)

 [FACT (n, r)] implikuje [fakt (n) = r] [MUL (n, m, prod)] implikuje [n * m = prod]

 FACT (0, 1) FACT (n, r) iff FACT (n-1, r1) a MUL (n, r1, r) pro všechny n> 0

Pamatovat si:

{...} univerzální kvantifikace [...] existenční kvantifikace (... | ...) (důkaz | hodnota) @ (...) plochá n-tice nebo variadická funkce parametry n-tice. <...>. metrika ukončení[7]

#zahrnout „share / atspre_staload.hats“dataprop SKUTEČNOST (int, int) =  | FACTbas (0, 1) z () // základní případ  | {n:nat}{r:int}       // induktivní případ    FACTind (n+1, (n+1)*r) z (SKUTEČNOST (n, r))(* všimněte si, že int (x), také int x, je monovaluovaný typ hodnoty int x. Podpis funkce níže říká: forall n: nat, exists r: int where fact (num: int (n)) returns (FACT (n, r) | int (r)) *)zábava skutečnost{n:nat} .<n>. (n: int (n)) : [r:int] (SKUTEČNOST (n, r) | int(r)) =(  ifcase  | n > 0 => ((FACTind(pf1) | n * R1)) kde   {     val (pf1 | R1) = skutečnost (n-1)  }  | _(*jiný*) => (FACTbas() | 1))

Část 2 (rutiny a test)

nářadí main0 (argc, argv) ={  val () = -li (argc != 2) pak prerrln! („Použití:“, argv[0], „“)  val () = tvrdit (argc >= 2)  val n0 = g0string2int (argv[1])  val n0 = g1ofg0 (n0)  val () = tvrdit (n0 >= 0)  val (_(* pf *) | res) = skutečnost (n0)  val ((* neplatné *)) = tisk! ("skutečnost(", n0, ") = ", res)}

To vše lze přidat do jednoho souboru a zkompilovat následujícím způsobem. Kompilace by měla fungovat s různými překladači typu back-end C, např. gcc. Sběr odpadu se nepoužívá, pokud není výslovně uvedeno u -D_ATS_GCATS)^[8]

$ patscc fact1.dats -o fact1$ ./fact1 4

sestaví a dá očekávaný výsledek

Funkce

Základní typy

• bool (true, false)
• int (literály: 255, 0377, 0xFF), unární mínus jako ~ (jako v ML )
• dvojnásobek
• char 'a'
• řetězec "abc"

N-tice a záznamy

prefix @ nebo none znamená přímý, byt nebo unboxed alokace

  val X : @(int, char) = @(15, 'C')  // X.0 = 15 ; X.1 = 'C'  val @(A, b) = X                    // vzor vhodný vazba, A= 15, b='C'  val X = @{za prvé=15, druhý='C'}    // X.za prvé = 15  val @{za prvé=A, druhý=b} = X       // A= 15, b='C'  val @{druhý=b, ...} = X           // s vynechání, b='C'

prefix “znamená nepřímé nebo krabicové přidělení

  val X : '(int, char) = '(15, 'C')  // X.0 = 15 ; X.1 = 'C'  val '(A, b) = X                    // A= 15, b='C'  val X = '{za prvé=15, druhý='C'}    // X.za prvé = 15  val '{za prvé=A, druhý=b} = X       // A= 15, b='C'  val '{druhý=b, ...} = X           // b='C'

speciální

S '|' jako oddělovač některé funkce vrátí zabalené výslednou hodnotu s hodnocením predikátů

val (predicate_proofs | values) = myfunct params

Běžný

{...} univerzální kvantifikace [...] existenční kvantifikace (...) závorkový výraz nebo n-tice (... | ...) (důkazy | hodnoty)

. <...>. ukončení metrické @ (...) plochá n-tice nebo variadická funkce n-tice parametrů (viz příklady printf) @ [byte] [BUFLEN] typ pole BUFLEN hodnot typu byte[9]@ [byte] [BUFLEN] () instance pole @ [byte] [BUFLEN] (0) pole inicializované na 0

Slovník

třídit

doména

 sortdef nat = {A: int | A >= 0 }     // z předehra: ∀ ''A'' ∈ int ... typedef Tětiva = [A:nat] tětiva(A)   // [..]: ∃ ''A'' ∈ nat ...

typ (jako druh)

obecný třídit pro prvky s délkou ukazatele slova, které mají být použity v polymorfních funkcích parametrizovaných typem. Také „krabicové typy“^[10]

// {..}: ∀ a, b ∈ type ... fun {a, b: type} swap_type_type (xy: @ (a, b)): @ (b, a) = (xy.1, xy. 0)

typ

lineární verze předchozí typ s abstrahovanou délkou. Také nebalené typy.^[10]

typ zobrazení

doménová třída jako typ s Pohled (paměťová asociace)

viewt @ ype

lineární verze typ zobrazení s abstrahovanou délkou. Supersety typ zobrazení

Pohled

vztah typu a umístění paměti. Infix @ je jeho nejběžnější konstruktor

T @ L tvrdí, že v místě L je pohled na typ T

 zábava {A:t@ype} ptr_get0 {l:adresa} (pf: A @ l | str: ptr l): @(A @ l | A)  zábava {A:t@ype} ptr_set0 {l:adresa} (pf: A? @ l | str: ptr l, X: A): @(A @ l | prázdnota)

typ ptr_get0 (T) je ∀ l: addr. (T @ l | ptr (l)) -> (T @ l | T) // viz příručka, část 7.1. Bezpečný přístup do paměti pomocí ukazatelů^[11]

viewdef array_v (a: viewt @ ype, n: int, l: addr) = @ [a] [n] @ l

T?

možná neinicializovaný typ

úplnost odpovídající vzorům

jako v případ +, val +, zadejte +, viewtype +, ...

• s příponou '+' kompilátor vydá chybu v případě neúplných alternativ
• bez přípony kompilátor vydá varování
• s příponou „-“ vyhýbá se kontrole vyčerpání

moduly

 staload "foo.sats" // foo.sats je načten a poté otevřen do aktuálního jmenného prostoru staload F = "foo.sats" // pro použití identifikátorů kvalifikovaných jako $ F.bar dynload "foo.dats" // načteno dynamicky na run-time

zobrazení dat

Datové náhledy jsou často deklarovány k zakódování rekurzivně definovaných vztahů na lineárních zdrojích.^[12]

dataview array_v (a: viewt @ ype +, int, addr) = | {l: addr} array_v_none (a, 0, l) | {n: nat} {l: addr} array_v_some (a, n + 1, l) z (a @ l, array_v (a, n, l + velikost a))

datový typ / datový pohled

Typy dat^[13]

datový typ pracovní den = pondělí | Út | St | Čt | Pá

seznamy

datový typ list0 (a: t @ ype) = list0_cons (a) z (a, list0 a) | list0_nil (a)

typ datového zobrazení

Typ dataview je podobný datovému typu, ale je lineární. U dataviewtype je programátorovi dovoleno explicitně uvolnit (nebo uvolnit) bezpečným způsobem paměť používanou pro ukládání konstruktorů přidružených k dataviewtype.^[14]

proměnné

lokální proměnné

var res: int s pf_res = 1 // zavádí pf_res jako alias zobrazit @ (res)

na zásobníku alokace pole:

#define BUFLEN 10var! p_buf s pf_buf = @ [byte] [BUFLEN] (0) // pf_buf = @ [byte] [BUFLEN] (0) @ p_buf[15]

Vidět val a var prohlášení^[16]

Reference

externí odkazy

• Domovská stránka ATS
• Programovací jazyk ATS Dokumentace pro ATS2
• Programovací jazyk ATS Stará dokumentace pro ATS1
• Manuál Koncept (zastaralý). Některé příklady odkazují na funkce nebo rutiny, které nejsou ve verzi obsaženy (Anairiats-0.1.6) (např .: přetížení tisku pro strbuf a použití jeho příkladů pole dává errmsgs jako „použití předplatného pole není podporováno“.)
• ATS pro programátory ML
• Učící se příklady a krátké případy použití ATS