Rogue Project's Friendica Social Network

mcc

2 months ago • •

mcc
2 months ago • •

#BabelOfCode 2024
Week 6
Language: Nameless experimental LISP

Confidence level: High

PREV WEEK: mastodon.social/@mcc/113975448…
NEXT WEEK: mastodon.social/@mcc/114433465…
RULES: mastodon.social/@mcc/113676228…

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!

#babelofcode

This entry was edited (1 month ago)

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

in reply to mcc

наб

in reply to mcc • 2 months ago • •

holy hell they put strings in lambda calculus??

in reply to наб

mcc

in reply to наб • 2 months ago • •

@nabijaczleweli but no functions. just strings

@наб

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

# Example program -- LISP syntax

# Create a "function" from a quoted list:

(set 'four-plus-five
'( (set 'x 4)
(set 'y 5)
(print (+ x y))
)
)

# But the quoted list isn't special...
# We could construct it "by hand":

(set 'four-times-five (make-array))
(set 'temp-line (make-array))
(push temp-line "print")
(set 'temp-call (make-array))
(push temp-call "*")
(push temp-call 4)
(push temp-call 5)
(push temp-line temp-call)
(push four-times-five temp-line)

# Call our functions:
(four-plus-five) (print ln)
(four-times-five) (print ln)

$ ./target/release/lisp0 sample/demo.ls0
9
20

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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

github.com/mcclure/lisp0-exper…

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

in reply to mcc

ase

in reply to mcc • 2 months ago • •

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…

in reply to ase

mcc

in reply to ase • 2 months ago • •

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.

This entry was edited (2 months ago)

mcc reshared this.

in reply to mcc

ase

in reply to mcc • 2 months ago • •

ok! not as primitiva as i imagined 😀. unpack args would go into global vars?

in reply to ase

mcc

in reply to ase • 2 months ago • •

@annanannanse yes, there's an intent to have it also allow unpacking into a dictionary, but I haven't done that yet. Essentials only.

@ase

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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!

# Demonstrate significant-whitespace / "l0" syntax
set 'x 3
set 'y 7

set 'array [
+ y x
- y x
* y x
/ y x
% y x
]

set 'noop {return nil}

set 'iter {
set 'iter-array (get args 0)
set 'iter-idx (get args 1)
set 'iter-continue (has iter-array iter-idx) # Index exists?

# Two functions: Noop does nothing; anonymous fn recurses iter.
# Due to a language design oversight, to write [1,2] you must
# write [return 1, return 2]. ("return" is identity combinator)
set 'func-pair [
return noop,
return {
print "at idx: " iter-idx sp \
"value: " (get iter-array iter-idx) ln
iter iter-array (+ iter-idx 1)
},
]

(get func-pair (to-int iter-continue)) # Call function 0 or 1
}

$ ./target/release/lisp0 sample/demo2.l0
at idx: 0 value: 10
at idx: 1 value: 4
at idx: 2 value: 21
at idx: 3 value: 2
at idx: 4 value: 1

in reply to mcc

phooky

in reply to mcc • 2 months ago • •

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

in reply to phooky

mcc

in reply to phooky • 2 months ago • •

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.

This entry was edited (2 months ago)

in reply to mcc

aerique

in reply to mcc • 2 months ago • •

Have you heard of Dylan?

en.wikipedia.org/wiki/Dylan_pr…

multi-paradigm programming language with support for functional and object-oriented programming

^{Contributors to Wikimedia projects (Wikimedia Foundation, Inc.)}

in reply to aerique

mcc

in reply to aerique • 2 months ago • •

@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)

@aerique

in reply to mcc

yuubi

in reply to mcc • 2 months ago • •

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

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).

Proposed syntax for the Lisp language

^{Contributors to Wikimedia projects (Wikimedia Foundation, Inc.)}

in reply to yuubi

mcc

in reply to yuubi • 2 months ago • •

@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.

@yuubi

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

# Advent of Code 2025, day 6, part 1 -- if-while test

set 'noop {return nil}

# Usage: if conditional {case1} {case2}
set 'if {
inset args '(_if_cond _if_true _if_false) # Mass-assign sugar
set '_if_pair [return noop, return _if_false]
set '_if_pair [
get _if_pair (to-int (to-bool _if_false))
return _if_true
]
(get _if_pair (to-int (to-bool _if_cond))) # Extra () means execute
}

