HNHacker News
TopNewBestAskShowJobs

justinpombrio

4,649 karma · joined March 26, 2011

"zall" + "ambo" + "@gmail.com"
submissionscomments
justinpombrio··on Intuitive concurrent programming in any language
It's an approach to building a library. You could implement it for COBOL, Fortran, or C#.
justinpombrio··on Example.com just launched the biggest redesign in decades
That assumes that (i) every region has a primary language, and (ii) everyone in that region speaks that language, both of which are false.

(And false often enough that guessing language based on IP address works badly in practice, I hear.)

justinpombrio··on Example.com just launched the biggest redesign in decades
I've used http://www.com for that.
justinpombrio··on Computation as a universal and fundamental concept
There's no such thing as an undecidable statement. A single statement can't be undecidable. Undecidability is a property of a class of statements.

For example, you can ask whether a Java program, run with infinite memory, will eventually halt. For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no". Might be hard to figure out which is the correct algorithm, but the Java program is fixed so the algorithm is definitely one of the two.

However, there is no algorithm which can take an arbitrary Java program as input and determine whether it will halt. It's about the class of all possible programs.

justinpombrio··on A software engineering interview question I like: computing the median
> That's average or mean. Median is the middle value.

The median of an even number of values is typically defined to be the mean of the two middle-most values.

justinpombrio··on Defeating Git Rigour Fatigue with Jujutsu
> it might be a week before i get back to it, and the name of the branch is a clue as to what the heck I was doing.

Ah, this is what the description (what git would call the commit message) is for. You can set the description even before you've made any changes.

justinpombrio··on Shunting-Yard Animation
Parsing is usually implemented in two steps: first there's lexing where the input is turned into a sequence of tokens, then there's proper parsing where the sequence of tokens is turned into an abstract syntax tree. This shunting yard algorithm is part of parsing. Lexing happens before that.

For example, this input:

    13- 2  *5 + 4
would be lexed into this sequence of tokens:

    "13" "-" "2" "*" "5" "+" "4"
You could use the shunting yard algorithm to put these in a convenient postfix order:

    "13" "2" "5" "*" "-" "4" "+"
It's really easy to then turn it into an abstract syntax tree (AST). Go through each token in order: if it's a number you make it into a node and push it onto a stack; if it's a binary operator you pop two nodes off the stack and make a node out of those and the binary operator. If you write down this AST as an s-expression you get:

    (+ (- 13 (* 2 5)) 4)
justinpombrio··on Shunting-Yard Animation
Yeah, it's a parsing algorithm for parsing infix (etc.) expressions. If you've seen a parsing library refer to "precedence climbing" or "operator precedence parsing", it's doing this (or something very similar).

If you want to enter the number `13`, that should be one token, but there's no way to make a `13` token in this UI. You need to stick to single digits for this site to work correctly.

justinpombrio··on Shunting-Yard Animation
It treated that as

    1 0 0 + 8 8 / 4
which is nonsensical, but it has no error detection so it rolled with it. Really `100` should be its own token, but there's no way to input that.
justinpombrio··on Microsoft is employing dark patterns to goad users into paying for storage?
Honestly I've had more technical problems installing Windows than Linux Mint recently, not to mention the multiple hours spent hunting down and disabling all of the telemetry and ads in Windows. Still can't believe they put ads in File Explorer.
justinpombrio··on 71% Desk Workers Say Screen-Related Visual Discomfort Is Reducing Productivity
This is a terrible source of information: it's talking about a survey about vision problems, by an eye care company, and you can't see the survey.

I'm completely sure that the way they worded the question the headline is about was very generously worded and that the phrasing in the headline misrepresents what it asked, because that's how these things work. Not that anyone is at fault, of course, the headline isn't a lie, and of course there are other reasons that the survey is hidden behind a subscription wall. It just so happens that the percent of people with screen-related visual discomfort according to the eye-care company survey is, I dunno, 2x higher than it would be if you asked the question directly. That's just how these things work.

(I suspect that someone is going to confuse this comment as me saying that eye-strain from screens isn't a problem for a lot of people. Pre-empting that by agreeing that, yes, of course eye-strain from screen is a problem for a lot of people.)

justinpombrio··on Memory access is O(N^[1/3])
Could you name one that seems likely to fail?
justinpombrio··on Why haven't local-first apps become popular?
I was going to say that that's not a CRDT because it requires a centralized server (the conflict resolution is "order in which the server received the messages", and clients aren't allowed to share updates with each other, they can only get updates from the server). But now I'm looking at definitions of CRDTs and it's not clear to me whether this is supposed to count or not.

Still, every algorithm that's actually labeled a CRDT shares a magical property: if my replica has some changes, and your replica has some changes, our replicas can share their changes with each other and each converge closer to the final state of the document, even if other people have been editing at the same time, and different subsets of their changes have been shared with you or I. That is, you can apply peoples' changes in any order and still get the same result. I don't think it's useful to call anything without that property a CRDT.

justinpombrio··on The Expression Problem and its solutions (2016)
Rust's traits _do_ solve the expression problem.

Each data type is a `struct`. Each operation is a trait. You `impl` each trait on each struct.

This works even if you're using a library that has declared `struct A` and `struct B` and `trait F` and `trait G`, and you want to add both a `struct C` and a `trait H`, and fill out the whole 3x3 grid without modifying the library.

The library says:

    struct A { ... }
    struct B { ... }

    trait F { ... }
    impl F for A { ... }
    impl F for B { ... }

    trait G { ... }
    impl G for A { ... }
    impl G for B { ... }

    fn some_function<T: F + G>(data: T) { ... }
Your code says:

    use library::{A, B, F, G};

    struct C { ... }
    impl F for C { ... }
    impl G for C { ... }

    trait H { ... }
    impl H for A { ... }
    impl H for B { ... }
    impl H for C { ... }

    fn another_function<T: F + G + H>(data: T);
Now `library::some_function()` can be called with an A, B, or C, even though C was defined by the user of the library. And `another_function()` can be called with A, B, or C, even though A was defined by the library.
justinpombrio··on Show HN: I made a tool to port tweets to Bluesky mantaining their original date
> (not an actual dictionary) Urban Dictionary

<troll> The definition of dictionary is just "Words about words" (source: Urban Dictionary), so I'd say that Urban Dictionary qualifies. </troll>

justinpombrio··on What can be computed? A practical guide to the theory of computation (2018) [pdf]
> by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system

Something that cannot be proven within which formal system? Every true statement can be proven by some formal system. No formal system can prove all true statements.

(This is all about Godel incompleteness. Turing incomputability does apply though, see the sibling comments! It's important to keep them separate, they're saying different things.)

justinpombrio··on What can be computed? A practical guide to the theory of computation (2018) [pdf]
Oof, I pattern matched OP to a different argument I've seen a lot. That's embarrassing.

