Языки первого и высшего порядка - Классификация языков программирования

Это продолжение увлекательной статьи про классификация языков программирования.

...

программы требуется ее перекомпиляция, что замедляет процесс разработки. Кроме того, скомпилированная программа может выполняться только на том же типе компьютеров и, как правило, под той же операционной системой, на которую был рассчитан компилятор. Чтобы создать исполняемый файл для машины другого типа, требуется новая компиляция. Интерпретируемые языки позволяют запускать программы сразу же после изменения, причем на разных типах машин и операционных систем без дополнительных усилий, а гомоиконные — и вовсе динамически перемещать программу между разными машинами без прерывания ее работы (наиболее общий случай сериализации), позволяя разрабатывать системы непрерывной доступности[en] (см.тж. системы высокой доступности). Портируемость интерпретируемой программы определяется только наличием реализаций интерпретаторов под те или иные аппаратные платформы. Ценой всего этого становятся заметные потери быстродействия; кроме того, если программа содержит фатальную ошибку, то об этом не будет известно, пока интерпретатор не дойдет до ее места в коде (в отличие от статически типобезопасных языков>>>).

Некоторые языки, например, Java и C#, находятся между компилируемыми и интерпретируемыми. А именно, программа компилируется не в машинный язык, а в машинно-независимый код низкого уровня, байт-код. Далее байт-код выполняется виртуальной машиной. Для выполнения байт-кода обычно используется интерпретация, хотя отдельные его части для ускорения работы программы могут быть транслированы в машинный код непосредственно во время выполнения программы по технологии компиляции «на лету» (Just-in-time compilation, JIT). Для Java байт-код исполняется виртуальной машиной Java (Java Virtual Machine, JVM), для C# — Common Language Runtime. Подобный подход в некотором смысле позволяет использовать плюсы как интерпретаторов, так и компиляторов.

Языки первого и высшего порядка

Начальные сведения

Математическая логика классифицируется по порядку — см. логика первого порядка и логика высшего порядка. Эта терминология естественным образом наследуется информатикой, образуя семантики, соответственно, первого и высшего порядка[33]. Языки первого порядка (например, потомки Алгола, такие как Basic или классический Pascal Вирта) позволяют определять только зависимости первого порядка между величинами. Например, значение sqare x зависит от значения x. Такие зависимости называются функциями. Языки высшего порядка позволяют определять зависимости между зависимостями. Например, значение map f x зависит от значений f и x, где значение f само выражает абстрактную зависимость (другими словами, параметр f варьируется над множеством функций определенной сигнатуры). Такие зависимости называются функциями высшего порядка. При этом в большинстве случаев говорят, что такой язык рассматривает зависимости (функции) как объекты первого класса, иначе говоря, допускает функции первого класса[34] (некоторые языки, например Си, не поддерживают первоклассные функции, но предоставляют ограниченные возможности строить функции высшего порядка). Эти термины ввел Кристофер Стрэчи[en]. К языкам высшего порядка относятся почти все функциональные языки (исключения очень редки; примером функционального языка первого порядка долгое время являлся SISAL[en], но в 2018 году в него была добавлена поддержка первоклассных функций). С развитием систем типов различение порядков распространилось и на типы (см. конструктор типов).

Выразительность

Языки первого порядка позволяют воплощать в виде кода алгоритмы, но не архитектуру программ. По мнению Стрэчи[en], это ограничение унаследовано языком Алгол (а от него другими языками) из классической математики, где используются только константные операции и функции, однозначно распознаваемые вне контекста, и отсутствует систематичная нотация для произвольной работы с функциями (в качестве такой нотации в 1930-х годах было построено лямбда-исчисление, которое позже легло в основу языков высшего порядка)[35]. Схемы взаимодействия компонентов (процедур, функций, объектов, процессов и др.) для программ на языках первого порядка могут существовать лишь на условном уровне, вне самих программ. Со временем были обнаружены многократно повторяющиеся однотипные схемы такого рода, в результате чего вокруг них выстроилась самостоятельная методология — шаблоны проектирования. Языки высшего порядка позволяют воплощать такие схемы в виде исполнимого кода, пригодного для многократного использования (функций, предназначенных для преобразования и композиции других функций — см., например, конверторы и сканеры в SML)[36][37]. В результате, решения, которые на языках первого порядка могут быть представлены фрагментами программ (порой довольно сложными и громоздкими), на языках высшего порядка могут сокращаться до одной команды или вообще использования элемента семантики самого языка, не имеющего синтаксического выражения. Например, шаблон «Команда», часто применяемый в языках первого порядка, эквивалентен непосредственно самому понятию функции первого класса. То же распространяется и на более высокие слои языков — типизацию (см. полиморфизм в высших рода́х) и типизацию типизации (см. полиморфизм родо́в).