# Usage if {conditional} {case}
set 'while {
inset args '(_while_cond _while_true)
set '_while_pair [return noop]
push _while_pair [ # Construct fn as data so we don't have to think about
return [make-quote _while_true] # ..variable shadowing when recursing
return [return 'while, make-quote _while_cond, make-quote _while_true]
]
(get _while_pair (to-int (to-bool (_while_cond))))
}

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

# Ad-hoc userland implementation of comparison ops

set '<0 { != 0 (& 9223372036854775808 (get args 0)) }
set '< {
<0 (- (get args 0) (get args 1))
}
set '>= { ! (< (get args 0) (get args 1)) }
set '<= { # No, these variable names aren't great
inset args '(_<=_x _<=_y)
|| (= _<=_x _<=_y) (< _<=_x _<=_y)
}
set '> { ! (<= (get args 0) (get args 1)) }

print (< 4 5) sp (<= 4 5) sp (> 4 5) sp (>= 4 5) ln
print (< 9 2) sp (<= 9 2) sp (> 9 2) sp (>= 9 2) ln
print (< 7 7) sp (<= 7 7) sp (> 7 7) sp (>= 7 7) ln

$ ./lisp0/target/release/lisp0 src/test-lt-gt.l0
[true] [true] [nil] [nil]
[nil] [nil] [true] [true]
[nil] [true] [nil] [true]

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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:

github.com/mcclure/aoc2024/blo…

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.

# Fizzbuzz up to command line argument [default 10 if absent]
set 'at 0
set 'target (get args 0)

if target {
set 'target (to-int target) # ARGV is strings...
} {
set 'target 10 # No ARGV
}

set '=0 { = 0 (get args 0) }

while {< at target} {
set 'at (+ at 1)
set 'three (=0 (% at 3))
set 'five (=0 (% at 5))
print (if three {
if five {
return "Fizzbuzz"
} {
return "Fizz"
}
} {
if five {
return "Buzz"
} {
return at
}
}) sp
}
print ln

$ ./lisp0/target/release/lisp0 src/test-fizzbuzz.l0 -- 25
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 Fizzbuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz

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

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

^GitHub

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

Got part 1 of the puzzle working this morning!

github.com/mcclure/aoc2024/blo…

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.

A complex maze, ending with "Steps: 5051 Visited: 5409"

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

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

^GitHub

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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!

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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 msm.runhello.com/p/category/pl… . 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

^{msm.runhello.com}

in reply to mcc

Chris [list of emoji]

in reply to mcc • 2 months ago • •

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:

git.information-superhighway.n…

honeylisp

Honeylisp is a programming environment for livecoding the Apple II, written in Fennel and based on the lite code editor.

^{git dot information dash superhighway dot net}

mcc reshared this.

in reply to Chris [list of emoji]

mcc

in reply to Chris [list of emoji] • 2 months ago • •

@suetanvil Oh! It's SpindleyQ! 😮

@Chris [list of emoji]

in reply to mcc

Chris [list of emoji]

in reply to mcc • 2 months ago • •

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

in reply to Chris [list of emoji]

JP

in reply to Chris [list of emoji] • 2 months ago • •

@suetanvil A+ name

@Chris [list of emoji]

in reply to JP

technomancy

in reply to JP • 2 months ago • •

@SpindleyQ oh wow I have known about HoneyLisp for like three years and I just got the name

@Spindley Q Frog

in reply to technomancy

mcc

in reply to technomancy • 2 months ago • •

@technomancy @jplebreton @suetanvil @SpindleyQ I do not get the name so I guess I need to think about it for three years

@Spindley Q Frog @JP @Chris [list of emoji] @technomancy

in reply to mcc

JP

in reply to mcc • 2 months ago • •

spoiler: something the name might be a pun on

Sensitive content

@Spindley Q Frog @Chris [list of emoji] @technomancy

in reply to mcc

✧✦Catherine✦✧

in reply to mcc • 2 months ago • •

or Forth

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

@mei unleashed

in reply to ✧✦Catherine✦✧

mcc

in reply to ✧✦Catherine✦✧ • 2 months ago • •

@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

@✧✦Catherine✦✧ @mei unleashed

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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:

return [return ".", return {
return FREE
}]

return [return "#", return {
return WALL
}]

return [return ">", return {
guard-found RIGHT
return FREE
}]

