CLRHack: Multiple return values

Multiple Return Value Implementation in CLRHack

The CLRHack compiler implements Multiple Return Values (MRV) by extending the single-value limitation of the .NET Common Intermediate Language (CIL) stack through a thread-local side-channel. This allows Lisp forms to communicate multiple values (up to 64) across function boundaries.

1. The Side-Channel Storage

Because a CIL method can only return a single object on the stack, CLRHack utilizes a static class [LispBase]Lisp.Values. This class contains [ThreadStatic] fields that act as a secondary communication channel:

• Primary Value: Always resides on the CIL evaluation stack.
• ReturnCount: An int32 field indicating the total number of values returned (including the primary one).
• Value1 through Value63: Object fields that store the second through sixty-fourth return values.

2. Producing Multiple Values (The Staging Logic)

To prevent corruption during evaluation, the values form uses a Stage-and-Commit strategy. This is necessary because the side-channel is global to the thread; if a sub-expression inside a values form itself returns multiple values, it would overwrite the global fields before the outer values form is finished.

The compilation process for (values form1 form2 ... formN) follows these steps:

1. Evaluation: Each form is evaluated in order.
2. Local Staging: The result of form1 is kept on the stack. The results of form2 through formN are immediately stored into method-local variables (temporaries). This ensures that if form3 calls a function that returns multiple values, the result of form2 is safely tucked away in a local variable and cannot be overwritten.
3. Commitment: After all forms are evaluated, the compiler generates code to move the values from the local temporaries into the global Value1...ValueN fields.
4. Finalization: The ReturnCount is set to N.

3. Preservation across Control Flow

Certain Lisp constructs must evaluate sub-forms without allowing those sub-forms to interfere with the return values of the primary form. This is handled by a Save-Restore pattern.

Multiple-Value-Prog1

The multiple-value-prog1 form evaluates its first form, then saves the entire side-channel state (the primary value, the ReturnCount, and all ValueN fields) into local variables. It then evaluates the subsequent forms. After they finish, it restores the side-channel state from its locals, ensuring the values of the first form are what the caller receives.

Unwind-Protect

In unwind-protect, the protected form is evaluated and its primary result is stored in a local variable. Crucially, the finally block (cleanup) must not destroy the side-channel state produced by the protected form. The compiler generates code at the start of the finally block to save ReturnCount and Value1...63 into locals. Once the cleanup forms complete, the state is restored from these locals before the method returns.

4. Nested Multiple Values (The Re-entrancy Problem)

The fundamental problem with a global side-channel is re-entrancy. If the compiler were to store form2 directly into the global Value1 field, and then form3 involved a function call like (some-func), that function might execute its own (values ...) logic. This would overwrite the global Value1 that was just set for the outer form.

By enforcing the use of method-local temporaries during the production of values, CLRHack ensures that the global side-channel is only updated at the last possible moment ("atomically" relative to the Lisp expression), effectively shielding the return values from being corrupted by nested evaluations.

CLRHack: Tail Recursion

Tail-Call Handling in CLRHack

I decided to make proper tail recursion a fundamental requirement in CLRHack. This prevents stack overflow errors during standard recursive patterns and ensures the runtime remains stable regardless of recursion depth. Technically, Common Lisp isn't required to be tail recursive, but I want mine to be.

1. Tail Position Identification

The compiler performs a structural analysis of the Abstract Syntax Tree (AST) to identify "tail positions." An expression is in a tail position if its value is the final result of the function, meaning no further work remains to be done in the current frame after the call returns. The generate-step2 walker propagates a tail-p flag through the following logic:

• Functions/Lambdas: The final expression in the body is in the tail position.
• Conditionals (IF): Both the "then" and "else" branches are in the tail position.
• Sequences (PROGN/LET): Only the very last form in the sequence is in the tail position.
• Blocks: The last form of a BLOCK is in the tail position, provided the block is not the target of a RETURN-FROM.

2. CIL Instruction Emission

To implement proper tail-call semantics, the compiler utilizes the native tail. prefix in the Common Intermediate Language (CIL). When a function call is detected in a tail position, the compiler applies the following mandatory transformation:

1. The Prefix: It prepends the tail. opcode to the call or callvirt instruction.
2. The Return: It immediately follows the call with a ret (return) instruction.

