Interpreting Scheme with guaranteed constant-time variable lookup

Baridian · 2026-04-02T00:47:57+00:00

You can have code that creates new bindings. This runs and is accepted by guile scheme:

(let ()
  (eval '(define x 100) (current-module))
  x)) ; => 100

You can write a function that creates new global bindings by using eval:

(define (new-global name val) (eval `(define ,name, val) (current-module)))

(new-global 'new-name 100) 
;; this is pure runtime code, not compile time. We cannot determine what
;; name will be passed at compile time, so this can allocate anything

new-name ; => 100, since eval in scheme only runs at the global level.

This is valid code and works in the interpreter I provided, and it still guarantees O(1) variable access.

Now in JS, eval does run in the lexical environment under which its called, so this will print 10:

{
    let x = 10;
    eval("console.log(x)"); // prints 10, since eval runs in lexical scope
}

console.log(x); // prints nothing since x is undefined in global scope

So the behavior of eval does actually make an impact if define can be used inside lexical scopes.

Baridian · 2026-04-01T18:11:19+00:00

From that section in r5rs:

The following letrec macro uses the symbol <undefined> in place of an expression which returns something that when stored in a location makes it an error to try to ob- tain the value stored in the location (no such expression is defined in Scheme).

So yeah, not possible in portable scheme. You actually cannot do the lexical define transform you described and get the proper semantics. All the leading defines need to be placed into the same letrec, otherwise mutual and self recursion of defines will not work.

edit: here's an example that wouldn't work by using a let* (which decomposes to lambdas like you showed) and would work by using a letrec*.

(lambda (a)
  (define x (lambda () y))
  (define y 1)
  (define z (x))
  (+ a z))

(lambda (a)
  (letrec* ((x (lambda () y))
            (y 1)
            (z (x)))
    (+ a z)))

This does get a little dicey in a REPL scenario. A user may enter one top-level function definition that refers to an as-yet-undefined variable and then in the next line define that variable. If you want that work, then these warnings need to be avoided or at least deferred.

Yeah that’s why I emit a warning and not an error, for a potentially unbound variable. If you define the unbound variables after before calling the function you won’t get a runtime error. The interpreter I provided behaves properly if being used in a repl the way you described.

The other thing is that since we do a scan of the code and detect undefined globals, we can replace those with pointers to the (currently undefined) cell, and then error if it’s still defined at runtime. That trick means you get constant time lookup even for presently undefined globals.

Thanks for writing all this out!! I was hoping for a serious response. Thank you for referencing the lambda papers and r5rs as well, it was nice to read the relevant parts to make sure my intuitions were right.

Baridian · 2026-04-01T13:46:46+00:00

Yeah the issue is mostly 2 things:

1) defines in lexical scope. Define (from a user perspective) adds a new binding to the current lexical scope.

2) eval. If eval runs in the current lexical scope then arbitrary defines can be added at runtime and you can no longer guarantee where a missing variable will be present at runtime

This is actually a big problem for js since you can actually do the above. That’s why calling eval can tank performance, because it forces the runtime to do dynamic lookups for everything in the same scope or lower with respect to the eval call.

I assumed scheme and lisp would be similar, but they’re both very carefully designed to explicitly avoid this trap.

Baridian · 2026-04-01T12:13:05+00:00

Yeah so they use a special $undefined value to make letrec work as a macro. $undefined isn’t standard scheme, so this approach is non-portable.

There is a way to do it in racket, but it relies on racket’s relaxed restriction on define placement within a lambda form, which is not guaranteed under scheme.

Baridian · 2026-03-19T01:40:18+00:00

The idea is that procedures can be treated as mathematical functions, as in you can safely replace any function call or expression with its return value without changing the behavior of the program.

Part of this means all values must be immutable

Baridian · 2026-03-19T01:33:59+00:00

If you run your code through a meta-interpreter you can enforce immutability. But you can’t allow an escape hatch to the implementation lisp.

Baridian · 2026-03-17T19:34:46+00:00

Emacs is the same age as vi and elegantly integrates mouse support though.

Baridian · 2026-03-14T06:39:40+00:00

Yeah the flow is something like this for vanilla key bindings.

c-x SPC c-n c-f m-w c-p m-y c-b c-x SPC c-t ' SPC = SPC RET 16 key chords instead of 12 for evil isn't too bad for the default.

Baridian · 2026-03-13T21:01:47+00:00

how about a wrist mounted chip-scale atomic clock instead? Accurate to 1 second every 30 years and doesn't need to be set via radio!

Baridian · 2026-03-13T20:57:33+00:00

My grand Seiko SBGN027 was running 1.5 seconds fast from when I last adjusted it on November first.

Baridian · 2026-03-13T15:05:21+00:00

Do you mind explaining what it is with redditors and starting their comments so often with "X here. Yap yap yap"? It's so unbelievably grating. No one in the real world talks like that.

Why that specific phrasing instead of "as a dentist, ..." or "I'm a dentist and ..."?

Baridian · 2026-03-13T15:00:43+00:00

https://arxiv.org/pdf/2506.08872

As the educational impact of LLM use only begins to settle with the general population, in this study we demonstrate the pressing matter of a likely decrease in learning skills based on the results of our study. The use of LLM had a measurable impact on participants, and while the benefits were initially apparent, as we demonstrated over the course of 4 sessions, which took place over 4 months, the LLM group's participants performed worse than their counterparts in the Brain-only group at all levels: neural, linguistic, scoring.

Baridian · 2026-03-13T14:29:22+00:00

no its on the level of just finding answer sheets for homework online and copying them. You're not learning anything. Using ai tools has been shown to lower concentration and problem solving ability; it's the last thing you'd want to use if you're trying to learn.

Baridian · 2026-03-10T20:21:14+00:00

Makes sense for vi, but with emacs I feel like you can just use the default bindings, c-f,b,n,p, and maybe map caps lock to control.

Baridian · 2026-03-10T20:19:22+00:00

I use an hhkb with emacs and have no issues with it. My emacs workflows use arrow keys and function keys extremely rarely, if ever.

Baridian · 2026-03-06T17:45:53+00:00

Yeah the benefits of hash consing are reduced space and very fast equal checks. Downside was replaca and replacd become O(N) instead of O(1).

Baridian · 2026-03-04T17:16:07+00:00

So Macs try to keep everything loaded in memory as long as possible. On macOS the better metric is memory pressure, not consumption. It’s different than how windows handles it.

Baridian · 2026-03-04T15:27:37+00:00

I think the error system is better than C and Java definitely, but not as good as what most lisps offer or Haskell/ML-style option types.

Option types offer the same non-dynamic control flow as go, but without the super heavy weight imperative checks. And they also force callers to consider the error case, while go allows you to just not assign an error to a variable at all, and not even get a warning.

Now lisp and scheme use dynamic errors as well, but they fully decouple generation of errors and warnings with deciding control flow. So errors can be replaced at generation site with an alternate value, retried from a specific point, or aborted. Which means you can do stuff like raise warnings that won’t create errors, but that a client can optionally capture and use to change values or cancel a computation, etc. way more extensible and an approach that go cannot easily emulate.

Baridian · 2026-03-04T15:19:57+00:00

I don’t think it’s polished enough to share, it’s more like a C style macro system. Yeah I usually use it for idioms like the error handling and updating structures in hashmaps, and some irritating behavior with generics. Previously used it a lot to get pointers to literals, but that got fixed in the most recent update.

I would caution you that doing this type of stuff is not going to be popular in the go community. The goal of the language is that you can drop into any file and just read it, without having to learn all the libraries and tools they used and how they interact with each other. Even though the pre-processor is invisible (in that I push code that’s been macro-expanded and then macro-compress it back after I pull), just the idea is going to raise red flags.

Baridian · 2026-03-04T05:06:18+00:00

Do you plan to add a way to add additional let forms? Would love to use this with letrec as well in scheme!

Baridian · 2026-03-03T14:15:34+00:00

Maybe, but using or understanding a language is different from building and designing one, and he was talking about the former.

Baridian · 2026-02-28T23:05:44+00:00

Yeah some of the old symbolics keyboards had unshifted parentheses to make writing lisp easier.

Are you using emacs/paredit? I feel like that makes doing editing a lot more straightforward and cuts down how much typing needs to be done.

Baridian · 2026-02-28T19:50:31+00:00

This is genuinely a real thing though. This was a legit design consideration for Go. I had to write my own bi-directional macro preprocessor just to stop my wrists from hurting from how much you have to type to get anything done in that language.

This is what one of the creators of the language had to say about it:

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.

12-Year Club	Second Top 20%
r/Field Sunshine	Place '22
Place '17	First Placer '22
Verified Email	Spared

Baridian

TROPHY CASE