Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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/