Почему первый компилятор был написан до первого интерпретатора?

72

Первый компилятор был написан Грейс Хоппер в 1952 году, в то время как интерпретатор Lisp был написан в 1958 году учеником Джона Маккарти Стивом Расселом. Написание компилятора кажется гораздо более сложной задачей, чем интерпретатор. Если это так, то почему первый компилятор был написан за шесть лет до первого интерпретатора?

anguyen
источник
67
потому что в то время было больше необходимости в компиляторе, чем в интерпретаторе
ratchet freak
23
Скомпилировать первый интерпретатор? : P (только частично язык в щеке, интерпретатор сложен (больше, чем простой компилятор), и было бы противно написать эффективный в машинном коде)
Vality
4
Если вы воспринимаете инструкции выполнения вашего процессора как интерпретирующие их (как я это понимаю (хотя и реализованные с помощью аппаратного обеспечения)), то утверждение о том, что первый интерпретатор был написан после первого компилятора, не выполняется. Кстати, я знаю, что это не помогает с вопросом / ответом. Это просто интересный комментарий с другой точки зрения.
Педро Энрике А. Оливейра
11
Маккарти не написал интерпретатор LISP. Маккарти изобрел математический формализм. Стив Рассел, один из студентов лаборатории MIT AI в то время, понял, что может написать переводчика для выполнения фантастических полетов Маккарти, а остальное уже история.
Джон Р. Штром
5
На самом деле, я слышал, что Маккарти полагал, что LISP невыполнимо. Именно Рассел понял, что универсальная функция Маккарти из руководства LISP а) была интерпретатором, а б) выполнимой.
Jörg W Mittag

Ответы:

97

Написание компилятора кажется гораздо более сложной задачей, чем интерпретатор.

Это может быть правдой сегодня, но я бы сказал, что это было не так 60 лет назад. Несколько причин почему:

  • С переводчиком вы должны хранить и его, и программу в памяти. В эпоху, когда 1 КБ памяти было огромной роскошью, поддержание низкого объема памяти было ключевым. И интерпретация требует немного больше памяти, чем запуск скомпилированной программы.
  • Современные процессоры чрезвычайно сложны с огромными каталогами инструкций. Так что написание хорошего компилятора - действительно сложная задача. Старые процессоры были намного проще, поэтому даже компиляция была проще.
  • Современные языки намного сложнее, чем старые, поэтому даже компиляторы намного сложнее. Таким образом, у старых языков были бы более простые компиляторы.
Euphoric
источник
65
и без компилятора вам пришлось бы писать интерпретатор на ассемблере
трещотка урод
34
Первые компиляторы, где люди. (Когда люди переводчики, нам не нужны компьютеры). Тогда кто-то должен был подумать о написании компилятора на скомпилированном языке (единственном, который у них был, но со временем компилировали мои люди).
ctrl-alt-delor
1
На самом деле .... Я недавно читал, что на компьютере-руководстве Apollo, который использовался в полете на Луну 60-х годов, был переводчик: запись в вики "... переводчик предоставил гораздо больше инструкций, чем изначально поддерживал AGC ..." Полагаю, этот "переводчик" был больше похоже на интерпретатор «Sweet 16», встроенный в старые компьютеры Apple II, чем на что-то вроде LISP.
Calphool
6
@ratchetfreak И это было. Как были первые компиляторы.
RBarryYoung
3
@ Richard: Когда люди были переводчиками / калькуляторами, их должность называлась «компьютер». Поэтому, когда люди были переводчиками, они были компьютерами, в буквальном смысле. В Манхэттенском проекте использовались тысячи «компьютеров» (собственно название работы), которым физики-ядерщики отправляли свои расчеты по почте для исполнения. На самом деле, в проекте также работали математики, которые ломали расчеты инженеров, которые формулировали расчеты из теорий физиков для отправки «компьютеров».
Slebetman
42

Фундаментальный момент заключается в том, что вычислительная аппаратная среда 1950-х годов сделала ее такой, что только компилятор был осуществим с учетом пакетной обработки компьютеров в то время.

В то время лучшие пользовательские интерфейсы были ограничены перфокартами и телетайпами . В 1961 году система SAGE стала первым дисплеем Cathode-Ray Tube (CRT) на компьютере. Таким образом, интерактивный характер переводчика не был предпочтительным или естественным намного позже.

Во многих компьютерах 1950-х годов для загрузки инструкций использовались переключатели на передней панели, а на выходе были просто ряды ламп / светодиодов, а любители даже использовали переключатели и светодиоды на передней панели в 1970-х годах. Может быть, вы знакомы с печально известным Altair 8800 .

