Announcement: Omega Calculator and Library Version 0.9

davew@cs.umd.edu (David G. Wonnacott)
Mon, 28 Nov 1994 23:08:39 GMT

          From comp.compilers

Related articles
Announcement: Omega Calculator and Library Version 0.9 davew@cs.umd.edu (1994-11-28)
| List of all articles for this month |

Newsgroups: comp.constraints,comp.compilers,comp.parallel,comp.theory,sci.math.symbolic
From: davew@cs.umd.edu (David G. Wonnacott)
Followup-To: comp.constraints
Keywords: arithmetic, available, FTP
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Date: Mon, 28 Nov 1994 23:08:39 GMT

Version 0.90 of the Omega Calculator and Omega Library is now
available for anonymous ftp from ftp.cs.umd.edu:pub/omega/omega_library
Version 0.90 is the first source code release of the Omega
Calculator and library.


The Omega library/calculator manipulates sets of integer tuples and
relations between integer tuples. Some examples include:


{ [i,j] : 1 <= i,j <= 10};
{ [i] ->[i,j] : 1 <= i < j <= 10};
{ [i,j] ->[j,j'] : 1 <= i < j < j' <= n};


The conditions describing a set or tuple can be an
formulas can described by an arbitrary Presburger formula.
Relations and sets can be combined using functions such as
composition, intersection, union and difference. It
also provides routines to generate code to iterate over
the points in an integer tuple set. The Omega library provides
a high-level, C++ interface to our routines. The Omega calculator
is a text-based interface to the Omega library.


We hope to get feedback from this release about our interface.
If you have an interest in using the Omega library in your
work, please look over the interface and give us feedback.
We will be much more likely to listen to requests for changes
in the interface now than after we release version 1.0.


The interface of this current version will hopefully change and improve
for version 1.0 as a result of feedback from users and our continuing work.
However, we are unlikely to make any changes that would require substantial
changes for people writing code that interfaces with version 0.9.


We will probably release version 0.91 shortly to fix minor
bugs and improve the documentation; we intend to release version 1.0
sometime in the late spring.


The implementation of the Omega Calculator have been done
by a number of people at the University of Maryland:


Wayne Kelly, Vadim Maslov, William Pugh,
Evan Rosser, Tatiana Shpeisman, Dave Wonnacott


To give you an idea of what the Omega calculator and library
can do, I've enclosed below same output from the Omega calculator.
The input is echoed on lines starting with #




# Omega Calculator, version 0.90, November 28, 1994:
# R := { [i] -> [i'] : 1 <= i,i' <= 10 && i' = i+1 };
#
# R;
{[i] -> [i+1] : 1 <= i <= 9}
#
# inverse R;
{[i] -> [i-1] : 2 <= i <= 10}
#
# domain R;
{[i] : 1 <= i <= 9}
#
# range R;
{[i] : 2 <= i <= 10}
#
# R compose R;
{[i] -> [i+2] : 1 <= i <= 8}
#
# # closure of R = R union (R compose R) union (R compose R ...
# R+;
{[i] -> [i'] : 1 <= i < i' <= 10}
#
# complement R;
{[i] -> [i'] : i <= 0} union
  {[i] -> [i'] : 10 <= i} union
  {[i] -> [i'] : i <= i'-2} union
  {[i] -> [i'] : i' <= i}
#
# S := {[i] : 5 <= i <= 25};
#
# S;
{[i] : 5 <= i <= 25}
#
# # apply R to S
# R(S);
{[i] : 6 <= i <= 10}
#
# # restrict domain of R to S
# R \ S;
{[i] -> [i+1] : 5 <= i <= 9}
#
# # restrict range of R to S
# R / S;
{[i] -> [i+1] : 4 <= i <= 9}
#
# (R\S) union (R/S);
{[i] -> [i+1] : 4 <= i <= 9}
#
# (R\S) intersection (R/S);
{[i] -> [i+1] : 5 <= i <= 9}
#
# (R/S) - (R\S);
{[4] -> [5] }
#
# # cross product
# S*S;
{[i] -> [i'] : 5 <= i <= 25 && 5 <= i' <= 25}
#
# D := S - {[9:16:2]} - {[17:19]};
#
# D;
{[i] : 5 <= i <= 8} union
  {[i] : Exists ( alpha : 2alpha = i && 6 <= i <= 16)} union
  {[i] : 20 <= i <= 25}
#
# T := { [i] : 1 <= i <= 11 & exists (a : i = 2a) };
#
# T;
{[i] : Exists ( alpha : 2alpha = i && 2 <= i <= 10)}
#
# known := {[i]: 1 <= i <= 11};
#
# gist T given known;
{[i] : Exists ( alpha : 2alpha = i)}
#
# Hull T;
{[i] : 2 <= i <= 10}
#
# Hull D;
{[i] : 5 <= i <= 25}
#
# codegen D;
for(t1 = 5; t1 <= 8; t1++) {
    s1[t1]
    }
for(t1 = 10; t1 <= 16; t1 += 2) {
    s1[t1]
    }
for(t1 = 20; t1 <= 25; t1++) {
    s1[t1]
    }
#
# codegen {[i,j] : 1 <= i+j,j <= 10};
for(t1 = -9; t1 <= 9; t1++) {
    for(t2 = max(-t1+1,1)); t2 <= min(-t1+10,10)); t2++) {
        s1[t1,t2]
        }
    }
#
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.