Back ] Up ]



The programming language Refal 
implemented on top of the
  JavaTM2 Platform.


Refal-Java was designed and implemented by Arkady Klimov and Andrei Klimov. Please send comments, suggestions and bug reports to

See the file copying.txt for copying permission.


The developement is sponsored by AviComp.


The language Refal (REcursive Functions Algorithmic Language) has been developed in Soviet Union by dr. Valentin Turchin since 1960s. The main intention was to use it as a basis for developing various program analysis and transformation tools. The most intriguing was the idea of their self-application, which implied the following two conflicting requirements for the language:

  • it must be simple enough to simplify algorithms which analyse and transform programs written in it

  • it must be rich and expressive enough to simplify writing these algorithms in it

The idea of supecompilation as a global program optimizer was invented (by V.Turchin) and first tested in the context of Refal.

In the 70-s the most popular implementation was Refal-2. During 80-s the language has been heavily revised and the three different implementations and dialects have been emerged: 

  • Refal-5 (by V. and D. Turchin, New York), 

  • Refal-6 (by N.Kondratiev and Ark.Klimov, Moscow) 

  • Refal Plus (by S.Romanenko and R.Gurin, Moscow)

These versions have much in common while differ in some syntax details, modularity and sets of built-in functions. The first two (R5 & R6) are essentially interpreters, in the sence that Refal is compiled into an intermediate language (so-called RASL - Refal ASsembly Language) which is then executed by an interpreter - a special exe-program written in C. The latter version (R+) is essentialy a compiler, as the source code is compiled (directly or thru C) to native machine code.

However all these three versions have a common drawback: they are rather isolated from the outer world, other popular programming languages and libraries, such as Fortran, Paskal, C, C++ etc. It can be partly justified by the fact that both computational and data models of Refal are essentially functional and thus differ much from the models of those imperative languages.

The last decade (1994-2003) in computer world was enaugurated by the emergence of the language Java - a highly portable general purpose object-oriented language. Nowadays Java became a platform for a large amount of world-wide applications.

Inspite of the fact that Java has inherited most of imperative (procedural) features of its predecessors, the Java computational and data models has noticeably evolved to become more close to the functional ones. To be more positive, this can be witnessed by the following features: 

  • fields and variables may be declared final

  • parameters are passed only "by value"

  • no pointers but object references

  • automated garbage collection

  • higher level safe data model

  • safe (due to verification) program code

Thereby there were at least two arguments in favour of implementing Refal on top of Java:

  • much of needed runtime support already exists in Java runtime support

  • JavaTM2 Platform includes a large amount of valuable libraries (APIs) which will be easily accessible from Refal

Why Java needs Refal

So far we have been talking about why Java is a benefit for Refal. Now we'll address the inverse issue: why and what can Java in its turn benefit from Refal.

There are 2 unique features of Refal which are absent in almost all other languages:

  • View-oriented data model

  • Pattern-oriented computational model

Both can be viewd as opposed to object-oriented (OO) model of data and computations. In OO programming data are abstract objects which can be accessed (preferably) only via sets of functions, or methods. You see your data only through the prizm of their interfaces. This has many well-known benefits, however it prevents you from seeing your data directly as they are. In Refal data are expressions as they are written on the paper, with familiar parenthesis notation for representing trees. They are nothing more than what you see: What-You-See-Is-What-You-Get. May be it is not as good for program decomposition, incapsulation, code reuse etc., but very often within certain components this is just what you need, as it allows to grasp the whole model with one glance.

Pattern-orientedness is another powefull feature which is tightly connected with previous one. It has two aspects: pattern matching as a basis and pattern composition algebra.

Basically, patterns are abstractions of data views: you take an arbitrary data (or object) expression, which is essentially a tree list and replace some of its subexpressions with variables. We use different sorts of variables depending of structural category of respective subexpression: leave (symbol), branch (term) or branchlist (expression). Equal variables denote equal parts. Pattern matching is a kind of predicate which tests whether given pattern can be obtained as abstraction of a given data expression. As a side effect in case of true we also get some positive result: a list of bindings where pattern variables are bound with matched parts of the expression. Since variables may be lists the pattern match may imply search.

Another important aspect of pattern-orientedness is a mechanism of composing pattern matches. Since patterns may be interpreted as conditions, the algebra of operations on patterns should include logical connectives: AND, OR, NOT. In Refal we denote them by "," (comma), ";" (semicolon) and "#" (sharp) respectively. However, in Refal their semantics is more complex, as they are used to combine not only booleans but also results associated with positive answers. Consequently, a specific combination of patterns induces a specific flow of control. Java itself does not contain adequate control structures, though they can be translated rather straightforward into Java native constructs, such as if, for, break, continue and  labeled blocks. Of course, one could code them directly in Java by hand, but considering readability, clarity, etc. this won't be a good substitute.