Другие аппаратные ограничения также делали интерпретаторов невозможными. В 1950-х годах в компьютерах была крайне ограниченная доступность первичной памяти (например, ОЗУ). До появления полупроводниковой интегральной схемы (которая появилась только в 1958 году) память была ограничена памятью магнитного сердечника или памятью линии задержки, которая измерялась в битах или словах , без префикса. В сочетании с медлительностью памяти вторичного хранилища (например, диска или ленты), было бы сочтено расточительным, если не невозможно, использовать большую часть памяти, используемой для интерпретатора, даже до загрузки интерпретируемой программы.

Ограничение памяти по-прежнему было основным фактором, когда команда под руководством Джона Бакуса из IBM создала компилятор FORTRAN в 1954-57 годах. Этот инновационный компилятор был успешным только потому, что он был оптимизирующим компилятором .

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

добавление

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

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

С точки зрения информатики, компиляторы и интерпретаторы являются переводчиками и примерно одинаковы по сложности для реализации.

mctylr
источник
Использовали ли компьютеры телетайпы до появления разделения времени? Я бы ожидал, что они будут использовать линейные принтеры или спул на ленту. В противном случае, 1-8 секунд, в течение которых компьютер должен был бы ждать после каждой строки текста, представляли бы 1-8 секунд, которые компьютер мог - но не делал - делал что-то полезное.
суперкат
2
@supercat - да, телетайпы использовались, но они были далеки от «интерактивного». Первый компьютер, который я запрограммировал, имел память, состоящую из 18-битных слов, из них 1 тыс. Сама память представляла собой вращающийся барабан , поэтому, когда вы включали компьютер, вам приходилось ждать, пока память не наберет скорость. К нему был подключен телетайп, и вы могли A) прочитать символ, набранный с клавиатуры, или прочитать с помощью устройства чтения бумажных лент (с точки зрения компьютера оба были одинаковыми), B) записать символ на «принтере» "телетайпа. Ах, великие дни - БОЛЬШИЕ дни ..! МОЙ ГРЕЛЬ ТЕПЛЫЙ ЕЩЕ?!?!? :-)
Боб Джарвис
@BobJarvis: в каком году это было бы?
суперкат
1
@supercat - 1973 - но компьютер, о котором идет речь (EDP-18, Education Data Products), даже тогда был относительно пожилым. Тем не менее, это было то, что у нас было (и иметь какой-либо компьютер, с которым можно было связываться в старшей школе в начале середины 70-х годов, было необычно), так как мы думали, что это было довольно удивительно. :-)
Боб Джарвис
2
Это гораздо лучший и полный ответ, чем принятый.
Джим Гаррисон
12

Первые языки программирования были довольно простыми (например, без рекурсии) и были близки к машинной архитектуре, которая сама по себе была простой. Перевод был тогда простым процессом .

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

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

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

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

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

Случай с Лиспом очень особенный, потому что это был чрезвычайно простой язык, который сделал его выполнимым (а компьютер стал немного больше в 58). Что еще более важно, интерпретатор Lisp был доказательством концепции самоопределимости Lisp ( мета-цикличности ), независимо от какой-либо проблемы юзабилити.

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

Babou
источник
3
Мой, как смелый .
Pharap
@Pharap Это неподходящий стиль? Моя цель - сделать так, чтобы ключевую информацию было легче найти, но при этом использовать более свободный стиль, чем просто перечисление фактов. Я должен признаться, что это не очень эффективно на этом сайте SE.
Бабу
@ anonymous-downvoter Понижение рейтинга без пояснительного комментария показывает, что кто-то может быть глупым. Тем не менее, это не говорит, кто.
Бабу
4

Я не согласен с предпосылкой вопроса.

Первый компилятор адмирала Хоппера (A-0) был больше похож на компоновщик или язык макросов. Она хранит подпрограммы на ленте (каждая из которых имеет свой номер), и ее программы будут записаны в виде списка подпрограмм и аргументов. Компилятор скопирует запрошенные подпрограммы с ленты и переупорядочит их в полную программу.

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

Насколько я могу судить, у этого первого компилятора не было лексера или парсера, что делает его отдаленным предком современного компилятора. Позже она создала еще один компилятор (B-0, он же FLOW-MATIC) с целью более похожего на английский синтаксиса, но он не был завершен до 1958 или 1959 года - примерно в то же время, что и интерпретатор Lisp.

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

Лучший ответ с цитатами здесь: https://stackoverflow.com/a/7719098/122763 .

Марк Э. Хаас
источник
3

