Quaternion Calculator
Introduction
The aim of this project is to construct a quaternion calculator using flex and yacc. Flex is a lexical analyzer that uses regular expressions. We use flex to match the elements of our language, quaternions, and pass these tokens to yacc. Yacc, Yet Another Compiler Compiler, parses context free grammars. We use yacc to evaluate the expression matched by flex.
Languages
We start with a set of characters $\sum$, which we call the alphabet. Then the set of all string concatenations is denoted as $\sum^*$, the universal language. A language is a subset of $\sum^*$.
Regular Languages
A language, $L$, is regular if it can be matched by a regular expression. We define a regular expression inductively as follows,
If $r \in L$, then $r$ is a regular expression (the empty string $\varepsilon$ and the empty set $\emptyset$ are also regular expressions)
Let $R, Q$ be regular expressions, then
$R \cup Q$, which means $R$ or $Q$
$(R)$
$R^*$, the Kleene star, which means $R$ concatenated with itself an arbitrary number of times
$RQ$, which means the concatenation of $R$ and $Q$
are regular expressions. For example, any finite language is regular as listing out all elements of the language separated by the or operator $\cup$ is a regular expression for the language.
Another example, let’s use the alphabet ${ a, b}$ and the regular expression $(aa \cup bb)^*$. The empty string is matched by this regular expression as we can concatenate $(aa \cup bb)$ 0 times. The string bbbbaa is matched by the regular expression as we can concatenate $(aa \cup bb)$ 3 times, pick bb on the first two and aa in the last one.
Context Free Languages
A language, $L$, is context free if it can be generated by a context free grammar. A context free grammar consists of production rules over a the alphabet and another set called the non terminals. The elements of the alphabet are called the terminals and usually denoted as lowercase, while terminals are usually denoted as uppercase. A production rule consists of a nonterminal on the LHS which produces the string of terminals and non terminals on the RHS, for example
\[X \to aXY\]To generate a string, we start with the nonterminal $S$ and finish when there are no more non terminals. For example, the language even-even over the alphabet ${a,b}$, which can be denoted by the set ${ a^n b^n \ | \ n \in \mathbb{N} }$, is generated by the context free grammar,
\[\begin{align} S &\to ASB \tag{1} \\ S &\to \varepsilon \tag {2} \\ A &\to a \tag{3} \\ B &\to b \tag{4} \end{align}\]We can generate aabb as follows, starting with the non terminal S \(\begin{align*} S &\to ASB \tag{Rule 1} \\ &\to AASBB \tag{Rule 1} \\ &\to AA\varepsilon BB \tag{Rule 2} \\ &\to aabb \tag{Rule 3, 4} \end{align*}\)
It turns out this language cannot be generated by any regular expression.
Quaternions
A quaternion is a number of the form \(w + x \mathbf{i} + y \mathbf{j} + z \mathbf{k}\) where $w,x,y,z \in \mathbb{R}$ and $\mathbf{i},\mathbf{j},\mathbf{k}$ are the quaternion units, satisfying
\[\begin{align*} \mathbf{i}^2 &= -1 \\ \mathbf{j}^2 &= -1 \\ \mathbf{k}^2 &= -1 \\ \mathbf{i}\mathbf{j}\mathbf{k} &= -1 \end{align*}\]The quaternions can be constructed rigorously using Clifford Algebras, but that is beyond the scope of this project. Along with the usual operations of addition, subtraction, multiplication and division, we also have the operation of rotation. Rotation(r, q)*p/Rotation(r,q) represents a rotation of the point p around the axis of rotation given by q by r radians.
\[\text{Rotation}(r, q) = \cos(r/2) + \sin(r/2) \hat{q}\]where $\hat{q}$ is the unit vector in the direction of $q$. It is not obvious that Rotation($r,q$) has this effect on $p$, this lesson by Grant Sanderson gives an explanation and intuition behind this formula.
Now we make precise what a quaternion expression is with the following inductive definition,
- $\mathbf{i},\mathbf{j},\mathbf{k}$ are quaternion expression
- If $r$ is a real number, then $r$, $r\mathbf{i}$, $r\mathbf{j}$, $r\mathbf{k}$ are quaternion expressions
- If $p$ and $q$ are quaternion expressions, then so are: $(q)$, $-q$, $p + q$, $p-q$, $p*q$, $p/q$
- If $q$ is a quaternion expression and $n$ is an natural number, then $q^n$ is a quaternion expression.
- If $r$ is a NUMBER and $q$ is a quaternion expression, then Rotation($r,q$) is a quaternion expression.
Flex
Now that we have regular expressions and context free grammars, we build the flex file to recognize the elements of the language quaternion. We will only consider numbers in their finite decimal representations or integers.
The following regular expression matches any non negative integer,
1
(0|[1-9][0-9]*)
and the corresponding language recognized by the expression as WHOLENUMBER. The following regular expression matches any non negative number in a finite decimal representation
1
([1-9][0-9]*\.[0-9][0-9]*|0\.[0-9][0-9]*)
and the corresponding language recognized by the expression as NUMBER. These two expressions along with a rule for operations and one for whitespace make up the flex file. For example the rule for NUMBER is as follows,
1
2
3
4
5
6
7
([1-9][0-9]*\.[0-9][0-9]*|0\.[0-9][0-9]*) {
/*
printf("Token: NUMBER; Lexeme: %s\n", yytext);
*/
yylval.num = atof(yytext);
return NUMBER;
}
Yacc
Converting the inductive definition for the langage QUATERNION of quaternion expressions to a context free grammar over the alphabet \(\{ \mathbf{i}, \mathbf{j}, \mathbf{k}, +, −, ∗, /, ˆ, (, ), \text{NUMBER}, \text{WHOLENUMBER}, \text{ROTATION}, \mathbf{,} \}\),
\[\begin{align*} S &\rightarrow Q \\ Q &\rightarrow (Q) \ | -Q \ | \ Q + Q \ | \ Q - Q \ | \ Q * Q \ | \ Q \backslash Q \\ Q &\rightarrow Q \text{^WHOLENUMER} \ | \ \text{ROTATION} (R, Q) \\ Q &\rightarrow R \ | \ E \ | \ R E \\ R &\rightarrow \text{WHOLENUMBER} \ | \ \text{NUMBER} \\ E &\rightarrow \mathbf{i} \ | \ \mathbf{j} \ | \ \mathbf{k} \end{align*}\]These are then used in the rules section of the yacc file to parse the file, taking the form, \(\it{pattern} \qquad \{ \ \ \ \it{action} \ \ \ \}\)
For example the rule $Q \to Q + Q$ becomes the rule,
1
expr : expr '+' expr { $$ = sum($1, $3); }
sum is a C function defined later in the yacc file as,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Quaternion sum(Quaternion q1, Quaternion q2)
/* returns the sum q1 + q2 of the quaternions q1 and q2.
This may be viewed as just a vector sum.
*/
{
Quaternion qsum;
qsum.w = q1.w + q2.w;
qsum.x = q1.x + q2.x;
qsum.y = q1.y + q2.y;
qsum.z = q1.z + q2.z;
return qsum;
}
Repeating this for the other production rules we obtain a rudimentary calculator.
Extension
The calculator works for simple operations, but there are a few issues. It can’t handle exponents that are quaternion expressions, the sqrt, log and exp functions are not defined, the return function prints zeros and +- instead of just -. There is also a computational error with juxtaposition, (3k)^2 is parsed as 3k^2.
We begin by making the return statements cleaner, we modify the simple print statement
1
return printf("%f + %f i + %f j + %f k\n", q.w, q.x, q.y, q.z);
to include if statements that check if the number is non zero, include a + or - sign depending on the parity of the number, and include the + sign if there are non zero number that occur before it. The final function is long, but the outputs are cleaner.
To fix the issue with juxtaposition, we replace the naive $Q \to Q\text{^WHOLENUMBER}$ production rule with the following set of rules,
1
2
3
4
5
power : '(' expr ')' '^' expr { $$ = QuatPower($2,$5); }
| real imag '^' expr { $$ = scalarTimesQuaternion($1, QuatPower($2,$4)); }
| imag '^' expr { $$ = QuatPower($1,$3); }
| real '^' expr { $$ = QuatPower(newQuaternion($1, 0, 0, 0), $3); }
;
Now for functions power, log, exp. To calculate the exponential, we use the Taylor Series for the exponential function. $q = w + x \mathbf{i} + y \mathbf{j} + z \mathbf{k} = w + \mathbf{v}$,
\[\begin{align} e^q = e^{w + \mathbf{v}} &= e^w \sum_{n = 0}^{\infty} \frac{\mathbf{v}^n}{n!} \\ &= e^w \bigg( \sum_{n = 0}^{\infty} \frac{\mathbf{v}^{2n}}{(2n)!} + \frac{\mathbf{v}^{2n+1}}{(2n+1)! }\bigg) \\ &= e^w \bigg( \sum_{n = 0}^{\infty} \frac{||\mathbf{v}||^{2n} \hat{\mathbf{v}}^{2n}}{(2n)!} + \frac{||\mathbf{v}||^{2n + 1}\hat{\mathbf{v}}^{2n+1}}{(2n + 1)! }\bigg) \\ &= e^w \bigg( \sum_{n = 0}^{\infty} \frac{(-1)^n ||\mathbf{v}||^{2n}}{(2n)!} + \frac{\mathbf{v}}{||\mathbf{v}||}\frac{(-1)^n||\mathbf{v}||^{2n + 1}}{(2n + 1)! }\bigg) \\ &= e^w \bigg( \cos||\mathbf{v}|| + \frac{\mathbf{v}}{||\mathbf{v}||} \sin||\mathbf{v}|| \bigg) \end{align}\]Then we use the C math functions to calculate each of these quantities.
1
2
3
4
5
6
7
8
9
10
11
Quaternion QuatExp(Quaternion p)
/* returns e^p. */
{
if (norm(imaginaryPart(p)) == 0){
return newQuaternion(exp(p.w), 0, 0, 0);
}
return scalarTimesQuaternion(exp(p.w),
sum(newQuaternion(cos(norm(imaginaryPart(p))), 0, 0, 0),
scalarTimesQuaternion(sin(norm(imaginaryPart(p))),
unitQuaternion(imaginaryPart(p)))));
}
Deriving the formula for the quaternion logarithm, let $w = s + \mathbf{v}$, where $s \in \mathbb{R}$ and $\mathbf{v}$ is a purely imaginary quaternion.
\[\ln(w) = \ln||w|| + \ln \bigg(\frac{s + \mathbf{v}}{||w||} \bigg)\]Let $\theta \in \mathbb{R}$ and $\mathbf{u}$ be a purely imaginary unit quaternion, using the exponential formula above,
\[e^{\theta \mathbf{u}} = \cos(\theta) + \mathbf{u} \sin(\theta)\]Therefore by definition,
\[\ln(\cos(\theta) + \mathbf{u} \sin(\theta)) = \theta \mathbf{u}\]Substituting $\theta = \arccos(\frac{s}{||w||})$,
\[\ln \bigg( \frac{s}{||w||} + \sqrt{1 - \frac{s^2}{||w||^2}} \mathbf{u} \bigg) = \mathbf{u} \arccos \bigg(\frac{s}{||w||} \bigg)\]Using Pythagoras’ Theorem,
\[||w|| = ||s + \mathbf{v}|| \Rightarrow ||w||^2 - s^2 = ||v||^2\] \[\ln \bigg( \frac{s + ||\mathbf{v}|| \mathbf{u}}{||w||} \bigg) = \mathbf{u} \arccos \bigg(\frac{s}{||w||} \bigg)\]Substituting $\mathbf{u} = \frac{\mathbf{v}}{||\mathbf{v}||}$, which is valid as $\mathbf{v}$ is a purely imaginary quaternion,
\[\ln \bigg( \frac{s + \mathbf{v}}{||w||} \bigg) = \frac{\mathbf{v}}{||\mathbf{v}||} \arccos \bigg(\frac{s}{||w||} \bigg)\]Therefore,
\[\ln(w) = \ln||w|| + \frac{\mathbf{v}}{||\mathbf{v}||} \arccos \bigg(\frac{s}{||w||} \bigg)\]The argument of the logarithm and inverse cosine are real so we can use C math functions to evaluate this formula,
1
2
3
4
5
6
7
8
9
10
11
Quaternion QuatLog(Quaternion p)
/* returns log(p). */
{
if (norm(imaginaryPart(p)) == 0){
return newQuaternion(log(p.w), 0, 0, 0);
}
return sum(newQuaternion(log(norm(p)), 0, 0, 0),
scalarTimesQuaternion(acos(p.w / norm(p)),
unitQuaternion(imaginaryPart(p))));
}
Finally we can use the logarithm and exponential functions to calculate powers of quaternions. By definition,
\[p^q = (e^{\ln(p)})^q = e^{q \ln(p)}\]where $p \neq 0$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Quaternion QuatPower(Quaternion p, Quaternion q)
/* returns p^q. */
{
if (norm(p) == 0){
if (norm(q) == 0){
return newQuaternion(1,0,0,0);
}
else{
return newQuaternion(0,0,0,0);
}
}
return QuatExp(product(q, QuatLog(p)));
}
To evaluate these expressions, we add rules to the lex file to recognize the functions,
1
2
3
4
5
6
7
(Log|Ln|log|ln) {
/*
printf("Token: LOG; Lexeme: %s\n", yytext);
*/
yylval.str = strdup(yytext);
return LOG;
}
This means we only need to write one production rule in the yacc file, and the calculator will recognize any of the above forms,
1
expr : LOG '(' expr ')' { $$ = QuatLog($3); }
If you would like to try out the calculator, an exe is available here Quat