3

Concatenative languages have some very intriguing characteristics, such as being able to compose functions of different arity and being able to factor out any section of a function. However, many people dismiss them because of their use of postfix notation and how it's tough to read. Plus the Polish probably don't appreciate people using their carefully crafted notation backwards.

So, is it possible to have prefix notation? If it is, what would the tradeoffs be?

I have an idea of how it could work, but I'm not experienced with concatenative languages so I'm probably missing something. Basically, a function would be evaluated in reverse order and values would be pulled from the stack in reverse order. To demonstrate this, I'll compare postfix to what prefix would look like. Here are some concatenative expressions with the traditional postfix notation.

5 dup *                             ! Multiply 5 by itself
3 2 -                               ! Subtract 2 from 3
(1, 2, 3, 4, 5) [2 >] filter length ! Get the number of integers from 1 to 5
                                    ! that are greater than 2

The expressions are evaluated from left to right: in the first example, 5 is pushed on the stack, then dup duplicates the top value on the stack, then * multiplies the top two values on the stack. Functions pull their last argument first from the stack: in the second example, when - is called, 2 is at the top of the stack, but it is the last argument.

Here is what I think prefix notation would look like:

* dup 5
- 3 2
length filter (1, 2, 3, 4, 5) [< 2]

The expressions are evaluated from right to left, and functions pull their first argument first from the stack. Note how the prefix filter example reads much more closely to its description and looks similar to the applicative style. One issue I noticed is factoring things out might not be as useful. For example, in postfix notation you can factor out 2 - from 3 2 - to create a subtractTwo function. In prefix notation you can factor out - 3 from - 3 2 to create a subtractFromThree function, which doesn't seem as useful.

Barring any glaring issues, perhaps a concatenative language that uses prefix notation could win over the people who dislike postfix notation. Any insight is appreciated.

Community
  • 1
  • 1
Risky Martin
  • 2,491
  • 2
  • 15
  • 16
  • Composition looks way better in postfix notation, you write it in the order of the data flow. This feels unnatural and awkward — neither applicative nor concatenative. – Cat Plus Plus Mar 02 '12 at 23:12
  • 1
    But for someone who's used to seeing a function name followed by its parameters, doesn't this style seem more inviting? The filter example looks very similar to its Haskell counterpart, except it doesn't require any funky composition operators or parenthesis. The predicate is awkward, but maybe there's a way to make it look better. – Risky Martin Mar 03 '12 at 00:30
  • It's a paradigm switch, there are always things you need to get used to. It's the same with functional vs imperative — someone coming from latter will be used to variables being mutable and actions always happening sequentially, but that's not an argument to change fundamental properties of functional languages. And after switching to concatenative, postfix just feels natural. – Cat Plus Plus Mar 03 '12 at 00:55
  • Hybrid languages exist. F# combines the functional, procedural, and object oriented paradigms. If data flowing the opposite way is the only big issue in using prefix notation in a concatenative language, then I think that is a great way to get people who consider postfix to be a deal breaker to enjoy the other benefits of concatenative languages. Then who knows? Maybe one day they will realize that it makes more sense for data to flow with the function calls. – Risky Martin Mar 03 '12 at 04:45
  • 1
    Any specific reason that you wrote the predicate `[< 2]` last instead of before the list? – day Jan 23 '13 at 12:38
  • @plmday No major reason. I just wanted to make it consistent with the ordering in the subtraction example, with the subject being first. This is also the ordering that folks in the imperative world would be most used to. That would make composition quite bothersome though. – Risky Martin Jan 24 '13 at 01:10

4 Answers4

5

Well certainly, if your words are still fixed-arity then it's just a matter of executing tokens right to left.

It's only because of n-arity functions that prefix notation implies parenthesis, and it's only because of wanting human "reading order" to match execution order that being a stack language implies postfix.

