Plankalkül - Plankalkül - Wikipedia

Plankalkül (Německá výslovnost: [ˈPlaːnkalkyːl]) je programovací jazyk navržen pro technické účely autorem Konrad Zuse mezi lety 1942 a 1945. Byla první programovací jazyk na vysoké úrovni být určen pro počítač.

Kalkül je Němec termín pro a formální systém -jako v Hilbert-Kalkül, původní název pro Dedukční systém ve stylu Hilberta -tak Plankalkül odkazuje na formální systém plánování.^[3]

Dějiny

V oblasti vytváření výpočetních strojů byl Zuse samouk a vyvíjel je bez znalosti dalších existujících mechanických výpočetních strojů. Aby popsal logické obvody, vynalezl Zuse svůj vlastní diagram a notační systém, který nazval „kombinatorika kondicionálů“ (Němec: Bedingungskombinatorik). Po dokončení Z1 v roce 1938 Zuse zjistil, že počet, který nezávisle vymyslel, již existuje a je znám jako výrokový kalkul.^[4] To, co měl Zuse na mysli, však muselo být mnohem silnější (výrokový kalkul není) Turing-kompletní a není schopen popsat ani jednoduché aritmetické výpočty^[5]). V květnu 1939 popsal své plány na rozvoj toho, co by se stalo Plankalkül.^[6] Do svého poznámkového bloku napsal:

Stůl na domě v Hinterstein [de ] kde Zuse pracoval na Plankalkül

Během své disertační práce vyvinul Zuse první známý formální systém notace algoritmů^[7] schopné manipulovat s větvemi a smyčkami.^[8][9] V roce 1942 začal psát a šachy program v Plankalkül.^[10] V roce 1944 se Zuse setkal s německým logikem a filozofem Heinrich Scholz, který vyjádřil uznání za využití Zuse logický počet.^[11] V roce 1945 popsal Zuse Plankalkül v nepublikované knize.^[12] Kolaps nacistické Německo mu však znemožnil předložit svůj rukopis.^[8]

V té době byly na světě pouze dva fungující počítače ENIAC a Harvard Mark I., žádný z nich nepoužíval kompilátor a ENIAC nebylo nutné přeprogramovat pro každý úkol změnou připojení vodičů.^[13]

Ačkoli většina jeho počítačů byla zničena spojeneckými bombami, Zuse dokázal zachránit jeden stroj, Z4 a přesuňte jej do alpské vesnice Hinterstein^[14] (část Bad Hindelang ).

Úplně poprvé se pokusil navrhnout algoritmický jazyk v roce 1948 K. Zuse. Jeho zápis byl docela obecný, ale návrh nikdy nedosáhl úvahy, kterou si zaslouží.

— Heinz Rutishauser, tvůrce ALGOL

Nelze pokračovat ve stavbě počítačů - což bylo také zakázáno spojeneckými mocnostmi^[15] - Zuse věnoval svůj čas vývoji programovacího modelu a jazyka na vyšší úrovni.^[8] V roce 1948 vydal příspěvek v Archiv der Mathematik a představeny na výročním zasedání Evropské komise GAMM.^[16] Jeho práce nedokázala přilákat větší pozornost.^{[Citace je zapotřebí ]} Na přednášce z roku 1957 vyjádřil Zuse naději, že Plankalkül „po nějaké době jako Spící kráska, ještě ožije. “^{[Citace je zapotřebí ]} Vyjádřil zklamání, že návrháři ALGOL 58 nikdy neuznali vliv Plankalkülu na jejich vlastní práci.^[8][17]

Plankalkül byl publikován komplexněji^{[vágní ]} v roce 1972. První kompilátor implementoval Joachim Hohmann ve své disertační práci z roku 1975.^[18] Další nezávislé implementace následovaly v roce 1998^[19] a 2000 na Svobodná univerzita v Berlíně.^[20]

Popis

Plankalkül vypracoval srovnání s jazykem APL a do relační algebra. Zahrnuje příkazy k zadání, podprogramy podmíněné příkazy, iterace, plovoucí bod aritmetika, pole, hierarchické struktury záznamů, tvrzení, zpracování výjimek a další pokročilé funkce, jako je cílené provedení. Plankalkül poskytuje datovou strukturu s názvem zobecněný graf (verallgemeinerter Graf), které lze použít k reprezentaci geometrických struktur.^[21]

