Stroj SECD - SECD machine

Stroj SECD je velmi vlivný ( viz: § Landinův příspěvek ) virtuální stroj a abstraktní stroj určený jako cíl pro kompilátory funkčního programovacího jazyka . Písmena znamenají S tack, E nvironment, C ontrol, D ump - interní registry stroje. Registry Stack, Control a Dump ukazují na (některé realizace) zásobníků a prostředí ukazuje na (některé realizace) asociativního pole .

Stroj byl první, který byl speciálně navržen pro vyhodnocení výrazů lambda kalkulu . Původně jej popsal Peter J. Landin v „The Mechanical Evaluation of Expressions“ v roce 1964. Popis publikovaný Landinem byl poměrně abstraktní a nechal mnoho možností implementace otevřených (jako operační sémantika ).

Lispkit Lisp byl vlivný překladač založený na stroji SECD a stroj SECD byl použit jako cíl pro jiné systémy, jako je Lisp / 370. V roce 1989 vědci z University of Calgary pracovali na hardwarové implementaci stroje.

Landinův příspěvek

DA Turner (2012) zdůrazňuje, že Revidovaná zpráva o Algolu 60 ( Naur 1963) specifikuje volání procedury kopírovacím pravidlem, které se vyhne zachycení proměnné se systematickou změnou identifikátorů. Tato metoda funguje v implementaci Algol 60, ale ve funkčním programovacím jazyce, kde jsou funkce občany první třídy, může být omylem dereferencována volná proměnná v zásobníku volání.

Turner podotýká, že Landin to vyřešil svým strojem SECD, ve kterém je funkce namísto toho představována uzavřením v haldě.

Neformální popis

Když začíná vyhodnocení výrazu, je výraz načten jako jediný prvek kontroly C. Prostředí E, zásobník Sa výpis Dzačínají prázdnými.

Během vyhodnocení Cse převede na reverzní polskou notaci (RPN), přičemž ap(pro použití ) je jediným operátorem. Například výraz F (G X)(jeden prvek seznamu) se změní na seznam X:G:ap:F:ap.

Hodnocení Cvýnosů obdobně jako u jiných výrazů RPN. Pokud je první položka v Chodnotě, je vložena do zásobníku S. Přesněji řečeno, pokud je položka identifikátor, hodnota vložená do zásobníku bude vazbou pro tento identifikátor v aktuálním prostředí E. Pokud je položka abstrakcí, je uzávěr konstruován tak, aby zachoval vazby jeho volných proměnných (které jsou v E), a právě tento uzávěr je vložen do zásobníku.

Pokud položka je ap, dvě hodnoty se vyskočí ze zásobníku a aplikace je hotová (nejprve aplikována na druhou). Pokud je výsledkem aplikace hodnota, je vložena do zásobníku.

Pokud je aplikace abstrakce k hodnotě, bude to mít za následek výraz lambda kalkulu, který může sám o sobě být aplikací (spíše než hodnotou), a proto jej nelze vložit do zásobníku. V tomto případě je aktuální obsah S, Ea Cjsou tlačeny na skládku D(což je stoh těchto trojic), Sje opět spuštěn vyprázdnit, a Cje opět spuštěn na výsledek aplikace s Eobsahem prostředí pro volné proměnné tohoto výrazu, rozšířeno o vazbu, která vyplynula z aplikace. Vyhodnocení pak pokračuje, jak je uvedeno výše.

Dokončené vyhodnocení je označeno Cprázdným, v takovém případě bude výsledek na zásobníku S. Poté se zobrazí poslední uložený stav vyhodnocení Da výsledek dokončeného vyhodnocení se vloží do obsahu zásobníku obnoveného z D. Vyhodnocení obnoveného stavu pak pokračuje, jak je uvedeno výše.

Pokud Ca Djsou oba prázdné, celkové hodnocení bylo dokončeno s výsledkem v zásobníku S.

Registry a paměť

Stroj SECD je založen na zásobníku . Funkce berou své argumenty ze zásobníku. Argumenty předdefinovaných pokynů jsou zakódovány bezprostředně za nimi v proudu instrukcí.

Stejně jako všechny interní datové struktury je i zásobník seznam, jehož Sregistr směřuje k hlavě nebo začátku seznamu. Kvůli struktuře seznamu nemusí být zásobník souvislým blokem paměti, takže prostor zásobníku je k dispozici, pokud existuje jedna volná buňka paměti. I když byly použity všechny buňky, odvoz odpadu mohou poskytnout další volné paměti. Je zřejmé, že konkrétní implementace struktury SECD mohou implementovat zásobník jako kanonickou strukturu zásobníku, čímž se zlepší celková účinnost virtuálního stroje, za předpokladu, že bude na rozměr zásobníku přidán přísný limit.

K Cregistru ukazuje na čele seznamu kódů nebo návodu, které budou hodnoceny. Jakmile je instrukce tam provedena, Cje namířena na další instrukci v seznamu - je to podobné jako u instrukčního ukazatele (nebo počítadla programu ) na konvenčních strojích, kromě toho, že následující instrukce jsou vždy specifikovány během provádění a nejsou standardně obsaženy v následujících paměťových místech, jako je tomu u konvenčních strojů.

