Optimizing quadratic-eqn
Quality of life improvements
Current architecture
. Dictionary Generation
. Functions
. Main Loop
Conclusion
Optimizing quadratic-eqn
========================
So now lets move on to more RPN programming, today we are gonna have a
look and see if we can't get that quadratic equation solver
shorter. Because its pretty knarly.
The easy way to do so would be to have the user enter in a, b and c in
an order that is convinient for us, including multiples. But thats
cheating. I was thinking about creating a new word for a rotate and
swap, but thats not really removing any of the stack dancing. I have
been looking at some of the user programs in the hpmuseum forums, and
they can get it down to less than 20 steps for their RPN calculators.
So lets see how we can do.
I'm going to add another version of rot that rotates the top 4 items
of the stack, rot4. We should be able to reduce the number of steps by
using rot4 to put the variables in the right order, plus duplicates,
so the stack dancing is reduced. (stack head is to the right)
stack func
(after op)
--------------------------
a b c
a c b swap
a c b b dup
b b c a rot4
b b c a a dup
b a a c b rot4
b a a c (b^2) square
b a (b^2) c a rot
b a (b^2) c a 4 4
b a (b^2) c (4a) *
b a (b^2) (4ac) *
b a D -
b a D sqrt
b D a swap
a b D rot
a b D D dup
a D D b rot
a D D -b neg
a D D -b -b dup
a D -b -b D rot
a D -b A1 -
a A1 -b D rot
a A1 A2 +
A2 A1 a rot
A2 A1 a 2 2
A2 A1 (2a) *
A2 A1 (2a) (2a) dup
(2a) (2a) A1 A2 rot4
(2a) A2 A1 (2a) rot
(2a) A2 S1 /
S1 A2 (2a) rot
S1 S2 /
Now we only use 31 words, not great but less. There 13 operations that
only move things around on the stack. So the minimum number of
operations is 18. So there is still room for improvement. But I might
leave it there for now, as any shorter and you you start cheating
mathematically. Which is interesting in and of itself, but not
something im going to explore here.
Quality of life improvements
============================
I think we need to do some final smoothing over of the code before I
shelve it for a while to work on other things. Firstly, I would like
to not have the program crash when /pop/ is called on an empty
list. The best option be to have execution stop there and return to
the repl. But an easier way is to just use /error/ which unfortunately
jumps us out of the main loop, but is much simpler.
Current architecture
====================
Lets have a look at the curent architecture of the calculator. There
are three parts I think, generation of the dictionary, how functions
are called, and the overall main loop.
Dictionary Generation
~~~~~~~~~~~~~~~~~~~~~
The initial dictionary is generated from a list, of which each memeber
is either a list of two or three elements. If its three elements,
thats one of the "wrapper" functions that just pops the stack and
passes those arguments to a standard scheme function. If its two
elements, then its a function that was written in scheme and doesn't
need to be passed the amount of arguments as it does its own
manipulation of the stack. And doesn't need to call /rpn-func/.
,----
| +--------------------+
| | generate-init-dict |
| +--------------------+
| / \
| (name func args) / \
| / \
| / \ (name func)
| +----------------------------+ \
| | return cons of name and | \
| | lambda executing func with | \
| | args number of elements | \
| | popped from stack | \
| +----------------------------+ \
| +------------------------------+
| | return cons of name and func |
| +------------------------------+
|
`----
<file:init-dict.png>
Then the next step is importing the user defined functions. In the
beginning of the main loop the /user-funcs/ file is read in and each
function is added to the runtime dictionary.
,----
| +--------------------+ funcs-file
| |load-funcs-from-file|-----
| +--------------------+
| | each list from funcs-file
| |
| +----------+
| | new-func | //inserts func into dict
| +----------+
| |
| | definition of func
| |
| +-------------------+
| |user-func-from-list| //returns the lambda executing each word
| +-------------------+ //in the definition
|
`----
<file:func-load.png>
When a new function is defined at the repl, we re-use /new-func/ to
add it to the runtime dictonary. And if a function has the same name
as the new function, it is rewritten with the new definition.
The function is also appended to the user-funcs file.
Functions
~~~~~~~~~
Functions are stored in the dictionary as an alist where the key is
its name, and the value is a function taking two arguments, the stack
and the dictionary.
Functions are called by checking if a function of that name exists in
the dictionary, if it does then it is run and the modified stack is
returned.
Main Loop
~~~~~~~~~
The main loop begins by initiating an empty stack, and reading in the
/user-funcs/ file, then reading from standard in. The input can be
either a number, list or symbol. Numbers being pushed onto the stack.
Lists being user defined functions that are added to the
dictionary. And symbols are functions to be executed. Anything else
signals an error.
Conclusion
==========
I think I will lay this project to rest for the mean time. I might
come back to it at a later date to screw around with it or maybe ad
some more features but I think for now there is enough features for it
to be useful just on its own, and hackable enough for anyone who wants
to have a go. Of course if anyone has any feature requests, patches or
ideas that would be sick too.