Plankalkül sdílel idiosynkratický zápis pomocí více řádků s Frege je Begriffsschrift z roku 1879 (jednání s matematická logika ).^{[je zapotřebí objasnění ]}

Některé vlastnosti Plankalkül:^[22]

• pouze lokální proměnné
• funkce nepodporují rekurzi
• pouze podporuje volání podle hodnoty
• kompozitní typy jsou pole a n-tice
• obsahuje podmíněné výrazy
• obsahuje smyčku for a while
• Ne jít do

Typy dat

Jediným primitivním datovým typem v Plankalkül je jediný bit nebo booleovský (Němec: Ja-Nein-Werte - ano-ne hodnota v terminologii Zuses). Je označen identifikátorem ${ displaystyle S0}$. Všechny další datové typy jsou složené a vytvářejí se z primitiv pomocí „polí“ a „záznamů“.^[23]

Posloupnost osmi bitů (což lze v moderních počítačích považovat za byte ) je označen ${ displaystyle 8 krát S0}$a booleovská matice velikosti ${ displaystyle m}$ podle ${ displaystyle n}$ popisuje ${ Displaystyle m krát n krát S0}$. Existuje také zkrácená notace, takže se dá psát ${ displaystyle S1 cdot n}$ namísto ${ displaystyle n krát S0}$.^[23]

Typ ${ displaystyle S0}$ může mít dvě možné hodnoty ${ displaystyle 0}$ a ${ displaystyle L}$. 4bitovou sekvenci lze tedy zapsat jako L00L, ale v případech, kdy taková sekvence představuje číslo, může programátor použít desítkové vyjádření 9.^[23]

Záznam dvou složek ${ displaystyle sigma}$ a ${ displaystyle tau}$ je psán jako ${ displaystyle ( sigma, tau)}$.^[23]

Typ (Němec: Umění) v Plankalkül se skládá ze 3 prvků: strukturovaná hodnota (Němec: Struktur), pragmatický význam (Němec: Typ) a možné omezení možných hodnot (Němec: Beschränkung).^[23] Uživatelem definované typy jsou označeny písmenem A s číslem, jako ${ displaystyle A1}$ - první uživatelsky definovaný typ.

Příklady

Zuse použil mnoho příkladů z šachové teorie^[24]:

