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

Теория языков программирования ( PLT ) — это раздел информатики , который занимается проектированием, реализацией, анализом, характеристикой и классификацией формальных языков , известных как языки программирования . Теория языка программирования тесно связана с другими областями, включая математику , разработку программного обеспечения и лингвистику . В этом районе проводится ряд научных конференций и журналов .

История [ править ]

В некотором смысле история теории языков программирования предшествует даже развитию самих языков программирования. Лямбда -исчисление , разработанное Алонзо Чёрчем и Стивеном Коулом Клином в 1930-х годах, рассматривается некоторыми как первый в мире язык программирования, хотя оно предназначалось для моделирования вычислений, а не для того, чтобы программисты могли описывать алгоритмы компьютерной системе. . Многие современные языки функционального программирования характеризуются как «тонкая оболочка» над лямбда-исчислением. ^[2] и многие из них легко описать с его точки зрения.

Первым языком программирования, который был изобретен, был Plankalkül , который был разработан Конрадом Цузе в 1940-х годах, но не был широко известен до 1972 года (и не был реализован до 1998 года). Первым широко известным и успешным языком программирования высокого уровня стал Фортран , разработанный с 1954 по 1957 год группой исследователей IBM под руководством Джона Бэкуса . Успех ФОРТРАНа привел к созданию комитета ученых для разработки «универсального» компьютерного языка; результатом их усилий стал АЛГОЛ 58 . Отдельно Джон Маккарти из Массачусетского технологического института разработал Lisp , первый язык, возникший в академических кругах и добившийся успеха. Благодаря успеху этих первоначальных усилий языки программирования стали активной темой исследований в 1960-х годах и позже.

Хронология [ править ]

Некоторые другие ключевые события в истории теории языков программирования с тех пор:

1950-е годы

Ноам Хомский разработал иерархию Хомского в области лингвистики, открытие, которое напрямую повлияло на теорию языков программирования и другие отрасли информатики.

1960-е годы

Язык Simula был разработан Оле-Йоханом Далем и Кристен Нюгаард ; широко считается, что это первый пример объектно-ориентированного языка программирования ; Simula также представила концепцию сопрограмм .
В 1964 году Питер Лэндин первым понял, что лямбда-исчисление Чёрча можно использовать для моделирования языков программирования. Он представляет машину SECD , которая «интерпретирует» лямбда-выражения.
В 1965 году Ландин вводит оператор J , по сути, форму продолжения .
В 1966 году Ландин представляет ISWIM , абстрактный язык программирования в своей статье «Следующие 700 языков программирования» . Он оказал влияние на разработку языков, которые привели к созданию языка программирования Haskell .
В 1966 году Коррадо Бём представил язык программирования CUCH (Curry-Church). ^[3]
В 1967 году Кристофер Стрейчи публикует свой влиятельный набор конспектов лекций « Фундаментальные концепции языков программирования» , в котором вводит терминологию R-значений , L-значений , параметрического полиморфизма и специального полиморфизма .
В 1969 году Дж. Роджер Хиндли публикует «Основную схему типов объекта в комбинаторной логике» , позже обобщенную в Хиндли-Милнера алгоритм вывода типа .
В 1969 году Тони Хоар представил логику Хоара — форму аксиоматической семантики .
В 1969 году Уильям Элвин Ховард «высокого уровня» заметил, что система доказательств , называемая естественной дедукцией версии может быть напрямую интерпретирована , в своей интуиционистской как типизированный вариант модели вычислений, известной как лямбда-исчисление . Это стало известно как переписка Карри-Ховарда .

1970-е годы

