Designing a programming language to speedrun Advent of Code
blog.vero.site
blog.vero.site
From the post:
> I think I predicted that requiring myself to use only Noulith on Advent of Code would make my median leaderboard performance better but my worst-case and average performances significantly worse. I don’t think my median performance improved, but my worst-case performance definitely got worse. Somehow it still didn’t matter and I placed top of the leaderboard anyway. (I will note that 2021’s second to fourth place all didn’t do 2022.)
(I also don't think it's unimaginable; lives change, everyone's going to have a point where they played one year and not the next, most obviously illness, but also life changes like marriage, kids, stressful new job, etc?)
One great golf on another younger great golfer that might catch up to him.
* I couldn’t really make operators first class functions, but I just autoimported operator which has this but in words
* I wanted partial application and hated lambda syntax, so I hacked it together with some magic. “_0 + 1” is basically equivalent to lambda x: x + 1
* Python really likes to make everything a free function, which messes with the whole left-to-right thing. So I monkey-patched functional methods onto all the collections
Together this means that if I have like a comma separated list of numbers in str and I want to, idk, count how many are above five I’d do something like
str.split(",").map(int).filter(_0 > 5).len
which matches how my brain things about it far better than how Python would like me to write it. It uses some tricks but it’s not actually that bad of a hack IMO: https://github.com/saagarjha/advent-of-code/blob/main/aoc.pyThe example above would like this in modern javascript:
str.split(',').map(char => Number(char)).filter(num => num > 5).length str.split(',').filter(n => +n > 5).lengthBut my big thing is about being able to scope values to the specific block where they belong:
...
let foo;
{
let x = blah();
let y = frob(x);
foo = munge(y);
}
and the temporaries 'x' and 'y' have gone away as soon as the } happens.also, if you've ever had "fun" trying to capture a loop variable,
for (let val of things) {
callbacks.push(() => val.finish());
}
has a different 'val' for each iteration of the loop so you can do that safely without requiring some sort of copying or an intermediate function invocation to create an extra scope.Oh, and it also renders impossible certain weird constructs like
if <test>:
some_name = ...
where now whether the some_name variable even -exists- after that if block is indeterminate without knowing which way the <test> went.I also like being able to do e.g.
for (let thing of things) {
let blah = thing.blah;
callbacks.push(() => blah.doThing());
}
Without 'let' you'd have to write (for the first 'for' example) for (var val of things) {
callbacks.push(((val) => {
return () => { val.finish() }
})(val));
}
to perpetrate let-over-lambda to get a separate scope for the callback function.This is not my favourite thing to write, and -very- far from my favourite thing to read later.
Hopefully that gives you a better idea of why I, at least, prefer having 'let' available.
It's really incredible how much such a small feature in the grand scheme of things `(function() { })()` influences all API and library design. Right now passing around functions in Python is ugly and reads as such which is enough of a deterrent for most people.
"," split [ string>number 5 > ] count
or "," split [ string>number ] map [ 5 > ] count
or "," split [ string>number 5 > ] filter lengthBut I do do the following sort of thing in Python: ``` from chainzzz import C
C(some_list).group_by(lambda x: x + 1).map(lambda key: key % 2).size() ```
Where C(...) gives us the same object but with some methods added to it as you can see
I did: https://github.com/lukechampine/slouch
"Find all ten-letter words that contain each of the letters A, B, and C exactly once and that have the ninth letter K"
:load wordlist wordlist.txt
words wordlist | filter -:(len == 10 and .8 == "k")
A more interesting example: https://www.youtube.com/watch?v=i_zDbInYOpQAoC solutions here: https://github.com/lukechampine/advent/tree/master/2022
(The language has builtin commands for fetching inputs and submitting solutions)
:load wordlist wordlist.txt
=hasABC { all (count _ x == 1) "abc" }
words wordlist | filter -:(len == 10 and hasABC and .8 == "k")
Notes:{ } defines a lambda with parameters named x,y,z,a,b,c...
_ is the same as in noulith -- it turns any expression into a lambda. Values can also be omitted from most expressions (e.g. len == 10) for the same effect.
-: takes a lambda with n parameters and turns it into a lambda that takes 1 parameter and replicates it n times.
The lambda formation is something that will have to be gnawed at though.
This feels very similar to an APL or K solution.
Are those languages you're aware of?
There are plenty of serious languages that are written this way. Most noticeably are shell scripting languages but I’ve seen stack based and functional languages that are written like this too.
3 negated + 2 negated.
Alas, as with the post, this also breaks down when you have more than 2 arguments (or in Smalltalk parlance, 1 argument in addition to the message receiver), as those are handled by keyword arguments and you can't tell where the keywords for one message stop and the ones for the next one start. Let's say we have some nested arrays, which are accessed with at: in Smalltalk: array at:4 at:2 at:1.
Alas, that doesn't get interpreted as 3 messages, but as the single message at:at:at:. As it kind of has to be as there is no way to disambiguate. Surprisingly, Smalltalk does have a way to chain messages and thus separate the keywords, the semicolon: array at:4;
at:2;
at:1.
Alas, this sends the subsequent messages to the original receiver, so it is equivalent to: array at:4.
array at:2.
array at:1.
(And so this example doesn't actually make sense, it's just a syntax example). So what you have to do is add parens: ((array at:4) at:2) at:1.
Hmm, not nice. For Objective-S (https://objective.st), I introduced the pipe for message chaining: array at:4 | at:2 | at:1.
One way of looking at this is as a syntactic device that allows left-to-right typing without backtracking, which it is. And that is both nice to write and quite readable, IMNSHO.A second way of looking at it is as a version of the pipe/filter architectural style, with each message expression being a filter, the results from the filter on the left piped into the filter on the right as the receiver. This is a little bit like |> in some FP languages. But really only a little bit, because in Objective-S this is not the whole story, but just a way of integrating messaging into the way the pipe/filter architectural style is supported at the language level.
A more pervasive example is how OOP languages do x.f(...) instead of f(x, ...). This also helps with autocomplete. Also it results in calls chaining like x.y(...).z(...) instead of nesting like z(y(x(...), ...), ...).
These kinds of things have noticeable effects on how easy it is to discover relevant methods and how fast they are to type.
So it boils down to getting gud and practice?
Lets take a hypothetical C-like language:
result = C(B(A()))
In this your result is on the left hand side. The first function to be executed is A and then B and lastly C, which also reads right to left. This is a pretty common way to write code, it's by no means unique to C-like languages. So you'd have gotten so good at reading code like this that you probably don't even realise you're reading right to left.Now lets look at a POSIX-like shell language:
result = $(A | B | C)
Here the result is still on the left hand side but now you're reading the functions from left to right (ie pipes)I'm not the article author by my own programming language takes things a step further from conventional shells and you can do the following:
A -> B -> C -> set result
Here it reads fully left to right. There is zero confusion about which order to read this.----------------
Going back to the more general point about reading left to right, it's worth noting that even math operators can be extended this way. For example with polish notation (https://en.wikipedia.org/wiki/Polish_notation) your operators precede your values. Effectively turning those symbols into function names:
+ 2 5
...would return 7Though personally I prefer the more traditional format of operators sitting between their values (2+5), but that's purely because that is what I'm used to.
Edit: this only works if the shell runs the last command in the current environment (as opposed to a subshell), and only ksh and zsh seem to do that...
result = A().B().C()
Python fails this criteria because if you type as you think through the process, you have to move the cursor to the beginning to prefix the 'map' around the input.
For example this series of transforming the input:
puzzle_input.split("\n\n")
map(ints, puzzle_input.split("\n\n"))
map(sum, map(ints, puzzle_input.split("\n\n")))
max(map(sum, map(ints, puzzle_input.split("\n\n"))))
----------------------
Compare to this postfix syntax where you can write this incrementally as you think through the operations:
puzzle_input split "\n\n" map ints map sum then max
puzzle_input split "\n\n" map ints map sum then max;
puzzle_input split "\n\n" map ints map sum then sort then (_[-3:]) then sum;In bash/ksh, it matches frou_dh's explanation. In zsh, it depends on how you've set the various *NULLCMD options and parameters. In csh, it is an error.
Even in zsh, when configured to behave like `cat file` it still doesn't quite do that as it won't concatenate files as it only passes the first shell word following the `<` to `cat`(or whatever you've set NULLCMD to). Guess that means you could be evil by making a wrapper that allows weird Unicode separators to pass multiple files in one word to get the concatenation back ;)
This means I get to remember an increasingly unfortunate amount of differences. I’ll add this one to the pile, thanks.
I definitely get the argument about shellcheck though, it would be nice if it supported zsh.
It definitely looks foreign, but then, so does parameter substitution in bash or zsh. There are shell scripts, and then there are those that make you break out the man pages to figure out what they’re doing.
https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V...
1) Muscle memory
2) Often when I don't I end up needing two files later
3) It annoys merlyn (Randal Schwartz)
command > file
https://www.gnu.org/software/bash/manual/html_node/Redirecti...> [--] I wanted access to Haskell’s list monad in a sloppier language.
> I like static types, but only if they’re sufficiently expressive and supported by good inference, and I like not having to implement any of that stuff even more, so I settled for dynamic typing.
Then it's some of the power of Haskell without any of the safeguards. Plus being able to write "x f y" to mean a function call to f with arguments x and y (whereas in Haskell you'd write "x `f` y").
So... Perl?
words←⊃⎕nget 'wordlist.txt' 1 ⍝ read lines
tenK←'^........k.$' ⎕S '&' ⊢ words ⍝ regex filter
↑tenK/⍨{∧/1='abc'(+/∘.∊)⍵}¨tenK ⍝ count abc and filter
Dyalog APL, but it's still kinda ... heavy.Is tenK←{(10=≢⍵)∧⍵[9]='k'}¨words better?
Feel that better matches the problem spec, although requires the each
words←↑⊃⎕nget 'wordlist.txt' 1
tenK←words⌿⍨('k'=words[;9])∧(' '≠words[;10])∧(' '=words[;11])
tenK⌿⍨{∧/1='abc'(+/∘.∊)⍵}⍤1⊢tenK
Mix ↑ turns the nested wordlist into a 2D array by padding short strings out to the length of the longest using spaces, which I don't like but am (ab)using here to tell when the words end. W in Wordlist,
length(W,10),
maplist(\L^memberchk(L,W),[a,b,c]),
nth(10,W,k). (findall(C,member(L,W),S),length(S,1)) sls '^........k.$' .\wordlist.txt -raw |where { $W=$_;
('a','b','c' |where
{ $W.Contains($_) -and $W.IndexOf($_) -eq $W.LastIndexOf($_) }
).Count -eq 3 } grep { len($_) == 10 && /^[^a]*a[^a]*$/i && /^[^b]*b[^b]*$/i && /^[^c]*c[^c]*$/i && /k.$/i } @words;
Is there a simpler way? $ grep '^........k.$' /usr/share/dict/words | grep a | grep b | grep c | grep -v 'a.*a' | grep -v 'b.*b' | grep -v 'c.*c'
backstroke
bailiwicks
benchmarks
branchlike
bushwhacks
greenbacks
matchbooks
piggybacks
roadblocks
scrapbooks
slingbacks
throwbacks
thumbtacks [me@fedora ~]$ time perl -n -e 'length($_) == 10 && /^[^a]*a[^a]*$/i && /^[^b]*b[^b]*$/i && /^[^c]*c[^c]*$/i && /k.$/i && print' /usr/share/dict/words | wc -l
26
real 0m0,168s
user 0m0,162s
sys 0m0,007s
[me@fedora ~]$ time perl -n -e '/^(?=.{8}k.$)(?=[^a]*a[^a]*$)(?=[^b]*b[^b]*$)(?=[^c]*c[^c]*$)/ && print' /usr/share/dict/words | wc -l
17
real 0m0,260s
user 0m0,254s
sys 0m0,006s
[me@fedora ~]$ time perl -n -e '/^.{8}k.$/ && /a/ && /b/ && /c/ && !/a.*a/ && !/b.*b/ && !/c.*c/ && print' /usr/share/dict/words | wc -l
17 real 0m0,115s
user 0m0,109s
sys 0m0,008s
[me@fedora ~]$ time bash -c "grep '^........k.\$' /usr/share/dict/words | grep a | grep b | grep c | grep -v 'a.*a' | grep -v 'b.*b' | grep -v 'c.*c'" | wc -l
17
real 0m0,015s
user 0m0,010s
sys 0m0,020s
[me@fedora ~]$ time awk '/^.{8}k.$/ && /a/ && /b/ && /c/ && !/a.*a/ && !/b.*b/ && ! /c.\*c/ { print }' /usr/share/dict/words | wc -l
17
real 0m0,129s
user 0m0,124s
sys 0m0,006s
[me@fedora ~]$ time perl -n -e 'local $_ = lc; length == 11 && substr($_,8,1) eq "k" && join("",sort [/([abc])/g]->@*) eq "abc" && print' /usr/share/dict/words | wc -l
17 real 0m0,234s
user 0m0,228s
sys 0m0,007s sed -e '/^........k.$/!d; /a/!d; /b/!d; /c/!d; /a.*a/d; /b.*b/d; /c.*c/d' /usr/share/dict/words
I wouldn't expect it to be much faster than AWK, but not much slower either.Interesting that the pipeline is the fastest! I would expect the sheer number of separate processes to slow things down considerably, but apparently it doesn't really matter. Probably because the first `grep` already filters out most of the dictionary, so there isn't a lot of I/O through the pipes.
The IO doesn’t matter so much because they’re done in parallel. Whereas the other examples have to filter each word throw the entirety of their steps before they can proceed onto the next word.
[me@fedora ~]$ time sed -e '/^........k.$/!d; /a/!d; /b/!d; /c/!d; /a.*a/d; /b.*b/d; /c.*c/d' /usr/share/dict/words | wc -l
17
real 0m0,075s
user 0m0,070s
sys 0m0,006s [me@fedora ~]$ time perl -n -e 'length($_) == 11 && /^[^a]*a[^a]*$/i && /^[^b]*b[^b]*$/i && /^[^c]*c[^c]*$/i && /k.$/i && print' /usr/share/dict/words | wc -l
17
real 0m0,160s
user 0m0,153s
sys 0m0,008s ^(?=.{8}k.$)(?=[^a]*a[^a]*$)(?=[^b]*b[^b]*$)(?=[^c]*c[^c]*$) $ perl -ne 'print if /^(?=.{8}k.$)(?=[^a]*a[^a]*$)(?=[^b]*b[^b]*$)(?=[^c]*c[^c]*$)/' /usr/share/dict/words [me@fedora ~]$ time perl -ne 'print if /^(?=.{8}k.$)(?=[^a]*a[^a]*$)(?=[^b]*b[^b]*$)(?=[^c]*c[^c]*$)/' /usr/share/dict/words | wc -l
17
real 0m0,250s
user 0m0,245s
sys 0m0,006s perl -ne '/^(?=([abc].*){3})(?!.*([abc]).*\2).{8}k.$/&&print' /usr/share/dict/words [me@fedora ~]$ time perl -ne '/^(?=([abc].*){3})(?!.*([abc]).*\2).{8}k.$/&&print' /usr/share/dict/words | wc -l
6
real 0m0,118s
user 0m0,112s
sys 0m0,007s my @found = grep {
local $_ = lc;
length == 10 &&
substr($_,8,1) eq "k" &&
join("",sort [/([abc])/g]->@*) eq "abc"
} @words;The last time I did AOC, I tracked every error I made to reflect on my mistakes when coding.
I think this year I will do "Advent of AI" and see how far AI tooling can get me.
IIRC Elm didn't have unary minus for quite some time just fine unless its author decided he really would like to have specifically unary minues but, weirdly, not any other unary operator. So, what's the deal with unary minus, why do people want it so much?
It’s been growing a bit; if interested, feel free to shoot me an email to [redacted]
Or [redacted] on X