Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Семантика языка программирования

Семантика языков программирования

План

Стандартизация языков программирования

Семантика языков программирования

Процедурные языки программирования

Объектно-ориентированные языки программирования

Введение

Мнения о том, какой язык лучше преподавать, разнятся: от того, что программирование изучать не нужно, а следует просто поднимать компьютерную грамотность и осваивать офисные программы (как на Западе), до того, что нужно изучать операционные системы и несколько языков программирования различных уровней абстракции и с различными парадигмами. Это крайние случаи, но золотую середину найти непросто. В первую очередь, нам нужно определить цель. Научить логически и алгоритмически мыслить? Познакомить с компьютерами на бытовом уровне, чтобы Вы умели пользоваться интернетом, электропочтой и текстовыми редакторами? Заложить базовые знания, необходимые для будущих инженеров, математиков, физиков и специалистов по информационным технологиям? А может, нам нужно каждого познакомить с программированием как явлением, чтобы он представлял потенциал компьютерных систем? Много ли из нас станет программистами? Немного. Но синусами и уравнениями Кирхгофа в жизни тоже пользуется не каждый. Безусловно, в науке о программировании есть фундаментальная составляющая, но определить её не просто. Некоторые считают, что не так важно, какой язык программирования взять: на уроках информатики нужно учить не языку программирования, а методам программирования и системному подходу решения задач. Нужно развивать алгоритмическое мышление и на примерах знакомиться с принципами построения современных компьютерных систем. Неужели действительно не так важно, какая среда и какой конкретный язык программирования будет использован для практических занятий? Оказывается, что у каждого преподавателя есть свой список требований к учебному языку программирования. Например: простой, интуитивный синтаксис, наличие высокоуровневых инструментов для обнаружения и недопущения ошибок и для отладки программ, наличие качественной документации с примерами, наличие дружелюбной среды разработки, межплатформенность (наличие версий под различные платформы). У некоторых преподавателей этот список очень короткий, например: «Только Паскаль» или «Любой, кроме Бейсика!»

Стандартизация языков программирования

Язык программирования может быть представлен в виде набора спецификаций, определяющих его синтаксис и семантику.

Для многих широко распространённых языков программирования созданы международные стандарты. Специальные организации проводят регулярное обновление и публикацию спецификаций и формальных определений соответствующего языка. В рамках таких комитетов продолжается разработка и модернизация языков программирования и решаются вопросы о расширении или поддержке уже существующих и новых языковых конструкций.

Типы данных

Современные цифровые компьютеры обычно являются двоичными и данные хранят в двоичном (бинарном) коде (хотя возможны реализации и в других системах счисления). Эти данные как правило отражают информацию из реального мира (имена, банковские счета, измерения и др.), представляющую высокоуровневые концепции.

Особая система, по которой данные организуются в программе, — это система типов языка программирования; разработка и изучение систем типов известна под названием теория типов. Языки могут быть классифицированы как системы со статической типизацией и языки с динамической типизацией.

Статически-типизированные языки могут быть в дальнейшем подразделены на языки с обязательной декларацией, где каждая переменная и объявление функции имеет обязательное объявление типа, и языки с выводимыми типами. Иногда динамически-типизированные языки называются латентно-типизированными.

Структуры данных

Системы типов в языках высокого уровня позволяют определять сложные, составные типы, так называемые структуры данных. Как правило, структурные типы данных образуются как декартово произведение базовых (атомарных) типов и ранее определённых составных типов.

Основные структуры данных (списки, очереди, хеш-таблицы, двоичные деревья и пары) часто представлены особыми синтаксическими конструкциями в языках высокого уровня. Такие данные структурируются автоматически.

Семантика языков программирования

Существует несколько подходов к определению семантики языков программирования.

Наиболее широко распространены разновидности следующих трёх: операционного, денотационного (математического) и деривационного (аксиоматического).

При описании семантики в рамках операционного подхода обычно исполнение конструкций языка программирования интерпретируется с помощью некоторой воображаемой (абстрактной) ЭВМ.

Деривационная семантика описывает последствия выполнения конструкций языка с помощью языка логики и задания пред- и постусловий. Денотационная семантика оперирует понятиями, типичными для математики — множества, соответствия, а также суждения, утверждения и др.

