This is documentation for the RATIO.4TH file. These are lists of rational numbers.
*******************************************************************************
*******************************************************************************
*******************************************************************************
We start out by defining our list of rationals:
list
d field .num \ signed numerator the sign of the numerator is the sign of the ratio
w field .den \ unsigned denominator
constant ratio
\ The denominator can be zero, which indicates infinity; the sign of the numerator is still valid.
\ The numerator is a double to help support ratios larger than one.
: init-ratio ( Dnum den node -- node )
init-list >r
dup 0< abort" *** INIT-RATIO doesn't allow negative denominators ***"
r@ .den !
r@ .num 2!
r@ <simplify>
r> ;
: new-ratio ( Dnum den -- node )
ratio alloc
init-ratio ;
Our RATIO data structure consists of the .NUM and .DEN fields (the numerator and denominator). These fields are appended onto the basic LIST data structure. You don't need to know what fields are in the LIST data structure in order to use it. This is information hiding --- you can ignore low-level details such as this.
Note that INIT-RATIO and NEW-RATIO are separate words. This was done so that we can later write a new type of list that is derived from RATIO in the same way that RATIO was derived from LIST. That type, lets call it XXX, will have a function INIT-XXX that calls INIT-RATIO in a similar manner to how INIT-RATIO called its parent constructor INIT-LIST. These initialization functions are very similar to the constructors that are used in OOP languages. As an example, you could define a new data-type NAMED-RATIO like this:
ratio
w field .name \ pointer to str
constant named-ratio
: init-named-ratio ( str Dnum den node -- node )
init-ratio >r
r@ .name !
r> ;
: new-named-ratio ( str Dnum den -- node )
named-ratio alloc
init-named-ratio ;
The INIT-NAMED-RATIO function first calls INIT-RATIO to take care of the initialization of the RATIO fields (.NUM and .DEN). It then does the initialization of the NAMED-RATIO fields (.NAME in this case).
Note that in an earlier release of LIST.4TH, it was necessary for NEW-NAMED-RATIO to call INIT-LIST after calling INIT-RATIO. This is no longer necessary.
Note that if you have a chain of data types derived in terms of each other, you only have to call the constructor for the immediate parent. You don't have to call the constructor for every data type in the chain, because the constructor of the parent calls its parent's constructor, which calls its parent's constructor, and so forth back to the most basic constructor, which is INIT-LIST.
Our INIT-RATIO called the word <SIMPLIFY> to reduce the fraction down to its simplest terms. We always want our fractions reduced to their simplest terms in order to prevent them from overflowing during arithmetic, and also so that they print out in a readable manner. For example, consider this code:
42. 56 new-ratio
This creates a ratio on the heap with a 3 being stored in the .NUM field, and a 4 in the .DEN field.
We also have a SIMPLIFY word:
: simplify ( head -- )
['] <simplify> each ;
SIMPLIFY simplifies an entire list of nodes. EACH traverses the list and calls the function that is provided as an XT (<SIMPLIFY> in this case) for each node. That function is given the node address as a parameter, which it consumes. EACH is the standard way to loop through a list. We have words like SIMPLIFY that do something to each element of the list, but they don't contain any explicit looping constructs, such as the DO loops, and neither yet do they contain any recursive calls. This is more information hiding. The mechanism of looping is buried inside of EACH and the programmer doesn't have know anything about the low-level details of this is done. The result is less error-prone code than would result from boiler-plate looping code having to be rewritten every time that the programmer needed to loop through a list.
We need a way to easily construct lists of rationals. For that we have MAKE-RATIO:
min-signed constant | \ the bad number used as a bracket
\ The MIN-SIGNED value hopefully won't be used by accident, but this would cause a bug.
: make-ratio ( bad n... bad -- head ) \ fills numerators, sets denominators to 1
>r \ r: -- bad
nil begin over r@ <> while \ -- bad n... head
swap s>d 1 new-ratio swap link repeat
swap r> 2drop ; \ throw away the two bads
\ MAKE-RATIO only accepts single-precision numerators.
\ Our .NUM field is double-precision in order to support ratios greater than one.
A sequence of numbers is provided, bracketed between | marks, which are invalid numbers --- like this:
| 4 -3 6 9 -1 2 1 | make-ratio
We can find print out the contents of a ratio list like this:
dup show-ratio
This prints out the list as: | 4 -3 6 9 -1 2 1 |. MAKE-RATIO assumes that the denominator is 1. We can set the denominators to other values however. We use SET-DENS to do this:
: ttt ( -- head )
| 4 -3 6 9 -1 2 1 | make-ratio >r
| 8 2 3 3 7 8 7 | r> set-dens ;
When we run TTT, we get this list: | 1/2 -1-1/2 2 3 -1/7 1/4 1/7 |. Note that, in the case of negative numbers, only the numerator is negative. The denominator has to be positive whether the number is positive or negative. We can also add integers to our list like this:
: ttt ( -- head )
| 4 -3 6 9 -1 2 1 | make-ratio >r
| 8 2 3 3 7 8 7 | r> set-dens >r
| 0 0 -1 0 -1 3 1 | r> add-ints ;
When we run TTT, we get this list: | 1/2 -1-1/2 1 3 -1-1/7 3+1/4 1+1/7 |. As a convention when constructing literal lists like this, the integer portion should have the same sign as the fractional portion. This isn't strictly necessary, but it does help readability. I broke this rule myself in the above, where I had a positive fractional part (6/3) and a negative integer part (-1), for a result of 1 (6/3-1=1).
We can convert ratios to and from floats:
: ratio>float { node -- float }
: float>ratio ( float -- node )
1. 5 new-ratio
dup ratio>float f.
Ratios can be more accurate than floats because floats approximate many ratios. In the above, for example, the float printed out is: 0.1999999
We have several words that modify lists:
: <ratio-negate> { node -- }
: ratio-negate ( head -- ) \ negate all of the nodes in head-list
: <ratio-invert> { node -- }
: ratio-invert ( head -- ) \ invert all of the nodes in head-list
: <ratio-sq> { node -- }
: ratio-sq ( head -- ) \ square all of the nodes in head-list
: <ratio-sqrt> { node -- }
: ratio-sqrt ( head -- ) \ square-root all of the nodes in head-list
The pattern here is that the words inside of pointy brackets modify a single node, and the corresponding word without the brackets modifies an entire list. For example <RATIO-SQRT> converts a node into its square root, where as RATIO-SQRT converts every element of a list into its square root. For the most part, you can ignore the pointy-bracket versions and just deal with entire lists at a time. If a list has only one element in it, then the two versions are the same. Consider this example:
2. 3 new-ratio dup <ratio-sqrt> show-ratio
2. 3 new-ratio dup ratio-sqrt show-ratio
In both cases, the result is: | 47140451/57735026 |. The following are several results obtained by different means:
0.8164965752 47140451/57735026 converted into a float
0.8164965 pocket calculator
0.816496580927726 Factor listener
Our RATIO-SQRT is roughly comparable to an 8-digit pocket calculator in accuracy.
We have functions for multiplication and addition:
: <multiply-ratio> ( dest node -- dest )
: product-ratio ( product-node head -- ) \ multiply all of head-list into product-node
: *ratio ( multiplier head -- ) \ multiply multiplier into all of the nodes in head-list
: <add-ratio> ( dest node -- dest ) \ adds node to dest
: sum-ratio ( sum-node head -- ) \ add all of head-list into the sum-node
: +ratio ( addend head -- ) \ add addend to all of the nodes in head-list
The pointy-bracket functions are for single nodes and should generally be ignored. For multiplication, you use either PRODUCT-RATIO or *RATIO, and for addition you use either SUM-RATIO or +RATIO. Notice that PRODUCT-RATIO and SUM-RATIO multiply and add every element in the head-list into a single node. By comparison, *RATIO and +RATIO multiply and add a single node into every element in the head-list.
We also have a function for comparing rationals:
-1 constant A>B
0 constant A=B
1 constant A<B
: ratio-compare ( nodeA nodeB -- A>B | A=B | A<B )
RATIO-COMPARE compares two nodes and returns one of the constants: A>B, A=B or A<B. RATIO-COMPARE is used internally in RATIO-SORT:
: <ratio-sort> ( new-node node -- new-node ? )
over ratio-compare A>B = ;
: ratio-sort ( head -- )
['] <ratio-sort> sort-list ;
The SORT-LIST function works on any list, and not just RATIO lists. The programmer has to provide a function that compares two nodes, whatever their type may be. If this comparer function returns TRUE for a > comparison, then the list will be sorted in an ascending order. Our RATIO-SORT does, in fact, sort in an ascending order. If you want descending, then you would have to write your own sorting function. Easier than this however, would be to use RATIO-SORT and then call the REVERSE function afterward. REVERSE reverses the order of any list, no matter what type.
We have functions that search for nodes within lists:
: find-node ( i*x head toucher -- j*x node|false ) \ toucher: i*x node -- j*x flag
: find-prior ( i*x head toucher -- j*x node|false ) \ toucher: i*x node -- j*x flag
: find-prev ( head node -- prev ) \ finds the node prior to node; nil if node = head
: tail ( head -- node ) \ finds the tail node in the list
: nth ( head n -- node ) \ returns nil if n is >= to the length of the list
: insert ( 1stHead 2ndMiddle -- ) \ insert 1st list into 2nd list after 2ndMiddle node
: remove ( head node -- new-head new-node ) \ removes the node from the list and returns it as a lone node
FIND-NODE is similar to EACH except that the function it is given doesn't just consume its node parameter, but also returns a flag indicating if this is the node we are looking for. FIND-NODE will stop traversing the list at this time, and will return that node. If FIND-NODE traverses the entire list without finding a good node, it returns FALSE. FIND-PRIOR is similar to FIND-NODE except that it returns the node prior to the found node. If the found node is the head of the list and there is no prior node, then FIND-PRIOR returns -1. FIND-PRIOR returns FALSE if it doesn't find a good node at all, just like FIND-NODE. FIND-PREV finds the node that is previous to a node that you already have found. TAIL finds the tail of the list, and NTH finds a node at an index into the list. Our RATIO implementation doesn't use any of these searching functions directly, although SORT-LIST does use FIND-PRIOR internally.
INSERT is used for inserting a list into the middle of another list. You might find a node in a list using FIND-NODE, FIND-PRIOR, FIND-PREV or NTH, and then use INSERT to insert a list into your list after that found node. INSERT can insert an entire list, or just a single node. REMOVE can remove a node from a list and return it as a lone node not attached to any list. Note that you can't REMOVE the head node of list.
For linking two lists together, we have LINK. The two lists are assumed to be not already in the same list. For breaking a list apart, we have DELINK. The two lists are assumed to be in the same list. We also have DELINK-ONE, etc., that delink a specified number of nodes from the front of the list.
: link ( 1stHead 2ndHead -- NewHead ) \ makes one list
: delink ( 1stHead 2ndHead -- 1stHead 2ndHead ) \ makes two lists
: delink-one ( head -- head rest )
: delink-two ( head -- head rest )
: delink-three ( head -- head rest )
: delink-four ( head -- head rest )
Our list program can compile in error-checking, which is the default, or not compile error-checking, which is faster. At the front of the program there is a constant SAFE? that is TRUE by default, causing error-checking to be compiled. Set this to FALSE before compiling LIST.4TH to turn off error checking. In regard to LINK and DELINK, the error-checking makes sure that the nodes are not in the same list, or are in the same list, respectively.
Some of our functions modify the list that they work on. An example would be RATIO-SQRT, that changes every element in the list into its square root. If you want to keep your original list, you need to clone it and then give the clone to the function that modifies its argument.
: clone-node ( node -- new-node ) \ returns a list with only one node in it
: clone-list ( head -- new-head )
We have the functions CLONE-NODE and CLONE-LIST that clone a node or an entire list. CLONE-NODE can be given a node that is inside of a list, and the clone will be a lone node --- it won't still link into the list that the original linked into.
Forth doesn't provide automatic garbage collection. The programmer has to remove unused nodes from the heap himself. Use REMOVE, and then kill the removed node. If he doesn't do this, he will have a memory leak and his heap will eventually fill up. DEALLOC can be used for removing any unused node. We also have these words:
Getting back to our rational numbers, we have some statistical functions:
: mean ( head -- result-node ) \ the average of the head-list
: sample-variance ( head -- result-node ) \ variance of a sample
: population-variance ( head -- result-node ) \ variance of a complete population
MEAN calculates the mean (average) of a list of rationals. SAMPLE-VARIANCE and POPULATION-VARIANCE calculate the variance for a list of rationals. SAMPLE-VARIANCE is for the case where you have a sample taken from a larger population of data. POPULATION-VARIANCE is for the case where your list of data includes the entire population. In either case, standard deviation can be calculated by giving the result-node to RATIO-SQRT.
The intrepid novice may wish to upgrade our program to support more advanced statistical functions.