The tail. prefix instructs the .NET Just-In-Time (JIT) compiler to discard the current method's stack frame before jumping to the target function. This ensures that the call consumes zero additional stack space, turning the recursive call into a semantic jump.

3. Safety and Context Constraints

The implementation of tail-calls is subject to specific safety rules imposed by the Common Language Runtime (CLR) to maintain execution integrity:

• Protected Regions: The CLR prohibits tail. calls inside try, catch, or finally blocks. Because Lisp constructs such as unwind-protect and handler-case rely on these CIL features, tail-call elimination is suspended within these specific scopes to ensure cleanup handlers and error recovery mechanisms function correctly.
• Frame Cleanup: The compiler ensures that all local resources are in a valid state before the tail. prefix is issued, allowing the CLR to safely deallocate the current frame.

Example CIL Output

Consider a recursive counter that must be able to run indefinitely:

  (defun count-down (n)
    (if (= n 0)
        "Done"
        (count-down (- n 1))))
  

The compiled CIL for the recursive branch is transformed to ensure stack neutrality:

      ; ... code to calculate (- n 1) ...
      tail.
      call object Program::'COUNT-DOWN'(object)
      ret
  

By strictly enforcing this pattern, CLRHack guarantees that recursive programs can execute with constant stack space, fulfilling my core requirement of tail recursion.

Pseudo

I was wondering what it would look like if a large language model were part of your programming language. I'm not talking about calling the model as an API, but rather embedding it as a language construct. I came up with this idea as a first cut.

The pseudo macro allows you to embed pseudocode expressions in your Common Lisp code. It takes a string description and uses an LLM to expand it into an s-expression. You can use pseudo anywhere an expression would be expected.

(defun my-func (a b)
  (pseudo "multiply b by factorial of a."))
MY-FUNC

(my-func 5 3)
360

(defun quadratic (a b c)
  (let ((d (sqrt (pseudo "compute discriminant of quadratic equation"))))
    (values (/ (+ (- b) d) (* 2 a)) (/ (- (- b) d) (* 2 a)))))
QUADRATIC

(quadratic 1 2 -3)
1.0
-3.0

The pseudo macro gathers contextual information and packages it up in a big set of system instructions to the LLM. The instructions include

• the lexically visible variables in the macro environment
• fbound symbols
• bound symbols
• overall directives to influence code generation
• directives to influence the style of the generated code (functional vs. imperative)
• directives to influence the use of the loop macro (prefer vs. avoid)
• the source code of the file currently being compiled, if there is one

pseduo sets the LLM to use a low temperature for more predictable generation. It prints the “thinking” of the LLM.

Lisp is a big win here. Since Lisp's macro system operates at the level of s-expressions, it has more contextual information available to it than a macro system that is just text expansion. The s-expression representation means that we don't need to interface with the language's parser or compiler to operate on the syntax tree of the code. Adding pseudo to a language like Java would be a much more significant undertaking.

pseudo has the usual LLM caveats:

• The LLM is slow.
• The LLM can be expensive.
• The LLM can produce unpredictable and unwanted code.
• The LLM can produce incorrect code; the more precise you are in your pseudocode, the more likely you are to get the results you want.
• You would be absolutely mad to use this in production.

pseudo has one dependency on SBCL which is a function to extract the lexically visible variables from the macro environment. If you port it to another Common Lisp, you'll want to provide an equivalent function.

pseudo was developed using Google's Gemini as the back end, but there's no reason it couldn't be adapted to use other LLMs. To try it out, you'll need the gemini library, available at https://github.com/jrm-code-project/gemini, and a Google API key.

Download pseudo from https://github.com/jrm-code-project/pseudo.

You'll also need these dependencies.

• alexandria — available from Quicklisp
• cl-json — available from Quicklisp
• dexador — available from Quicklisp
• fold — https://github.com/jrm-code-project/fold
• function — https://github.com/jrm-code-project/function
• named-let — https://github.com/jrm-code-project/named-let
• uiop — available from Quicklisp

If you try it, let me know how it goes.

Does CONS take its arguments in the wrong order?

