mccApr 9

#BabelOfCode 2024
Week 6
Language: Nameless experimental LISP

Confidence level: High

PREV WEEK: https://mastodon.social/@mcc/113975448813565537
NEXT WEEK: https://mastodon.social/@mcc/114433465965880352
RULES: https://mastodon.social/@mcc/113676228091546556

Okay… here things get weird!

My project to, gradually over the course of 2025, do each puzzle from Advent of Code 2024 in a different programming language I've never used before, has stalled out for exactly two months now as I've instead been creating…

…the programming language I'm going to use this week!

Show threadmccApr 9

For "Week 5" I did TCL, and it kind of set my brain on fire with "wait… you can just DO that?".

In TCL, strings are anonymous functions and vice versa. In my old Emily language, "if" and "while" blocks were implemented by passing in lambdas; but in TCL you do the same thing by *passing in a string containing {the code to execute}*. I started trying to imagine what "hygienic" TCL would be; if TCL is a C macro, I want an ML or Rust macro. I tried to imagine something closer to LISP than TCL.

epwJun 15
Show threadmcc

This is what I came up with; I think of it as "0-lisp". In LISP a "2-LISP" is a LISP where functions and variables live in different namespaces, and in a "1-LISP" they live in one namespace. Projecting backward, in my 0-LISP, the distinction itself disappears totally; functions are lists and *any list can be executed*. I wanted to know what this changed. Here's what I found:

It helps very little, and makes certain important things a huge pain. Oops! Still, it was very educational to learn this.

Apr 9 at 4:11pmWeb
Show threadmccApr 9

Anyway, now I have a LISP interpreter written in Rust.

https://github.com/mcclure/lisp0-experiment/tree/2025-04-07

It's a very minimal "MVP"; the language currently lacks:

- Variable scopes
- Loops
- Conditionals
- Floating point numbers
- Errors lack backtraces or line numbers (and cannot be recovered from)

It has

- One global scope
- Ints, strings, arrays and hashtables
- Tail recursion
- File I/O

But math and recursion means it's Turing complete. Which means it's sufficient to use it for a AOC problem!

GitHub - mcclure/lisp0-experiment at 2025-04-07

???? don't look at this. Contribute to mcclure/lisp0-experiment development by creating an account on GitHub.

GitHub
Show threadmccApr 9

Now, since *I'm* the one writing this LISP, I do get to make some changes. The main thing I wanted to change, as it's the #1 thing that infuriates me writing LISP, is parentheses. This "LISP" has a syntax where each line (as separated by newlines or commas) implicitly has () around it. Meanwhile, {} and [] are shorthand, for

{x,y,z} => '((x)(y)(z))

[x,y,z] => (make-array [(x),(y),(z)])

In other words {} is functions (quoted lists) and [] is array literals.

Is this still a LISP? I don't care!

Show threadmccApr 9

Before I can start, I need to make some utilities. By "utilities" I mean "if" and "while" statements, which again, this language currently lacks. MVP, remember. Implementing these in userland is possible! It's *ugly*, though. For `if`, I simulate branching by putting the two possible outcomes (functions) into an array, casting the condition to a bool and then the bool to an int, and using that as an index to the array.

"while" is even more nightmarish. I don't… understand the use of make-quote.

Show threadmccApr 9

Like, I wrote the code, but I don't understand it. I initially wrote it with all the `make-quote`s being `return`s, and that didn't work, so I experimentally replaced them with make-quotes and it did work. I need to reread the interpreter code to really understand why that was required.

If even the designer can't understand the model here, the model is probably too complicated for anyone ELSE to write self-modifying code either! That's a sign of a problem, or better abstractions needed.

Show threadmccApr 9

Anyway, I like testing things before I use them, so after implementing my "if" and "while" I decide to write a simple Fizzbuzz program. This causes me to immediately realize—

I FORGOT TO IMPLEMENT > AND <

I just forgot!! Fortunately I *did* include bit arithmetic ops, so I implement <, >, <=, >= in userland as well, by testing bit (1<<63) as a proxy for 2's compliment negative. This is actually a little worrisome. I'm not sure if this code truly "works" or if I'm just leveraging UB in Rust.

Show threadmccApr 9

So after a prelude containing reimplementations of if, while, int comparisons, and "noop", I am now ready to implement "fizzbuzz". I do not need an implementation of "fizzbuzz", I'm supposed to be doing AOC2024 day 6. But at least I know my helper routines work!

Fizzbuzz source:

https://github.com/mcclure/aoc2024/blob/6d12e9cf65158b5f511da8545d263f4ed1dcad99/06-01-guard/src/test-fizzbuzz.l0

I was GOING to implement a `proc` that modified function code in-place to add local variable support, but debugging `while` took a lot out of me, so I think I will not do that for this project.

aoc2024/06-01-guard/src/test-fizzbuzz.l0 at 6d12e9cf65158b5f511da8545d263f4ed1dcad99 · mcclure/aoc2024

Advent of Code 2024 challenge (laid-back/"babel" version) - mcclure/aoc2024

GitHub
Show threadmccApr 10

Got part 1 of the puzzle working this morning!

https://github.com/mcclure/aoc2024/blob/2656c75da28669ad11568fae6f5f3a9c24a311a6/06-01-guard/src/puzzle.l0

App code "proper" starts around line 124 (43-123 are "library code" I didn't post above; I implemented "for" and "switch", and a very small vector math library.)

Writing this program was not at all hard (other than the library code… `for` was painful), but nor was it particularly *pleasant*; it didn't feel fluid. That might speak poorly for my minimal LISP, and the question of whether I use it again after this project.

aoc2024/06-01-guard/src/puzzle.l0 at 2656c75da28669ad11568fae6f5f3a9c24a311a6 · mcclure/aoc2024

Advent of Code 2024 challenge (laid-back/"babel" version) - mcclure/aoc2024

GitHub
Show threadmccApr 10
In particular, what worries me is the "hard part" of this code turned out to be the higher order functions (if, while, for, foreach, proc). This LISP is contrived compared to other LISPs, with no special "forms", and no sugar other than the {} and [] which are supposed to be swiss army knives you can construct anything else you need from. I did it this way to make self-modifying / generated-at-runtime code easy & fluid. *But that's exactly what turned out to be hardest*. And *that's* a bad sign!
Show threadmccApr 10

Making this little LISP was *in part* a "can I do this?" for the Babel project. But there's another thing, which is I want a general purpose assembler. I've recently started wanting to target some unusual/retro systems (NES, N64, Saturn) and I forsee frustration with having no common toolchain among these projects for any language I like, nor a common macroassembler syntax I can take with me across different ISAs.

So I was hoping my tiny LISP could be reworked into a macroassembler.

Show threadmccApr 10

I've realized something:

mov rax, r10
add r8, 1
jmp _main_loop_reset

Assembly looks a lot like LISP once you remove the parentheses! So I wanted to design an ASM syntax that exists as a data structure within a LISP, and write code as a LISP program that generates that data structure. In other words make a DSL similar to "Amaranth" or my old "No Compiler" blog posts https://msm.runhello.com/p/category/plt/no-compiler . I may be just confusing you at this point— I'm not sure I can describe this idea clearly in 500 chars.

Run Hello » No Compiler

Show threadmccApr 10

Anyway, before I move on to Week 6 Part 2, I'm considering going back and making changes to the interpreter. I told myself whatever I had written as of 04-07, I'd stick with it— I could fix bugs but not language design issues. Well, I hit some stuff straddling the line:

- lack of "fail" (exit with error message) is m i s e r a b l e, the second half of my program is all `if (!abort)` every few lines
- "the return problem"

…Oh geez. i can't describe the return problem in 500 characters either.

Show threadmccApr 10

The point of my "no parentheses"/l0 syntax was each independent line has an implicit () around it— each line is a function call. This creates a problem: How do you form an expression that returns a value without executing code? I foresaw this during design and added a function named "return" that takes one argument and returns it. So a fn def looks like

{
set 'result
return result
}

Kludgy but readable. *But I forgot about lists!* So all lists turn out an ugly traffic jam of `return`s:

Show threadmccApr 10
So the obvious fix for *this* is to have the interpreter simply treat any single-symbol line as a value, not a function call. But NOW I have to introduce a *separate* syntax for no-argument function calls! (emily had a higher order function named "do" for this), and I risk sneaky bugs if I ever forget to use that syntax on some given line. Gradually I'm losing the elegant simplicity that inspired me to base this language on the idea of LISPness rather than resurrecting Emily or something. Messy.
Show threadmccApr 10
Anyway, the GOOD news from part 1 is that I found a bug in my garbage collector! That's not a joke or sarcasm, I am legitimately excited I'm now exercising my GC enough that it's possible to find bugs in it. If you run my part 1 solution in verbose-debug mode it crashes at some random point partway through execution, which I haven't fully investigated but to me screams "GC bug". So now I get to do more work on my GC (my favorite part of language implementation).
Show threadmccApr 11

So that flows well into this next post…
I tried out "part 2" last night. Part 2 involves rerunning the simulation from part 1, but repeatedly stopping it and backing it up to test untaken paths.

That GC bug I was excited about? Yeah, it turns out my part 2 solution stresses my GC enough I get the GC bug *just running the basic program*. Every time I run, I get a random failure in a random place after memory corrupts (usually by randomly scrambing which object which pointer points to).

"LOL"

Show threadmccApr 11

I mentioned before I was looking forward to fixing this GC bug, but that doesn't mean I want to fix it *now*.

Guessing the bug happens after a random number of GCs, I tried increasing the GC space size (by default it's 56 MB, and doubles when a collection ends with the space more than half full— which in this program never happens), to increase the time between GCs. Oddly, this *also* caused the program to survive for more GCs without crashing. But I couldn't find a size it didn't crash.

Show threadmccApr 12

So yesterday got… a little silly.

Let me explain the puzzle.

The idea is a guard (▲) is walking a room with various obstructions (#) [📎 1]. They turn right every time they hit an obstruction, and continue until they reach the room border and "escape" [📎 2]. My goal in part two (SPOILERS!!!!) is to find all the places I can insert a new obstruction (X) which would cause the guard to enter a "loop" and prevent them from escaping [📎 3].

Interestingly, this problem is "embarrassingly parallel".

Show threadmccApr 12
The "walk" must be done linearly, but in a setup where you can multithread, you could split up the search space for wall insertion into chunks and have each chunk be tested separately. My handmade language can't multithread; it can't even single-thread, insofar as it crashes after a certain amount of time. But the solution is the same! I simply ran the program 14 times, by hand, each time checking only a few hundred of the 5,950 possible wall insertion positions, bailing out before it crashes.
Show threadmccApr 12
Add together the outputs from the 14 runs, and I have an answer! My answer's wrong. It's too high. I instantly realize why: I find wall candidate positions by looking "one step ahead" of the guard at each of the 5,950 steps. This creates a potential for double counting if the guard twice approaches the same square from different directions. Good thing I thought ahead and added proper file I/O! I rewrite the script to output every wall location to a file as it goes and rerun it (again in chunks)…
Show threadmccApr 12

…then deduplicate the results using, of course, a small script written in my experimental LISP:

https://github.com/mcclure/aoc2024/blob/stable/06-02-guard/src/dedup.l0

(I could have just used UNIX uniq, but that's! Not! The point! Of this! Exercise!)

It's still too high!!! And now I'm in trouble. After double checking I conclude the problem isn't my weird multisegmented run process; there's either a very fundamental bug or I've misread the prompt.

My LISP isn't unpleasant to write, but it's not well instrumented for intricate debugging :(

aoc2024/06-02-guard/src/dedup.l0 at stable · mcclure/aoc2024

Advent of Code 2024 challenge (laid-back/"babel" version) - mcclure/aoc2024

GitHub
Show threadChris LApr 12
@mcc that’s some fine application of software engineering solutions to programming problems.
Show threadнабApr 12
@mcc arriving at unix de novo? you love too see it
Show threadRiley S. FaelanApr 10
@mcc Some of these issues were wrestled with in the Scheme I-forms: https://srfi.schemers.org/srfi-49/srfi-49.html (but also see https://srfi.schemers.org/srfi-119/srfi-119.html).
SRFI 49: Indentation-sensitive syntax

Show threadChris [list of emoji]Apr 10

@mcc

Did I already mention Honeylisp? It does exactly that, but for the Apple 2.

On the off chance that I'd planned to mention it but forgot, here it is:

https://git.information-superhighway.net/SpindleyQ/honeylisp

honeylisp

Honeylisp is a programming environment for livecoding the Apple II, written in Fennel and based on the lite code editor. It also currently contains the work-in-progress code for an Apple II port of Neut Tower, as the development of this game is driving the development of the environment.

git dot information dash superhighway dot net
Show threadmccApr 10
@suetanvil Oh! It's SpindleyQ! :O
Show threadChris [list of emoji]Apr 10

@mcc

Yup. (I didn't want to @ him in case the noise was unwelcome.)

Show threadJPApr 10
@suetanvil @mcc A+ name
Show threadtechnomancyApr 19
@jplebreton @suetanvil @mcc @SpindleyQ oh wow I have known about HoneyLisp for like three years and I just got the name
Show threadmccApr 19
@technomancy @jplebreton @suetanvil @SpindleyQ I do not get the name so I guess I need to think about it for three years
Show threadJPApr 19
@mcc @technomancy @suetanvil @SpindleyQ dunno for sure but it's a great pun on "honeycrisp", a pretty tasty apple varietal
Show threadSpindley Q FrogApr 19
@jplebreton @mcc @technomancy @suetanvil that is 100% where the name comes from, yes!
Show thread✧✦Catherine✦✧Apr 10

@mcc or Forth

(cc @meithecatte who wrote a very cool boot sector forth)

Show threadmccApr 10
@whitequark @meithecatte I'm still confused how you go about effectively compiling or typechecking Forth. I am hoping to try out some modern Forths later in this "Babel" project
Show threadbobApr 10
@mcc you know about GOAL/GOOL, right?
Show threadmccApr 10
@bob I do not, what is it?
Show threadbobApr 10
@mcc https://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp it's a macro-assembler embedding in common lisp developed at naughty dog. they wrote the jak and daxter games in it
Game Oriented Assembly Lisp - Wikipedia

Show threadjcoglanApr 10
@mcc does "no special forms" imply it has lazy evaluation?
Show threadjcoglanApr 10
@mcc (I once wrote a lisp that was optionally lazy and another that had optional continuations which would make it switch to a completely different evaluator depending on context)
Show threadmccApr 10
@jcoglan That second thing sounds like something I'm considering, but rather than compiler modes I was going to implement it as different types of "eval". The goal here was to try to explore the TCL idea of "no anonymous functions, just eval" in a syntactically hygienic context. I imagined a base-level symbolic eval, and then a "JIT me" eval that is written in the base language and compiles a restricted, typed subset into target platform ASM at runtime…
Show threadmccApr 10
@jcoglan No, unless you count '( ) as lazy evaluation. The code is nested lists and it makes decisions about when to evaluate or not evaluate those lists.
Show threadphookyApr 9
@mcc I would love a lisp that has things like (a (b (c)³, so I don't go blind from trying to count parens. Or even something like (¹a (²b (³c)³)²)¹, although I suppose this is the kind of annotation an editor could do
Show threadmccApr 9

@phooky i've wondered about color-matching them. however, i have a better solution than your )^3, which I used in Emily: The colon

(print: + 2 3)

becomes

(print (+ 2 3))

I think this is similar to Haskell $ or ocaml |>, but it reads a lot more naturally.

Show threadKatApr 9

@phooky @mcc I strongly recommend enabling colour highlighting in your editor. Even vim has a lisp mode, which changes colour for each successively nested pair.

Counting parens is just tedious and error-prone; nobody has time for that.

Show threadaeriqueApr 9

@mcc Have you heard of Dylan?

http://en.wikipedia.org/wiki/Dylan_programming_language

Dylan (programming language) - Wikipedia

Show threadmccApr 9
@aerique Yeah! I've never used it but I've wondered about it for decades. It's on my list for this project and my current plan for the 0-lisp, if I keep with it, is to give it typeclasses/multimethods to make it more dylan-like (once I've written enough Dylan to see how it works ofc)
Show threadyuubiApr 9

@mcc any opinions on m-notation, which is definitely part of the lisp tradition, but has a but more texture than just identical parentheses everywhere? https://en.m.wikipedia.org/wiki/M-expression

i feel like some of that punctuation should have been whitespace, but that feeling probably comes at least in part from familiarity with the syntax that won (insofar as any lisp syntax won).

M-expression - Wikipedia

Show threadmccApr 9

@yuubi doesn't necessarily feel like an improvement to me.

I have done something similar in the past by treating ML syntax as a way of constructing s expressions tho.

Show threadaseApr 9
@mcc does it have function arguments? are the ”functions” named lists of instructions? i guess you could make functions out of that with a calling convention via globals and a global array for the stack…
Show threadmccApr 9
@annanannanse The closest thing to a function scope here is an "args" variable, which is different at each level of the stack (there's still only one global scope, but when a function completes, the interpreter restores the "args" variable to the value it had before the function was invoked). "args" contains the arguments supplied to the currently invoked function, and you have to unpack those arguments out into variables if you want to name them.
Show threadaseApr 9
@mcc ok! not as primitiva as i imagined :). unpack args would go into global vars?
Show threadmccApr 9
@annanannanse yes, there's an intent to have it also allow unpacking into a dictionary, but I haven't done that yet. Essentials only.