Действия как основа семантики программирования: подход Уатта и Моссеса.
Action semantics
Действия семантики: формальная спецификация семантики языков программирования. Объединяет денотационную, операционную и алгебраическую семантику, масштабируемость и модифицируемость.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Семантика действий — это фреймворк для формальной спецификации семантики языков программирования, изобретенный Дэвидом Уаттом и Питером Д. Моссом в 1990-х годах. Она представляет собой сочетание денотационной, операционной и алгебраической семантики. Семантика действий стремится быть прагматичной, а описания семантики действий (ASD) разработаны для масштабирования и обработки реалистичных языков программирования. Этому способствует расширяемость и модифицируемость ASD, что помогает гарантировать, что расширения и изменения не потребуют слишком большого количества изменений в описании. Это отличается от типичной ситуации при расширении денотационной или операционной семантики, которая может потребовать переформулировки всего описания. Фреймворк семантики действий был первоначально разработан в Университете Орхуса и Университете Глазго. С тех пор группы и отдельные исследователи по всему миру внесли свой вклад в развитие этого подхода.
Action semantics is a framework for the formal specification of semantics of programming languages invented by David Watt and Peter D. Mosses in the 1990s. It is a mixture of denotational, operational and algebraic semantics. Action semantics aim to be pragmatic, and action semantic descriptions (ASDs) are designed to scale up to handle realistic programming languages. This is aided by the extensibility and modifiability of ASDs. This helps to ensure that extensions and changes do not require too many changes in the description. This is in contrast to the typical case when extending denotational or operational semantics, which may require reformulation of the entire description. The action semantics framework was originally developed at the University of Aarhus and the University of Glasgow. Groups and individuals around the world have since contributed further to the approach.
Семантические сущности
Важной частью семантики действий, которая обеспечивает ей модульность, не свойственную семантике предыдущих языков программирования, является использование семантических сущностей первого порядка. Под первым порядком понимается то, что, в отличие от денотационной семантики, где семантическая функция может быть применена к другой семантической функции, в семантике действий семантическая сущность не может быть применена к другой сущности того же типа. Более того, семантические сущности, используемые в семантике действий, расширяют возможности фреймворка по описанию конструкций языка программирования, позволяя обозначать как поведение программы, не зависящее от конкретной реализации, так и влияние частей программы на общую производительность целого. Для выражения трех типов семантических сущностей, используемых в семантике действий – действий, данных и генераторов – используется соответствующая нотация действий. Центральной семантической сущностью в этом фреймворке являются действия, в то время как данные и генераторы играют вспомогательную роль. В частности, действия являются механизмами, посредством которых обрабатываются генераторы и данные. Действие, которое может происходить внутри другого действия, представляет собой пошаговое представление поведения программы, где каждый шаг получает доступ к текущей информации, изменяет её или делает и то, и другое. Генераторы появляются внутри действий и получают доступ только к текущей информации. Сущность генератора может быть вычислена, и результатом вычисления является сущность данных.
An important part of action semantics that gives it a modularity not seen in previous programming language semantics is the use of first order semantic entities. First order refers to how, unlike in denotational semantics, where a semantic function can be applied to another semantic function, in action semantics, a semantic entity cannot be applied to another semantic entity of its kind. Furthermore, the semantic entities utilized by action semantics broaden the framework’s ability to describe a programming language’s constructs by serving to denote both program behavior that is independent of any particular implementation and the way in which parts of a program influence the overall performance of the whole. The appropriately named action notation is employed to express the three types of semantic entities found in action semantics: actions, data, and yielders. The central semantic entity in this framework is actions, with data and yielders occupying supplementary roles. More specifically, actions are the mechanisms through which yielders and data are processed. An action, which can occur within another action, is a step by step representation of program behavior, where each step accesses current information, changes current information, or does both. Yielders appear within actions and only access current information. A yielder entity is capable of being evaluated, and when it is, the product is a datum entity.
Субъекты действий
Субъекты действия могут непосредственно представлять семантику программ, описывая возможное поведение программы, или представлять более косвенным образом влияние, которое отдельные части программы, такие как операторы или выражения, оказывают на семантику программы в целом. Они моделируют вычислительное поведение, указывая на изменения состояния посредством генерации новых значений из переданных. В частности, действие принимает данные, переданные ему через текущую информацию – временные данные, полученные связывания и текущее состояние памяти, – и на основе этого генерирует новые временные данные, создает новые связывания, обновляет состояние памяти или любую их комбинацию. Сущность действия может завершиться четырьмя способами: успешно завершиться (нормальное завершение), прерваться (завершение с исключением), не выполниться (альтернатива отклонена) или зациклиться (не завершиться). Существует четыре категории информации, обрабатываемой при выполнении действия. Временная информация соответствует промежуточным результатам и доступна для немедленного использования действием. Данные, составляющие временную информацию, включают значения, полученные выражениями. Если эти значения не используются немедленно, они теряются. Областная информация соответствует таблицам символов и может быть использована в любом месте внутри действия и его поддействий. Также возможно скрыть такую информацию внутри поддействия, создав внутреннюю область видимости, в этом случае она будет доступна только локально в этой области для данного поддействия. Стабильная информация соответствует значениям, присвоенным переменным, и может быть изменена в процессе выполнения действия. Поскольку изменения в памяти во время выполнения действия являются постоянными, только явные действия могут вызывать такие модификации. Соответственно, стабильная информация доступна до тех пор, пока она не будет явно уничтожена. И, в отличие от областной информации, её нельзя скрыть. Постоянная информация соответствует данным, обмениваемым между действиями, и может быть расширена, но не изменена. Временная информация генерируется только при успешном завершении или прерывании действия, а областная – только при успешном завершении. Изменение стабильной информации и расширение постоянной информации должны происходить в процессе выполнения действия. Сущность действия имеет пять различных граней: одна для обработки, не зависящей от информации, и четыре для обработки каждого из четырех типов информации. Базовая грань, примером которой являются потоки управления, не связана с информацией какого-либо рода. Функциональная грань обрабатывает временную информацию и характеризуется действиями, передающими и принимающими данные. Декларативная грань обрабатывает областную информацию и характеризуется действиями, создающими и получающими связывания. Императивная грань обрабатывает стабильную информацию и характеризуется действиями, выделяющими и освобождающими ячейки памяти, а также извлекающими и изменяющими хранящиеся в них данные. Коммуникативная грань обрабатывает постоянную информацию и характеризуется действиями отправки и получения сообщений и «предложения контрактов агентам». Существуют два типа действий с точки зрения их влияния на информацию в каждой грани. Примитивные действия влияют на информацию только в одной грани. Комбинаторы действий позволяют создавать действия, включающие несколько граней, определяя, как управляются и передаются данные для каждой грани, участвующей в комбинированном действии. При комбинировании действий комбинаторы действий управляют последовательностью выполнения поддействий и входящими и исходящими потоками данных для каждого поддействия.
Action entities can directly represent programs’ semantics by describing possible program behaviors or represent, in a more indirect way, the impact that individual pieces of a program, like statements or expressions, have on the semantics of the program as a whole. They model computational behavior by indicating changes in state through their generation of new values from passed values. Specifically, an action accepts data passed to it via the current information — the transient data given to it, the bindings received by it, and the current state of storage — and, from this, gives new transient data, creates new bindings, updates the state of storage, or any combination of these. An action entity can culminate in four possible ways. It can: complete (terminate normally), escape (terminate in an exception), fail (alternative is discarded), or diverge (not terminate). There are four categories of information that are processed by action performance. Transient information corresponds to intermediate results and is accessible for immediate use by the action. The data that comprises transient information encompasses the values given by expressions. If these values are not immediately used, they are lost. Scoped information corresponds to symbol tables and can be referenced from anywhere within the action and its sub actions. It is also possible for such information to be hidden within a sub action, via the creation of an inner scope, in which case it would be only locally accessible within that scope, to that sub action. Stable information corresponds to values assigned to variables and can be modified in the action performance. Because alterations to storage during the performance of an action are persistent, only explicit actions can cause such modifications. In accordance with this, stable information is available until it is explicitly destroyed. And, unlike scoped information, it cannot be hidden. Permanent information corresponds to data exchanged between actions and can be extended but not modified. Transient information is produced only when an action completes or escapes, and scoped information is produced only when an action completes. The modification of stable information and the extension of permanent information must take place during action performance. An action entity has five different facets, one for processing that does not rely on information, and four for processing each of the four different types of information. The basic facet, an example of which would be control flows, is not tied to information of any kind. The functional facet deals with the processing of transient information and is characterized by actions giving and accepting data. The declarative facet deals with the processing of scoped information and is characterized by actions creating and receiving bindings. The imperative facet deals with the processing of stable information and is characterized by actions allocating and freeing storage cells, and fetching and modifying the data stored in them. The communicative facet deals with processing permanent information and is characterized by actions sending and receiving messages and “offer[ing] contracts to agents.” There are two different kinds of actions in terms of their effect on the information in each facet. Primitive actions only affect the information in one facet. Action combinators permit actions that involve multiple facets, governing how control and information flows for each facet involved in a combined action. In combining actions, action combinators governor the sequencing of sub action performances and the incoming and outgoing flows of data for each sub action.
Субъекты данных
Сущности данных – это элементы, составляющие информацию, обрабатываемую сущностями действия. Данные организованы в структуры, известные как сорта. Сорты – это множества математических объектов, включающие операции, которые могут быть выполнены над этими объектами, и определяются на основе алгебраических критериев. Эти структуры обеспечивают доступ к каждой отдельной сущности. Примеры сущностей данных могут включать конкретные элементы, такие как отображения, списки, множества, строки, символы, числа и логические значения, а также более абстрактные элементы, используемые исключительно для целей вычислительной операции, а именно доступа к данным, такие как агенты, ячейки памяти и токены, или элементы, такие как контракты и сообщения, являющиеся составными компонентами данных. Абстракция – это сущность данных, инкапсулирующая сущность действия, в этом случае выполнение абстракции приводит к выполнению действия. Это метод, с помощью которого семантика действий представляет объявление и вызов подпрограмм.
Data entities are the items that comprise the information processed in action entities. The data is arranged into structures known as sorts. Sorts are sets of mathematical objects, include operations that can be performed on those objects, and are defined according to algebraic criteria. These structures allow access to each individual entity. Examples of data entities can include concrete elements like maps, lists, sets, strings, characters, numbers, and truth values, more abstract elements used solely for the purpose of some computational operation, namely data access, like agents, cells corresponding to memory locations, and tokens, or elements like contracts and messages that are a composite of data components. An abstraction is a data entity that encapsulates an action entity, in which case enacting the abstraction results in the action being performed. This is the technique by which action semantics represents the declaring and invoking of subprograms.
Субъекты доходности
Сущности-генераторы состоят из неоцененных объемов данных. Значения этих объемов зависят от текущей информации и состояния вычислений. Генераторы используют временные данные, связи и хранилище для выбора информации, подлежащей обработке действиями. Оценка генераторов происходит в процессе выполнения действий, и результатом оценки являются сущности данных. Хотя текущая информация может влиять на данные, полученные при оценке сущности-генератора, сама оценка не может влиять на текущую информацию. Применение операций с данными к сущностям-генераторам может привести к формированию составных сущностей-генераторов.
Yielder entities consist of unevaluated quantities of data. The values of these quantities are contingent on the current information and state of computation. Yielders draw on transient data, bindings, and storage to select the information to be processed by actions. It is during action performance that yielders are evaluated, and their evaluation results in data entities. While the current information can influence the data produced by the evaluation of a yielder entity, the evaluation cannot influence the current information. If data operations are employed on yielder entities, compound yielder entities may be formed as a result.
Обозначение действия
Обычные английские слова используются в качестве символов в нотации действий. Нотация действий разработана для имитации естественного языка, что отражается в частях речи, используемых для обозначения семантических единиц. Действия представлены глагольными фразами, а данные и результаты – именными фразами. Благодаря такому выбору символов, эта система отличается высокой читаемостью и не уступает в формальности другим системам, поскольку остаётся чётко определённой.
Regular English words serve as the symbols of action notation. Action notation is designed to simulate natural language, which is illustrated in the parts of speech used to denote semantic entities. Action entities are represented by verb phrases and data and yielder entities by noun phrases. The result of this choice of symbols is a framework that is highly readable and no less formal than other frameworks since it remains precisely defined.
Другие ключевые аспекты
Семантика действий воплощает уровень абстракции, повышающий её понятность. Специфика потоков управления и данных, связанных с действием, неявно содержится в самом действии, в отличие от явного выражения деталей семантических функций, как это делается в денотационной семантике. При выполнении действия большая часть обработки и манипулирования информацией происходит автоматически. Программные конструкции сопоставляются с действиями при построении определения семантики языка программирования в рамках семантики действий. Исполнение программной конструкции соответствует выполнению действия, которому она сопоставлена. Спецификация языка программирования, полученная с помощью семантики действий, может быть разделена на нижний уровень (микросемантика) и верхний уровень (макросемантика). Нижний уровень определяет значение обозначений действий, а верхний уровень определяет значение языка программирования, используя эти обозначения.
Action semantics embodies a level of abstraction that increases its comprehensibility. The specifics of the control and data flows that an action involves are implicitly incorporated in the action, as opposed to being explicitly expressed as the details of semantic functions are in denotational semantics. When an action is performed, most information processing and manipulation occurs automatically. Program phrases are mapped to actions when constructing a definition of a programming language’s meaning in action semantics. The execution of a programming phrase corresponds to the performance of the action to which it maps. The programming language specification generated from the application of action semantics can be broken down into a lower level (microsemantics) and an upper level (macrosemantics). The lower level consists of defining the meaning of action notation, while the upper level consists of defining the meaning of a programming language, using action notation to do so.