Can you recommend an implementation for experimenting with Kernel? I'm unsure about the implications of the wrap/unwrap primitives and how they interact with apply, so more interested in a correct/reference implementation than a high performance one.
klisp is the most complete implementation I've used. Website is now down and original bitbucket host too, but mirror here: https://github.com/dbohdan/klisp
Performance will never be great due to the nature of the language, which is incompatible with usual forms of compilation.
I'll try to give a brief explanation of wrap and unwrap.
A combination is of the form `(combiner combiniends)`, where combiner must be either an operative or applicative. In the case that it is operative, the combiniends are passed verbatim to the operative, without being reduced. If the combiner is applicative, the combiniends are reduced, by evaluating each item in the list using the metacircular evaluator, until a list of arguments is returned. The arguments are then passed to the underlying combiner of the applicative.
Operatives are constructed using `$vau`, and applicatives by using `wrap` on another combiner. Usually the underlying combiner is operative, but the language used in the report is clearly permitting you to wrap other applicatives too, so in the case that you evaluate an applicative whose underlying combiner is applicative, and the underlying combiner of that is operative, then the list of combiniends would be reduced twice before being passed to the final operative. I've honestly not encountered a single use-case for this in my time using Kernel, but who knows. It might just be easier to consider that `wrap` wraps operatives into applicatives.
The description of the evaluator from section 3 of the report is a pretty clear explanation of what happens.
* If the expression to be evaluated is a pair, then:
* The car of the pair must be a combiner
* If the combiner is operative, call the operative with the cdr of the pair
* If the combiner is applicative, evaluate cdr of the pair to produce an argument list 'd. eval the cons of the the underlying combiner of the applicative with 'd.
($define! eval
($lambda (o e)
($if (not (environment? e)) (exit))
($if (pair? o)
($let ((c (car o)))
($if (operative? c)
(call c (cdr o) e)
($if (applicative? c)
(eval (cons (unwrap c) (eval-list (cdr o) e)) e)
(error "not a combiner in combiner position"))))
o)))
($define! eval-list
($lambda (l e)
($if (null? l)
()
($if (pair? l)
(cons (eval (car l) e)
(eval-list (cdr l) e)
(error "operand to applicative must be a list"))))))
Yep, it's the `(wrap (wrap operative))` which stands out as strange. Thank you for the evaluator - factoring as a call which only acts on operatives makes it clear.
The inner call I expected was more like:
($cond (operative? c)
(apply c (cdr o) e)
(applicative? c)
(apply (unwrap c) (eval-list (cdr o) e) e)
(error "bad times"))
where that would only convert an applicative into an operative once. Interesting that you haven't come across a use for the multiple reduction on arguments.
The difficulty I have with the multiple wrap model is you don't know how many times to evaluate the arguments until you have evaluated the car of the list (I think your eval is missing an evaluation on the head of the list, probably at the let binding, as otherwise ((lambda (x) x) 42) fails).
- If the car of the list is an operative, call it on the arguments. Simple.
- If the car of the list is a applicative (wrap operative), eval the arguments, call it on the result.
Those extend easily to eval the head of the list first, once, and then test what sort of function it is. However given a function which evaluates the arguments N times (via N wraps over an operative), for N > 1, it feels like the head of the list should also be evaluated N times. But it can't be, because we don't know N until we know the head of the list.
That could be made to work with semantics of continue evaluating the head of the list until a fixpoint (e.g. a self-evaluating function), and then look at the tail, but that's a significant increase in complexity over evaluating the head exactly once.
The alternative setup would be (= (wrap (wrap an-operative)) (wrap an-operative)) where N wraps have the same effect as one. You lose some syntactic expressivity - functions that actually want to evaluate the arguments multiple times would have to call eval themselves instead of writing an extra wrap - but I think you get simpler core semantics.
> I think your eval is missing an evaluation on the head of the list, probably at the let binding, as otherwise ((lambda (x) x) 42) fails)
You're correct. I was going off the top of my head and forgot the precise implementation, but it's stated clearly in the report.
Otherwise, o is a pair. Let a and d be the car and cdr of o. a is evaluated in e; call its result f.
> However given a function which evaluates the arguments N times (via N wraps over an operative), for N > 1, it feels like the head of the list should also be evaluated N times. But it can't be, because we don't know N until we know the head of the list.
This is why we cons the underlying combiner with the reduced argument list, then recursively call eval. It will keep on reducing until the combiner is operative.
> functions that actually want to evaluate the arguments multiple times would have to call eval themselves instead of writing an extra wrap
There's a discussion in the report as to whether wrap should even be in the language, since you can create a wrap with an operative, but then unwrap is non-trivial.
Honestly, I think it's much simpler to only wrap operatives. I don't think our minds are good at comprehending what will happen as a result of evaluating lists of arguments multiple times, and it's easier to implement - you can make the evaluator simpler by removing the recursive call to eval for applicatives and replace it with a direct call to the underlying operative.
> The alternative setup would be (= (wrap (wrap an-operative)) (wrap an-operative)) where N wraps have the same effect as one.
I think attempting to wrap an applicative should error in the same way attempting to unwrap an operative would, since our expectation would be that `wrap` takes an operative as its argument rather than any combiner.
TBH, I've not really searched for problems for which evaluating the arguments multiple times would be a nice solution. I think they probably exist but as you suggest, the programmer could approach this by providing an operative which performs multiple reduction.
