tasks.md

Заняты "академиками"

1. C++ и наследование (Шишкин)
   Подробнее

   • Объявления функций, приваивание, рекурсия, стандартные типы, что-то для печати на консоль.
   • Объекты, поля, методы
   • Анонимные функции можно не делать
   • Наследование: public, private, protected, virtual
     • diamond problem1.
2. F# (Быков на F#)
   Подробнее
3. Python (Бакаев)
   Подробнее

   this one starts expanded because of the "open"
4. Стрёмное подмножество c#
   Дмитрий Кузнецов

   • Async/await
   • Стрёмный LINQ синтаксис: select ... from ... where ...
   • лямбды с присваиваниями и замыканиями
   • Пользовательские классы можно не делать, один класс Program c кучей статических методов пойдет.
   • Стандартные типы данных, массивы
     • продемонстрировать на массивах ArrayTypeMismatchException
5. Pascal (Казанцев Антон)
   • функции/процедуры, присваивание, стандартные типы и типы-записи
   • динамическое выделение памяти не надо
6. Объектно-ориентированый C# c классами, интерфейсами
   Алимов

   • Наследование классов и интерфейсов, без generics.
   • public/private/protected и override.
   • Стандартные конструкции языка + приведение типов объектов.
   • Целые числа, строки, стандартные функции работы с ними; массивы и лямбды не надо.
   • Что-нибудь для печатанья значений переменных в языке.
   • Какой-нибудь тайпчекер на случай, чтобы отфильтровывать бредовые программы.
   • new методы
     • Я слышал, что при их использовании вместе с интерфейсами, там возникает какая-то нетривиальная семантика. Надо будет разобраться. Вот пример.
7. OCaml + ООП
   Матвей

   • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
   • в OCaml есть интерсные объекты и их типизация, нужно поддержать объекты+методы+поля
   • (может быть классы и наследование тоже надо будет, но пока не уверен)
   • как тесты предлагаю реализовать некоторые структуры данных как камлёвые объекты и посмотреть, что будет

Основные домашки (надо примерно 40)

1. OCaml + ADT

   Подробнее

   • стандартный мини-язык, базовые типы
   • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
   • алгебраические типы как основной способ проектирования типов; учтите, что
     • в OCaml и Haskell типы int и float -- примитивные (встроенные)
     • тип списков алгебраический и там, и там; в AST не должно быть, что списки отдельно, а алгебраических значения отдельно
     • в OCaml тип bool примитивный, а в Haskell -- алгебраический
   • можно поддержать пары, но можно и обойтись алгебраическим типом с одним конструктором
   • разумеется, объявления типов, паттерн-мэтчинг и типизация
   • присваивание не надо
   • исключения не надо

2. OCaml + скомпилированные алгебраические типы (задача может показать объёмной, поэтому разрешаю сдавать в одной кодовой базе в месте с задаче про OCaml + алгебраические типы)

   Подробнее

   • Прочитать как окамлёвые алгебаические типы представляются в памяти, разобраться как устроены "блоки" и unboxed immediate values
   • Написать парсер (параметризовать уже существующий из другой задачи) который понимает функции для конструирования/заглядывания в блоки
   • Интерпретатор этого дела.
   • Алгоритм преобразования программ с алгебраиками и сопоставлением с образцом в низкоуровневое представление.
   • Преобразования программ из задачи про ADT, в низкоуровневое представление этой задачи. (По сути надо избавляться от алгебраических значений и сопоставления с образцом. Можно посмотреть алгоритм с матрицами отсюда )

3. Haskell + стандартные типы данных + ленивость

   Бучин

   • Из стандартных типов: полиморфные списки и бинарные деревья, туплы, Maybe (который option)
   • С ленивостью надо будет продемонстрировать работоспособность
     • Лямбда-исчисление с call-by-name
     • ленивых списков и операция над ними (например, фибоначчи, решето Эратосфена и т.п.)
     • прочие ленивые задачи (например, за один проход заменить все числа в дереве на их минимум и вернуть новое дерево)

4. OCaml + полиморфные вариантые типы

   • Как первая домашка "OCaml + ADT", только вместо алгебраических типов полиморфные варианты как они есть в OCaml
   • Объявления типов можно не делать
   • Стандартные типы (пары, списки, option) можно делать, а можно не делать, выразив через полиморфные варианты
   • Глава в мануале OCaml

5. F# + active patterns

   Подробнее

   • miniML + стандартные типы данных: пары, полиморфные списки, option; сопоставление с образцом
   • возможность описывать активные паттерны, которые выглядят как алгебраические конструкторы

      let (|Even|Odd|) input = if input % 2 = 0 then Even else Odd
     

   • Возможность использования активных паттернов в сопоставлении с образцом

      let TestNumber = function
      | Even -> printf "%d is even\n" input 
      | Odd -> printf "%d is odd\n" input
     

6. OCaml + effects (2 человека)

   • супер-модное в наши дни движение в мире ФП
   • По сути, это исключения, но в момент обработки которых у нас есть функция, которой можно был передать значение, которое должно было бы быть вместо бросания исключение, и продолжить исполнение с места бросания исключения.
   • Туториал в контексте OCaml https://github.com/ocamllabs/ocaml-effects-tutorial
   • два человека только потому, что хочу чтобы задачу кто-то взял. А так это очень сильно напоминает задачи про delim/cc

8. OCaml + GADT (2 человека)

   • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
   • OCaml где алгебраические типы заменены на обобщенные (generalized) алгебраические типы
   • Интерпретатор будет такой же, как в задаче про обычные алгебраические типы (можно делать вместе)
   • Вывод/проверка типов там сложнее, чем для обычных алгебраических, поэтому два человека
     • Нужно поддержать явные аннотации типов, потому что автоматический вывод типов всё
     • Типовые переменные могут убегать из области видимости и т.д.
   • Умная сслыка, описывающая что примерно вас ждет

10. OCaml + модули (2 человека)

    Подробнее

    • MiniML c базовыми типами, (целые числа, строки) и стандартными алгебраическими (option, list)
    • Объявления типов-синонимов (type abbreviations, typedef) type ('a, 'b) my_typ = 'a * ('b, 'b) list * пользовательские алгебраические типы не надо
    • Объявления модулей и типов модулей
      • Многофайловость не надо
      • let module X = ... in не надо
      • Функторы не надо (может потом про них отдельную задаче сделаю)
    • Передача модулей как first-class values в функции Пример:

    # module type SHOW = sig type t  val show : t -> string end;;  
    module type SHOW = sig type t val show : t -> string end  
    # module ShowInt: SHOW with type t = int  = struct type t = int let show = string_of_int end;;  
    module ShowInt : sig type t = int val show : t -> string end 
    # let show (type a) x (module S: SHOW with type t = a) = S.show x;;  
    val show : 'a -> (module SHOW with type t = 'a) -> string = <fun>   
    # show 42 (module ShowInt);;  
    - : string = "42"

12. OCaml, именованые и опциональные аргументы

    • mini-ML с функциями обычными и анонимными, замыканиями и рекурсией
    • Тайпчекер с полиморфизмом обязательно
    • Стандартные типы (числа, списки, option)

13. SML + equality types + value restriction

    Подробнее

    • Почти предыдущая задача, но проще
    • Немножко другой парсер, потому что SML немножко отличается
    • Еquality types:
      • в типах функций появляются типовые переменные с двумя апострофами, что означает, что туда можно подставлять только типы, на которых работает функция проверки на равенство (функции и вещественные числа нельзя сравнивать)
    • Value restiction
      • Заставляет выводить менее полиморфные типы, потому что присваивание может нарушать типовую безопасность
      • https://users.cs.fiu.edu/~smithg/cop4555/valrestr.html

14. SML + Value polymorphism restriction + rank 1 typing

    Подробнее

    • https://smlsharp.github.io/en/documents/4.0.0/Ch9.S2.html

15. 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 для пары захардкоженных в язык исключений
      • С системой типов в описанном выше смысле.

16. miniML с компиляцией в .NET (2 человека, только потому что выглядит страшно)

    Подробнее

    • Взять miniML, по нему сделать MSIL, натравить компилятор из MSIL в .NET, и оно запускается!
    • Интерпретатор писать не надо, у нас .NET вместо интерпретатора будет.
    • Страшно может быть только потому, что внутреннее представлением программ на .NET пугливому студенту покажется страшным
    • По факту, надо взять miniML; сделать lambda-lifting, чтобы внутри функций не создавались замыкания; вытащить внутри объявленные функции вверх; отобразить полученные фукнции в статические методы один к одному
    • Другой независимой задачей будет поддержка арифметических выражений, путём отображения в стековые команды .NET
    • Ну, а когда это уже будет готово, надо будет поддержать пары, тип option, и остальное по мелочи.

18. F# + Units of Measure

    • miniML: функции, полиморфизм, рекурсия
    • Числа (обосновано следующим пунктом)
    • Возможность объявлять и использовать Units of Measure

19. Scheme + call/cc

    Подробнее

    • относительно легко гуглящаяся особенность Scheme, человеку в том году удалось такую домашку сдать
    • call/cc
    • целые числа, рекурсия, списки, печать на консоль
    • функции обычные и анонимные, замыкания и рекурсия
    • присваивание не надо
    • quote/unquote
    • парсер очень простой
    • никаких статических типов, разумеется, нет
    • учитывая следующую задачу, получается в некотором смысле на двоих

20. 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

21. Котлин, ООП и flow-sensitive typing

    • Стандартные типы данных, функции/методы, присваивание
    • функции/методы обычные и анонимные, замыкания и рекурсия
    • ООП, наследование, вызов методов, изменение полей
    • Flow-sensitive typing: вывод того, может ли значение быть null или нет
      • Важный пример отсюда должен работать
    • Давать на двоих не хочу, так как про всё это вам должны были рассказывать.

22. Refal 5

    • одскульный отечественный язык программирования, где последовательности можно мэтчить не только с начала, но и с конца

23. Ruby

    • Известный язык программирования, по типу Питона
    • Стандартные конструкции, присваивание,
    • Рекурсивные и анонимные функции, замыкания
    • Объекты
    • Статической типизации там нет, потому и не надо
    • method_missing -- отличительная штука Ruby, где можно сказать, что делать, если метода нет
      • с помощью обработки отсутсвующего метода предлагаю сделать примеры про реализацию тестирования кода в стиле rspec
    • Прикольные штуки из WAT talk

24. 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 ...)

25. Cypher

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

