6.6 Infix Notation

Infix

One of the main complaints that some people have with Lisp is the fact that mathematical formulas lack a certain readability.

If you compare the following expressions:

# Infix
x^^3 + 10*x^^2 + 2*x - 1

and

; prefix 
(- (+ (^^ x 3) (* 10 (^^ x 2)) (* 2 x)) 1)

Most people will bizarrely be more confortable with the first expression than with the pure Lisp version.

Infix Operator

LispE provides a specific operator: infix that allows LispE expressions to be written infixed. The only constraint is that operators and operands must be separated with a space.

These expressions are compiled on the fly and replaced in the code with their actual LispE interpretation. The way the expression is compiled takes into account the traditional notion of operator precedence.

It is also possible to have an idea of how these expressions are actually compiled if you put them in a lambda in the console, which will display how the infix expression was handled. Furthermore, note that the infix operator only applies to the top expression in parentheses. If you have a sub-expression within the expression, you will need to use the infix operator again.

infix or /\ or • or §

These four operators are all equivalent.

; This is compiled as (lambda (x) (- (+ 10 20) (* 4 x)))
(lambda (x) (infix 10 + 20 - 4 * x)) 

; This is compiled as (lambda (x) (- (+ (^^ x 3) (* 10 (^^ x 2)) (* 2 x)) 1))
(lambda (x) (• x ^^ 3 + 10 * x ^^ 2 + 2 * x - 1)) 

; This is compiled as (lambda (x) (- (+ (* 10 (^^ (- x 1) 2)) (* 2 (- 4 x))) 1))
; If you don't use the infix operator in an expression, you need to write it as usual
(lambda (x) (/\ 10 * (§ x - 1) ^^ 2 + 2 * (- 4 x) - 1)) 

Algorithm

The algorithm in LispE is quite simple. It takes for granted that the expression has already been transformed into a list.

The operators are all placed every two elements intertwined with the different values.

//Our list contains: (infix V1 op1 V2 op2 V3 ... Vn)
//we scan the operators in the list every two slots with iop
// The expression should have an even number of elements
Element* infix(LispE* lisp) {
    if (listsize % 2)
        throw new Error("Error: Infix expression is malformed");
    //We will use two lists to handle our prefix translation
    List* operations = new List;
    //root points to the top list
    List* root = operations;

    Element* op = liste[2]; //the first operator is at position 2
    long iop = 4; //the next operator is at position 4
    long ival = 1; //the values start at position 1
    operations->append(op); //We push our operator in prefix position

    while (ival < listsize) {

        //We check the sequence of operators of the same kind
        for (; iop < listsize - 1; iop+=2) {
            //If it is a different operator: 10 + 20 + 30 + 40 (*) 4 + 5
            if (op != liste[iop]) {
                op = liste[iop];
                break;
            }
        }

        //we then push all the values up to '*' for instance (10 20 30 40)
        for (;ival < iop; ival += 2)
            operations->append(liste[ival]);

        if (iop < listsize -1) {
            //If this operator is + or -, we create one level up
            // This is where operator precedence is handled
            if (op->type == l_plus || op->type == l_minus) {
                //We can reuse this structure if the operator is the same
                //as the top one... Else we create a new top level
                // it happens for 10 + 20 + 30 + 40 * 4 (+) 5
                // root is (+ 10 20 30 (* 40 4)), we share the same structure
                if (op->type != root->index(0)->type) {
                    List* inter = new List;
                    inter->append(op);
                    inter->append(root);
                    root = inter;
                }
                //In all cases, operations points to the top level
                operations = root; //operations is now (+ 10 20 30 (* 40 4))
            }
            else {
                //We create one level down.
                //We feed this new List with the last element of the current list
                List* inter = new List;
                inter->append(op);
                Element* last = operations->liste.back(); 
                operations->liste.pop_back(); //The first element is removed from the current list
                inter->append(last); // inter is (* 40)
                operations->append(inter); //operation is now (+ 10 20 30 (* 40))
                operations = inter; //operation is now (* 40)
            }
        }
        iop += 2;
    }
    return root;
}