5 ms·

Reverse Polish notation, or RPN, removes the need for operator precedence. This is true of prefix or "Lisp notation" as well. I would show you an operator prec

Reverse Polish notation, or RPN, removes the need for operator precedence. This is true of prefix or "Lisp notation" as well. I would show you an operator precedence table for Common Lisp or Clojure, but we don't need such a table. With that said, one does need to keep in mind how function evaluation and macro evaluation differ. e.g. Consider (f (g (h x))). If f, g, h are functions, then (h x) is evaluated first. If they are all macros, then f is macroexpanded first with the body (g (h x)). ... with postfix operators, the only data structure you need is a stack. This also applies to prefix. I wonder what the motivation was to introduce postfix notation and prefer it over prefix.

kstrauser 2y ago
I vastly prefer postfix for interactive use. I can enter a bunch of numbers and then decide what to do with them. With prefix, I start by typing operators when I haven’t even fully decided which numbers I’m going to be using with them. Basically, prefix emphasizes the operations and postfix emphasizes the numbers. Prefix is perfectly fine for entering formulas into code. In dc or any other scratchpad, I find postfix much, much more convenient.
somat 2y ago
They both remove the need for screwball operator precedence, but the lisp s-expression do it by putting everything in parentheses(or perhaps everything in function notation is the better way to put it) and RPN does it by making the stack an integral part of the mental model needed to understand it.
- adrian_b 2y ago
  The parentheses are needed in LISP only because many functions have a variable number of operands, so that parentheses are needed to show where is the end of the list of operands. In a language where all functions had a fixed number of operands, prefix notation (or function invocation in general) could be used without any parentheses. Parentheses are also required for postfix notation when functions with variable number of operands are accepted (e.g. the sum of an arbitrary number of operands).
  - kazinator 2y ago
    The parentheses are needed in Lisp because the input is data and not code. There are no "functions" and "arguments" in the data; that's a particular interpretation imposed on the data. We wouldn't want the data notation to have an implicit shape which depends on the programming language semantics of the symbols which appear in it, like their arity.
    - adrian_b 2y ago
      Code is a special kind of data, i.e. the kind of data that can be the input of an interpreter or compiler. A LISP program is not (arbitrary) data, i.e. it does not contain arbitrary lists. Giving data, i.e. an arbitrary list to any LISP interpreter or compiler will just result in an error message and a translation failure. A LISP program contains only invocations of functions or macros (besides special forms) and each invocation has an associated list of arguments. While the classic LISP convention is to write the function/macro name after the opening parenthesis, this notation is equivalent with writing first the name of the function/macro followed by a list of arguments enclosed in parentheses. Conceptually, data in LISP, which consists of lists of values, should have used a different kind of brackets for delimiting a list. Because of the limitations of the character sets available in old computers, the round parentheses have a dual role in LISP, as delimiters for lists that are data and as delimiters for the lists of arguments used by function/macro invocations. The two roles are differentiated by the use of the QUOTE special form, which is just a workaround for not using two different kinds of brackets, which would more clearly differentiate LISP data and LISP code. If all the LISP functions or macros had a fixed number of arguments, then the LISP code, i.e. the invocations of functions or macros, could have been written without parentheses. In that case, the LISP data, i.e. lists, could have been delimited by round parentheses without using the QUOTE special form, which would not have been necessary.
      - _19qg 2y ago
        LISP is short of "List Processor". It was developed as a language & system for processing lists. The programming language LISP was supposed to have M-Expressions (M -> Meta) for code and S-Expressions for data. For example a call to append two lists would have looked like this: append[listvar;(PARIS BERLIN NEWYORK TOKYO)] The arguments are enclosed in square brackets. The second argument is written as an S-Expression. S-Expressions were the data notation and were enclosed in parentheses. Symbols were upper case. The names of operators and variables were lower case. The append call then looked like this: (APPEND LISTVAR (QUOTE (PARIS BERLIN NEWYORK TOKYO))) A conditional would have been: [eq[car[l];0] → cons[(ZERO);cdr[l]]; T → x] Which in S-expression only syntax is: (COND ((EQ (CAR L)) (CONS (QUOTE (ZERO)) (CDR L))) (T X)) As you can see the conditional would have a special infix syntax. > Because of the limitations of the character sets available in old computers, the round parentheses have a dual role in LISP, as delimiters for lists that are data and as delimiters for the lists of arguments used by function/macro invocations. No, the syntax above wasn't actually implemented at first. The M-Expression/S-Expression combination was hand translated into S-Expressions, since the Interpreter and Compiler took lists as input. The reason why the syntax is like this is not a lack of characters or so. The reason is because the language early on worked on code as list data and not on code as text. The input and output was then of list data. The famous "Read Eval Print Loop" reads data, evaluates it and prints the result in data format. It was thought that a later version of LISP had the M-Expression/S-expression syntax as surface syntax. But that did not get any traction, because the S-expressions would be visible in the programming tools anyway: debugger, code inspector, code stepper. Thus it was more convenient to stay in the s-expression syntax, than to convert S-Expressions both from and into M-Expressions/S-Expressions. For example a stepper for LISP code might look like this. :s is the single step command: CL-USER 8 > (step (plus (minus 10 20) (plus 20 30))) (PLUS (MINUS 10 20) (PLUS 20 30)) -> :s (MINUS 10 20) -> :s 10 -> :S 10 20 -> :S 20 (- A B) -> :s A -> :S 10 B -> :s 20 -10 -10 (PLUS 20 30) -> and so on. The interpreter internally sees Lisp code as lists and just prints the lists while it steps the code... If we wanted M-Expressions, then the things would needed to be converted everywhere/everytime, which is much less elegant than leaving everything in one notation. LISP 2 was an effort to modernize LISP and to switch to a different syntax.