26. BQN -- упоротый язык с парадигмой array programming (скорее всего на двоих)

    Подробнее

    * [https://github.com/mlochbaum/BQN/tree/master/tutorial](tutorial) * Отличный вариант, чтобы закрепить знания Юникода

28. 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.

29. Ассемблер x86_64 --- очень простой язык и для парсинга, и для реализации интерпретатора. Халява.

    Подробнее

    • Язык должен быть настоящим ассемблером, т. е. входные программы должны компилироваться соответствующим компилятором и выдавать ответ как в интерпретаторе
    • Примеры стоит взять из первой части книжки И. Жиркова "Low-level programming".
    • Чтобы задача не была чересчур простой, хочу также в ассемблере SIMD операции и тесты к ним (перемножение вектора/матрицы на вектор/матрицу)
    • Опыты прошлых лет показывает, что написание AST в лоб оставляет большое пространство для плохих программ, представимых в AST. Например, 64битные команды никак не должны принимать 32битные операнды-регистры как аргументы. Потребуется обмазаться фантомными-типами и/или GADT, чтобы не нужно было писать гавнокод. Буду следить!

30. 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

31. Go с горутинами

    • Стандартные типы данных(int, bool, string)
    • Циклы
    • Условный оператор(if)
    • Массивы
    • Функции (обычные, анонимные и рекурсивные)
    • Каналы (достать, положить, закрыть)
    • Горутины (переключение по ожиданию данных из канала)

32. Производительный SQL

    • Минимальный язык запросов к базам данных: SELECT, JOIN WHERE и может что-то ещё
    • Интерпретатор запросок на этом языке
    • Эти запросы должны исполняться на больших данных, автогенеренных с помощью https://github.com/NetApp/SQL_Storage_Benchmark
    • Большие входы должны заставить интерпретатор исполняться запросы эффективно, а не как попало.

33. Cи

    • Целые числа разного размера (например, int32_t и int8_t)
    • char
    • Указатели и арифметика указателей, malloc
    • Продемонстрировать стандартные примеры программ на указатели
      • Короткий memcpy и что с ним может пойти не так
      • Реинтерпретировать кусок памяти с массивом int32_t как в 4 раза большее количество чисел int8_t
    • Функции и рекурсия: факториал, фибоначчи, и т.п.
    • Объявления пользовательских структур не надо.

34. Моделирование параллельного исполнения

    Подробнее

    За описание благодарите старшего студента.

    • Ast Программа состоит из N параллельных участков. В них бывает арифметика, присваивание, thread-local registers (отдельный для каждого потока набор регистров, например EAX, EBX или r1, r2), shared variables (переменные в которые могут писать и из которых могут читать сразу несколько потоков), ветвления и барьеры чтения/записи.

    • Parser Код потока записывается в столбик, код разных потоков разделен с помощью значка |||. Потоки исполняются параллельно. Если нет идей как такое парсить, то попробуйте следующий способ. Научитесь парсить один конкретный поток по его индексу (нулевой, первый, …, N-1й), потом используя эту функцию распарсите все потоки по очереди и получите список распаршеных потоков. Пример кода на этом языке:

      x <-1   ||| y<-1
      smp_mb  ||| smp_mb
      r1 <-y  ||| r2<-x		
      

      x,y это shared переменные. r1,r2 – локальные для потока регистры. smp_mb – барьер памяти. В этом примере 2 параллельных потока, в каждом потоке 3 инструкции.

    • Интерпретатор Не стоит пугаться, на самом деле вы будете исполнять по одной инструкции за раз чередуя потоки из которых эта инструкция берётся. Модель же памяти будет влиять на операции чтения и записи: эффекты этих операций могут проявляться не в те моменты времени, как вам подсказывает интуиция, из-за этого возникают интересные поведения. Отмечу, что интерпретатор должен осуществить всевозможные исполнения переданной ему на вход программы, с этим поможет монада List

    • Описание моделей памяти:

      • Sequential Consistency – простейшая модель, выбираете произвольный поток и исполняете в нем одну инструкцию. Повторяете пока есть неисполненные инструкции. Барьеры памяти в этой модели не оказывают эффекта на исполнение программы.
      • TSO – модель памяти процессоров x86. Здесь возможны интересные поведения. Если в примере выше изначально в переменных x и y хранятся значения ноль, а также из кода будут удалены инструкции барьеров памяти (smp_mb), то возможны поведения, в которых после исполнения будет x == 0 и y == 0. При наличии барьеров памяти после исполнения хотя бы одна переменная всегда будет иметь значение один. Вообще этот код называется store buffering test о нём и не только о нём можно прочесть в статье a better x86 memory model.

    • Полезные материалы:

      • Открытая лекция «weak memory models» от Антона Подкопаева. В CSC тоже были лекции на эту тему: раз и два.
      • К двум лекциям от CSC необходимо добавить статью Memory Barriers: a Hardware View for Software Hackers (http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)
      • Статья расскажет о том, что такое store buffer(write buffer) и как работают барьеры памяти. A better x86 memory model: x86-TSO (extended version). В ней можно найти тесты (litmus tests) для модели x86 и проверить свой интерпретатор
      • СТАТЬЯ, КОТОРАЯ МЕНЯЕТ ВСЁ! После прочтения этой статьи в конце 3й недели работы над домашкой. Я за 2 часа удалил 2/3 своего кода и получил работающие модели. Поэтому я уверен, что она может сильно помочь, после того, как всё предыдущее будет изучено и что-то будет написано.

35. Promela

36. Lua -- примитивный язык без типов

    • Вещественные числа, строки
    • Функции и функции высшего порядка
    • Стандартные конструкции: ветвления, цикл и т.п.
    • Присваивание и хитрые ассоциативные массивы с двойной индексацией, специфичные для Lua

37. Menhir + рекурсивный спуск

    Подробнее

    • Такой своеобразный DSL для написания парсеров. По умолчанию он парсит LR-способом (вам не обязательно знать, что это такое)
    • без action кода, ассоциативности, приоритетов
    • трансляция в парсер-комбинаторы
    • устранение левой рекурсии

38. Menhir как LALR интерпретатор

    Подробнее

    • Menhir как LALR интерпретатор принимает последовательность лексем, и грамматикой разбирает их успешно или нет.
    • Надо сделать интерпретатор LALR-парсера по аналогии с менхировским (глава 8 в мануале)
    • TODO спросить у Семёна сгодится ли тут простой табличный анализатор

39. Make

    Подробнее

    • Поддержать объявление и вызов функций make (скорее всего вот этот пример достаточно полный)
    • Так как язык Makefileов выглядит достаточно просто, то надо еще реализовать клон make, который можно использовать как билд-систему. Протестировать сборку C и OCaml проектов клоном make

Гробы, которые никто не возьмет

1. Javascript
   • Объекты, числа, строки, массивы
   • Функции обычные и анонимные, замыкания, рекурсия
   • Типичное для Javascript прототипное наследование
   • Прикольные штуки из WAT talk
2. 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;
        }
     }	

