Refal -> Java

Subject: Refal -> Java
From: Arkady Klimov (klark@bagirra.rinet.ru)
Date: Tue Dec 07 1999 - 22:46:55 MSK

Андрей, привет,
недавно мы обсуждали вопрос о реализации рефала на основе Java. Я имел в виду компиляцию рефала в Яву. Делались оценки эффективности (умственные). Я был оптимистом - говорил, что по сравнению с нынешними (имя в виду рефал-5/6) будет уступать не более чем в пять раз и это хорошо. Ты называл цифру 10. Так вот, сегодня я поставил решающий эксперимент. Результаты меня ошеломили.

Я взял тот самый тест - select - который мы обсуждали в Переславле. И руками, по прямому алгоритму с минимумом оптимизаций (даже сознательно не делая некоторых очевидных, но не совсем тривиальных оптимизаций) - перевел его в Яву так, как это сделал бы несложный компилятор, присобачил минимально необходимый runtime-support, и исполнил. Предлагаю сравнительную таблицу результатов (N - параметр задачи, время в секундах):
 
 

N
Рефал-6
Refal->Java (byte-code)
Refal->Java (JIT)
11
5
10.5
1.22
12
29
59
6.5

Выполнял на Sun-овской java из JDK 1.2.2. Режим байт-кода включал ключом -Xint.
Итак, в режиме байт-кода уступает рефалу-6 в 2 раза (а не в 10 и даже не в 5). Поскольку было установлено, что рефал-5 обгоняет 6-й в 1.5 раза, то рефалу-5 - в 3 раза. Но в режиме jit-компиляции скорость наоборот повышается более чем в 4 раза! А от рефала-5, значит, почти  в 3. То есть эта скорость примерно соответствует Рефалу Плюс, который, помнится, в последнем тестировании показывал скорость где-то 2.5-3 по сравнению с рефалом-5.

Теперь немного о том, как выглядит отображение в Яву. Используется наиболее прямое, с моей точки зрения, отображение данных. Выражение - это массив, терм - любой объект, не массив и не null. Есть специальный объект "выражение в скобках", я назвал его Parenth. Слово = String. Символ-литера = Char. Символ-число = Integer или BigInteger и т.п.
Функция F формата ((e1) t2 e3)  -> e компилируется сигнатуру:

    static Object[] f(Object[] e1, Object t2, Object[] e3)

Если выходной формат из нескольких перменных, то из них делается выражение (e-перменные берутся в скобки) и выдается один массив, у которого размер равен числу выходных переменных.
Все функции делаются рекурсивными, хвостовая рекурсия пока никак не оптимизируется, но можно будет оптимизировать. Подвыражения при передаче аргумента дублируются, чтобы они были целым массивом (а не его частью). Однако, в процессе отождествления, локальные переменные выражения указываются, возможнжо, как части массивов, со смещением для начала и конца.
Сравнение термов отрабатывается через метод equals класса Object.
Неуспех вырабатывается в форме null (очень удобно!). Error = Exception.
Переходы при неуспехах - прямые передачи управления (if, break, continue), удлинения = циклы. При формирование результатного выражения зараз захватывается массив нужной длины (длина подсчитывается из длин компонентов), а потом копируются компоненты. Также при отождествлении жесткая часть проверяется однократным сравнением длин. Например, отождествление e0 с образцом t1 e2 t1, это проверка

(e0.length>2) && e0[0].equals(e0(e0.length-1))

Программу прикладываю: в подкатологе refal необходимый runtime-support.
В самом модуле Select "честно" оттранслированы только две функции, остальное обрамление написано просто на Яве. При вызове надо указывать список параметров вида:

java [-Xint] Select a b c d e f g h i j k

Длина списка аргументов, начиная с "а" - это и есть параметр задачи.

Я все это так подробно описал, чтобы стало понятно, насколько будет это просто, хорошо и удобно. Нельзя медлить с реализацией!
Срочно ищем исполнителя на тему.

Аркадий.

This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD