Return to ex.tex CVS log

Up to [local] / OpenXM / src / kan96xx / Doc

, is treated as a space.
,, (parse in a given ring) is changed to __
,,, (reparse a polynomial) is changed to ___

% $OpenXM: OpenXM/src/kan96xx/Doc/ex.tex,v 1.3 2004/09/10 13:20:22 takayama Exp $
\documentclass{article}
\title{\bf kan/examples}
\author{Nobuki Takayama}
\date{January 7,1995 : Revised, August 15, 1996; \\ Revised December 17, 1998.}

\def\kansm{ {\tt kan/sm1}\ }
\def\pd#1{ \partial_{#1} }
\newtheorem{example}{Example}
\newtheorem{grammer}{Grammer}

\begin{document}
\maketitle
\tableofcontents

\section{About this document}

The system \kansm is a Gr\"obner engine specialized especially
to the ring of differential operators with a subset of
Postscript language and an extension for object oriented programming. 
It is designed to be a back-end engine for a 
heterotic distributed computing system.
However, it is not difficult to control \kansm directly.
This document is a collection of programs for \kansm Version 2.xxxx.
Since the system is still evolving, there is no comprehensive manual
for the libraries of kan and the Postscript-like language {\tt sm1}.
However, all operators in \kansm are shortly explained in
{\tt onlinehelp.tex} in this directory and
it will be enough once one understands the fundamental design of the system.
This document provides introductory examples
and explains the fundamental design of the system.
If there are questions,
please send an E-mail to the author 
({\tt kan\at math.kobe-u.ac.jp}).


There are two design goals of \kansm.
\begin{enumerate}
\item Providing a backend engine in a distributed computing system for
      computations in the ring of differential operators.
\item Providing a virtual machine based on stacks to teach intermediate
level computer science especially for mathematics students.
\end{enumerate}

\section{Getting started}

To start the system, type in {\tt sm1}.
To quit the system, type in {\tt quit}.
You can make a program run in \kansm by the operator
\begin{verbatim}
        (filename) run  ;
\end{verbatim}
or
\begin{verbatim}
        $filename$ run  ;
\end{verbatim}
The two expressions \verb! $xyz$ ! and {\tt (xyz)} have the same meaning;
they means the string {\tt xyz}.
The pair of brackets generates a string object.
The dollar sign is used for a compatibility to \kansm Version 1.x.


There are three groups of functions. 
The first group is those of primitive operators.
They are functions written in C.
The second group is those of macro operators.
They are functions written in {\tt sm1} language and automatically
loaded when the system starts.
The third group is those of macro operators defined in the library files
in {\tt lib/} directory.
These operators provide a user friendly interfaces of computing
characteristic ideal, holonomic rank, $b$-function, annihilating
ideal, hypergeometric differential operators,
restrictions, de Rham cohomology groups.
You can get a list of primitive operators and macros
by {\tt ?} and {\tt ??} respectively.
To see the usage of a macro, type in
{\tt (macro name) usage ; }.
Note that you need a space before {\tt ;}.
All tokens should be separated by the space
or special characters \verb+ ( ) [ ] { } $ % +.
The help message usually provides examples.
For example, the line
{\tt (add) usage } present the example
\verb+ Example:  2 3 add ::  ==> 5+
You may try the input line
{\tt 2 3 add ::}
and will get the output {\tt 5}.
All printable characters except the special characters
\verb+ ( ) [ ] { } $ % +
can be a part of a name
of a macro or primitive operator.
For example, {\tt ::} is a name of macro which
outputs the top of the stack and the prompt.


\kansm is a stack machine.
Any object that has been input is put on the top of the stack.
Any operator picks up objects from the stack, executes computations and
puts results on the stack.
For example, the primitive operator {\tt print} picks up one object
from the stack and print it to the screen.
If you type in
{\tt (Hello World) print},
then the string ``Hello World'' is put on the stack and the operator
{\tt print} picks up the string and print it.
The macro {\tt message} works like {\tt print} and outputs the newline.
The macro {\tt :: } is similar to {\tt message}, 
but it also outputs the newline and the prompt;
it picks up one object from the stack, print the object to the screen and
output the prompt {\tt sm1>}.
For example, when you type in
\begin{verbatim}
    (Hello World) ::
\end{verbatim}
you get
\begin{verbatim}
Hello World
sm1>
\end{verbatim}
We introduce two more useful stack operators.
\begin{enumerate}
\item[] {\tt pop} \quad Remove the top element from the stack.
\item[] {\tt pstack} \quad Print the contents of the entire stack.
\end{enumerate}
You can use \kansm as a reverse Polish calculator; try the following lines.
\begin{verbatim}
     11 4 mul ::
     3 4 add /a set
     5 3 mul /b set
     a b add ::
\end{verbatim}

Mathematical expressions such as \verb! x^2-1 ! are not parsed by the
stackmachine. 
The parsing is done by the primitive operator {\tt .} (dot) in the current
ring.
For example,  type in the following line just after you started \kansm
\begin{verbatim}
(  (x+2)^10 ).   ::
\end{verbatim}
then you will get the expansion of $ (x+2)^{10} $.
\verb! (  (x+2)^10 ) ! is a string and is pushed on the stack.
Next, the operator {\tt .} parses the expression and convert it
to an internal expression of the polynomial.
Note that the given string is parsed in the current ring.
In order to see the current ring, use the operator
{\tt show\_ring}.
Note that the polynomials in {\tt sm1} means
polynomials with the coefficients in a given ring such as {\bf Z}.
So,
\verb! (x/3+2). !
is {\em not accepted}.