Язык программирования строится в соответствии с той или иной базовой моделью вычислений и парадигмой программирования.

Несмотря на то, что большинство языков ориентировано на императивную модель вычислений, задаваемую фоннеймановской архитектурой ЭВМ, существуют и другие подходы. Можно упомянуть языки со стековой вычислительной моделью (Forth, Factor, Postscript и др.), а также функциональное (Лисп, Haskell, ML и др.) и логическое программирование (Пролог) и язык Рефал, основанный на модели вычислений, введённой советским математиком А.А. Марковым-младшим.

В настоящее время также активно развиваются проблемно-ориентированные, декларативные и визуальные языки программирования.

Большая Энциклопедия Нефти и Газа

Семантика — язык — программирование

Семантика языка программирования — это смысл, который закладывается в каждую конструкцию языка. Семантический анализ — это проверка смысловой правильности конструкции. Например, если в выражении используется переменная, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорит о допустимости операции с данной переменной. [1]

Изучение семантики языка программирования в своей основе связано с приписыванием значений компонентам программ. В общем случае значение каждой такой компоненты определяется как ее контекстом в данной программе, так и некоторым фиксированным способом ее означивания с помощью этой программы. Этот вопрос предполагает, что имеется соответствие, частично определяемое множеством процедур Р, между предикатными символами и некоторыми другими объектами, являющимися их значениями. Что же можно использовать в качестве таких объектов. Для вычислительной семантики очевидным выбором являются эффективно вычислимые отношения. Они разработали три различных вида семантики, в каждом из которых в качестве денотата предикатного символа определяется некоторое вычислимое отношение, и установили соотношения между ними. Если рассматривать опровержение как вычисление и заметить, что для порождения этих вычислений имеются такие системы вывода, как резолюция, то термин операционная семантика становится оправданным. Это определение операционной семантики аналогично традиционному способу задания семантик обычных языков программирования — а именно, посредством определения механизма исполнения ( как правило, на некоторой абстрактной машине) и объяснения затем значения программы, исходя из того, что вычисляется в результате применения к программе данного механизма. [2]

Синтаксис и семантика языка программирования должны соответствовать прикладной области. Отсутствие такого соответствия в универсальных языках требует дополнительных программных действий. [3]

Синтаксис и семантика языка программирования хранятся в такой системе в виде аксиом на языке исчисления предикатов. Система построения доказательств определяет выделенные пути в исследуемой программе и затем использует саму программу, утверждения и аксиомы для генерации условий верификации. Затем она использует правила вывода исчисления предикатов в сочетании с дедуктивными и эвристическими принципами рассуждения, пытаясь доказать каждое условие верификации. [4]

Способ описания семантики языков программирования посредством задания для каждой элементарной конструкции языка предусловий и аксиом, определяющих соответственно условия, необходимые для се применения, и условия, которые становятся истинными после ее применения. [5]

Читать еще:  Визуальные средства программирования

Формальным определением семантики языка программирования является языковой процессор. Языковой процессор — это программа или техническое устройство, выполняющие трансляцию или интерпретацию. [6]

Попытка единообразного систематического изложения семантики языков программирования вызвала немало трудностей, в частности терминологического характера. [7]

Единого общепринятого формального метода описания семантики языков программирования на сегодняшний день не существует. Описание языка обычно состоит из формального описания синтаксиса и неформального описания семантики языка. [8]

В доказательстве правильности программ и аксиоматической семантике языков программирования — логическое выражение, которое должно быть истинно после выполнения некоторого действия, если перед выполнением этого действия было истинно соответствующее предусловие. [9]

И наконец, должна быть определена семантика языка программирования . Семантика языка программирования — это набор правил, по которым исполнитель выполняет программы на этом языке. Пользуясь семантикой языка, можно однозначно определить результат выполнения программы с заданными входными данными. Более подробно с синтаксисом и семантикой мы будем знакомиться на примере конкретных языков программирования. [11]

И наконец, должна быть определена семантика языка программирования . Семантика языка программирования — это набор правил, по которым исполнитель выполняет программы на этом языке. Пользуясь семантикой языка, можно однозначно определить результат выполнения программы с заданными входными данными. Более подробно с синтаксисом и семантикой мы будем знакомиться на примере конкретных языков программирования. [13]

Чтобы сформулировать условия верификации, необходимо аксиоматическое описание семантики языка программирования . Гипотетический язык, на котором написана изображенная на рис. 17.2 программа, сводится к операторам двух типов ( присваивание и принятие решения), так что нужно описать, как должны изменяться утверждения при рассмотрении этих операторов. Эти аксиомы должны отвечать на такой вопрос: если некоторое утверждение истинно после оператора программы, какое утверждение должно быть истинным перед оператором. Другими словами, вы отменяете присваивание, заменяя в утверждении все вхождения переменной, указанной слева от знака присваивания, выражением справа. [14]

Основные области, охватываемые теорией программирования, связаны с семантикой языков программирования ( S. [15]

Семантика языков программирования.

Один из путей исследования взглядов на мир, навязываемых языками программирования, — это изучение семантики (смысла) языковых конструкций. Программирование при помощи конструкций некоторого языка требует мышления в терминах семантики этих конструкций. Таким образом, семантика служит ключом к пониманию процесса мышления программиста. Языки программирования можно разбить на три широкие категории в соответствии с природой семантики этих языков: 1) процедурные языки, 2) функциональные языки и 3) реляционные языки. Смысл конструкции процедурного языка определяется в терминах поведения компьютера при выполнении этой конструкции. Поведение может быть либо внешним (например, вывод сообщения на терминал), либо внутренним (например, изменение значения переменной). Смысл конструкции в функциональном языке (например, вызова функции) определяется в терминах значения, которое она вырабатывает. Вызов функции можно рассматривать как объявление вырабатываемого ею значения. Смысл конструкции в реляционном языке определяется как отношение между отдельными сущностями или классами сущностей. С декларативной точки зрения реляционную конструкцию можно интерпретировать как формулировку того, что существует отношение между аргументами, представленное именем этого отношения.

Уровень языка Предположим далее, что программист, приступающий к написанию программы, располагает логической спецификацией, в которой четко описана подлежащая решению задача или структура системы, которую необходимо представить. Это предположение позволяет провести классификацию взглядов на мир, навязываемых языками программирования, в соответствии с уровнем языка по отношению к заданной спецификации. Язык низкого уровня дает картину мира, близкую к взгляду на мир с позиций компьютера. Язык высокого уровня обеспечивает взгляд на мир, приближающийся к картине мира, представленной в спецификации задачи. Согласно этому критерию процедурные языки относятся к языкам низкого уровня. В соответствии с семантикой конструкций процедурного языка программист должен мыслить в терминах конструкций, определяющих поведение компьютера. При использовании процедурного языка требуется проведение большой работы по переводу спецификации сложной системы в работоспособную программу. Функциональные языки имеют более высокий уровень, чем процедурные, поскольку программист может мыслить в терминах вычисления значений, а не поведения ЭВМ. Сами же значения нередко являются частью спецификации. Реляционные языки имеют наивысший уровень, так как семантика конструкций реляционного языка весьма близка к спецификации задачи. Взгляд на мир для идеального реляционного языка будет таким же, как и взгляд на мир с позиций логической спецификации, поэтому для преобразования одного в другое понадобятся минимальные усилия. При использовании идеального реляционного языка становится возможным написание программы, структурно изоморфной по отношению к своей спецификации, т. е. для каждой вариации формы спецификации будет существовать соответствующая вариация формы программы.

Дата добавления: 2016-05-05 ; просмотров: 700 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Что означает семантика с точки зрения программирования?

учитывая эту неудачную ситуацию, это имеет смысл подчеркнуть хранение сначала механизм, а затем семантика второй.

легко получить словарь что означает «семантический», но что это означает с точки зрения компьютерного жаргона?

7 ответов

но что это значит с точки зрения компьютерного жаргона?

по сути то же самое. Пример:

выше синтаксис (представительство). The смысл (т. е. семантика) этого термина заключается в присвоении значения 5 символу (переменной, что угодно), называемому x . Разные языки предлагают разные синтаксисы для обеспечения одной и той же семантики. Например, вышеуказанное назначение будет написано as