During decades the Refal has shown itself a powerful tool applicable to many non-traditional domains where conventional languages and tools would require much more effort and courage. And the most compelling results were achieved in those cases when advanced users could glue Refal with some other "normal" language like Fortran, C, etc. With the advent of Refal-Java this poweful tandem is hopefully becoming available for all. Enjoy!

Implementation overview

Refal-Java implementation consists of 2 parts:

  • a run-time library written in Java

  • a compiler from Refal to Java written in Refal

The compiler was developed on the base of existing Refal-6-to-RASLcompiler which was also written in Refal-6. The front end remained unchanged. Thus the syntax of Refal-J is exactly the same as that of Refal-6. The back-end was completely rewritten in such a way that the whole Refal-Java compiler could run within Refal-6 machine.

Further the run-time library was written in Java so as to cover all built-in functions of Refal-6. As a result, any program written for Refal-6 can be compiled to Java and run within Java machine.

As compiler is written totally in Refal(-6) it can be compiled to Java. Thus the Refal-to-Java compiler written in Java emerged. Now it can run quite independently of any previous impementations of Refal. In particular it can compile itself.


Version 0.1.2
  • Constant declarations like 
        $CONST A=5, B=<MUL &A &A>, MAXINT = <SUB <POW 32 2> 1>;
    where the rhs may contain function calls, however must be, or evaluate to a single term (rather than arbitrary expression). The rhs evaluates at initialization time. Constants may be used only below definition in either rhs of other constant defs or in function bodies.
Version 0.1.1
Initial release of Refal-Java.

Manual (in Russian)

Full description of Refal-6/J, library of built-in functions, examples etc.

A more thorough manual of Refal-Java interface


The most recent (raw) version can be loaded from .

A file RefalJava*.zip includes

  • bin/ - Refal-6 (compiler+runtime) system plus all needed bat-files

  • compiler/ - sources in Refal for both Refal-RASL and Refal-Java compilers

  • lib/ - run-time library for Refal-Java (package org.refal.j) in Java

  • examples/ - Refal sample programs

  • doc/ - some documenatation

  • readme.txt - usage instructions

  • rfjc.jar - java class archive of Refal-Java compiler (optional)

The last item is optional as it can be built from refal sources using Refal-6 system. For installation and bootsrtrapping follow instructions in readme.txt. However the Refal-6 implementation runs only under Windows (95/98/NT/2000/XP). Hence if you use any other OS (Linux, AIX, Solaris, ...) you need rfjc.arj to compile your refal programs.

Requirements: You need the Sun JDK 1.2 or newer installed on your computer.


First, the run-time library must be compiled by the command (in directory %refalj_home%/lib/):

javac org/refal/j/*.java

In addition the resource file bin/builtinj.fls must be copied to package directory org/refal/j. This file contains the list of all builtin functions and their location. Using it the compiler allows to not import built-in functions in your refal modules.

For compilation use the command:

java -classpath %refalj_home%/rfjc.jar;%refalj_home%/lib org.refal.j.compiler.Rcmainj [options] file1.ref file2.ref ...

To get help on [options] run the command without file names.

Then compile resulting .java files using javac.

For running your refal program use the command

java -classpath %refalj_home%/lib <your main module>

(see details in the Manual)

Future plans

You are welcome to discuss and suggest topics in the list below

The Compiler

  1. Warning messages on undefined names should be bound to line number

The language

  1. Reverse (from right to left) pattern recognition (keyword $R, $r).

  2. Iterator (keyword $ITER) as in Refal Plus.

  3. Anonymous function as part of result expressions (aka lambda-expression) as in
           <Map &{ sn = <MUL sn sn>;} e.numbers>

  4. Java type specifiers for variables:
       s:int.1 e:Class.a e:double.x.

  5. Format declarations as in Refal Plus extended with type specifiers, e.g.:
            $Func F s:int e:char = s:char

  6. Multi-valued blocks and functions. A kind of block (function) which generates multivalue, or stream of values. The semantics is: select the first value, for which the subsequent tail yields success.

  7. Object oriented extension.

The library

  1. Java reflection. A facility to invoke (almost) arbitrary method of Java API.
  2. Interface with JDBC.