Improving mgcLisp's define syntax

mgcadmin 17-05-2025

When implementing mgclisp, I took a shortcut (gasp! horror!) when implementing user defined lambdas. Scheme, and pretty much every other modern lisp when defining a function allows you to write something like the following:

(define (add-two x y) (+ x y))

Which as we know is really just syntactic sugaring for the following expression:

(define add-two (lambda (x y) (+ x y)))

This second, "unsugared" version also happens to be the syntax for user defined functions in mgclisp. So how do I get my lisp to ah.. conform to the commonly expected syntax? Well, sit back and grab some coffee, because in todays post I'm going to describe how I massaged my interpreter into converting the first form into the second form, while still accepting both.

Working, though unsweetened

Before I talk about how I improved the implementation of the define special form, I should take a moment to describe how it was implemented originally. Special forms are those lisp expressions who's evaluation deviates from the normal eval/apply in that we make special exceptions on which terms get evaluated when, and define is one of the fundamental special forms.

Atom* sfDefine(List* args, List* env) {
    Atom* oprndA = first(args);
    Atom* oprndB = first(rest(args)->listval);
    String* nstr = makeString(oprndA->stringval->data, oprndA->stringval->len);
    env = envInsert(env, makeBindingAtom(makeBinding(makeSymbolAtom(nstr), oprndB)));
    return makeStringAtom(nstr);
]

The above code is straight forward implementation of creating a binding using operand A as the key with operand B as the bound value, it allows us to easily wrtie expressions such as the lambda example shown above, in addition to binding simple variables in the environment.

(define a 42)
(define b 29)
(define c  (+ a b))
(define d (lambda (m n) (+ m n))

With define being a special form, the evaluation rules for the above implementation has us not evaluate the first argument, but we do evaluate the second argument.   

setFlags(flags, NO_EVAL, EVAL, NO_EVAL);
specialForms = appendList(specialForms, createSpecialForm(makeString("define", 6), 2, flags, &sfDefine));

Keep that last part in mind, it will come into play in a little bit.

A Special Form of a Special Form

Because we want to change the syntax of our existing special form, but only in some circumstances, we essentially want to make a special form of a special form. In a language with a traditional abstract syntax tree, we would implement this in the parsing phase, perhaps creating different types of "define" nodes for our AST. If you've read my post on parsing lisp expressions, then you already know why this is a fundamentally wrong approach for lisp. If you don't then go back and read that post, ok? Great.

Since we aren't implementing this change during parsing, we're left to implement it at run time. Now when the procedure for handling a special form is called, we start similarly but, now we check the type of the first operand, and if it's a list instead of a symbol then we should handle it as our special special form.

So how do we handle our special special form? Actually quite similarly to what we did before. Not only do we know that the first operand being a list is meant to be a lambda, we also know that the first member of that list is meant to be the name of the lambda, the rest of the list its parameters, and operandB should be the body. Armed with that knowledge, its all fairly straight forward:

Atom* sfDefine(List* args, List* env) {
    Atom* oprndA = first(args);
    Atom* oprndB = first(rest(args)->listval);
    String* nstr = NULL;
    if (typeOf(oprndA) == AS_LIST) {
        nstr = makeString(first(oprndA->listval)->stringval->data, first(oprndA->listval)->stringval->len);
        List* fargs = rest(oprndA->listval)->listval;
        List* body = oprndB->listval;
        Function* func = makeLambdaFunction(fargs, body, env);
        env = envInsert(env, makeBindingAtom(makeBinding(makeSymbolAtom(nstr), makeFunctionAtom(func))));
    } else {
        nstr = makeString(oprndA->stringval->data, oprndA->stringval->len);
        env = envInsert(env, makeBindingAtom(makeBinding(makeSymbolAtom(nstr), eval(oprndB, env))));
    }
    return makeStringAtom(nstr);
}

The keen eyed among you may notice however, that in the case we aren't defining a lambda, we have now wrapped the value being bound in an call to eval(). This is because we have to change the associated rules for our new syntax to work, otherwise we risk the function trying to access variables that havent been bound in its environment.

    setFlags(flags, NO_EVAL, NO_EVAL, NO_EVAL);
    specialForms = appendList(specialForms, createSpecialForm(makeString("define", 6), 2, flags, &sfDefine));

And now, we can happly execute either form of function definition as well as binding simple variables:

MGCLisp Loaded Successfully.
misp(0)> (define (fib n) (if (lt n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))
 => fib
misp(1)> (fib 6)
 => 13
misp(2)> (define fact (lambda (x) (if (lt x 2) 1 (* x (fact (- x 1)))))
 => fact
misp(3)> (fact 5)
 => 120
misp(4)> (define a 13) 
 => a
misp(5)>

That's what I've got for today, until next time Hapy Hacking!

---