|
|
|
last edited 5 years ago by test1 |
Edit detail for TutorialIntroductionToFriCAS revision 1 of 1
| 1 | ||
|
Editor: test1
Time: 2019/07/20 21:00:29 GMT+0 |
||
| Note: | ||
changed: - <html><!---------------------------------------------------------------------------- Authors: M. Dunstan (mnd@uk.ac.st-andrews) {enter_new_authors_here} History: 2nd December 1995: Original version from LaTeX. (mnd) 2nd May, 1996: Alterations of my own and from suggestions by Mike Dewar (NAG). (mnd) {enter_major_changes_here} ----------------------------------------------------------------------------> <head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <title>A Tutorial Introduction To FriCAS</title> <link rev="made" href="mailto:mnd@dcs.st-andrews.ac.uk (Martin Dunstan)"> </head> <body> <hr> <center> <h1>An Introduction To Programming In</h1> <h1><img align="middle" alt="FriCAS" src="site_logo"></h1> </center> <hr> <center> <h1>By Martin N. Dunstan</h1> May 2, 1996 </center> <hr> <!------------------------------------------------------> <!-- Table of contents: use hyperlinks where possible --> <!------------------------------------------------------> <h2>Contents</h2> <ol> <li><a href="#introduction">Introduction</a></li> <li><a href="#pocket">Using <b>FriCAS</b> As A Pocket Calculator</a></li> <ol> <li><a href="#basicArith">Basic Arithmetic</a></li> <li><a href="#typeConversionA">Type Conversion</a></li> <li><a href="#usefulFunctions">Useful Functions</a></li> </ol> <li><a href="#symbolic">Using <b>FriCAS</b> As A Symbolic Calculator</a></li> <ol> <li><a href="#exprSymbols">Expressions Involving Symbols</a></li> <li><a href="#complexNumbers">Complex Numbers</a></li> <li><a href="#numberReps">Number Representations</a></li> <li><a href="#modularArith">Modular Arithmetic</a></li> </ol> <li><a href="#generalPoints">General Points About <b>FriCAS</b></a></li> <ol> <li><a href="#compNoOutput">Computation Without Output</a></li> <li><a href="#earlierResults">Accessing Earlier Result</a></li> <li><a href="#splittingExprs">Splitting Expressions Over Several Lines</a></li> <li><a href="#comments">Comments And Descriptions</a></li> <li><a href="#typeConversionB">Control Of Result Types</a></li> </ol> <li><a href="#data">Data Structures In <b>FriCAS</b></a></li> <ol> <li><a href="#lists">Lists</a></li> <li><a href="#segLists">Segmented Lists</a></li> <li><a href="#Streams">Streams</a></li> <li><a href="#arraysEtc">Arrays, Vectors, Strings and Bits</a></li> <li><a href="#flexibleArrays">Flexible Arrays</a></li> </ol> <li><a href="#functionsEtc">Functions, Choices And Loops</a></li> <ol> <li><a href="#readFromFile">Reading Code From A File</a></li> <li><a href="#Blocks">Blocks</a></li> <li><a href="#functions">Functions</a></li> <li><a href="#choices">Choices</a></li> <li><a href="#loops">Loops</a></li> <ol> <li><a href="#repeat">The repeat Loop</a></li> <li><a href="#while">The while Loop</a></li> <li><a href="#for">The for Loop</a></li> </ol> </ol> </ol> <hr> <!------------------------------------------------------------------------> <!------------------------------------------------------> <!-- List of figures: use hyperlinks where possible --> <!------------------------------------------------------> <h2>List Of Figures</h2> <blockquote> <dl compact=""> <dt>2.1</dt> <dd><a href="#figure2point1">Table of simple <b>FriCAS</b> functions.</a></dd> <dt>2.2</dt> <dd><a href="#figure2point2">Table of simple <b>FriCAS</b> operators.</a></dd> <dt>2.3</dt> <dd><a href="#figure2point3">Table of some useful <b>FriCAS</b> macros.</a></dd> <pre></pre> <dt>5.1</dt> <dd><a href="#figure5point1">List <em>u</em> before <tt>setrest(endOfu,partOfu)</tt>.</a></dd> <dt>5.2</dt> <dd><a href="#figure5point2">List <em>u</em> after <tt>setrest(endOfu,partOfu)</tt>.</a></dd> </dl> </blockquote> <hr> <!------------------------------------------------------------------------> <p></p> <a name="introduction"> <h2>Chapter 1</h2> <h2>Introduction</h2> </a> <p> This document is intended to be a tutorial introduction to the <b>FriCAS</b> (Release 1.3.5) system and its language. Initially the examples and discussion will relate to the interactive system and the use of input files will be touched on later. </p> <p> Although "FriCAS Book":http://fricas.github.io/book.pdf (updated version of <a href="#jenks1992">[jenks1992]</a>) is an extremely useful book for those wanting to use the <b>FriCAS</b> system it is not quite so helpful for learning to program in <b>FriCAS</b>. Generally one learns a new programming language by writing short programs ("one-liners") before learning about the various flow-control instructions such as <tt>if</tt> and <tt>while</tt>. However, learning to use a large system such as <b>FriCAS</b> requires a text that covers a significant part of the available features while keeping the number of pages to a minimum as FriCAS Book does. This is not to say that FriCAS Book does not explain how to program in <b>FriCAS</b> since this is how the author learned! </p> <p> As a result the author has decided to produce this text as an introduction to the <b>FriCAS</b> language for readers who are already familiar with at least one programming language. Knowledge of a functional programming language would be a benefit since many of the concepts found in functional languages are present in <b>FriCAS</b> but is by no means essential. <b>FriCAS</b> is <em>not</em> a functional language since it has a notion of state and functions can (and sometimes do) have side-effects. </p> <p> This document has been compiled by working through <a href="#jenks1992">[jenks1992]</a> in parallel with interactive sessions of <b>FriCAS</b> (a new session is started for each chapter). The structure of the text is the author's but the majority of the information has come from <a href="#jenks1992">[jenks1992]</a> in some form or another since this appears to be the only large body of information on <b>FriCAS</b> (apart from the HyperDoc program). However, the examples are mostly of the author's own design and are all extracted directly from the output produced by <b>FriCAS</b> - the code for each example was copied from the <b>LaTeX</b> version of this document into the <b>FriCAS</b> interpreter and the results copied back. As a result there shouldn't be any mistakes. </p> <hr> <blockquote> Please let me (<b><tt><a href="mailto:mnd@dcs.st-andrews.ac.uk">mnd@dcs.st-andrews.ac.uk</a></tt></b>) know of any errors or any comments/criticisms you have regarding this document as I would like to make it as useful as possible. </blockquote> <hr> <!------------------------------------------------------------------------> <p></p> <a name="pocket"> <h2>Chapter 2</h2> <h2>Using <b>FriCAS</b> As A Pocket Calculator</h2> </a> <p> At the simplest level <b>FriCAS</b> can be used as a pocket calculator where expressions involving numbers and operators are entered directly in infix notation. In this sense the more advanced features of the calculator can be regarded as operators (e.g. <b>sin</b>, <b>cos</b> etc.). </p> <!------------------------------------------------------------------------> <p></p> <a name="basicArith"> <h3>2.1 Basic Arithmetic</h3> </a> <p> An example of this might be to calculate the cosine of 2.45 (in radians). To do this one would type: </p> <pre> (1) -> cos 2.45 (1) -0.7702312540 473073417 Type: Float </pre> <p> Before proceeding any further it would be best to explain the previous three lines. Firstly the text ``<tt>(1) -> </tt>'' is part of the prompt that the <b>FriCAS</b> system provides when in interactive mode. The full prompt probably has other text preceding this but it is not relevent here. The number in parenthesis is the step number of the input which may be used to refer to the <em>results</em> of previous calculations. The step number appears at the start of the second line to tell you which step the result belongs to. Since the interpreter probably loaded numerous libraries to calculate the result given above and listed each one in the process, there could easily be several pages of text between your input and the answer. </p> <p> The last line contains the type of the result. The type <b>Float</b> is used to represent real numbers of arbitrary size and precision (where the user is able to define how big arbitrary is - the default is 20 digits but can be as large as your computer system can handle). The type of the result can help track down mistakes in your input if you don't get the answer you expected. </p> <p> Other arithmetic operations such as addition, subtraction, multiplication behave as expected: </p> <pre> (2) -> 6.93 * 4.1328 (2) 28.640304 Type: Float (3) -> 6.93 / 4.1328 (3) 1.6768292682 926829268 Type: Float </pre> <p> but integer division isn't quite so obvious. For example, if one types: </p> <pre> (4) -> 4/6 2 (4) - 3 Type: Fraction Integer </pre> <p> a fractional result is obtained. The function used to display fractions attempts to produce the most readable answer. In the example: </p> <pre> (5) -> 4/2 (5) 2 Type: Fraction Integer </pre> <p> the result is stored as the faction 2/1 but is displayed as the integer 2. This fraction could be converted to type <b>Integer</b> with no loss of information but <b>FriCAS</b> will not do so automatically. </p> <!------------------------------------------------------------------------> <p></p> <a name="typeConversionA"> <h3>2.2 Type Conversion</h3> </a> <p> To obtain the floating point value of a fraction one must convert (according to the documentation, <em>coercions</em> are conversions that are automatically applied by the kernel) it to type <b>Float</b> using the ``<tt>::</tt>'' operator (see <a href="#typeConversionB">Section 4.5</a>) as follows (the parentheses are required due to the relative precedences of ``<tt>::</tt>'' and ``<tt>/</tt>''): </p> <pre> (6) -> (4/6) :: Float (6) 0.6666666666 6666666667 Type: Float </pre> <p> Although <b>FriCAS</b> can convert this back to a fraction it might not be the same fraction it started as due to rounding errors. For example, the following conversion appears to be without error but others might not: </p> <pre> (7) -> % :: Fraction Integer 2 (7) - 3 Type: Fraction Integer </pre> <p> where ``<tt>%</tt>'' represents the previous <em>result</em> (not the calculation). </p> <p> Although <b>FriCAS</b> has the ability to work with floating-point numbers to very high precision it must be remembered that calculations with these numbers are <em>not</em> exact. Since <b>FriCAS</b> is a computer algebra package and not a numerical solutions package this should not create too many problems. The idea is that the user should use <b>FriCAS</b> to do all the necessary symbolic manipulation and only at the end should actual numerical results be extracted. </p> <p> If you bear in mind that <b>FriCAS</b> appears to store expressions just as you have typed them and does not perform any evaluation of them unless forced to then programming in the system will be much easier. It means that anything you ask <b>FriCAS</b> to do (within reason) will be carried with complete accuracy. </p> <p> In the previous examples the ``<tt>::</tt>'' operator was used to convert values from one type to another. This type conversion is not possible for all values for instance, it is not possible to convert the number 3.4 to an integer type since it can't be represented as an integer. The number 4.0 however can be converted to an integer type since it has no fractional part. Refer to <a href="#typeConversionB">Section 4.5</a>) for more details on type conversion. </p> <p> Conversion from floating point values to integers is performed using the functions <b>round</b> and <b>truncate</b>. The first of these rounds a floating point number to the nearest integer while the other truncates i.e. removes the fractional part. Both functions return the result as a <em>floating point</em> number. To extract the fractional part of a floating point number use the function <b>fractionPart</b> but note that the sign of the result depends on the sign of the argument (<b>FriCAS</b> obtains the fractional part of ``<tt>x</tt>'' using ``<tt>x - truncate x</tt>''): </p> <pre> (8) -> round(3.77623) (8) 4.0 Type: Float (9) -> round(-3.77623) (9) -4.0 Type: Float (10) -> truncate(9.235) (10) 9.0 Type: Float (11) -> truncate(-9.654) (11) -9.0 Type: Float (12) -> fractionPart(-3.77623) (12) -0.77623 Type: Float </pre> <!------------------------------------------------------------------------> <p></p> <a name="usefulFunctions"> <h3>2.3 Useful Functions</h3> </a> <p> To obtain the absolute value of a number the <b>abs</b> function can be used. This takes a single argument which is usually an integer or a floating point value but doesn't necessarily have to be. The sign of a value can be obtained via the <b>sign</b> function which returns -1, 0, or 1 depending on the sign of the argument: </p> <pre> (13) -> abs(4) (13) 4 Type: PositiveInteger (14) -> abs(-3) (14) 3 Type: PositiveInteger (15) -> abs(-34254.12314) (15) 34254.12314 Type: Float (16) -> sign(-49543.2345346) (16) -1 Type: Integer (17) -> sign(0) (17) 0 Type: NonNegativeInteger (18) -> sign(234235.42354) (18) 1 Type: PositiveInteger </pre> <p> Tests on values can be done using using various functions which are generally more efficient than using relational operators such as ``<tt>=</tt>'' particularly if the value is a matrix. Examples of some of these functions are: </p> <pre> (19) -> positive?(-234) (19) false Type: Boolean (20) -> negative?(-234) (20) true Type: Boolean (21) -> zero?(42) (21) false Type: Boolean (22) -> one?(1) (22) true Type: Boolean (23) -> odd?(23) (23) true Type: Boolean (24) -> odd?(9.435) (24) false Type: Boolean (25) -> even?(-42) (25) true Type: Boolean (26) -> prime?(37) (26) true Type: Boolean (27) -> prime?(-37) (27) false Type: Boolean </pre> <p> Some other functions that are quite useful for manipulating numerical values are shown in <a href="#figure2point1">Figure 2.1</a> while <a href="#figure2point2">Figure 2.2</a> contains a table of simple infix and prefix operators. <a href="#figure2point3">Figure 2.3</a> is a table of predefined macros that can be used in various situations. </p> <a name="figure2point1"> <pre> +---------------+------------------------------------+ | Function | Operation | +---------------+------------------------------------+ | sin(x) | Sine of x | | cos(x) | Cosine of x | | tan(x) | Tangent of x | | asin(x) | Arcsin of x | | acos(x) | Arccos of x | | atan(x) | Arctangent of x | | gcd(x,y) | Greatest common divisor of x and y | | lcm(x,y) | Lowest common multiple of x and y | | max(x,y) | Maximum of x and y | | min(x,y) | Minimum of x and y | | factorial(x) | Factorial of x | | factor(x) | Prime factors of x | | divide(x,y) | Quotient and remainder of x/y | +---------------+------------------------------------+ Figure 2.1: Table of simple FriCAS functions. </pre> </a> <a name="figure2point2"> <pre> +--------+--------------------+--------+------------------+ | Symbol | Operation | Symbol | Operation | +--------+--------------------+--------+------------------+ | + | Addition | - | Subtraction | | - | Numerical Negation | ~ | Logical Negation | | /\ | Conjunction (AND) | \/ | Disjunction (OR) | | and | Logical AND (/\) | or | Logical OR (\/) | | not | Logical Negation | ^ | Exponentiation | | * | Multiplication | / | Division | | quo | Quotient | rem | Remainder | | < | Less than | > | Greater than | | <= | Less or equal | >= | Greater or equal | +--------+--------------------+--------+------------------+ Figure 2.2: Table of simple FriCAS operators. </pre> </a> <a name="figure2point3"> <pre> +----------------+------------------------------------+ | Macro | Value | +----------------+------------------------------------+ | %i | The square root of -1. | | %e | The base of the natural logarithm. | | %pi | Pi. | | %infinity | Infinity. | | %plusInfinity | Positive Infinity. | | %minusInfinity | Negative Infinity. | +----------------+------------------------------------+ Figure 2.3: Table of some useful FriCAS macros. </pre> </a> <hr> <!------------------------------------------------------------------------> <p></p> <a name="symbolic"> <h2>Chapter 3</h2> <h2>Using <b>FriCAS</b> As A Symbolic Calculator</h2> </a> <p> In the previous section all the examples involved numbers and simple functions. Also none of the expressions entered were assigned to anything. In this section we will move on to simple algebra i.e. expressions involving symbols and other features available on more sophisticated calculators. </p> <!------------------------------------------------------------------------> <p></p> <a name="exprSymbols"> <h3>3.1 Expressions Involving Symbols</h3> </a> <p> Expressions involving symbols are entered just as they are written down, for example: </p> <pre> (1) -> xSquared := x^2 2 (1) x Type: Polynomial Integer </pre> <p> where the assignment operator ``<tt>:=</tt>'' represents immediate assignment. Later it will be seen that this form of assignment is not always desirable and the use of the delayed assignment operator ``<tt>==</tt>'' will be introduced. The type of the result is <b>Polynomial Integer</b> which is used to represent polynomials with integer coefficients. Some other examples along similar lines are: </p> <pre> (2) -> xDummy := 3.21*x^2 2 (2) 3.21 x Type: Polynomial Float (3) -> xDummy := x^2.5 2 +-+ (3) x \|x Type: Expression Float (4) -> xDummy := x^3.3 3 10+-+3 (4) x \|x Type: Expression Float (5) -> xyDummy := x^2 - y^2 2 2 (5) -y + x Type: Polynomial Integer </pre> <p> Given that we can define expressions involving symbols, how do we actually compute the result when the symbols are assigned values? The answer is to use the <b>eval</b> function which takes an expression as it's first argument followed by a list of assignments. For example, to evaluate the expressions <b>xDummy</b> and <b>xyDummy</b> resulting from their respective assignments above we type: </p> <pre> (6) -> eval(xDummy, x=3) (6) 37.5405075985 29552193 Type: Expression Float (7) -> eval(xyDummy, [x=3, y=2.1]) (7) 4.59 Type: Polynomial Float </pre> <!------------------------------------------------------------------------> <p></p> <a name="complexNumbers"> <h3>3.2 Complex Numbers</h3> </a> <p> For many scientific calculations real numbers aren't sufficient and support for complex numbers is also required. Complex numbers are handled in an intuitive manner by <b>FriCAS</b> which uses the <tt>%i</tt> macro to represent <em>i</em>, the square root of -1. Thus expressions involving complex numbers are entered just like other expressions: </p> <pre> (8) -> (2/3 + %i)^3 46 1 (8) - -- + - %i 27 3 Type: Complex Fraction Integer </pre> <p> The real and imaginary parts of a complex number can be extracted using the <b>real</b> and <b>imag</b> functions and the complex conjugate of a number can be obtained using <b>conjugate</b>: </p> <pre> (9) -> real(3 + 2*%i) (9) 3 Type: PositiveInteger (10) -> imag(3 + 2*%i) (10) 2 Type: PositiveInteger (11) -> conjugate(3 + 2*%i) (11) 3 - 2%i Type: Complex Integer </pre> <p> The function <b>factor</b> can also be applied to complex numbers but the results aren't quite so obvious as for factoring integers: </p> <pre> (12) -> factor(144 + 24*%i) 6 (12) %i (1 + %i) 3 (6 + %i) Type: Factored Complex Integer </pre> <!------------------------------------------------------------------------> <p></p> <a name="numberReps"> <h3>3.3 Number Representations</h3> </a> <p> By default all numerical results are displayed in decimal with real numbers shown to 20 significant figures. If the integer part of a number is longer than 20 digits then nothing after the decimal point is shown and the integer part is given in full. To alter the number of digits shown the function <b>digits</b> can be called. The result returned by this function is the previous setting. For example, to find the value of <i>pi</i> to 40 digits we type: </p> <pre> (13) -> digits(40) (13) 20 Type: PositiveInteger (14) -> %pi :: Float (14) 3.1415926535 8979323846 2643383279 502884197 Type: Float </pre> <p> As can be seen in the example above, there is a gap after every ten digits. This can be changed using the <b>outputSpacing</b> function where the argument is the number of digits to be displayed before a space is inserted. If no spaces are desired then use the value 0. Two other functions controlling the appearance of real numbers are <b>outputFloating</b> and <b>outputFixed</b>. The former causes <b>FriCAS</b> to display floating-point values in exponent notation and the latter causes it to use fixed point notation. For example: </p> <pre> (15) -> outputFloating(); % (15) 0.3141592653 5897932384 6264338327 9502884197 E 1 Type: Float (16) -> outputFloating(3); 0.00345 (16) 0.345 E -2 Type: Float (17) -> outputFixed(); % (17) 0.00345 Type: Float (18) -> outputFixed(3); % (18) 0.003 Type: Float (19) -> outputGeneral(); % (19) 0.00345 Type: Float </pre> <p> Note that the semicolon ``<tt>;</tt>'' in the examples above allows several expressions to be entered on one line. The result of the last expression is displayed. Remember also that the percent symbol ``<tt>%</tt>'' is used to represent the result of a previous calculation. </p> <p> To display rational numbers in a base other than 10 the function <b>radix</b> is used. The first argument of this function is the expression to be displayed and the second is the base to be used: </p> <pre> (20) -> radix(10^10,32) (20) 9A0NP00 Type: RadixExpansion 32 (21) -> radix(3/21,5) ______ (21) 0.032412 Type: RadixExpansion 5 </pre> <p> Rational numbers can be represented as a repeated decimal expansion using the <b>decimal</b> function or as a continued fraction using <b>continuedFraction</b>. Any attempt to call these functions with irrational values will fail. </p> <pre> (22) -> decimal(22/7) ______ (22) 3.142857 Type: DecimalExpansion (23) -> continuedFraction(6543/210) 1 | 1 | 1 | 1 | (23) 31 + +---+ + +---+ + +---+ + +---+ | 6 | 2 | 1 | 3 Type: ContinuedFraction Integer </pre> <p> Finally, partial fractions in compact and expanded form are available via the functions <b>partialFraction</b> and <b>padicFraction</b> respectively. The former takes two arguments, the first being the numerator of the fraction and the second being the denominator. The latter function takes a fraction and expands it further while the function <b>compactFraction</b> does the reverse: </p> <pre> (24) -> partialFraction(234,40) 3 3 (24) 6 - -- + - 2 5 2 Type: PartialFraction Integer (25) -> padicFraction(%) 1 1 3 (25) 6 - - - -- + - 2 2 5 2 Type: PartialFraction Integer (26) -> compactFraction(%) 3 3 (26) 6 - -- + - 2 5 2 Type: PartialFraction Integer (27) -> padicFraction(234/40) 117 (27) --- 20 Type: PartialFraction Fraction Integer </pre> <p> To extract parts of a partial fraction the function <b>nthFractionalTerm</b> is available and returns a partial fraction of one term. To decompose this further the numerator can be obtained using <b>firstNumer</b> and the denominator with <b>firstDenom</b>. The whole part of a partial fraction can be retrieved using <b>wholePart</b> and the number of fractional parts can be found using the function <b>numberOfFractionalTerms</b>: </p> <pre> (28) -> t := partialFraction(234,40) 3 3 (28) 6 - -- + - 2 5 2 Type: PartialFraction Integer (29) -> wholePart(t) (29) 6 Type: PositiveInteger (30) -> numberOfFractionalTerms(t) (30) 2 Type: PositiveInteger (31) -> p := nthFractionalTerm(t,1) 3 (31) - -- 2 2 Type: PartialFraction Integer (32) -> firstNumer(p) (32) -3 Type: Integer (33) -> firstDenom(p) 2 (33) 2 Type: Factored Integer </pre> <!------------------------------------------------------------------------> <p></p> <a name="modularArith"> <h3>3.4 Modular Arithmetic</h3> </a> <p> By using the type constructor <b>PrimeField</b> it is possible to do arithmetic modulo some prime number. For example, arithmetic modulo 7 can be performed as follows: </p> <pre> (34) -> x : PrimeField 7 := 5 (34) 5 Type: PrimeField 7 (35) -> x^5 + 6 (35) 2 Type: PrimeField 7 (36) -> 1/x (36) 3 Type: PrimeField 7 </pre> <p> The first example should be read as </p> <blockquote> ``Let <i>x</i> be of type <b>PrimeField 7</b> and assign to it the value 5.'' </blockquote> <p> Note that it is only possible to invert non-zero values if the arithmetic is performed modulo a prime number. Thus arithmetic modulo a non-prime integer is possible but the reciprocal operation is undefined and will generate an error. Attempting to use the <b>PrimeField</b> type constructor with a non-prime argument will generate an error. An example of non-prime modulo arithmetic is: </p> <pre> (37) -> y : IntegerMod 8 := 11 (37) 3 Type: IntegerMod 8 (38) -> y*4 + 27 (38) 7 Type: IntegerMod 8 </pre> <p> Note that polynomials can be constructed in a similar way: </p><pre> (39) -> (3*a^4 + 27*a - 36)::Polynomial PrimeField 7 4 (39) 3a + 6a + 6 Type: Polynomial PrimeField 7 </pre> <hr> <!------------------------------------------------------------------------> <p></p> <a name="generalPoints"> <h2>Chapter 4</h2> <h2>General Points About <b>FriCAS</b></h2> </a> <p> This chapter contains a jumble of various points about <b>FriCAS</b>. </p> <!------------------------------------------------------------------------> <p></p> <a name="compNoOutput"> <h3>4.1 Computation Without Output</h3> </a> <p> It is sometimes desirable to enter an expression and prevent <b>FriCAS</b> from displaying the result. To do this the expression should be terminated with a semicolon ``<tt>;</tt>''. In <a href="#numberReps">Section 3.3</a> it was mentioned that a set of expressions separated by semicolons would be evaluated and the result of the last one displayed. Thus if a single expression is followed by a semicolon no output will be produced (except for its type): </p> <pre> (1) -> 2 + 4*5; Type: PositiveInteger </pre> <!------------------------------------------------------------------------> <p></p> <a name="earlierResults"> <h3>4.2 Accessing Earlier Results</h3> </a> <p> As mentioned in previous sections the ``<tt>%</tt>'' macro represents the result of the previous computation and some other macros were given in <a href="#figure2point3">Figure 2.3</a>. To refer to earlier calculations the ``<tt>%%</tt>'' macro is available which takes a single integer argument. If the argument is positive then it refers to the step number of the calculation where the numbering begins from one and can be seen at the end of each prompt (the number in parentheses). If the argument is negative then it refers to previous results counting backwards from the last result i.e. ``<tt>%%(-1)</tt>'' is the same as ``<tt>%</tt>''. The value of ``<tt>%%(0)</tt>'' is not defined and will generate an error if requested. </p> <!------------------------------------------------------------------------> <p></p> <a name="splittingExprs"> <h3>4.3 Splitting Expressions Over Several Lines</h3> </a> <p> Although <b>FriCAS</b> will quite happily accept expressions that are longer than the width of the screen (just keep typing without pressing the <b>Return</b> key) it is often preferable to split the expression being entered at a point where it would result in more readable input. To do this the underscore ``_'' symbol is placed before the break point and then the <b>Return</b> key pressed. The rest of the expression is typed on the next line and can be preceded by any number of whitespace characters, for example: </p> <pre> (2) -> 2_ +_ 3 (2) 5 Type: PositiveInteger </pre> <p> The underscore symbol is an escape character and its presence alters the meaning of the characters that follow it. As mentioned above whitespace following an underscore is ignored (the <b>Return</b> key generates a whitespace character). Any other character following an underscore loses whatever special meaning it may have had. Thus one can create the identifier ``<tt>a+b</tt>'' by typing ``<tt>a_+b</tt>'' although this might lead to confusions. Also note the result of the following example: </p> <pre> (3) -> ThisIsAVeryLong_ VariableName (3) ThisIsAVeryLongVariableName Type: Variable ThisIsAVeryLongVariableName </pre> <!------------------------------------------------------------------------> <p></p> <a name="comments"> <h3>4.4 Comments And Descriptions</h3> </a> <p> Comments and descriptions are really only of use in files of <b>FriCAS</b> code but can be used when the output of an interactive session is being spooled to a file (via the system command <b><tt>)spool</tt></b>). A comment begins with two dashes ``<tt>--</tt>'' and continues until the end of the line. Multi-line comments are only possible if each individual line begins with two dashes. </p> <p> Descriptions are the same as comments except that the <b>FriCAS</b> compiler will include them in the object files produced and make them available to the user for documentation purposes. For more details on this refer to <a href="#watt1995">[watt1995]</a>. </p> <p> A description placed <em>before</em> a calculation begins with three plus symbols ``<tt>+++</tt>'' and a description placed after a calculation begins with two plus symbols ``<tt>++</tt>''. </p> <!------------------------------------------------------------------------> <p></p> <a name="typeConversionB"> <h3>4.5 Control Of Result Types</h3> </a> <hr> <b> <blockquote> <blockquote> <blockquote> This section needs to be rewritten and extended to give a proper description of converting values from one type to another. </blockquote> </blockquote> </blockquote> </b> <hr> <p> In earlier sections the type of an expression was converted to another via the ``<tt>::</tt>'' operator. However, this is not the only method for converting between types and two other operators need to be introduced and explained. </p> <p> The first operator is ``<tt>$</tt>'' and is used to specify the package to be used to calculate the result. Thus: </p> <pre> (4) -> (2/3)$Float (4) 0.6666666666 6666666667 Type: Float </pre> <p> tells <b>FriCAS</b> to use the ``<tt>/</tt>'' operator from the <b>Float</b> package to evaluate the expression 2/3. This does not necessarily mean that the result will be of the same type as the domain from which the operator was taken. In the following example the <b>sign</b> operator is taken from the <b>Float</b> package but the result is of type <b>Integer</b>. </p> <pre> (5) -> sign(2.3)$Float (5) 1 Type: Integer </pre> <p> The other operator is ``<tt>@</tt>'' which is used to tell <b>FriCAS</b> what the desired type of the result of the calculation is. In most situations all three operators yield the same results but the example below should help to distinguish them. </p> <pre> (6) -> (2 + 3)::String (6) "5" Type: String (7) -> (2 + 3)@String An expression involving @ String actually evaluated to one of type PositiveInteger . Perhaps you should use :: String . (7) -> (2 + 3)$String The function + is not implemented in String . </pre> <p> If an expression <i>X</i> is converted using one of the three operators to type <i>T</i> the interpretations are follows: </p> <blockquote> <dl compact=""> <dt><b><tt>::</tt></b></dt> <dd>means explicitly convert <i>X</i> to type <i>T</i> if possible.</dd> <dt><b><tt>$ </tt></b></dt> <dd>means use the available operators for type <i>T</i> to compute <i>X</i>.</dd> <dt><b><tt>@ </tt></b></dt> <dd>means choose operators to compute <i>X</i> so that the result is of type <i>T</i>.</dd> </dl> </blockquote> <hr> <!------------------------------------------------------------------------> <p></p> <a name="data"> <h2>Chapter 5</h2> <h2>Data Structures in <b>FriCAS</b></h2> </a> <p> This chapter is an overview of <em>some</em> of the data structures provided by <b>FriCAS</b>. </p> <!------------------------------------------------------------------------> <p></p> <a name="lists"> <h3>5.1 Lists</h3> </a> <p> The <b>FriCAS</b> <b>List</b> type constructor is used to create homogenous lists of finite size. The notation for lists and the names of the functions that operate over them are similar to those found in functional languages such as ML. </p> <p> Lists can be created by placing a comma separated list of values inside square brackets or if a list with just one element is desired then the function <b>list</b> is available: </p> <pre> (1) -> [4] (1) [4] Type: List PositiveInteger (2) -> list(4) (2) [4] Type: List PositiveInteger (3) -> [1,2,3,5,7,11] (3) [1,2,3,5,7,11] Type: List PositiveInteger </pre> <p> The function <b>append</b> takes two lists as arguments and returns the list consisting of the second argument appended to the first. A single element can be added to the front of a list using <b>cons</b>: </p> <pre> (4) -> append([1,2,3,5],[7,11]) (4) [1,2,3,5,7,11] Type: List PositiveInteger (5) -> cons(23,[65,42,19]) (5) [23,65,42,19] Type: List PositiveInteger </pre> <p> Lists are accessed sequentially so if <b>FriCAS</b> is asked for the value of the twentieth element in the list it will move from the start of the list over nineteen elements before it reaches the desired element. Each element of a list is stored as a node consisting of the value of the element and a pointer to the rest of the list. As a result the two main operations on a list are called <b>first</b> and <b>rest</b>. Both of these functions take a second optional argument which specifies the length of the first part of the list: </p> <pre> (6) -> first([1,5,6,2,3] (6) 1 Type: PositiveInteger (7) -> first([1,5,6,2,3],2) (7) [1,5] Type: List PositiveInteger (8) -> rest([1,5,6,2,3]) (8) [5,6,2,3] Type: List PositiveInteger (9) -> rest([1,5,6,2,3],2) (9) [6,2,3] Type: List PositiveInteger </pre> <p> Other functions are <b>empty?</b> which tests to see if a list contains no elements, <b>member?</b> which tests to see if the first argument is a member of the second, <b>reverse</b> which reverses the order of the list, <b>sort</b> which sorts a list and <b>removeDuplicates</b> which removes any duplicates. The length of a list can be obtained using the ``<tt>#</tt>'' operator. </p> <pre> (10) -> empty?([7,2,-1,2]) (10) false Type: Boolean (11) -> member?(-1,[7,2,-1,2]) (11) true Type: Boolean (12) -> reverse([7,2,-1,2]) (12) [2,- 1,2,7] Type: List Integer (13) -> sort([7,2,-1,2]) (13) [-1,2,2,7] Type: List Integer (14) -> removeDuplicates([1,5,3,5,1,1,2]) (14) [1,5,3,2] Type: List PositiveInteger (15) -> #[7,2,-1,2] (15) 4 Type: PositiveInteger </pre> <p> Lists in <b>FriCAS</b> are mutable and so their contents (the elements and the links) can be modified <i>in situ</i>. Functions that operate over lists in this way have names ending with the symbol ``<tt>!</tt>''. For example, <b>concat!</b> takes two lists as arguments and appends the second argument to the first (except when the first argument is an empty list) and <b>setrest!</b> changes the link emanating from the first argument to point to the second argument (see <a href="#figure5point1">Figure 5.1</a> and <a href="#figure5point2">Figure 5.2</a> for a graphical explanation of the following example of <b>setrest!</b>): </p> <pre> (16) -> u := [9,2,4,7] (16) [9,2,4,7] Type: List PositiveInteger (17) -> concat!(u,[1,5,42]); u (17) [9,2,4,7,1,5,42] Type: List PositiveInteger (18) -> endOfu := rest(u,4) (18) [1,5,42] Type: List PositiveInteger (19) -> partOfu := rest(u,2) (19) [4,7,1,5,42] Type: List PositiveInteger (20) -> setrest!(endOfu,partOfu); u ----- (20) [9,2,4,7,1] Type: List PositiveInteger </pre> <p></p><br> <a name="figure5point1"> <center> <img src="./A Tutorial Introduction To AXIOM_files/setrest.1.gif" alt="[Image]"><br><br> <b>Figure</b> 5.1: List <i>u</i> before <tt>setrest(endOfu,partOfu)</tt>. </center> </a> <p></p><br><br> <a name="figure5point2"> <center> <img src="./A Tutorial Introduction To AXIOM_files/setrest.2.gif" alt="[Image]"><br><br> <b>Figure</b> 5.2: List <i>u</i> after <tt>setrest(endOfu,partOfu)</tt>. </center> </a> <p> From this it can be seen that the lists returned by <b>first</b> and <b>rest</b> are pointers to the original list and <em>not</em> a copy. Thus great care must be taken when dealing with lists in <b>FriCAS</b>. </p> <p> Although the <i>n</i>th element of a list <i>l</i> can be obtained by applying the <b>first</b> function to <i>n</i>-1 applications of <b>rest</b> to <i>l</i>, <b>FriCAS</b> provides a more useful access method in the form of the ``<tt>.</tt>'' operator: </p> <pre> (21) -> u.3 (21) 4 Type: PositiveInteger (22) -> u.5 (22) 1 Type: PositiveInteger (23) -> u.6 (23) 4 Type: PositiveInteger (24) -> first rest rest u -- Same as u.3 (24) 4 Type: PositiveInteger (25) -> u.first (25) 9 Type: PositiveInteger (26) -> u(3) (26) 4 Type: PositiveInteger </pre> <p> The operation <i>u.i</i> is referred to as <em>indexing into <i>u</i></em> or <em>elting into <i>u</i></em>. The latter term comes from the <b>elt</b> function which is used to extract elements (the first element of the list is at index 1). </p> <pre> (27) -> elt(u,4) -- Same as u.4 (27) 7 Type: PositiveInteger </pre> <p> If a list has no cycles then any attempt to access an element beyond the end of the list will generate an error. However, in the example above there was a cycle starting at the third element so the access to the sixth element wrapped around to give the third element. Since lists are mutable it is possible to modify elements directly: </p> <pre> (28) -> u.3 := 42; u ------ (28) [9,2,42,7,1] Type: List PositiveInteger </pre> <p> Other list operations are: </p> <pre> (29) -> L := [9,3,4,7]; #L (29) 4 Type: PositiveInteger (30) -> last(L) (30) 7 Type: PositiveInteger (31) -> L.last (31) 7 Type: PositiveInteger (32) -> L.(#L - 1) (32) 4 Type: PositiveInteger </pre> <p> </p><hr> <center> <img src="./A Tutorial Introduction To AXIOM_files/warning.gif" align="center" alt="WARNING: "> Using the ``<tt>#</tt>'' operator on a list with cycles causes <b>FriCAS</b> to enter an infinite loop. <img src="./A Tutorial Introduction To AXIOM_files/warning.gif" align="center" alt="WARNING: "> </center> <hr> <p></p> <p> Note that any operation on a list <i>L</i> that returns a list <i>L'</i> will, in general, be such that any changes to <i>L'</i> will have the side-effect of altering <i>L</i>. For example: </p> <pre> (33) -> m := rest(L,2) (33) [4,7] Type: List PositiveInteger (34) -> m.1 := 20; L (34) [9,3,20,7] Type: List PositiveInteger (35) -> n := L (35) [9,3,20,7] Type: List PositiveInteger (36) -> n.2 := 99; L (36) [9,99,20,7] Type: List PositiveInteger (37) -> n (37) [9,99,20,7] Type: List PositiveInteger </pre> <p> Thus the only safe way of copying lists is to copy each element from one to another and not use the assignment operator: </p> <pre> (38) -> p := [i for i in n] -- Same as `p := copy(n)' (38) [9,99,20,7] Type: List PositiveInteger (39) -> p.2 := 5; p (39) [9,5,20,7] Type: List PositiveInteger (40) -> n (40) [9,99,20,7] Type: List PositiveInteger </pre> <p> In the previous example a new way of constructing lists was given. This is a powerful method which gives the reader more information about the contents of the list than before and which is extremely flexible. The example, </p> <pre> (41) -> [i for i in 1..10] (41) [1,2,3,4,5,6,7,8,9,10] Type: List PositiveInteger </pre> <p> should be read as </p> <blockquote> ``Using the expression <i>i</i>, generate each element of the list by iterating the symbol <i>i</i> over the range of integers [1,10].'' </blockquote> <p> To generate the list of the squares of the first ten elements we just use: </p> <pre> (42) -> [i^2 for i in 1..10] (42) [1,4,9,16,25,36,49,64,81,100] Type: List PositiveInteger </pre> <p> For more complex lists we can apply a condition to the elements that are to be placed into the list thus to obtain a list of even numbers between 0 and 11: </p> <pre> (43) -> [i for i in 1..10 | even?(i)] (43) [2,4,6,8,10] Type: List PositiveInteger </pre> <p> This example should be read as </p> <blockquote> ``Using the expression <i>i</i>, generate each element of the list by iterating the symbol <i>i</i> over the range of integers [1,10] such that <i>i</i> is even.'' </blockquote> <p> The following achieves the same result: </p> <pre> (44) -> [i for i in 2..10 by 2] (44) [2,4,6,8,10] Type: List PositiveInteger </pre> <!------------------------------------------------------------------------> <p></p> <a name="segLists"> <h3>5.2 Segmented Lists</h3> </a> <p> A segmented list is one in which some of the elements are ranges of values. The <b>expand</b> function converts lists of this type into ordinary lists: </p> <pre> (45) -> [1..10] (45) [1..10] Type: List Segment PositiveInteger (46) -> [1..3,5,6,8..10] (46) [1..3,5..5,6..6,8..10] Type: List Segment PositiveInteger (47) -> expand(%) (47) [1,2,3,5,6,8,9,10] Type: List Integer </pre> <p> If the upper bound of a segment is omitted then a different type of segmented list is obtained and expanding it will produce a stream (which will be considered in the next section): </p> <pre> (48) -> [1..] (48) [1..] Type: List UniversalSegment PositiveInteger (49) -> expand(%) (49) [1,2,3,4,5,6,7,8,9,10,...] Type: Stream Integer </pre> <!------------------------------------------------------------------------> <p></p> <a name="Streams"> <h3>5.3 Streams</h3> </a> <p> Streams are infinite lists which have the ability to calculate the next element should it be required. For example, a stream of positive integers and a list of prime numbers can be generated by: </p> <pre> (50) -> [i for i in 1..] (50) [1,2,3,4,5,6,7,8,9,10,...] Type: Stream PositiveInteger (51) -> [i for i in 1.. | prime?(i)] (51) [2,3,5,7,11,13,17,19,23,29,...] Type: Stream PositiveInteger </pre> <p> In each case the first few elements of the stream are calculated for display purposes but the rest of the stream remains unevaluated. The value of items in a stream are only calculated when they are needed which gives rise to their alternative name of ``lazy lists''. </p> <p> Another method of creating streams is to use the <b>generate(f,a)</b> function. This applies it's first argument repeatedly onto it's second to produce the stream [<i>a,f(a),f(f(a)),f(f(f(a))) ...</i>]. Given that the function <b>nextPrime</b> returns the lowest prime number greater than it's argument we can generate a stream of primes as follows: </p> <pre> (52) -> generate(nextPrime,2)$Stream Integer (52) [2,3,5,7,11,13,17,19,23,29,...] Type: Stream Integer </pre> <p> As a longer example a stream of Fibonacci numbers will be computed. The Fibobacci numbers start at 1 and each following number is the addition of the two numbers that precede it i.e. 1,1,2,3,5,8,... The idea behind this example is from <a href="#jenks1992">[jenks1992, page 457]</a> but the explanation and construction below is that of the author's. </p> <p> Since the generation of any Fibonacci number only relies on knowing the previous two numbers we can look at the series through a window of two elements. To create the series the window is placed at the start over the values [1,1] and their sum obtained. The window is now shifted to the right by one position and the sum placed into the empty slot of the window; the process is then repeated. To implement this we require a function that takes a list of two elements (the current view of the window), adds them and outputs the new window. The result is the function <i>[a,b] -> [b,a+b]</i>: </p> <pre> (53) -> win : List Integer -> List Integer Type: Void (54) -> win(x) == [x.2, x.1 + x.2] Type: Void (55) -> win([1,1]) (55) [1,2] Type: List Integer (56) -> win(%) (56) [2,3] Type: List Integer (57) -> win(%) (57) [3,5] Type: List Integer </pre> <p> (For more details on functions definitions see <a href="#functions">Section 6.3</a>.) </p> <p> Thus it can be seen that repeatedly applying <b>win</b> to the results of the previous invocation, each element of the series is obtained. Clearly <b>win</b> is an ideal function to construct streams using the <b>generate</b> function: </p> <pre> (58) -> fibs := [generate(win,[1,1])] (58) [[1,1],[1,2],[2,3],[3,5],[5,8],[8,13],...] Type: Stream List Integer </pre> <p> This isn't quite what is wanted - we need to extract the first element of each list and place that in our series: </p> <pre> (59) -> fibs := [i.1 for i in [generate(win,[1,1])]] (59) [1,1,2,3,5,8,13,21,34,55,...] Type: Stream Integer </pre> <p> Obtaining the 200th Fibonacci number is trivial: </p> <pre> (60) -> fibs.200 (60) 280571172992510140037611932413038677189525 Type: PositiveInteger </pre> <p> One other function of interest is <b>complete</b> which expands a finite stream derived from an infinite one (and thus was still stored as an infinite stream) to form a finite stream. </p> <!------------------------------------------------------------------------> <p></p> <a name="arraysEtc"> <h3>5.4 Arrays, Vectors, Strings and Bits</h3> </a> <p> The simplest array data structure is the <em>one-dimensional array</em> which can be obtained by applying the <b>oneDimensionalArray</b> function to a list: </p> <pre> (61) -> oneDimensionalArray([7,2,5,4,1,9]) (61) [7,2,5,4,1,9] Type: OneDimensionalArray PositiveInteger </pre> <p> One-dimensional arrays are homogenous (all the elements must have the same type) and mutable like lists but unlike lists they are constant in size and have uniform access time (it is just as quick to read the last element of a one-dimensional array as it is to read the first: this is not true for lists). </p> <p> Since these arrays are mutable all the warnings that apply to lists apply to arrays i.e. it is possible to modify an element in a copy of an array and change the original: </p> <pre> (62) -> x := % (62) [7,2,5,4,1,9] Type: OneDimensionalArray PositiveInteger (63) -> y := x (63) [7,2,5,4,1,9] Type: OneDimensionalArray PositiveInteger (64) -> y.3 := 20; x (64) [7,2,20,4,1,9] Type: OneDimensionalArray PositiveInteger </pre> <p> Note that because these arrays are of fixed size the <b>concat!</b> function cannot be applied to them without generating an error. If arrays of this type are required use the <b>FlexibleArray</b> type constructor (see <a href="#flexibleArrays">Section 5.5</a>). </p> <p> One-dimensional arrays can be created using <b>new</b> which specifies the size of the array and the initial value for each of the elements. Other operations that can be applied to one-dimensional arrays are <b>map!</b> which applies a mapping onto each element, <b>swap!</b> which swaps two elements and <b>copyInto!(a,b,c)</b> which copies the array <i>b</i> onto <i>a</i> starting at position <i>c</i>: </p> <pre> (65) -> a : ARRAY1 PositiveInteger := new(10,3) (65) [3,3,3,3,3,3,3,3,3,3] Type: OneDimensionalArray PositiveInteger (66) -> map!(i +-> i+1,a); a (66) [4,4,4,4,4,4,4,4,4,4] Type: OneDimensionalArray Integer (67) -> b := oneDimensionalArray([2,3,4,5,6]) (67) [2,3,4,5,6] Type: OneDimensionalArray PositiveInteger (68) -> swap!(b,2,3); b (68) [2,4,3,5,6] Type: OneDimensionalArray PositiveInteger (69) -> copyInto!(a,b,3) (69) [4,4,2,4,3,5,6,4,4,4] Type: OneDimensionalArray PositiveInteger (70) -> a (70) [4,4,2,4,3,5,6,4,4,4] Type: OneDimensionalArray PositiveInteger </pre> <p> (note that <b>ARRAY1</b> is an abbreviation for the type <b>OneDimensionalArray</b>.) Other types based on one-dimensional arrays are <b>Vector</b>, <b>String</b> and <b>Bits</b>: </p> <pre> (71) -> vector([1/2,1/3,1/4]) 1 1 1 (71) [-,-,-] 2 3 4 Type: Vector Fraction Integer (72) -> "Hello World" (72) "Hello World" Type: String (73) -> bits(8,true) (73) "11111111" Type: Bits </pre> <p> A vector is similar to a one-dimensional array except that if it's components belong to a ring then arithmetic operations are provided. </p> <!------------------------------------------------------------------------> <p></p> <a name="flexibleArrays"> <h3>5.5 Flexible Arrays</h3> </a> <p> Flexible arrays are designed to provide the efficiency of one-dimensional arrays while retaining the flexibility of lists. They are implemented by allocating a fixed block of storage for the array. If the array needs to be expanded then a larger block of storage is allocated and the contents of the old block are copied into the new one. </p> <p> There are several operations that can be applied to this type, most of which modify the array <i>in situ</i>. As a result these functions all have names ending in ``<tt>!</tt>''. All the functions in the example below are fairly obvious. The <b>physicalLength</b> returns the actual length of the array as stored in memory while the <b>physicalLength!</b> allows this value to be changed by the user. </p> <pre> (74) -> f : FARRAY INT := new(6,1) (74) [1,1,1,1,1,1] Type: FlexibleArray Integer (75) -> f.1 := 4;f.2 := 3;f.3 := 8;f.5 := 2;f (75) [4,3,8,1,2,1] Type: FlexibleArray Integer (76) -> insert!(42,f,3); f (76) [4,3,42,8,1,2,1] Type: FlexibleArray Integer (77) -> insert!(28,f,8); f (77) [4,3,42,8,1,2,1,28] Type: FlexibleArray Integer (78) -> removeDuplicates!(f) (78) [4,3,42,8,1,2,28] Type: FlexibleArray Integer (79) -> delete!(f,5) (79) [4,3,42,8,2,28] Type: FlexibleArray Integer (80) -> g := f(3..5) (80) [42,8,2] Type: FlexibleArray Integer (81) -> g.2 := 7; f (81) [4,3,42,8,2,28] Type: FlexibleArray Integer (82) -> insert!(g,f,1) (82) [42,7,2,4,3,42,8,2,28] Type: FlexibleArray Integer (83) -> physicalLength(f) (83) 10 Type: PositiveInteger (84) -> physicalLength!(f,20) (84) [42,7,2,4,3,42,8,2,28] Type: FlexibleArray Integer (85) -> merge!(sort!(f),sort!(g)) (85) [2,2,2,3,4,7,7,8,28,42,42,42] Type: FlexibleArray Integer (86) -> shrinkable(false)$FlexibleArray(Integer) (86) true Type: Boolean </pre> <p> There are several things to point out concerning the previous examples. Firstly although flexible arrays are mutable, making copies of these arrays creates separate entities. This can be seen by the fact that the modification of element <i>b.2</i> above did not alter <i>a</i>. Secondly, the <b>merge!</b> function can take an extra argument before the two arrays being merged. The argument is a comparison function and defaults to <tt><=</tt> if omitted. Lastly, <b>shrinkable</b> tells the <b>FriCAS</b> system whether or not to let flexible arrays contract when elements are deleted from them. An explicit package reference must be given as in the example above. </p><hr> <b> <blockquote> <blockquote> <blockquote> Although there are several other data structures that ought to be covered here such as sets and records, I want to move on to more important areas such as functions and iteration before finishing this chapter off. </blockquote> </blockquote> </blockquote> </b> <hr> <!------------------------------------------------------------------------> <p></p> <a name="functionsEtc"> <h2>Chapter 6</h2> <h2>Functions, Choices And Loops</h2> </a> <p> By now the reader should be able to construct simple one-line expressions involving variables and different data structures. This chapter builds on this knowledge and shows how to use iteration, make choices and build functions in <b>FriCAS</b>. At the moment it is assumed that the reader has a rough idea of how types are specified and constructed so that they can follow the examples given. A more detailed coverage of types in <b>FriCAS</b> will be provided in a later chapter (sometime in the future!). </p> <p> From this point on most examples will be taken from input files. The prompt for such examples is faked and should actually contain a command such as ``<tt>)read eg01.input</tt>''. There may be jumps in the step numbers of the examples due to the way <b>FriCAS</b> calculates them and due to the editing done on the output. If the example code is free from bugs then a value and type for the code will be given otherwise just the code will be displayed </p> <p> Although the author has not covered this topic yet please make do with the following snippet until I write that section: </p> <!------------------------------------------------------------------------> <p></p> <a name="readFromFile"> <h3>6.1 Reading Code From A File</h3> </a> <ul> <li>The names of all input files in <b>FriCAS</b> should end in the suffix ``<tt>.input</tt>'' otherwise <b>FriCAS</b> will refuse to consult them.</li> <li>Use the command <b>)read fred.input</b> to read and interpret the contents of the file ``<tt>fred.input</tt>''.</li> <li>To start everything afresh before reading in an input file enter the command <b>)clear all</b> or put it at the start of the file.</li> </ul> <!------------------------------------------------------------------------> <p></p> <a name="Blocks"> <h3>6.2 Blocks</h3> </a> <p> The <b>FriCAS</b> constructs that provide looping, choices and user-defined functions all rely on the notion of blocks. According to <a href="#jenks1992">[jenks1992, page 112]</a> a block is a sequence of expressions which are evaluated in the order that they appear except when it is modified by control expressions such as loops. To leave a block prematurely use the expression <i>BoolExpr => Expr</i> where <i>BoolExpr</i> is any <b>FriCAS</b> expression that has type <b>Boolean</b>. The value and type of <i>Expr</i> determines the value and type returned by the block. </p> <p> If blocks are entered at the keyboard (as opposed to reading code in from a text file) then there is only one way of creating them; the syntax is: </p> <blockquote> <tt>(</tt> <i>expression1</i> <tt>;</tt> <i>expression2</i> <tt>;</tt> ... <tt>;</tt> <i>expressionN</i> <tt>)</tt> </blockquote> <p> In an input file a block can be constructed as above or by placing all the statements at the same indentation level. In this situation the block is called a <em>pile</em>. As an example of a simple block a list of three integers can be constructed using parentheses </p> <pre> (1) -> (a := 4;b := 1; c := 9; L := [a,b,c]) (1) [4,1,9] Type: List PositiveInteger </pre> <p> or using piles </p> <pre> (2) -> L := a := 4 b := 1 c := 9 [a,b,c] (2) [4,1,9] Type: List PositiveInteger </pre> <p> Since blocks have a type and a value they can be used as arguments to functions or as part of other expressions. It should be pointed out that the following example is not recommended practice but helps to illustrate the idea of blocks and their ability to return values: </p> <pre> (3) -> sqrt(4.0 + a := 3.0 b := 1.0 c := a + b c ) (3) 2.8284271247 461900976 Type: Float </pre> <p> Note that indentation is <em>extremely</em> important. If the example given above had the pile starting at ``<tt>a :=</tt>'' moved left by two spaces so that the ``<tt>a</tt>'' was under the ``<tt>(</tt>'' of the first line then the interpreter would signal an error. Furthermore, if the closing bracket ``<tt>)</tt>'' is moved up to give: </p> <pre> (4) -> sqrt(4.0 + a := 3.0 b := 1.0 c := a + b c) </pre> <p> then the parser will generate errors and if the bracket is shifted right by several spaces so that it is in line with the ``<tt>c</tt>'' similar errors will be raised. Finally, the ``<tt>)</tt>'' must be indented by at least one space otherwise more errors will be generated. </p> <p> Thus it can be seen that great care needs to be taken when constructing input files consisting of piles of expressions. It would seem prudent to add one pile at a time and check it is acceptable before adding more, particularly if piles are nested. However, it should be pointed out that the use of piles as values for functions is not very readable and so perhaps the delicate nature of their interpretation should deter programmers from using them in these situations. Using piles should really be restricted to constructing functions etc. and a small amount of rewriting can remove the need to use them as arguments. For example, the previous block could easily be implemented as: </p> <pre> (4) -> a := 3.0 b := 1.0 c := a + b sqrt(4.0 + c) (4) 2.8284271247 461900976 Type: Float </pre> <p> which achieves the same result and is easier to understand. Note that this is still a pile but it is not as fragile as the previous version. </p> <!------------------------------------------------------------------------> <p></p> <a name="functions"> <h3>6.3 Functions</h3> </a> <p> Definitions of functions in <b>FriCAS</b> are quite simple providing two things are observed. Firstly the type of the function must either be completely specifed or completely unspecified and secondly the body of the function is assigned to the function identifier using the delayed assignment operator ``<tt>==</tt>''. </p> <p> To specify the type of something the ``<tt>:</tt>'' operator is used. Thus to define a variable <i>x</i> to be of type <b>Fraction Integer</b> we enter: </p> <pre> (5) -> x : Fraction Integer Type: Void </pre> <p> For functions the method is the same except that the arguments to are placed in parentheses and the return type is placed after the symbol ``<tt>-></tt>''. More details on type definitions will be given later which will explain this more fully. For now an example of type definitions for functions taking zero, one, two and three integer arguments and returning a list of integers are given: </p> <pre> (6) -> f : () -> List Integer Type: Void (7) -> g : (Integer) -> List Integer Type: Void (8) -> h : (Integer, Integer) -> List Integer Type: Void (9) -> k : (Integer, Integer, Integer) -> List Integer Type: Void </pre> <p> Now the actual definition of the functions might be: </p> <pre> (10) -> f() == [] Type: Void (11) -> g(a) == [a] Type: Void (12) -> h(a,b) == [a,b] Type: Void (13) -> k(a,b,c) == [a,b,c] Type: Void </pre> <p> with some invokations of these functions: </p> <pre> (14) -> f() (14) [] Type: List Integer (15) -> g(4) (15) [4] Type: List Integer (16) -> h(2,9) (16) [2,9] Type: List Integer (17) -> k(-3,42,100) (17) [-3,42,100] Type: List Integer </pre> <p> The value returned by a function is either the value of the last expression evaluated or the result of a <b>return</b> statement. For example the following are effectively the same: </p> <pre> (18) -> p : Integer -> Integer p x == a := 1 b := 2 a + b + x Type: Void (19) -> p : Integer -> Integer p x == a := 1 b := 2 return a + b + x Type: Void </pre> <p> Note that a block (pile) is assigned to the function identifier <b>p</b> and thus all the rules about blocks apply to function definitions. Also there was only one argument so the parentheses were discarded. </p> <p> This is basically all that one needs to know about defining functions in <b>FriCAS</b> - first specify the complete type and then assign a block to the function. The rest of this chapter is concerned with defining more complex blocks than those in this section and as a result function definitions will crop up continually particularly since they are a good way of testing examples. </p> <!------------------------------------------------------------------------> <p></p> <a name="choices"> <h3>6.4 Choices</h3> </a> <p> Apart from the ``<tt>=></tt>'' operator that allows a block to be left before the end <b>FriCAS</b> provides the standard <b>if-then-else</b> construct. The general syntax is: </p> <blockquote> <tt>if </tt><i>BooleanExpr</i> <tt>then </tt><i>Expr1</i> <tt>else </tt><i>Expr2</i> </blockquote> <p> where ``<tt>else </tt><i>Expr2</i>'' can be omitted. If the expression <i>BooleanExpr</i> evaluates to <i>true</i> then <i>Expr1</i> is executed otherwise <i>Expr2</i> (if present) will be. An example of piles and <b>if-then-else</b> in <b>FriCAS</b> from <a href="#jenks1992">[jenks1992, page 114]</a> is given below: </p> <pre> (20) -> h := 2.0 if h > 3.1 then 1.0 else z := cos(h) max(z,0.5) (20) 0.5 Type: Float </pre> <p> Note the indentation - the ``<tt>else</tt>'' must be indented relative to the ``<tt>if</tt>'' otherwise it will generate an error (<b>FriCAS</b> will think there are two piles, the second one beginning with ``<tt>else</tt>''). </p> <p> Any expression that has type <b>Boolean</b> can be used as <i>BooleanExpr</i> and the most common will be those involving the relational operators ``<tt>></tt>'', ``<tt><</tt>'' and ``<tt>=</tt>''. Usually the type of an expression involving the equality operator ``<tt>=</tt>'' will be <b>Boolean</b> but in those situations when it isn't you may need to use the ``<tt>@</tt>'' operator to ensure that it is. </p> <!------------------------------------------------------------------------> <p></p> <a name="loops"> <h3>6.5 Loops</h3> </a> <p> Loops in <b>FriCAS</b> are regarded as expressions containing another expression called the <em>loop body</em>. The loop body is executed zero or more times depending on the type of the loop. Loops can be nested to any depth. </p> <!------------------------------------------------------------------------> <p></p> <a name="repeat"> <h4>6.5.1 The repeat Loop</h4> </a> <p> The simplest type of loop provided by <b>FriCAS</b> is the <b>repeat</b> loop. The general syntax of this is: </p> <blockquote> <tt>repeat </tt><i>loopBody</i> </blockquote> <p> This will cause <b>FriCAS</b> to execute <i>loopBody</i> repeatedly until either a <b>break</b> or <b>return</b> statement are encountered. If <i>loopBody</i> contains neither of these statements then it will loop forever. The following piece of code will display the numbers from 1 to 4: </p> <pre> (21) -> i := 1 repeat if i > 4 then break output(i) i := i + 1 1 2 3 4 Type: Void </pre> <p> <b>Note:</b> In <b>FriCAS</b> Release 1.3.5 the <b>break</b> keyword replaces <b>leave</b> which was used in old AXIOM versions. Use of <b>leave</b> will generate an error if it is used with <b>FriCAS</b>. </p> <p> It was mentioned that loops will only be left when either a <b>break</b> or <b>return</b> statement is encountered so why can't one use the ``<tt>=></tt>'' operator? The reason is that the ``<tt>=></tt>'' operator tells <b>FriCAS</b> to leave the current block whereas <b>break</b> and <b>return</b> tell <b>FriCAS</b> to leave the current loop (the latter actually tells <b>FriCAS</b> to leave the current function which could mean leaving several levels of loop if necessary). An example of this is given in <a href="#jenks1992">[jenks1992]</a> and is provided here for reference: </p> <pre> (22) -> i := 0 repeat i := i + 1 i > 3 => i output(i) 1 2 3 ^C >> Sytem error: Console interrupt. </pre> <p> Here the ``<tt>=></tt>'' operator instructs <b>FriCAS</b> to leave the block when the value of <i>i</i> reaches 4 but then the loop continues to execute the first statement (increment <i>i</i>) forever (or until the user interrupts it). However, the <b>break</b> keyword can be used to represent a return value so we can combine the two previous examples as follows: </p> <pre> (22) -> i := 0 repeat i := i + 1 i > 3 => break output(i) 1 2 3 Type: Void </pre> <p> To skip the rest of a loop body and begin the next iteration of the loop one uses the <b>iterate</b> keyword: </p> <pre> (23) -> i := 0 repeat i := i + 1 if i > 6 then break -- Return to start if i is odd. if odd?(i) then iterate output(i) 2 4 6 Type: Void </pre> <!------------------------------------------------------------------------> <p></p> <a name="while"> <h4>6.5.2 The while Loop</h4> </a> <p> The <b>while</b> statement extends the basic <b>repeat</b> loop to place the control of leaving the loop at the start rather than have it buried in the middle. Since the body of the loop is still part of a <b>repeat</b> loop, <b>break</b> and ``<tt>=></tt>'' work in the same way as in the previous section. The general syntax of a <b>while</b> loop is: </p> <blockquote> <tt>while </tt><i>BoolExpr</i><tt> repeat </tt><i>loopBody</i> </blockquote> <p> As before, <i>BoolExpr</i> must be an expression of type <b>Boolean</b>. Before the body of the loop is executed <i>BoolExpr</i> is tested. If it evaluates to <b>true</b> then the loop body is entered otherwise the loop is terminated. Multiple conditions can be applied using the logical operators such as <b>and</b> or by using several <b>while</b> statements before the <b>repeat</b>. The following examples are from <a href="#jenks1992">[jenks1992, page 122]</a>: </p> <pre> (24) -> x := 1; y := 1 while x < 4 and y < 10 repeat output [x,y] x := x + 1 y := y + 2 [1,1] [2,3] [3,5] Type: Void (25) -> x := 1; y := 1 while x < 4 while y < 10 repeat output [x,y] x := x + 1 y := y + 2 [1,1] [2,3] [3,5] Type: Void </pre> <p> Note that the last example using two <b>while</b> statements is <em>not</em> a nested loop but the following one is: </p> <pre> (26) -> x := 1; y := 1 while x < 4 repeat while y < 10 repeat output [x,y] x := x + 1 y := y + 2 [1,1] [2,3] [3,5] [4,7] [5,9] Type: Void </pre> <p> As a longer example the following is taken from <a href="#jenks1992">[jenks1992, page 123]</a> although the matrix used is different. Given a matrix of arbitrary size, find the position and value of the first negative element by examining the matrix in row-major order: </p> <pre> (27) -> m := matrix [[21,37,53,14],_ [8,22,-24,16],_ [2,10,15,14],_ [26,33,55,-13]] +21 37 53 14 + | | |8 22 - 24 16 | (27) | | |2 10 15 14 | | | +26 33 55 - 13+ Type: Matrix Integer (28) -> lastrow := nrows(m); lastcol := ncols(m) r := 1 while r <= lastrow repeat c := 1 -- Index of first column while c <= lastcol repeat if elt(m,r,c) < 0 then output [r,c,elt(m,r,c)] r := lastrow break -- Don't look any further c := c + 1 r := r + 1 [2,3,-24] Type: Void </pre> <!------------------------------------------------------------------------> <p></p> <a name="for"> <h4>6.5.3 The for Loop</h4> </a> <p> The last loop of interest is the <b>for</b> loop. There are two ways of creating a <b>for</b> loop and the general syntax for both is as follows (with and without the ``such that'' predicates): </p> <blockquote> <tt>for </tt><i>var</i><tt> in </tt><i>seg</i><tt> repeat </tt><i>loopBody</i><br> <tt>for </tt><i>var</i><tt> in </tt><i>list</i><tt> repeat </tt><i>loopBody</i><br> <tt>for </tt><i>var</i><tt> in </tt><i>seg</i><tt> | </tt><i>BoolExpr</i><tt> repeat </tt><i>loopBody</i><br> <tt>for </tt><i>var</i><tt> in </tt><i>list</i><tt> | </tt><i>BoolExpr</i><tt> repeat </tt><i>loopBody</i><br> </blockquote> <p> where <i>var</i> is an index variable which is iterated over the values in <i>seg</i> or <i>list</i>. The value <i>seg</i> is a segment e.g. <tt>1..10</tt> or <tt>1..</tt> and <i>list</i> is a list of some type. The last two types of <b>for</b> loop will only execute the statements in <i>loopBody</i> if <i>BoolExpr</i> evaluates to <b>true</b>. Some examples of this type of loop are given below: </p> <pre> (29) -> for i in 1..10 repeat ~prime?(i) => iterate output(i) 2 3 5 7 Type: Void </pre> <pre> (30) -> for i in 1..10 | prime?(i) repeat output(i) 2 3 5 7 Type: Void </pre> <pre> (31) -> for w in ["This", "Is", "Your", "Life!"] repeat output(w) This Is Your Life Type: Void </pre> <pre> (32) -> for i in 1.. repeat if even?(i) then output(i) if i < 7 then iterate break 2 4 6 Type: Void </pre> <p> The last example loop can be simplified by adding a <b>while</b> clause: </p> <pre> (33) -> for i in 1.. while i < 7 repeat if even?(i) then output(i) 2 4 6 Type: Void </pre> <p> and by using the ``such that'' clause it becomes even simpler: </p> <pre> (34) -> for i in 1.. | even?(i) while i < 7 repeat output(i) 2 4 6 Type: Void </pre> <p> Similarly it is possible to have multiple <b>for</b> clauses on a line to iterate over several symbols in parallel: </p> <pre> (35) -> for a in 1..4 for b in 5..8 repeat output [a,b] [1,5] [2,6] [3,7] [4,8] Type: Void </pre> <p> As a general point it should be noted that any symbols referred to in the ``such that'' and <b>while</b> clauses must be pre-defined. This either means that the symbols must have been defined in an outer level (e.g. in an enclosing loop) or in a <b>for</b> clause appearing before the ``such that'' or <b>while</b>. For example, </p> <pre> (36) -> for a in 1..4 repeat for j in 7..9 | prime?(a + b) repeat output [a,b,a + b] [2,9,11] [3,8,11] [4,7,11] [4,9,13] Type: Void </pre> <p> is legal but </p> <pre> (37) -> for b in 7..9 | prime?(a + b) repeat for a in 1..4 repeat output [a,b,a + b] </pre> <p> is not and will generate an error because <i></i> is not defined in the first line. </p> <p> Finally it is often useful to be able to use a segment in which the elements are in decreasing order. To do this the <b>by</b> keyword is used: </p> <pre> (38) -> for a in 1..4 for b in 8..5 by -1 repeat output [a,b] [1,8] [2,7] [3,6] [4,5] Type: Void </pre> <p> Note that without ``<b>by -1</b>'' the loop body would never be executed (the segment 8..5 is empty so there is nothing to iterate over): </p> <pre> (39) -> for a in 1..4 for b in 8..5 by -1 repeat output [a,b] Type: Void </pre> <hr> <!------------------------------------------------------------------------> <p></p> <a name="biblio"> <h2>Bibliography</h2> </a> <dl> <dt><a name="jenks1992">[jenks1992]</a></dt> <dd>Richard D. Jenks and Robert S. Sutor. <i>AXIOM: the scientific computation system.</i> NAG Ltd., 1992.</dd> <dt><a name="watt1995">[watt1995]</a></dt> <dd>Stephen M. Watt, Peter A. Broadbery, Samuel S. Dooley, Pietro Iglio, Scott C. Morrison, Jonathon M. Steinbach, and Robert S. Sutor. <i>AXIOM Library Compiler User Guide.</i> NAG Ltd., first edition, March 1995. Reprinted with corrections from November 1994.</dd> </dl> <hr> <address> <b>Martin Dunstan</b><tt> (mnd@dcs.st-andrews.ac.uk)</tt><br> Updated: 2nd May, 1996. </address> <!-- FILE ARCHIVED ON 6:51:40 Feb 5, 2007 AND RETRIEVED FROM THE INTERNET ARCHIVE ON 16:36:41 Apr 1, 2011. JAVASCRIPT APPENDED BY WAYBACK MACHINE, COPYRIGHT INTERNET ARCHIVE. ALL OTHER CONTENT MAY ALSO BE PROTECTED BY COPYRIGHT (17 U.S.C. SECTION 108(a)(3)). --> </body></html>
An Introduction To Programming In
By Martin N. Dunstan
May 2, 1996Contents
- Introduction
- Using FriCAS As A Pocket Calculator
- Using FriCAS As A Symbolic Calculator
- General Points About FriCAS
- Computation Without Output
- Accessing Earlier Result
- Splitting Expressions Over Several Lines
- Comments And Descriptions
- Control Of Result Types
- Data Structures In FriCAS
- Functions, Choices And Loops
List Of Figures
Chapter 1
Introduction
This document is intended to be a tutorial introduction to the FriCAS (Release 1.3.5) system and its language. Initially the examples and discussion will relate to the interactive system and the use of input files will be touched on later.
Although "FriCAS Book":http://fricas.github.io/book.pdf (updated version of [jenks1992]) is an extremely useful book for those wanting to use the FriCAS system it is not quite so helpful for learning to program in FriCAS. Generally one learns a new programming language by writing short programs ("one-liners") before learning about the various flow-control instructions such as if and while. However, learning to use a large system such as FriCAS requires a text that covers a significant part of the available features while keeping the number of pages to a minimum as FriCAS Book does. This is not to say that FriCAS Book does not explain how to program in FriCAS since this is how the author learned!
As a result the author has decided to produce this text as an introduction to the FriCAS language for readers who are already familiar with at least one programming language. Knowledge of a functional programming language would be a benefit since many of the concepts found in functional languages are present in FriCAS but is by no means essential. FriCAS is not a functional language since it has a notion of state and functions can (and sometimes do) have side-effects.
This document has been compiled by working through [jenks1992] in parallel with interactive sessions of FriCAS (a new session is started for each chapter). The structure of the text is the author's but the majority of the information has come from [jenks1992] in some form or another since this appears to be the only large body of information on FriCAS (apart from the HyperDoc program). However, the examples are mostly of the author's own design and are all extracted directly from the output produced by FriCAS - the code for each example was copied from the LaTeX version of this document into the FriCAS interpreter and the results copied back. As a result there shouldn't be any mistakes.
Please let me (mnd@dcs.st-andrews.ac.uk) know of any errors or any comments/criticisms you have regarding this document as I would like to make it as useful as possible.
Chapter 2
Using FriCAS As A Pocket Calculator
At the simplest level FriCAS can be used as a pocket calculator where expressions involving numbers and operators are entered directly in infix notation. In this sense the more advanced features of the calculator can be regarded as operators (e.g. sin, cos etc.).
2.1 Basic Arithmetic
An example of this might be to calculate the cosine of 2.45 (in radians). To do this one would type:
(1) -> cos 2.45
(1) -0.7702312540 473073417
Type: Float
Before proceeding any further it would be best to explain the previous three lines. Firstly the text ``(1) -> '' is part of the prompt that the FriCAS system provides when in interactive mode. The full prompt probably has other text preceding this but it is not relevent here. The number in parenthesis is the step number of the input which may be used to refer to the results of previous calculations. The step number appears at the start of the second line to tell you which step the result belongs to. Since the interpreter probably loaded numerous libraries to calculate the result given above and listed each one in the process, there could easily be several pages of text between your input and the answer.
The last line contains the type of the result. The type Float is used to represent real numbers of arbitrary size and precision (where the user is able to define how big arbitrary is - the default is 20 digits but can be as large as your computer system can handle). The type of the result can help track down mistakes in your input if you don't get the answer you expected.
Other arithmetic operations such as addition, subtraction, multiplication behave as expected:
(2) -> 6.93 * 4.1328
(2) 28.640304
Type: Float
(3) -> 6.93 / 4.1328
(3) 1.6768292682 926829268
Type: Float
but integer division isn't quite so obvious. For example, if one types:
(4) -> 4/6
2
(4) -
3
Type: Fraction Integer
a fractional result is obtained. The function used to display fractions attempts to produce the most readable answer. In the example:
(5) -> 4/2
(5) 2
Type: Fraction Integer
the result is stored as the faction 2/1 but is displayed as the integer 2. This fraction could be converted to type Integer with no loss of information but FriCAS will not do so automatically.
2.2 Type Conversion
To obtain the floating point value of a fraction one must convert (according to the documentation, coercions are conversions that are automatically applied by the kernel) it to type Float using the ``::'' operator (see Section 4.5) as follows (the parentheses are required due to the relative precedences of ``::'' and ``/''):
(6) -> (4/6) :: Float
(6) 0.6666666666 6666666667
Type: Float
Although FriCAS can convert this back to a fraction it might not be the same fraction it started as due to rounding errors. For example, the following conversion appears to be without error but others might not:
(7) -> % :: Fraction Integer
2
(7) -
3
Type: Fraction Integer
where ``%'' represents the previous result (not the calculation).
Although FriCAS has the ability to work with floating-point numbers to very high precision it must be remembered that calculations with these numbers are not exact. Since FriCAS is a computer algebra package and not a numerical solutions package this should not create too many problems. The idea is that the user should use FriCAS to do all the necessary symbolic manipulation and only at the end should actual numerical results be extracted.
If you bear in mind that FriCAS appears to store expressions just as you have typed them and does not perform any evaluation of them unless forced to then programming in the system will be much easier. It means that anything you ask FriCAS to do (within reason) will be carried with complete accuracy.
In the previous examples the ``::'' operator was used to convert values from one type to another. This type conversion is not possible for all values for instance, it is not possible to convert the number 3.4 to an integer type since it can't be represented as an integer. The number 4.0 however can be converted to an integer type since it has no fractional part. Refer to Section 4.5) for more details on type conversion.
Conversion from floating point values to integers is performed using the functions round and truncate. The first of these rounds a floating point number to the nearest integer while the other truncates i.e. removes the fractional part. Both functions return the result as a floating point number. To extract the fractional part of a floating point number use the function fractionPart but note that the sign of the result depends on the sign of the argument (FriCAS obtains the fractional part of ``x'' using ``x - truncate x''):
(8) -> round(3.77623)
(8) 4.0
Type: Float
(9) -> round(-3.77623)
(9) -4.0
Type: Float
(10) -> truncate(9.235)
(10) 9.0
Type: Float
(11) -> truncate(-9.654)
(11) -9.0
Type: Float
(12) -> fractionPart(-3.77623)
(12) -0.77623
Type: Float
2.3 Useful Functions
To obtain the absolute value of a number the abs function can be used. This takes a single argument which is usually an integer or a floating point value but doesn't necessarily have to be. The sign of a value can be obtained via the sign function which returns -1, 0, or 1 depending on the sign of the argument:
(13) -> abs(4)
(13) 4
Type: PositiveInteger
(14) -> abs(-3)
(14) 3
Type: PositiveInteger
(15) -> abs(-34254.12314)
(15) 34254.12314
Type: Float
(16) -> sign(-49543.2345346)
(16) -1
Type: Integer
(17) -> sign(0)
(17) 0
Type: NonNegativeInteger
(18) -> sign(234235.42354)
(18) 1
Type: PositiveInteger
Tests on values can be done using using various functions which are generally more efficient than using relational operators such as ``='' particularly if the value is a matrix. Examples of some of these functions are:
(19) -> positive?(-234)
(19) false
Type: Boolean
(20) -> negative?(-234)
(20) true
Type: Boolean
(21) -> zero?(42)
(21) false
Type: Boolean
(22) -> one?(1)
(22) true
Type: Boolean
(23) -> odd?(23)
(23) true
Type: Boolean
(24) -> odd?(9.435)
(24) false
Type: Boolean
(25) -> even?(-42)
(25) true
Type: Boolean
(26) -> prime?(37)
(26) true
Type: Boolean
(27) -> prime?(-37)
(27) false
Type: Boolean
Some other functions that are quite useful for manipulating numerical values are shown in Figure 2.1 while Figure 2.2 contains a table of simple infix and prefix operators. Figure 2.3 is a table of predefined macros that can be used in various situations.
+---------------+------------------------------------+
| Function | Operation |
+---------------+------------------------------------+
| sin(x) | Sine of x |
| cos(x) | Cosine of x |
| tan(x) | Tangent of x |
| asin(x) | Arcsin of x |
| acos(x) | Arccos of x |
| atan(x) | Arctangent of x |
| gcd(x,y) | Greatest common divisor of x and y |
| lcm(x,y) | Lowest common multiple of x and y |
| max(x,y) | Maximum of x and y |
| min(x,y) | Minimum of x and y |
| factorial(x) | Factorial of x |
| factor(x) | Prime factors of x |
| divide(x,y) | Quotient and remainder of x/y |
+---------------+------------------------------------+
Figure 2.1: Table of simple FriCAS functions.
+--------+--------------------+--------+------------------+
| Symbol | Operation | Symbol | Operation |
+--------+--------------------+--------+------------------+
| + | Addition | - | Subtraction |
| - | Numerical Negation | ~ | Logical Negation |
| /\ | Conjunction (AND) | \/ | Disjunction (OR) |
| and | Logical AND (/\) | or | Logical OR (\/) |
| not | Logical Negation | ^ | Exponentiation |
| * | Multiplication | / | Division |
| quo | Quotient | rem | Remainder |
| < | Less than | > | Greater than |
| <= | Less or equal | >= | Greater or equal |
+--------+--------------------+--------+------------------+
Figure 2.2: Table of simple FriCAS operators.
+----------------+------------------------------------+
| Macro | Value |
+----------------+------------------------------------+
| %i | The square root of -1. |
| %e | The base of the natural logarithm. |
| %pi | Pi. |
| %infinity | Infinity. |
| %plusInfinity | Positive Infinity. |
| %minusInfinity | Negative Infinity. |
+----------------+------------------------------------+
Figure 2.3: Table of some useful FriCAS macros.
Chapter 3
Using FriCAS As A Symbolic Calculator
In the previous section all the examples involved numbers and simple functions. Also none of the expressions entered were assigned to anything. In this section we will move on to simple algebra i.e. expressions involving symbols and other features available on more sophisticated calculators.
3.1 Expressions Involving Symbols
Expressions involving symbols are entered just as they are written down, for example:
(1) -> xSquared := x^2
2
(1) x
Type: Polynomial Integer
where the assignment operator ``:='' represents immediate assignment. Later it will be seen that this form of assignment is not always desirable and the use of the delayed assignment operator ``=='' will be introduced. The type of the result is Polynomial Integer which is used to represent polynomials with integer coefficients. Some other examples along similar lines are:
(2) -> xDummy := 3.21*x^2
2
(2) 3.21 x
Type: Polynomial Float
(3) -> xDummy := x^2.5
2 +-+
(3) x \|x
Type: Expression Float
(4) -> xDummy := x^3.3
3 10+-+3
(4) x \|x
Type: Expression Float
(5) -> xyDummy := x^2 - y^2
2 2
(5) -y + x
Type: Polynomial Integer
Given that we can define expressions involving symbols, how do we actually compute the result when the symbols are assigned values? The answer is to use the eval function which takes an expression as it's first argument followed by a list of assignments. For example, to evaluate the expressions xDummy and xyDummy resulting from their respective assignments above we type:
(6) -> eval(xDummy, x=3)
(6) 37.5405075985 29552193
Type: Expression Float
(7) -> eval(xyDummy, [x=3, y=2.1])
(7) 4.59
Type: Polynomial Float
3.2 Complex Numbers
For many scientific calculations real numbers aren't sufficient and support for complex numbers is also required. Complex numbers are handled in an intuitive manner by FriCAS which uses the %i macro to represent i, the square root of -1. Thus expressions involving complex numbers are entered just like other expressions:
(8) -> (2/3 + %i)^3
46 1
(8) - -- + - %i
27 3
Type: Complex Fraction Integer
The real and imaginary parts of a complex number can be extracted using the real and imag functions and the complex conjugate of a number can be obtained using conjugate:
(9) -> real(3 + 2*%i)
(9) 3
Type: PositiveInteger
(10) -> imag(3 + 2*%i)
(10) 2
Type: PositiveInteger
(11) -> conjugate(3 + 2*%i)
(11) 3 - 2%i
Type: Complex Integer
The function factor can also be applied to complex numbers but the results aren't quite so obvious as for factoring integers:
(12) -> factor(144 + 24*%i)
6
(12) %i (1 + %i) 3 (6 + %i)
Type: Factored Complex Integer
3.3 Number Representations
By default all numerical results are displayed in decimal with real numbers shown to 20 significant figures. If the integer part of a number is longer than 20 digits then nothing after the decimal point is shown and the integer part is given in full. To alter the number of digits shown the function digits can be called. The result returned by this function is the previous setting. For example, to find the value of pi to 40 digits we type:
(13) -> digits(40)
(13) 20
Type: PositiveInteger
(14) -> %pi :: Float
(14) 3.1415926535 8979323846 2643383279 502884197
Type: Float
As can be seen in the example above, there is a gap after every ten digits. This can be changed using the outputSpacing function where the argument is the number of digits to be displayed before a space is inserted. If no spaces are desired then use the value 0. Two other functions controlling the appearance of real numbers are outputFloating and outputFixed. The former causes FriCAS to display floating-point values in exponent notation and the latter causes it to use fixed point notation. For example:
(15) -> outputFloating(); %
(15) 0.3141592653 5897932384 6264338327 9502884197 E 1
Type: Float
(16) -> outputFloating(3); 0.00345
(16) 0.345 E -2
Type: Float
(17) -> outputFixed(); %
(17) 0.00345
Type: Float
(18) -> outputFixed(3); %
(18) 0.003
Type: Float
(19) -> outputGeneral(); %
(19) 0.00345
Type: Float
Note that the semicolon ``;'' in the examples above allows several expressions to be entered on one line. The result of the last expression is displayed. Remember also that the percent symbol ``%'' is used to represent the result of a previous calculation.
To display rational numbers in a base other than 10 the function radix is used. The first argument of this function is the expression to be displayed and the second is the base to be used:
(20) -> radix(10^10,32)
(20) 9A0NP00
Type: RadixExpansion 32
(21) -> radix(3/21,5)
______
(21) 0.032412
Type: RadixExpansion 5
Rational numbers can be represented as a repeated decimal expansion using the decimal function or as a continued fraction using continuedFraction. Any attempt to call these functions with irrational values will fail.
(22) -> decimal(22/7)
______
(22) 3.142857
Type: DecimalExpansion
(23) -> continuedFraction(6543/210)
1 | 1 | 1 | 1 |
(23) 31 + +---+ + +---+ + +---+ + +---+
| 6 | 2 | 1 | 3
Type: ContinuedFraction Integer
Finally, partial fractions in compact and expanded form are available via the functions partialFraction and padicFraction respectively. The former takes two arguments, the first being the numerator of the fraction and the second being the denominator. The latter function takes a fraction and expands it further while the function compactFraction does the reverse:
(24) -> partialFraction(234,40)
3 3
(24) 6 - -- + -
2 5
2
Type: PartialFraction Integer
(25) -> padicFraction(%)
1 1 3
(25) 6 - - - -- + -
2 2 5
2
Type: PartialFraction Integer
(26) -> compactFraction(%)
3 3
(26) 6 - -- + -
2 5
2
Type: PartialFraction Integer
(27) -> padicFraction(234/40)
117
(27) ---
20
Type: PartialFraction Fraction Integer
To extract parts of a partial fraction the function nthFractionalTerm is available and returns a partial fraction of one term. To decompose this further the numerator can be obtained using firstNumer and the denominator with firstDenom. The whole part of a partial fraction can be retrieved using wholePart and the number of fractional parts can be found using the function numberOfFractionalTerms:
(28) -> t := partialFraction(234,40)
3 3
(28) 6 - -- + -
2 5
2
Type: PartialFraction Integer
(29) -> wholePart(t)
(29) 6
Type: PositiveInteger
(30) -> numberOfFractionalTerms(t)
(30) 2
Type: PositiveInteger
(31) -> p := nthFractionalTerm(t,1)
3
(31) - --
2
2
Type: PartialFraction Integer
(32) -> firstNumer(p)
(32) -3
Type: Integer
(33) -> firstDenom(p)
2
(33) 2
Type: Factored Integer
3.4 Modular Arithmetic
By using the type constructor PrimeField? it is possible to do arithmetic modulo some prime number. For example, arithmetic modulo 7 can be performed as follows:
(34) -> x : PrimeField 7 := 5
(34) 5
Type: PrimeField 7
(35) -> x^5 + 6
(35) 2
Type: PrimeField 7
(36) -> 1/x
(36) 3
Type: PrimeField 7
The first example should be read as
``Let x be of type PrimeField? 7 and assign to it the value 5.''
Note that it is only possible to invert non-zero values if the arithmetic is performed modulo a prime number. Thus arithmetic modulo a non-prime integer is possible but the reciprocal operation is undefined and will generate an error. Attempting to use the PrimeField? type constructor with a non-prime argument will generate an error. An example of non-prime modulo arithmetic is:
(37) -> y : IntegerMod 8 := 11
(37) 3
Type: IntegerMod 8
(38) -> y*4 + 27
(38) 7
Type: IntegerMod 8
Note that polynomials can be constructed in a similar way:
(39) -> (3*a^4 + 27*a - 36)::Polynomial PrimeField 7
4
(39) 3a + 6a + 6
Type: Polynomial PrimeField 7
Chapter 4
General Points About FriCAS
This chapter contains a jumble of various points about FriCAS.
4.1 Computation Without Output
It is sometimes desirable to enter an expression and prevent FriCAS from displaying the result. To do this the expression should be terminated with a semicolon ``;''. In Section 3.3 it was mentioned that a set of expressions separated by semicolons would be evaluated and the result of the last one displayed. Thus if a single expression is followed by a semicolon no output will be produced (except for its type):
(1) -> 2 + 4*5;
Type: PositiveInteger
4.2 Accessing Earlier Results
As mentioned in previous sections the ``%'' macro represents the result of the previous computation and some other macros were given in Figure 2.3. To refer to earlier calculations the ``%%'' macro is available which takes a single integer argument. If the argument is positive then it refers to the step number of the calculation where the numbering begins from one and can be seen at the end of each prompt (the number in parentheses). If the argument is negative then it refers to previous results counting backwards from the last result i.e. ``%%(-1)'' is the same as ``%''. The value of ``%%(0)'' is not defined and will generate an error if requested.
4.3 Splitting Expressions Over Several Lines
Although FriCAS will quite happily accept expressions that are longer than the width of the screen (just keep typing without pressing the Return key) it is often preferable to split the expression being entered at a point where it would result in more readable input. To do this the underscore ``_'' symbol is placed before the break point and then the Return key pressed. The rest of the expression is typed on the next line and can be preceded by any number of whitespace characters, for example:
(2) -> 2_
+_
3
(2) 5
Type: PositiveInteger
The underscore symbol is an escape character and its presence alters the meaning of the characters that follow it. As mentioned above whitespace following an underscore is ignored (the Return key generates a whitespace character). Any other character following an underscore loses whatever special meaning it may have had. Thus one can create the identifier ``a+b'' by typing ``a_+b'' although this might lead to confusions. Also note the result of the following example:
(3) -> ThisIsAVeryLong_
VariableName
(3) ThisIsAVeryLongVariableName
Type: Variable ThisIsAVeryLongVariableName
4.4 Comments And Descriptions
Comments and descriptions are really only of use in files of FriCAS code but can be used when the output of an interactive session is being spooled to a file (via the system command )spool). A comment begins with two dashes ``--'' and continues until the end of the line. Multi-line comments are only possible if each individual line begins with two dashes.
Descriptions are the same as comments except that the FriCAS compiler will include them in the object files produced and make them available to the user for documentation purposes. For more details on this refer to [watt1995].
A description placed before a calculation begins with three plus symbols ``+++'' and a description placed after a calculation begins with two plus symbols ``++''.
4.5 Control Of Result Types
This section needs to be rewritten and extended to give a proper description of converting values from one type to another.
In earlier sections the type of an expression was converted to another via the ``::'' operator. However, this is not the only method for converting between types and two other operators need to be introduced and explained.
The first operator is ``$'' and is used to specify the package to be used to calculate the result. Thus:
(4) -> (2/3)$Float
(4) 0.6666666666 6666666667
Type: Float
tells FriCAS to use the ``/'' operator from the Float package to evaluate the expression 2/3. This does not necessarily mean that the result will be of the same type as the domain from which the operator was taken. In the following example the sign operator is taken from the Float package but the result is of type Integer.
(5) -> sign(2.3)$Float
(5) 1
Type: Integer
The other operator is ``@'' which is used to tell FriCAS what the desired type of the result of the calculation is. In most situations all three operators yield the same results but the example below should help to distinguish them.
(6) -> (2 + 3)::String
(6) "5"
Type: String
(7) -> (2 + 3)@String
An expression involving @ String actually evaluated to
one of type PositiveInteger . Perhaps you should use
:: String .
(7) -> (2 + 3)$String
The function + is not implemented in String .
If an expression X is converted using one of the three operators to type T the interpretations are follows:
- ::
- means explicitly convert X to type T if possible.
- $
- means use the available operators for type T to compute X.
- @
- means choose operators to compute X so that the result is of type T.
Chapter 5
Data Structures in FriCAS
This chapter is an overview of some of the data structures provided by FriCAS.
5.1 Lists
The FriCAS List type constructor is used to create homogenous lists of finite size. The notation for lists and the names of the functions that operate over them are similar to those found in functional languages such as ML.
Lists can be created by placing a comma separated list of values inside square brackets or if a list with just one element is desired then the function list is available:
(1) -> [4]
(1) [4]
Type: List PositiveInteger
(2) -> list(4)
(2) [4]
Type: List PositiveInteger
(3) -> [1,2,3,5,7,11]
(3) [1,2,3,5,7,11]
Type: List PositiveInteger
The function append takes two lists as arguments and returns the list consisting of the second argument appended to the first. A single element can be added to the front of a list using cons:
(4) -> append([1,2,3,5],[7,11])
(4) [1,2,3,5,7,11]
Type: List PositiveInteger
(5) -> cons(23,[65,42,19])
(5) [23,65,42,19]
Type: List PositiveInteger
Lists are accessed sequentially so if FriCAS is asked for the value of the twentieth element in the list it will move from the start of the list over nineteen elements before it reaches the desired element. Each element of a list is stored as a node consisting of the value of the element and a pointer to the rest of the list. As a result the two main operations on a list are called first and rest. Both of these functions take a second optional argument which specifies the length of the first part of the list:
(6) -> first([1,5,6,2,3]
(6) 1
Type: PositiveInteger
(7) -> first([1,5,6,2,3],2)
(7) [1,5]
Type: List PositiveInteger
(8) -> rest([1,5,6,2,3])
(8) [5,6,2,3]
Type: List PositiveInteger
(9) -> rest([1,5,6,2,3],2)
(9) [6,2,3]
Type: List PositiveInteger
Other functions are empty? which tests to see if a list contains no elements, member? which tests to see if the first argument is a member of the second, reverse which reverses the order of the list, sort which sorts a list and removeDuplicates which removes any duplicates. The length of a list can be obtained using the ``#'' operator.
(10) -> empty?([7,2,-1,2])
(10) false
Type: Boolean
(11) -> member?(-1,[7,2,-1,2])
(11) true
Type: Boolean
(12) -> reverse([7,2,-1,2])
(12) [2,- 1,2,7]
Type: List Integer
(13) -> sort([7,2,-1,2])
(13) [-1,2,2,7]
Type: List Integer
(14) -> removeDuplicates([1,5,3,5,1,1,2])
(14) [1,5,3,2]
Type: List PositiveInteger
(15) -> #[7,2,-1,2]
(15) 4
Type: PositiveInteger
Lists in FriCAS are mutable and so their contents (the elements and the links) can be modified in situ. Functions that operate over lists in this way have names ending with the symbol ``!''. For example, concat! takes two lists as arguments and appends the second argument to the first (except when the first argument is an empty list) and setrest! changes the link emanating from the first argument to point to the second argument (see Figure 5.1 and Figure 5.2 for a graphical explanation of the following example of setrest!):
(16) -> u := [9,2,4,7]
(16) [9,2,4,7]
Type: List PositiveInteger
(17) -> concat!(u,[1,5,42]); u
(17) [9,2,4,7,1,5,42]
Type: List PositiveInteger
(18) -> endOfu := rest(u,4)
(18) [1,5,42]
Type: List PositiveInteger
(19) -> partOfu := rest(u,2)
(19) [4,7,1,5,42]
Type: List PositiveInteger
(20) -> setrest!(endOfu,partOfu); u
-----
(20) [9,2,4,7,1]
Type: List PositiveInteger
![[Image]](./A Tutorial Introduction To AXIOM_files/setrest.1.gif)
Figure 5.1: List u before setrest(endOfu,partOfu).
![[Image]](./A Tutorial Introduction To AXIOM_files/setrest.2.gif)
Figure 5.2: List u after setrest(endOfu,partOfu).
From this it can be seen that the lists returned by first and rest are pointers to the original list and not a copy. Thus great care must be taken when dealing with lists in FriCAS.
Although the nth element of a list l can be obtained by applying the first function to n-1 applications of rest to l, FriCAS provides a more useful access method in the form of the ``.'' operator:
(21) -> u.3
(21) 4
Type: PositiveInteger
(22) -> u.5
(22) 1
Type: PositiveInteger
(23) -> u.6
(23) 4
Type: PositiveInteger
(24) -> first rest rest u -- Same as u.3
(24) 4
Type: PositiveInteger
(25) -> u.first
(25) 9
Type: PositiveInteger
(26) -> u(3)
(26) 4
Type: PositiveInteger
The operation u.i is referred to as indexing into u or elting into u. The latter term comes from the elt function which is used to extract elements (the first element of the list is at index 1).
(27) -> elt(u,4) -- Same as u.4
(27) 7
Type: PositiveInteger
If a list has no cycles then any attempt to access an element beyond the end of the list will generate an error. However, in the example above there was a cycle starting at the third element so the access to the sixth element wrapped around to give the third element. Since lists are mutable it is possible to modify elements directly:
(28) -> u.3 := 42; u
------
(28) [9,2,42,7,1]
Type: List PositiveInteger
Other list operations are:
(29) -> L := [9,3,4,7]; #L
(29) 4
Type: PositiveInteger
(30) -> last(L)
(30) 7
Type: PositiveInteger
(31) -> L.last
(31) 7
Type: PositiveInteger
(32) -> L.(#L - 1)
(32) 4
Type: PositiveInteger
Using the ``#'' operator on a list with cycles causes
FriCAS to enter an infinite loop.
Note that any operation on a list L that returns a list L' will, in general, be such that any changes to L' will have the side-effect of altering L. For example:
(33) -> m := rest(L,2)
(33) [4,7]
Type: List PositiveInteger
(34) -> m.1 := 20; L
(34) [9,3,20,7]
Type: List PositiveInteger
(35) -> n := L
(35) [9,3,20,7]
Type: List PositiveInteger
(36) -> n.2 := 99; L
(36) [9,99,20,7]
Type: List PositiveInteger
(37) -> n
(37) [9,99,20,7]
Type: List PositiveInteger
Thus the only safe way of copying lists is to copy each element from one to another and not use the assignment operator:
(38) -> p := [i for i in n] -- Same as `p := copy(n)'
(38) [9,99,20,7]
Type: List PositiveInteger
(39) -> p.2 := 5; p
(39) [9,5,20,7]
Type: List PositiveInteger
(40) -> n
(40) [9,99,20,7]
Type: List PositiveInteger
In the previous example a new way of constructing lists was given. This is a powerful method which gives the reader more information about the contents of the list than before and which is extremely flexible. The example,
(41) -> [i for i in 1..10]
(41) [1,2,3,4,5,6,7,8,9,10]
Type: List PositiveInteger
should be read as
``Using the expression i, generate each element of the list by iterating the symbol i over the range of integers [1,10]?.''
To generate the list of the squares of the first ten elements we just use:
(42) -> [i^2 for i in 1..10]
(42) [1,4,9,16,25,36,49,64,81,100]
Type: List PositiveInteger
For more complex lists we can apply a condition to the elements that are to be placed into the list thus to obtain a list of even numbers between 0 and 11:
(43) -> [i for i in 1..10 | even?(i)]
(43) [2,4,6,8,10]
Type: List PositiveInteger
This example should be read as
``Using the expression i, generate each element of the list by iterating the symbol i over the range of integers [1,10]? such that i is even.''
The following achieves the same result:
(44) -> [i for i in 2..10 by 2]
(44) [2,4,6,8,10]
Type: List PositiveInteger
5.2 Segmented Lists
A segmented list is one in which some of the elements are ranges of values. The expand function converts lists of this type into ordinary lists:
(45) -> [1..10]
(45) [1..10]
Type: List Segment PositiveInteger
(46) -> [1..3,5,6,8..10]
(46) [1..3,5..5,6..6,8..10]
Type: List Segment PositiveInteger
(47) -> expand(%)
(47) [1,2,3,5,6,8,9,10]
Type: List Integer
If the upper bound of a segment is omitted then a different type of segmented list is obtained and expanding it will produce a stream (which will be considered in the next section):
(48) -> [1..]
(48) [1..]
Type: List UniversalSegment PositiveInteger
(49) -> expand(%)
(49) [1,2,3,4,5,6,7,8,9,10,...]
Type: Stream Integer
5.3 Streams
Streams are infinite lists which have the ability to calculate the next element should it be required. For example, a stream of positive integers and a list of prime numbers can be generated by:
(50) -> [i for i in 1..]
(50) [1,2,3,4,5,6,7,8,9,10,...]
Type: Stream PositiveInteger
(51) -> [i for i in 1.. | prime?(i)]
(51) [2,3,5,7,11,13,17,19,23,29,...]
Type: Stream PositiveInteger
In each case the first few elements of the stream are calculated for display purposes but the rest of the stream remains unevaluated. The value of items in a stream are only calculated when they are needed which gives rise to their alternative name of ``lazy lists''.
Another method of creating streams is to use the generate(f,a) function. This applies it's first argument repeatedly onto it's second to produce the stream [a,f(a),f(f(a)),f(f(f(a))) ...]?. Given that the function nextPrime returns the lowest prime number greater than it's argument we can generate a stream of primes as follows:
(52) -> generate(nextPrime,2)$Stream Integer
(52) [2,3,5,7,11,13,17,19,23,29,...]
Type: Stream Integer
As a longer example a stream of Fibonacci numbers will be computed. The Fibobacci numbers start at 1 and each following number is the addition of the two numbers that precede it i.e. 1,1,2,3,5,8,... The idea behind this example is from [jenks1992, page 457] but the explanation and construction below is that of the author's.
Since the generation of any Fibonacci number only relies on knowing the previous two numbers we can look at the series through a window of two elements. To create the series the window is placed at the start over the values [1,1]? and their sum obtained. The window is now shifted to the right by one position and the sum placed into the empty slot of the window; the process is then repeated. To implement this we require a function that takes a list of two elements (the current view of the window), adds them and outputs the new window. The result is the function [a,b]? -> [b,a+b]?:
(53) -> win : List Integer -> List Integer
Type: Void
(54) -> win(x) == [x.2, x.1 + x.2]
Type: Void
(55) -> win([1,1])
(55) [1,2]
Type: List Integer
(56) -> win(%)
(56) [2,3]
Type: List Integer
(57) -> win(%)
(57) [3,5]
Type: List Integer
(For more details on functions definitions see Section 6.3.)
Thus it can be seen that repeatedly applying win to the results of the previous invocation, each element of the series is obtained. Clearly win is an ideal function to construct streams using the generate function:
(58) -> fibs := [generate(win,[1,1])]
(58) [[1,1],[1,2],[2,3],[3,5],[5,8],[8,13],...]
Type: Stream List Integer
This isn't quite what is wanted - we need to extract the first element of each list and place that in our series:
(59) -> fibs := [i.1 for i in [generate(win,[1,1])]]
(59) [1,1,2,3,5,8,13,21,34,55,...]
Type: Stream Integer
Obtaining the 200th Fibonacci number is trivial:
(60) -> fibs.200
(60) 280571172992510140037611932413038677189525
Type: PositiveInteger
One other function of interest is complete which expands a finite stream derived from an infinite one (and thus was still stored as an infinite stream) to form a finite stream.
5.4 Arrays, Vectors, Strings and Bits
The simplest array data structure is the one-dimensional array which can be obtained by applying the oneDimensionalArray function to a list:
(61) -> oneDimensionalArray([7,2,5,4,1,9])
(61) [7,2,5,4,1,9]
Type: OneDimensionalArray PositiveInteger
One-dimensional arrays are homogenous (all the elements must have the same type) and mutable like lists but unlike lists they are constant in size and have uniform access time (it is just as quick to read the last element of a one-dimensional array as it is to read the first: this is not true for lists).
Since these arrays are mutable all the warnings that apply to lists apply to arrays i.e. it is possible to modify an element in a copy of an array and change the original:
(62) -> x := %
(62) [7,2,5,4,1,9]
Type: OneDimensionalArray PositiveInteger
(63) -> y := x
(63) [7,2,5,4,1,9]
Type: OneDimensionalArray PositiveInteger
(64) -> y.3 := 20; x
(64) [7,2,20,4,1,9]
Type: OneDimensionalArray PositiveInteger
Note that because these arrays are of fixed size the concat! function cannot be applied to them without generating an error. If arrays of this type are required use the FlexibleArray? type constructor (see Section 5.5).
One-dimensional arrays can be created using new which specifies the size of the array and the initial value for each of the elements. Other operations that can be applied to one-dimensional arrays are map! which applies a mapping onto each element, swap! which swaps two elements and copyInto!(a,b,c) which copies the array b onto a starting at position c:
(65) -> a : ARRAY1 PositiveInteger := new(10,3)
(65) [3,3,3,3,3,3,3,3,3,3]
Type: OneDimensionalArray PositiveInteger
(66) -> map!(i +-> i+1,a); a
(66) [4,4,4,4,4,4,4,4,4,4]
Type: OneDimensionalArray Integer
(67) -> b := oneDimensionalArray([2,3,4,5,6])
(67) [2,3,4,5,6]
Type: OneDimensionalArray PositiveInteger
(68) -> swap!(b,2,3); b
(68) [2,4,3,5,6]
Type: OneDimensionalArray PositiveInteger
(69) -> copyInto!(a,b,3)
(69) [4,4,2,4,3,5,6,4,4,4]
Type: OneDimensionalArray PositiveInteger
(70) -> a
(70) [4,4,2,4,3,5,6,4,4,4]
Type: OneDimensionalArray PositiveInteger
(note that ARRAY1 is an abbreviation for the type OneDimensionalArray?.) Other types based on one-dimensional arrays are Vector, String and Bits:
(71) -> vector([1/2,1/3,1/4])
1 1 1
(71) [-,-,-]
2 3 4
Type: Vector Fraction Integer
(72) -> "Hello World"
(72) "Hello World"
Type: String
(73) -> bits(8,true)
(73) "11111111"
Type: Bits
A vector is similar to a one-dimensional array except that if it's components belong to a ring then arithmetic operations are provided.
5.5 Flexible Arrays
Flexible arrays are designed to provide the efficiency of one-dimensional arrays while retaining the flexibility of lists. They are implemented by allocating a fixed block of storage for the array. If the array needs to be expanded then a larger block of storage is allocated and the contents of the old block are copied into the new one.
There are several operations that can be applied to this type, most of which modify the array in situ. As a result these functions all have names ending in ``!''. All the functions in the example below are fairly obvious. The physicalLength returns the actual length of the array as stored in memory while the physicalLength! allows this value to be changed by the user.
(74) -> f : FARRAY INT := new(6,1)
(74) [1,1,1,1,1,1]
Type: FlexibleArray Integer
(75) -> f.1 := 4;f.2 := 3;f.3 := 8;f.5 := 2;f
(75) [4,3,8,1,2,1]
Type: FlexibleArray Integer
(76) -> insert!(42,f,3); f
(76) [4,3,42,8,1,2,1]
Type: FlexibleArray Integer
(77) -> insert!(28,f,8); f
(77) [4,3,42,8,1,2,1,28]
Type: FlexibleArray Integer
(78) -> removeDuplicates!(f)
(78) [4,3,42,8,1,2,28]
Type: FlexibleArray Integer
(79) -> delete!(f,5)
(79) [4,3,42,8,2,28]
Type: FlexibleArray Integer
(80) -> g := f(3..5)
(80) [42,8,2]
Type: FlexibleArray Integer
(81) -> g.2 := 7; f
(81) [4,3,42,8,2,28]
Type: FlexibleArray Integer
(82) -> insert!(g,f,1)
(82) [42,7,2,4,3,42,8,2,28]
Type: FlexibleArray Integer
(83) -> physicalLength(f)
(83) 10
Type: PositiveInteger
(84) -> physicalLength!(f,20)
(84) [42,7,2,4,3,42,8,2,28]
Type: FlexibleArray Integer
(85) -> merge!(sort!(f),sort!(g))
(85) [2,2,2,3,4,7,7,8,28,42,42,42]
Type: FlexibleArray Integer
(86) -> shrinkable(false)$FlexibleArray(Integer)
(86) true
Type: Boolean
There are several things to point out concerning the previous examples. Firstly although flexible arrays are mutable, making copies of these arrays creates separate entities. This can be seen by the fact that the modification of element b.2 above did not alter a. Secondly, the merge! function can take an extra argument before the two arrays being merged. The argument is a comparison function and defaults to <= if omitted. Lastly, shrinkable tells the FriCAS system whether or not to let flexible arrays contract when elements are deleted from them. An explicit package reference must be given as in the example above.
Although there are several other data structures that ought to be covered here such as sets and records, I want to move on to more important areas such as functions and iteration before finishing this chapter off.
Chapter 6
Functions, Choices And Loops
By now the reader should be able to construct simple one-line expressions involving variables and different data structures. This chapter builds on this knowledge and shows how to use iteration, make choices and build functions in FriCAS. At the moment it is assumed that the reader has a rough idea of how types are specified and constructed so that they can follow the examples given. A more detailed coverage of types in FriCAS will be provided in a later chapter (sometime in the future!).
From this point on most examples will be taken from input files. The prompt for such examples is faked and should actually contain a command such as ``)read eg01.input''. There may be jumps in the step numbers of the examples due to the way FriCAS calculates them and due to the editing done on the output. If the example code is free from bugs then a value and type for the code will be given otherwise just the code will be displayed
Although the author has not covered this topic yet please make do with the following snippet until I write that section:
6.1 Reading Code From A File
- The names of all input files in FriCAS should end in the suffix ``.input'' otherwise FriCAS will refuse to consult them.
- Use the command )read fred.input to read and interpret the contents of the file ``fred.input''.
- To start everything afresh before reading in an input file enter the command )clear all or put it at the start of the file.
6.2 Blocks
The FriCAS constructs that provide looping, choices and user-defined functions all rely on the notion of blocks. According to [jenks1992, page 112] a block is a sequence of expressions which are evaluated in the order that they appear except when it is modified by control expressions such as loops. To leave a block prematurely use the expression BoolExpr? => Expr where BoolExpr? is any FriCAS expression that has type Boolean. The value and type of Expr determines the value and type returned by the block.
If blocks are entered at the keyboard (as opposed to reading code in from a text file) then there is only one way of creating them; the syntax is:
( expression1 ; expression2 ; ... ; expressionN )
In an input file a block can be constructed as above or by placing all the statements at the same indentation level. In this situation the block is called a pile. As an example of a simple block a list of three integers can be constructed using parentheses
(1) -> (a := 4;b := 1; c := 9; L := [a,b,c])
(1) [4,1,9]
Type: List PositiveInteger
or using piles
(2) -> L :=
a := 4
b := 1
c := 9
[a,b,c]
(2) [4,1,9]
Type: List PositiveInteger
Since blocks have a type and a value they can be used as arguments to functions or as part of other expressions. It should be pointed out that the following example is not recommended practice but helps to illustrate the idea of blocks and their ability to return values:
(3) -> sqrt(4.0 +
a := 3.0
b := 1.0
c := a + b
c
)
(3) 2.8284271247 461900976
Type: Float
Note that indentation is extremely important. If the example given above had the pile starting at ``a :='' moved left by two spaces so that the ``a'' was under the ``('' of the first line then the interpreter would signal an error. Furthermore, if the closing bracket ``)'' is moved up to give:
(4) -> sqrt(4.0 +
a := 3.0
b := 1.0
c := a + b
c)
then the parser will generate errors and if the bracket is shifted right by several spaces so that it is in line with the ``c'' similar errors will be raised. Finally, the ``)'' must be indented by at least one space otherwise more errors will be generated.
Thus it can be seen that great care needs to be taken when constructing input files consisting of piles of expressions. It would seem prudent to add one pile at a time and check it is acceptable before adding more, particularly if piles are nested. However, it should be pointed out that the use of piles as values for functions is not very readable and so perhaps the delicate nature of their interpretation should deter programmers from using them in these situations. Using piles should really be restricted to constructing functions etc. and a small amount of rewriting can remove the need to use them as arguments. For example, the previous block could easily be implemented as:
(4) -> a := 3.0
b := 1.0
c := a + b
sqrt(4.0 + c)
(4) 2.8284271247 461900976
Type: Float
which achieves the same result and is easier to understand. Note that this is still a pile but it is not as fragile as the previous version.
6.3 Functions
Definitions of functions in FriCAS are quite simple providing two things are observed. Firstly the type of the function must either be completely specifed or completely unspecified and secondly the body of the function is assigned to the function identifier using the delayed assignment operator ``==''.
To specify the type of something the ``:'' operator is used. Thus to define a variable x to be of type Fraction Integer we enter:
(5) -> x : Fraction Integer
Type: Void
For functions the method is the same except that the arguments to are placed in parentheses and the return type is placed after the symbol ``->''. More details on type definitions will be given later which will explain this more fully. For now an example of type definitions for functions taking zero, one, two and three integer arguments and returning a list of integers are given:
(6) -> f : () -> List Integer
Type: Void
(7) -> g : (Integer) -> List Integer
Type: Void
(8) -> h : (Integer, Integer) -> List Integer
Type: Void
(9) -> k : (Integer, Integer, Integer) -> List Integer
Type: Void
Now the actual definition of the functions might be:
(10) -> f() == []
Type: Void
(11) -> g(a) == [a]
Type: Void
(12) -> h(a,b) == [a,b]
Type: Void
(13) -> k(a,b,c) == [a,b,c]
Type: Void
with some invokations of these functions:
(14) -> f()
(14) []
Type: List Integer
(15) -> g(4)
(15) [4]
Type: List Integer
(16) -> h(2,9)
(16) [2,9]
Type: List Integer
(17) -> k(-3,42,100)
(17) [-3,42,100]
Type: List Integer
The value returned by a function is either the value of the last expression evaluated or the result of a return statement. For example the following are effectively the same:
(18) -> p : Integer -> Integer
p x ==
a := 1
b := 2
a + b + x
Type: Void
(19) -> p : Integer -> Integer
p x ==
a := 1
b := 2
return a + b + x
Type: Void
Note that a block (pile) is assigned to the function identifier p and thus all the rules about blocks apply to function definitions. Also there was only one argument so the parentheses were discarded.
This is basically all that one needs to know about defining functions in FriCAS - first specify the complete type and then assign a block to the function. The rest of this chapter is concerned with defining more complex blocks than those in this section and as a result function definitions will crop up continually particularly since they are a good way of testing examples.
6.4 Choices
Apart from the ``=>'' operator that allows a block to be left before the end FriCAS provides the standard if-then-else construct. The general syntax is:
if BooleanExpr? then Expr1 else Expr2
where ``else Expr2'' can be omitted. If the expression BooleanExpr? evaluates to true then Expr1 is executed otherwise Expr2 (if present) will be. An example of piles and if-then-else in FriCAS from [jenks1992, page 114] is given below:
(20) -> h := 2.0
if h > 3.1 then
1.0
else
z := cos(h)
max(z,0.5)
(20) 0.5
Type: Float
Note the indentation - the ``else'' must be indented relative to the ``if'' otherwise it will generate an error (FriCAS will think there are two piles, the second one beginning with ``else'').
Any expression that has type Boolean can be used as BooleanExpr? and the most common will be those involving the relational operators ``>'', ``<'' and ``=''. Usually the type of an expression involving the equality operator ``='' will be Boolean but in those situations when it isn't you may need to use the ``@'' operator to ensure that it is.
6.5 Loops
Loops in FriCAS are regarded as expressions containing another expression called the loop body. The loop body is executed zero or more times depending on the type of the loop. Loops can be nested to any depth.
6.5.1 The repeat Loop
The simplest type of loop provided by FriCAS is the repeat loop. The general syntax of this is:
repeat loopBody
This will cause FriCAS to execute loopBody repeatedly until either a break or return statement are encountered. If loopBody contains neither of these statements then it will loop forever. The following piece of code will display the numbers from 1 to 4:
(21) -> i := 1
repeat
if i > 4 then break
output(i)
i := i + 1
1
2
3
4
Type: Void
Note: In FriCAS Release 1.3.5 the break keyword replaces leave which was used in old AXIOM versions. Use of leave will generate an error if it is used with FriCAS.
It was mentioned that loops will only be left when either a break or return statement is encountered so why can't one use the ``=>'' operator? The reason is that the ``=>'' operator tells FriCAS to leave the current block whereas break and return tell FriCAS to leave the current loop (the latter actually tells FriCAS to leave the current function which could mean leaving several levels of loop if necessary). An example of this is given in [jenks1992] and is provided here for reference:
(22) -> i := 0
repeat
i := i + 1
i > 3 => i
output(i)
1
2
3
^C
>> Sytem error:
Console interrupt.
Here the ``=>'' operator instructs FriCAS to leave the block when the value of i reaches 4 but then the loop continues to execute the first statement (increment i) forever (or until the user interrupts it). However, the break keyword can be used to represent a return value so we can combine the two previous examples as follows:
(22) -> i := 0
repeat
i := i + 1
i > 3 => break
output(i)
1
2
3
Type: Void
To skip the rest of a loop body and begin the next iteration of the loop one uses the iterate keyword:
(23) -> i := 0
repeat
i := i + 1
if i > 6 then break
-- Return to start if i is odd.
if odd?(i) then iterate
output(i)
2
4
6
Type: Void
6.5.2 The while Loop
The while statement extends the basic repeat loop to place the control of leaving the loop at the start rather than have it buried in the middle. Since the body of the loop is still part of a repeat loop, break and ``=>'' work in the same way as in the previous section. The general syntax of a while loop is:
while BoolExpr? repeat loopBody
As before, BoolExpr? must be an expression of type Boolean. Before the body of the loop is executed BoolExpr? is tested. If it evaluates to true then the loop body is entered otherwise the loop is terminated. Multiple conditions can be applied using the logical operators such as and or by using several while statements before the repeat. The following examples are from [jenks1992, page 122]:
(24) -> x := 1; y := 1
while x < 4 and y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
[1,1]
[2,3]
[3,5]
Type: Void
(25) -> x := 1; y := 1
while x < 4 while y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
[1,1]
[2,3]
[3,5]
Type: Void
Note that the last example using two while statements is not a nested loop but the following one is:
(26) -> x := 1; y := 1
while x < 4 repeat
while y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
[1,1]
[2,3]
[3,5]
[4,7]
[5,9]
Type: Void
As a longer example the following is taken from [jenks1992, page 123] although the matrix used is different. Given a matrix of arbitrary size, find the position and value of the first negative element by examining the matrix in row-major order:
(27) -> m := matrix [[21,37,53,14],_
[8,22,-24,16],_
[2,10,15,14],_
[26,33,55,-13]]
+21 37 53 14 +
| |
|8 22 - 24 16 |
(27) | |
|2 10 15 14 |
| |
+26 33 55 - 13+
Type: Matrix Integer
(28) -> lastrow := nrows(m); lastcol := ncols(m)
r := 1
while r <= lastrow repeat
c := 1 -- Index of first column
while c <= lastcol repeat
if elt(m,r,c) < 0 then
output [r,c,elt(m,r,c)]
r := lastrow
break -- Don't look any further
c := c + 1
r := r + 1
[2,3,-24]
Type: Void
6.5.3 The for Loop
The last loop of interest is the for loop. There are two ways of creating a for loop and the general syntax for both is as follows (with and without the ``such that'' predicates):
for var in seg repeat loopBody
for var in list repeat loopBody
for var in seg | BoolExpr? repeat loopBody
for var in list | BoolExpr? repeat loopBody
where var is an index variable which is iterated over the values in seg or list. The value seg is a segment e.g. 1..10 or 1.. and list is a list of some type. The last two types of for loop will only execute the statements in loopBody if BoolExpr? evaluates to true. Some examples of this type of loop are given below:
(29) -> for i in 1..10 repeat
~prime?(i) => iterate
output(i)
2
3
5
7
Type: Void
(30) -> for i in 1..10 | prime?(i) repeat
output(i)
2
3
5
7
Type: Void
(31) -> for w in ["This", "Is", "Your", "Life!"] repeat
output(w)
This
Is
Your
Life
Type: Void
(32) -> for i in 1.. repeat
if even?(i) then output(i)
if i < 7 then iterate
break
2
4
6
Type: Void
The last example loop can be simplified by adding a while clause:
(33) -> for i in 1.. while i < 7 repeat
if even?(i) then output(i)
2
4
6
Type: Void
and by using the ``such that'' clause it becomes even simpler:
(34) -> for i in 1.. | even?(i) while i < 7 repeat
output(i)
2
4
6
Type: Void
Similarly it is possible to have multiple for clauses on a line to iterate over several symbols in parallel:
(35) -> for a in 1..4 for b in 5..8 repeat
output [a,b]
[1,5]
[2,6]
[3,7]
[4,8]
Type: Void
As a general point it should be noted that any symbols referred to in the ``such that'' and while clauses must be pre-defined. This either means that the symbols must have been defined in an outer level (e.g. in an enclosing loop) or in a for clause appearing before the ``such that'' or while. For example,
(36) -> for a in 1..4 repeat
for j in 7..9 | prime?(a + b) repeat
output [a,b,a + b]
[2,9,11]
[3,8,11]
[4,7,11]
[4,9,13]
Type: Void
is legal but
(37) -> for b in 7..9 | prime?(a + b) repeat
for a in 1..4 repeat
output [a,b,a + b]
is not and will generate an error because is not defined in the first line.
Finally it is often useful to be able to use a segment in which the elements are in decreasing order. To do this the by keyword is used:
(38) -> for a in 1..4 for b in 8..5 by -1 repeat
output [a,b]
[1,8]
[2,7]
[3,6]
[4,5]
Type: Void
Note that without ``by -1'' the loop body would never be executed (the segment 8..5 is empty so there is nothing to iterate over):
(39) -> for a in 1..4 for b in 8..5 by -1 repeat
output [a,b]
Type: Void
Bibliography
- [jenks1992]?
- Richard D. Jenks and Robert S. Sutor. AXIOM: the scientific computation system. NAG Ltd., 1992.
- [watt1995]?
- Stephen M. Watt, Peter A. Broadbery, Samuel S. Dooley, Pietro Iglio, Scott C. Morrison, Jonathon M. Steinbach, and Robert S. Sutor. AXIOM Library Compiler User Guide. NAG Ltd., first edition, March 1995. Reprinted with corrections from November 1994.
Martin Dunstan (mnd@dcs.st-andrews.ac.uk)
Updated: 2nd May, 1996.