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.