Сказанное преимущественно относится к языкам, семантика которых основана на лямбда-исчислении (потомки Lisp, ML). Однако некоторые языки иной природы также предоставляют возможность программирования высшего порядка[en]. Примерами служат стековые языки (Forth) и определенная разновидность объектно-ориентированных языков (Smalltalk, CLOS, см. сообщение высшего порядка[en]).

Изучение

Введя терминологию «сущностей первого и второго класса», Стрэчи[en] тут же акцентировал внимание на том, что из личного опыта и обсуждений со множеством людей он убедился, что невероятно тяжело перестать думать о функциях как об объектах второго класса[35]. То есть порядок языка имеет ярко выраженное психологическое влияние (см. гипотеза Сепира — Уорфа). Владение языками более высокого уровня поможет программисту думать в терминах более высокоуровневых абстракций[38].

Низкоуровневые же языки могут навязывать обратное, в связи с чем широко известно следующее высказывание:

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

Оригинальный текст (англ.)

It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration

— Эдсгер Дейкстра

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

Понимание возможностей и ограничений высокоуровневых конструкций, базовых принципов их реализации не только дают программисту возможность наиболее эффективно использовать изученный им язык, но и позволят создавать и использовать аналогичные механизмы в случае разработки на языке, где они не реализованы[38].

Разработчику, владеющему бо́льшим спектром языков программирования, будет проще выбрать среди них инструмент, наиболее подходящий для решения стоящей перед ним задачи, изучить, в случае необходимости, новый язык или реализовать предметно-ориентированный язык, к которым, к примеру, можно отнести интерфейс командной строки достаточно сложной программы[40].

Парадигма программирования

Отнесение языков к парадигмам может производиться по нескольким признакам, из которых одни соответствуют конкретным техническим характеристикам языков, а другие весьма условны.

Технически языки делятся, например, на допускающие побочные эффекты и ссылочно-прозрачные. Во втором случае говорят, что язык принадлежит к «чисто функциональной парадигме». В качестве парадигмы также иногда рассматриваются определенные свойства системы типов и стратегии вычисления языка, например, для параметрически полиморфных систем типов нередко говорят о реализации парадигмы обобщенного программирования. Другим примером может служить свойство гомоиконности, открывающее целый спектр разновидностей метапрограммирования. Существует масса «языков, наследованных от математики»>>>, многие из которых формируют уникальные парадигмы. Яркими представителями являются Lisp, впервые воплотивший лямбда-исчисление и положивший таким образом начало функциональной парадигме, Smalltalk, впервые воплотивший объектно-ориентированную парадигму (появившаяся за много лет до него Симула поддерживала понятие класса, но воплощала структурную парадигму), и стековый язык Forth, воплощающий конкатенативную парадигму.

Более условно языки делятся на поколения. Первые два поколения являются низкоуровневыми, то есть ориентированными на специфику конкретного аппаратного обеспечения, и в принципе не соотносятся с какой-либо парадигмой (хотя конкретный разработчик на них, разумеется, может идеологически следовать определенным тенденциям). Вместе с третьим поколением они формируют императивную парадигму программирования, а последующие поколения — декларативную (более подробно см. раздел Языки низкого и высокого уровня). Многие декларативные языки включают в себя определенные императивные возможности, иногда — наоборот.

С ростом размера и сложности программ уже при использовании языков второго поколения начала формироваться парадигма процедурного программирования, требующая производить декомпозицию крупных процедур в цепочку иерархически связанных более мелких. Примерно в то же время появились первые языки третьего поколения и сформировалось сперва структурное программирование как прямое развитие процедурного, а затем и модульное. Со временем появилось огромное количество разнообразных путей решения проблемы комплексирования растущих программных систем>>> с сохранением исходно императивного подхода в основе. В некоторых случаях достигнуто существенное влияние на показатели скорости разработки и качества, но в общем и целом, как выше отмечено>>>, языки третьего поколения абстрагируются от машинной логики лишь до определенного уровня и незначительно подвержены эквивалентным преобразованиям[en]. К настоящему времени третье поколение языков представлено наиболее обширным спектром разнообразных парадигм.