В 1970 году Дана Скотт впервые публикует свою работу по денотационной семантике .
В 1972 году были разработаны логическое программирование и Пролог , что позволило выражать компьютерные программы в виде математической логики.
Группа ученых из Xerox PARC под руководством Алана Кея разработала Smalltalk — объектно-ориентированный язык, широко известный своей инновационной средой разработки.
В 1974 году Джон К. Рейнольдс открывает Систему F. Его уже открыл в 1971 году математик-логик Жан-Ив Жирар .
С 1975 года Джеральд Джей Сассман и Гай Стил разрабатывают язык программирования Scheme , диалект Лиспа, включающий лексическую область видимости , единое пространство имен и элементы модели актера , включая первоклассные продолжения .
Бэкус на лекции на Премии Тьюринга 1977 года раскритиковал современное состояние промышленных языков и предложил новый класс языков программирования, теперь известный как языки программирования функционального уровня .
В 1977 году Гордон Плоткин представил «Программирование вычислимых функций» — абстрактный типизированный функциональный язык.
В 1978 году Робин Милнер представил алгоритм вывода типа Хиндли-Милнера для ML . Теория типов стала применяться как дисциплина в языках программирования. Это приложение за последние годы привело к огромному прогрессу в теории типов.

1980-е годы

В 1981 году Гордон Плоткин публикует свою статью о структурированной операционной семантике .
В 1988 году Жиль Кан опубликовал свою статью о естественной семантике .
Появились исчисления процессов , такие как исчисление коммуникативных систем Робина Милнера и коммуникативных последовательных процессов модель К.А.Р. Хоара , а также аналогичные модели параллелизма, такие как модель актера Карла Хьюитта .
В 1985 году выпуск Miranda вызвал академический интерес к чисто функциональным языкам программирования с ленивой оценкой. Для определения открытого стандарта был сформирован комитет, результатом которого стал выпуск стандарта Haskell 1.0 в 1990 году.
Бертран Мейер создал методологию Design by Contract и включил ее в язык программирования Eiffel .

1990-е годы

Грегор Кичалес , Джим Де Ривьер и Дэниел Г. Боброу опубликовали книгу «Искусство метаобъектного протокола» .
Эухенио Моджи и Филип Вадлер представили использование монад для структурирования программ, написанных на языках функционального программирования .

Субдисциплины и смежные области [ править ]

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

Формальная семантика [ править ]

Формальная семантика — это формальная спецификация поведения компьютерных программ и языков программирования. Три распространенных подхода к описанию семантики или «значения» компьютерной программы — это денотатационная семантика , операционная семантика и аксиоматическая семантика .

Теория типов [ править ]

Теория типов — это изучение систем типов ; которые представляют собой «удобный синтаксический метод доказательства отсутствия определенного поведения программы путем классификации фраз в соответствии с типами значений, которые они вычисляют». ^[4] Многие языки программирования отличаются особенностями своих систем типов.

Анализ и трансформация программы [ править ]

Анализ программы — это общая задача исследования программы и определения ее ключевых характеристик (таких как отсутствие классов ошибок программы ). Преобразование программы — это процесс преобразования программы из одной формы (языка) в другую форму.

Сравнительный анализ языков программирования [ править ]

Сравнительный анализ языков программирования направлен на классификацию языков программирования на различные типы в зависимости от их характеристик; широкие категории языков программирования часто называют парадигмами программирования .

Generic and metaprogramming [ edit ]

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

Языки, специфичные для предметной области [ править ]

Предметно-ориентированные языки — это языки, созданные для эффективного решения проблем определенной части предметной области.

Конструкция компилятора [ править ]

Теория компиляторов — это теория написания компиляторов (или, в более общем смысле, трансляторов ); программы, которые переводят программу, написанную на одном языке, в другую форму. Действия компилятора традиционно разбиваются на синтаксический анализ ( сканирование и синтаксический анализ ), семантический анализ (определение того, что должна делать программа), оптимизацию (улучшение производительности программы, на что указывает некоторая метрика; обычно скорость выполнения) и генерация кода. (генерация и вывод эквивалентной программы на некотором целевом языке; часто набор команд ЦП).

Системы времени выполнения [ править ]

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

Журналы, публикации и конференции [ править ]