in reply to mcc

Fish Id Wardrobe

in reply to mcc • 2 months ago • •

if a line is a syntactic unit – and since each line is executed I suppose it is – why not have the return keyword return *everything* on the rest of the line?

this is probably horrible to do, I suppose.

in reply to Fish Id Wardrobe

mcc

in reply to Fish Id Wardrobe • 2 months ago • •

@fishidwardrobe No multi-return in this language. if it returned everything on the line, it would have to return an array containing the remaining items on the line. Which in addition to violating some vague rule I have about return types not vary too much based on parameter types, that would make [return x y z] do something VERY SURPRISING.

@Fish Id Wardrobe

in reply to mcc

Fish Id Wardrobe

in reply to mcc • 2 months ago • •

bummer

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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).

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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"

Various runs of the program ending in errors like "Error: Tried to execute non-function: Quote" or "Error: Too few args to `&`" or "Error: Too few args to `||`"

This entry was edited (2 months ago)

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

Running with 56 MB of memory, the program survives for 8 GCs.

Running with 896 MB of memory, the program survives for 20 GCs.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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".

Map of dots and hashes, with the guard in the middle

Carets show the path the guard walks to reach the exit

Same as image 2, but with Xes added in various places.

This entry was edited (2 months ago)

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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.

in reply to mcc

Chris L

in reply to mcc • 2 months ago • •

that’s some fine application of software engineering solutions to programming problems.

in reply to mcc

наб

in reply to mcc • 2 months ago • •

arriving at unix de novo? you love too see it

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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)…

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

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

github.com/mcclure/aoc2024/blo…