в Паскале, и как

на нескольких других языках. Во всех случаях смысл по сути то же самое. Но иногда те же синтаксисы также могут иметь разные значения, в зависимости от языка и / или контекста. VB, например, переопределяет оператор equals, чтобы означать две разные вещи. Во-первых, задание, как и выше.

во-вторых, в следующем коде sippet, а не назначение, это принимает значение сравнение два значения:

семантика-это то, что мы подразумеваем под программой. Sytax — это языковое ограничение на то, как мы выражаем семантику.

теоретически, пока семантика программы верна, не имеет значения, какой язык использовался для ее написания.

применяется определение словаря.

семантика есть (есть?) все о значении слов.

например, если вы используете тип .NET KeyValuePair для представления чего-то другого, кроме ключа и значения, у вас есть семантическая проблема. Это может сработать. это может быть лучшим решением, но оно не является семантически точным.

Это именно то, о чем он говорит в этом сообщении в блоге. Сначала мы перечисляем типы возврата на C-подобных языках, но на самом деле возвращается последний. Это семантически неточно.

в терминах жаргона языка программирования существует несколько понятий семантики:

статическая семантика говорит вам, какие программы, которые являются грамматическими, также хорошо сформированы. Многие языки либо не имеют статической семантики (Scheme, Ruby, Python, Icon, Lua, Perl), либо имеют статическую семантику, которая в первую очередь связана с реализацией введите system (Java, C, C#, Haskell). «Объявление, требуемое перед использованием» — это еще одна возможная статика семантика. Статическая семантика отвечает на вопрос «имеет ли эта программа смысл?» и делает это во время компиляции.

Читать еще:  Не работает безопасный режим

динамическая семантика говорит вам одну из двух вещей:

  • учитывая, что программа имеет смысл, что это значит?смысл был определен математически многими, многими различными способами. Классическая динамическая семантика может определять функцию (или отношение) между программами входы и выходы программы. Смысловые функции («денотационная семантика») были пионерами даны Скоттом и Кристофером Стрейчи; смысловые отношения («аксиоматическая семантика») были пионерами Тони хора. Скотт и Хоэр получили награды Тьюринга; Стрейчи, вероятно, получил бы, но он умер молодым. Хороший способ познакомиться — прочитать книгу Тони хора Очерки по информатике.
  • учитывая, что программа имеет смысл, как он будет вести себя, когда казнен?. Этот вид семантики обычно называют «операционной семантикой» и описывает выполнение программы на какой-то абстрактной машине. Опять же, существует много, много разновидностей. Сегодня операционная семантика является инструментом выбора, потому что существуют мощные методы доказательства, поэтому, например, используя операционную семантику, вы можете доказать, что в управляемом коде никогда нет ошибки памяти. Робин Милнер получил его премия Тьюринга частично для различных операционных методы, используемые для описания параллельных или многопоточных программ (CCS и исчисление pi). Его книга 1999 года на коммуникационные и мобильные системы также очень хорошо читать, если вы пропустите доказательства: -)

Если Вы читаете слово «семантика» в руководстве или статье, и контекст является неофициальным английским, а не точным математическим описанием, автор, вероятно, имеет в виду динамическое операционное поведение-если хотите, операционное семантика описывается неформально. Такое неформальное описание может быть весьма полезным для составителей компиляторов и программистов.

Как я понимаю, семантика-это «то, что все это значит для человека». Это что это часть, а не как он это делает.

немного больше контекста блог:

поэтому в C вы кладете хранение сначала метаданные (static int customerCount;), а не сначала семантика (это могло быть var customerCount: static int;).

Он говорит, что «static int» появляется перед «customerCount». Вызов «static int»хранилища метаданных и «customerCount» семантика. The хранилища метаданных информация о переменная неявно содержит в себе то, сколько битов она занимает, какие значения она может иметь, является ли она общей для экземпляров и ее волатильность.

на семантика, имя переменной, является информацией для читателей кода о том, что должно храниться в переменной. Какая переменная означает. Вы можете назвать это» x», и программа будет работать так же хорошо, но программисту будет трудно понять это. Назвав его «customerCount» предоставляет переменной значение, и это семантика.

