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

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

Строчная греческая буква λ ( лямбда ) - неофициальный символ из области теории языков программирования. ^{[ необходимая цитата ]} Это использование происходит из лямбда-исчисления , модели вычислений, введенной Алонзо Чёрчем в 1930-х годах и широко используемой исследователями языков программирования. Он украшает обложку ^{[ необходима цитата ]} классического текста « Структура и интерпретация компьютерных программ» и заголовок так называемых лямбда-документов 1975–1980 годов, написанных Джеральдом Джеем Сассманом и Гаем Стилом., разработчики языка программирования Scheme . ^{[ жаргон ]}

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

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

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

Первым языком программирования , который был изобретен, был 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). ^[2]
• В 1967 году Кристофер Стрейчи публикует свой влиятельный набор конспектов лекций « Фундаментальные концепции языков программирования» , вводя терминологию R-значения , L-значения , параметрический полиморфизм и специальный полиморфизм .
• В 1969 году Дж. Роджер Хиндли публикует « Основную схему типов объекта в комбинаторной логике» , позже обобщенную в алгоритм вывода типов Хиндли – Милнера .
• В 1969 году Тони Хоар вводит логику Хора , форму аксиоматической семантики .
• В 1969 году Уильям Элвин Ховард заметил, что «высокоуровневую» систему доказательств , называемую естественным выводом , можно напрямую интерпретировать в своей интуиционистской версии как типизированный вариант модели вычислений, известной как лямбда-исчисление . Это стало известно как переписка Карри – Ховарда .

1970-е [ править ]

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

1980-е [ править ]

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

1990-е [ править ]

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

Поддисциплины и связанные поля [ править ]

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

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

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

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

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

Анализ и преобразование программ [ править ]

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

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

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

Обобщение и метапрограммирование [ править ]

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

Доменные языки [ править ]

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

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

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

Системы поддержки [ править ]

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

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

Конференции - это основная площадка для представления исследований в области языков программирования. Наиболее известные конференции включают симпозиум по принципам Языки программирования (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.