Aktuální prostředí proměnné je spravováno Eregistrem, který ukazuje na seznam seznamů. Každý jednotlivý seznam představuje jednu úroveň prostředí: parametry aktuální funkce jsou v záhlaví seznamu, proměnné, které jsou v aktuální funkci volné, ale jsou vázány okolní funkcí, jsou v jiných prvcích E.

Výpis, na jehož hlavě Dregistr směřuje, se používá jako dočasné úložiště pro hodnoty ostatních registrů, například během volání funkce. Lze to přirovnat k zpětnému zásobníku jiných strojů.

Organizace paměti stroje SECD je podobná modelu používanému většinou tlumočníků funkčních jazyků : řada paměťových buněk, z nichž každá může obsahovat buď atom (jednoduchá hodnota, například 13 ), nebo představuje prázdný nebo ne- prázdný seznam. V druhém případě buňka obsahuje dva ukazatele na jiné buňky, jeden představuje první prvek a druhý představuje seznam s výjimkou prvního prvku. Tyto dva ukazatele jsou tradičně pojmenovány auto a cdr - ale místo toho se často používají modernější výrazy hlava a ocas . Různé typy hodnot, které může buňka obsahovat, se liší podle značky . Často se také rozlišují různé typy atomů (celá čísla, řetězce atd.).

Takže seznam obsahující čísla 1 , 2 a 3 , obvykle psaný jako (1 2 3), může být reprezentován následovně: 

Address   Tag       Content (value for integers, car & cdr for lists)

      9 [ integer |     2 ]
      8 [ integer |     3 ]
      7 [ list    | 8 | 0 ]
      6 [ list    | 9 | 7 ]
      ...
      2 [ list    | 1 | 6 ]
      1 [ integer |     1 ]
      0 [ nil             ]

Paměťové buňky 3 až 5 nepatří do našeho seznamu, jejichž buňky lze náhodně distribuovat po paměti. Buňka 2 je hlavičkou seznamu, ukazuje na buňku 1, která obsahuje hodnotu prvního prvku, a seznam obsahující pouze 2 a 3 (počínaje buňkou 6). Buňka 6 ukazuje na buňku obsahující 2 a na buňku 7, což představuje seznam obsahující pouze 3 . Dělá to tak, že ukazuje na buňku 8 obsahující hodnotu 3 a ukazuje na prázdný seznam ( nil ) jako cdr. V zařízení SECD buňka 0 vždy implicitně představuje prázdný seznam, takže k signalizaci prázdného seznamu není potřeba žádná speciální hodnota značky (vše, co potřebuje, může jednoduše ukazovat na buňku 0).

Princip, že cdr v buňce seznamu musí ukazovat na jiný seznam, je pouze konvence. Pokud auto i cdr ukazují na atomy, získá se pár, obvykle psaný jako(1 . 2)

Instrukce

  • nil tlačí nulový ukazatel do zásobníku
  • ldc vloží do zásobníku konstantní argument
  • ldvloží hodnotu proměnné do zásobníku. Proměnná je označena argumentem, dvojicí. Auto páru určuje úroveň, cdr pozici. Takže (1 . 3)dává třetí parametr aktuální funkce (úroveň 1).
  • seločekává dva argumenty seznamu a zobrazí hodnotu ze zásobníku. První seznam je proveden, pokud vyskakovací hodnota byla nenulová, druhý seznam jinak. Předtím, než je jeden z těchto ukazatelů seznamu nový C, je na výpis uložen ukazatel na následující instrukci .
  • joinobjeví odkaz na výpis z výpisu a udělá z toho novou hodnotu C. Tato instrukce se vyskytuje na konci obou alternativ a sel.
  • ldfpřebírá jeden argument seznamu představující funkci. Vytvoří uzávěr (pár obsahující funkci a aktuální prostředí) a posune jej do zásobníku.
  • apobjeví uzavření a seznam hodnot parametrů ze zásobníku. Uzávěr se použije na parametry instalací jeho prostředí jako aktuálního, posunutím seznamu parametrů před tím, vymazáním zásobníku a nastavením Cukazatele funkce uzávěru. Předcházející hodnoty S, Ea další hodnoty Cjsou ukládány na skládku.
  • retobjeví jednu návratovou hodnotu ze zásobníku, obnoví S, Ea Cz výpisu, a vrátí návratovou hodnotu do nyní aktuálního zásobníku.
  • dum posune před seznam prostředí „fiktivní“, prázdný seznam.
  • rapfunguje jako , pouze že nahrazuje výskyt fiktivního prostředí současným, což umožňuje rekurzivní funkce

Existuje řada dalších pokynů pro základní funkce, jako je auto, cdr, konstrukce seznamu, přidání celého čísla, I / O atd. Všichni berou všechny potřebné parametry ze zásobníku.

Viz také

Reference

Další čtení

externí odkazy