About The Contest

The first ever Olympiad of Misguided Geeks contest at Worse Than Failure (or OMGWTF for short) is a new kind of programming contest. Readers are invited to be creative with devising a calculator with the craziest code they can write. One lucky and potentially insane winner will get either a brand new MacBook Pro or comparable Sony VAIO laptop.

Navigation

Advertisements

Entry #100281: NQAPLPCOLPISC

by Todd Neal
NQAPLPCOLPISC: The N-Queen, Arbitrary Precision, Lexing, Parsing,
Compiling, Optimizing, Lexing, Parsing, Interpreting,
Simulating, Calculator

=======================================================================
Contents
=======================================================================

1) Compilation
2) Major WTFs
3) File Listing
4) Sequence of Events for Execution of "1+1"
5) Assembly and walkthrough for "9*9 + 2*2"
6) Internal Represenation of "123"
7) Future Direction: Adding Exponentation
8) Limitations
9) Notable Features

=======================================================================
1) Compilation
=======================================================================
- Run "make"
- Run "make run" to run the calculator (This adds
LD_LIBRARY_PATH=/usr/X11R6/lib so it should run on a clean NetBSD
install)

Hint: Be sure to click a button when a little dude err "busy
indicator" is standing on it, it causes him to fall to the
button below. When the "busy indicator" stands still/and or
hovers the calculator is busy. You can also click on their
heads to pick them up and move them.

=======================================================================
2) Major WTFs
=======================================================================

* Gui is written in pure Xlib

* ...using only arcs,lines, and rects

* ...and only means "only" (Who needs fonts? Check out Util.h)

* Hand implemented lexer and recursive descent parser for arithmetic
expressions which handles order of operations (eg. 1+2*3 = 7 not 9)

* Arithmetic expressions are compiled to assembly for a non-existent
CPU

* This assembly is then optimized with a peephole optimizer

* Since the CPU doesn't exist we need an emulator for it, so the
emulator is provided in a lispy language (source in CPU.cpp)

* Since gcc unfortunately doesn't provide a frontend for "Todd's made
up on the fly lispy language" another hand written lexer/parser and
interpreter is included to parse the CPU simulator in "lispy" which
is running the assembly code generated by the first optimizing compiler.

* So a C++ Lispy Interpreter runs a "lispy" program which is emulating a
CPU which is running an assembly equivalent of the users arithmetic
expression.

* Both Lexers/Parsers are pretty awful, with the "lispy" parser being
particularly bad

* Lispy language represents numbers as arbitrary precision floating
points, which in turn means that the CPU is simulated using
arbitrary precision floating points.

* Arbitrary precision library stores digits internally as NxN
chessboards with N queens placed on them (A single solution to an
N-queen problem, see Sec. 6)
* AP lib has not been tested much beyond the test cases, doing things
with negative numbers and negative floating point numbers in
particular is incredibly untested

* Progress indicator consists of two little dudes that run around the
calculator jumping from button to button and a pair of scissors, per
Jake Vinson's comment "If any readers manage to pull off a UI like
this for the OMGWTF contest, I'll be impressed." at
http://worsethanfailure.com/Articles/Innovative-Calculator-UI.aspx

=======================================================================
3) File Listing
=======================================================================

- Arithmetic Expression Optimizing Compiler
ASTNode.h - Abstract Syntax Tree Node for the Arithmetic Expression Parser
ExprNode.h - Expr node for Arithmetic AST
FactorNode.h - Factor node for Arithmetic AST
Lexer.h - Lexer
Lexer.cpp
Parser.h - Recursive Descent Parser
Parser.cpp
Optimizer.h - Peephole Optimizer
Token.h - Token class used by the Lexer
TermNode.h
Token.cpp


- "Lispy Language" Interpreter
LLexer.h - Lexer
LLexer.cpp
LParser.h - Parser
LParser.cpp
LToken.h - Token used by Lexer
LExprNode.h
LASTNode.h - Abstract Syntax Tree Node for the "Lispy Language" Parser
Result.h - Used for storing results of LASTNode::eval()
SymTable.h - Symbol Table for Interpreter


- CPU Instruction Definitions and Simulator
CPU.h - CPU Instruction Definition
CPU.cpp - CPU Instruction Printing and CPU Simulator in "Lispy Language"


- Misc/Gui
main.cpp
Button.h - Button Implementation in pure Xlib
Util.h
XL.h - Wrapper to make Xlib slightly nicer
XL.cpp

- Arbitrary Precision Math
APMath.h - AP Math Library
APMath.cpp
NQueen.h - NQueen type that acts as an integer, but stores the integer
internally as an NxN chessboard with N queens
NQueen.cpp

=======================================================================
4) Sequence of Events for Execution of "1+1"
=======================================================================

1) User enters "1+1" and hits the "=" key

2) Using a hand written lexer,parser, and peephole optimizer we
produce the following Assembly instructions for a non-existent CPU:

Ld 1 B
Ld 1 A
Add A B

3) This is then converted into a setf statement that sets a variable
called "code" to a list containing lists of the instructions like
this:
(setf code (list
(list ld 1.000000 B )
(list ld 1.000000 A )
(list add A B )
))

4) Finally this is inserted into the middle of our lispy CPU emulator
resulting in this set of instructions:


(setf add 0) ; Initial Constants Setup
(setf sub 1)
(setf mul 2)
(setf div 3)
(setf mov 4)
(setf ld 5)
(setf areg 0) ; Initialize our registers
(setf breg 0)
(setf creg 0)
(setf dreg 0)
(setf ereg 0)
(setf A 0) ; More constants
(setf B 1)
(setf C 2)
(setf D 3)
(setf E 4)
(setf code (list ; Assembly that we want to run
(list ld 1.000000 B)
(list ld 1.000000 A)
(list add A B)))

(dotimes i (len code)
(setf inst (nth i code)) ; Save our instruction
(if (eq (nth 0 inst) ld) ; Handle ld instructions
(dotimes n 1 (if (eq (nth 2 inst) A)
(setf areg (nth 1 inst)))
(if (eq (nth 2 inst) B)
(setf breg (nth 1 inst)))
(if (eq (nth 2 inst) C)
(setf creg (nth 1 inst)))
(if (eq (nth 2 inst) D)
(setf dreg (nth 1 inst)))
(if (eq (nth 2 inst) E)
(setf ereg (nth 1 inst)))))

(if (eq (nth 0 inst) mov) ; Handle mov instructions
(dotimes n 1 (if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) B)
(setf breg areg)))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) C)
(setf creg areg)))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) D)
(setf dreg areg)))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) E)
(setf ereg areg)))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) A)
(setf areg breg)))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) C)
(setf creg breg)))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) D)
(setf dreg breg)))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) E)
(setf ereg breg)))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) B)
(setf breg creg)))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) A)
(setf areg creg)))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) D)
(setf dreg creg)))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) E)
(setf ereg creg)))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) B)
(setf breg dreg)))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) C)
(setf creg dreg)))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) A)
(setf areg dreg)))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) E)
(setf ereg dreg)))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) B)
(setf breg ereg)))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) C)
(setf creg ereg)))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) A)
(setf areg ereg)))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) D)
(setf dreg ereg)))))


(if (eq (nth 0 inst) mul) ; Handle multiply instructions
(dotimes n 1 (if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) B)
(setf areg (* breg areg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) C)
(setf areg (* creg areg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) D)
(setf areg (* dreg areg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) E)
(setf areg (* ereg areg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) A)
(setf breg (* areg breg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) C)
(setf breg (* creg breg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) D)
(setf breg (* dreg breg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) E)
(setf breg (* ereg breg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) B)
(setf creg (* breg creg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) A)
(setf creg (* areg creg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) D)
(setf creg (* dreg creg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) E)
(setf creg (* ereg creg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) B)
(setf dreg (* breg dreg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) C)
(setf dreg (* creg dreg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) A)
(setf dreg (* areg dreg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) E)
(setf dreg (* ereg dreg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) B)
(setf ereg (* breg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) C)
(setf ereg (* creg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) A)
(setf ereg (* areg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) D)
(setf ereg (* dreg ereg))))))

(if (eq (nth 0 inst) ; Handle add instructions
add)
(dotimes n 1 (if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) B)
(setf areg (+ breg areg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) C)
(setf areg (+ creg areg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) D)
(setf areg (+ dreg areg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) E)
(setf areg (+ ereg areg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) A)
(setf breg (+ areg breg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) C)
(setf breg (+ creg breg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) D)
(setf breg (+ dreg breg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) E)
(setf breg (+ ereg breg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) B)
(setf creg (+ breg creg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) A)
(setf creg (+ areg creg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) D)
(setf creg (+ dreg creg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) E)
(setf creg (+ ereg creg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) B)
(setf dreg (+ breg dreg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) C)
(setf dreg (+ creg dreg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) A)
(setf dreg (+ areg dreg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) E)
(setf dreg (+ ereg dreg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) B)
(setf ereg (+ breg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) C)
(setf ereg (+ creg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) A)
(setf ereg (+ areg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) D)
(setf ereg (+ dreg ereg))))))

(if (eq (nth 0 inst) ; Handle sub instructions
sub)
(dotimes n 1 (if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) B)
(setf areg (- areg breg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) C)
(setf areg (- areg creg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) D)
(setf areg (- areg dreg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) E)
(setf areg (- areg ereg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) A)
(setf breg (- breg areg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) C)
(setf breg (- breg creg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) D)
(setf breg (- breg dreg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) E)
(setf breg (- breg ereg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) B)
(setf creg (- creg breg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) A)
(setf creg (- creg areg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) D)
(setf creg (- creg dreg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) E)
(setf creg (- creg ereg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) B)
(setf dreg (- dreg breg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) C)
(setf dreg (- dreg creg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) A)
(setf dreg (- dreg areg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) E)
(setf dreg (- dreg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) B)
(setf ereg (- ereg breg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) C)
(setf ereg (- ereg creg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) A)
(setf ereg (- ereg areg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) D)
(setf ereg (- ereg dreg))))))


(if (eq (nth 0 inst) ; Handle div instructions
div)
(dotimes n 1 (if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) B)
(setf areg (/ areg breg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) C)
(setf areg (/ areg creg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) D)
(setf areg (/ areg dreg))))
(if (eq (nth 1 inst)
A)
(if (eq (nth 2 inst) E)
(setf areg (/ areg ereg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) A)
(setf breg (/ breg areg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) C)
(setf breg (/ breg creg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) D)
(setf breg (/ breg dreg))))
(if (eq (nth 1 inst)
B)
(if (eq (nth 2 inst) E)
(setf breg (/ breg ereg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) B)
(setf creg (/ creg breg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) A)
(setf creg (/ creg areg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) D)
(setf creg (/ creg dreg))))
(if (eq (nth 1 inst)
C)
(if (eq (nth 2 inst) E)
(setf creg (/ creg ereg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) B)
(setf dreg (/ dreg breg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) C)
(setf dreg (/ dreg creg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) A)
(setf dreg (/ dreg areg))))
(if (eq (nth 1 inst)
D)
(if (eq (nth 2 inst) E)
(setf dreg (/ dreg ereg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) B)
(setf ereg (/ ereg breg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) C)
(setf ereg (/ ereg creg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) A)
(setf ereg (/ ereg areg))))
(if (eq (nth 1 inst)
E)
(if (eq (nth 2 inst) D)
(setf ereg (/ ereg dreg)))))))
(print areg) ; Finally print the result


5) Finally this CPU emulator is parsed and interpreted by another hand
written lexer/parser combo. The last statement is "(print areg)" which
besides printing the contents of areg to the console also returns
the result of areg, the a register where the final solution is.

6) We then convert this result to a string and display it to the user.


=======================================================================
5) Assembly and walkthrough for "9*9 + 2*2"
=======================================================================
The below is in the format

Instruction ; Registers after instruction execution

Ld 2 D ; [A 0] [B 0] [C 0] [D 2] [E 0]
Ld 2 A ; [A 2] [B 0] [C 0] [D 2] [E 0]
Mul A D ; [A 4] [B 0] [C 0] [D 2] [E 0]
Mov A B ; [A 4] [B 4] [C 0] [D 2] [E 0]
Ld 9 C ; [A 2] [B 4] [C 9] [D 2] [E 0]
Ld 9 A ; [A 9] [B 4] [C 9] [D 2] [E 0]
Mul A C ; [A 81] [B 4] [C 9] [D 2] [E 0]
Add A B ; [A 85] [B 4] [C 9] [D 2] [E 0]



=======================================================================
6) Internal Represenation of "123"
=======================================================================

Digits of the arbitrary precision number are stored internally as
solved (if the solution exists) N-Queen problems, where n is the ASCII
character code of the digit and the size of the chessboard.

123 = 49 50 51 in ASCII, so it is represented by a 49x49 board with 49
queens, a 50x50 board with 50 queens, and a 51x51 board with 51
queens. Below is an textual representation of the internal format of "123"

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q
_ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q
Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _

=======================================================================
7) Future Direction: Adding Exponentation
=======================================================================

If one were to add Exponentation to the calculator you would need to:

1) Modify Lexer/Parser to support the exponentiation operator. The
parser would be more difficult as exponentiation is right associative
and all other operators currently implemented are left associative.

2) Either add a new exponentiation operation to the CPU and modify
the AST walking code to emit it as needed, or add branching/conditional
opcodes to the CPU and implement exponentiation in ASM instead of as
a new operation.

3) If you add the operation to the CPU you will need to modify the
lispy CPU simulator so that it can evaluate the opcode. This may
require adding new constructs to the lispy language, if so you'll
need to modify the lispy interpeter as well.

If you implemented the operation in ASM with the compiler, then you
would have needed to add some other new operations for
branching/conditional expressions to the CPU which also requires
modifying the CPU simulator (written in lispy) and possibly also the
interpreter depending on if you need things like "functions" in lispy.

4) If you added an exponentiation operation to the CPU and thus the
CPU simulator, then you'll also need to add exponentiation to the
arbitrary precision library. Try to do this without using division,
as doing a divide turns the arbitrary precision divisor into a
double. (This is necessary as otherwise division is rediculously
slow, who would have thought representing integer digits as chess
boards would have caused any problems?)

=======================================================================
8) Limitations
=======================================================================

- The CPU only has 5 registers and no memory, so if your AST gets too
deep (using too many operands) you will run out of registers to
store temporaries and get an invalid result. This can be detected
by double checking your calculation on paper. Adding memory to the
lispy simulator and new opcodes to the CPU's instruction set to
access this memory is left as an exercise for the reader.

- All of the lexers/parsers are "finicky". Any changes to grammars
will need to be done very carefully.

- Lispy Language parser indicates failure to parse/execute by
crashing. Note: The calculator only outputs valid lispy code so this
is a minor limitation.

- Lispy variables all share the same scope and never go out of scope
once defined.

- Both parsers leak their AST Nodes, it is recommended that the user
reboot the calculator occasionally.


=======================================================================
9) Notable Features
=======================================================================

- Knows about operator precedence:
- 1+2*3 = 7
- 1-2/3 = 0.3333333...
- 1/4+3/4 = 1

- Full answer to ~49 decimal digits displays in the console

Compiled 1/7 to 4 instructions.
......
Lispy Code is (setf code (list
(list ld 7.000000 C )
(list ld 1.000000 A )
(list div A C )
))

Lispy Lexer...
Lispy Interpeter evaluating assembly with simulated CPU (written in lispy)...
Print: 0.1428571428571428571428571428571428571428571428571

- Arbitrary Precision Multiplication/Addition/Subtraction algorithms
are the classical algorithms from Knuth's TAOCP.

- NQueen class implements it's own sqrt function.

Download0 Comments