К четвертому поколению относят функциональные языки, из которых выделяются «чисто функциональные» (англ. purely functional, соответствующие выше упомянутой технической категории ссылочно-прозрачных), а остальные называются «не чисто функциональными» (англ. impurely functional).

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

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

Языки для программирования в мелком и крупном масштабе

Программы могут решать задачи различного масштаба[en]: одна программа строит график для заданной функции, а другая управляет документооборотом крупного предприятия. Различные языки программирования рассчитаны на разный исходный масштаб задачи и, что еще более важно, по-разному справляются с ростом сложности программных систем. Ключевым качеством языка, от которого зависит, как меняется трудоемкость разработки по мере наращивания системы, является абстракция, то есть возможность отделять смысл (поведение) компонента системы от способа его реализации[41][42].

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

Оригинальный текст (англ.)

There is a fundamental limit to complexity of any software system for it to be still manageable: if it requires more than "one brainfull" of information to understand a component of the system, then that component will not be understood fully. It will be extremely difficult to make enhancements or fix bugs, and each fix is likely to introduce further errors due to this incomplete knowledge.

— Martin Ward, «Language Oriented Programming»[43]

Такие показатели качества исходного кода, как тестируемость и модифицируемость, очевидным образом определяются коэффициентом повторного использования. Это может означать как применение разных функций к одному и тому же компоненту, так и возможность применять одну и ту же функцию к разным компонентам. Параметрически полиморфные (особенно выводящие) и динамические системы типов существенно повышают коэффициент повторного использования: например, функция, вычисляющая длину массива, будет применима к бесконечному множеству типов массивов[27][44]. Если же язык требует в сигнатуре функции указывать конкретный способ реализации входных данных, то этот коэффициент резко страдает. Например, Pascal критиковался за необходимость всегда указывать конкретный размер массива[45], а C++ — за необходимость различать . и -> при обращении к компонентам составных данных[en][46]. Языки высшего порядка>>> позволяют выделять схемы взаимодействия функций в многократно вызываемый блок кода (функцию высшего порядка)[36][47], а наибольших значений повторное использование достигает при переходе к языку более высокого уровня — при необходимости специально разрабатываемого для данной задачи — в этом случае повторно используется язык, а не одна функция[43], а сама разработка языка может вестись с интенсивным повторным использованием компонентов компилятора[48].

С развитием языков появились особые (присущие исключительно программированию, не требовавшиеся ранее в математике) категории компонентов и зависимостей: монады, классы типов, полиморфные ветвления, аспекты и др. Их использование позволяет выражать бо́льшую функциональность в том же объеме кода, тем самым переводя программирование-по-крупному[en] в более мелкий масштаб.

Другие фундаментальные проблемы, связанные со сложностью крупных систем, лежат вне самих программ: это взаимодействие разрабатывающих ее программистов между собой, документирование и т. д. Помимо обеспечения абстракции, не последнюю роль в этом играет концептуальная целостность>>> выбранного языка программирования .

Кроме свойств семантики языка, повторное использование может обеспечиваться посредством модульной структуры программной системы или комплекса. Более того, сколь бы гибким ни был язык, работа с огромными объемами кодов, особенно множеством людей, требует их декомпозиции на модули тем или иным образом. Модульная структура подразумевает не просто разбиение монолитного исходного кода программы на множество текстовых файлов, а обеспечение абстракции в более крупном масштабе, то есть определение интерфейса для всякого логически завершенного фрагмента и сокрытие деталей его реализации. В зависимости от примененных в языке правил определения области видимости язык может допускать или не допускать автоматическое определение зависимостей. Если согласно правилам возможен конфликт имен, то автоопределение зависимостей невозможно, и тогда в заголовке модуля требуется явно перечислять имена модулей, компоненты которых в нем используются.