AshleyF
  • 3,682
  • 1
  • 25
  • 23
  • Thanks for the simple objective answer. I'm also curios about what the tradeoffs would be, but that is more of a hypothetical and subjective discussion. – Risky Martin Sep 03 '12 at 18:21
  • As for trade offs: I believe that with fixed-arity words, prefix and postfix are exactly equivalent as far as the machine cares. You can literally just flip things around or execute in reverse. The humans may care, depending on whether they're a top-down or a bottom-up kind of person :) Some people like to see "if x do y" for example while others prefer "do y when x".I personally like having no forward references – AshleyF Sep 04 '12 at 13:06
  • ...not even to arguments. So postfix is nice. But I think it's just a preference that makes no essential difference. Maybe both the machine and I should just read "backwards" :) – AshleyF Sep 04 '12 at 13:15
  • 1
    I do see the problem you point out with non-commutative ops, trying to keep args in infix order. Your 3 2 - would become - 2 3, but still mean 3 - 2 to keep the "concatenative" properties. Again though, it's just a human convention to think in infix. In early grade school kids write the 3 above the 2 with the - to the left. Maybe they would be comfortable with prefix if they hadn't later had infix drilled into them. Another aside: Chuck Moore in his colorForth actually chose to reverse the order for subtraction with 2 3 - meaning 3 - 2. Now that's just *crazy*, but hey, why not? :) – AshleyF Sep 04 '12 at 15:59
  • So can I infer that if a concatenative language introduces variadic words, parentheses are needed? – day Jan 23 '13 at 12:43
  • 1
    Yes, or another approach is to keep fixed-arity but allow collections as an argument type (with delimiting syntax for those). Joy, for example, does this with square-bracketed lists (and quotations) and curly-braced sets, but no delimiters for arguments. – AshleyF Jan 25 '13 at 02:40
  • Looking back at this years later now, I do see one issue with saying, "it's just a matter of executing tokens right to left." If any of the words have side effects and the human is reading left-to-right then executing in reverse has confusing effects! I was blinded by thinking purely functionally. – AshleyF May 16 '18 at 20:11
  • One more issue with prefix is that some associative operators may need to be reversed to make partial application more natural. For example, `let 'half [/ 2]` looks nice, but requires `/` to be defined such that it's first argument is divided into the second (e.g. `/ 2 6` -> `3`; opposite to what seems "natural". In postfix `6 2 /` is in the "natural" RPN-style order. And partial application in definitions such as `: half 2 / ;` works too. – AshleyF Feb 23 '21 at 19:37
3

I'm writing such a language right now as it happens, and so far I like some of the side-effects of using prefix notation. The semantics are based on Joy:

  • Files are parsed from left to right, but executed from right to left.
  • By extension, definitions must come after the point at which they are used.
  • As a nice side-effect, comments are simply lists which are dropped.

Here's the factorial function, for instance:

def 'fact [cond [* fact - 1 dup] [1 drop] dup]

I also find it easier to reason about the code as I'm writing it, but I don't have a strong background in concatenative languages. Here's my (probably-naive) derivation of the map function over lists. The 'nb' function drops something and is used for comments. 'stash [f]' pops into a temp, runs 'f' on the rest of the stack, then pushes the temp back on.

def 'map [q [cons map stash [head swap i] dup stash [tail dup]] [nb] is_cons nip]
nb [map [f] (cons x y) -> cons map [f] x f y
    stash [tail dup]    [f] (cons x y)       = [f] y (cons x y)
    dup                 [f] y (cons x y)     = [f] [f] y (cons x y)
    stash [head swap i] [f] [f] y (cons x y) = [f] x (f y)
    cons map            [f] x (f y)          = cons map [f] x f y

    map [f] [] -> []]
Spencer Tipping
  • 31
  • 2
3

I just came from reading about the Om Language

Seems just what you are talking about. From it's description (emphasis mine):

The Om language is:

  • a novel, maximally-simple concatenative, homoiconic programming and algorithm notation language with:
    • minimal syntax, comprised of only three elements.
    • prefix notation, in which functions manipulate the remainder of the program itself. [...]

It also states that it's not finished, and will experience much change yet.

Still, it seems to be working, and really interesting as proof of concept.

fede s.
  • 582
  • 3
  • 17
1

I imagine a concatenative prefix language without stack. It could call functions, which would then themselves interpret code until they got all needed operands. Interpreter would then call next function. It would only need one memory construct - the result. Everything else could be read from the source code at time of execution. As you might have noticed, I am talking about interpreted language, not compiled one.

majTheHero
  • 123
  • 1
  • 13
  • Interesting idea. How would you handle multiple intermediate results? Like in the prefix expression `- + 1 1 + 3 3`, how would you keep track of the results of `+ 1 1` and `+ 3 3`? – Risky Martin May 09 '12 at 17:22
  • I don't know. Check out XY, a concatenative language with queue instead of stack. There are also some other languages that could be referenced. – majTheHero Oct 16 '12 at 13:20