Object-oriented languages often come with a “collections” library that provides a variety of data structures for storing collections of objects. Methods on collections usually pass the collection as the first argument for two reasons: (1) the collection is the primary object being operated on, and (2) in many languages, method dispatch only works on the first argument.

In Lisp, however, lists are a collection type that is derived from a more primitive data type, the cons cell. Lists are not fully abstracted from cons cells and many list operations are actually defined as operations on cons cells. Rather than the list argument always coming first, there is little rhyme or reason to the order of arguments in list operations. This becomes evident when you try to use higher-order operations on lists.

cons constructs a cons cell, with two fields, a car and a cdr. The car is traditionally written to the left of the cdr, and cons takes the car as the first argument.

In Lisp, there is no special constructor for lists. The user directly constructs the underlying cons cell and simply “declares in his head” that the result is a list. Hence when we are extending a collection with an item, the collection is the second argument to cons rather than the first. In a “modern” curly-brace, object-oriented language, we would extend mylist by writing mylist.cons(item)

Here’s where it makes a difference:

The fold-left function iterates down a list and calls a combining function on each element of the list. The first argument to the combining function is the accumulated answer, the second is the element being accumulated. If we want to accumulate into a list, the accumulated list is passed first and the new item is passed second. This means that cons is not suitable as the combining function in fold-left because the arguments come in the wrong order:

(defun bad-reverse (list)
  (fold-left #’cons ’() list)) ;; does not reverse a list

(defun xcons (cdr car)  ;; takes original list first
  (cons car cdr))

(defun reverse (list)
  (fold-left #’xcons ’() list)) ;; correcty reverses a list

Many list operations, remove and adjoin for example, take their arguments in an inconvenient order for fold-left.

Monkeys vs. Shakespeare

Google's golang was designed for mediocre programmers that aren't “capable of understanding a brilliant language”. It omits features that are hard to understand or hard to use, like conditional expressions, macros, exceptions, and object systems.

Lisp, on the other hand, was originally designed for smart programmers in order to research artificial intelligence. It contains language constructs like conditional expressions, a powerful macro system, a highly customizable error handling system, and a sophisticated object system.

A million monkeys typing on a million keyboards will eventually produce the works of Shakespeare. Lisp is a language for Shakespeares, while golang is a language for monkeys.

What is the fundamental problem we are solving? If the problem is simply an insufficient amount of software, then we need to write as much software as possible as rapidly as possible. Hire more monkeys. If the problem is gainfully employing all the monkeys quickly, give them crude tools that are easy to use. But if the problem is lack of quality software, then we need the tools to write the best software possible. Hire more Shakespeares and give them powerful tools.

Hiring monkeys is easier and cheaper than hiring Shakespeares. So why not just keep hiring monkeys until you have a Shakespeare equivalent? Experience shows how well this works. Just think of all the projects that were brought in on time and under budget when they doubled the number of monkeys. Just think of any project that was brought in on time and under budget when they doubled the number of monkeys. Surely there must be one?

Embrace the Suck

The key point here is our programmers are Googlers, they’re not researchers. They’re typically fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt.
— Rob Pike

How sad. Google used to hire top-notch programmers. Now it appears that they have hired a bunch of mediocre programmers who can't even learn how to properly use exceptions or ternary conditionals. Programmers that need “training wheels” on their C.

And how insulting to Googlers to be told that they are not capable of understanding a brilliant language. To be seen as merely a fungible resource to be “used” to build software. I'm sure some of them are capable of understanding a brilliant language. I'm sure that some are capable of learning how to use Haskell or OCaml or Clojure (or F# or Rust or Erlang or Scala) whatever language is best for the task.

Does success come to those that strive for excellence or those that embrace mediocrity?

Roll Your Own Syntax

Unlike most languages, Lisp represents its programs as data structures. A Lisp program is a set of nested lists. We can look at a Lisp program as a tree, with each nested list as a node in the tree. The first element of each list indicates the kind of node it is. For instance, a sublist beginning with LET binds local variables, a sublist beginning with IF is a conditional, and so on.

In most languages, it difficult or impossible to add new node types to the syntax tree. The syntax is wired into the language parser and if you even can add new syntax, you have to carefully modify the parser to recognize it. In Lisp, adding new node types is quite easy: you just mention them.

To give an example, suppose you wanted to add a new node to the syntax tree called COMMENT, which would have a string and a subexpression as components. You'd use it like this:

(comment "Avoid fencepost error" (+ x 1))

Here's how you could define the semantics of a COMMENT node in Lisp:

(defmacro comment (string expr)
  expr)

That's it. You can now insert arbitrary COMMENT nodes into your Lisp programs.

Compare that to what you would have to do in a language like Java to add a new kind of node to the syntax tree. You'd have to modify the parser, the lexer, the AST classes, and probably a bunch of other stuff. It's non trivial.

For a more complex example, consider adding transactions to a language. In a language like Java, you'd have to modify the parser to recognize the new syntax, and then you'd have to modify the compiler to generate the correct code. In Lisp, you can just define a new node type:

(defmacro with-transaction (body)
  <complex macro elided>)

And then use it like this:

(with-transaction
  (do-something)
  (do-something-else))

Now obviously you should put some thought into doing this. Adding dozens of random new node types to the language would be a bad idea: readers of the code wouldn't be expecting them. But in some cases, a new node type can be just what is called for to abstract out complexity or boilerplate. Lisp gives you that option.

If I Were in Charge

If I were in charge of Python development, here are a few things I would do:

• Add (optional) tail recursion. This would make it easier to write pure functional code. It would also make it possible to effectively program in continuation passing style. Making tail recursion optional should placate those that feel that stack traces are important for debugging.
• Add macros. I am thinking of Lisp-like macros that do code transformation, not C-like macros that simply do token substitution. A good macro system would allow advanced users to create new syntactic forms for the language and provide a way to abstract boilerplate.
• Allow a way to use statements inside expressions, or beef up the expression syntax to have exception expressions, loop expressions, etc. This, too, would make it easier to write pure functional code.
• Optional end-of-block markers. These would allow you to automatically fix indentation errors and recover indentation when it is lost.
• Use true lexical scoping. Changing this might break legacy code that depends on the current scoping quirks, though.
• Use modern interpretation techniques to get the performance up to a more reasonable level. Performance doesn't matter that much, but Python is notably slow.
• Get rid of the global interpreter lock so that multithreading works better. Probably easier said than done.

I don't believe any of these necessarily involve fundamental changes to the language. They'd just make the language more flexible, though I'm sure many people would disagree with me.

But, perhaps for the best, they're not going to put me in charge.

Why I Want Tail Recursion

The reason I want tail recursion is not to write loops (I can do that with a while loop), but to write in continuation passing style if I need to. Continuation passing style allows you to implement any control flow pattern you can imagine, not just the ones intrinsic to the language. You don’t want to use it all the time, but it’s a valuable fallback when you need some ad hoc advanced control flow. Without tail recursion, any non-trivial use of continuation passing style risks blowing the stack.

Iteration is just the special case of linear recursion that doesn’t accumulate state. 99 percent of the time, you know beforehand that you are looping and can use a looping construct, but sometimes you have the general case where whether you loop or not depends on the data at runtime. If you have tail recursion, you just write the code recursively and the tail recursion mechanism will turn it into a loop if it notices that you aren’t accumulating state.

If your language has lambda and tail recursion, it can implement any other control flow that might have been overlooked by the language designer. If it doesn’t, you're limited to the control flow the language designer bothered to implement.

Statements and Expressions

In some languages, like Lisp and OCaml, every language construct is an expression that returns a value. Other languages, like Java or Python, have two kinds of language constructs: expressions, which combine compositionally and which have return values, and statements, which combine sequentially and which have no return values and thus must operate by side effect. Having statements in your language needlessly makes things more complicated, but language designers seem to want to go much further and add complexity that just seems capricious.

You cannot usually use a statement in a context where an expression is expected because there is no return value. You can use an expression where a statement is expected by simply discarding the return value. This means there are two kinds of contexts. A sane designer would provide a way to switch between statement and expression contexts, but language designers typically omit these.

Language constructs, such as binding or iteration, must be provided as statements or expressions or both. Language designers seem to randomly decide which constructs are statements and which are expressions based on whims and ease of compiler implementation. If you need to use a construct, but aren’t in the right kind of context, you need to switch contexts, but without a way to do this, you may have to rewrite code. For example, if you have a subexpression that could raise an exception that you want to handle, you’ll have to rewrite the containing expression as a series of statements.

A sane language designer would use the same syntax for the same construct in both expression and statement form, but typically the construct will have a very different syntax. Consider sequential statements in C. They are terminated by semicolons. But sequential expressions are separated by commas. Conditional statements use if/else, but conditional expressions use ?:. When refactoring, you cannot simply move code between contexts, you have to change the syntax as well.

Writing a function adds a new expression to the language. But function bodies aren’t expressions, they are statements. This automatically destroys referential transparency because you cannot substitute the function body (statements) at the call site (expression context).

try/catch is a nightmare. Usually you only get try/catch as a statement, not an expression, so you cannot use exception handling in a subexpression. You cannot get a value out of a try/catch without a side effect. Throw, on the other hand, throws a value, so it could throw to an expression context, except that catch is a statement.

Having two kinds of language constructs and two different contexts in which you can use some of them but not others, and different syntaxes depending on the context just makes it that much more difficult to write programs. You have to keep track of which context is current and which syntax to use and constantly switch back and forth as you write a program. It would be easy for a compiler to introduce the necessary temporaries and rewrite the control flow so that you could use all language constructs in either context, but language designers don’t bother and leave it up to the programmer to do it manually.

And all this mess can be avoided by simply making everything be an expression that returns a value.

Off-sides Penalty

Many years ago I was under the delusion that if Lisp were more “normal looking” it would be adopted more readily. I thought that maybe inferring the block structure from the indentation (the “off-sides rule”) would make Lisp easier to read. It does, sort of. It seems to make smaller functions easier to read, but it seems to make it harder to read large functions — it's too easy to forget how far you are indented if there is a lot of vertical distance.

I was feeling pretty good about this idea until I tried to write a macro. A macro’s implementation function has block structure, but so does the macro’s replacement text. It becomes ambiguous whether the indentation is indicating block boundaries in the macro body or in it’s expansion.

A decent macro needs a templating system. Lisp has backquote (aka quasiquote). But notice that unquoting comes in both a splicing and non-splicing form. A macro that used the off-sides rule would need templating that also had indenting and non-indenting unquoting forms. Trying to figure out the right combination of unquoting would be a nightmare.

The off-sides rule doesn’t work for macros that have non-standard indentation. Consider if you wanted to write a macro similar to unwind-protect or try…finally. Or if you want to have a macro that expands into just the finally clause.

It became clear to me that there were going to be no simple rules. It would be hard to design, hard to understand, and hard to use. Even if you find parenthesis annoying, they are relatively simple to understand and simple to use, even in complicated situations. This isn’t to say that you couldn’t cobble together a macro system that used the off-sides rule, it would just be much more complicated and klunkier than Lisp’s.

The Garden Path

Follow me along this garden path (based on true events).

We have a nifty program and we want it to be flexible, so it has a config file. We make up some sort of syntax that indicates key/value pairs. Maybe we’re hipsters and use YAML. Life is good.

But we find that we to configure something dynamically, say based on the value of an environment variable. So we add some escape syntax to the config file to indicate that a value is a variable rather than a literal. But sometimes the string needs a little work done to it, so we add some string manipulation features to the escape syntax.

And when we deploy the program, we find that we’ve want to conditionalize part of the configuration based on the deployment, so we add a conditional syntax to our config language. But conditionals are predicated on boolean values, so we add booleans to our config syntax. Or maybe we make strings do double duty. Of course we need the basic boolean operators, too.

But there’s a lot of duplication across our configurations, so we add the ability to indirectly refer to other config files. That helps to some extent, but there’s a lot of stuff that is almost duplicated, except for a little variation. So we add a way to make a configuration template. Templating needs variables and quoting, so we invent a syntax for those as well.

We’re building a computer language by accident, and without a clear plan it is going to go poorly. Are there data types (aside from strings)? Is there a coherent type system? Are the variables lexically scoped? Is it call-by-name or call-by-value? Is it recursive? Does it have first class (or even second class) procedures? Did we get nested escaping right? How about quoted nested escaping? And good grief our config language is in YAML!

If we had some forethought, we would have realized that we were designing a language and we would have put the effort into making it a good one. If we’re lazy, we’d just pick an existing good language. Like Lisp.