r6 - 14 Sep 2006 - 22:03:40 - Sergej ZnamenskijYou are here: TWiki >  Refaldevel Web > ForJavaProgrammer

Рефал для программиста на Java

Пока пример.

На странице http://nuclight.livejournal.com/111696.html на примере некоторой небольшой задачи (проверка соответствия строки шаблону) сравнивается производительность труда программиста на Pascal и на Java.

Итоги таковы:

  • решение задачи на Pascal потребовало у автора 1.5 часа и занимает 116 строк;
  • решение задачи на Java потребовало 3 часа и занимает 270 строк.

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

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

Приведём формулировку задачи:

Во входном файле две ASCII-строки, одна состоит только из больших латинских букв, в другой могут встречаться большие латинские буквы и еще два спецсимвола - * (звездочка) и ? (знак вопроса). Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Строку только с буквами назовем словом. Строка со спецсимволами - шаблон, в котором "?" и "*" играют роль символов подстановки по правилам, идентичным wildcards в именах файлов в DOS или Unix-shell, т.е. "?" заменяет собой ровно один произвольный символ, а "*" заменяет собой любое количество произвольных символов - 0 или более (т.е. может заменять и пустую строку). Программа должна выдать ответ YES, если слово подпадает под шаблон (match'ит его), либо NO в противном случае.

У меня решение задачи на Рефале Плюс отняло 20 минут (полностью от начала чтения условия до окончательной версии кода). Занимает 25 строк (см. match.rf).

Вот как выглядит основная функция программы, занимающаяся сопоставлением строки с шаблоном:

Листинг 1. Определение функции Match.
 1  $func? Match e.word (e.pattern) = ;
 2
 3  Match \{
 4      t1 e2     (t1 e3)  = <Match e2 (e3)>;
 5      t1 e2     ('?' e3) = <Match e2 (e3)>;
 6      e1        ('*' e3) = { e1 : e11 e12, <Match e12 (e3)>; };
 7      /*empty*/ ()       = /*yes*/;
 8  };

Функция Match принимает в качестве первого аргумента слово, и в качестве второго — шаблон. Расшифруем её определение:

  • строка 4: если первый символ строки совпадает с первым символом шаблона, то сопоставлять остаток строки с остатком шаблона;
  • строка 5: если следующий символ шаблона — '?', то первый символ строки нас не интересует; сопоставлять дальше;
  • строка 6: если следующий символ шаблона — '*', то попробовать разбить строку на две части таким образом, чтобы вторая часть сопоставилась с остатком шаблона;
  • если разбить строку таким образом не удалось, то аварийно завершить работу функции (это обеспечивают фигурные скобки в строке 6); никакие другие варианты сопоставления рассматриваться не будут;
  • строка 7: если всё, что осталось — пустая строка и пустой шаблон, то сопоставление прошло успешно; завершить работу;
  • если осталось что-то другое (никакое из предложений не сработало), то завершить работу неуспехом; если в шаблоне встречались '*', то перебор вариантов сопоставления будет продолжен.

Как видно, Рефал позволяет записать данный алгоритм коротко и ясно. Мало того, при попытке подумать, как подойти к решению данной задачи на Рефале, этот алгоритм выписывается совершенно естественным образом.

Единственным тонким местом являются фигурные скобки в строке 6. По сути они означают следующее: если строку не удаётся сопоставить с шаблоном, какую бы её часть мы ни отводили на '*', то работа заканчивается (даже если до этого в шаблоне были ещё '*'). Действительно, если хвост строки не сопоставляется с шаблоном, то какое бы мы ни отнимали у него начало (с помощью предыдущих '*'), сопоставление не сможет завершиться успешно.

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

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

Заметим, что для того чтобы функция Match была доступна из других модулей рефал-программы (и из других классов Java-программы), она должна быть объявлена внешней: её формат вынесен в интерфейс модуля — match.rfi.

После компиляции модуля match.rf, мы получим Java-class match (файл match.java), содержащий, в частности, статический метод match.Match.

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

Листинг 2. RunMatch.java
 1  import java.io.*;
 2  import org.refal.plus.*;
 3
 4  public class RunMatch
 5  {
 6      public static void main (String[] args) throws Exception
 7      {
 8          BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
 9          String line1 = r.readLine();
10          String line2 = r.readLine();
11          boolean res;
12          try {
13              if (line1.indexOf('?') < 0 && line1.indexOf('*') < 0) {
14                  res =
15                      match.Match(Expr.fromSequence(line1), Expr.fromSequence(line2));
16              } else {
17                  res =
18                      match.Match(Expr.fromSequence(line2), Expr.fromSequence(line1));
19              }
20              if (res)
21                  System.out.println("YES");
22              else
23                  System.out.println("NO");
24          } catch (RefalException _) {
25              System.out.println("NO");
26          }
27      }
28  }

Итак, по порядку. В строке 2 импортируются основные рефальские структуры данных. Прежде всего, это Expr — рефальское выражение. Все функции в Рефале принимают выражения в качестве аргументов и возвращают их в качестве результатов. Поэтому практически любой Java-код, взаимодействующий с Рефалом, будет конструировать рефальские выражения для передачи их рефальским функциям, либо разбирать выражения — результат работы рефальских функций.

В нашем случае функция Match принимает на вход два выражения и не возвращает ничего. Эти два входных выражения строятся в строке 15 (и, аналогично, в строке 18). Статический метод Expr.fromSequence конструирует рефал-выражение из CharSequence.

Рефальская функция Match может завершиться неуспехом, поэтому она компилируется в метод, возвращающий boolean. Если работа функции завершилась неуспехом, то match.Match вернёт false.

Осталась всего одна тонкость — перехват исключения типа RefalException на строке 24. Дело в том, что любая рефал-функция компилируется в метод, способный выбросить исключение RefalException. Этот тип соответствует исключениям Рефала Плюс, которые могут быть сгенерированы при помощи специальной конструкции $error, либо возникнуть при невозможности сопоставления с образцом. В определении функции Match мы используем последнее, для того чтобы прекратить работу функции, если не удалось сопоставить остаток строки с остатком шаблона, при наличии в нём '*' (см. строку 6 листинга 1). Поэтому мы должны перехватить исключение и выдать в этом случае ответ "NO".

Что ж, тонкостей не так уж много. Взаимодействие с классом, полученным из рефал-кода, происходит ровно также, как и с любым другим Java-классом. Разница же в усилиях программиста, требуемых чтобы решить задачу на Рефале и на Java, мягко говоря, заметна. Основной алгоритм на Рефале занимает всего 5 строк, легко читаем, понимаем и исправляем. 20 минут работы против 3-ёх часов, 8 + 28 строк кода против 270 — достаточно весомый повод, чтобы задуматься о применении данной технологии, не правда ли?

-- Anton Orlov - 10 Jun 2006

Show attachmentsHide attachments
Topic attachments
I Attachment Action Size Dateup Who Comment
elserfi match.rfi manage 0.1 K 10 Jun 2006 - 03:30 OrloV Интерфейс функции Match на Рефале Плюс
javajava RunMatch.java manage 0.8 K 10 Jun 2006 - 03:33 OrloV Пример запуска рефальской функции Match из Java
elserf match.rf manage 0.4 K 10 Jun 2006 - 14:31 OrloV Решение задачи на Рефале Плюс
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r6 < r5 < r4 < r3 < r2 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback