[sparkie]

When I learned Scheme, I liked the language but strongly disliked macros and quotation. I'd only been using it a short while and when I searched for solutions to a few problems these "fexpr" things kept appearing up, which i didn't understand, and this "Kernel" language. I decided to learn it since "fexprs" were apparently the solution to several of my problems. This wasn't easy at first - I had to read the Kernel Report several times, but I ended up finding it way more intuitive than using macros and quotes.

I've not written a Scheme macro since. I've written hundreds of Kernel operatives though.

I was also a typoholic previously, but am in remission now thanks to Kernel.

https://web.cs.wpi.edu/~jshutt/kernel.html

[pfdietz]

Think of macros as what you want when you want to perform computation at compile time rather than run time.

An example: building the equivalent of a switch statement, but that compares (via string equality) with a set of strings. The macro would translate this into code that would do something like a decision tree on string length or particular characters at particular positions.

Basically anything that's done with a preprocessor in another language can be done with macros in Lisp family languages.

[brabel]

The other motivation for me is to drastically reduce boilerplate code. I can’t believe people here are saying they never use macros, they are so good for this that avoiding them sounds to me like a skill issue! Overuse can damage readability, sure, but so can pretending macros are not an option.

[sparkie]

Operatives do that for me, better than macros. Parent is correct that macros are compile time, which gives them a performance advantage over operatives - but IMO, they're not better ergonomically. I find operatives simpler, cleaner and more powerful.

[pfdietz]

I hadn't heard of operatives. Can you describe them or provide a link?

[sparkie]

Operatives are based on FEXPRS from older lisps - they're basically a function-like form, but where the operands are not implicitly reduce at the time of call.

    (foo (+ 2 3) (* 3 4))
    ($bar (+ 2 3) (* 3 4))

`foo` is a function, when it is combined with the arguments, it receives the values 5 and 7.

`$bar` however, receives its operands verbatim. It receives (+ 2 3) as its first operand and (* 3 4) as its second - unevaluated.

The operative/FEXPR body decides how to evaluate the operands - if at all.

The difference between an operative/FEXPR and a macro is that macros are second-class objects which must appear in their own name - we cannot assign them to variables, pass them or return them from functions. Operatives and FEXPRs are first-class objects that can be treated like any other.

The difference between FEXPRs and Operatives is to do with scoping and environments. FEXPRs were around before Scheme - when Lisps were dynamically scoped. This meant we could have unpredictable behavior and so called "spooky action at distance". They were problematic and basically abandoned almost entirely in the 1980s.

Shutt introduced Operatives as a more hygienic version - based on statically scoped Scheme. Instead of the operative being able to mutate the dynamic environment arbitrarily, there are limitations. The first part of this is that environments are made into first-class objects - so we can assign them to a symbol and pass them around. The final part is that an operative receives a reference to the dynamic environment of its caller - which we bind to a symbol using the operative constructor, `$vau`.

    ($vau (operands) dynamic-env . body)

Compare to:

    ($lambda (arguments) . body)

So operatives are called in the same way a function is called - but the operands are not reduced, and the environment is passed implicitly.

The body can decide to evaluate the operands using the environment of the caller - essentially behaving as if the caller had evaluated them

    (eval operands dynamic-env)

But it can chose other evaluation strategies for the operands - such as evaluating them in a custom created environment which we can make with (make-environment) or ($bindings->environment).

This also allows the operative to mutate the environment of its callee - but only the locals of that environment. The parent environments cannot be mutated through the reference `dynamic-env`.

Technically, `$lambda` is not primitive in Kernel - though it is the main constructor of applicatives (functions) - the primitive constructor is called `wrap` - and it takes another combiner (an operative or applicative) as its parameter. Wrapping a combiner simply forces the evaluation of its arguments when called - so functions are just wrappers around operatives - and the underlying operative of any function can be extracted with `unwrap`.

There's a lot more to them. They're conceptually quite simple in terms of implementation, but they have enormous potential use cases that are unexplored.

Read more on the Kernel page[1]. In particular, the Kernel report[2]. There's also a formal calculus describing them, called the vau calculus[3].

[1]:https://web.cs.wpi.edu/~jshutt/kernel.html

[2]:https://ftp.cs.wpi.edu/pub/techreports/pdf/05-07.pdf

[3]:https://web.archive.org/web/20150224035948/http://www.wpi.ed...

[pfdietz]

Hmm, this sounds like exactly the opposite of what I was talking about. It delays execution rather than promoting execution to compile time.

What I had expected you to talk about was some way of getting the compile time execution of macros by a sufficiently smart compiler that could do extensive partial evaluation at compile time, including crossing procedure boundaries. Of course that's antithetical to the Lisp philosophy of allowing dynamic redefinition of functions and such.

[pfdietz]

In Common Lisp macros can also be used to implement a kind of Aspect-Oriented Programming, using the macroexpand hook. This hook enables macroexpansion to be dynamically modified at compile time without changing the source code.

[sparkie]

I understand the use case, but Scheme macros never felt intuitive to me. I think it may be the quotation more than anything that I dislike - though I also dislike that they're second class (which was the key thing which led me to Kernel).

I use C preprocessor macros extensively and don't have the typical dislike for them that many people have - though I clearly understand their limitations and the advantage Scheme macros have over them.

Since learning Kernel, the boundary of "compile time" and "runtime" is more blurry - I can write operatives which behave somewhat like a macro, and I do more "multi-stage" programming, where one operative optimizes its argument to produce something more efficient which is later evaluated - though there are still limitations due to the inability to fully compile Kernel.

As one example, I've used a kind of operative I call a "template", which evaluates its free symbols ahead of time but doesn't actually evaluate the body. When we later apply the some operands it replaces the bound symbols with the operands, looking up any symbols to produce an expression which we don't need to immediately evaluate either - but this expression has all symbols fully resolved. This is somewhere between a macro and regular operative.

Consider:

    ($define! z 10)

    ($define! @add-z
        ($template (x y)
            (+ x y z)))

In this template `x` and `y` are bound variables and `+` and `z` are free. The template resolves the free symbols and returns an operative expecting 2 operands, effectively providing an operative with the body:

    ([#applicative: +] x y 10)

When we call the template with the two operands, it resolves any symbols in the arguments and returns the full expression with no symbols present, but it doesn't evaluate the expression yet.

    > ($let ((x 9)
             (y 7))
          (@add-z (* x 3) (- y 13)))
    ([#applicative: +] ([#applicative: *] 9 3) ([#applicative: -] 7 13) 10)

When we decide to evaluate the expression, no symbol lookup is necessary - it can perform the operation rather quickly, despite the slow interpretation.

---

The $template form above isn't too difficult to implement. I've iterated several forms of this - some which only partially resolved the bound symbols, but lost them in a RAID failure. An earlier version which has some issues I still have because I put it online:

    ($provide! ($template)
        ($define! $resolve-free-symbols
            ($vau (params expr) env
                ($cond
                    ((null? expr) ())
                    ((pair? expr)
                        (cons (apply (wrap $resolve-free-symbols) 
                                     (list params (car expr)) 
                                     env)
                              (apply (wrap $resolve-free-symbols) 
                                     (list params (cdr expr)) 
                                     env)))
                    ((symbol? expr)
                        ($if (member? expr params)
                             expr
                             (eval expr env)))
                    (#t expr))))

        ($define! $resolve-bound-symbols
            ($vau (params expr) env
                ($cond
                    ((null? expr) ())
                    ((pair? expr)
                        (cons (apply (wrap $resolve-bound-symbols)
                                     (list params (car expr))
                                     env)
                              (apply (wrap $resolve-bound-symbols)
                                     (list params (cdr expr))
                                     env)))
                    ((symbol? expr)
                        ($if (member? expr params)
                             (eval expr env)
                             expr))
                    (#t expr))))

        ($define! zip
            ($lambda (fst snd)
                ($cond
                    (($and? (null? fst) (null? snd)) ())
                    (($and? (pair? fst) (pair? snd))
                        (cons (list (car fst)
                                    (list* (($vau #ignore #ignore list)) (car snd)))
                              (zip (cdr fst) (cdr snd)))))))

        ($define! $template
            ($vau (params body) senv
                ($let ((newbody 
                        (eval (list $resolve-free-symbols params body) senv)))
                    ($vau args denv
                        (eval (list $resolve-bound-symbols params newbody)
                              (eval (list* $bindings->environment
                                           (zip params args))
                                    denv))))))) 

---

At present the best interpreter is klisp, and the fastest is bronze-age-lisp, which uses klisp - with parts of hand-written 32-bit x86 assembly.

I've been working on a faster interpreter for a number of years as a side project, optimized for x86_64 with some parts C and some parts assembly. It has diverged in some parts from the Kernel report, but still retains what I see are the key ingredients.

My modified Kernel has optional types, and we have operatives to `$typecheck` complex expressions ahead of evaluating them. I intend to go all in on the "multi-stage" aspect and have operatives to JIT-compile expressions in a manner similar to the above template.

[orthoxerox]

Which implementation do you use?

[sparkie]

I use klisp[1] and bronze-age-lisp[2] mostly for testing, as they're the closest to a feature complete implementation of the Kernel Report.

I've written a number of less complete interpreters over the years. I currently have a long-running side-project to provide a more complete, highly optimized implementation for x86_64.

[1]:https://github.com/dbohdan/klisp

[2]:https://github.com/ghosthamlet/bronze-age-lisp