другими словами, учитывая контекст статьи, он говорит, что было бы лучше для разработчиков C# сосредоточиться на том, как они будут хранить данные внутри, когда переменная была объявлена, и не заботиться о том, чтобы указать точный метод объявления переменной.

другими словами, делая это в C#

вы говорите компилятору подготовить хранилище для статически доступного целого числа, а затем говорите ему чтобы обозначить это хранилище как customerCount

тогда как в VB вы бы использовали эту строку

говоря компилятору, теоретически, что у вас есть переменная customerCount что он должен хранить и делать статически доступным, и, кстати, это, оказывается, целое число.

это все действительно тонкая грань различия вроде вещи.

Семантика языков программирования

Транскрипт

1 Семантика языков программирования В данной лекции будут рассмотрены вопросы, относящиеся к понятийному аппарату, истории развития, существующим подходам и выразительным возможностям семантического представления формальных теорий и языков программирования.

2 Содержание лекции 1. Понятие семантики в математике и программировании 2. Виды семантик. Возможные подходы к исследованию семантики 3. Средства формализации семантики 4. Теория вычислений Д. Скотта. Конструкторы доменов 5. Синтаксис базовых конструкций SML 6. Денотационная семантика базовых конструкций SML 7. Библиография В ходе лекции будут рассмотрены важнейшие научные исследования, относящиеся к эволюции подходов к математическому моделированию семантического представления формальных теорий и языков программирования. При этом будет предпринята попытка классификации существующих видов семантики. Далее будет представлено неформальное введение в наиболее адекватный целям данного курса и достаточно широко распространенный на сегодня подход к семантике, а именно, так называемый денотационный подход. Теоретические рассуждения о семантике в формальных теориях (на примере теории вычислений Д.Скотта) будут проиллюстрированы представлением денотационной семантики подмножества языка программирования SML, ограниченного наиболее важными, основополагающими конструкциями. При этом существенное внимание будет также уделено сопоставлению и сравнительному анализу синтаксического и семантического аспектов наиболее важных с точки зрения программирования классов конструкций языка программирования SML. Лекция завершится обзором литературы для более глубокого исследования материала.

3 Важнейшие работы в области семантики (1) 1960-е Х. Барендрегт (H. Barendregt) описал семантику ламбда-исчисления 1969 Д. Скотт (Dana S. Scott) предложил использовать домены (особый вид множеств) для формализации денотационной семантики как функции вычисления значения синтаксически корректных конструкций языка 1979 М. Гордон (Michael J.C. Gordon) исследовал денотационную семантику языков программирования Кратко остановимся на наиболее значительных (с точки зрения данного курса) этапах эволюции теории и практики семантического анализа языков программирования. В 60-х г.г. Х. Барендрегтом (H. Barendregt) была детально описана семантика ламбдаисчисления математической формализации, поддерживающей языки функционального программирования. Позднее, в конце 60-х г.г., Д. Скоттом (Dana S. Scott) было предложено использовать для формализации семантики математических теорий так называемые домены (пока будем неформально понимать их как особый вид множеств). При этом на основе доменов Д. Скоттом был предложен так называемый денотационный подход к семантике. Такой подход предполагает анализ синтаксически корректных конструкций языка (или, иначе, денотатов) с точки зрения возможности вычисления их значений посредством специализированных функций. Далее, в 70-х г.г., М. Гордоном (Michael J.C. Gordon) был исследован аппарат денотационной семантики применительно к языкам функционального программирования и сделал вывод об адекватности и практической эффективности применения этого подхода для решения поставленной задачи.

