Reverse Cambridge Polish notation for Lisp?


One of the things that still seem unnatural sometimes with Lisp, is the fact that in many cases the actual evaluation need to start quite for into the structure – especially if you’re programming in a heavily functional style. The problem with this is that the way you read code doesn’t go left-to-right. Instead you need to read inside out. To make this less abstract, take a look at this example Lisp code:

(defun foo (x)
  (flux
   (bar
    (conc "foo"
          (get-bar
           (something "afsdfsd")
           (if (= x "foo")
               (conc "foo" "bar")
               (conc "bar" "foo")))))))

As you can see, this is totally bogus code. The nesting makes it possible to identify the parts that will be evaluated first. Compare that to the order it will actually be evaluated. You can see this order by transforming it to Reverse Cambridge Polish notation. This is equivalent – although I know no Lisp that actually does it. As you can see the way you read it, is actually the order it will be evaluated:

(foo (x)
  ((("foo"
     (("afsdfsd" something)
      ((x "foo" =)
       ("foo" "bar" conc)
       ("bar" "foo" conc)
       if)
      get-bar)
     conc)
    bar)
   flux)
  defun)

Well. It’s different, I grant you that. And of course, you need to keep the stack in your head, while reading it. But it’s an interesting experiment.


7 Comments, Comment or Ping

  1. Dave Newton

    ForthLisp?

    November 17th, 2008

  2. Reino Göransson

    If is not actually in the order it will be evaluated.
    If must be evaluated in two steps:
    First the first parenthesis, with the condition.
    Then one of the other parenthesis.
    When not every row gets evaluated there should be a special syntax, with the rows that gets controlled by the conditional expression.

    And it would be be easier to read with indentation instead of balancing parenthesis on different rows.
    Each row can stand for a stack.
    Rows with the same indentation can stand for pieces of stack that gets added (arguments to a function).
    The function can stand for the stack after the function.
    The function in each list can stand on the last row, with one step less indentation.

    November 18th, 2008

  3. Your observation of the discrepance between execution order and syntactical order shows the inherent flaw, yes even paradox in programming language design.
    Since the times of machine code and assembler programming language designers strived to overcome the limits of these primitive tools by introducing new abstractions. One common abstraction, expressions, should ideally hide the implementation detail how and in which order the value actually is calculated. Or see anonymous function values (closures), aren’t programming constructs consuming them awfully opaque if you just look at the syntax? Execution order, time or even the count of evaluations is not just visible. Nonetheless they are a needed and useful instrument for abstracting.

    The problem is: in today’s impure programming languages you can’t be sure if the execution order matters. Side-effects may have to be executed in the correct order. This limits the use of these constructs in contrast to pure functional PLs where you never (need to) know when some value is calculated.

    November 18th, 2008

  4. Hey Ola,

    While I agree the foo function is a little difficult to read, couldn’t a let* be used to make the evaluation order more clear?

    (defun foo (x)
    (let* ((a (if (equalp x “foo”)
    (conc “foo” “bar”)
    (conc “bar” “foo”)))
    (b (get-bar (something “afsdfsd”) a)))
    (flux (bar (conc “foo” b)))))

    November 18th, 2008

  5. Hmm — sorry, my code is hard to read :-). I guess comments get their indentation removed.

    November 18th, 2008

  6. Bill,

    Well, that’s exactly the point. If I use a let, I will change the order of reading stuff, so a let is among other things a way of making the reading order more like the evaluation order. =)

    November 18th, 2008

  7. I wonder if macro support will be more difficult with this notation.

    November 25th, 2008

Reply to “Reverse Cambridge Polish notation for Lisp?”