(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

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

Today went back and carefully reread my [aoc 2024, day 6, part 2] source looking for problems. Discovered there was a line where I believed— had from the beginning intended!— for it to do test A, but in fact it was doing slightly different test B which would produce bad results. The fact I didn't notice this until now emphasizes the importance of languages which encourage clear, readable code! However even with the fix I am still delivering the wrong answer.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

This might be the worst I've ever done on an AOC problem (grading by number of unsuccessful submissions)! The site is no longer giving me too high/too low hints, I guess to discourage binary search.

I think the only way I can proceed is to rewrite my code to be "dumber" ( mastodon.social/@mcc/114144927… ) — right now I have some clever optimizations, but those optimizations are potential sites for bugs. Increasingly worried about potential weasel wording in the problem statement mastodon.social/@mcc/114332477…

This entry was edited (2 months ago)

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

Okay. So.

- I rewrote my search program to be less optimized in terms of time and more optimized in terms of memory (eg, creating less garbage).

github.com/mcclure/aoc2024/blo…

- In this less optimized state, it took nearly all day to run— like, six hours (but despite doing more work, only crashed and had to be restarted 8 times… so that part worked… sorta… I guess…)

- The "dumber" version produced the correct answer on the first try.

I'm not sure what, if anything, I've learned here.

aoc2024/06-02-guard/src/puzzle-exhaustive.l0 at 4fd6939cbac0a024ed0b5ea85670311688d3fb6a · mcclure/aoc2024

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

^GitHub

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

My original implementation was very smart about avoiding unnecessary work; it only checked the 5,930 "one step ahead" squares, on the logic a wall that never crosses the guard's path can't affect the guard's behavior, and when speculatively placing a wall it would only run the simulation from the moment the guard first reached that square on. Somewhere in that "smart" logic hid a bug. By contrast, the version that eventually worked ran the entire simulation start to finish 16,900 times.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

However I don't really get to go "there's a moral here!" because the brute force placement method only occurred to me *after* I'd implemented the "smart" time-rewinding method. So I didn't do it the smart/broken way because I prematurely optimized; I did it because I didn't want to rewrite the program. But then I had to do that anyway. Oh well!

Anyway, the second half of this was miserable, but I think I've got some useful feedback (from myself) about how to proceed with the "tiny LISP".

in reply to mcc

Allan Chow

in reply to mcc • 2 months ago • •

@mcc

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

Most of the issues I found [in the language] were obvious or things I'd already planned to fix. (Errors without line numbers suck; programming without locals is a pain. Well, obviously.) That "macros" made by constructing lists by-append would turn out to be so painful… that was more of a surprise. I think I have a clearer idea of what I want function declaration to look like now (the plans I had before were too naive). Getting a good repro case that activates the bugs in my GC *is* a blessing.

This entry was edited (1 month ago)

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

This language may show up again in this post series, once I change it enough it constitutes a "different language". Before that though I want to do weeks with textual WASM (to get ideas about LISP-flavored assembly), Dylan & Haskell (to get ideas about multimethods) and Fennel (so I can try out HoneyLISP freeradical.zone/@suetanvil/11…). Alternately, the next version may just be a self-hosted macroassembler! I also hope to do an Emily 2 week, so my occasional "Emily" references won't just be incoherent.

Chris [list of emoji]

2025-04-10 17:45:28

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:
git.information-superhighway.n…

honeylisp
Honeylisp is a programming environment for livecoding the Apple II, written in Fennel and based on the lite code editor.
^{git dot information dash superhighway dot net}

This entry was edited (2 months ago)

in reply to mcc

rk: it’s hyphen-minus actually

in reply to mcc • 2 months ago • •

Dylan’s multimethods are very pretty. To have a random deep cut, REBOL desperately needed multimethods. It could’ve worked, and it would’ve been beautiful.

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

As followup, I'm adding now to the language everything I missed while writing my test program.

This means adding > < >= <=, which means writing test cases for string comparison, which means an excuse to come up with cute Hanzi testcases…

Fun fact: Did you know that in Unicode the Chinese numerals are not actually sorted in lexicographic order?? Or any apparent order at all?

(一 < 四)
but
(四 > 五)

A series of LISP statements comparing letters (d, e) words (ade, aed), and Chinese characters for alphabetical ordering. The Chinese characters:

四 and 五 — 4 and 5 — 4 is greater than 5
九 and 二 — 2 and 9 — 2 is greater than 9
七 and 七 — 7 and 7 — 7 is equal to 7

生 and 死 — "Life" and "Death" — Life is greater than death
善 and 恶 — "Good" and "Evil" — Evil is greater than good
天 and 天 — "Heaven" and "Heaven" — Heaven is equal to Heaven

in reply to mcc

Elias Mårtenson

in reply to mcc • 2 months ago • •

There is a specific Unicode character property for this, although I'm sure you already knew this.

Specifically, the nv property that is the numeric value of a character which represents a number: en.wikipedia.org/wiki/Unicode_…

properties of Unicode characters

^{Contributors to Wikimedia projects (Wikimedia Foundation, Inc.)}

in reply to Elias Mårtenson

mcc

in reply to Elias Mårtenson • 2 months ago • •

@loke I'm going with codepoint/lexicographic ordering because I'm inheriting the Rust implementation, and I think it's the correct approach since afaik there are multiple different "content aware" Unicode sorts so really none of them should be treated as privileged.

@Elias Mårtenson

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

@loke If you want a unicode ordering that should be something you specify longform, not in the short-form > < operators, and probably that code should live in a library.

@Elias Mårtenson

in reply to mcc

Elias Mårtenson

in reply to mcc • 2 months ago • •

Yeah, I'd never actually suggest it's a good idea. In fact, I'm not sure the nv property can ever be really useful for much either.

No "smart" ordering of Unicode characters is ever going to be correct (they can't be, because of conflicting expectations).

in reply to mcc

Brian Campbell

in reply to mcc • 2 months ago • •

Are you talking about in code point order, or according to the Unicode Collation Algorithm?

in reply to Brian Campbell

mcc

in reply to Brian Campbell • 2 months ago • •

@unlambda code point order, which is what I would consider [byte] lexicographic order.

@Brian Campbell

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

So one of the unusual solutions I have created to one of the unusual problems my new language has is that every array, every array ever created by the language, now remembers what line of code it was created on forever¹, because the language doesn't yet have an a priori way of knowing which arrays might later become functions and it *might* be needed for error messages

¹ Oddly, due to another questionable decision I made, this doesn't result in any additional memory usage

This entry was edited (2 months ago)

in reply to mcc

mcc

in reply to mcc • 2 months ago • •

Post-field-test updates:

Finished:
- Line numbers in error messages
- do (call unary function) apply (call function given car element and cdr array) and if (if) builtins now exist
- Lone symbols on a line now return the value instead of calling it as a function

Fizzbuzz is now MUCH more readable and doesn't have to define any library functions except `while`:

github.com/mcclure/lisp0-exper…

TODO:
- `proc` (maybe `fun`) to create functions with named args and locals
- builtin `while`/`for`/`foreach`

Screenshot of `while` implementation from the link, with explanation: Because there are no reliable local variables in the language yet, I fake locals using metaprogramming. The metaprogramming isn't very readable yet, but it's better than it was.

lisp0-experiment/sample/fizzbuzz.l0 at 3b7a6676aca477fe529680fe3e008be24308c720 · mcclure/lisp0-experiment

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

^GitHub

in reply to mcc

mcc

in reply to mcc • 1 month ago • •

Final update for this thread:

So based on the field test of this AOC, the Nameless Experimental LISP has been improved to a point I'm no longer embarrassed publishing it and "released", as open source, on Codeberg:

codeberg.org/mcc/nameless-expe…

I also documented it, pretty extensively, the documentation .md is now the longest single file in the project.

The main new thing is { } lambdas no longer accept arguments, and there's a `fn` and `set-fn` functions that upgrade a { } to have args/locals.

# Argument: 2D-Array -- copy FROM arg1 TO arg0
set-fn 'board-copy '(a1 a2) '(r1 r2) { # args, locals
for 'y 0 (len a1) {
set 'r1 (get a1 y) # Row
set 'r2 (get a2 y)
for 'x 0 (len r1) {
set r2 x (get r1 x)
}
}
}

