Recursive LISP programming - formula solver

The formula solver is in itself a very interesting workout, and at a certain point this workout can be very useful in another task - designing a new formula, automatically checking it (error, calculating the values ​​according to the list of coordinates) ... And excel does not help you, and is unsportsmanlike.


Immediately make a reservation - the code is made for LISP sample of '87, and the fresh Common LISP will not understand it categorically, which is sad ... But - 2 steps from LISP code to understanding how to write the same thing in a more decent for practical task C # or Delphi, in LISP, a more sweet performance is given to my heart and eye)

Entering a formula from the keyboard, against a hard task in the code, has a lot of advantages. How to implement it, the programmer thought, perhaps, from the school iron chair. The task is great, and it seems impossible, but the main thing is to start. Getting >>
')

1. How will the formula be written?

Regular entry for the first step is unnecessarily complicated. Polish form of record - use it. And operations on numbers are written in the form of lists, which can be set the most complex mathematical expression:
#
2+3->(+ 2 3)
2-3->(- 2 3)
2*3->(* 2 3)
2/3->(/ 2 3)
2+3+5->(+ 2 3 5)
2+3*5->(+ 2 (* 3 5))
(2+3)*5->(* (+ 2 3) 5)


2. How will it work? (simple formulas)

We will write a solver (solver) in the revo ... recursive spirit of LISP: he will grab the first element from the list of the head, and then process the tail in accordance with the head value. At the input, the solver receives each time the formula (a), the result of the previous action (b), the sign © and, if foreseen in advance, then the values ​​of the unknown parameters (xx).

(defun solver (abc xx)
((null a) b)
((equal (searchx a) NIL) (solver (presolver a NIL xx) T c xx))
((eq (atom a) T) a)
((equal c NIL) (solver (cdr (cdr a)) (car (cdr a)) (car a) xx))
((equal c ps) (solver (cdr a) (+ b (car a)) c xx))
((equal c ms) (solver (cdr a) (- b (car a)) c xx))
((equal c mu) (solver (cdr a) (* b (car a)) c xx))
((equal c di) (solver (cdr a) (/ b (car a)) c xx))
)


Unknown parameters specified in the formula with their own names # (+ x 5)) should replace the corresponding function with values. And to the solver. We call it a predecessor (presolver), feed the formula, the result (when called from the solver, NIL) and the value of the unknown element for substitution of the element 'x' (I single it out here specifically, for LISP does not distinguish, thank God, data types)

(defun presolver (ab xx)
((null a) (revers b))
((eq (car a) x) (presolver (cdr a) (cons xx b) xx))
((eq (equal (car a) x) NIL) (presolver (cdr a) (cons (car a) b) xx))
)


And - the presence of unknowns still need to be confirmed. The search function of the unknown is born, searchx, and at the same time the reverse function of the revers list, for the result of presolver, by default, goes backwards.

(defun searchx (a)
((null a) T)
((equal (car a) x) NIL)
(searchx (cdr a))
)


(defun revers (ab)
((null a) b)
(revers (cdr a) (cons (car a) b))
)


Run-check-

(solver '(ps x 2 3) NIL NIL 5)

-ura-works. But - only on simple formulas, with lists without nested lists, with atom elements.

3. How will it work-2? (complex formulas)

You can think for a long time how to turn a simple solver into an interesting way in an interesting way, but we will go in a more rational way - we will not touch the working piece, but let us work on the project solver2 - the solver of complex formulas.

(defun solver2 (a xx)
((eq (iseasy a) T)
(solver a NIL NIL xx))
((eq (atom (car a)) T)
(solver (cons (car a) (solver2 (cdr a) xx)) NIL NIL xx))
((eq (iseasy (car a)) T)
(cons (solver (car a) NIL NIL xx) (solver2 (cdr a) xx)))
((eq (iseasy (car a)) NIL)
(cons (solver2 (car a) xx) (solver2 (cdr a) xx)))
)


Each complex formula contains at least one list element. But let's start with the compatibility problem, so that the new function works at least for simple calculations. To do this, you need to check the input formula for simplicity, and if it's simple, send it to the solver, but if it's difficult, think about it a little more.

The iseasy function with a single input parameter, the formula itself, can help you define a simple list or not quite. Iseasy sees the element non-atom - and falls with the answer NIL

(defun iseasy (a)
((null a) T)
((equal (atom (car a)) Nil) NIL)
(iseasy (cdr a))
)


Then everything is simple, and at the same time elegantly incomprehensible. The correct operation of the function is obvious, but the algorithm is not obvious. He is:
- First, solver2 checks the formula entirely for simplicity. If the formula is simple entirely, it can and should be solved by solver.
- Next, there is a check - “is it not the atom's head at the formula 'a'?” If the head is an atom, then we send the solver constructor from this atom and tail, which requires re-consideration of solver2
- If the first 2 checks did not pass, something with the formula is definitely wrong (it seems to me 2 years after writing the code), then we should check the formula head for simplicity, and if that is simple (BUT not an atom! - and that means the list ), we will send the construction of the resolved head and the reversed solver2 tail of the formula to the launching solver2 function. For example, "on the screen" ... Perhaps this is some kind of bugreport?
- If the first 3 checks have not passed (quite a disaster, it means that the formula is not simple, in the head of this formula there is not an atom (that is, not the ± / * / :) sign, and not even a list of atoms, we will issue "on the screen "A design from the resurrected solver2 head and tail, also with revision solver2

Run ...
(solver2 '(mu (ps x 2 3) (ms x 5)) 10)
Be surprised

4. Why does it work? (conclusion)

Obviously, solver2 in the above code can read simple formulas. But how, running it, he considers and complex? Vision in recursive programming is very deceptive.

Each correct formula starts with an atom of operation. Follow the actions of LISP, reader: solver2 begins to solve the correct complex formula, and sends to the solver a construction from the head of this formula (sign), and ... a revised tail in itself. The tail comes to solver2 and, naturally, does not contain an operation atom in the head. Therefore, solver2 is deservedly sent to further simplify ...

What is his essence, what is he doing, this solver2? In general, nothing even simpler - he takes the list and replaces it with a number ... In the end, any arbitrarily long formula, even with a 10-fold nesting, will collapse to a simple list, with a sign in his head and a tail consisting of only atoms, with all atoms being numbers. It is beautiful, and absolutely incomprehensible by the code, incomprehensible and at the first step of writing the function) ... For which the RP I love.