Другая часть уравнения состоит в том, что компиляторы были ступенчатой ​​абстракцией над ассемблером. Сначала у нас был жестко закодированный машинный код. «Мы» были ассемблером. Каждый прыжок, смещение и т. Д. Вычислялись вручную в гекс (или восьмеричное), а затем перфорировались в бумажную ленту или карточки. Поэтому, когда на сцену вышли ассемблеры, это сильно сэкономило время. Следующим шагом был сборщик макросов. Это дало возможность написать макрос, который расширится до набора машинных инструкций. Так что Фортран и Кобол были огромным шагом вперед. Нехватка ресурсов (хранилища, памяти и процессорных циклов) означала, что интерпретаторам общего назначения приходилось ждать развития технологий. Большинство ранних интерпретаторов были механизмами байт-кода (как сегодня Java или CLR, но с гораздо меньшими возможностями). UCSD Pascal был очень популярным (и быстрым) языком. MS Basic был байт-код движком под капотом.

С точки зрения накладных расходов, это полностью зависит от того, какой процессор запускается. В течение некоторого времени отрасль переживала большой кризис RISC против CISC. Я лично написал ассемблер для IBM, Data General, Motorola, Intel (когда они появились), TI и некоторых других. Существовала довольно значительная разница в наборах команд, регистрах и т. Д., Которые влияли бы на то, что требовалось для «интерпретации» p-кода.

Как пример времени, я начал программировать в телефонной компании около 1972 года.

Билл Братья
источник
2

Если вы не держите все в памяти, скомпилированный код будет намного быстрее. Не забывайте, что в это время функции были присоединены к скомпилированному коду. Если вы не компилируете, вы не знаете, какие функции вам понадобятся. Итак, вы вызываете функции из ... О, еще не с диска, мы в начале 50-х, а с карт! Во время выполнения!

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

Гангнус
источник
1

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

Но компиляторы намного эффективнее интерпретаторов. Если бы вы предложили написать переводчика в то время, люди бы подумали, что вы сошли с ума. Можете ли вы представить себе покупку компьютера за миллион долларов, а затем тратить 90% его мощности на интерпретацию кода?

gnasher729
источник
Я не очень разбираюсь в компьютерах 1950-х годов, но, по крайней мере, для простых машин фон Неймана более поздних десятилетий накладные расходы интерпретатора будут составлять от двух до пяти инструкций (может быть, всего от четырех до десяти циклов) на интерпретируемую инструкцию: декодирование, косвенный переход, возможно декодирование дополнительные аргументы. Если вы сделаете набор интерпретируемых команд достаточно высокоуровневым (таким образом, вы выполняете несколько машинных инструкций для каждой инструкции интерпретатора), это будет менее 90% и, возможно, даже приемлемо. Смотрите также: далее.
3
До того, как был написан первый компилятор, большинство программ были написаны на реальном машинном коде, а не на языке ассемблера (мнемоника оп-кодов).
mctylr
2
@delnan Эти системы работали с тактовой частотой в килогерцах, поэтому потеря производительности в 3-5 раз, скорее всего, была бы разницей между успешным завершением программы до сбоя системы из-за аппаратного сбоя (например, из-за перегоревшей вакуумной трубки) или нет. Аппаратные сбои были ежедневным явлением в 1950-х, если я правильно помню.
mctylr
delnan: Покажите мне переводчика, который может интерпретировать с пятью инструкциями. И Forth это не интерпретируемый язык, это мерзость :-). Извините, я имею в виду многопоточный язык. Что-то вроде BASIC требует миллиардов инструкций для интерпретации одного утверждения.
gnasher729
@gnasher: В 1974 году я создал высокопроизводительный интерпретатор BASIC для Keronix (к примеру, клоны Data General Nova), который использовал байтово-ориентированный P-код для кодирования оператора BASIC. Потребовалось около 25-50 машинных инструкций, чтобы «интерпретировать» pCode, 10 из них для самой выборки байтов. (Я сделал один токен на основе еще в 1969 году, который потребовал больше, потому что он фактически должен был повторно проанализировать выражения). Но это не было и не "gazillions".
Ира Бакстер
1

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

Обратите внимание, что целью ранних компиляторов было не создание файла на языке ассемблера или объектного кода на диске, а создание кода в ОЗУ, который был готов к выполнению. Это на самом деле на удивление легко, когда на пути нет операционной системы. Компилятор может генерировать код, начиная с одного конца памяти, и распределять переменные и цели перехода, начиная с другого. Если инструкция помечена меткой «1234», компилятор сохранит в переменной с именем «1234» инструкцию для перехода к текущему адресу генерации кода, создавая эту переменную, если она не существует. Оператор «goto 1234» создаст переменную «1234», если она не существует, и затем перейдет к этой переменной [которая, как мы надеемся, будет иметь переход в надлежащее местоположение, сохраненное в нем до выполнения этого оператора].gotoметка, которая еще не была определена, так как она знает, когда gotoкомпилирует, куда она собирается перейти - к переменной. Возможно, это не самый эффективный способ генерации кода, но он соответствует размерам программ, которые компьютеры должны были обрабатывать.

