Scheme Infix to Postfix

Question

Let me establish that this is part of a class assignment, so I'm definitely not looking for a complete code answer. Essentially we need to write a converter in Scheme that takes a list representing a mathematical equation in infix format and then output a list with the equation in postfix format.

We've been provided with the algorithm to do so, simple enough. The issue is that there is a restriction against using any of the available imperative language features. I can't figure out how to do this in a purely functional manner. This is our fist introduction to functional programming in my program.

I know I'm going to be using recursion to iterate over the list of items in the infix expression like such.

(define (itp ifExpr)
  (
    ; do some processing using cond statement
    (itp (cdr ifExpr))
  ))

I have all of the processing implemented (at least as best I can without knowing how to do the rest) but the algorithm I'm using to implement this requires that operators be pushed onto a stack and used later. My question is how do I implement a stack in this function that is available to all of the recursive calls as well?

Answer 1

(Updated in response to the OP's comment; see the new section below the original answer.)

---

Use a list for the stack and make it one of the loop variables. E.g.

(let loop ((stack (list))
           ... ; other loop variables here,
               ; like e.g. what remains of the infix expression
            )
  ... ; loop body
  )

Then whenever you want to change what's on the stack at the next iteration, well, basically just do so.

(loop (cons 'foo stack) ...)

Also note that if you need to make a bunch of "updates" in sequence, you can often model that with a let* form. This doesn't really work with vectors in Scheme (though it does work with Clojure's persistent vectors, if you care to look into them), but it does with scalar values and lists, as well as SRFI 40/41 streams.

---

In response to your comment about loops being ruled out as an "imperative" feature:

(let loop ((foo foo-val)
           (bar bar-val))
  (do-stuff))

is syntactic sugar for

(letrec ((loop (lambda (foo bar) (do-stuff))))
  (loop foo-val bar-val))

letrec then expands to a form of let which is likely to use something equivalent to a set! or local define internally, but is considered perfectly functional. You are free to use some other symbol in place of loop, by the way. Also, this kind of let is called 'named let' (or sometimes 'tagged').

You will likely remember that the basic form of let:

(let ((foo foo-val)
      (bar bar-val))
  (do-stuff))

is also syntactic sugar over a clever use of lambda:

((lambda (foo bar) (do-stuff)) foo-val bar-val)

so it all boils down to procedure application, as is usual in Scheme.

Named let makes self-recursion prettier, that's all; and as I'm sure you already know, (self-) recursion with tail calls is the way to go when modelling iterative computational processes in a functional way.

Clearly this particular "loopy" construct lends itself pretty well to imperative programming too -- just use set! or data structure mutators in the loop's body if that's what you want to do -- but if you stay away from destructive function calls, there's nothing inherently imperative about looping through recursion or the tagged let itself at all. In fact, looping through recursion is one of the most basic techniques in functional programming and the whole point of this kind of homework would have to be teaching precisely that... :-)

If you really feel uncertain about whether it's ok to use it (or whether it will be clear enough that you understand the pattern involved if you just use a named let), then you could just desugar it as explained above (possibly using a local define rather than letrec).

Answer 2

I'm not sure I understand this all correctly, but what's wrong with this simpler solution:

First:

You test if your argument is indeed a list:

If yes: Append the the MAP of the function over the tail (map postfixer (cdr lst)) to the a list containing only the head. The Map just applies the postfixer again to each sequential element of the tail.

If not, just return the argument unchanged.

Three lines of Scheme in my implementation, translates:

(postfixer '(= 7 (/ (+ 10 4) 2)))

To:

(7 ((10 4 +) 2 /) =)

The recursion via map needs no looping, not even tail looping, no mutation and shows the functional style by applying map. Unless I'm totally misunderstanding your point here, I don't see the need for all that complexity above.

Edit: Oh, now I read, infix, not prefix, to postfix. Well, the same general idea applies except taking the second element and not the first.