A variable is defined by placing the variable's name, value and 
{\tt def} operator on the stack of \kansm as in the following
line:
\begin{verbatim}
   /abc  23  def
\end{verbatim}
The macro {\tt set} is an alternative way to define a variable and set a value.
\begin{verbatim}
   23 /abc set
\end{verbatim}
means to set the value {\tt 23} to the variable {\tt abc}.

In order to output an expression to a file,
the macro {\tt output} is convinient.
For example, the lines
\begin{verbatim}
 ( (x+2)^10 ). /a set
 a output
\end{verbatim}
output the expansion of $(x+2)^{10}$ to the file
{\tt sm1out.txt}.

If you need to run a start-up script, 
modify the shell script {\tt Doc/startsm1} and write what you need
in the file {\tt Doc/Sm1rc}.

\smallbreak
The system \kansm  is not designed for a heavy interactive use.
So, unless you are a stackmachine fan,
it is recommended to write your input in a file, for example,
in {\tt abc.sm1}, and execute your input as
{\footnotesize \begin{verbatim}
    sm1 -q <abc.sm1
\end{verbatim}}
\noindent Here is an example of an input file {\tt abc.sm1}:
{\footnotesize \begin{verbatim}
    (cohom.sm1) run
    [(y^2-x^3-2) (x,y)] deRham ::
\end{verbatim}}
\noindent The option {\tt -q} is for not outputting starting messages.


\medbreak

We close this section with introducing some useful references.

For the reader who are interested in writing a script for {\tt kan/sm1},
it is strongly recommended to go through Chapters 2 and 4
(stack and arithmetic, procedures and variables) of the so called
``postscript blue book'' \cite{Postscript}.
The control structure of {\tt Kan/sm1} is based on a subset of
Postscript.

The book \cite{Oaku} is a nice introduction to compute $D$-module invariants
with Gr\"obner bases. 
The book \cite{SST} is the latest book on this subject.
This book explains the notion of homogenized Weyl algebra,
which is the main ring for computations in \kansm.
and algorithms for $D$-modules.
As to an introduction to mathematical aspect of $D$-modules, 
Chapter 5 of \cite{Hotta} is recommended.

The latest information on {\tt kan/sm1} and related papers are put on the
http address \cite{www}.

\section{Package files in the Doc/ (lib/) directory}

A set of user friendly packages are provided
for people who are interested in $D$-modules
($D$ is the ring of differential operators), but
are not interested in the aspect of {\tt sm1}
as a part of distributed computing system.
Here is a list of packages.
\begin{enumerate}
\item {\tt bfunction.sm1} : Computing b-functions.
                        This script is written by T.Oaku.
\item{\tt factor-a.sm1} : A sample interface with {\tt risa/asir} \cite{asir}
to factor given polynomials.
\item{\tt hol.sm1} : A basic package for holonomic systems (Gr\"obner basis and
initial ideals, holonomic rank, characteristic variety, annihilating ideal
of $f^s$).
\item{\tt gkz.sm1} : Generate GKZ system for a given $A$ and $b$.
\item{\tt appell.sm1} : Generate Appell hypergeometric differential equations.
\item{\tt cohom.sm1} : An experimental package for computing restrictions
and de Rham cohomology groups mainly written by T.Oaku.
\item {\tt kanlib1.c} : An example to explain an interface between kan and
 C-program. Type in ``make kanlib1'' to compile it.