- kazinator 2y ago
  RPN also means that the programming notation is only that. It doesn't give us a data notation, other than a flat sequence of words. This is why Lisp and Forth are not really comparable. In Lisp, you can write made-up words that don't have any previous definition (let alone operator arity), and clump them into whatever nesting you want. As long as you don't try to pass that through the standard evaluator, it's fine.
kragen 2y ago
postfix notation only needs a stack of numbers, it's shallower, and it does one operation per token. zuse's z3 didn't have much memory or complex control logic when you have said * + 3 4 - 5 (assuming dyadic operators) you have a stack containing an operator, a computed result, another operator, and an entered operand. when you complete the expression with 6 the computation of the result, -1, should trigger the lurking multiplication. the machine's sequencing is state-dependent by contrast, in 3 4 + 5 6 - * there are never more than three things on the stack in this expression, operators are never on the stack, and no input ever triggers more than one operation. from a user interface perspective, the user also gets faster feedback i just wrote a command-line postfix calculator in c on my cellphone touchscreen in 20 minutes. it's 31 lines of code. i think that to do that so simply with prefix you have to do it right to left, effectively making it postfix
adrian_b 2y ago
When the expression is interpreted, not compiled, postfix has the advantage that you only need to memorize the yet unused operands. With prefix, you have to memorize also the yet not executed operations and for each operation you need to memorize how many operands have already been provided for it, in order to execute the operation as soon as its last operand has been provided. So for a compiled language it does not matter much whether an expression is written with prefix notation or with postfix notation, but for an interpreted language the latter is more efficient.
boomlinde 2y ago
With postfix, numbers get pushed to the stack in the order you enter them and operators can be evaluated immediately. This way, intermediate results are always naturally available as you type an expression. On a HP calculator you'd usually see the intermediate results on-screen, but in dc you type p at any point to print the current top-of-stack. Prefix notation in its simplest form is essentially the same thing but backwards, and you would only get intermediate results if you start writing from the innermost expression, which is complicated by the fact that that expression doesn't appear in the order you normally type.

kstrauser 2y ago

I vastly prefer postfix for interactive use. I can enter a bunch of numbers and then decide what to do with them. With prefix, I start by typing operators when I haven’t even fully decided which numbers I’m going to be using with them. Basically, prefix emphasizes the operations and postfix emphasizes the numbers. Prefix is perfectly fine for entering formulas into code. In dc or any other scratchpad, I find postfix much, much more convenient.

somat 2y ago

They both remove the need for screwball operator precedence, but the lisp s-expression do it by putting everything in parentheses(or perhaps everything in function notation is the better way to put it) and RPN does it by making the stack an integral part of the mental model needed to understand it.