4. OCaml + implicits
   • В OCaml нет ad hoc полиморфизма (то, что вы знаете под термином overloading), поэтому многим хочется иметь в грядущей версии OCaml следующую штуку
     • в области видимости объявляется некоторое количество OCamlовских модулей
     • у функций могут появляться неявные аргументы (implicit), которые программист не передает явно руками
     • момент вызова функции компилятор ищет в области видимости подходящие по типу модули и подставляет и вместо неявных аргументов, если не найти -- ошибка, если больше 1го подходящего варианта -- тоже
5. Scala 3 + givens
   • как предыдущее, только вместо OCaml -- синтаксис Scala 3, вместо камлёвых модулей -- скальные объекты
6. мини-Coq с индуктивными типами (2 человека)
   • похож на OCaml + ADT, но с некоторыми ограничениями
   • вводятся ограничения на объявления алгебраических типов
     • чтобы избегать парадокса Карри
     • иметь индуктивные типы, размер которых очевиден
   • объявляемые функции принимаются только если они завершаются
     • проверка делается на основе рассуждения "убывает по такому-то аргументу"
8. OchaCaml (Caml Light + delim/cc) (2 человека)
   • стандартные типы (числа, списки),
   • функции обычные и анонимные, замыкания и рекурсия
   • конструкции для отладочной печати
   • delim/сс
   • полиморфные типы для всего этого
     • типизация там необычная, надо по одной ссылке долистать до описания того, как это типизировать; по другой ссылке долистать до способов написания интерпретатора/компиляции
   • По сути эта задача и две предыдущие про */сс -- суть одно и то же

Определюсь/допишу потом если тем будет не хватать/или кому-то очень захочется/и не будет лениво их доформулировать, а может на 2023 год оставлю

1. Pascal (записан за Казанцевым)
   • алгебраические типы данных variant records (пункт 12).
2. Fortran?
3. Visual Basic.NET (клон C# с другим синтаксисом)
   • На вики есть список отличий. Если сесть и посмотреть, то наверняка можно придумать задачу.
4. C# c паттерн-мэтчингом
5. Какие-нибудь смарт-контракты
6. MSIL
7. С# с многофайловостью, мультиметодами и экстеншинами
8. OCaml с первоклассными модулями
10. Aspectual Caml?
11. Aspect C# ?
12. C# c Goto и ещё чем-нибудь
13. Scala где есть и аргументы call-by-value, и аргументы call-by-name. И ещё что-нибудь
14. Refinement types by Ranjit Jhala
15. Sed (а тестировать будем примером реализации brainfuck на sed)
16. Smalltalk
17. Ideal Parallel Algol
18. AWK
19. J
20. TSQL
21. Forth (может оказаться слишком простым)
22. Amulet? https://github.com/amuletml/amulet
23. Prolog/Datalog Solving murder with prolog
24. TCL
25. Полиморфные варианты set-theoretic (с общим парсером и интерпретатором)
26. Язык с присваиванием через монаду IO
27. ML + subtyping по Долану
28. GADT одним способом типизации
29. И другим способом типизации
30. Функции с исключениями + yeild
31. Scheme + typed racket
32. ФП c letbox от Трунова https://github.com/mtt-lang/mtt-lang/tree/master/examples
33. Новый Smalltalk с идеей сделать там resumable exceptions, которые как эффекты (ГРОБ)
34. Wolfram Mathematica (там синтаксис очень стрёмный)
35. Erlang на основе карамели
36. Curry/Mercury?

Прочие замечания

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

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

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

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