Примеры решения домашнего задания №0, курс математической логики, КТ, весна 2018

Яндекс.Контест

Домашние задания принимают в системе Яндекс.Контест в виде соревнования, доступного по ссылке. Единственным доступным компилятором в соревновании является Make. Вам необходимо послать свой проект, запакованный в zip-архив, и включить туда Makefile, специфицирующий, как собирать и запускать ваш проект.

Более формально:

• Во время стадии компиляции Яндекс.Контест вызовет make в корне вашего проекта для компиляции проекта.
• Во время запуска каждого из тестов Яндекс.Контест будет вызывать make run для запуска вашего проекта.

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

Полная спецификация того, что вам доступно для запуска из Makefile, на данный момент не известна даже нам. Возможно, она появится позже. На данный момент можно предполагать, что там находится:

Компилятор	Версия
gcc	4.9.2
g++	4.9.2
javac	1.8.0
ghc	7.4.1
scalac	2.9.1
python2	2.7.3
python3	3.2.3
ocaml	4.02.3
kotlin	NA
perl	5.14.2
go	NW
rustc	NW

По вопросам относительно того, почему всё настолько плохо, обращайтесь к Лиде.

Примеры решения задания №0

Так как посылка решений в Яндекс.Контест и структурирование своих собственных проектов может оказаться проблематичным для многих студентов, мы решили предоставить примеры решения домашнего задания №0 на некоторых языках, доступных в Яндекс.Контесте.

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

Также вопросы о работе с Яндекс.Контестом и вообще любые вопросы по курсу математической логики можно задавать в Telegram чате.

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

Пример решения на Java

Расположен в директории java-solution и содержит полностью рабочее решение домашнего задания №0, использующее стороннюю библиотеку ANTLR. Проект структурирован следующим образом:

• В директории src находится исходный код непосредственно проекта
• В директории lib находится jar-файл сторонних библиотек (т.е. библиотеки ANTLR)
• В корне проекта находится файл Makefile, в котором специфицирована процедура сборки, запуска и запаковки в zip-архив в формат, распознаваемый Яндекс.Контестом

Полный процесс сборки, использования и запаковки проекта:

$ make
...
$ echo "A&B" > input.txt
$ make run
...
$ cat output.txt
(&,A,B)
$ make pack
...
$ ls
...
hw0.zip
...

Пример решения на Scala

Расположен в директории scala-solution и содержит полностью рабочее решение домашнего задания №0 используя стороннюю библиотеку parboiled2. Тем не менее есть некоторые технические трудности в работе со Scala на Яндекс.Контесте. На текущий момент по умолчанию в запускаемом окружении Яндекс.Контеста доступна только scalac версии 2.9.1. Чтобы обойти данное ограничение, в засылаемый архив запаковывается бинарная версия scalac версии 2.12.4 и она используется для компиляции проекта вместо предоставленной окружением. Проект структурирован следующим образом:

• В директории src находится исходный код непосредственно проекта
• В директории lib/scala-2.12.4 находится немного обрезанный (вырезаны scala-xml, scala-swing и некоторые другие пакеты) дистрибутив scalac версии 2.12.4.
• В директории lib находится jar-файл сторонних библиотек (т.е. библиотеки parboiled2 и ее зависимости бибилотеки shapeless)
• В корне проекта находится файл Makefile, в котором специфицирована процедура сборки, запуска и запаковка в zip-архив в формате распознаваемый Яндекс.Контестом

Процесс сборки данного примера идентичен процессу сборки Java-примера.

Пример решения на C++

Расположен в директории cpp-solution и содержит полностью рабочее решение домашнего задания №0 используя сторонний инструмент bison. Проект структурирован следующим образом:

• В директории src находится исходный код непосредственно проекта
• В корне проекта находится файл Makefile, в котором специфицирована процедура сборки, запуска и запаковка в zip-архив в формате распознаваемый Яндекс.Контестом

Заметьте, что в среде запуска на Яндекс.Контесте отсутствует инструмент bison, поэтому парсер и лексер генерируются на стороне пользователя во время запуска make pack. Этот момент отличается от, например, примера решения на Java, т.к. пример решения на Java явно содержит в себе jar-файл ANTLR-а и запускает его для генерации парсера во время стадии компиляции на Яндекс.Контесте (т.е. во время запуска make).

Процесс сборки данного примера идентичен процессу сборки Java-примера.

Пример решения на Окамле

Расположен в директории ocaml-solution, использует Окамлевые инструменты ocamllex и ocamlyacc, в остальном похож на решение на C++.

Пример решения на Rust

Расположен в директории rust-solution и содержит полностью рабочее решение домашнего задания №0 с использованием пары сторонних библиотек.

Заметьте, что в среде запуска на Яндекс.Контесте компилятор Rust хоть номинально и присутствует, но не запускается, поэтому статически слинкованный исполняемый файл генерируется на стороне пользователя во время запуска make pack. Этот момент отличается от предыдущих примеров, где во время стадии компиляции на Яндекс.Контесте (т.е. во время запуска make) происходит что-то содержательное.

Для сборки проекта необходим кросс-тулчейн Rust под таргет x86_64-unknown-linux-musl (можно установить с помощью rustup: rustup target add x86_64-unknown-linux-musl) и подходящий линковщик (на GNU/Linux скорее всего подойдёт системный; на macOS можно установить из brew: brew install filosottile/musl-cross/musl-cross — в этом случае нужно создать файл .cargo/config со следующим содержимым:

[target.x86_64-unknown-linux-musl]
linker = "x86_64-linux-musl-gcc"

).

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

Пример решения на Haskell

Расположен в директории haskell-solution, использует генератор лексеров Alex и генератор парсеров Happy, что делает его похожим на решение на OCaml и C++. К решению прилагается Makefile, содержащий инструкции make и make run для сборки и запуска решения на сервере, а также make pack, работающий аналогично таковому для решения на C++.

Так как на Яндекс.Контесте недоступны такие замечательные инструменты, как stack и cabal, а также используется не самая свежая версия ghc, возникают определенные сложности с использованием разных удобных библиотек, например, Megaparsec. Мы будем думать, как исправить эту неприятную ситуацию наилучшим образом, но пока что рекомендуется использовать Alex и Happy для парсинга и использовать минимальный сет стандартных пакетов, входящих в дистрибутив ghc-7.10.3:

• array
• base
• binary
• bytestring
• containers
• deepseq
• directory
• filepath
• ghc-prim
• old-locale
• old-time
• process
• template-haskell
• time
• unix
• Win32

NB: обратите внимание, что в Makefile прописан абсолютный путь до ghc. Это связано с багом на сервере Яндекс.Контеста -- версия ghc, лежащая в PATH, попросту не работает.