Трета задача

Предадени решения

Краен срок:

14.11.2012 17:00

Точки:

6

Срокът за предаване на решения е отминал

Искаме да имплементираме малък интерпретатор на аритметични изрази. Освен да ги интерпретира, той трябва да може да намира и техните производни. Ето как изглежда примерна сесия в интерактивната му конзола:

→ ruby repl.rb
>> x = 10
>> y = 20
>> x + y
-> 30
>> x * y
-> 200
>> derive x: x * sin(x)
-> (sin(x) + (x * cos(x)))

Ние ще напишем парсера и интерактивния шел. От вас се очаква на направите частта, която интерпретира и намира производни на аритметичните изрази. Ще ви подаваме аритметичните изрази като масив от масиви (или s-expression-и).

Видове s-expression-и

[:number, 1]    # Число
[:variable, :x] # Променлива
[:+, a, b]      # Сбор
[:*, a, b]      # Произведение
[:-, a]         # Отрицание
[:sin, a]       # Синус
[:cos, a]       # Косинус

Например, ако имате израза 1 + 2 * x, той ще се представи с дървото [:+, [:number, 1], [:*, [:number, 2], [:variable, :x]]].

Изпълняване на изрази

Отново ще имаме абстракция на интерфейса. Ние ще подаваме дървото на метода Expr.build, а вие трябва да върнете нещо, което представлява този израз. Например:

expr = Expr.build([:+, [:number, 1],
                       [:*, [:number, 2], [:variable, :x]]])

Обектите от върнатия тип трябва да имат определени методи. Те са описани по-долу.

Парсер

Ние сме имплементирали парсер, който превежда текстово представяне като 1 + 2 * x до дърво. С цел да опростим описанието на останалата част на условието, нека си представим, че имаме метод Expr.parse(string), който получава текстов низ, парси го до дърво, подава резултата на Expr.build и го връща.

Ще използваме Expr.parse в това условие с цел четимост. От вас не се иска да имате такъв метод в Expr.

Expr#==

Изразите се сравняват символично. Т.е.:

Expr.parse('x * 2') == Expr.parse('x * 2')
Expr.parse('x * 2') != Expr.parse('2 * x')

Expr#evaluate(environment = {})

Изпълнява израза в дадена област с имена. Например:

Expr.parse('x * 2 + y').evaluate(x: 3, y: 4) # => 10

Ако някоя от променливите в израза не е дефинирана, предизвиквайте каквото и да е изключение.

Expr#simplify

Опростява израза, ако е възможно. Всякакви съчетания, които не включват променливи, се опростяват до стойността им. Отделно, операциите събиране и умножение се опростяват където е възможно. Например:

x + 0 => x
0 + x => x

0 * x => 0
x * 0 => 0
x * 1 => x
1 * x => x

2 * (x * 0) => 0
0 + 1 * (3 * 0) => 0
2 * x + 1 * (3 * 0) => 2 * x

sin(0) => 0

Expr#derive(variable)

Класът за израз трябва да може да намери производна. Ето няколко прости примера:

Expr.parse('x * x').derive(:x)         => Expr.parse('x + x')
Expr.parse('2 * x + 3 * y').derive(:y) => Expr.parse('3')
Expr.parse('sin(x)').derive(:x)        => Expr.parse('cos(x)')

Ще ви припомним правилата за изчисляване на производни, където x е променлива, а a и b са функции:

1'       => 0
x'       => 1 (ако променливата е x)
x'       => 0 (ако променливата е различна от x)
(a + b)' => a' + b'
(a * b)' => a' * b + a * b'
sin(a)'  => a' * cos(a)
cos(a)'  => a' * -sin(a)

Резултатните изрази трябва да са в същия ред като тези по-горе. Резултатът трябва да е опростен със #simplify.

Как ще тестваме

Първо, очакваме да имплементирате Expr#== правилно. Това е относително лесна задача. По-късно тази седмица ще ви дадем тест, с който да проверите дали наистина е така. Ако сравнението ви не работи правилно, не отговаряме за резултите от автоматизираните тестове.

• За #evaluate ще проверяваме конкретната върната стойност.
• За #simplify ще проверяваме какъв израз връщате.
• За #derive ще проверяваме израза, който връщате. Трябва да правите нещата в същия ред, в които сме ги дали по-горе (т.е. (a + b)' да бъде a' * b + a * b', а не a' * b + b' * a или друг еквивалентен израз. Ако върнете по-прост израз от този израз, който ние очакваме, няма да считаме това за грешка.

REPL

В хранилището с примерния тест има и малък read-eval-print loop, с който може да тествате вашия интерпретатор. Уверете се, че сте в същата директория и го пуснете с:

$ ruby repl.rb

За да сработи, има нужда вашето решение да бъде в solution.rb. Уверете се, че в същата директория се намира и файла parser.treetop.

Пускане на тестовете (и конзолата)

За да пуснете всичко, ще имате нужда от treetop, което е малък gem, улесняващ писането на парсери. Инсталирайте го с:

$ gem install treetop

Идеи за имплементация

Класовете, с които ние сме решили задачата, са следните:

class Expr
class Unary < Expr
class Binary < Expr
class Number < Unary
class Addition < Binary
class Multiplication < Binary
class Variable < Unary
class Negation < Unary
class Sine < Unary
class Cosine < Unary

Като подсказка сме ви показали кое от кое наследява. Имайте предвид, че има и по-добър дизайн.

Открихме, че това всички изрази да имат метод #exact? е полезно за реализирането на #simplify. #exact? връща дали израза (не) съдържа променливи.

Също така, открихме, че е много полезно да дефинираме операторите *, + и -@ върху базовия клас.

Може да пробвате да решите задачата с по-малко класове и без тази йерархия, но това може да се окаже предизвикателна задача. Ако не сте уверени, пробвайте нашата йерархия.

Ресурси

Има смисъл да погледнете две различни четива за идеи. Първото е статията за Interpreter Design Pattern в Wikipedia. Второто е кратката глава за symbolic differentiation в Structure and Interpretation of Computer Programs.

Ограничения

Тази задача има следните ограничения:

• Най-много 100 символа на ред
• Най-много 10 реда на метод
• Най-много 2 нива на влагане

Ако искате да проверите дали задачата ви спазва ограниченията, следвайте инструкциите в описанието на хранилището за домашните.

Няма да приемаме решения, които не спазват ограниченията. Изпълнявайте rubocop редовно, докато пишете кода. Ако смятате, че rubocop греши по някакъв начин, пишете ни на fmi@ruby.bg, заедно с прикачен код или линк към такъв като private gist. Ако пуснете кода си публично (например във форумите), ще смятаме това за преписване.