[HN Gopher] Designing a programming language to speedrun Advent ...
___________________________________________________________________
Designing a programming language to speedrun Advent of Code
Author : polyrand
Score : 206 points
Date : 2023-11-13 21:45 UTC (1 days ago)
(HTM) web link (blog.vero.site)
(TXT) w3m dump (blog.vero.site)
| lawn wrote:
| Such a fantastic and inspiring post, and a very cool language.
| Kudos!
| hnlmorg wrote:
| > Before we move on, I want to point out that "being able to
| write code from left to right without backtracking" is a
| completely bonkers thing to optimize a programming language for.
| This should not be anywhere in the top hundred priorities for any
| "serious programming language"!
|
| 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.
| bmitc wrote:
| I don't really even understand what is meant by "being able to
| write code from left to right without backtracking", much less
| why that is bonkers. Scrolling down and seeing the code
| examples, the language even seems quite conventional, so I'm
| even more confused.
| KeplerBoy wrote:
| Isn't that a whole lot more "being able to write code without
| making a lot of dumb mistakes", which is a feature of the
| programer.
|
| So it boils down to getting gud and practice?
| Cthulhu_ wrote:
| That's what it sounds like to me. Thinking about a line of
| code before writing it down, or knowing what the code will
| do instead of trial and error (which... is what I often do,
| lol)
| ThreeToZero wrote:
| The post gives an example of how python doesn't have this
| feature in the section
| [https://blog.vero.site/post/noulith#coding-with-and-
| without-...]
|
| 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
| bmitc wrote:
| Thanks for pointing out that specific example and
| comparison. The solution seems like it's just a less
| readable pipeline. 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;
| dekhn wrote:
| after a while, my brain reorganized and i think of the
| map() first, before thinking about the content of the
| map, basically to avoid the keystrokes required to go to
| beginning of line, then back to where I was typing.
| hnlmorg wrote:
| No, what the author is discussing is a syntax thing.
|
| 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 7
|
| Though 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.
| xiaq wrote:
| You can write A | B | C | result=$(cat) in shell.
|
| 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...
| _0ffh wrote:
| Or with uniform function call syntax
|
| result = A().B().C()
| Strilanc wrote:
| Here's an example. In SQL the "select" clause comes at the
| start. In C# LINQ queries, "select" comes at the end. A major
| resulting difference is autocomplete works in the latter case
| but not the former.
|
| 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.
| frou_dh wrote:
| Talking of shell, the preference for left-to-right is often
| used to justify "useless use of cat", i.e. `cat file | command`
| instead of `command <file`, but it can just be written `<file
| command` instead.
| robertlagrant wrote:
| I'm surprised that file> command isn't the preferred idiom.
| Does that mean something else?
| hnlmorg wrote:
| Yes, that would write to a file called "command". So the
| correct way to write that would be:
| command > file
|
| https://www.gnu.org/software/bash/manual/html_node/Redirect
| i...
| smrq wrote:
| That would execute the command `file` and put the output
| into the file `command`.
| robertlagrant wrote:
| Oh, now I re-read it - of course! Hah.
| sgarland wrote:
| Is `<file` shorthand for `cat file`, or is that only true
| when used in a sub-shell?
| frou_dh wrote:
| I guess it's equivalent to `: <file` i.e. hooking up the
| stdin of the no-op command.
| xigoi wrote:
| No, `< file command` is completely equivalent to `command <
| file`.
| mst wrote:
| I'll often commit 'useless use of cat' there for three
| reasons:
|
| 1) Muscle memory
|
| 2) Often when I don't I end up needing two files later
|
| 3) It annoys merlyn (Randal Schwartz)
| mpweiher wrote:
| Yeah, Smalltalk also works this way...mostly. 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.
| firejake308 wrote:
| The syntax reads similar to R with pipes
| rohithgilla wrote:
| Amazing, the cross inspiration from python and rust is cool. Good
| work!
| dtx1 wrote:
| > I solve and write a lot of puzzlehunts, and I wanted a better
| programming language to use to search word lists for words
| satisfying unusual constraints, such as, "Find all ten-letter
| words that contain each of the letters A, B, and C exactly once
| and that have the ninth letter K."
|
| So... Perl?
| jstanley wrote:
| grep { len($_) == 10 && /^[^a]*a[^a]*$/i && /^[^b]*b[^b]*$/i &&
| /^[^c]*c[^c]*$/i && /k.$/i } @words;
|
| Is there a simpler way?
| darrenf wrote:
| Perl has `length`, not `len` :) Also I can't resist a bit of
| TIMTOWTDI: my @found = grep {
| local $_ = lc; length == 10 &&
| substr($_,8,1) eq "k" && join("",sort
| [/([abc])/g]->@*) eq "abc" } @words;
| sltkr wrote:
| Might as well do it on the command line at that point:
| $ 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
| cmdlineluser wrote:
| Not sure if it would be considered simpler but lookaheads can
| be used to express it in a single pattern.
| ^(?=.{8}k.$)(?=[^a]*a[^a]*$)(?=[^b]*b[^b]*$)(?=[^c]*c[^c]*$)
| sltkr wrote:
| It does lead to a very concise invocation:
| $ perl -ne 'print if /^(?=.{8}k.$)(?=[^a]*a[^a]*$)(?=[^b]*b
| [^b]*$)(?=[^c]*c[^c]*$)/' /usr/share/dict/words
| shabble wrote:
| and to squash a little further: perl
| -ne '/^(?=([abc].*){3})(?!.*([abc]).*\2).{8}k.$/&&print'
| /usr/share/dict/words
| oneshtein wrote:
| Bug: 11 words are missing. [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
| oneshtein wrote:
| [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
| oneshtein wrote:
| [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
| sltkr wrote:
| You can also do: 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.
| cptnapalm wrote:
| The pipeline wasn't just the fastest; it left everything
| else in the proverbial dust!
| oneshtein wrote:
| [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
| oneshtein wrote:
| Bug fixed. [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
| Avshalom wrote:
| W in Wordlist, length(W,10),
| maplist(\L^memberchk(L,W),[a,b,c]), nth(10,W,k).
| jodrellblank wrote:
| I think memberchk will do one check for each letter (not
| checking the rest of the list and leaving no choice point)
| rather than checking each letter is present only once.
| Avshalom wrote:
| Oh, yeah, my brain skipped over that part of the
| constraint. Does ruin the simplicity a bit.
| (findall(C,member(L,W),S),length(S,1))
| shaftoe444 wrote:
| Inspired me to have another run at the second half of Crafting
| Interpreters.
| ghj wrote:
| I didn't realize who this was by the title, but this is
| betaveros, the guy who won 1st place in Advent of Code every
| single year since 2019:
| https://clist.by/account/32289/resource/adventofcode.com/
| cjbprime wrote:
| Including in 2022 with the self-created programming language
| the post is about, which is just amazing, and lives somewhere
| in my head near FlaSh's 2020 decision to switch to playing pro
| StarCraft Brood War tournaments as the Random race -- requiring
| him to become world-class at three races (nine race matchups)
| while his opponents only have to be world-class at one race
| (three race matchups). FlaSh came third in the largest
| tournament that year.
|
| 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.)
| dataengineer56 wrote:
| It seems crazy that 2nd to 4th in 2021 didn't do 2022 at all!
| It's an annual ritual for me, I couldn't imagine being so
| heavily into it one year and then not competing at all the
| next. Was there a reason?
| cjbprime wrote:
| I heard something about a large competitive programming
| tournament (i.e. a commercial one) happening at a nearby
| time to AoC, I think it was that for at least one person.
|
| (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?)
| avgcorrection wrote:
| All it takes is someone convincing you to take a travel
| vacation around Christmas so that you are too busy to be
| competitive. (And maybe you don't bother to play if you
| can't be competitive at it.) Nothing LIVES CHANGE sized
| has to be the case...
| mrits wrote:
| "I don't know what his total will be when he's finished
| because life gets in the way. Things happen."
|
| One great golf on another younger great golfer that might
| catch up to him.
| saagarjha wrote:
| I think it's interesting how similar a lot of this stuff is to
| what I do, except I'm not very good at Advent of Code and also I
| decided to hack Python to do this instead of writing my own
| language. For example:
|
| * 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.py
| master-lincoln wrote:
| reads a bit like javascript now. You might want to consider
| switching languages
| saagarjha wrote:
| Oh it definitely does. The reason I stick with Python is that
| it has a somewhat decent standard library, and IMO fewer
| surprises (I don't know Python or JavaScript all that well,
| since I basically never use it professionally, so I need to
| reduce footguns for myself).
| djxfade wrote:
| Type cohersion and type juggling can bring a few surprises.
| But usually only when you do something weird to hit those
| edge cases. Otherwise, it's standard library is actually
| very decent now. Especially when working with arrays. You
| have all the nice to have methods, like, split, find,
| filter, map, reduce, every, some, etc... Which makes it a
| really nice language for these kind of tasks.
|
| The example above would like this in modern javascript:
| str.split(',').map(char => Number(char)).filter(num => num
| > 5).length
| worksonmine wrote:
| Or if you like to live dangerously:
| str.split(',').filter(n => +n > 5).length
| dumbo-octopus wrote:
| Not all that dangerous, tbh. My main concern would be NaN
| potentially cascading through, but not only is `NaN > 5`
| false, `!!NaN` is too.
| saagarjha wrote:
| To be clear by "standard library" I mean that Python has
| like actual data structures that are useful. Also while
| not part of the standard library arbitrary precision
| integers and associated functions (e.g. modular pow) can
| be quite helpful.
| recursive wrote:
| Javascript now has Map, Set, and bigint. But no powmod.
| contravariant wrote:
| Honestly I'm jealous of JavaScript's arrow syntax. I don't
| really need anything else but the arrows are nice (and Turing
| complete).
| maegul wrote:
| I always figured that once Python got the walrus operator
| it would be a matter of time until arrow functions of some
| sort made more and more sense on Python.
| Spivak wrote:
| I really hope not tbh, once you break that seal it will
| consume the entire language into nested anonymous
| function soup without all the facilities JS has
| accumulated over the years to mitigate it. Python is an
| iterator based language and it leads to some very nice
| code if you design with that in mind.
|
| 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.
| mst wrote:
| I really wish python would steal 'let' from JS,
| specifically in a block scoped form - coming from perl's
| 'my' as a way of life, python's (and ruby's) function level
| scoping and "surprise! variable just popped into existence
| on assignment!" behaviour really messed me up.
| tuukkah wrote:
| One key point I overlooked on first reading:
|
| > _[--] 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").
| nemo1618 wrote:
| > The title is clickbait. I did not design and implement a
| programming language for the sole or even primary purpose of
| leaderboarding on Advent of Code.
|
| 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_zDbInYOpQ
|
| AoC solutions here:
| https://github.com/lukechampine/advent/tree/master/2022
|
| (The language has builtin commands for fetching inputs and
| submitting solutions)
| brandly wrote:
| You should write a longer post about it!
| nemo1618 wrote:
| aight
| avindroth wrote:
| Are you participating in AoC maybe? I might write some stuff.
| jodrellblank wrote:
| How does that do the fiddly bit "contain each of the letters A,
| B, and C exactly once" ?
| avindroth wrote:
| In terms of speedrunning, couple of friends and I are trying to
| speedrun AoC using LLMs (sacrilegious i know).
|
| It's been growing a bit; if interested, feel free to shoot me an
| email to joshcho@stanford.edu
|
| Or @eating_entropy on X
___________________________________________________________________
(page generated 2023-11-14 23:02 UTC)