Задачка архитекторная.

[valexey]

Нашел на просторах интернетов. Собственно очень было бы интересно посмотеть как эта задачка решается на:
1) Oberon-07 (можно даже M)
2) Oberon-2
3) КП в динамической среде исполнения (в ББ например).

Маленький Эксель
----------------

Необходимо реализовать простую электронную таблицу в виде программы, выполняющейся
из командной строки. Она должна уметь обрабатывать ячейки таблицы как и более
продвинутые аналоги, только с упрощенным синтаксисом выражений. Каждая ячейка
может содержать:
 - Ничего
 - Неотрицательное целое число
 - Текстовые строки, которые начинаются с символа '
 - Строки-выражения, которые начинаются с символа '=' и могут содержать
   неотрицательные целые числа, ссылки на ячейки и простые арифметические
   выражения. Скобки запрещены, у всех операций одинаковый приоритет.
   Ссылки на ячейки состоят из одной латинской буквы и следующей за ней
   цифры.

   Эти ограничения введены для упрощения разбора выражений, поскольку разбор
   выражений не является основной частью проблемы. Вы можете спокойно
   положиться на эти ограничения. Вот грамматика содержимого ячейки:

Код: [Выделить]

     expression ::= '=' term {operation term}*
      term ::= cell_reference | nonnegative_number
      cell_reference ::= [A-Za-z][0-9] --
      operation ::= '+' | '-' | '*' | '/'
      text ::= '\\'' {printable_character}

Процесс обработки:
 - Все выражения должны быть заменены на вычисленный результат.
 - Все вычисления выполняются с помощью целочисленной арифметики со знаком.
 - Ячейки с текстом должны быть вычислены как соответствующий текст без
   префикса '.
 - Операции над строками текста запрещены.
 - В случае любой ошибки вычисления формулы, вычисляемая ячейка должна содержать
   слово-сообщение об ошибке, начинающееся с символа '#'. Используйте короткие,
   ясные сообщения. Не надо предоставлять подробности об ошибках в выводе.

Программа должна использовать только стандартные библиотеки и классы и не должна
вызывать сторонние программы, библиотеки или системные компоненты.


Ввод и вывод
------------

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


Выход должен содержать только ожидаемую информацию, включая сообщения об
ошибках, и никакой другой информации в выводе не должно быть, включая и
welcome text. Выход должен быть отформатирован в соответствии с приведенным
ниже примером.

Пример данных:

Код: [Выделить]

3            4
12          =C2       3       'Sample
=A1+B1*C1/5 =A2*B1    =B3-C3  'Spread
'Test       =4-3      5       'Sheet

Ожидаемый вывод:

Код: [Выделить]

12      -4      3       Sample
4       -16     -4      Spread
Test    1       5       Sheet


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

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

Вам необходимо будет указать, какие изменения необходимо сделать для
реализации второй фазы проекта.

С этой задачей в одной конторе не справился ни один из тех, кому ее давали. Точнее, не справился в полном объеме. После более или менее успешного ее решения проводилось интервью. Задача использовалась для выявления потенциальных архитекторов.

[valexey]

Да, ТЗ задачки такой какой он есть. Уточняющие вопросы задавать не разрешается. Разрешается только сразу выдать ответ.

[valexey]

Да, времени на задачку давалось 2-3 дня (это давалось на дом, до собеседования). Впереди как раз выходные, условия у всех участников сего форума в точности те же (или лучше) нежели у тех кто был пред собеседованием.

[valexey]

кстати, вот этот пункт:

Программа должна использовать только стандартные библиотеки и классы и не должна
вызывать сторонние программы, библиотеки или системные компоненты.

Применительно к оберонам можно и обсудить. Потому как если руководствоваться только language report'ами, то там и Hello World не написать.

[Geniepro]

Ну вот моё решение: [тут покопался злобный валексей и скрыл ссылку до понедельника, жалобы принимаются]
Я справился с задачей со сверхсветовой скоростью, за -3.5 года )))

[valexey]

Ссылку скрыл, дабы народ не отвлекался на изучение чужих решений (ибо это больно уж затягивающее занятие) а написал что-нибудь своё. Хочется таки хоть одно решение на каком-нибудь Обероне.

Если geniepro возразит супротив такой меры, то моментально все верну взад. Ну, или если народ массово против вдруг будет.

[valexey]

В общем, относительно стандартных либ, я считаю так: стандартное все, что идет искаробки с выбранным компиятором/средой. Нестандартные сборки в рассчет не берутся.

То есть, если это BB, то пользоваться можно всем тем, что идет в наборе от Оминков.
Если это XDS, то пользоваться тем, что идет с ним искаропки.
Если это Oberon-07M.. Ну, похоже тут и выбора то не остается :-) Единственное но -- желательно таки в логике программы не использовать что-то WinAPI'шно-привязанное. (кроме всего прочего, решение данной задачки может и должно послужить толчком к созданию на Оберон-07М стандартной библиотеки).

[valexey]

Хотя, конечно, Оберон-2 можно было бы ограничить библиотекой из Дубовых Требований.

[Geniepro]

Если geniepro возразит супротив такой меры, то моментально все верну взад. Ну, или если народ массово против вдруг будет.

Да я-то до понедельника потерплю, чо уж там ))

В общем, относительно стандартных либ, я считаю так: стандартное все, что идет искаробки с выбранным компиятором/средой. Нестандартные сборки в рассчет не берутся.

То есть, если это BB, то пользоваться можно всем тем, что идет в наборе от Оминков.
Если это XDS, то пользоваться тем, что идет с ним искаропки.

То есть учебную сборку от инфо21 юзать низзя? ))
А Haskell Platform годится? Ибо он рекомендуемой производителем сборкой является и стандарт де-факто...

[valexey]

То есть учебную сборку от инфо21 юзать низзя? ))

Ни в коем ни в случае! :-)

А Haskell Platform годится? Ибо он рекомендуемой производителем сборкой является и стандарт де-факто...

А это надо подумать. Потому как, в отличае от Оберонов, у хаскеля таки есть стандартная библиотека вполне достаточная для данной задачи. Наверно так -- если получилось обойтись тем и только тем, что есть в описании стандарта (haskell 2010, кстати), то отлично. если вылезли во вне и заюзали что-то нестандартное (в плане библиотек) из Haskell Platform, то это не серьезная ошибка дизайна, при условии, что оно реализовано не только в ghc, и серьезная (но не фатальная), если есть только в ghc.

[Geniepro]

А это надо подумать. Потому как, в отличае от Оберонов, у хаскеля таки есть стандартная библиотека вполне достаточная для данной задачи. Наверно так -- если получилось обойтись тем и только тем, что есть в описании стандарта (haskell 2010, кстати), то отлично. если вылезли во вне и заюзали что-то нестандартное (в плане библиотек) из Haskell Platform, то это не серьезная ошибка дизайна, при условии, что оно реализовано не только в ghc, и серьезная (но не фатальная), если есть только в ghc.

Так кроме GHC других промышленных трансляторов у Хаскелла нет, а Haskell Platform -- его рекомендуемая сборка.

[valexey]

А это надо подумать. Потому как, в отличае от Оберонов, у хаскеля таки есть стандартная библиотека вполне достаточная для данной задачи. Наверно так -- если получилось обойтись тем и только тем, что есть в описании стандарта (haskell 2010, кстати), то отлично. если вылезли во вне и заюзали что-то нестандартное (в плане библиотек) из Haskell Platform, то это не серьезная ошибка дизайна, при условии, что оно реализовано не только в ghc, и серьезная (но не фатальная), если есть только в ghc.

Так кроме GHC других промышленных трансляторов у Хаскелла нет, а Haskell Platform -- его рекомендуемая сборка.

Ну, про промышленность ghc я бы таки промолчал (ну недотягивает оно до промышенных стандартов в плане стабильности и обратной совместимости, чуточку, но не дотягивает пока). Но вот ведь есть же еще и (Win)Hugs! Вполне популярная реализация haskell'я. Да, в ынтырпрайз оно возможно не пойдет как база, но вот для экспериментов, для разработки, проверки и так далее -- вполне. Оно простое и там цикл разработки быстрее чем на ghci. Оно много более легковесное. Оно дружелюбное. И да, оно умеет часть из того, что умеет и ghc, например монаду ST.

[Geniepro]

Ну, про промышленность ghc я бы таки промолчал (ну недотягивает оно до промышенных стандартов в плане стабильности и обратной совместимости, чуточку, но не дотягивает пока).

Однако GHC используется во вполне серьёзных промышленных проектах. Альтернативы в общме-то ему нет.

Но вот ведь есть же еще и (Win)Hugs! Вполне популярная реализация haskell'я. Да, в ынтырпрайз оно возможно не пойдет как база, но вот для экспериментов, для разработки, проверки и так далее -- вполне. Оно простое и там цикл разработки быстрее чем на ghci. Оно много более легковесное. Оно дружелюбное. И да, оно умеет часть из того, что умеет и ghc, например монаду ST.

Ага, вот только этот самый ST реализован в HUGS по другому, чем в GHC, поэтому библиотека работы с графами не компилируется в HUGS...
Да и как Вы организуете ввод/вывод из консоли в WinHUGS, скажите на милость...  
Из нескольких моих решений этой задачи лишь одно запустилось в хугсе, но оно не может правильно обработать циклы в формулах -- выпадает в осадок с переполнением стека...

[valexey]

Ну, это я с удовольствием разберу все позжее. Возможно твое решение будет наилучшим просто вследствие отсутствия конкурентов :-)

[Geniepro]

Но вот ведь есть же еще и (Win)Hugs! Вполне популярная реализация haskell'я. Да, в ынтырпрайз оно возможно не пойдет как база, но вот для экспериментов, для разработки, проверки и так далее -- вполне. Оно простое и там цикл разработки быстрее чем на ghci.

Кстати, вот я так до сих пор и не осилил разработку в стиле REPL. С редактором текста и компилятором мне как-то проще. В Хугсе если и запускаю программу, то чисто что бы проверить, есть ли ошибки, и если нет, и алгоритм достаточно быстрый, то что бы тут же протестировать. Но это мало отличается от цикла разработки с компилятором, потому что REPL хугса я очень редко использую.
Да и в GHC есть репл -- GHСi...