Yes, that's correct, it's provably impossible to construct an LLM that, if you ask it "Will this program halt? <program>", answers correctly for all programs. Likewise humans, under the assumption that you can accurately simulate physics with a computer. (Note that QM isn't an obstacle, as you can emulate QM just fine with a classical computer with a mere exponential slowdown.)

justinpombrio··on What can be computed? A practical guide to the theory of computation (2018) [pdf]
Gödel's Incompleteness Theorem places a limit on what you can prove within a formal system. Neither humans nor LLMs are a formal system, so it says nothing about them.

Someone's going to think that, since you can formally model computer programs (and thus formally model how an LLMs runs), that means that Gödel's Incompleteness Theorem applies to computer programs and to LLMs. But that's irrelevant; being model-able doesn't make something a formal system!

"Formal system" has a very technical meaning: it has a set of consistent axioms, and the ability to enumerate formal proofs using those axioms. For example, Zermelo-Fraenkel set theory is a formal system [1]. It has nine formal axioms, which you can see listed in its Wikipedia article. Utterly different kind of thing than humans or LLMs. Comparing an LLM to ZFC is like comparing a particular watermelon to the number 4.

[1] https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...

justinpombrio··on Is this the simplest (and most surprising) sorting algorithm ever? (2021)
Can you give a reference to your teaching materials? The way this sort works is bizarre enough that I'm curious what you said about it. (Also to verify that this is actually the algorithm you taught, given how many other people thought it was something else.)
justinpombrio··on Is this the simplest (and most surprising) sorting algorithm ever? (2021)
Yeah, 2410 vs. 2509 swaps not including the first iteration. You should try measuring these things yourself, I'm not sure if it's doing what you think it's doing.
justinpombrio··on Is this the simplest (and most surprising) sorting algorithm ever? (2021)
> Why is there any difference? Does the entire difference come from the iteration where i = 1?

Sometimes it's more swaps, and sometimes it's less. The vague pattern looks like Can't Believe Sort does slightly fewer swaps on larger lists, but that could also have been noise.

Why do you expect them to have exactly the same number of swaps?

> Bubble sort can do less than this.

Oh sorry yeah, I implemented bubble sort without any sort of early return, for a more direct comparison.

justinpombrio··on Is this the simplest (and most surprising) sorting algorithm ever? (2021)
The number of swaps is nearly the same between Bubble Sort and Can't Believe Sort. For a random list with 100 elements, it's 2505 swaps vs. 2513 swaps.

The number of comparisons is of course about twice as large, because Bubble Sort always does exactly n(n-1)/2 comparisons while Can't Believe sort always does exactly n*n comparisons.

https://play.rust-lang.org/?version=stable&mode=debug&editio...

justinpombrio··on Is this the simplest (and most surprising) sorting algorithm ever? (2021)
I did search for "trivial sorting network", but the only networks that were called trivial were the ones for exactly two elements, while this algorithm sorts an arbitrary number of elements.

Could you link to what you're talking about? And what's its big-O runtime?

justinpombrio··on After 20 years, math couple solves major group theory problem
The paper: https://arxiv.org/abs/2410.20392
justinpombrio··on JJ Cheat Sheet
Yup, that's all correct. I drew `squash` and `backout` in terms of files in order to avoid needing notation for the opposite of an edit and the composition of two edits.
justinpombrio··on JJ Cheat Sheet
Yes, I think you understand perfectly. `abandon` was the diagram I struggled the most to draw.

I like the idea of putting the edits on the arrows, but there are a couple senses in which the edit is associated with the change itself rather than an edge between two changes:

1. A change with two parents starts out by merging them, and then it can make edits on top of that merge. If the edits go on an edge instead of on a node, which of the two edges do those changes belong on?

2. If you move a change (e.g. by rebasing it), its diff comes with it. I guess you could say that when you rebase, you're not moving just the node but also the edge from it to its parent?

Even so, diffs on edges feels very right. I may update that diagram.

EDIT: Updated!

justinpombrio··on JJ Cheat Sheet
This might be what you're looking for: https://jj-vcs.github.io/jj/latest/git-comparison/
justinpombrio··on JJ Cheat Sheet
Thanks for the kind word!

Unfortunately the arrows are kind of confusing regardless of which way they go. You're suggesting they point forward in time, from the old commit to the new commit. The way they're drawn is the direction of the reference: a commit points at its parent. The argument in favor of each way the arrows could go feel about equally strong to me, and my understanding is that the convention in repo diagrams is for arrows to go in the direction of the reference, so that's what I went with.

justinpombrio··on Tell HN: Cloudflare is blocking Pale Moon and other non-mainstream browsers
> Of course, I didn't, and decided to buy the product elsewhere

Consider messaging the owner to tell them you were trying to buy a product on their site and the site wouldn't let you. There's a chance that they'll care and be able to do something about it. But no chance if they don't know about the problem!

justinpombrio··on Jujutsu VCS: Introduction and patterns
> the default (which I've never messed with personally) essentially considers commits in tracked branches from remotes to be "immutable", meaning that anything purely local is "mutable"

The default for what's immutable is actually `main` together with untracked remote branches [1]. I agree that what you suggested should be the default though. You can change it by adding this line to your `jj` config:

  [revset-aliases]
  "immutable_heads()" = "builtin_immutable_heads() | remote_bookmarks()"
(To edit your jj config, run `jj config edit --user`.)

[1] https://jj-vcs.github.io/jj/latest/config/#set-of-immutable-...

Page 1 of 30Next →