HNHacker News
TopNewBestAskShowJobs

rntz

2,169 karma · joined May 25, 2009

www.rntz.net email: http://www.google.com/recaptcha/mailhide/d?k=018XOhLYKe9NqLdmoSmt6HsQ==&c=mcxnT-9mQPQEL6wailXqNUHk3aPs4Jv1T3vTJsNNAkg=
submissionscomments
rntz··on The New ‘Absent Operator’ in Ruby’s Regular Expressions
It isn't quite that easy to emulate lookahead using intersection (AND). For (?=a)b you're right, but that's because `a` and `b` both only ever match strings of length one. `(?=foo)f`, for example, will match the first character of the string "foobar". But `foo&f` is the empty language: no string is both "foo" and "f"; they have different lengths!

The trouble with lookahead and lookbehind is that they aren't even describable in terms of the "language" which the regular expression corresponds to; rather, they modify how the pattern matches in the context of an overall string. So they don't quite use the same formalism as intersection, union, and negation of regular languages.

rntz··on The New ‘Absent Operator’ in Ruby’s Regular Expressions
The negation (complement) of a regular language is always regular. So in the CS theory sense, these are still regular expressions. However, while regular languages correspond to finite automata, the transformation which negates a NFA is not very easy to describe, which is one reason regular expression matching libraries have rarely included negation proper as an operation. Implementing negation proper using backtracking is somewhat easier, but quite expensive if done naively.
rntz··on Announcing the first SHA-1 collision
EDIT: My original comment was wrong. Git commit signing apparently only signs the commit hash itself, so it's only as trustworthy as the integrity of the hash. However, see also other comments which point out that this isn't a pre-image attack; you can't find a collision for a given thing (in this case, the linux kernel); rather, you can generate from scratch two pieces of data which happen to collide. Still, this is worrying.

ORIGINALLY (INCORRECT): Git commit hashes were at least never intended as a form of authentication. That's why git has commit signing. That said, they list GPG signatures as one of the things affected by SHA1 brokenness, so maybe even that's not enough? I don't know enough about how git commit signing or GPG works to tell.

rntz··on Harvey Friedman bringing incompleteness and infinity out of quarantine
The "there is at least one class which.." doesn't mean "there is at least one class in that class of mutually exclusive classes which..."; it means "there exists at least one class at all which...". This is one way of phrasing the axiom of choice (although Russell uses "class" instead of "set"; in modern-day usage, we distinguish classes from sets, and AC applies to sets only).
rntz··on Ruby `reject!`
In a multithreaded context, even that isn't perfect; another thread can observe the array in an inconsistent state while you're mutating it. I wonder what Ruby does here?
rntz··on Grammar isn't merely part of language (2016)
I do not work on NLP, but my understanding was that, for purely syntactic work, standard parse-tree-based techniques had been quite successful in NLP; and that it is only for semantic work that symbolic representations begin to show weaknesses. Since we often care about the meanings of words, this is a pretty strong limitation; still, it suggests that standard grammar-and-parse-tree approaches do capture something significant about how human languages work.

Is this inaccurate?

rntz··on There Are Three Programming Paradigms (2013)
Compilation and interpretation are also implementation strategy issues, unrelated to programming paradigms. Almost any language can be implemented using either strategy, and most systems we think of as "interpreted" in reality employ a mixture of the two strategies.

I don't know what you mean when you say they are also spatial and temporal in nature. You are being extremely glib, and I don't really understand what points you are trying to make.

rntz··on Show HN: A self-hosted js compiler in 1k loc
The immediate question I had was: "compiles JS to what"?

Apparently the answer is: to Javascript. It's what some call a transpiler: it compiles Javascript plus some extra features down to a more "vanilla" Javascript (es5?). I tend to dislike the term transpiler (transpilers are just compilers that target high-level languages), but I guess in this case the term would have helped me understand what was meant!

rntz··on There Are Three Programming Paradigms (2013)
This is about implementation strategies, which I think are a lower-level idea than paradigms. Datalog is a logic language that can be implemented without using backtracking/"search", for example.
rntz··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
What does it mean to say that analog and digital computers have the same computational power? My intuition would be something like: for any function calculable by an analog computer, for any desired degree of precision, there is a Turing-computable function which approximates it to that degree of precision. But you have to be a bit finnicky, since you can't actually feed an analogue input to a digital computer, either. So it has to be some relation between the precision of the input and the precision of the output. And of course there's the other direction, that analogue computers can simulate digital ones.

Do you know whether anything like this been formalized and proven?

