Отрасль информатики
Строчная
греческая буква λ (
лямбда ) является неофициальным символом теории языков программирования. Это использование происходит от
лямбда-исчисления,
модели вычислений, введенной
Алонзо Черч в 1930-х годах и широко используемой исследователями языков программирования. Он украшает обложку классического текста
Структура и интерпретация компьютерных программ и заголовок так называемых
лямбда-документов 1975–1980 годов, написанных
Джеральдом Джей Сассманом. и
Гай Стил, разработчики
языка программирования схем.
Теория языков программирования (PLT ) является отраслью информатики, который имеет дело с проектированием, реализацией, анализом, характеристикой и классификацией языков программирования и их индивидуальных функций. Это относится к дисциплине информатики, как зависящей от математики, программной инженерии, лингвистики и даже когнитивной науки, и влияя на нее. Это стало общепризнанной отраслью информатики и активной областью исследований, результаты которой опубликованы в многочисленных журналах, посвященных PLT, а также в общих публикациях по информатике и инженерии.
Содержание
- 1 История
- 1.1 1950-е
- 1.2 1960-е
- 1.3 1970-е
- 1.4 1980-е
- 1.5 1990-е
- 2 Поддисциплины и связанные области
- 2.1 Формальная семантика
- 2.2 Теория типов
- 2.3 Анализ и преобразование программ
- 2.4 Сравнительный анализ языков программирования
- 2.5 Общее и метапрограммирование
- 2.6 Доменно-ориентированные языки
- 2.7 Создание компилятора
- 2.8 Время выполнения систем
- 3 Журналы, публикации и конференции
- 4 См. также
- 5 Ссылки
- 6 Дополнительная литература
- 7 Внешние ссылки
История
В некотором смысле история теории языков программирования предшествовали даже развитию самих языков программирования. лямбда-исчисление, разработанное Алонзо Черч и Стивеном Коулом Клини в 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 году Коррадо Бём представил язык программирования (Curry-Church)
- В 1967 году Кристофер Стрейчи публикует свой влиятельный набор конспектов лекций Фундаментальные концепции языков программирования, вводя терминологию R-значения, L-значения, параметрический полиморфизм и специальный полиморфизм.
- В 1969 году J. Роджер Хиндли публикует Основную схему типов объекта в комбинаторной логике, позже обобщенную в алгоритм Хиндли-Милнера вывода типа.
- В 1969 г. Тони Хоар вводит логику Хора, форму аксиоматической семантики.
- . В 1969 году Уильям Элвин Ховард заметил, что «высокоуровневый» система доказательства, именуемая естественной дедукцией, может быть непосредственно интерпретирована в ее интуиционистской версии как типизированный вариант модели вычислений известное как лямбда-исчисление. Это стало известно как соответствие Карри – Ховарда.
1970-е годы
- В 1970 году Дана Скотт впервые публикует свою работу по денотационной семантике.
- В 1972 году логика программирование и Prolog были разработаны, что позволило выражать компьютерные программы в виде математической логики.
- Группа ученых из Xerox PARC во главе с Аланом Кей разработал Smalltalk, объектно-ориентированный язык, широко известный своей инновационной средой разработки.
- В 1974 году Джон С. Рейнольдс открывает System Ф. Он был открыт еще в 1971 году математиком-логиком Жан-Ивом Жираром.
- . С 1975 года Джеральд Джей Сассман и Гай Стил разрабатывают язык программирования Scheme., диалект Лиспа, включающий лексическую область видимости, единое пространство имен и элементы из модели акторов, включая первоклассные продолжения.
- Бэкуса, в 1977 г. 130>ACM Turing Award, подвергнув критике текущее состояние промышленных языков и предложив новый класс языков программирования, теперь известный как языки программирования на уровне функций.
- В 1977 году Гордон Плоткин представляет Программирование вычислимых функций, абстрактный типизированный функциональный язык.
- В 1978 году Робин Милнер представляет тип Хиндли-Милнера алгоритм вывода для языка программирования ML. Теория типов стала применяться как дисциплина к языкам программирования, это приложение за годы привело к огромным успехам в теории типов.
1980-е годы
- В 1981 году Гордон Плоткин публикует его статья о структурированной операционной семантике.
- В 1988 году Жиль Кан опубликовал свою статью о естественной семантике.
- . Появились вычисления процессов, такие как Расчет коммуникационных систем из Робина Милнера и модель взаимодействующих последовательных процессов из C. AR Hoare, а также аналогичные модели параллелизма, такие как модель акторов из Карла Хьюитта.
- . В 1985 году выпуск Miranda вызвал академический интерес. на чистых функциональных языках программирования с отложенным вычислением. Был сформирован комитет для определения открытого стандарта, в результате чего в 1990 г. был выпущен стандарт Haskell 1.0.
- Бертран Мейер создал методологию Дизайн по контракту и включил ее в Eiffel. язык программирования.
1990-е годы
Поддисциплины и связанные поля
Есть несколько полей исследования, которые либо лежат в рамках теории языков программирования, либо оказывают на нее глубокое влияние; многие из них в значительной степени пересекаются. Кроме того, PLT использует многие другие разделы математики, включая теорию вычислимости, теорию категорий и теорию множеств.
формальную семантику
Формальная семантика - это формальная спецификация поведения компьютерных программ и языков программирования. Три распространенных подхода к описанию семантики или «значения» компьютерной программы: денотационная семантика, операционная семантика и аксиоматическая семантика.
Теория типов
Теория типов - это изучение систем типов ; которые являются «понятным синтаксическим методом для доказательства отсутствия определенного поведения программы путем классификации фраз по типам вычисляемых ими значений». Многие языки программирования различаются по характеристикам систем типов.
Анализ и преобразование программы
Анализ программы - это общая проблема исследования программы и определения ключевых характеристик (таких как отсутствие классов программных ошибок ). Преобразование программы - это процесс преобразования программы из одной формы (языка) в другую.
Сравнительный анализ языков программирования
Сравнительный анализ языков программирования стремится классифицировать языки программирования на различные типы на основе их характеристик; широкие категории языков программирования часто известны как парадигмы программирования.
Общее и метапрограммирование
Метапрограммирование - это генерация программ высшего порядка, которые при выполнении создают программы (возможно, на другом языке или в подмножестве исходного языка) в результате.
Доменные языки
Доменные языки - это языки, созданные для эффективного решения проблем в определенной части предметной области.
Конструирование компилятора
Компилятор теория - это теория написания компиляторов (или, в более общем смысле, переводчиков); программы, которые переводят программу, написанную на одном языке, в другую форму. Действия компилятора традиционно делятся на синтаксический анализ (сканирование и синтаксический анализ ), семантический анализ (определение того, что программа должна делать), оптимизация (улучшение производительность программы, определяемая некоторой метрикой; обычно скорость выполнения) и генерация кода (генерация и вывод эквивалентной программы на некотором целевом языке; часто набор инструкций ЦП).
Системы времени выполнения
Системы времени выполнения относятся к разработке языков программирования сред выполнения и их компонентов, включая виртуальные машины, сборка мусора и интерфейсы сторонних функций.
Журналы, публикации и конференции
Конференции являются основным местом проведения исследований по языкам программирования. Наиболее известные конференции: Симпозиум по принципам языков программирования (POPL), Разработка и реализация языков программирования (PLDI), Международная конференция по функциональному программированию (ICFP), Международная конференция по объектно-ориентированному программированию, системам, языкам и приложениям (OOPSLA) и Международная конференция по архитектурной поддержке языков программирования и операционных систем (ASPLOS).
Известные журналы, публикующие исследования PLT, включают ACM Transactions on Programming Languages and Systems (TOPLAS), Journal of Functional Programming (JFP), Journal of Функциональное и логическое программирование и Высшие порядковые и символьные вычисления.
См. Также
Ссылки
Дополнительная литература
- Абади, Мартин и Карделли, Лука. Теория объектов. Springer-Verlag.
- Майкл Дж. С. Гордон. Теория языков программирования и ее реализация. Прентис Холл.
- и Митчелл, Джон К. (ред.). Теоретические аспекты объектно-ориентированных языков программирования: типы, семантика и языковое проектирование. MIT Press.
- Харпер, Роберт. Практические основы языков программирования. Черновая версия.
- Knuth, Donald E. (2003). Избранные статьи по компьютерным языкам. Стэнфорд, Калифорния: Центр изучения языка и информации.
- Митчелл, Джон К.. Основы языков программирования.
- Митчелл, Джон К.. Введение в теорию языков программирования.
- О'Хирн, Питер. W. и (1997). Алголообразные языки. Успехи теоретической информатики. Биркхаузер, Бостон.
- Пирс, Бенджамин К. (2002). Типы и языки программирования. MIT Press.
- Пирс, Бенджамин С. Расширенные темы по типам и языкам программирования.
- Пирс, Бенджамин С. и др. (2010). Основы программного обеспечения.
Внешние ссылки
| Викискладе есть материалы, связанные с теорией языка программирования. |