nameless-experimental-lisp

Unsupported, untitled, but extensively documented, experimental programming language interpreter. Do not actually use.

^Codeberg.org

in reply to mcc

mcc

in reply to mcc • 1 month ago • •

Some fun benefits of the refactor:
- "do" ("create a function and immediately call it") now can be used EITHER as a feral flow control construct OR to inject variables into a block's scope (my `for` impl uses this)
- I seem to have fixed the GC crash by accident?! That's terrifying?

The AOC answers, upgraded to the new variant (they're sample code!) are now part 1:

codeberg.org/mcc/nameless-expe…

And part 2, although I think there's a bug:
codeberg.org/mcc/nameless-expe…

And I find them much more readable!

set 'counter 10
do 'recurse { # Do block knows its own name
print counter ln
if (> counter 0) {
set 'counter (- counter 1)
do recurse
} else {
print "Done" ln
}
}

# Usage: for 'varname from to {case} step
# Because of dynamic scope, higher order functions like this have to namespace
# their local variables (so they don't shadow variables in the inner scope 😢)
set-fn 'for '(_for_var _for_from _for_to _for_case _for_step) {_for_scope} {
# step argument is optional, and defaults to "smart" picking 1 or -1
if (! _for_step) {
set '_for_step \
(if (< _for_from _for_to) {1} {-1})
}

# Create a dictionary to store the "locals". There's one local, the iter var
set '_for_scope (make-dict)
set _for_scope _for_var _for_from

# Repeatedly call the given block until the iter var reaches its destination
while {!= (get _for_scope _for_var) _for_to} {
# Invokes block with _for_var injected into scope
do _for_scope _for_case

# Increment iter var
set _for_scope _for_var (+ (get _for_scope _for_var) _for_step)
}
}

# Same as "do" code in other example
for 'i 10 0 {
print i ln
}

nameless-experimental-lisp/sample/aoc/2024-day6-part1.l0 at 36435712e43afcde5bc85e74341928e5cbf3d12c

nameless-experimental-lisp - Unsupported, untitled, but extensively documented, experimental programming language interpreter. Do not actually use.

^Codeberg.org

in reply to mcc

Amir Livne Bar-on

in reply to mcc • 2 months ago • •

about locals - isn't it solvable by macros? lambda that parses the argument list and pushes to a linked list of environments

in reply to Amir Livne Bar-on

mcc

in reply to Amir Livne Bar-on • 2 months ago • •

@Pashhur There are two problems with solving it with a macro:

- If I place any extra code at the end of the function-- for example, setting the locals to previous values, or to nil-- then I will break any tail recursion the function performs.

- I don't have any builtins for environment manipulation; if I did I'd want to choose them very carefully, because part of the point of this language is to be less aggressively dynamic than my previous language attempts, so I can easily write a compiler.

@Amir Livne Bar-on

in reply to mcc

Owen Nelson

in reply to mcc • 2 months ago • •

drunk driving does let people get to work on time sort of vibe

in reply to mcc

fabiosantoscode

