Комментарии 29
Забыл добавить — особенных требований к знанию языка Racket не требуется. То есть, достаточно пройти первую треть SICP или https://htdp.org или ещё что-то подобное. Для Racket написаны хорошие руководства и cheat sheet — https://docs.racket-lang.org/racket-cheat/index.html , по которым легко определяется то, что нужно.
Для алгоритмики достаточно базового набора функциональщика — map, filter, filterMap, fold(left/right) + базовый набор "питониста" — hash-map, dictionary + начальные сведения по графам.
парсер для LISP на Parsec у меня занимает 2 (два) часа
Слушайте, но это же в первый раз, очевидно? Все-таки парсек — это близкий аналог регулярок, и в него надо хоть немного вникнуть.
Ну интерпретатор LISP'а я писал первый раз. Парсер на именно Parsec — кажется второй раз. Я не предлагаю писать парсеры на скорость, и даже не особо хвастаюсь, просто так получилось.
Парсер — это самое там скучное, поэтому прекрасно, что он остался за бортом!
Ну да, что и там, и там какой-то парсинг + это прямо встроено в код, а не используется генератор аля bison.
Меня всё время интересовал вопрос - чем отличаются на примере аппликативный и монадический парсеры. Скажем, вот ту же грамматику LISP может съесть аппликативный парсер? А Cшную?
Понятно что это не эквивалент. Я имел в виду, что даже на то, чтобы освоить регулярки, которые более простые, нужно какое-то время (у некоторых это вообще не получается сделать). Поэтому два часа на написание парсера лиспа — вполне нормальное время для первого раза.
Когда учился в НЭТИ, там был полугодовой курс создания компилятора (примерно 90 листов конспекта). Мне было очень интересно.
Если есть желание создать компилятор для DataFlow системы (компьютер 5 поколения), то пишите (будет совсем новый опыт).
Курс «компиляторостроения» преподается в рамках какого то «учебного процесса» в университете или другом учебном заведении?
Да, в Indiana University Bloomington - https://www.indiana.edu/
Вот страница курса: https://iucompilercourse.github.io/IU-Fall-2021/
Создание нейронного компьютера — не интересно (не является универсальным вычислителем).
P.S. А, не рассматривалась ли возможность, к примеру, включения в курс и темы применения конкатенативных языков Форт направленности (Factor) на каком то «уровне» курса/примеров?
К примеру, в книге компиляторов построения от Серебрякова трансляция производится в стековый вычислитель.
А в этом проекте — Forthress — приложениe к книге низкоуровневого программирования для x86-64, Форт выбран как иллюстрирующий материал.
Есть и такой проект cc64 cc64 is a small-C compiler, written in Forth (here's why), targeting the 6502 CPU. (возможно выглядит в чём то «наивным» в сделанном варианте)
true-grue как мне известно Форт тоже использует или использовал в том или ином варианте в своей профессиональной деятельности.
Интересно, что процессоры/контроллеры MISC архитектуры почти не представлены на рынке как вычислительные устройства при всех их имеющихся достоинствах и недостатках, да и опубликованных работ в этом направлении не так много представлено в i-net сети.
Может быть этому какое то объяснение, кроме того, что RISC архитектура «круче»?
На странице курса некоторые ссылки на дополнительные материалы не валидны.
Только ссылка на "решение", ну и ладно. Не, там косяков масса, но, в основном, в теле книги — она явно не "книжного качества". :-(
А, не рассматривалась ли возможность, к примеру, включения в курс и темы применения конкатенативных языков Форт направленности (Factor) на каком то «уровне» курса/примеров?
Конкретно в этот? Наверняка — нет, оно там ни к чему. И так объём весьма и весьма велик.
Серебрякова посмотрю, спасибо.
P.S. В тему дополнительные проекты/материалы для компилятор построения.
libFirm — A graph based SSA intermediate representation
firmforth is a just-in-time-compiling forth-like system using libfirm.
It is small and comprehensible and was written to evaluate JIT-compilation using libfirm.
LibFirm on Github
Как-то тема не соответствует посту. При чем тут Nanopass?
"в рамках Nanopass компилятор — это некоторое последовательное применение процедур-проходов к тексту программы..."
Почти все современные компиляторы и компиляторные инфраструктуры так и устроены, при чем тут именно Nanopass? Смысл слова "Nano" не раскрыт. Скорее статью стоило бы назвать - "как я проходил курс университета xxx по компиляторам".
Но в целом круто, примите мой плюс в карму.
Спасибо, но позволю себе несогласиться, в конце-концов это же я выбирал название. :-)
Nanopass — это "человек и пароход": определённый фреймворк (которым я не пользовался, но, видимо, надо будет увидеть его в деле), а кроме того подход чёткого разделения этих проходов с явно прописанными интерфейсами. Прошу прощения, что недостаточно чётко это сформулировал.
То есть, на вход каждого прохода попадает программа на языке с чётко определённой семантикой (для него есть тестовый интерпретатор!), а после каждого прохода получается программа на, как правило, другом, но не менее чётко определённом языке со своим интерпретатором. То есть, вы можете "запустить" программу после любого прохода и сравнить её результат с интерпретацией изначальной программы.
Нет, не каждый компилятор устроен по архитектуре Nanopass. К примеру, знакомый мне Ocaml хоть и содержит проходы, они, как правило, комплексные. Внутренние языки компилятора Ocaml не имеют опубликованной чётко определённой семантики. И хотя есть механизмы печати внутренних представлений, нет никаких интерпретаторов.
Название статьи двойное, вторая часть как раз о курсе. Здесь, на Хабре термин nanopass упоминается впервые, поэтому если вы можете рассказать по этой теме ещё, напишите, пожалуйста, заметку.
Всегда считал подход gcc (там не один десяток проходов и ан min-end и на back-end) превалирующим в сегодняшнем компиляторостроении (JIT-компиляторы, конечно имеют больше trade-off по скорости-качеству кода).
Объясните в чём, по-вашему, ключевые отличия nanopass от многопроходного компилятора?
ПС
Список проходов в min-edn для gcc.
https://gcc.gnu.org/wiki/MiddleEnd
Объясните пожалуйста [прим. Vkni] в чём, по-вашему, ключевые отличия nanopass от многопроходного компилятора?
В том, что в gcc это несколько стихийно, и далеко не везде (например распределение регистров - это отдельные модули). Кроме того, не фиксированы и не описаны хорошо промежуточные языки, нет интерпретаторов для промежуточных языков.
А так, если смотреть "из простых программистов", то да, совершенно ничем - и там, и там консольная программа-конвейер.
Насколько я понимаю, для коммерческого применения этот подход слегка
хуже обычного, т.к. компилятор из-за огромного кол-ва проходов
получается несколько медленнее
А значимо большее число проходов, в сравнении со стандартным подходом в компиляторостроении (скажем в gcc) действительно имеет место быть? Сколько проходов в типовом nanopass - компиляторе?
П.С.
Спасибо, если не примете технический вопрос к содержимому статьи на личный счёт.
Насколько я понимаю, где-то в 2-3 раза. И ухудшение производительности на десятки процентов.
Зато можно строить компилятор итеративно (по слоям), проще его проверять на корректность (это из разряда "тише едешь - дальше будешь" - в программировании очень хорошо работает). Можно до какой-то степени тасовать эти слои, заменять, скажем, распределение регистров на работу исключительно со стеком.
Был с вами существенно не согласен, почти по каждому написанному пункту.
Залез вот сюда: nanopass.org -> papers -> http://andykeep.com/pubs/dissertation.pdf
Судя по всему это какой-то сугубо академический подход (упоминания SSA-IR или его аналогов не нашёл, то, что они называют intermediate language основано на чём-то похожем на lambda-calculus (p.134)).
Собственно кажется, что сравнение с промышленными компиляторами, в этом случае малоосмысленно.
В этом смысле отзываю изначальный вопрос про gcc - т.к. это просто два принципиально разных подхода.
ПС
А может мне объяснить кто-нибудь (так получилось, что в под вашем постом, просто не знаю кого тэгнуть): почему практически все papaer-ы относятся к front-end (ну или к тому, что в промышленном компиляторе назвали бы так)?
В конце концов, тот же gradual typing, рассматриваемый в главе 10 — это вообще слишком близко к переднему краю исследований, чтобы рядовой программист был об этом наслышен и, следовательно, заинтересован.
Подождите, если мы не запутались в терминах, то gradual typing был ещё в начале 80-х в протолиспах, которые потом собрались в трансформера Common Lisp.
Раскройте тему, пожалуйста. Я под gradual typing подразумеваю то, чем активно занимались ракетчики года 4 назад — попытки построения эффективного сплава Хиндли-Милнера и динамической типизации, когда у вас типы стираются в как можно большем числе мест.
А, хм. Я под gradual typing имею в виду последовательную типизацию, то есть тот случай, когда вы можете в некоторых местах программы указывать типы, а можете не указывать, и в последнем случае компилятору ничего не остаётся, кроме как под капотом использовать обобщённые ("generic") версии операций, которые делают диспетчеризацию по типам уже в рантайме. Для примера:
CL-USER> (disassemble #'(lambda (x)
(declare (optimize (safety 0) (debug 0)))
(1+ x)))
; disassembly for (LAMBDA (X))
; Size: 18 bytes. Origin: #x5367A4D6 ; (LAMBDA (X))
; D6: BF02000000 MOV EDI, 2
; DB: FF1425E8050050 CALL [#x500005E8] ; #x52A00EA0: GENERIC-+
; E2: 488BE5 MOV RSP, RBP
; E5: F8 CLC
; E6: 5D POP RBP
; E7: C3 RET
NIL
CL-USER> (disassemble #'(lambda (x)
(declare (optimize (safety 0) (debug 0))
(type fixnum x))
(the fixnum (1+ x))))
; disassembly for (LAMBDA (X))
; Size: 10 bytes. Origin: #x5367A5E6 ; (LAMBDA (X))
; E6: 4883C202 ADD RDX, 2
; EA: 488BE5 MOV RSP, RBP
; ED: F8 CLC
; EE: 5D POP RBP
; EF: C3 RET
NIL
Обратите внимание, как во втором случае, после указания типов аргумента (x) и возвращаемого значения функции, компилятор заменяет вызов функции GENERIC-+, которая осуществляет диспетчеризацию времени выполнения, на обычную ассемблерную инструкцию ADD.
Nanopass или как я писал компилятор этой осенью