${ displaystyle A1}$	${ displaystyle S1 cdot 3}$	Souřadnice šachovnice (má velikost 8x8, takže stačí 3 bity)
${ displaystyle A2}$	${ displaystyle 2 krát A1}$	čtverec desky (například L00, 00L označuje e2 v algebraická notace )
${ displaystyle A3}$	${ displaystyle S1 cdot 4}$	kus (například 00L0 - bílý král)
${ displaystyle A4}$	${ displaystyle (A2, A3)}$	kus na desce (například L00, 00L; 00L0 - bílý král na e2)
${ displaystyle A5}$	${ displaystyle 64 krát A3}$	deska (pozice kusů, popisuje, který kousek obsahuje každý ze 64 čtverců)
${ displaystyle A10}$	${ displaystyle (A5, S0, S1 cdot 4, A2)}$	stav hry (${ displaystyle A5}$ - prkno, ${ displaystyle S0}$ - kdo se pohybuje, ${ displaystyle S1 cdot 4}$ - možnost rošády (2 pro bílou a 2 pro černou), A2 - informace o buňce, na které En passant tah je možný

Identifikátory

Identifikátory jsou alfanumerické znaky s číslem.^[23] U proměnných existují následující druhy identifikátorů ^[25]:

• Vstupní hodnoty (Němec: Eingabewerte, Variablen) - označeno písmenem V.
• Indermediate, dočasné hodnoty (Němec: Zwischenwerte) - označeno písmenem Z.
• Konstanty (Němec: Constanten) - označeno písmenem С.
• Výstupní hodnoty (Němec: Resultatwerte) - označeno písmenem R.

Konkrétní proměnná nějakého druhu je identifikována číslem zapsaným pod druhem.^[23] Například:

${ displaystyle { begin {matrix} V 0 end {matrix}}}$, ${ displaystyle { begin {matrix} Z 2 end {matrix}}}$, ${ displaystyle { begin {matrix} C 31 end {matrix}}}$ atd.

Programy a podprogramy jsou označeny písmenem P, následovaným číslem programu (a volitelně podprogramu). Například ${ displaystyle P13}$, ${ displaystyle P5 cdot 7}$.^[23]

Výstupní hodnota programu ${ displaystyle P13}$ uloženy tam v proměnné ${ displaystyle { begin {matrix} R 0 end {matrix}}}$ je k dispozici pro ostatní podprogramy pod identifikátorem ${ displaystyle { begin {matrix} R17 0 end {matrix}}}$a hodnota pro čtení této proměnné také znamená provedení souvisejícího podprogramu.^[24]

Přístup k prvkům pomocí indexu

Plankalkül umožňuje přístup k samostatným prvkům proměnné pomocí „indexu komponent“ (Němec: Komponenten-Index). Když například program přijímá vstup do proměnné ${ displaystyle { begin {matrix} V 0 end {matrix}}}$ typu ${ displaystyle A10}$ (stav hry) ${ displaystyle { begin {matrix} V 0 0 end {matrix}}}$ - udává stav desky, ${ displaystyle { begin {matrix} V 0 0 cdot i end {matrix}}}$ - kus na čtvercovém čísle i a ${ displaystyle { begin {matrix} V 0 0 cdot i cdot j end {matrix}}}$ bitové číslo j tohoto kusu.^[24]

V moderních programovacích jazycích by to bylo popsáno podobným zápisem V0 [0], V0 [0] [i], V0 [0] [i] [j] (i když pro přístup k jednomu bitu v moderních programovacích jazycích a bitová maska se obvykle používá).

Dvojrozměrná syntaxe

Protože indexy proměnných se zapisují svisle, vyžaduje každá instrukce Plankalkül několik řádků k zápisu.

První řádek obsahuje druh proměnné, poté číslo proměnné označené písmenem V (Němec: Variablen-index), poté indexy proměnných dílčích složek označené K (Němec: Komponenten-Index), a pak (Němec: Strukturální index) označené písmenem S, které popisuje typ proměnné. Typ není vyžadován, ale Zuse poznamenává, že to pomáhá při čtení a porozumění programu.^[26]

V řadě ${ displaystyle S}$ typy ${ displaystyle S0}$ a ${ displaystyle S1}$ lze zkrátit na ${ displaystyle 0}$ a ${ displaystyle 1}$. ^[26]

Příklady:

${ displaystyle { begin {pole} {r | l} & V V & 3 K & S & m krát 2 krát 1 cdot n end {pole}}}$	proměnná V3 - seznam ${ displaystyle m}$ páry hodnot typu ${ displaystyle S1 cdot n}$
${ displaystyle { begin {pole} {r | l} & V V & 3 S & m krát 2 krát 1 cdot n end {pole}}}$	Řádek K lze přeskočit, když je prázdný. Proto tento výraz znamená totéž jako výše.
${ displaystyle { begin {pole} {r | l} & V V & 3 K & i cdot 0 cdot 7 S & 0 end {pole}}}$	Hodnota osmibitového (index 7), prvního (index 0) páru, i-tého prvku proměnné V3, má logický typ (${ displaystyle S0}$).

Indexy mohou být nejen konstanty. Proměnné lze použít jako indexy pro jiné proměnné, a to je označeno řádkem, který ukazuje, ve kterém indexu komponenty by hodnota proměnné byla použita:

Z5-tý prvek proměnné V3. Ekvivalent k výrazu V3 [Z5] v mnoha moderních programovacích jazycích.[26]

Operace přiřazení

Zuse představil ve svém operátoru počtu, neznámém pro matematiku před ním - zadání. Označil to «${ displaystyle Rightarrow}$», A nazval jej výnos-znaménko (Němec: Ergibt-Zeichen). Použití konceptu úkolu je jedním z klíčových rozdílů mezi matematikou a informatikou.^[27]

Zuse napsal tento výraz:

${ displaystyle { begin {pole} {r | lll} & Z + 1 & Rightarrow & Z V & 1 && 1 end {pole}}}$

je analogický s tradičnější matematickou rovnicí:

${ displaystyle { begin {pole} {r | lll} & Z + 1 & = & Z V & 1 && 1 K & i && i + 1 end {pole}}}$

Existuje názor, že Konrad Zuse původně používal pro přiřazení znamení , a začal používat ${ displaystyle Rightarrow}$ pod vlivem Heinz Rutishauser.^[26] Knuth a Pardo věří, že Zuse vždy psal ${ displaystyle Rightarrow}$, a byl představen vydavateli «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben».^[27] Na ALGOL 58 konference v Curychu, evropští účastníci navrhli použít pro přiřazení charakter představený Zuseem, ale americká delegace trvala na :=.^[26]

Proměnná, která ukládá výsledek přiřazení (l-hodnota ) je zapsán na pravou stranu operátora přiřazení.^[27] První přiřazení proměnné se považuje za deklaraci.^[26]

Pro výraz se používá levá strana operátoru přiřazení (Němec: Ausdruck), který definuje, která hodnota bude přiřazena proměnné. Výrazy mohou používat aritmetické operátory, logické operátory a operátory porovnání (${ displaystyle =, neq, leq}$ atd.).^[28]

Operace umocňování se zapisuje podobně jako operace indexování - pomocí řádků ve 2D zápisu^[29]:

Řízení toku

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Září 2020)