in reply to mcc • 2 months ago • •

if your problem was just variables, you could have solved it elegantly by making them all nullary functions.

So assigning X = 3 would be essentially creating a function called X that takes no arguments and returns 3.

But alas, the problem also affects primitives

in reply to fabiosantoscode

mcc

in reply to fabiosantoscode • 2 months ago • •

@fabiosantoscode I solved the problem a way like this in my previous language design attempts but I'm trying to do something simpler this time because I want a compiler. Last time I made things complicated and so the compiler was hard to implement

@fabiosantoscode

in reply to mcc

dave

in reply to mcc • 2 months ago • •

like webassembly text format?

in reply to dave

mcc

in reply to dave • 2 months ago • •

@dthompson Yes, like that. But for 6502.

@dave

in reply to mcc

slembcke

in reply to mcc • 2 months ago • •

You would be in good company! I actually vaguely remember there being a LISP based assembler for 6502.

in reply to mcc

Ölbaum

in reply to mcc • 2 months ago • •

The L in LISP already stands for Little. So saying “this little LISP” is like saying “this automatic ATM.” /j

in reply to Ölbaum

mcc

in reply to Ölbaum • 2 months ago • •

@oscherler It's one order of magnitude littler. We need to introduce SI prefixes.

@Ölbaum

in reply to mcc

Graham Sutherland / Polynomial

in reply to mcc • 2 months ago • •

@oscherler attolisp

@Ölbaum

in reply to mcc

R

in reply to mcc • 2 months ago • •

just saw this post -- Back In The Day there were a number of table-driven retargetable assemblers for systems like this, with "Telemark Assembler" being especially common in the circles we personally lurked around

they're all quite underpowered by modern devtool standards though, and they very much didn't have good implementations for architecture-specific fixups

it'll be interesting to see your take on this!

in reply to R

mcc

in reply to R • 2 months ago • •

@r someone recommended this as a project along similar lines, im curious about it bitbucket.org/SpindleyQ/honeyl… (spindleyq is on Mastodon also)

Bitbucket

^{bitbucket.org}

in reply to mcc

Riley S. Faelan

in reply to mcc • 2 months ago • •

Sensitive content

in reply to Riley S. Faelan

mcc

in reply to Riley S. Faelan • 2 months ago • •

@riley It's on my todo list for the Babel project! Lua integration makes it of special interest to me (I burned out on Lua bad over the last five years, but it still might be my favorite language if you judge it as an intellectual object rather than something practical I expect to use.)

@Riley S. Faelan

in reply to mcc

jcoglan

in reply to mcc • 2 months ago • •

does "no special forms" imply it has lazy evaluation?

in reply to jcoglan

mcc

in reply to jcoglan • 2 months ago • •

@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.

@jcoglan

in reply to jcoglan

jcoglan

in reply to jcoglan • 2 months ago • •

(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)

in reply to jcoglan

mcc

in reply to jcoglan • 2 months ago • •

@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…

@jcoglan

in reply to mcc

spv

in reply to mcc • 2 months ago • •

now make it Bizzfuzzbog with the numbers 7, 43, and 8041962

in reply to mcc

Elias Mårtenson

in reply to mcc • 2 months ago • •

hey, that implementation of if is exactly how I implemented it in the Kap standard library. I don't think it's ugly at all.

in reply to mcc

Joe Groff

in reply to mcc • 2 months ago • •

if it's a language inspired by LISP and Tcl, does that make it a Listcl

in reply to mcc

Ted Mielczarek

in reply to mcc • 2 months ago • •

the one thing I genuinely liked about writing LISP when I got to do so at work (almost 30 years ago now) was that Emacs has genuinely fantastic keyboard shortcuts for code navigation, like C-M-{f,b} to move forward or backwards by one sexp, and C-M-{d,u} to move into and out of a sexp. Does your paren-free syntax allow for this without having a full-blown parser hooked up to the editor?

in reply to Ted Mielczarek

mcc

in reply to Ted Mielczarek • 2 months ago • •

@tedmielczarek I think so, because the parser is pretty simple— all it would have to know is a backslash-joined line is "a sexp". But also, I don't use emacs, so this feels like not my problem lol.

@Ted Mielczarek

in reply to mcc

Ted Mielczarek

in reply to mcc • 2 months ago • •