adrian_b 2y ago
The parentheses are needed in LISP only because many functions have a variable number of operands, so that parentheses are needed to show where is the end of the list of operands. In a language where all functions had a fixed number of operands, prefix notation (or function invocation in general) could be used without any parentheses. Parentheses are also required for postfix notation when functions with variable number of operands are accepted (e.g. the sum of an arbitrary number of operands).
- kazinator 2y ago
  The parentheses are needed in Lisp because the input is data and not code. There are no "functions" and "arguments" in the data; that's a particular interpretation imposed on the data. We wouldn't want the data notation to have an implicit shape which depends on the programming language semantics of the symbols which appear in it, like their arity.
  - adrian_b 2y ago
    Code is a special kind of data, i.e. the kind of data that can be the input of an interpreter or compiler. A LISP program is not (arbitrary) data, i.e. it does not contain arbitrary lists. Giving data, i.e. an arbitrary list to any LISP interpreter or compiler will just result in an error message and a translation failure. A LISP program contains only invocations of functions or macros (besides special forms) and each invocation has an associated list of arguments. While the classic LISP convention is to write the function/macro name after the opening parenthesis, this notation is equivalent with writing first the name of the function/macro followed by a list of arguments enclosed in parentheses. Conceptually, data in LISP, which consists of lists of values, should have used a different kind of brackets for delimiting a list. Because of the limitations of the character sets available in old computers, the round parentheses have a dual role in LISP, as delimiters for lists that are data and as delimiters for the lists of arguments used by function/macro invocations. The two roles are differentiated by the use of the QUOTE special form, which is just a workaround for not using two different kinds of brackets, which would more clearly differentiate LISP data and LISP code. If all the LISP functions or macros had a fixed number of arguments, then the LISP code, i.e. the invocations of functions or macros, could have been written without parentheses. In that case, the LISP data, i.e. lists, could have been delimited by round parentheses without using the QUOTE special form, which would not have been necessary.
    - _19qg 2y ago
      LISP is short of "List Processor". It was developed as a language & system for processing lists. The programming language LISP was supposed to have M-Expressions (M -> Meta) for code and S-Expressions for data. For example a call to append two lists would have looked like this: append[listvar;(PARIS BERLIN NEWYORK TOKYO)] The arguments are enclosed in square brackets. The second argument is written as an S-Expression. S-Expressions were the data notation and were enclosed in parentheses. Symbols were upper case. The names of operators and variables were lower case. The append call then looked like this: (APPEND LISTVAR (QUOTE (PARIS BERLIN NEWYORK TOKYO))) A conditional would have been: [eq[car[l];0] → cons[(ZERO);cdr[l]]; T → x] Which in S-expression only syntax is: (COND ((EQ (CAR L)) (CONS (QUOTE (ZERO)) (CDR L))) (T X)) As you can see the conditional would have a special infix syntax. > Because of the limitations of the character sets available in old computers, the round parentheses have a dual role in LISP, as delimiters for lists that are data and as delimiters for the lists of arguments used by function/macro invocations. No, the syntax above wasn't actually implemented at first. The M-Expression/S-Expression combination was hand translated into S-Expressions, since the Interpreter and Compiler took lists as input. The reason why the syntax is like this is not a lack of characters or so. The reason is because the language early on worked on code as list data and not on code as text. The input and output was then of list data. The famous "Read Eval Print Loop" reads data, evaluates it and prints the result in data format. It was thought that a later version of LISP had the M-Expression/S-expression syntax as surface syntax. But that did not get any traction, because the S-expressions would be visible in the programming tools anyway: debugger, code inspector, code stepper. Thus it was more convenient to stay in the s-expression syntax, than to convert S-Expressions both from and into M-Expressions/S-Expressions. For example a stepper for LISP code might look like this. :s is the single step command: CL-USER 8 > (step (plus (minus 10 20) (plus 20 30))) (PLUS (MINUS 10 20) (PLUS 20 30)) -> :s (MINUS 10 20) -> :s 10 -> :S 10 20 -> :S 20 (- A B) -> :s A -> :S 10 B -> :s 20 -10 -10 (PLUS 20 30) -> and so on. The interpreter internally sees Lisp code as lists and just prints the lists while it steps the code... If we wanted M-Expressions, then the things would needed to be converted everywhere/everytime, which is much less elegant than leaving everything in one notation. LISP 2 was an effort to modernize LISP and to switch to a different syntax.
kazinator 2y ago
RPN also means that the programming notation is only that. It doesn't give us a data notation, other than a flat sequence of words. This is why Lisp and Forth are not really comparable. In Lisp, you can write made-up words that don't have any previous definition (let alone operator arity), and clump them into whatever nesting you want. As long as you don't try to pass that through the standard evaluator, it's fine.

kragen 2y ago

postfix notation only needs a stack of numbers, it's shallower, and it does one operation per token. zuse's z3 didn't have much memory or complex control logic when you have said * + 3 4 - 5 (assuming dyadic operators) you have a stack containing an operator, a computed result, another operator, and an entered operand. when you complete the expression with 6 the computation of the result, -1, should trigger the lurking multiplication. the machine's sequencing is state-dependent by contrast, in 3 4 + 5 6 - * there are never more than three things on the stack in this expression, operators are never on the stack, and no input ever triggers more than one operation. from a user interface perspective, the user also gets faster feedback i just wrote a command-line postfix calculator in c on my cellphone touchscreen in 20 minutes. it's 31 lines of code. i think that to do that so simply with prefix you have to do it right to left, effectively making it postfix

adrian_b 2y ago

When the expression is interpreted, not compiled, postfix has the advantage that you only need to memorize the yet unused operands. With prefix, you have to memorize also the yet not executed operations and for each operation you need to memorize how many operands have already been provided for it, in order to execute the operation as soon as its last operand has been provided. So for a compiled language it does not matter much whether an expression is written with prefix notation or with postfix notation, but for an interpreted language the latter is more efficient.

boomlinde 2y ago

With postfix, numbers get pushed to the stack in the order you enter them and operators can be evaluated immediately. This way, intermediate results are always naturally available as you type an expression. On a HP calculator you'd usually see the intermediate results on-screen, but in dc you type p at any point to print the current top-of-stack. Prefix notation in its simplest form is essentially the same thing but backwards, and you would only get intermediate results if you start writing from the innermost expression, which is complicated by the fact that that expression doesn't appear in the order you normally type.