rntz··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
That is not what programs as proofs means. It is not that the program finds or performs the proof; the program is the proof, in a certain formal sense. The thing it proves is its type. The validation step is type-checking. For most programming languages, type-checking is decidable, so testing whether the proof is valid is fine. However, most programming languages correspond to trivial proof systems (every type is inhabitable, so every proposition is provable).

This is part of the problem with proofs-as-programs: it's a beautiful theory, and inspires a lot of useful work, but if taken too literally it's wrong and useless.

rntz··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
(nitpick) Are metabolic systems and neuron networks really discrete (as opposed to analog) systems?
rntz··on Proofs are Programs – 19th Century Logic and 21st Century Computing (2000) [pdf]
There are accounts of infinitely-running programs as proofs; they have to do with the proof technique of conduction, which has to do with proving properties of infinite data structures; a counterpart of the more familiar technique of induction, which lets you prove things about finite data structures.

Side effects are a little harder to see proof-theoretically; for some effects there are reasonable stories (exceptions, for example, are a special case of continuations, which have connections to classical logic), but for many I think the story is still murky.

The Curry-Howard correspondence is more of a lens through which to approach PL theory, or an evolving research agenda, than it is a settled account of all programming practice.

rntz··on The struggle with Rust
Okay, then I can pick another example: A dictionary where the type of the values depends on the key they're inserted under. (For example, a representation of the closure of a function in a typed language.) Of course, then I can go to a dependently typed language, but are you really going to tell me that only dependently typed languages count as "good" static type systems?
rntz··on The struggle with Rust
EDIT: I've been chewing over the following:

> This means that we can trivially translate a dynamically typed program into a statically typed program, though obviously we don't gain anything by that at this point (this is essentially an argument that Bob Harper has advanced before) and we pay for it in additional verbosity.

This is exactly the opposite of the argument I advance below; you're claiming that there is a "local" translation from dynamic to static. And on reflection, you might be right, but I'm not entirely sure. It hinges on exactly what counts as "local". Translating away exceptions, for example, requires inserting case-analyses which propagate an exception if one has been thrown literally everywhere in your program. It's "global" in the sense that it touches every node in the program; it's "local" in the sense that the transformations performed don't involve any global knowledge or analysis. I'm rereading Felleisen's paper now to see how precisely he defines things.

ORIGINAL:

> I had Matthias Felleisen's characterization of expressiveness [1] in mind (incidentally, he's also one of Racket's authors).

Great! I believe, by that definition, your assertion that "good" typesystems don't reduce expressiveness is false, at least for common type systems such as Haskell's, Java's, ML's, etc. There are plenty of programs which require non-local rewriting ("a global reorganization of the entire program") in order to appease the typechecker.

A simple example can be adapted from the expression problem: suppose I'm writing an compiler for a simple language, so I have an AST datatype and some functions on it. Then I add a pass to my compiler that removes a certain feature from the language I'm implementing - a certain branch of the AST. Now I wish to simplify my backend by removing the case which handles this branch of the AST. I cannot do that without either dynamically failing in that case (which a type system might even prevent me from doing) or introducing an entirely new AST type which does not have that branch - but this could require duplicating or else considerably generalizing existing code that operates on the AST (a global reorganization). Of course, a sufficiently powerful typesystem might let me do that, but for any typesystem you name, I suspect a similar example can be procured.

To get more precise, the "feature" we're considering adding is "ignoring the typechecker and running anyway". For example, GHC's -fdefer-type-errors. The question is "can any legitimate program written with -fdefer-type-errors be locally translated into an equivalent program that typechecks without -fdefer-type-errors". Without reaching for an explicit escape hatch like unsafeCoerce (which is analogous to "unsafe" blocks in Rust), I think the answer is no.

rntz··on The struggle with Rust
> The difference compared to a (good) static type system is that a good [1] static type system does not measurably reduce expressiveness

This is pseudo-jargon. What counts as a "measurable" reduction? Do you have any substantive evidence that "good" typesystems don't reduce it? And why are only type systems which satisfy this property "good"? You talk cogently about tradeoffs later on, but this sentence taken literally suggests only a type system which doesn't make this particular tradeoff can be "good". Why?

My go-to languages for the past few years have been Haskell and Racket. There have definitely been times I picked Racket because I knew Haskell's type system would interfere with my expressiveness. Certainly Haskell is less restrictive than Rust with regards to ownership, but all type systems restrict you. I think GP is spot-on in pointing out that you just get used to it over time as you learn to think and code in ways that avoid pushing against the type-system's weak spots.

> But where garbage collection is an option, the tradeoffs that Rust makes become much less attractive.