For the record: I'm not arguing that anyone should use Emacs! I quit that habit myself a few years back. It was just a really great code editing experience that I don't think I've experienced an equivalent of with any other language+editor combination.

in reply to mcc

Ingvar

in reply to mcc • 2 months ago • •

In a 1-lisp, there may or may not be a distinction between functions and variables. A worked example would be the really weird lisp "xlisp" (which was a lisp with very pre-CLtL object orientation on top), where something like

((lambda (a b) (+ a b) 17 42)

would evaluate to 59.

And "(defun sum (a b) (+ a b))" would cause the symbol "sum" to be bound to the list (lambda (a b) (+ a b))

So on that basis, if you have any way to bind symbols to values, it's probably not a 0-lisp.

mcc reshared this.

in reply to mcc

varx/social

in reply to mcc • 6 days ago • •

Thank you for Doing A Learning and sharing it. 😀

Unknown parent

mcc

Unknown parent • 2 months ago • •

@dysfun That's the advantage of writing code in a totally novel programming langugae… I can't use copilot… no sample code to work off

@gaytabase

Unknown parent

mcc

Unknown parent • 2 months ago • •

@dysfun I'm not actually 100% sure WHAT I'm doing! I'd have to trace the number interpreter and the implementation of +.

Now that I think about it, it might be better to replace the positive (1<<63) with whatever negative number (1<<63) corresponds to, and have the reader reject number literals over ((1<<63)-1)?

@gaytabase

in reply to mcc

Matthew Abbott

in reply to mcc • 2 months ago • •

May I suggest the stand-in name NELS?

Nameless
Experimental
LISP
Sandbox (or Specification, Setup, Something)

in reply to Matthew Abbott

mcc

in reply to Matthew Abbott • 2 months ago • •

@matt I mean I was thinking NEL.

I am amused by languages that sound like someone's name. "Nel" for Nameless Experimental List, "Uli" for Unnamed Lisp Interpreter, "Uel" for Unnamed Experimental Lisp.

@Matthew Abbott

Unknown parent

mcc

Unknown parent • 2 months ago • •

@bob I do not, what is it?

@bob

Unknown parent

mcc

Unknown parent • 2 months ago • •

@RenewedRebecca i think so, but I was trying to cut down the lisp syntax by removing the (parenthesis), and then i ran into this other problem.

@Becky

Unknown parent

mcc

Unknown parent • 2 months ago • •

@somebody I mean of course another way of looking at it is the unoptimized version literally took *six hours*, and my laptop was mostly unavailable while it was running because I was trying to let it use all the RAM. So there really was a legitimate reason to avoid that.

@Dataline

Unknown parent

mcc

Unknown parent • 2 months ago • •

@somebody "All this said, given more time, I'm sure you could have had the space to make sure at every step in the smarter answer" yes… but *that's* probably not possible when using a literal unfinished proof-of-convept interpreter!

@Dataline

Unknown parent

Dataline

Unknown parent • 2 months ago • •

All this said, given more time, I'm sure you could have had the space to make sure at every step in the smarter answer, breaking it all up into a sequence of dumb answers to subproblems, all tied together by some nice formal mathematical idea, as we do when we're composing a smarter system, and the smarter answer would have worked if each of it's parts were as dumb as a lever, not trying to do too much by itself. But for this problem, the point of inflection was to let the computer do the heavy lift in a way you could wrap your head around in the moment.

Unknown parent

mcc

Unknown parent • 2 months ago • •

@deshipu Oh, is it? That would make sense. But surely they can't keep to that consistently due to the 2 byte / 3 byte discrepancy and that characters were added to the standard at different times?

@ɗ𐐩ʃƕρʋ

mcc reshared this.

in reply to mcc

Adriano

in reply to mcc • 2 months ago • •

@deshipu 生 > 死 seems to indicate otherwise.

@ɗ𐐩ʃƕρʋ

in reply to mcc

Shar(yna)Tran/Shark(aeopteryx)

in reply to mcc • 2 months ago • •

@deshipu heh, someone else I follow also saw this the other day and did a thread about their befuddlement and how even if it makes sense it doesn't really make a *lot* of sense:
outerheaven.club/objects/e5706…

xrvs (@xarvos@outerheaven.club)

>>> '一' < '二' True >>> '二' < '三' False

^{outerheaven.club}

@ɗ𐐩ʃƕρʋ

⇧