gCAS has come a long way. Version 1 was written on a car trip in a day and was able to do basic math. Later on, I started from scratch and made gCAS2 in a day or so. After that, a lot of time was put into it to get a very small CAS to function in small ROM/RAM situations, an aspect that most CASes don't address.
gCAS was intended to be used as the caclulator backing up GlassOS. Currently, it is used by KermM's Graph3DP addin, providing excellent 3D graphing for a platform lacking 3D features. It has gained a lot of code, but it also showed its weaknesses in the core design. So, I propose a rewrite that will still be optimized and run on GlassOS and other platforms.
My idea was to redesign math functionality to instead of using native function, instead use a VM to run through algorithms. That way functions can be created and included outside of the size limit of the library itself, but still be easy to add new methods. JIT compiling can be an option
Another thing must be addressed: functions and variable-sized nodes. There needs to be a better method to handling and creating these. Ideas?
Any ideas for improving the cas in general? The parser could have implicit multiplication added, but other than that, I don't like to mess with it since I couldn't understand how it worked when I was half-way through writing it :-\
Also, any changes by KermM will be loved here since that can help with either adding functionality or redesigning code.
Note: Hopefully there will be limited or no changes to how you would use the library, just changes to the backend itself.
I started on a VM that should work much nicer than z80 asm or SH4a asm. Should be fun.
Well, I don't want to touch anything else right now, so here I am. I am thinking about how a tokenized language would work for making algorithms for gCAS2. If I have tokens, I would try to do something like the below:
Code: ; Node1 is the input
; Function is abs
; Inside would have been simplified
If Mode(Distribute)
If Type(Node1,Number)
; Only numbers for now
F1=absf(Node1.N)
If F1!=Node1.N
Node1.N=F1
Return Node1
EndIf
EndIf
EndIf
Return Null
Another idea is a Forth-like language that is compiled into a bytecode and run by gCAS2.
<edit>
gCFvm is a forth-like interpreter, compiler, and VM that is being experimented with. Since forth is such a fun language and I can write the CAS algorithms on-calc with this, I will experiment and try to make it highly optimized. After a few minutes, it runs this custom code Code: ![HAL@HAL build]$ ./forth
@" 2+3-4=" 4 2 3 + - SWAP PRINTS PRINT CR
2+3-4=1
ok
@PRINT
DStack overread
ok
@
<edit>
I am thinking about adding in a separate floating point stack to run floating point ops. This is partly because I may drop floats for something from GMP or some other library that gives me fixed point math ops.
Anyways, I have conditionals and I can create and destroy cas nodes.
<edit>
Node manipulation!
Code: ![HAL@HAL build]$ ./forth
@NODENEW f1.23 NSETN 11 NSETTYPE DUP PRINTN NODEDEL
1.230000ok
@
![HAL@HAL build]$
Now, FORTH is based on 2 byte addresses and 4 byte floats (at least on original/old ones). Since gCAS2 is supposed to be portable to multiple platforms, it currently has either floats one stack entry if sizeof(float) <= sizeof(uintptr_t) (x86/x86_64/SH4) or 2 if it is smaller (z80). Floats are read if the first letter is 'f'.
The other thing to look into is a better number system. I am wondering if there is anything like libGMP that is small and portable (unless I can rip low-level functions from GMP).
<edit>
I now now that there is "The GNU Multiple Precision Arithmetic Library" and another is the "GNU Multiple Precision Complex Library". I probably will not add in complex numbers for a while, so I will see about ripping out GMP low-level functions and adding them to FORTH. I will need to check, but they will most likely be malloc'd and will be put onto the dstack as one entry :3 I doubt that there are z80 optimized functions, but not sure about SH3/SH4.
Splitting into a new post, also for the bump as edits don't work well at that
Loading files works, defining and unloading words works.
Code: ![HAL@HAL build]$ echo -e "\" This is a loaded file\" PRINTS CR\n: TEST \" I am a new word\" PRINTS CR\n12345 PRINT CR" > test
![HAL@HAL build]$ ./forth
@WORDS
PRINT PRINTS PRINTN CR DROP + - DROPALL SWAP / * DUP IF ELSE THEN NODENEW NODEDEL NODEDELR NGETTYPE NGETN NSETTYPE NSETN PRINTF NGETB NSETB NGETP NSETP NGETN1 NGETN2 NSETN1 NSETN2 WORDS LOAD UNLOAD ok
@" test" LOAD
This is a loaded file
12345
ok
@WORDS
PRINT PRINTS PRINTN CR DROP + - DROPALL SWAP / * DUP IF ELSE THEN NODENEW NODEDEL NODEDELR NGETTYPE NGETN NSETTYPE NSETN PRINTF NGETB NSETB NGETP NSETP NGETN1 NGETN2 NSETN1 NSETN2 WORDS LOAD UNLOAD TEST ok
@TEST
I am a new word
ok
@" TEST" UNLOAD
ok
@TEST
Unknown word 'TEST
@
![HAL@HAL build]$
<edit>
Here is a nice indicator of progress: With long labels and a few printed strings, the tokenized gCFvm code is 111 bytes. For the same code in SDCC, the output is 309 bytes. My language is 35% of the original asm!.
I will be expanding the FORTH-like language to allow for multiple stacks in order to aid in manipulating nodes. I will also look into optimizing features and other fun things.
Very impressive updates, can't wait for a usable FORTH-extendable gCAS
(For sake of terminology, gCAS3 is the completed CAS with all features, gCFvm is the gCAS FORTH-like Virtual Machine)
gCFvm is now using my own linked list/stack for the data stack! Still need to move out some other std::vector usage.
So can we look forward to a new CAS for PRIZM?
The gCAS line was always cross-platform and already runs on the prizm
For doing user input, I will need to get back to addin making.
gCFvm was dropped for now in favor of gCasp, a Lisp interpreter that will run in low memory requirements. This is a test for math processing on GlassOS, just as gCFvm was.
gCasp was able to parse ("asdf" "zxcv"), but I will have to look into garbage collection, evaluation, and holding intern'd variables and functions. Due to the complexity, I don't think gCasp will run any byte-code any time soon, so ram usage will take a hit.
I have looked into doing pattern matching on node trees in gCAS3. Still trying to work out the details on this, but I am still looking.
I am thinking about having a weird mix of languages to get this to work. Essentially, the engine is made up of functions and matches. Functions are things like integ(x-x^2,x). Matches are things like {* front[,,] {+ :list[]}} (which will match a multiplication of a number with any value, base, power and the sum of anything of varying length.). This will let me do things like have matches for things like {a[,t,p]} returning [a.n,t,p+1]/(p+1), allowing integ(x^2,x) to match and evaluate to x^3/3.
<edit>
This will be more RAM hungry, but will let me make this a more complete CAS. I will post status updates of gCAS3 here
- Started laying out the new node, variable, and search structs.
- Match string parser is being written. I will need to look into optimizing how I search as it seems like it is overly complex.
More updates:
- Matching parser works and was able to read "{+ a[,x,p] b[,x,p]}" properly. I will work on the tree matching function soon.
- Functions in gCAS3 will be static for now, meaning that you cannot arbitrarily add in your own functions and expect gCAS3 to recognize and use them. Not a problem for me as I am making the CAS. This may change in the future, but not likely. This is to have ALL node types (addition, mult., sine, integration, plotting, etc.) as unique digits (8bit) and not need to have strings used outside the equation parser.
- The language used here will not be used outside of internal CAS workings.
- I am thinking about things like lists, matrices, strings, unit conversions, etc.
So, more pain here. I am currently getting the matching for the nodes right now. This means that I need to be aware of all variables which are used to link the different parts of the nodes, ex the x in a[,x,] b[,x,] which means that the base must be the same (base being 0 for regular numbers and >0 for a variable).
The other issue is matching a list to another list out of order. :/
- Internal variables for matching being added
- Actual matching code is going.
- Matching had its first true match!
Code: Function start
[+]
Found it!
[2.000000,1,3.000000]
New stack
Found a node!
[3.000000,0,1.000000]
[1.000000,1,3.000000]
Found a node!
Tree matched!
[2.000000,1,3.000000]
[3.000000,0,1.000000]
[1.000000,1,3.000000]
1
From above, the [f] and [n,b,p] are the nodes (f→function name, n→number, b→base, p→power). It was matching 2x^3+3+x^3 against "{+ a[,x,p] b[,x,p]}".
Once a match has been found, I need to run some sort of script in order to either reject this match or return a replacement for this.
Before I get there, I need to figure out what happens in odd matching situations. What happens when matching on order-specific operations, like /? matching {/ a[,x,] b[,x,]} with y/x/x will also match x/y/x, which isn't the same.
So, my current goal is to make a CAS that uses matching patterns to find math expressions to transform.
I wanted to take an approach to have math evaluated by matching up parts of an expression on various "patterns" or tree fragments. Once a match is found, certain code provided by the pattern will be run to transform the output (either custom code or another pattern used to transform the tree).
Now, the CAS will start out with function support. Yes, KermM, function support starting at the beginning, not the end
Lets say we have 2+2. Originally, nodes for gCAS2 were made as such:
Code: node:
node *n1, *n2; // left/right children
unsigned int type; // Node type
float nN; // Number value
int nB; // Base (0 is regular number, else variable ID)
int nP; // Power
Instead, I am looking at a system close to how LISP structures it.Code: node:
node *child; // Lower level
node *next; // Same level
int type; // Node type
float nN; // Either number or variable ID
Here, 2+2 is generated as (+ 2 2). + is not an internal function, but lets say that ADD is and will sum all numbers given to it (just same type of either imaginary or real numbers).
I will have a pattern set up like:Code: TRANSFORM
IN=(+ c1 c2)
OUT=(ADD c1 c2)
Now, matching will happen (more on this later) to basically assign c1=2 and c2=2. It will then remove the affected nodes and replace it with (ADD c1 c2). This evaluates nicely to 4.
Simple enough. Now, what about more complex functions? Since pattern replacing is planned to be in files, I also planned to have these patterns be placed in pattern groups. Think about this: You run math functions in the default pattern group, ::*. Lets say that you evaluate (a+b)*(c+d). Normally, nothing would happen. But lets say that you use the function expand(...). Besides a bit of custom code, it changes the namespace to expand::*. Lets also assume that the pattern (* a (+ b c)) --> (+ (* a b) (* a c)) exists in that namespace. When running expand(...), it finds a matching pattern and runs it.
Now, the issue is this: what about (a+b)*(c+d)? Ideally, the pattern should find a=(a+b), b=c, c=d and make (a+b)*c+(a+b)*d, which could then be matched again and fully expand it. I am struggling at this kind of matching where there isn't a perfect match.
Also, consider this pattern: x^2. I am trying to apply this to 4. Ideally, this should get x=root(4,2) and give me root(4,2)^2 = 4. Remember, matching is NOT solving, it is trying to fit a tree into the structure of another. I was thinking that I would have the recursively try to pattern match... but how?! Maybe I have to solve for these cases?
This system would, if done correctly, allow a plethora of math much more advanced to be processed than gCAS2 and not have the same issue of space taken up in the binary.
I will keep posting here with more info, but I have been trying to get matching to work. So far, I know that I MUST sort trees in order to have matching work nicely. I also know that I will have issues when I have to extract single nodes from various places out of order in a tree.
gCAS3 has moved away from FORTH due to problems with C and lacking the ability to extend a lot of the language for things like complex processing of math operations.
Instead, a LISP-variant is being created to let gCAS3 evaluate math statements as lisp. This variant is close to muLISP, using M-expressions and using implicitly-defined symbols.
For example, in LISP, solving 2x^2+x+3 is written as (+ (* 2 (^ 'x 2)) 'x 3). In gCAS3, certain operators can be implicitly made into function calls. In gCAS3, the expressions is simply written as 2*x^2+x+3. Note that there is order of operations based on order defined.
For example, in LISP, plotting 2x from -10,-10 to 10,10 is (plot (* 2 'x) -10 10 -10 10) . gCAS3 would instead run plot(2*x,-10,10,-10,10).
Currently hammering out the parser. I will need to plan out how garbage collection will work. Right now, I don't have the best way of GC'ing stuff and am not focusing on it too much.
Quote:
[14:59:53] <AHelper0> KermM, lisp parser using OOO with implicity n-nary symbols figured out and much simpler than gCAS2
[15:00:03] <AHelper0> and should provide the same amount of error checking
[15:00:10] <AHelper0> without leaking memory
[15:00:12] <AHelper0>
The parser works like this:Code: To do OOO, a global map must be set up specifying order values, like
(setf ooo '((+ 1) (- 2) (* 3) (/ 4) (^ 5)))
Parsing symbols returns the token as a string and identifier if it is a number, implicit op, or a string.
Showing recursive parsing of the non-list parser (which handles m-expressions) for the expression 1-(2*3)^4*5+6:
1:- (Parse token, check ahead for implicit. Error out if non-implicit found.)
"(" -> List parse
2:*
3
(* 2 3)
")" <- End list parse
(* 2 3):^
4:*
5:+
6
(+ 5 6)
[(+] 5 6) * > +
(+ (* 4 5) 6) 5 is not in ooo list, insert
[(+] (* 4 5) 6) ^ > +
(+ [(*] 4 5) 6) ^ > *
(+ (* (^ (* 2 3) 4) 5) 6) 4 is not in ooo list, insert
[(+] (* (^ (* 2 3) 4) 5) 6) - > +
(+ (- 1 (* (^ (* 2 3) 4) 5)) 6) - < *
On =, prepend to list. These rules work even with functions like 2+pow(2,3)+2.
<edit>
Parsing and evaluation is starting to work!Code: > 123
123
> "This is a test"
"This is a test"
> print("Hello World")
Hello World
>print("I can also do variable arguments" 123 "\nand I can use \"escaped\" characters!")
I can also do variable arguments 123
and I can use "escaped" characters!
>
As you can see, the m-expression handling works, parsing is working (lacking implicit ops), evaluation is working (derpy, I am using code from small-lisp to help me get going, but I have different internals so rewriting and refactoring is needed).
Currently waiting on floating point math. gCAS3 will use 64bit IEEE754 floats as a special type while using ints for normal numbers.
gCAS3 is using a custom floating point format that I am creating. Hopefully I can make it in a way that SDCC will be happy with compiling and not make it huge like all of the other floating point libraries I have looked at.
The current floating point library uses BCD math to make it very easy for the z80 to use as well as making it very portable since the implementation is in C. The float library uses 8 digit mantissa 4 digit exponent (can be configured to some other size). Once I have enough added, I can start throwing it at SDCC to see what the compiled size is (it should be a lot smaller than other float libs since I only do unsigned 8bit math, have global FP registers, small parameters for functions, and running things loop-based). Then I should be able to plug it into gCAS3 and try running a bit of simple math.
Major work on garbage collection and managing memory! Below is a small test for memory usage:
Code: ![HAL@HAL build]$ valgrind --leak-check=full --show-leak-kinds=all ./gcas3
==23700== Memcheck, a memory error detector
==23700== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==23700== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
==23700== Command: ./gcas3
==23700==
:print("1+2=",add(1,2))
1+2= 3
nil
:mem()
1190
:gc()
472
:
==23700==
==23700== HEAP SUMMARY:
==23700== in use at exit: 0 bytes in 0 blocks
==23700== total heap usage: 61 allocs, 61 frees, 1,351 bytes allocated
==23700==
==23700== All heap blocks were freed -- no leaks are possible
==23700==
==23700== For counts of detected and suppressed errors, rerun with: -v
==23700== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