Некоторые языки (например, Basic или классический Pascal Вирта) ориентированы исключительно на разработку мелких, структурно простых программ. Они не обеспечивают ни развитой системы модулей, ни гибкости конкретных фрагментов. Язык Си создавался как «высокоуровневый ассемблер», что само по себе не предполагает разработку систем выше некоторого порога сложности, поэтому поддержка крупномасштабного программирования в него заложена также не была. Некоторые языки высокого и сверхвысокого уровня (Erlang, Smalltalk, Prolog) предоставляют в качестве базовых примитивных элементов концепции, которые в других языках представляются конструктивно и алгоритмически сложными (процессы, классы, базы знаний) — аналогично разнообразным математическим исчислениям (см. также концептуальная целостность языков). Поэтому такие языки нередко рассматриваются в роли предметно-специфичных — на них выглядят простыми некоторые (но далеко не все) задачи, которые на других языках выглядят сложными. Однако расширение функциональности в других аспектах на этих языках может оборачиваться затруднениями. Standard ML и его родственники расслаиваются на два языка, из которых один — «язык-ядро» (англ. core language) — ориентирован на разработку простых программ, а другой — «язык модулей» (англ. module language),— соответственно, на нелинейную компоновку их в сложные программные системы. Со временем были построены варианты слияния их воедино (1ML). Многие другие языки также включают системы модулей, но большинство из них являются языками модулей первого порядка>>>. Язык модулей ML является единственным в своем роде языком модулей высшего порядка>>>. Языки Lisp и Forth позволяют наращивать системы произвольно и безгранично, в том числе позволяя создавать встраиваемые предметно-специфичные языки внутри себя (как свое синтаксическое и семантическое подмножество) — поэтому их нередко называют метаязыками.

Наиболее популярным на сегодняшний день подходом к решению проблемы комплексирования является объектно-ориентированное программирование, хотя успешность его применения на протяжении десятилетий существования неоднократно подвергалась скепсису, и до сих пор отсутствуют достоверные данные о том, что он приносит выигрыш по сравнению с другими подходами по тем или иным показателям качества. Ему сопутствуют (а порой конкурируют) различные технологии регламентирования зависимостей между компонентами: метаклассы, контракты, прототипы, примеси, типажи и др.

Более мощным подходом исторически считалось использование различных форм метапрограммирования, то есть автоматизации самого процесса разработки на различных уровнях. Принципиально различается метапрограммирование внешнее по отношению к языку и доступное в самом языке. При использовании языков первого порядка>>> сложность растущих программных систем быстро переходит порог способностей человека по восприятию и переработке информации, поэтому применяются внешние средства предварительного визуального проектирования, позволяющие обозревать сложные схемы в упрощенном виде и в уменьшенном масштабе и затем автоматически порождать каркас кода — см. CASE. В сообществах разработчиков, использующих языки высшего порядка>>>, доминирует прямо противоположный подход — пресекать саму возможность выхода сложности из-под контроля за счет разделения информационных моделей на независимые составляющие и разработки средств автоматического преобразования одних моделей в другие — см. языково-ориентированное программирование.

Концептуальная целостность языков

Фредерик Брукс[50] и Ч. Э. Р. Хоар делают акцент на необходимости обеспечения концептуальной целостности информационных систем вообще и языков программирования в частности, чтобы в каждой части системы использовались сходные синтаксические и семантические формы и не требовалось осваивать помимо собственно состава системы также и правила ее идиоматического использования. Хоар предсказывал, что сложность Ады станет причиной катастроф. Алан Кэй отделяет языки, являющиеся «стилем во плоти» (англ. crystalization of style) от прочих языков, являющихся «склеиванием возможностей» (англ. agglutination of features) . Грег Нельсон и Эндрю Аппель выделяют в особую категорию «языки, наследованные от математики» (англ. mathematically-derived languages).

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

Лишь некоторые языки попадают под эту категорию; большинство же языков проектируются приоритетно исходя из возможности эффективной трансляции в машину Тьюринга. Многие языки опираются на общие теории, но при разработке они почти никогда не проверяются на безопасность совместного использования конкретных языковых элементов, являющихся частными приложениями этих теорий, что неизбежно приводит к несовместимости между реализациями языка. Эти проблемы либо игнорируются, либо начинают преподноситься как естественное явление (англ. «not a bug, but a feature»), но в действительности их причиной является то, что язык не был подвергнут математическому анализу[54].