4 Важнейшие работы в области семантики (2) 1964 П. Лендин (Peter J. Landin) разработал семантику модели языка программирования в форме абстрактной машины на состояниях 1969 Ч. Хоар (Charles A.R. Hoare) создал аксиоматический метод, моделирующий операторы языка программирования 1960-е Р. Флойд (Robert W. Floyd) создал метод индуктивных утверждений для формализации семантики протекания информации в программе (графическая иллюстрация — блок-схемы) Параллельным направлением изучения семантики был подход, исследовавший изменения, которые происходили в процессе работы программы на основе отслеживания смены состояний программы. Одним из практических результатов работ в этом направлении стала разработка П. Лендином (Peter J. Landin) семантики модели языка программирования в форме абстрактной машины, существенно использовавшей понятие состояния. Альтернативный подход к формализации семантики (который был осуществлен в рамках исследования так называемой операционной семантики языков программирования) привел к созданию Ч. Хоаром (Charles A.R. Hoare) аксиоматического метода, моделирующего отношения и причинно-следственные связи, возникающие между операторами языка программирования. Развитие операционной семантики языков программирования привело Р. Флойда (Robert W. Floyd) к созданию так называемого метода индуктивных утверждений, который использовался для формализации семантики протекания информации в программе. При этом существенным преимуществом предложенного Р. Флойдом метода стала возможность интуитивно прозрачной и наглядной графической иллюстрации, основанной на блок-схемах, формализующих последовательность протекания информации.

Читать еще:  Программирование диалога с компьютером

5 Общие требования к описанию языков программирования 1) полнота: синтаксис и семантика всех допустимых конструкций должны быть описаны без пропусков; 2) ясность: удобочитаемость, легкость и результативность поиска ответов на вопросы; 3) естественность: интуитивная близость пользователю, использование стандартных обозначений; 4) реализм: учет ограничений на объем оперативной памяти, время реакции и т.д. Перейдем к рассмотрению неформальной семантики языков программирования. Для построения адекватной и удобной в использовании семантики необходимо, прежде всего, определить критерии, характеризующие «хороший» язык программирования. Попытаемся сформулировать обобщенные требования, предъявляемые к описанию языков программирования. Во-первых, необходимо потребовать от языка программирования соблюдения принципа полноты, т.е. оснастить язык программирования таким набором конструкций, который позволяет описать синтаксис (и семантику) всех допустимых конструкций языка без пропусков существенных аспектов. Во-вторых, язык программирования должен удовлетворять интуитивному требованию ясности, а именно, объективно обеспечивать удобочитаемость программ, а также легкость и результативность поиска ответов на вопросы, возникающие в процессе разработки программных проектов. Немаловажной характеристикой языка программирования является естественность, под которой мы будем понимать интуитивную близость языка к терминологии разработчика, а также использование унифицированных, стандартных, привычных обозначений. Наконец, необходимо учитывать и такой важный параметр, как реализм, который понимается как учет естественных ограничений на среду реализации языка программирования, а именно: объем оперативной памяти, время реакции и целый ряд других существенных факторов.

6 Общие сведения о семантике (1) Семантикой называется интерпретация (т.е. смысловое значение) абстрактного синтаксиса (т.е. множества допустимых конструкций языка), выраженное в терминах той или иной математически строгой модели. Основные подходы к семантике: 1) ориентированные на компиляцию (семантика множество преобразований над синтаксической моделью); 2) ориентированные на интерпретацию (семантика множество описанных на метаязыке преобразований синтаксически правильных языковых конструкций). После обсуждения обобщенных и концептуально важных требований к языкам программирования в целом, перейдем к неформальному обсуждению семантического подхода, способного обеспечить реализацию этих требований. Прежде всего, расширим наивное представление о семантике языка программирования (или формальной теории) хотя и предварительным, но более конкретным определением этого понятия. Семантикой будем называть интерпретацию (или, иначе, смысловое значение) абстрактного синтаксиса (а точнее, множества допустимых видов конструкций языка), представленное в терминах той или иной математически строгой формальной модели. Как оказывается, все многообразие возможных подходов к семантике можно в основном представить всего двумя типами семантик, а именно, семантиками, ориентированными на компиляцию и семантиками, ориентированными на интерпретацию. В дальнейшем под подходами к семантике, ориентированными на компиляцию, будем понимать такие подходы, в которых семантика представляет собой множество преобразований над синтаксической моделью в той или иной форме. В отличие от предыдущего подхода, под подходами к семантике, ориентированными на интерпретацию, будем понимать такие подходы, в которых семантика представляет собой множество описанных на специально построенном метаязыке преобразований синтаксически правильных конструкций языка программирования.

