Expression evaluator (an example of parsing blocks)
[1/12] from: g:santilli:tiscalinet:it at: 14-Oct-2000 13:12
Hi all!
Have you been sometimes annoyed by tha fact REBOL does not support
operator precedence? Here's the answer:
>> a: 2 b: 4 c: 3
== 3
>> eval [b ^ 2 - 4 * a * c]
== -8
The magic trick is:
>> eval/translate [b ^ 2 - 4 * a * c]
== [subtract power b 2 multiply multiply 4 a c]
Other examples:
>> eval/translate [1 / k !]
== [divide 1 factorial k]
>> eval/translate [a * - b]
== [multiply a negate b]
>> eval/translate [e ^ (i / h * (p * x - E * t))]
== [power e multiply divide i h subtract multiply p x multiply E t]
NOTE: it still needs improvements, such as error handling. They
are "left to the reader as an exercise". :-)
Enjoy!,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
REBOL [
Title: "Expression evaluator"
Author: "Gabriele Santilli <[giesse--writeme--com]>"
Comment: {
Evaluates expressions taking usual operator precedence
into account.
1. (...)
2. - [negation], ! [factorial]
3. ^ [power]
4. *, /
5. +, - [subtraction]
}
]
; A simple iterative implementation; returns 1 for negative
; numbers. FEEL FREE TO IMPROVE THIS!
factorial: func [n [integer!] /local res] [
if n < 2 [return 1]
res: 1
; should avoid doing the loop for i = 1...
repeat i n [res: res * i]
]
expression-parser: make object! [
slash: to-lit-word first [ / ]
expr-val:
expr-op: none
expression: [
term (expr-val: term-val)
any [
['+ (expr-op: 'add) | '- (expr-op: 'subtract)]
term (expr-val: compose [(expr-op) (expr-val) (term-val)])
]
]
term-val:
term-op: none
term: [
pow (term-val: power-val)
any [
['* (term-op: 'multiply) | slash (term-op: 'divide)]
pow (term-val: compose [(term-op) (term-val) (power-val)])
]
]
power-val: none
pow: [
unary (power-val: unary-val)
opt ['^ unary (power-val: compose [power (power-val) (unary-val)])]
]
unary-val:
pre-uop:
post-uop: none
unary: [
(post-uop: pre-uop: [])
opt ['- (pre-uop: 'negate)]
primary
opt ['! (post-uop: 'factorial)]
(unary-val: compose [(post-uop) (pre-uop) (prim-val)])
]
prim-val: none
; WARNING: uses recursion for parens.
primary: [
set prim-val [number! | word!]
| set prim-val paren! (prim-val: translate to-block :prim-val)
]
translate: func [expr [block!] /local res recursion] [
; to allow recursive calling, we need to preserve our state
recursion: reduce [
:expr-val :expr-op :term-val :term-op :power-val :unary-val
:pre-uop :post-uop :prim-val
]
res: if parse expr expression [expr-val]
set [
expr-val expr-op term-val term-op power-val unary-val
pre-uop post-uop prim-val
] recursion
res
]
set 'eval func [expr [block!] /translate] [
expr: self/translate expr
either translate [expr] [do expr]
]
]
[2/12] from: chaz:innocent at: 19-Oct-2000 13:12
This is delightful! Thank you!
At 01:12 PM 10/14/00 +0200, you wrote:
[3/12] from: larry:ecotope at: 19-Oct-2000 15:01
Hi Gabriele
Just finished reading through the eval object. It is a useful tool, but I
am even more impressed by the elegance of your code. Nice work!
I have one quick question. Could you comment on why 'self is required in the
line
expr: self/translate expr
It is clearly needed, because the code won't run correctly without it, but I
am a little fuzzy about why.
-Larry
[4/12] from: g:santilli:tiscalinet:it at: 20-Oct-2000 22:38
Hello Larry!
On 20-Ott-00, you wrote:
LP> I have one quick question. Could you comment on why 'self is
LP> required in the line
LP> expr: self/translate expr
Because EVAL has a refinement called /TRANSLATE, so the word
translate
inside EVAL refers to the refinement (as you can see
in the EITHER TRANSLATE... line).
It would have been wiser to just choose two different names, but I
thought that that way it can be useful to illustrate how to deal
with such a situation.
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[5/12] from: rishi:picostar at: 20-Oct-2000 11:54
I like the fact that rebol doesn't support operator precedence. It is so much easier
when things are being evaluated from left to right. No need to remember a table and it
is easy to work with without parenthesis. just remember one concept...left->right
rishi
Previously, you (chaz) wrote:
[6/12] from: g:santilli:tiscalinet:it at: 21-Oct-2000 13:46
Hello Rishi!
On 20-Ott-00, you wrote:
RO> I like the fact that rebol doesn't support operator
RO> precedence. It is so much easier when things are being
RO> evaluated from left to right. No need to remember a table and
RO> it is easy to work with without parenthesis. just remember
RO> one concept...left->right
How do you write A * B - C * D in REBOL without using parens? You
need to use parens or use the notation:
subtract multiply a b multiply c d
which I prefer but might be less readable for people not used to
functional languages.
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[7/12] from: rryost:home at: 21-Oct-2000 13:55
Or,
>> subtract 4 * 5 6 * 7
== -22
Russell [rryost--home--com]
[8/12] from: larry:ecotope at: 21-Oct-2000 14:35
Hi Gabriele
> How do you write A * B - C * D in REBOL without using parens? You
> need to use parens or use the notation:
You can do it without parens by mixing infix and prefix forms:
>> - 4 * 5 3 * 4
== 12
I looked for a more complex example and noted that even with parens, the
result from REBOL may be surprising, because of the way the interpreter
evaluates parens.
>> - (4 * 5) ((3 * 4) + (2 * 3))
== 18 ; not the naive expected result
>> (4 * 5) - ((3 * 4) + (2 * 3))
== 2 ; the expected result
But I found a way to do this without parens (readability becoming an issue)
>> + - + 3 * 4 2 * 3 4 * 5
== 2
This is kind of fun, eh?
Regards
-Larry
PS I suspect it can be shown that with suitable rearrangement of terms and
with both infix and prefix forms available, that parens are not needed.
Counter example?
----- Original Message -----
From: Gabriele Santilli <[g--santilli--tiscalinet--it]>
To: <[rebol-list--rebol--com]>
Sent: Saturday, October 21, 2000 4:46 AM
Subject: [REBOL] Re: Expression evaluator (an example of parsing blocks)
-------snip--------------------
[9/12] from: rryost:home at: 21-Oct-2000 15:04
I believe Larry has encountered a problem in his first example. See
inserted comments below:
Russell [rryost--home--com]
----- Original Message -----
From: "Larry Palmiter" <[larry--ecotope--com]>
To: <[rebol-list--rebol--com]>
Sent: Saturday, October 21, 2000 2:35 PM
Subject: [REBOL] Re: Expression evaluator (an example of parsing blocks)
> Hi Gabriele
>
> > How do you write A * B - C * D in REBOL without using parens? You
> > need to use parens or use the notation:
>
> You can do it without parens by mixing infix and prefix forms:
>
> >> - 4 * 5 3 * 4
The following result obtained by Larry is merely the result of 3 * 4; the
result of - 4 * 5 (-20) has been discarded.
20 - 12 should give 8 as a result.
> == 12
>
> I looked for a more complex example and noted that even with parens, the
> result from REBOL may be surprising, because of the way the interpreter
> evaluates parens.
>
> >> - (4 * 5) ((3 * 4) + (2 * 3))
> == 18 ; not the naive expected result
Again, - (4 * 5) {-20} has been discarded; 18 is the result of the following
operation, ((3 * 4) + (2 * 3))
> >> (4 * 5) - ((3 * 4) + (2 * 3))
> == 2 ; the expected result
>
> But I found a way to do this without parens (readability becoming an
issue)
> >> + - + 3 * 4 2 * 3 4 * 5
> == 2
>
> This is kind of fun, eh?
>
> Regards
> -Larry
In REBOL, - 12 8 simply negates 12 and discards it, returning 8. REBOL
defines '-, in the absence of a preceding value, as a unitary (single
operand) operator that negates the following value. I fail to see the
utility of this, and would prefer '- to work like '+ on two following
arguments. But that's the way it is!
> PS I suspect it can be shown that with suitable rearrangement of terms and
> with both infix and prefix forms available, that parens are not needed.
As Gabriele and I showed with subtract 3 * 4 5 * 6
[10/12] from: larry:ecotope at: 21-Oct-2000 15:42
Hi Russell
Thanks for the corrections. Silly me, I fell into the "negate" trap. I agree
that it would be preferable for REBOL to implement the prefix "-" as a
binary operator, so that it worked like "+", etc. And have the unary "-" be
just no space before a number. IIRC it used to be this way in Core 2.1 or
so. I think there was also some talk at the time of making "+", "*", etc.
work only as infix operators with the prefix versions being "add",
multiply
, etc.
I still wonder if one can always avoid parens with use of both perfix and
infix forms.
Cheers
-Larry
[11/12] from: rishi:picostar at: 16-Oct-2000 9:18
I think that is a great feature. Operator precedence always confused me. In Rebol, it
is done
left-right...the way it should have been done in other languages..
rishi
[12/12] from: g:santilli:tiscalinet:it at: 22-Oct-2000 12:12
Hello Larry!
On 21-Ott-00, you wrote:
LP> PS I suspect it can be shown that with suitable rearrangement
LP> of terms and with both infix and prefix forms available, that
LP> parens are not needed.
Yup, but then again, why not using infix at all? If you're mixing
infix and prefix notation that way, you'll get less readability
than using prefix notation only.
My suggestion is: use infix notation with a lot of parens if
readability by the occasional reader is the priority; use prefix
notation (perhaps generating it with eval/translate :) when
code elegance is the priority.
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/