Примеры математически обоснованных языков и воплощаемых ими математических моделей:

• Agda, Epigram[en], Idris — интуиционистская теория типов[en] Мартин-Лефа.
• APL и его потомки (J, K) — оригинальная семантика, не имеющая названия, воплощающая нотацию Айверсона для исчисления массивов (часто встречается термин «array languages»).
• Coq — исчисление индуктивных конструкций[en].
• Erlang — исчисление процессов (первоначально в форме модели акторов, позже также построено обоснование на {\displaystyle \pi }-исчислении[55]).
• Forth — стековая машина[en] и конкатенативный язык программирования.
• Haskell — теория категорий (включая «декартово замкнутую категорию», воплощающую лямбда-исчисление; категорию монад для моделирования побочных эффектов; расширение системы типов Хиндли — Милнера; систему родо́в; и др.).
• Joy — композиция функций и гомоморфизм (иначе говоря, чистый конкатенативный язык программирования и, как следствие, чистый функциональный).
• Lisp — лямбда-исчисление Черча (в том числе язык S-выражений, воплощающий нотацию пар Черча[en]).
  • Scheme — «облагороженный» диалект Лиспа (сильнее типизированный, в большей степени гомоиконный, ограничивающийся гигиеническими макроопределениями[en] и соблюдающий числовую башню[en]), дополненный нотацией продолжений.
• ML — типизированное лямбда-исчисление, то есть лямбда-исчисление, дополненное системой типов Хиндли — Милнера.
• Prolog — исчисление предикатов.
  • Mercury — исчисление предикатов, дополненное системой типов Хиндли — Милнера.
• Smalltalk — теория множеств[56] (с соблюдением числовой башни[en]).
• SQL — исчисление кортежей (вариант реляционного исчисления, в свою очередь основанного на исчислении предикатов первого порядка).
• SGML и его потомки (HTML, XML) — нотация деревьев (важный случай графов).
• Unlambda — комбинаторная логика.
• Регулярные выражения.
• Рефал — оригинальная семантика Турчина, носящая название «Рефал-машины» или «Рефал-автомата», созданная на основе нормального алгоритма Маркова, воплощающая композицию теории автоматов, сопоставления с образцом и переписывания термов.

Наличие математического обоснования для языка может гарантировать (или, как минимум, обещать с очень высокой вероятностью) некоторые или все из следующих положительных свойств:

