Жоғары реттік абстрактілі синтаксис: Айтмалы түйіндерді ұсыну тәсілі
Higher-order abstract syntax
Жоғары реттік абстрактілі синтаксис (HOAS) – байланыстыратын айнымалылары бар тілдердегі абстрактілі синтаксис ағаштарын ұсыну әдісі. Программалау, компиляторлар үшін маңызды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда жоғары реттік абстрактілік синтаксис (қысқартылып HOAS) – айнымалыларды байланыстыратын тілдер үшін абстрактілік синтаксистік ағаштарды ұсыну тәсілі.
In computer science, higher order abstract syntax (abbreviated HOAS) is a technique for the representation of abstract syntax trees for languages with variable binders.
Бірінші реттік абстрактілік синтаксиспен байланысы
Абстрактты синтаксис абстрактты, өйткені ол өз табиғаты бойынша белгілі бір құрылымы бар математикалық объектілермен бейнеленеді. Мысалы, бірінші реттік абстрактілік синтаксис (FOAS) ағаштарында, көбінесе компиляторларда қолданылатындай, ағаш құрылымы қосымша өрнек қатынасын білдіреді, яғни бағдарламаларды нақтылау үшін жақшалар қажет емес (конкретті синтаксисте). HOAS қосымша құрылымды көрсетеді: айнымалылар мен олардың байланысқан жерлері арасындағы қатынас. FOAS ұсынылымдарында айнымалы әдетте идентификатормен бейнеленеді, байланысқан жер мен қолданылу арасындағы байланыс бірдей идентификаторды пайдалану арқылы көрсетіледі. HOAS-та айнымалының аты жоқ; айнымалының әрбір қолданылуы тікелей байланысқан жерге сілтеме жасайды. Бұл техниканың пайдалы болуының бірнеше себебі бар. Біріншіден, ол бағдарламаның байланыс құрылымын нақтылайды: FOAS ұсынылымында операторлардың басымдығын түсіндірудің қажеті жоқ болғандай, HOAS ұсынымын түсіндіру үшін байланыс және ауқым ережелерін білудің қажеті жоқ. Екіншіден, альфа эквивалентті (тек байланысқан айнымалылардың аттарымен ғана ерекшеленетін) бағдарламалар HOAS-та бірдей ұсынылады, бұл эквиваленттілікті тексеруді тиімдірек етеді.
An abstract syntax is abstract because it is represented by mathematical objects that have certain structure by their very nature. For instance, in first order abstract syntax (FOAS) trees, as commonly used in compilers, the tree structure implies the subexpression relation, meaning that no parentheses are required to disambiguate programs (as they are, in the concrete syntax). HOAS exposes additional structure: the relationship between variables and their binding sites. In FOAS representations, a variable is typically represented with an identifier, with the relation between binding site and use being indicated by using the same identifier. With HOAS, there is no name for the variable; each use of the variable refers directly to the binding site. There are a number of reasons why this technique is useful. First, it makes the binding structure of a program explicit: just as there is no need to explain operator precedence in a FOAS representation, there is no need to have the rules of binding and scope at hand to interpret a HOAS representation. Second, programs that are
alpha equivalent (differing only in the names of bound variables) have identical representations in HOAS, which can make equivalence checking more efficient.
Іске асыру
HOAS-ты іске асыруға болатын математикалық нысан – айнымалылары қабырғалар арқылы байланыс орындарымен байланыстырылған граф. HOAS-ты іске асырудың тағы бір кең таралған тәсілі (мысалы, компиляторларда) – де Брюйн индекстерін пайдалану.
One mathematical object that could be used to implement HOAS is a graph where variables are associated with their binding sites via edges. Another popular way to implement HOAS (in, for example, compilers) is with de Bruijn indices.