05.11.2020 11:14
lockywolf 5 1100 Источник

TL;DR: Я написал и выложил на всеобщее обсуждение Scheme Request for Implementation 216. Он нацелен на то, чтобы одна из самых известных в мире учебных программ по Computer Science, Structure and Interpretation of Computer Programs, стала выполнимой в полном объёме не только на MIT/GNU Scheme, но и на других интерпретаторах и компиляторах, в частности, на вашем любимом. И если раньше запрос в багтрекер "сделайте, пожалуйста, поддержку SICP" звучал бы расплывчато, то после принятия данного SRFI, поддержка SICP должна стать намного более общепринятой.

Чтобы написать этот документ, я проработал SICP целиком (что потребовало более 700 рабочих часов и заслуживает отдельного поста), выделил части, до сих пор не вошедшие в стандарт, и сформулировал их в качестве двух документов, SRFI-203 (принят в сентябе 2020), и данного, SRFI-216, к которому я и приглашаю всех присоединиться.

За техническими деталями и подробностями, прошу под кат.

Что такое "Структура и Интерпретация Компьютерных Программ"? (Structure and Interpretation of Computer Programs)

Это одна из самых известных учебных программ по "общему программированию", ранее преподаваемая в Массачусеттском Технологическом Институте (MIT), в качестве вступительной, а ныне перенесённая на старшие курсы из-за гигантского объёма и глубины, которая, как считается более программисту не требуется. Курс проводит студента от однострочной программы, которая складывает два числа, до написания собственной реализации Scheme, включающей компилятор и интерпретатор. Первое издание книги, в которой изложена программа, было выпущено в 80е годы, второе вышло в 1996 году. В книге более 350 задач. Существует русский перевод. Книга была одной из первых, к которым стал прилагаться веб-сайт. (Который работает до сих пор.)

Чем она хороша?

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

Чем она не устраивает сейчас?

За исключением двух программных систем, (MIT/GNU Scheme и Racket, из которых только одна (MIT) является Scheme-системой в полном смысле этого слова) SICP непроходима на большинстве Схем, которые встречаются в живой природе. Представьте, что книжка, "Язык Си" позволяла бы вам выучить только Intel C.

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

Зачем проходить SICP на других Scheme-системах?

Одно из главных достоинств SICP -- это то, что он рассказывает, как построить "систему искусственного интеллекта" (в данном случае под ней понимается язык программирования высокого уровня) на практически любом Тьюринг-полном субстрате. Но тем более обидно осознавать, что проработать её в полной мере можно исключительно на двух программных системах, одна из которых не поддерживает Windows (MIT, по крайней мере, официально), а вторая вообще заявляет, что не является Scheme.

К тому же, основная сила Scheme в наши дни -- это не сила языка общего назначения ( программы общего назначения тоже получаются отличные, а компания Cisco до сих пор поддерживает собственный оптимизирующий интерпретатор), а возможность встраивания его как языка расширения в практически любой программный продукт, написанный на любом языке. Есть Схемы, работающие на JVM, CLR, Fortran, JavaScript. Схема является языком написания расширений расширения таких проектов как GNU Debugger, GNU GIMP и GNU Guix.

Для заинтересовавшегося программиста логичнее осваивать SICP на той Scheme, которая лучше всего встраивается в ту инфраструктуру, к которой он привык.

На реализацию этой цели и направлен данный SRFI.

Что же делать?

Поскольку автор сих строк всё-таки приобрёл (ложное) ощущение всемогущества, он решил поставить пару бетонных опор для того мостика, о котором говорилось несколькими абзацами выше. Конкретно это выразилось в написании документа Scheme Request For Implementation, под номером 216, в котором собран список требований, которым должен удовлетворять интерпретатор Scheme для того, чтобы на нём запускался полный набор примеров программного кода из SICP.

Конечно, сам факт наличия документа ещё ничего не гарантирует, необходимо, чтобы функционал был реализован в программных системах, однако документ сопровождается "возможной реализацией", которая работает как минимум на одной программной системе, отсутствующей в списке выше (Chibi-Scheme).

Что входит в SRFI-216?

Функционал, требуемый для прохождение SICP, но не общепринятый.

Случайные числа.

Предлагается функция (random x), которая генерирует случайное целое число меньше заданного. В связи с тем, что Схема спроектированна так, чтобы работать в том числе на CPU, не имеющих ни доступа к часам, ни источника энтропии, средства для работы со случайными числами не входят в стандарт R7RS-small. (Но будут входить в -large, вероятно.)

Доступ к дате и времени.

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

Булевы значения.

В связи с тем, что Схема очень старый язык, работа с логическими выражениями была в разных реализациях осуществлена по-разному. Например, в каких-то реализациях символ #f, существует, а в каких-то нет. Также, во некоторых системах, по традиции LISP, пустой список также является "ложным" значением.

Для большей абстракции, таким образом, SICP нигде не использует ложное выражение само по себе, а пользуется переменными/константами true и false, которые гарантированно имеют, соответственно, верное значение, и ложное значение.

Эти две константы также реализуются в данном документе.

Многопоточное программирование.

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

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

SICP, соответственно, требует существование двух примитивов, parallel-execute и test-and-set!, которые ровно эти две концепции и призваны прояснить.

Сама же по себе многопоточная модель Scheme сходна с таковой в Java.

Streams.

"Стримы" -- это бесконечные структуры данных, схожие с генераторами/итераторами в языке Python (или использовавшимся ранее xrange), только несравнимо более гибкие.

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

Соответственно, эта структура также реализуется в данном proposal.

Что насчёт графики?

Работа с графикой не затрагивается в данном документе. Возможные примитивы опубликованы в SRFI-203.

Чем я могу помочь?

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

Если у вас уже есть любимая реализация Scheme, поинтересуйтесь у людей, которые за неё отвечают, возможна ли реализация данного стандарта в вашей любимой системе.

Расскажите своим друзьям, студентам и энтузиастам, о том, что учиться по SICP не обязательно должно быть процессом, полным боли.

Если вы преподаёте программирование, или функциональное программирование, или у вас есть знакомые преподаватели, предложите им взглянуть на предлагаемое расширение, их фидбек будет в высшей степени ценным.

Ну, и надо сказать, что я просто считаю Схему отличным языком. Пользуйтесь Схемой, это можно делать на громадном количестве платформ, включая Plan9, Android, WebAssembly, и встраивать в другие программы.

Как именно можно присоединиться к обсуждению, можно найти по ссылке: https://srfi.schemers.org/srfi-216/

Контакты

Если вам показался этот пост полезным, на мои заметки можно подписаться, или задонатить без подписки: