Haskell Computer Algebra System HCAS Final Report Rob Tougher rt2301 columbia edu December 15 2007 1 Contents 1 Introduction 3 2 Language Tutorial 3 2 1 Command Line Usage 3 2 2 Hello World 4 3 Language Manual 6 3 1 Introduction 6 3 2 Top Level Structure 6 3 3 Expressions 7 3 3 1 Data Types 7 3 3 2 Expression Atoms 8 3 3 3 Boolean Operators 10 3 3 4 Math Operators 11 3 3 5 List Operators 11 3 3 6 Miscellaneous Expressions 12 Functions 12 3 4 1 Function Precedence 13 3 4 2 Applicative Order Argument Evaluation 14 Syntax Summary 14 3 4 3 5 4 Project Plan 15 2 5 Architectural Design 16 6 Test Plan 17 6 1 6 2 Example Scripts 17 6 1 1 Basics 17 6 1 2 Calculus Derivatives 19 6 1 3 Simplification 19 Unit Tests 20 7 Lessons Learned 21 8 Appendix Code Listing 21 8 1 AST hs 21 8 2 Parser hs 26 8 3 Interpreter hs 32 8 4 MainInterpreter hs 38 8 5 AllTests hs 39 3 1 Introduction For the class project I implemented a simple computer algebra system HCAS HCAS is a purely functional programming language that provides a set of basic operations for constructing and manipulating algebraic expressions Simply put you can think of HCAS as a subset of Haskell plus support for computer algebra HCAS has three main features Purely Functional Language HCAS is a purely functional subset of Haskell There are functions recursion lists strings pattern matches for function arguments etc No variables sequencing of operations or other items from imperative programming languages Construction of Mathematical Expressions HCAS allows you to construct mathematical expressions using an intuitive syntax You are able to define mathematical expressions inline That is if you write the expression x y z this is automatically constructed as a math expression Navigation of Mathematical Expressions HCAS uses the concept of pattern matching in function arguments to allow you to navigate mathematical expressions Consider the following simple function printType l e f t r i g h t Multiplication printType l e f t r i g h t Addition This function has two definitions one for addition and one for multiplication The version that gets executed at runtime is chosen based on the expression argument that you pass in So if you call the function as printType x y z the version for addition will be called because addition binds the loosest In the body of the function left refers to x y and right refers to z 2 2 1 Language Tutorial Command Line Usage One command line utility is shipped with this project hcasi the HCAS interpreter This utility uses standard input for the HCAS input and standard output for the program output 4 hcasi myscript hcas out txt 2 2 Hello World Every good language tutorial contains a few Hello World programs The following examples get you started You can run these using the following syntax echo main hcasi The simplest script is the following main Hello World An HCAS script contains one or more function declarations One of the functions must be named main and have no arguments When HCAS interprets your script it finds the main function evaluates it and then returns the result to standard output In the above example the main function returns the string Hello World HCAS allows you to perform basic math calculations like many other languages main 3 7 4 Here the script will return 31 All of the typical mathematical operations are supported including addition subtraction multiplication division and exponentiation HCAS also allows you to use lists main 1 2 3 4 5 In the above program main returns a list of numbers Like many of the current popular languages HCAS allows you to create user defined functions These functions can have zero or more arguments main foo 5 foo x x 7 5 5 Here main will return the number 12 5 You are allowed to create multiple definitions for a function You can give each of these definitions different patterns for its arguments HCAS chooses the function to call based on the arguments you pass to the call This is called pattern matching main foo x y foo left right This is addition foo left right This is subtraction foo x This is neither addition nor subtraction In the above example main will return This is addition because the addition expression x y is passed as the first argument to foo Besides math patterns you can also use list patterns main head 1 2 3 4 5 head x xs x In the above example x refers to the first item of the list and xs refers to the rest of the list The head function returns the first item of the list so our main function will return the number 1 You can also give literal values as patterns main foo hello foo hello Hi foo goodbye Bye Here the call to foo will match the function declaration that has the string hello which returns the string Hi Any literal values can be used in function declarations including numbers strings and lists The following is a simple example script that calculates the derivative for a math expression main derivative 3 x 2 2 x derivative a b derivative a b derivative c x e derivative c x derivative x 0 derivative a derivative b derivative a derivative b c e simplify x e 1 c 6 simplify x 1 simplify x 0 simplify x 0 simplify 0 x simplify x y simplify x y simplify x x x 1 x x simplify x simplify y simplify x simplify y If you run this with HCAS it should print out 6 x 2 3 3 1 Language Manual Introduction HCAS is a purely functional programming language that allows for the manipulation of mathematical expressions This section describes the language 3 2 Top Level Structure The top level of the HCAS grammar is the program A program is contained in a single source file A program has one or more functions as shown by the following grammar program function list function list function function function list Functions are separated in the file by one or more characters of whitespace Whitespace can either be a single space carriage return tab or comment Functions are typically declared on separate lines though they do not need to be A function declares a reusable parameterized expression It contains zero or more input expressions and a single output expression 7 function identifier expression list expression expression list expression expression expression list The identifier is the function s name and is how other expressions can call this function more on identifiers later The expression list specifies the list of input expressions for the function and are available to be used in the body of the output expression The parentheses and expression list are optional if no input
View Full Document
Unlocking...