7 Общие сведения о семантике (2) Виды семантик, ориентированные на интерпретацию: 1) Операционные (смысл конструкций языка в терминах переходов абстрактной машины из одного состояния в другое), например, SECD-машина П. Лендина; 2) Пропозиционные (смысл конструкций языка в терминах множества формул, описывающих состояния объектов программы), например, подходы Хоара и Флойда; 3) Денотационные (смысл конструкций языка в терминах абстракции функций на состояниях программы), например, теория семантических доменов Д. Скотта. Сразу заметим, что целям нашего курса в большей степени соответствует второй подход, как более универсальный в силу того обстоятельства, что в нем используется метатеория, т.е. формализация, моделирующая преобразования текста программ. Выделим основные направления, существующие в рамках подхода к семантике, ориентированного на интерпретацию и свяжем их с рассмотренными нами в ходе лекции направлениями исследований. Оказывается, что существуют три основных вида семантик, ориентированных на интерпретацию. Во-первых, необходимо упомянуть об операционных семантиках. Значение конструкций языка в таких семантиках выражается в терминах переходов той или иной абстрактной машины из одного состояния в другое. В качестве показательных примеров абстрактных машин можно привести, в частности, так называемую SECD-машину П. Лендина, а также категориальную абстрактную машину. Обе формализации будут рассмотрены подробнее в ходе дальнейших лекций. Другим типом семантик, ориентированных на интерпретацию, являются так называемые пропозиционные семантики. В отличие от операционных семантик, значение конструкций языка в таких семантиках выражается в терминах множества формул, описывающих состояния объектов программы. В качестве примеров можно, привести, в частности, аксиоматический метод Хоара и метод индуктивных утверждений Флойда. Наконец, наиболее значимым для нас типом семантик, ориентированных на интерпретацию, являются денотационные семантики, в которых смысл конструкций языка представляется в терминах абстракции функций, оперирующих состояниями программы. В частности, данный подход иллюстрирует теория вычислений Д. Скотта, основанная на семантических доменах, которую и предлагаем вашему вниманию.

8 Теория вычислений Д. Скотта Создана в 1969 г. для непротиворечивой формализации семантики языков на основе алгебры доменов аналогов множеств, адекватно моделирующих самоприменимые функции и множества. Последовательность построения теории: 1) перечисление стандартных (наиболее часто используемых) доменов; 2) определение конечных доменов с явно перечисляемыми элементами ; 3) определение конструкторов (способов комбинирования) доменов. Напомним, что теория вычислений Д. Скотта была создана до появления большинства современных языков программирования, а именно в конце 60-х г.г. Существенно, что именно эта теория (в отличие от, скажем, классической логики и ряда других формальных систем) позволяет произвести адекватную (а именно, полную и непротиворечивую) формализацию семантики языков программирования. Теория вычислений Д. Скотта основана на фундаментальном понятии домена, который будем пока неформально понимать как некоторый аналог множества, впрочем, в отличие от традиционных множеств, адекватно формализующий рекурсивно (т.е. на основе самоприменения) определенные функции и множества. Сформулируем последовательность изложения теории вычислений Д. Скотта. Для построения теории вычислений необходимо, во-первых, перечислить так называемые стандартные, или, точнее, наиболее часто используемые в рамках данной формализации, домены. После перечисления стандартных доменов необходимо определить так называемые конечные домены, или, точнее, домены, элементы которых возможно перечислить явным образом. Наконец, после перечисления доменов перейдем к определению конструкторов доменов, под которыми понимаются операции построения новых доменов на основе имеющихся, или, иначе, определим способы комбинирования доменов.

9 Конструкторы доменов 1) Функциональное пространство: [D 1 D 2 ]=; 2) Декартово произведение домен всевозможных n-ок: [D 1 D 2 D n ]=<(d 1 d 2 d n ) d 1 D 1, d 2 D 2,d n, D n >; 3) Последовательность D*- домен всех конечных последовательностей вида d=(d 1,d 2,,d n ) из элементов d 1,d 2,,d n, домена D, где n>0; 4) Дизъюнктная сумма [D 1 +D 2 + +D n ]=<(d i,i) d i D i, 0 0. Наконец, под дизъюнктной суммой будем понимать домен с определением [D 1 +D 2 + +D n ]=< (d i, i) d i D i, 0 I agree.

Ссылка на основную публикацию
Adblock
detector