README.md

# Пример реализации DSL

## Что делаем

Создаем свой "малый" язык программирования для решения определенного круга задач. Такие языки называют еще Domain Specific Language (DSL). Есть более строгое определение, см. лекции.

## Подготовка

Нам потребуется
  - python3
  - textX (``pip install textX``)
  - graphviz (проверить наличие, желательно)

## Задача 1 (1 балл)

Сделаем Hello world! Из документации к [``textX``](http://textx.github.io/textX/stable/tutorials/hello_world/).
Хотим получить приветствия на выходе для каждого участника. Примерно так:

```
Hello World!
Hello Universe!
```

1. Изучаем, как создавать [грамматику](http://textx.github.io/textX/stable/grammar/). 
2. Смотрим [пример грамматики](./hello.tx)
3. Построим диаграмму метамодели (модели созданного языка) из грамматики:

```
$ textx generate hello.tx --target dot
$ dot -Tpng hello.dot -o hello.png
```

4. Теперь пишем пример "программы" на нашем DSL. [Текст здесь](./example.hello)
5. И нам нужен интерпретатор модели, который сможет ее выполнить. Он простой, делаем на python, код есть [здесь](./hello.py). Обратите внимание на импорты из ``textx`` и как загружать модель.
6. Далее запускаем интерпетатор

```
$ python hello.py
```

## Задача 2 (5 баллов)

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

Мы будем использовать реализацию самого робота на python, найденную [здесь](https://github.com/xsebek/karel) и исправленную уже в [проекте](./karel_robot)

Создадим что-то похожее на вот это [описание](http://mormegil.wz.cz/prog/karel/prog_doc.htm):

### Задание 1 (1 балл)

Начнем с последовательного исполнения команд ``move``, ``turn``, ``exit``, ``beeper``. Пример грамматики [здесь](./karel-plain.tx). 
   
 - Какие команды определены, есть ли у них параметры? 
 - Какие ключевые слова есть в языке?
 - Напишите программу, которая передвигает робота на 2 клетки вперед и на 2 направо
 - Какие соглашения используются для токенизации?

### Задание 2 (1 балл)

Сделаем интерпретатор. Проще всего сделать отдельный класс для него, экземпляры которого будут хранить состояние исполнения программы. В нашем случае ``karel_robot`` хранит состояние глобально, поэтому это не существенно.

Реализуйте методы выполнения программы на DSL ``interpret(self, model)`` и j,обработки отдельной команды ``process_command(self, c)`` в классе интерпретатора.

Для использования визуализации и уже готовых команд импортируйте все из ``karel_robot.run``. [Пример реализации.](./karel_plain.py)

 - Какой способ реализации мы здесь применяем?
 - Подойдут ли здесь какие-либо паттерны проектирования?
 - Как вы проверяете, что обрабатываемый узел модели имеет определенный тип из метамодели языка?

Проверьте, что все работает как надо, запустив интерпретатор. Должна появится текстовая картинка, по которой ходит робот.

```
$ python karel_plain.py
```

### Задание 3 (3 балла)

Добавим в наш язык логические выражения для проверки положения и направления робота: ``north``, ``south``, ``east``, ``west``; определения есть ли стена, маяк или сокровище напротив ``front_is_blocked``, ``is_beeper``, ``front_is_treasure``; а также логические операции ``not``, ``or``, ``and``.

 - Как указать приоритет ``and`` над ``or``? И ``not`` над ними обоими?

Теперь добавим условные конструкции ``if-then-else`` и ``while``. Можно еще добавить повторение ``n`` раз. Пример реализации [здесь](./karel-control.tx)

 - Выясните, в чем состоит проблема dangling-else, как она решается в нашем случае в textx?
 - Обратите внимание, что кроме команд теперь есть и выражения, которые возвращают логическое значение и не являются командами. Как они добавлены в грамматику языка?
 - Добавьте цикл из ``n`` повторений самостоятельно

Аналогично, нужно добавить реализацию в интерпретатор. Добавим метод ``process_expression(self, e)`` и расширим обработку команд. Один из вариантов [доработки](./karel_control.py).

 - Программа теперь состоит из команды и выражений. Как бы вы реализовали их обработку?

Если все сделано верно, теперь уже можем написать программу обхода лабиринта в поиска сокровищ для произвольного ограниченного стенами лабиринта. Пример программы [здесь](./maze.karel). Не забудьте остановить программу по нахождении сокровища.

## Задача 3 (4 балла)

Теперь посложнее. Нужно добавить подрограммы и пользовательские функции. Сигнатура должна описывать передаваемые параметры - логические выражения. Еще будет полезна отдельная команда на вызов.

 - Есть синтаксис pascal-like, c-like и python-like. Какой вам ближе?
 - Продумайте, как обозначить возвращаемое значение из функции. 

Реализуем в интерпертаторе. Сохранять место текущего исполнения можно вызывая подпрограмму в текущем месте в самом язке программирования интерпертатора. Вот как [здесь](./karel_structured.py)

 - Как лучше передавать параметры - по значению или по ссылке? 
 - Нужен ли стек для реализации подпрограмм? Узнайте, что такое stack frames.Сравните с тем, что уже знаете про область видимости переменных

Еще стоит добавить команду прерывания цикла ``break``. Она должна приводить к выходу из текущего цикла внутри одной подпрограммы, если такой цикл есть. Приммер реализации без нарушения структуры кода см. [там же](./karel_structured.py).
 
  - Как бы вы реализовали ``goto``? В ранних вариантах Бейсика можно было выходить как за пределы структурного блока, так и за пределы подпрограмм, чем это грозит?
  - Обратите внимание, что мы пока не определяли никакие хранимые данные. ТО есть все данные хранятся на поле в клетку. Если нужно, можно ставить маяки. Как считаете, нужны ли переменные в программе и зачем?

Реализуйте программу поиска сокровищ в лабиринте с применением добавленных конструкций языка. Примера в этот раз нет.