Supercat
источник
1
Диск? Ummmm ... нет. Tape. Большие, медленные, катушечные ленты. И их много. Я помню, как ходил на лекцию, прочитанную Грейс Мюррей Хоппер (для меня это было вдвойне интересно, потому что я был специалистом по системному анализу и мичманом в отряде Военно-морского флота в кампусе, а CAPT Hopper был военно-морским офицером). Она рассказала историю, в которой, по ее словам, ей пришла идея записать неиспользуемые части программы на ленту - она ​​назвала это «использованием вспомогательного хранилища». «Но, - сказала она, - идея не завоевала популярность, пока IBM не сделала то же самое и не назвала ее виртуальной памятью». CAPT Хоппер действительно не любил IBM ... :-)
Боб Джарвис
@BobJarvis: я не рассматривал этот аспект, но тот же общий однопроходный дизайн, который будет использоваться для компиляции готового к запуску кода в ОЗУ, может хорошо работать с ленточным накопителем; выходные данные компилятора будут отправляться на ленту, затем лента будет перематываться и считываться в последовательные адреса памяти и работать напрямую, без необходимости иметь какую-либо часть компилятора в памяти одновременно.
суперкат
0

Потому что для работы интерпретаторам нужны компиляторы.

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

В строгом смысле, компиляторы и интерпретаторы делают совершенно разные вещи. Компилятор считывает текст из некоторого источника и преобразует его в другой формат: ассемблер, машинный код, другой язык высокого уровня, структура данных или что-либо еще. Тем временем интерпретатор принимает какую-то структуру данных и на ее основе выполняет инструкции.

В настоящее время мы склонны считать «компилятором» компилятор, который был связан с генератором кода : программой, которая получает данные из некоторого источника и выводит код в некотором формате на основе того, что он видит. Это довольно интуитивно понятное использование для компиляторов, и это была одна из первых вещей, для которых были созданы компиляторы. Но если вы посмотрите на это по-другому, это похоже на то, что делает переводчик. Он всегда выводит код вместо выполнения более общих операций, но принцип тот же.

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

Вот почему компиляторы были написаны первыми. Идея интерпретации структур данных не была новой, даже когда были задуманы компиляторы, но компиляторы были «недостающим звеном», которое позволяло программистам создавать эти структуры из текста.

Ложка
источник
Оригинальный интерпретатор Basic для Apple] [насколько я понимаю, был вручную переведен в машинный код и никогда не существовал в машиночитаемом формате исходного кода. Я не уверен, какой «компилятор», как вы сказали, использовался для его создания.
суперкат
@supercat: Я не знаю, как был создан упомянутый вами интерпретатор Basic, но я не говорю о компиляторах, используемых для создания интерпретаторов. Я говорю о компиляторах, которые являются частью интерпретаторов. Как часть своего кода, интерпретатору Apple] [BASIC необходим какой-то способ чтения текстовых файлов, содержащих код BASIC, и создания синтаксического дерева из этого текста, который он затем выполняет. Код, который делает это, является компилятором; он не генерирует машинный код, но он все еще выполняет задачи чтения в коде и перевода его в другую форму.
Ложный
Типичные интерпретаторы ОСНОВНОГО микрокомпьютера не производят ничего, даже отдаленно напоминающего синтаксическое дерево. Я не знаком с оригинальным интерпретатором Apple BASIC (называемым «integer BASIC»), но интерпретатор BASIC, реализованный Microsoft для Apple («Applesoft BASIC»), Commodore и других компаний, сохранял текст программы как есть, за исключением двух вещей. : (1) каждой строке предшествует 16-битный номер строки и 16-битный адрес следующей строки, за которым следует нулевой байт; (2) каждое ключевое слово было заменено одним байтом с установленным старшим битом. Кроме этого, выражения были проанализированы ...
суперкат
... символ за символом, слева направо; оператор типа A = 1234 "преобразовал бы цифры 1, 2, 3 и 4 в число с плавающей точкой во время выполнения.
суперкат
@supercat: Это звучит ближе к байт-коду, чем к синтаксическому дереву, поэтому я ошибаюсь в этом конкретном случае. Но главное остается в силе: псевдобайтовый код все еще должен быть составлен из текста, а код, который делает это, является компилятором.
Ложный
-1

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

Лорен Печтель
источник