Could a concatenative language use prefix notation?

Question

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.

Answer 1

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.

Answer 2

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] [] -> []]

Answer 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.

Answer 4

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.