Теория языка программирования - Programming language theory
Теория языков программирования ( PLT ) - это раздел информатики, который занимается проектированием, реализацией, анализом, характеристикой и классификацией формальных языков, известных как языки программирования, и их индивидуальных особенностей . Это относится к дисциплине информатики, как зависящей от математики , программной инженерии , лингвистики и даже когнитивных наук , так и влияющих на них . Это стало широко признанной отраслью информатики и активной областью исследований, результаты которой публикуются в многочисленных журналах, посвященных PLT, а также в общих публикациях по информатике и инженерии.
История
В некотором смысле история теории языков программирования предшествует даже развитию самих языков программирования. Лямбда - исчисление , разработанное Алонзо церкви и Клини в 1930 году , по мнению некоторых , чтобы быть первым в мире язык программирования, даже если он был предназначен для модели вычислений , а не быть средством для программистов описывать алгоритмы компьютерной системы . Многие современные языки функционального программирования были описаны как обеспечивающие «тонкую оболочку» над лямбда-исчислением, и многие из них легко описываются с его помощью.
Первым языком программирования , который был изобретен, был Plankalkül , который был разработан Конрадом Цузе в 1940-х годах, но не был публично известен до 1972 года (и не был реализован до 1998 года). Первым широко известным и успешным языком программирования высокого уровня был Fortran , разработанный с 1954 по 1957 год группой исследователей IBM под руководством Джона Бэкуса . Успех FORTRAN привел к формированию комитета ученых для разработки «универсального» компьютерного языка; Результатом их усилий стал АЛГОЛ 58 . Отдельно Джон Маккарти из Массачусетского технологического института разработал Lisp , первый успешный язык с академическими корнями. Благодаря успеху этих первоначальных усилий языки программирования стали активной темой исследований в 1960-х годах и позже.
Некоторые другие ключевые события в истории теории языков программирования с тех пор:
1950-е годы
- Ноам Хомский разработал иерархию Хомского в области лингвистики, открытие, которое напрямую повлияло на теорию языков программирования и другие отрасли информатики.
1960-е
- Язык Simula был разработан Оле-Йоханом Далем и Кристен Найгаард ; он широко считается первым примером объектно-ориентированного языка программирования ; Simula также представила концепцию сопрограмм .
- В 1964 году Питер Лэндин первым понял, что лямбда-исчисление Черча можно использовать для моделирования языков программирования. Он представляет машину SECD, которая «интерпретирует» лямбда-выражения.
- В 1965 году Ландин вводит оператор J , по сути, форму продолжения .
- В 1966 году Ландин представляет ISWIM , абстрактный язык программирования для компьютеров, в своей статье «Следующие 700 языков программирования» . Он играет важную роль в разработке языков, ведущих к языку программирования Haskell .
- В 1966 году Коррадо Бем представил язык программирования CUCH (Curry-Church).
- В 1967 году Кристофер Стрейчи публикует свой влиятельный набор конспектов лекций « Фундаментальные концепции языков программирования» , вводя терминологию R-значения , L-значения , параметрический полиморфизм и специальный полиморфизм .
- В 1969 году Дж. Роджер Хиндли публикует « Основную схему типов объекта в комбинаторной логике» , позже обобщенную в алгоритм вывода типов Хиндли – Милнера .
- В 1969 году Тони Хоар вводит логику Хора , форму аксиоматической семантики .
- В 1969 году Уильям Элвин Ховард заметил, что «высокоуровневую» систему доказательств , называемую естественным выводом , можно напрямую интерпретировать в своей интуиционистской версии как типизированный вариант модели вычислений, известной как лямбда-исчисление . Это стало известно как переписка Карри – Ховарда .
1970-е
- В 1970 году Дана Скотт впервые публикует свою работу по денотационной семантике .
- В 1972 году были разработаны логическое программирование и Пролог, что позволило выражать компьютерные программы в виде математической логики.
- Команда ученых из Xerox PARC во главе с Аланом Кей разрабатывает Smalltalk , объектно-ориентированный язык, широко известный своей инновационной средой разработки.
- В 1974 году Джон С. Рейнольдс обнаруживает System F . Он был открыт еще в 1971 году математиком-логиком Жан-Ивом Жираром .
- С 1975 года Джеральд Джей Сассман и Гай Стил разрабатывают язык программирования Scheme , диалект Лиспа, включающий лексическую область видимости , единое пространство имен и элементы модели акторов, включая первоклассные продолжения .
- Бэкус на лекции премии Тьюринга 1977 года подверг критике текущее состояние промышленных языков и предложил новый класс языков программирования, ныне известных как языки программирования функционального уровня .
- В 1977 году Гордон Плоткин представляет « Программирование вычислимых функций» - функциональный язык с абстрактными типами.
- В 1978 году Робин Милнер представил алгоритм вывода типа Хиндли – Милнера для машинного обучения . Теория типов стала применяться как дисциплина к языкам программирования, это приложение за годы привело к огромным успехам в теории типов.
1980-е годы
- В 1981 году Гордон Плоткин публикует свою статью о структурированной операционной семантике .
- В 1988 году Жиль Кан опубликовал свою статью о естественной семантике .
- Там возникли процесс исчисления , такие как Исчисление сообщающихся систем с Робином Милнера , и Взаимодействующими последовательных процессами модели CAR Хора , а также аналогичные модели параллелизма , такие как актер модель из Карл Хьюитт .
- В 1985 году выпуск Miranda пробудил академический интерес к чистым функциональным языкам программирования с отложенным вычислением. Был сформирован комитет для определения открытого стандарта, в результате чего в 1990 году был выпущен стандарт Haskell 1.0.
- Бертран Мейер создал методологию « Дизайн по контракту» и включил ее в язык программирования Eiffel .
1990-е годы
- Грегор Кичалес , Джим Дес Ривьер и Дэниел Боброу опубликовали книгу «Искусство протокола метаобъектов» .
- Эудженио Моджи и Филип Вадлер ввели использование монад для структурирования программ, написанных на языках функционального программирования .
Есть несколько областей исследования, которые либо лежат в рамках теории языков программирования, либо имеют на нее глубокое влияние; многие из них в значительной степени пересекаются. Кроме того, PLT использует многих других отраслей математики , в том числе теории вычислимости , теории категорий и теории множеств .
Формальная семантика
Формальная семантика - это формальная спецификация поведения компьютерных программ и языков программирования. Три общих подхода к описанию семантики или «значения» компьютерной программы - это денотационная семантика , операционная семантика и аксиоматическая семантика .
Теория типов
Теория типов - это изучение систем типов ; которые представляют собой «управляемый синтаксический метод для доказательства отсутствия определенного поведения программы путем классификации фраз в соответствии с типами вычисляемых ими значений». Многие языки программирования различаются характеристиками систем типов.
Анализ и преобразование программ
Анализ программы - это общая проблема изучения программы и определения ключевых характеристик (таких как отсутствие классов программных ошибок ). Преобразование программы - это процесс преобразования программы из одной формы (языка) в другую.
Сравнительный анализ языков программирования
Сравнительный анализ языков программирования стремится классифицировать языки программирования на различные типы на основе их характеристик; широкие категории языков программирования часто называют парадигмами программирования .
Дженерик и метапрограммирование
Метапрограммирование - это генерация программ более высокого порядка, которые при выполнении в результате создают программы (возможно, на другом языке или на подмножестве исходного языка).
Доменные языки
Доменно-специфические языки - это языки, созданные для эффективного решения проблем в определенной части предметной области.
Конструкция компилятора
Теория компиляторов - это теория написания компиляторов (или, в более общем смысле, переводчиков ); программы, которые переводят программу, написанную на одном языке, в другую форму. Действия компилятора традиционно подразделяются на синтаксический анализ ( сканирование и синтаксический анализ ), семантический анализ (определение того, что программа должна делать), оптимизацию (повышение производительности программы, на что указывает некоторая метрика; обычно скорость выполнения) и генерация кода. (создание и вывод эквивалентной программы на некотором целевом языке; часто набор инструкций ЦП).
Системы поддержки
Системы времени выполнения относятся к разработке сред выполнения языков программирования и их компонентов, включая виртуальные машины , сборку мусора и интерфейсы внешних функций .
Журналы, публикации и конференции
Конференции - это основная площадка для представления исследований в области языков программирования. Наиболее известные конференции включают симпозиум по принципам Языки программирования (POPL), Язык программирования Проектирование и реализация (PLDI), на Международной конференции по функциональному программированию (МКВП), Международная конференция по объектно - ориентированного программирования, систем, языков и приложений ( OOPSLA) и Международная конференция по Architectural Поддержка Языки программирования и операционные системы (ASPLOS) .
Известные журналы, публикующие исследования PLT, включают ACM Transactions по языкам и системам программирования (TOPLAS), Journal of Functional Programming (JFP), Journal of Functional and Logic Programming , а также High-Order and Symbolic Computing .
Смотрите также
Рекомендации
дальнейшее чтение
- Абади, Мартин и Карделли, Лука . Теория объектов . Springer-Verlag.
- Майкл Дж . К. Гордон . Теория языков программирования и ее реализация . Прентис Холл.
- Гюнтер, Карл и Митчелл, Джон К. (ред.). Теоретические аспекты объектно-ориентированных языков программирования: типы, семантика и языковой дизайн . MIT Press.
- Харпер, Роберт . Практические основы языков программирования . Черновая версия.
- Кнут, Дональд Э. (2003). Избранные статьи по компьютерным языкам . Стэнфорд, Калифорния: Центр изучения языка и информации.
- Митчелл, Джон С. . Основы языков программирования .
- Митчелл, Джон С. . Введение в теорию языков программирования .
- О'Хирн, Питер. В. и Теннент, Роберт. Д. (1997). Алголообразные языки . Успехи теоретической информатики. Биркхаузер, Бостон.
- Пирс, Бенджамин С. (2002). Типы и языки программирования . MIT Press.
- Пирс, Бенджамин С. Продвинутые темы по типам и языкам программирования .
- Пирс, Бенджамин С. и др. (2010). Основы программного обеспечения .
Внешние ссылки
- Lambda the Ultimate , блог сообщества для профессионального обсуждения и хранилище документов по теории языков программирования.
- Отличные работы по языкам программирования . Собран Бенджамином К. Пирсом ( Университет Пенсильвании ).
- Классические статьи по языкам программирования и логике . Собрал Карл Крэри ( Университет Карнеги-Меллона ).
- Исследование языка программирования . Справочник Марка Леоне .
- Тексты теории языков программирования онлайн . В Утрехтском университете .
- λ-Calculus: Then & Now от Даны С. Скотт для празднования столетия ACM Тьюринга
- Грандиозные вызовы языков программирования . Панельная сессия на POPL 2009.