Terminologie

Zuse nazval jediný program a Rechenplan ("výpočetní plán"). Představoval si, co nazýval a Planfertigungsgerät („zařízení pro sestavení plánu“), které by automaticky převedlo matematickou formulaci programu do strojově čitelného děrovaný filmový materiál.^[30]

Příklad

Původní notace byla dvojrozměrná.^{[je zapotřebí objasnění ]} Pro pozdější implementaci v 90. letech byla vyvinuta lineární notace.

Následující příklad definuje funkci max3 (v lineárním přepisu), který vypočítá maximálně tři proměnné:

P1 max3 (V0 [: 8,0], V1 [: 8,0], V2 [: 8,0]) → R0 [: 8,0] max. (V0 [: 8,0], V1 [: 8,0]) → Z1 [: 8,0] max (Z1 [: 8,0], V2 [: 8,0]) → R0 [: 8,0] ENDP2 max (V0 [: 8,0], V1 [: 8,0]) → R0 [: 8,0] V0 [: 8,0] → Z1 [: 8,0] ( Z1 [: 8,0] 
Viz také
Historie programovacích jazyků
Časová osa programovacích jazyků
Seznam programovacích jazyků
Poznámky
^ „Early Programming Languages ​​/ CS208e: Great Ideas in Computer Science“ (PDF).
^ Rojas, Raúl; Hashagen, Ulf (2002). První počítače: historie a architektury. MIT Stiskněte. p. 292. ISBN  978-0262681377. Citováno 25. října 2013.
^ Hector Zenil (ed.), 2012. A Computable Universe: Understanding and Exploring Nature as Computation with a Foreword by Sir Roger Penrose. Singapur: Světová vědecká nakladatelská společnost. Stránka 791.
^ A b Rojas a kol. 2004, str. 3.
^ „Proč není Turingova logika úplná?“.
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. p. 216.
^ Knuth & Pardo 1976, str. 9
^ A b C d Giloi 1997
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. p. 56.
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. p. 216 217.
^ Hartmut Petzold,Moderne Rechenkünstler. Die Industrialisierung der Rechentechnik v Německu. Mnichov. C.H. Beck Verlag 1992
^ (plný text rukopisu z roku 1945)
^ Rojas a kol. 2000, str. 3.
^ Knuth & Pardo 1976, str. 8
^ Wolfgang Coy: Byl ist Informatik? Zur Entstehung des Faches an den deutschen Universitäten, v: Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. p. 474.
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. p. 89.
^ Knuth & Pardo 1976, str. 15
^ Joachim Hohmann: Der Plankalkül im Vergleich mit algorithmischen Sprachen. Reihe Informatik und Operations Research, S. Toeche-Mittler Verlag, Darmstadt 1979, ISBN  3-87820-028-5.
^ Popis kompilátoru Plankalkül od Wolfganga Mauerera
^ Rojas a kol. 2000, str. 2.
^ Prof. Wolfgang Giloi [de ]: Konrad Zuses Plankalkül als Vorläufer moderner Programmiermodelle, listopad 1990
^ Hans Dieter Hellige (ed.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. p. 217.
^ A b C d E F G h Bauer & Wössner 1972, str. 679.
^ A b C Bauer & Wössner 1972, str. 680.
^ Zuse 1945, str. 10. chyba sfn: žádný cíl: CITEREFZuse1945 (Pomoc)
^ A b C d E F Bauer & Wössner 1972, str. 681.
^ A b C Knuth & Pardo 1976, str. 14.
^ Bauer & Wössner 1972, str. 682.
^ Zuse 1945, str. 45. chyba sfn: žádný cíl: CITEREFZuse1945 (Pomoc)
^ Hellige, Hans Dieter, Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlín, Springer 2004, ISBN  3-540-00217-0. 45, 104, 105
Reference
Giloi, Wolfgang (1997). „Plankalkül Konrada Zuse: První programovací jazyk na vysoké úrovni„ mimo von Neumanna “. IEEE Annals of the History of Computing. 19 (2): 17–24. doi:10.1109/85.586068.
Knuth, Donald Ervin; Pardo, Luis Trabb (1976), Počáteční vývoj programovacích jazyků (PDF), Stanford University, Katedra informatiky, archivovány od originál (PDF) dne 12. 9. 2017, vyvoláno 2017-12-28
Zuse, Konrad (1943), „Ansätze einer Theorie des allgemeinen Rechnens unter besonderer Berücksichtigung des Aussagenkalküls und dessen Anwendung auf Relaisschaltungen“, (tj. Vznik univerzální teorie výpočtu se zvláštním zřetelem na výrokový počet a jeho aplikace na reléové obvody.) nepublikovaný rukopis, Zuse Papers 045/018.
Zuse, Konrad (1948/49). „Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben“. Oblouk. Matematika. 1, s. 441–449, 1948/49.
Zuse, Konrad (1972). „Der Plankalkül“. Gesellschaft für Mathematik und Datenverarbeitung. Č. 63, BMBW - GMD - 63, 1972.
Bauer, Friedrich L.; Wössner, Hans (1972). „Plankalkül“ Konrada Zuse: předchůdce dnešních programovacích jazyků (PDF). Archivovány od originál (pdf) dne 20. 2. 2009. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: ref = harv (odkaz)(HTML verze )
Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike (2000). Plankalkül: První programovací jazyk na vysoké úrovni a jeho implementace (PDF). Archivovány od originál dne 01.05.2006.CS1 maint: ref = harv (odkaz)
Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike; Scharf, Ludmila (2004). Konrad Zuses Plankalkül - Seine Genese und eine moderne Implementierung (PDF). doi:10.1007/978-3-642-18631-8_9. Archivovány od originál (PDF) dne 01.05.2006.CS1 maint: ref = harv (odkaz)
externí odkazy
„Plankalkül“ Konrada Zuse: Předchůdce dnešních programovacích jazyků podle Friedrich L. Bauer (alternativní zdroj )
Rojas, Raúl, et al. (2000). „Plankalkül: První programovací jazyk na vysoké úrovni a jeho implementace“. Institut für Informatik, Freie Universität Berlin, technická zpráva B-3/2000. (celý text)(archivováno)
Mauerer, Wolfgang (06.06.2016). „Der Plankalkül von Konrad Zuse“ (v němčině). Implementace v němčině. Archivovány od originál dne 2016-06-03. Citováno 2017-10-03.
„Plankalkül“. Internetový archiv Konrada Zuse. Archivovaná stránka s Java applety Plankalkül (nefunguje) a několika dokumenty (německy / anglicky). 21. 8. 2014. Archivovány od originál dne 21. 8. 2014. Citováno 2017-10-04.CS1 maint: ostatní (odkaz)
Bram Bruines: Plankalkul (2010) - Plankalkül popsán formálně