Skip to content

Latest commit

 

History

History
370 lines (347 loc) · 34.4 KB

tasks.md

File metadata and controls

370 lines (347 loc) · 34.4 KB
Raw
Заняты "академиками"
  1. F# (Быков на F#)
  2. Parallel model (Фаст)
  3. Python (Бакаев)
  4. Cи (Andrew)
  5. Дмитрий Кузнецов (Стрёмное подмножество c#)
    • Async/await
    • Стрёмный LINQ синтаксис: select ... from ... where ...
    • лямбды с присваиваниями и замыканиями
    • Пользовательские классы можно не делать, один класс Program c кучей статических методов пойдет.
    • Стандартные типы данных, массивы
      • продемонстрировать на массивах ArrayTypeMismatchException
  6. Pascal (Казанцев Антон)
    • функции/процедуры, присваивание, стандартные типы и типы-записи
    • динамическое выделение памяти не надо
Для "новеньких" (надо минимум 23 домашки)
  1. OCaml + ADT
    • стандартный мини-язык, базовые типы,
    • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
    • алгебраические типы как основной способ проектирования типов
    • можно поддержать пары, но можно и обойтись алгебраическим типом с одним конструктором
    • разумеется, объявления типов, паттерн-мэтчинг и типизация
    • присваивание не надо
    • исключения не надо
  2. OCaml + полиморфные вариантые типы
    • Как предыдущий проект "OCaml + ADT", только вместо алгебраических типов полиморфные варианты как они есть в OCaml
    • Объявления типов можно не делать
  3. Haskell + ADT
    • Как "OCaml + ADT" только стратегия вычислений другая. Ну, и из-за этого примеры кода могут быть написаны по-другому.
  4. OCaml + объекты
    • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
    • в OCaml есть интерсные объекты и их типизация, нужно поддержать объекты+методы+поля
    • (может быть классы и наследование тоже надо будет, но пока не уверен)
    • как тесты предлагаю реализовать некоторые струтуры данных как камлёвые объекты и посмотреть, что будет
  5. OCaml + effects (2 человека)
    • супер-модное в наши дни движение в мире ФП
    • По сути, это исключения, но в момент обработки которых у нас есть функция, которой можно был передать значение, которое должно было бы быть вместо бросания исключение, и продолжить исполнение с места бросания исключения.
    • Туториал в контексте OCaml https://github.com/ocamllabs/ocaml-effects-tutorial
    • два человека только потому, что хочу чтобы задачу кто-то взял. А так это очень сильно напоминает задачи про delim/cc
  7. OCaml + GADT (2 человека)
    • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
    • OCaml где алгебраические типы заменены на обобщенные (generalized) алгебраические типы
    • Вывод/проверка типов там сложнее, чем для обычных алгебраических, поэтому два человека
    • Умная сслыка, описывающая что примерно вас ждет
  9. OCaml, присваивание, именованые и опциональные аргументы
    • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
      • придется поддержать присваивание в замыканиях
    • а также учесть, что присваивание влияет на вывод типов
    • стандартные типы (числа, списки, option)
    • функции, рекурсия,
  10. SML + equality types + value restriction
    • Почти предыдущая задача, но проще
    • Немножко другой парсер, потому что SML немножко отличается
    • equality types:
      • в типах функций появляются типовые переменные с двумя апострофами, что означает, что туда можно подставлять только типы, на которых работает функция проверки на равенство (функции и вещественные числа нельзя сравнивать)
    • какая-то ссылка https://users.cs.fiu.edu/~smithg/cop4555/valrestr.html
  11. OCaml с типизированными эффектами
    • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
    • https://www.janestreet.com/tech-talks/effective-programming
    • Идея заключается в том, что теперь мы будем перечислять в типе функции-стрелки эффекты, которые совершает функция

      • Обычная стрелка -> делает что угодно

      • Длинная стрелка --> (или -[]->) -- это чистая функция: не присваиваний, ввода-вывода. Ничего не делает такого.

      • Над стрелкой можно перечислять, что она делает:

        • -[IO]-> делает ввод-вывод
        • -[exc Not_found]-> кидает исключение Not_found
        • -['a]-> совершает какой-то эффект, но он не указан (полиморфизм)

      • Пример:

        val id : 'a --> 'a
val print_int: int -[IO]-> unit

let map : ('a -['e]-> 'b) --> 'a list -['e]-> 'b list = fun f xs ->
  match xs with
  | [] -> []
  | x::xs -> (f x) :: (map f xs)

let _ : 'a list --> 'b list = map id
let _ : int list -[IO]-> int list = map (fun n -> print_int n; n+1)

        Фунция id чистая, поэтому над стрелочкой ничего не написано

        Функция print_int совершает ввод-вывод, что указано в типе

        List.map полиморфна (как обычно) по типу элементу списка, но также полиморфная по типу эффекта переданной функции, что указано в стрелке, которая выдает результат. Первая стреклка в типе map чистая, так как при передаче аргументов ничего не вычисляется и эффектов не совершается. В map id не совешается эффектов, поэтому типовая переменная 'e сунифицировалась с отсутсвием эффектов. Во втором примере из-за того, что переданная функция совершает ввод-вывод, система типов догадывается, что и вычисление map совершает ввод-вывод.

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

    • Итого, надо реализовать miniML
      • Стандартные штуки: числа, строки, функции высшего порядка, пары, списки
      • C эффектами: присваивание, печать на консоль и try/catch/raise для пары захардкоженных в язык исключений
      • С системой типов в описанном выше смысле.
  12. OCaml + implicits
    • В OCaml нет ad hoc полиморфизма (то, что вы знаете под термином overloading), поэтому многим хочется иметь в грядущей версии OCaml следующую штуку
      • в области видимости объявляется некоторое количество OCamlовских модулей
      • у функций могут появляться неявные аргументы (implicit), которые программист не передает явно руками
      • момент вызова функции компилятор ищет в области видимости подходящие по типу модули и подставляет и вместо неявных аргументов, если не найти -- ошибка, если больше 1го подходящего варианта -- тоже
  13. Scala 3 + givens
    • как предыдущее, только вместо OCaml -- синтаксис Scala 3, вместо камлёвых модулей -- скальные объекты
  14. Scheme + call/cc
    • относительно легко гуглящаяся особенность Scheme, человеку в том году удалось такую домашку сдать
    • call/cc
    • целые числа, рекурсия, списки, печать на консоль
    • функции обычные и анонимные, замыкания и рекурсия
    • присваивание не надо
    • quote/unquote
    • парсер очень простой
    • никаких статических типов, разумеется, нет
    • учитывая следующую задачу, получается в некотором смысле на двоих
  15. Scheme + delim/cc
    • почти как предыдущая задача, только понятней
    • Кратко про delim/cc
      • есть две новые конструкции в языке: reset (fun () -> M) и shift (fun k -> M)
      • Пример: reset (fun () -> 2 + 2 * shift (fun k -> k 20))
        • Наличие одинокого reset не влияет на вычисление
        • Когда исполнение доходит до shift, то вместо аргумета подставляется функция, которая "зажата" между этим shift и ближайшим reset, В даннои случае это fun y -> 2 + 2 * y
        • таким образом, выражение выше вычисляется в 42
  16. OchaCaml (Caml Light + delim/cc) (2 человека)
    • стандартные типы (числа, списки),
    • функции обычные и анонимные, замыкания и рекурсия
    • конструкции для отладочной печати
    • delim/сс
    • полиморфные типы для всего этого
      • типизация там необычная, надо по одной ссылке долистать до описания того, как это типизировать; по другой ссылке долистать до способов написания интерпретатора/компиляции
    • По сути эта задача и две предыдущие -- суть одно и то же
  18. мини-Coq с индуктиыными типами (2 человека)
    • похож на OCaml + ADT, но с некоторыми ограничениями
    • вводятся ограничения на объявления алгебраических типов
      • чтобы избегать парадокса Карри
      • иметь индуктивные типы, размер которых очевиден
    • объявляемые функции принимаются только если они завершаются
      • проверка делается на основе рассуждения "убывает по такому-то аргументу"
  20. Котлин, ООП и flow-sensitive typing
    • Стандартные типы данных, функции/методы, присваивание
    • функции/методы обычные и анонимные, замыкания и рекурсия
    • ООП, наследование, вызов методов, изменение полей
    • Flow-sensitive typing: вывод того, может ли значение быть null или нет
      • Важный пример отсюда должен работать
    • Давать на двоих не хочу, так как про всё это вам должны были рассказывать.
  21. C++ и наследование
    • Объявления функций, приваивание, рекурсия, стандартные типы, что-то для печати на консоль.
    • Объекты, поля, методы
    • Анонимные функции можно не делать
    • Наследование: public, private, protected, virtual
      • diamond problem
  22. Java и generics (2 человека)
    • целые числа (float не нужно)
    • рекурсия
    • стандартные конструкции языка
      • if, else, while (взаимозаменяем с do { ... } while), for
      • break и continue оставить на потом
      • switch можно не реализовывать
      • исключения и тернарный оператор не нужны
    • присваивание
    • анонимные функции
    • классы (без enum), интерфейсы, наследование
    • поддержка многопоточности, нативного кода и сериализации не нужна
    • многофайловость не требуется
    • передача аргументов командной строки в main не нужна
    • в каком-то виде понадобится поддержка функций стандартной библиотеки
    • из методов класса Object достаточно поддерживать hashCode, equals и toString
    • реализовать более точное указание generic параметров (например, <? super x> и т.п.)
      • если заработает проверка типов (нужно отдельно реализовать тайпчекер) и интерпретатор на вот такой программе, то будет круто
      interface Z {}
interface N<x> {}
interface L<x> {}
interface Qlr<x> {}
interface Qrl<x> {}
interface E<x> extends
   Qlr<N<?super Qr<?super E<?super E<?super x>>>>>,
   Qrl<N<?super Ql<?super E<?super E<?super x>>>>> {}
interface Ql<x> extends
   L<N<?super Ql<?super L<?super N<?super x>>>>>,
   E<Qlr<?super N<?super x>>> {}
interface Qr<x> extends
   L<N<?super Qr<?super L<?super N<?super x>>>>>,
   E<Qrl<?super N<?super x>>> {}
class Main {
   L<?super N<?super
   L<?super N<?super
   L<?super N<?super
   E<?super E<?super Z>>>>>>>>
      doit( Qr<? super E<? super E<? super Z>>> v ) {
         return v;
   }
}
  24. Refal 5
    • одскульный отечественный язык программирования, где последовательности можно мэтчить не только с начала, но и с конца
  25. Ruby
    • Известный язык программирования, по типу Питона
    • Стандартные конструкции, присваивание,
    • Рекурсивные и анонимные функции, замыкания
    • Объекты
    • Статической типизации там нет, потому и не надо
    • method_missing -- отличительная штука Ruby, где можно сказать, что делать, если метода нет
      • с помощью обработки отсутсвующего метода предлагаю сделать примеры про реализацию тестирования кода в стиле rspec
    • Прикольные штуки из WAT talk
  26. Javascript
    • Объекты, числа, строки, массивы
    • Функции обычные и анонимные, замыкания, рекурсия
    • Типичное для Javascript прототипное наследование
    • Прикольные штуки из WAT talk
  27. Bash
    • Надо будет сделать основную штуку, что отличает bash от всего остального -- вызов сторонних исполняемых файлов по ходу дела
      • Чтобы Ctrl-C их сторонних файлов возвращался обратно в bash
      • Чтобы вызов через пайпы правильно соединял различные stdin и stdout
    • Кавычки одинарные и двойные
      • Escape character сделайте для перносов строк и экранирования кавычек. Всякие \t не надо.
      • Нужны ли ANSI-C Quoting и Locale-Specific Translation?
    • Комментарии не надо
    • Команды
      • Простые команды
      • Пайплайны
        • поддержка [time [-p]] и [!] не нужна
      • Списки команд && нужны
      • compound
        • until, while (один из)
        • for два варианта
        • if, case
          • select не нужен
        • ((...))
        • [[...]]
          • Влечет за собой поддержку Conditional Expressions
            • Только С locale
        • без Grouping Commands
        • без coproc
    • Функции (два варианта синтаксиса)
      • С рекурсией.
    • Параметры
    • Переменные, разумеется. На += можно забить
    • Нужна ли поддержка positional parameters? Нужно будет думать, откуда их брать
      • Нет. Если что, то их можно взять из Sys.argv
    • Нужна ли поддержка special parameters?
      • Нет
    • Expansions
    • Brace expansion
    • Нужно ли поддерживать Tilde expansion? не надо
    • Shell Parameter Expansion
    • Двойные backtickи надо
    • Arithmetic Expansion, без него какой-нибудь факториал не написать
    • Process Substitution не надо
    • Word Splitting сделайте дефолтный. Вообще, всякие переменные можно брать из окружения, в котором запушен интерпретатор BashML
    • Filename Expansion
    • Quote Removal
    • Pattern Matching
      • Рекурсивный ** не нужен
      • Нужно ли поддерживать особые случаи в [...]? я не знаю что это такое
        • Можно ли при - использовать лишь стандартную "C локаль"? Да, только стандартную
        • Нужно ли поддерживать [:class:], [=c=], [.symbol.]? я не знаю что это, скорее всего нет
      • Composite patterns не нужно
    • Перенаправления
      • <, >, >>
      • Custom descriptors не нужно
        • Если да, то нужно ли поддерживать дублирования и перемещения дескрипторов?
        • Если да, то нужно ли поддерживать замену кастомных дескрипторов переменными?
      • разницу между > и >| не нужно
      • Нужно ли поддерживать >& или &>? По мануалу, последнее предпочтительнее, но первое принадлежит к более широкому классу "дублирований", о которых выше
        • &>word не надо, но >word 2>&1 хочу, чтобы работало
      • Here Documents и Here Strings нет
      • Нужно ли поддерживать <>? нет
    • #! не надо
    • Массивы нужно, потому что других структур данных там вроде бы нет
      • Индексирование с конца не надо
      • Ассоциативные надо, инициализацию сделайте какую-нить одну из двух видов
        • name=(key1 value1 key2 value2 ... )
        • name=( [key1]=value1 [key2]=value2 ...)
  28. Cypher
    • мини-язык для доступа к графовым базам данных
    • простой парсер, простой интепретатор, который исполняет запросоы на конкретных графах
    • оптимизации запросов я пока не придумывал, но я думаю, что их придумать не сложно
  29. miniKanren -- относительно простой язык реляционного (логического) программирования. Может быть в разных синтаксисах, проще всего найти описание в синтаксисе Scheme в книжке Reasoned Schemer (ещё есть стартовый туториал). Состоит из довольно малого количества понятий. Ниже кратко опишу в синтаксисе Scheme.

    • Логические переменные, им можно сопоставлять выражение с логическими переменными (или без) внутри и получать подстановку.

    • Goal (цель) -- то, что можно посчитать. По сути функция из стартовой подстановки в ленивую последовательность подстановок.

    • Примитив (run number (vars) goal) -- вычисляет goal, подставляя туда стартовую пустую подстановку; и достает из результирующих подстановок (нужны первые number штук) посчитанные значения переменных верхнеуровневых vars

    • Унификация (== expr expr) -- позволяет получать знания о подстановках переменных.

    • Объявление новых логических переменных fresh (vars) goal для их использования. Например:

      > (run 1 (q) (fresh (x y z) (== x z) (== 3 y)))
(_.0)

      Выдан один ответ, переменная q с номером 0 является свободной, потому что с ней никто не унифицировался

      > (run 1 (y)  (fresh (x z)   (== x z)    (== 3 y)))
(3)

      Мы проунифицировали y и 3, что и видно в ответе.

    • Конъюнкция: если пишем fresh (...) goal1 goal2 ... то все цели неявно объединяются конъюнкцией. Конъюнкция (conj l r) является целью и вычисляется следующим образом:

      • Запускаемся на какой-то подстановке. Левая часть дает какой-то ответ (подстановку), и её и будем передавать в правый goal r. Там получатся какие-то ответы, их складываем в ответ. Затем делаем то же самое со вторым ответом из l и т.д. От перемены мест конъюнктов ответы не меняются, но может нарушиться завершаемость вычисления этих ответов!

    • delay (пауза) -- указание, что сейчас можно поиск в этой ветке приостановить и поискать в другой. Обычно вставляется внутрь конъюнкции и после fresh.

    • Дизъюнкция: (conde (goal1 goal2 ...)) -- альтернатива, пытаемся искать ответ разными способами. Если вычисляем goal до конца -- будет поиск в глубину (плох тем, что если в одной ветке никогда не найдется ответ -- мы можем там зависнуть). Если делаем по одному шагу в каждом goal --- поиск в ширину (плох тем, что пространство поиска растёт очень быстро). В miniKanren принято делать interleaving search: вычисляем первый дизъюнкт до паузы, затему второй, 1й, 3й, 1й, 2й и т.д. Грубо говоря, первый работает в половине случаев, второй -- в четверти и т.д. Таким образом получается что-то среднее между в глубину и в ширину.

    • TODO: описать disequality constrains.

  30. Ассемблер x86_64 --- очень простой язык и для парсинга, и для реализации интерпретатора. Халява.
    • Язык должен быть настоящим ассемблером, т.е. входные программы должны компилироваться соответствующим компилятором и выдавать ответ как в интерпретаторе
    • Примеры стоит взять из первой части книжки И.Жиркова "Low-level programming".
    • Чтобы задача не была чересчур простой, хочу также в ассемблере SIMD операции и тесты к ним (перемножение вектора/матрицы на вектор/матрицу)
  31. C# c исключениями.

    • Стандартные конструкции языка.

    • Целые числа, строки, стандартные функции работы с ними.

    • Массивы и лямбды не надо.

    • try/catch/finally

    • Исключения

      • Пользователь может наследоваться от класса Exception и объявлять свои исключения без новых методов внутри. Получатся какие-то супер-сокращенные объекты с иерархией наследования высоты 2 и синтаксисом на подобие record'ов. Короче, полноценные объекты не надо.
      public class Person : Exception {
  public string FirstName {get; init;}
  public string LastName {get; init;}
}
var a = new Person { FirstName = "Michael", LastName = "Page" };
      • Исключения должны уметь выдавать backtrace c именами функий и позциями в файле, где они вызывались. С этим скорее всего придется запариться
      • Фильтры исключений, которые я просил в том году у Мирошникова -- не надо.

    • Какой-нибудь тайпчекер на случай, чтобы отфильтровывать бредовые программы

    • Какое-нибудь API для чтения/записи файлов, чтобы можно было содержательно протестировать finally

  32. Объектно-ориентированый C# c классами, интерфейсами (Алимов)
    • Наследование классов и интерфейсов, без generics.
    • public/private/protected и override.
    • Стандартные конструкции языка + приведение типов объектов.
    • Целые числа, строки, стандартные функции работы с ними; массивы и лямбды не надо.
    • Что-нибудь для печатанья значений переменных в языке.
    • Какой-нибудь тайпчекер на случай, чтобы отфильтровывать бредовые программы.
    • new методы
      • Я слышал, что при их использовании вместе с интерфейсами, там возникает какая-то нетривиальная семантика. Надо будет разобраться. Вот пример.
Определюсь/допишу потом если тем будет не хватать/или кому-то очень захочется/и не будет лениво их доформулировать
  1. Pascal (записан за Казанцевым)
    • алгебраические типы данных variant records (пункт 12).
  2. Go
  3. Fortran?
  4. Visual Basic.NET (клон C# с другим синтаксисом)
    • На вики есть список отличий. Если сесть и посмотреть, то наверняка можно придумать задачу.
  5. F# + active patterns
  6. C# c паттерн-мэтчингом
  7. Какие-нибудь смарт-контракты
  8. MSIL
  9. Makefiles -- может оказаться чересчур просто
  10. С# с многофайловостью, мультиметодами и экстеншинами
  11. OCaml с первоклассными модулями
  12. Aspectual Caml?
  13. Aspect C# ?
  14. C# c Goto и ещё чем-нибудь
  15. Scala где есть и аргументы call-by-value, и аргументы call-by-name. И ещё что-нибудь
  16. Refinement types by Ranjit Jhala
Прочие замечания

В общем и целом вы делаете парсер, интерпретатор + преобразования AST, набираете баллы. Они влияют на максимум оценки за экзамен. Планируется, что те, кто сделают интерпретатор смогут претендовать на оценку C, а также смогут легко добрать баллов до A.

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

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

Если у Вас есть предложения по добавлению других языков -- пишите.

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