Yes, precisely. It's not a fundamentally different issue from getting used to other static type-systems; it's just a different tradeoff.

rntz··on The Sound of Silence
> That was absolutely not what I intended to say with this admittedly tongue-in-cheek quip.

Thank you for clarifying.

> There is a kernel of (subjective) truth in there though: if you find yourself agreeing with one side of a meme war 100% on everything, it's most likely time to rethink some assumptions.

Yes. But "you're probably wrong if you agree with anyone completely" and "you're probably right if you disagree with most people" are very different.

> > Group identity and culture wars are not new (and are certainly not going away).

> I thought I addressed that.

I think here it's me who has been unclear. That was just an introductory remark. The substance of that part of my comment was to wonder whether the internet is really what's been exacerbating the current culture wars and factionalism, or if it's just coincidental. I still don't feel confident either way on that question.

rntz··on The Sound of Silence
In this context, it just means "very strong". The idea is that biased investors have a lot of leverage, despite being a minority, because of the environment they're in. So yes, it's that their behavior is driving everyone else's.
rntz··on Rust vs. Go
GP meant to say GGP is arguing against emotions, not arguing using emotions. He's accusing GGP's detractors of emotionality, not GGP.
rntz··on What Happens to OO When Processors Are Free? (2015)
Message-oriented no-shared-state approaches (whether you call it Actors, objects, CSP, session types, or whatever) to concurrency have proved much easier to write correct software in than the traditional threads, locks, and shared memory approach. And it's the message-oriented approach that the article proposes basing the hardware design on.
rntz··on Rust and the limits of swarm design
In the end, it doesn't matter who it's "fair" to assign responsibility to; a language you can't rely on is a language you can't rely on. All esr is pointing out is that there's a problem. Personally I think the Rust folks are pretty aware of this problem, and are managing just fine; Rust is definitely still in the early stages of language community growth, and locking things down too much would be a mistake.
rntz··on The Sound of Silence
This is true. It does seem, however, like that is the short-term trend of the last decade or three. Things don't have to be as bad as the mid 20th century to be worrying.
rntz··on The Sound of Silence
> As a rule of thumb: if both parties are angry at you, you're on the right track.

No; this is an excuse to pat yourself on the back for being contrary. Don't validate your beliefs by how much they make others angry, any more than you validate them by how much they make others happy.

> the group identity thing

Group identity and culture wars are not new (and are certainly not going away). It's plausible to me that the internet is making this worse - a premise of your post - but I'm not yet convinced. It's possible they're merely coincident. What concrete reasons are there to believe the internet is a primary cause of today's increasingly vitriolic culture wars, rather than merely a new venue in which they are being pursued?

rntz··on Vivaldi – A Browser for Our Friends
GP: and the response from the devs is simply to grumble that old-school Opera was best and all other browsers today have bad defaults

P: It's the wrong default behaviors

You're talking past each other.

rntz··on The Real Name Fallacy
Perhaps the common cause here was disqus, rather than anonymity per se? Does anyone know if there any features of disqus that might encourage trolling?

Also, I've certainly seen plenty of flaming in FB comments on news sites.

rntz··on Ask HN: Who wants to be hired? (January 2017)
Location: Oxford, UK

Remote: Yes

Willing to relocate: Yes (NB. I am both a US & a UK citizen, so no visa issues w/ moving to US.)

Technologies: I design, implement, and improve programming languages. Do you have a problem that could benefit from its own programming language? Are you using a language that you wish had some feature, but doesn't? Talk to me. Systems programming (kernels, GCs, JIT compilers) is another interest of mine.

Resume/CV: http://www.rntz.net/resume.html

Email: (click link to get email) http://www.google.com/recaptcha/mailhide/d?k=018XOhLYKe9NqLd...

rntz··on Ask HN: Who is hiring? (January 2017)
Exempting fresh-out-of college students from requirements that apply to others seems like straight-up bullshit to me. Either those requirements are flexible, or they aren't.
rntz··on Neurodiversity
Is there any evidence that they have different underlying causes or are otherwise fundamentally distinct rather than one simply being an extreme case of the other? (Honest question; I'm not familiar with the literature here.)

Or, even if they were in some sense fundamentally the same, is your argument that their effects are so practically different that they ought to be called by distinct names anyway?

rntz··on Neurodiversity
This isn't as inconsistent as it seems. People would probably also be equally uncomfortable with both the idea of "editing" an embryo's genome to make it light-skinned, and the inverse idea of editing it to make it dark-skinned.
rntz··on Musical Chord Progression Arpeggiator
A melodic minor lacks C major, and instead has C augmented.
← PreviousPage 5 of 15Next →