Теория языка программирования - Википедия - Programming language theory

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

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

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

История

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

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

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

1950-е годы

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

1960-е

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

1970-е годы

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

1980-е

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

1990-е

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

Поддисциплины и смежные области

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

Формальная семантика

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

Теория типов

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

Анализ и преобразование программ

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

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

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

Генерик и метапрограммирование

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

Доменные языки

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

Конструкция компилятора

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

Системы поддержки

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

Журналы, публикации и конференции

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

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

Смотрите также

• SIGPLAN
• Хронология языков программирования
• Язык программирования очень высокого уровня

Рекомендации

дальнейшее чтение

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

внешняя ссылка

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