\item{\tt ox.sm1} : A package for communication based on the open XM protocol.
The open sm1 server {\tt ox\_sm1} can be obtainable from the same ftp cite
of {\tt kan/sm1}.
See {\tt http://www.math.kobe-u.ac.jp/openxxx} for the protocol design.
\item{\tt oxasir.sm1} : A package to use open asir server based on the open
                        XM protocol.
Open asir server {\tt ox\_asir} will be distributed from \cite{asir}.
The package {\tt cohom.sm1} ({\tt deRham}) and {\tt annfs} need this package 
to analyze the roots of $b$-functions.
The built-in function to analyze the roots is slow. The open asir server
and {\tt oxasir.sm1} should be used for efficient analysis of the roots
of $b$-functions.
See the usage of {\tt oxasir} for the latest information.
\item{\tt intw.sm1} : Compute $0$-th integration of a given $D$-module
by using a generic weight vector.
\end{enumerate}

See the section three of {\tt onlinehelp.tex} for more informations.

\subsection{Examples: {\tt gb, rrank, gkz, bfunction, deRham}}

Execute {\tt Loadall} to load packages before executing examples.
{\tt Dx} means $\partial_x$.

\begin{example} \rm
Compute a Gr\"obner basis and the initial ideal 
with respect to the weight vector
$(0,0,1,1)$ of the $D$-ideal
$$D \cdot \{ (x \partial_x)^2 + (y \partial_y)^2 -1, 
             x y \partial_x \partial_y-1 \}.$$
See \cite{SST} on the notion of 
Gr\"obner basis and the initial ideal with respect
to a weight vector.
\begin{verbatim}
 [ [( (x Dx)^2 + (y Dy)^2 -1) ( x y Dx Dy -1)] (x,y) 
             [ [ (Dx) 1 (Dy) 1] ] ] gb pmat ; 
\end{verbatim}
{\footnotesize
Output:
\begin{verbatim}
 [ 
  [ x^2*Dx^2+y^2*Dy^2+x*Dx+y*Dy-1 , x*y*Dx*Dy-1 , y^3*Dy^3+3*y^2*Dy^2+x*Dx ] 
  [ x^2*Dx^2+y^2*Dy^2 , x*y*Dx*Dy , y^3*Dy^3 ] 
 ]
\end{verbatim}
}
The first line is the Gr\"obner basis and the second line is a set of
generators of the initial ideal with respect to the weight
vector $(0,0,1,1)$.
In order to get syzygies, use {\tt syz}.
\end{example}

\begin{example} \rm
Generate the GKZ system for $A=\pmatrix{1 & 1 & 1 & 1  \cr
                                   0 & 1 & 3 & 4 \cr}$
and $\beta = (1,2)$.
Here, the GKZ system is a holonomic system of differential equations
introduced by Gel'fand, Kapranov and Zelevinsky.
The system is also called ${\cal A}$-hypergeometric system.
\begin{verbatim}
   [ [[1 1 1 1] [0 1 3 4]] [1 2]] gkz  ::
\end{verbatim}
{\footnotesize
Output:
\begin{verbatim}
 [ x1*Dx1+x2*Dx2+x3*Dx3+x4*Dx4-1 , x2*Dx2+3*x3*Dx3+4*x4*Dx4-2 , 
   Dx2*Dx3-Dx1*Dx4 , -Dx1*Dx3^2+Dx2^2*Dx4 , Dx2^3-Dx1^2*Dx3 , 
   -Dx3^3+Dx2*Dx4^2 ]
\end{verbatim}
}
\end{example}

\begin{example} \rm
Evaluate the holonomic rank of
    the GKZ systems for $A=\pmatrix{1 & 1 & 1 & 1  \cr
                                   0 & 1 & 3 & 4 \cr}$
and $\beta = (1,2)$ and $\beta=(0,0)$.
Show also the time of the execution.
\begin{verbatim}
  { [ [[1 1 1 1] [0 1 3 4]] [1 2]] gkz  rrank ::} timer
  { [ [[1 1 1 1] [0 1 3 4]] [0 0]] gkz  rrank ::} timer
\end{verbatim}
{\footnotesize
Output:
\begin{verbatim}
   5
User time: 1.000000 seconds, System time: 0.010000 seconds, Real time: 1 s
   4
User time: 1.320000 seconds, System time: 0.000000 seconds, Real time: 1 s
\end{verbatim}
}
\end{example}

\begin{example} \rm
Compute the $b$-function of  $f=x^3-y^2 z^2$
and the annihilating ideal of $f^{r_0}$ where
$r_0$ is the minimal integral root of the $b$-function.
\begin{verbatim}
   (oxasir.sm1) run
   [(x^3 - y^2 z^2) (x,y,z)] annfs /ff set
   ff message
   ff 1 get 1 get fctr ::
\end{verbatim}
{\footnotesize
Output:
\begin{verbatim}
[  [ -y*Dy+z*Dz , 2*x*Dx+3*y*Dy+6 , -2*y*z^2*Dx-3*x^2*Dy , 
   -2*y^2*z*Dx-3*x^2*Dz , -2*z^3*Dx*Dz-3*x^2*Dy^2-2*z^2*Dx ]  , 
 [-1,-139968*s^7-1119744*s^6-3802464*s^5-7107264*s^4-7898796*s^3-5220720*s^2-1900500*s-294000]] 
[[ -12 , 1 ] , [ s+1 , 1 ], [3*s+5 , 1], [ 3*s+4, 1], [6*s+7, 2], [6*s+5, 2]] 
\end{verbatim}
}
The first two rows of the output give generators of the annihilating
ideal of
$(x^3-y^2 z^2)^{-1}$.
The $b$-function is
$(s+1)(3s+5)(3s+4)(6s+7)^2(6s+5)^2$
and $-1$ is the minimal integral root.
\end{example}


\begin{example} \rm
Compute the de Rham cohomology group 
of $X={\bf C}^2 \setminus V(x^3-y^2)$.
\begin{verbatim}
    (cohom.sm1) run
    [(x^3-y^2) (x,y)] deRham ;
\end{verbatim}
{\footnotesize
Output:
\begin{verbatim}
  0-th cohomology:  [    0 , [   ]  ] 
  -1-th cohomology:  [    1 , [   ]  ] 
  -2-th cohomology:  [    1 , [   ]  ] 
 [1 , 1 , 0 ]
\end{verbatim}
}
This means that $H^2(X,{\bf C}) = 0$,
$H^1(X,{\bf C}) = {\bf C}^1$,
$H^0(X,{\bf C}) = {\bf C}^1$.
\end{example}

\begin{example} \rm
Compute the integral of
$ I=D\cdot \{\partial_t -(3 t^2-x) ,\,  \partial_x+t \}$,
which annihilates the function $e^{t^3-x t}$,
with respect to $t$.
\begin{verbatim}
 (cohom.sm1) run
 [ [(Dt - (3 t^2-x)) (Dx + t)] [(t)]
   [ [(t) (x)] [ ]] 0] integration
\end{verbatim}
{\footnotesize Output:
\begin{verbatim}
[    [    1 , [    3*Dx^2-x ]  ]  ]
\end{verbatim} }

\end{example}



\section{Data types}

Each object in {\tt sm1} has a data type.
Here is a list of main primitive data types,
which are common to other languages except the type polynomial
and the type ring.
\begin{enumerate}
\item[] {\bf null}
\item[] {\bf integer}(machine integer), \quad
   32 bit integer. \quad Example: {\tt 152}
\item[] {\bf literal}, \quad
   literal. \quad Example: {\tt /abc}
\item[] {\bf string}, \quad
   string. \quad Example: {\tt (Hello)}
\item[] {\bf executableArray}, \quad
   program data. \quad Example: {\tt \{ add\ 2 \ mul \} }
\item[] {\bf array}, \quad
   array, \quad Example: {\tt [(abc) \ 5 ]}
\item[] {\bf polynomial}, \quad
   polynomial, \quad Example: \verb! (x^2-1). !
\item[] {\bf ring}, \quad
   ring definition. 
\item[] {\bf number}(universalNumber), \quad
   Big num. \quad Example: \verb! (123).. 456 power !
\item[] {\bf class}, \quad
   Class.
\end{enumerate}

\subsection{Array}
Array is a collection of one dimensional objects surrounded by square
brackets and
indexed by integers (machine integers) $0, 1, 2, \ldots$.
Elements of any array may be arrays again, so we can express
list structures by using arrays.
An array is constructed when the {\tt sm1} encounters the right square
bracket. 
Note that square brackets are also operators.
Thus, the line
\begin{verbatim}
    [(Hello) 2  50  add]
\end{verbatim}
sets up an array
\begin{verbatim}
    [(Hello)  52]
\end{verbatim}
where the $0$-th element of the array is the string
{\tt (Hello)}
and the $1$-th element is the integer {\tt 52}.
The {\tt put} and {\tt get} operator store and fetch an element of
an array.
The {\tt get} operator takes an array and an index from the stack
and returned the object indexed by the second argument.
The line
\begin{verbatim}
   [(sm1)  12  [(is) (fun)] 15]   2    get
\end{verbatim}
would return the array
{\tt [(is) (fun)]} on the stack.
The {\tt put} operator takes an array, an index {\tt i}, an object
from the stack
and store the object at the $i$-th position of the array.
That is,
\begin{verbatim}
 /a [(sm1) (is) (fun)] def
 a 2 (a stackmachine) put
\end{verbatim}
would rewrite the contents of the variable {\tt a} as
\begin{verbatim}
   [(sm1) (is)  (a stackmachine)]
\end{verbatim}

\subsection{Ring}

The ring object is generated by the operator {\tt define\_ring}.
This operator has a side effect;
it also changes the {\it current ring}.
The line
\begin{verbatim}
  [(x,y)  ring_of_differential_operators 0] define_ring /R set
\end{verbatim}
would create the ring of differential operators
$$ {\bf Z} \langle x, y, \partial_x, \partial_y \rangle, $$
store it in the variable {\tt R} and changes the current ring
to this Weyl algebra.
$\partial_x$ is denoted by ${\tt Dx}$ on {\tt sm1}.
The suffix ${\tt D}$ can be changed;
for example, if you want to use {\tt dx} instead of {\tt Dx},
execute the command
{\tt /\at \at \at}\verb+.Dsymbol (d) def +
The current ring can be obtained by
{\tt [(CurrentRingp)] system\_variable }.
The current ring is the ring of polynomials of
two variables $x, h$ when the system starts.

All polynomial except $0$ belongs to a ring.
For a non-zero polynomial {\tt f},
the line
\begin{verbatim}
   f (ring)  dc /rr set
\end{verbatim}
put the associated ring object of {\tt f} to the variable {\tt rr}.
As we have seen before,
a given string is parsed as a polynomial in the current ring by the operator
``{\tt .}''.
To parse in a given ring,
the operator ``{\tt \_\_}'' is used.
That is,
\begin{verbatim}
   [(x,y)  ring_of_differential_operators 0] define_ring /R set
   (x^2-y) R  __  /f  set
\end{verbatim}
means to parse the string \verb! x^2-y ! in the ring {\tt R}
and put the polynomial $x^2-y$ in the variable {\tt f}.
Arithmetic operators for two polynomials can be performed only
when the two polynomials belong to a same ring.
If you want to map a polynomial to a different ring,
the easiest way is to translate the polynomial into a string and
parse it in the ring.
That is,
\begin{verbatim}
   [(x,y) ring_of_polynomials 0] define_ring /R1 set
   (x-y). /f set
   [(x,y,z) ring_of_differential_operators 0] define_ring /R2 set
   (y+Dz). /g set
   f toString . /f set
   f g add ::
\end{verbatim}
would output
$ (x-y) + (y+Dz) = Dz$.

It is convinient to have a class of numbers that is contained in
any ring.
The datatype number (universalNumber) is the class of bignum, which is
allowed to be added and multiplied to any polynomials with characteristic 0.

\subsection{Tag}
Each object of {\tt kan/sm1} has the tag expressed by an integer.
The tag expresses the class to which the object belongs.
You can see the tag of a given object by the operator {\tt tag}.
For example, if you type in
\begin{verbatim}
10 tag ::
\end{verbatim}
then you get the number $1$.
If you type in
\begin{verbatim}
[ 1  2]  tag ::
\end{verbatim}
then you get the number $6$.
The number $1$ is the tag of the integer objects and
the number $6$ is the tag of the array objects.
These tag numbers are stored in the variables
{\tt IntegerP} and {\tt ArrayP}.
In order to translate one object to that in a different class,
there is the operator {\tt data\_conversion} or {\tt dc}.
For example,
\begin{verbatim}
(10). (integer) dc  ::
\end{verbatim}
translates the polynomial $10$ in the current ring into the integer $10$
and
\begin{verbatim}
(10). (string) dc  ::
\end{verbatim}
translates the polynomial $10$ into the string 10.

\section{Gr\"obner basis and Syzygy computation in \kansm}
\subsection{Computing Gr\"obner or standard basis in the ring of the polynomials}

\begin{example}
Obtain the Gr\"obner basis of the ideal generated by 
the polynomials $x^2+y^2-4$ and $xy-1$ in terms of the graded reverse
lexicographic order :
$$ 1 < x < y < x^2 < xy < y^2 < \cdots. $$
\end{example}
 
All inputs must be homogenized to get Gr\"obner basis
by the command {\tt groebner}. 
Usually, the variable $h$ is used for the homogenization.
In this example,
Gr\"obner bases in 
${\bf Q}[x,y,h]$ are computed, 
but rational coefficients in the input is not allowed.
All coefficients must be integers.

The operator {\tt groebner\_sugar} is for non-homogenized
computation of Gr\"obner basis.

The following code is a convinient template to obtain
Gr\"obner bases.

@gbrev.sm1

The letters after the symbol {\tt \%} are ignored by \kansm ;
comments begin with the symbol {\tt \%}.
If one needs to compute Gr\"obner basis of a given set of polynomials,
one may only change the lines marked by the comment
{\tt \% Change here}.

\begin{grammer}
Any string of alphabets can be used as a name of a variable except
{\tt h}, {\tt E}, {\tt H} and {\tt e\_}.
For $q$-difference operators, {\tt q} is also reserved.
Upper and lower case letters are distinct.
\end{grammer}

\bigbreak

\begin{example}
Obtain the Gr\"obner basis of the ideal generated by 
the polynomials $x^2+y^2-4$ and $xy-1$ in terms of the 
lexicographic order :
$$ 1 < x < x^2 < x^3 < \cdots < y < yx < yx^2 < \cdots. $$
\end{example}


@gblex.sm1
In this example, the order is specified by the weight vector.
If the line \\
\verb+ [vec1  vec2  ...] weight_vector +
is given in the definition of the ring,
monomials are compared by the weight vector {\tt vec1}.
If two monomials have the same weight, then they are
compared by the weight vector {\tt vec2}.
This procedure will be repeated until all weight vectors are used.

The weigth vector is expressed in the form
{\tt [v1 \  w1 \ v2 \ w2 \  ... vp \ wp ]},
which
means that the variable {\tt v1} has the weight {\tt w1},
the variable {\tt v2} has the weight {\tt w2}, $\ldots$.
For example,
when the ring is defined by
\begin{verbatim}
  [(x,y,z) ring_of_polynomials 
   [[(x) 1 (y) 3]  [(z) -5]] weight_vector 0]
  define_ring
\end{verbatim}
two monomials 
$x^a y^b z^c \succ x^A y^B z^C$
if and only if
$ a+3b > A+3B$ or
($ a+3b = A+3B$ and $ -5 c > -5 C$)
or
($ a+3b = A+3B$ and $ -5 c = -5 C$ and $(a,b,c) \succ_{grlex} (A,B,C)$)
where $\succ_{grlex}$ denotes the graded reverse lexicographic order.
\bigbreak

The Buchberger's criterion 1 is turned off by default,
because it does not work in case of the ring of differential operators.
To turn it on,
input \\
\verb! [(UseCriterion1) 1] system_variable !

The operator {\tt groebner} outputs the status of degree by degree computation
of Gr\"obner basis.
To turn off this message, input
\verb! [(KanGBmessage) 0] system_variable !


\begin{example}
Obtain the Gr\"obner basis of the ideal generated by 
the polynomials 
$$x^2+y^2+z^2-1,xy+yz+zx-1,  xyz-1                   $$
in terms of the 
elimination order 
$ x,y > z. $
\end{example}

@gbelim.sm1
\bigbreak


\subsection{Computing Gr\"obner basis in the ring of differential operators}

\begin{example}
Obtain the Gr\"obner basis of the ideal in the Weyl algebra
$$  {\bf Q } \langle x,y,\pd{x},\pd{y} \rangle, \quad \hbox{ where }\ 
    \pd{x}=\frac{\partial}{\partial x},
    \pd{y}=\frac{\partial}{\partial y}
$$
generated by 
the differential operators
$$ x \pd{x} + y \pd{y},
   \pd{x}^2 + \pd{y}^2
$$
in terms of the elimination order 
$ \pd{x}, \pd{y} > x,y $
by using the homogenized Weyl algebra.
\end{example}

@gbdiff.sm1
\bigbreak

\subsection{Computing Gr\"obner basis in $R^n$}

\begin{example}
Let $S$ be the ring of polynomials
$Q [x,y]$.
Obtain the Gr\"obner basis of the $S$-submodule of $S^3$
generated by the vectors
$$ (x-1,y-1,z-1), (xy-1,yz-2,zx-3). $$
\end{example}

@gbvec.sm1
\bigbreak

\subsection{Computing syzygies}

Let $R$ be a ring and $f_1, \ldots, f_m$ be elements of $R$.
The left $R$-module 
$$ \{ (s_1, \ldots, s_m \in R^m \,|\, \sum_{i=1}^m s_i f_i = 0 \} $$
is called the syzygy among $f_1, \ldots, f_m$.
The following script computes the generators of the syzygy
among
$$ x \pd{x} + y \pd{y},
   \pd{x}^2+\pd{y}^2
$$
in the homogenized Weyl algebra.

@syz.sm1
The 0-th element of {\tt ans} is the Gr\"obner basis.
The 1st element of {\tt ans} is the transformation matrix from the input
to the Gr\"obner basis.
The 2nd element of {\tt ans} is a set of generators of the syzygies
of the input.

\bigbreak


\section{Control Structures and programming}

\subsection{if}
The conditional operator {\tt if} requires three objects on the stack:
an integer value and two executable arrays, which are program data.
The first executable array will be executed if the integer value is not 0.
The second executable array will be executed if the integer value is 0.
For example, the program line
\begin{verbatim}
    1 { op1 } {op2} ifelse
\end{verbatim}
executes {\tt \{ op1 \}} and the program line
\begin{verbatim}
    0 { op1 } {op2} ifelse
\end{verbatim}
executes {\tt \{ op2 \}}.

Here is a list of comparison operators.
\begin{enumerate}
\item[] {\tt eq} \quad $=$ \quad  Example: {\tt [1 2] [1 3] eq }
\item[] {\tt gt} \quad $>$ \quad  Example: {\tt 3 2 gt}
\item[] {\tt lt} \quad $<$ \quad  Example: {\tt 3 2 lt}
\item[] {\tt not}  \quad  Example: {\tt 3 2 eq not}
\item[] {\tt and}  \quad  Example: {\tt 3 2 eq 5 6 lt and }
\item[] {\tt or}  \quad  Example: {\tt 3 2 eq 5 6 lt or }
\end{enumerate}


\subsection{for}
The {\tt for} operator implements a counting loop.
This operator takes three integers and one executable array:
\begin{verbatim}
   i0  d  i1  { ops } for
\end{verbatim}
{\tt i0} is the loop counter's starting value,
{\tt d} is the increment amount,
{\tt i1} is the final value.
The {\tt for} operator put the value of the counter on the stack before
each execution of {\tt ops}.
For example, the program line
\begin{verbatim}
  1 1 5  { /i set i message } for
\end{verbatim}
outputs
\begin{verbatim}
   1  2   3   4   5 
\end{verbatim}



\subsection{{\tt map} function}

{\tt map} function is used to apply an operator to each element
of a given array.
For example, the following line is used to translate each polynomial
of the given array {\tt aa} into the corresponding string
\begin{verbatim}
          /aa [( (x-1)^2 ). (2^10).] def
          aa { (string) dc } map /ff set ;
          ff ::
\end{verbatim}
It becomes easier to writing script for {\tt kan/sm1} by using the {\tt map}
function.

\subsection{Function definition}

Programs are stored in executable arrays and
the curly brackets generate executable arrays.
For example, if you input the line
\begin{verbatim}
    {  add 2 mul }
\end{verbatim}
then the executable array object which represents the program
``take two elements from the stack, add them, and multiply two 
and put the result on the stack''
will be store on the top of the stack.
You can bind the program to a name.
That is, 
\begin{verbatim}
   /abc { add 2 mul } def
\end{verbatim}
binds the executable array to the variable {\tt abc}.
The input \verb+ 2 4 abc :: + outputs {\tt 12}.
When {\tt sm1} encounters the name {\tt abc},
it looks up the user dictionary and finds that
the value of {\tt abc} is the executable array
\verb+ { add 2 mul } +.
The executable array is loaded to the stack machine and
executed.

Funtions can be defined by using executable arrays.
Here is a complete example of a function definition in {\tt sm1}
following standard conventions.
\begin{verbatim}
   /foo {
     /arg1 set
     [/n /i /ans] pushVariables
     [
       /n arg1 def
       /ans 0 def
       1 1 n {
         /i set
         /ans ans i add def
       } for
       ans /arg1 set
     ] pop
     popVariables
     arg1
   } def
\end{verbatim}
The function returns the sum $1+2+\cdots+ n$.
For example, 
{\tt 100 foo ::} outputs $5050$.
The arguments of the function should firstly be stored in the variables
{\tt arg1}, {\tt arg2}, $\ldots$.
It is a convension in {\tt sm1} programming.
The local variables are declared in the line
\begin{verbatim}
     [/n /i /ans] pushVariables
\end{verbatim}
The macro {\tt pushVariables} stores the previous values of
{\tt n}, {\tt i}, {\tt ans} on the stack and
the macro {\tt popVariables} restores the previous values.
So, you can use {\tt n}, {\tt i}, {\tt ans}
as a local variable of this function.
The function body should be enclosed as
\begin{verbatim}
    [

    ] pop
\end{verbatim}
It is also a convension in {\tt sm1} programming
to avoid unmatched use of
{\tt pushVariables} and {\tt popVariables}.


\begin{example} \rm
{\tt cv0.sm1} is a script to compute characteristic variety
for $D$-submodules in $D^n$.

{\tt cv2.sm1} is a script to compute the multiplicites of
$D$-modules.
\end{example}


\section{Dictionaries and contexts}

The {\tt def} or {\tt set} operators associate a key with a value
and that key-value pair is stored in the current dictionary.
They key may starts with any printable character except
\verb+ ( ) [ ] { } $ % +
and numbers and be followed by any printable characters
except the special characters.
For example,
\begin{verbatim}
  foo  test   Test!   foo?59
\end{verbatim}
are accepted as names for keys.

A key-value pair is stored in the current dictionary
when you use the operator {\tt def}
or the operator {\tt set}.
For example,
when you input the line
\begin{verbatim}
   /foo  15   def
\end{verbatim}
then the key-value pair
({\tt foo}, 15) is stored in the current dictionary.
We can generate several dictionaries in {\tt sm1}.
Each dictionary must have its parent dictionary.
When you input a token (key) that is not a number or a string or a literal,
{\tt sm1} looks up the current dictionary to find the value of the key.
If the value is an executable array, then it will be executed.
If the value is not an executable array, then the value is put on the stack
as an object.
If the looking-up fails, 
then it tries to find the value in the parent dictionary.
If it fails again, then it tries to find the value in the grandparent
dictionary and so on.
This mechanism enables us to write an object oriented system.
When the system starts, there are two dictionaries:
primitive dictionary and the standard user dictionary.
For example, the input {\tt ?} makes {\tt sm1} to look up
the standard user dictionary and {\tt sm1} finds the value of {\tt ?},
which is an executable array that displays all keys in the primitive
dictionary.

A new dictionary can be created by the operator {\tt newcontext}.
Here is an example of creating a new dictionary.
\begin{verbatim}
/abc { (Bye) message } def 
/aaa 20 def 
abc  aaa ::
\end{verbatim}
The key-value pairs ({\tt abc}, \verb+ { (Bye) message } +
and
({\tt aaa}, \verb+ 20 +)
are stored in the current dictionary ({\tt StandardContextp}).
Here is the output from the system.
{\footnotesize \begin{verbatim}
Bye
20
\end{verbatim} }
\begin{verbatim}
(mycontext) StandardContextp newcontext /nc set ;
nc setcontext ;
\end{verbatim}
Create a new dictionary and change the current dictionary
by {\tt setcontext}.
\begin{verbatim}
/abc { (Hello) message } def ;
abc aaa ::
\end{verbatim}
Store a new key-value pair in the new dictionary.
Here is the output of the system.
{\footnotesize \begin{verbatim}
Hello
20
\end{verbatim} }
The key {\tt abc} was found in the current dictionary, so
the system outputs {\tt Hello}.
The key {\tt aaa} was not found in the current dictionary,
so the system looked for it in the parent dictionary and
outputs the value {\tt 20}.


It is sometimes preferable to protect the key-value pairs
from unexpected rewriting.
If you input the following lines, then all pairs in the current dictionary
except
{\tt arg1}, {\tt arg2}, {\tt arg3}, {\tt v1}, {\tt v2}, {\tt \at.usages}
will become readonly pairs.
{\footnotesize \begin{verbatim}
[(Strict2) 1] system_variable  %% from var.sm1
[(chattrs) 2] extension
[(chattr) 0 /arg1] extension
[(chattr) 0 /arg2] extension
[(chattr) 0 /arg3] extension
[(chattr) 0 /v1] extension  %% used in join.
[(chattr) 0 /v2] extension
\end{verbatim} 
{\tt [(chattr) 0 /\at.usages] extension}}

\section{Using {\tt sm1} to teach computer science for 
students in mathematics}

There are two design goals in {\tt sm1}.
One  goal  is to provide a backend engine for the ring of differential
operators in a 
heterotic distributed computing system.
Another interesting design goal is to help to teach basics of
intermediate level computer science quickly
and invite students to mathematical programmers' world.
It is a fun to learn computer science with {\tt sm1}!
Here are some topics that I tried in class rooms.
These are intermediate level topics that should be learned after
students have learned elementary programming by languages like
Pascal, C, C++, Java, Basic, Mathematica, Maple,  Macaulay 2, etc.

\subsection{Recursive call and the stack}

The notion of stack is one of the most important idea in computer science.
The notion of recursive call of functions is usually taught in the first
course of programming.
I think it is important to understand how the stack is used to emulate
recurisve calls.
The idea is the use of the stack.
Function arguments and local variables are stored in the stack.
It enables the system to restore the values of the local variables and arguments
after an execution of the function.
However, it should be noted that, for each function call, the stack 
dynamically grows.

As an example that I used in a class room, 
let us evaluate the $n$-th Fibonacci number
defined by
$$ f_n = f_{n-1}+f_{n-2}, \ f_1 = f_2 = 1 $$
by using a recurisive call.
\begin{verbatim}
  /fib {
    /arg1 set 
    [/n /ans] pushVariables
    pstack
      /n arg1 def
      (n=) messagen n message
      (-------------------------------) message
      n 2 le {
        /ans  1  def
      }
      {
        n 1 sub fib  n 2 sub fib add /ans set
      } ifelse
      /arg1 ans def
    popVariables
    arg1
  } def
\end{verbatim}
The program would return the $n$-th Fibonacci number.
That is,
\verb+ 4 fib :: +
would return $f_4=3$.
It also output the entire stack at each call,
so you can observe how stack grows during the computation
and how local variables {\tt n}, {\tt ans} are stored 
in the stack.
You would also realize that this program is not efficient
and exhausts huge memory space.


\subsection{Implementing  a Java-like language}

One of the exciting topic in the course of computer science
is mathematical theory of parsing.
After learning the basics of the theory,
it is a very good Exercise to design a small language and
write a compiler or interpreter for the language.
If you do not like to write a compiler for real CPU,
the stackmachine {\tt sm1} will be a good target
machine.
For example, the language may accept the input
\begin{verbatim}
  12345678910111213*(256+2)
\end{verbatim}
and the interpreter or the compiler generate the following code for {\tt sm1}
\begin{verbatim}
  (12345678910111213)..
  (256)..
  (2).. add
   mul message
\end{verbatim}
One can easily write an arbitrary precision calculator by using
{\tt sm1}
and also try algorithms in the number theory by one's own language.

\noindent
Exercise 1: parse a set of linear equations like
{\tt  2x+3y+z = 2; y-z =4; }, output the equation in the matrix form
and find solutions. \\
Exercise 2: 
Modify the calculator {\tt hoc} so that it can use {\tt sm1} as the
backend engine.
The calculator {\tt hoc} is discussed in the book:
Kerningham and Pike, Unix programming environment.

The stackmachine {\tt sm1} provides a very strong virtual machine for
object oriented system by the dictionary tree.
We can easily implement a language, on which Java-like object 
oriented programming mechanism is installed,
by using {\tt sm1}.
Here is a sample program of {\tt kan/k0}, which is an object oriented
language and works on {\tt sm1}.
I taught a course on writing mathematical softwares
in a graduate school with {\tt k0}.
\begin{verbatim}
class Complex extends Object {
  local re, /* real part */
        im; /* imaginary part*/
  def new2(a,b) {
    this = new(super.new0());
    re = a;
    im = b;
    return(this);
  }
  def real() { return(re); }
  def imaginary() { return(im); }
  def operator add(b) {
    return( new2(re+b.real(), im+b.imaginary()) );
  }
  def operator sub(b) {
    return( new2(re-b.real(), im-b.imaginary()) );
  }
  def operator mul(b) {
    return(new2( re*b.real()-im*b.imaginary(), re*b.imaginary()+im*b.real()));
  }
  def operator div(b) {
    local den,num1,num2;
    den = (b.real())^2 + (b.imaginary())^2 ;
    num1 = re*b.real() + im*b.imaginary();
    num2 = -re*b.imaginary()+im*b.real();
    return(new2(num1/den, num2/den));
  }

  def void show() {
    Print(re); Print(" +I["); Print(im); Print("]");
  }
  def void showln() {
    this.show(); Ln();
  }
}

\end{verbatim}
\verb! a = Complex.new2(1,3); ! \\
\verb! a: ! \\
1 +I[3]  \\
\verb! a*a: ! \\
-8 +I[6]  \\



\subsection{Interactive distributed computing}

The plugin modules file2, cmo, socket and the package file
{\tt ox.sm1} provide functions for 
interactive distributed computing.
To install these plugin modules, compile {\tt sm1} after modifying 
{\tt kan/Makefile}.
See {\tt README} for details.
These plugins are already installed in the binary distributions of {\tt sm1}.
The sm1 server {\tt ox\_sm1} and {\tt ox} which are complient to the Open XM
protocol
(see \cite{openxxx})
is distributed from the same ftp cite with {\tt sm1}.
The sm1 server is also a stack machine.
Here is an example input of server and client computation.

\noindent Server:
\begin{verbatim}
     ./ox -ox ox_sm1 -data 1300 -control 1200 
\end{verbatim}

\noindent Client:
\begin{verbatim}
(ox.sm1) run
[(localhost) 1300 1200] oxconnect /oxserver set
/f (123).. def ;
oxserver f oxsendcmo ;     %% send the data f to the server
oxserver f oxsendcmo ;     %% send the data f to the server
oxserver (power) oxexec ;  %% execute f f power
oxserver oxpopcmo ::       %% get data from the server.
\end{verbatim}
The output is $123^{123}$ and equal to
$114374367....9267$.


\noindent
Exercise:
write a graphical interface for functions in packages of {\tt sm1} by Java
and call sm1 server to execute them.

\subsection{More exercises}

\begin{enumerate}
\item \kansm contains the GNU MP package for computations of bignumbers.
You can call the functions in GNU MP by the operator {\tt mpzext}.
Write a program to find integral solution $(x,y)$ of
$ a x + b y = d$ for given integers $a, b, d$.
\item Write a program for RSA encryption.
\end{enumerate}

\begin{thebibliography}{99}
\bibitem{asir} Risa/Asir --- computer algebra system, \hfill\break
{\tt ftp://endaevor.fujitsu.co.jp/pub/isis/asir}.
\bibitem{Postscript} PostScript --- Language Turorial and Cookbook,
(1985), Addison-Wesley
\bibitem{Hotta} R.Hotta, Introduction to Algebra, Asakura-shoten, Tokyo
(in Japanese).
\bibitem{Oaku} T.Oaku, 
Gr\"obner basis and systems of differential equations,
(1994) Seminor note series of Sophia University.
(in Japanese).
\bibitem{SST}
M.Saito, B.Sturmfels, N.Takayama,
Gr\"obner deformations of hypergeometric differential equations,
to appear from Springer.
\bibitem{www} {\tt http://www.math.kobe-u.ac.jp/KAN} and \hfill\break
{\tt http://www.math.kobe-u.ac.jp/$\tilde{\ }$taka}
\bibitem{openxxx}
{\tt http://www.math.kobe-u.ac.jp/openxxx}
\end{thebibliography}

\end{document}