• Существенное повышение стабильности программ. В одних случаях — за счет построения доказательства надежности для самого языка (см. типобезопасность), существенного упрощения формальной верификации программ и даже получения языка, который сам является системой автоматического доказательства (Coq, Agda). В других случаях — за счет раннего обнаружения ошибок на первых же пробных запусках программ (Forth и регулярные выражения).
• Обеспечение потенциально более высокой эффективности программ. Даже если семантика языка далека от архитектуры целевой платформы компиляции, к нему могут быть применимы формальные методики глобального анализа программ (хотя трудоемкость написания даже тривиального транслятора может оказаться выше). Например, для языков Scheme и Standard ML существуют развитые полнопрограммно-оптимизирующие компиляторы и суперкомпиляторы, результат работы которых может уверенно конкурировать по скорости с языком низкого уровня Си и даже опережать последний (хотя ресурсоемкость работы самих компиляторов оказывается значительно выше). Одна из самых быстрых СУБД — KDB[57] — написана на языке K. Язык Scala (унаследовавший математику от ML) обеспечивает на платформе JVM более высокую скорость, чем «родной» для нее язык Java . С другой стороны, Forth имеет репутацию одного из самых нетребовательных к ресурсам языков (менее требователен, чем Си) и используется для разработки приложений реального времени под самые маломощные ЭВМ; кроме того, транслятор Форта является одним из наименее трудоемких в реализации на ассемблере.
• Заранее известный (неограниченный или, наоборот, четко очерченный) предел роста сложности программных компонентов, систем и комплексов, которые можно выразить средствами этого языка с сохранением показателей качества[27][58]. Языки, не имеющие математического обоснования (а именно такие наиболее часто применяются в мейнстриме: C++, Java, C#, Delphi и др.), на практике ограничивают реализуемую функциональность и/или снижают качество по мере усложнения системы[59], так как им присущи экспоненциальные кривые роста сложности как относительно работы одного отдельно взятого человека, так и относительно сложности управления проектом в целом[49][60]. Прогнозируемая сложность системы приводит либо к поэтапной декомпозиции проекта на множество более мелких задач, каждая из которых решается соответствующим языком, либо к языково-ориентированному программированию для случая, когда адресуемой языком задачей является как раз описание семантик и/или символьные вычисления (Lisp, ML, Haskell, Рефал, Регулярные выражения). Языки с неограниченным пределом роста сложности программ нередко относят к метаязыкам (что в непосредственном толковании термина не верно, но практике сводимо, так как всякий мини-язык, выбранный для решения некоторой подзадачи в составе общей задачи, может быть представлен в виде синтаксического и семантического подмножества данного языка, не требуя трансляции[61]).

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

Особые категории языков

• Учебные
• Предметно-специфичные
• Эзотерические
• Визуальные

Формальные преобразования и оптимизация

В. Ф. Турчин отмечает[62], что достоинства всякого формализованного языка определяются не только тем, сколь он удобен для непосредственного использования человеком, но и тем, в какой степени тексты на этом языке поддаются формальным преобразованиям.

Например, ссылочная прозрачность означает, что параметры функций не обязаны вычисляться перед вызовом — вместо этого фактически переданное выражение может быть целиком подставлено на место переменной в функции, и поведение функции от этого не изменится. Это открывает возможности почти произвольных автоматических преобразований программ[en]: могут устраняться ненужные промежуточные представления данных, редуцироваться сложные цепочки вычислений, подбираться оптимальное количество параллельных процессов, вводиться мемоизация, и пр. С другой стороны, это означает полное отсутствие побочных эффектов, а это делает реализацию некоторых алгоритмов заведомо менее эффективной, чем при использовании изменяемого состояния.

Для небольших и простых программ языки высокого уровня порождают машинный код большего размера и исполняются медленнее. Однако для алгоритмически и структурно сложных программ преимущество может быть на стороне некоторых языков высокого уровня, так как человек физически не способен выражать сложные концепции с учетом их эффективного исполнения на языке машины. К примеру, существует бенчмарк, на котором MLton и Stalin Scheme[en] уверенно опережают GCC. Есть масса частных причин, по которым автоматическая оптимизация в ходе трансляции языков высокого уровня дает в принципе более высокую скорость исполнения, чем сознательный контроль способа реализации на языках низкого уровня. Например, имеются достоверные данные о том, что автоматическое управление памятью более эффективно, чем ручное, уже только при использовании динамического метода (см. сборка мусора)[63], а существует и потенциально более эффективный статический метод (см. управление памятью на основе регионов?!). Далее, для каждого микроконтекста необходимо распределить регистры с учетом минимизации обращения к памяти, а это требует решения задачи раскраски графа. Такого рода особенностей машинной логики очень много, так что общая информационная сложность возрастает экспоненциально при каждом «шаге на уровень вниз», а компиляция языка высокого уровня может включать десятки таких шагов.

Существует множество стратегий автоматической оптимизации. Некоторые универсальны, другие могут быть применимы лишь к языкам определенной природы, а некоторые зависят от способа использования языка. Примером может служить оптимизация хвостовых вызовов и ее частный случай — оптимизация хвостовой рекурсии. Хотя компиляторы многих языков осуществляют оптимизацию хвостовой рекурсии при определенных условиях, лишь некоторые языки способны семантически гарантировать оптимизацию хвостовых вызовов в общем случае. Стандарт языка Scheme требует, чтобы всякая реализация гарантировала ее. Для многих функциональных языков она в принципе применима, но лишь оптимизирующие компиляторы ее выполняют. В языках вроде Си или С++ она может производиться лишь в определенных случаях и лишь при использовании глобального анализа потока управления[64].

Языки высшего порядка в

продолжение следует...

Продолжение:

Часть 1 Классификация языков программирования
Часть 2 Языки программирования высокого уровня - Классификация языков программирования
Часть 3 Языки первого и высшего порядка - Классификация языков программирования
Часть 4 Популярность языков( Индекс TIOBE) - Классификация языков программирования