Probably Programming

Prefix notation?

Have you ever dreamed of a language which uses strictly prefix (a.k.a. polish, Łukasiewicz) notation?

No? Well, I can’t say I’m surprised. Lisp is often called a prefix notation language, but I’ll let you in on a secret, it’s not purely prefix notation. It uses another notation you’ve probably never heard of: outfix notation.

Outfix notation?

I’d say I made outfix notation up, but I found a reference to it on abstractmath.org, so I at least have something to back this claim up with. Basically, the parentheses are a function which says, “put these items into a list.”

Of course, Lisp uses lists for everything, so you can hardly call it a prefix notation language any more.

Real prefix notation

Now, how about making a real prefix notation language? A real prefix notation language needs no parentheses because it knows how many arguments each function takes, so it can simply pull in the next two expressions following the function name.

A real prefix notation language is a piece of cake to implement, as long as every function has a fixed arity and that arity is known at compile time. Of course, then how do we represent things such as lists with varying amounts of items. How do we pass a variable number of arguments to a function?

The same way Lisp does, we use a list.

(more…)