Where you have (append `(+ ,x) (forthify `(+ ,@xs)))
I think you could change that to (append `(,x) (forthify `(+ ,@xs)) `(+))
or equivalently `(,x ,@(forthify `(+ ,@xs)) +)
Thanks @rokitna! shunting all of operators to the end may be a better approach. I wonder, given any prefix (numeric, at least) expression, is it always possible - producing an equivalent expression - to push all of the operands in the order they appear, and then insert the deferred operators at the end? I get the feeling it may be impossible due to precedence, but I’m really not sure; my lack of mathematical maturity shows in situations like these. I’ll keep chipping away at it, thanks again :)
That’s awesome! thanks. Is the proof-of-concept code included in the repo somewhere? I had a look but couldn’t seem to find it. I’d be interested to see how you implemented the algorithm in Racket.
I converted this algorithm (https://www.geeksforgeeks.org/prefix-postfix-conversion/) to Racket: (define op? (curryr member '(+ - * /)))
(define (convert ls stk)
(cond
[(null? ls) (flatten (reverse stk))]
[(op? (car ls)) (displayln "op")
(let ([op1 (car stk)]
[op2 (cadr stk)]
[stk (cddr stk)])
(convert (cdr ls)
(cons (list op1 op2 (car ls))
stk)))]
[else (convert (cdr ls)
(cons (car ls)
stk))]))
(define (pre->post ls) (convert (reverse ls) '()))
(pre->post example)
The output matches the output in the page the method was taken from, but I get the feeling it doesn’t work quite right: (pre->post '(* - 5 / 4 3 - / 5 2 1))
in Racket, this original expression yields 11/2
the converted expression '(5 4 3 / - 5 2 / 1 - * )
in Forth yields 4
am I goofing, or is the algorithm incorrect? I’ve seen a couple of comments stating that you can’t go directly from prefix->postfix, there must be an intermediate infix step between. I can only assume this could be to do with precedence, but the whole advantage of prefix and postfix as opposed to infix is that the precedence is unambiguous, right? All of this is entirely new to me, so forgive me if I’m missing something obvious or my conversion is wrong. Thanks :)
I doubt converting to infix would help here. (I think it only came up because @notjack thought you were converting from infix in the first place.)
Both results sound correct to me. The result 4
is what you get when using integer division that truncates or rounds down, and it sounds like Forth is doing one of those things. Racket has a numeric tower that in this case does rational arithmetic, so you get the precise result 11/2
without rounding.
Not yet, no. I’ll get around to pushing it somewhere eventually though.
My approach is to write a tree walker/interpreter/compiler that builds up the forth-style expression.
https://gist.github.com/samdphillips/a62bcda26e7577ac2eba4dec6326f958