Конференции являются основным местом проведения исследований в области языков программирования. Наиболее известные конференции включают Симпозиум по принципам языков программирования (POPL), Проектирование и реализация языков программирования (PLDI), Международную конференцию по функциональному программированию (ICFP), Международную конференцию по объектно-ориентированному программированию, системам, языкам и приложениям ( OOPSLA) и Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS) .

Известные журналы, публикующие исследования PLT, включают транзакции ACM на языках и системах программирования (TOPLAS), Журнал функционального программирования (JFP), Журнал функционального и логического программирования , а также Вычисления высшего порядка и символические вычисления .

См. также [ править ]

Ссылки [ править ]

^ Абельсон, Гарольд (1996). Структура и интерпретация компьютерных программ . Джеральд Джей Сассман, Джули Сассман (2-е изд.). Кембридж, Массачусетс: MIT Press. ISBN 0-262-01153-0 . OCLC 34576857 .
^ «Модели вычислений» . wiki.c2.com . 3 декабря 2014 г. Архивировано из оригинала 30 ноября 2020 г.
^ К. Бём и В. Гросс (1996). Знакомство с CUCH. В ER Caianiello (ред.), Теория автоматов , стр. 35-64/
^ Бенджамин К. Пирс. 2002. Типы и языки программирования . MIT Press, Кембридж, Массачусетс, США.

Дальнейшее чтение [ править ]

Абади, Мартин и Карделли, Лука . Теория объектов . Спрингер-Верлаг.
Майкл Джей Си Гордон . Теория языка программирования и ее реализация . Прентис Холл.
Гюнтер, Карл и Митчелл, Джон К. (ред.). Теоретические аспекты объектно-ориентированных языков программирования: типы, семантика и языковой дизайн . МТИ Пресс.
Харпер, Роберт . Практические основы языков программирования . Черновая версия.
Кнут, Дональд Э. (2003). Избранные статьи по компьютерным языкам . Стэнфорд, Калифорния: Центр изучения языка и информации.
Митчелл, Джон К. Основы языков программирования .
Митчелл, Джон К. Введение в теорию языков программирования .
О'Хирн, Питер. В. и Теннент, Роберт. Д. (1997). Алголоподобные языки . Прогресс в теоретической информатике. Биркхаузер, Бостон.
Пирс, Бенджамин К. (2002). Типы и языки программирования . МТИ Пресс.
Пирс, Бенджамин К. Расширенные темы по типам и языкам программирования .
Пирс, Бенджамин С. и др. (2010). Основы программного обеспечения .

Внешние ссылки [ править ]

Lambda the Ultimate — блог сообщества для профессионального обсуждения и хранилище документов по теории языков программирования.
Великие работы в области языков программирования . Собрано Бенджамином К. Пирсом ( Пенсильванский университет ).
Классические статьи по языкам программирования и логике . Собрано Карлом Крэри ( Университет Карнеги-Меллон ).
Исследование языка программирования . Справочник Марка Леоне.
λ-исчисление: тогда и сейчас, автор Дана С. Скотт, к празднованию столетия ACM Тьюринга
Большие проблемы языков программирования . Панельная сессия на POPL 2009.

[1] Абельсон, Гарольд (1996). Структура и интерпретация компьютерных программ . Джеральд Джей Сассман, Джули Сассман (2-е изд.). Кембридж, Массачусетс: MIT Press. ISBN 0-262-01153-0 . OCLC 34576857 .

[2] «Модели вычислений» . wiki.c2.com . 3 декабря 2014 г. Архивировано из оригинала 30 ноября 2020 г.

[3] К. Бём и В. Гросс (1996). Знакомство с CUCH. В ER Caianiello (ред.), Теория автоматов , стр. 35-64/

[4] Бенджамин К. Пирс. 2002. Типы и языки программирования . MIT Press, Кембридж, Массачусетс, США.

[1]

[2]

[3]

[4]