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 Very Long Proofs
Many folks would say that's not a proof, because it's not efficiently checkable. To tell whether it actually proves the thing, I have to go off and check every number, which takes an enormous amount of time compared to the length of the "proof".

Of course, the solution of listing every single case seems about equally unhelpful. The whole thing leads one to question whether proofs are really the goal of mathematics, or just a useful proxy.

rntz··on Very Long Proofs
That isn't a proof, it's a procedure for finding a proof. The procedure might fail, and whether it will fail or not cannot be checked without running it - which is not guaranteed to halt! Of course, to guarantee that it halts, you could include an upper bound on the size of the proofs it searches in your program. So then at least your "proof" is checkable. However, it is not in general efficiently checkable - that is, checkable in polynomial time. If it were, it could only produce polynomial compression!

(Though admittedly, polynomial compression is pretty good, practically speaking.)

As for Kolmogorov complexity, there are infinitely many distinct proofs, so their Kolmogorov complexity cannot possibly be bounded.

rntz··on Critical Behavior from Deep Dynamics: A Hidden Dimension in Natural Language
I think that means only that programs written in a language described by a CFG could exhibit "criticality", not that they will. "Exhibiting criticality" is a property of a distribution (e.g. a corpus of human-written programs or an algorithm for generating programs), not of a grammar, IIUC.
rntz··on Extra Mass on Bike Wheels Is Worse than on Frames
To get a constant horizontal speed, a small-radius wheel must turn faster than a large-radius wheel. For a constant turn rate & rim mass, a small-radius wheel will have less energy than a large-radius one. I suspect (given the article's statement doesn't depend on the wheel radius) that these precisely cancel, but I haven't done the math to prove it.
rntz··on A 32nm 1000-Processor Array
Arguably the first 1000-processor chip was the CM-1, made in the 1980's: https://en.wikipedia.org/wiki/Connection_Machine

They also bury the lede somewhat. Apparently the KiloCore is a 1.78 Terahertz chip:

> The energy-efficient “KiloCore” chip has a maximum computation rate of 1.78 trillion instructions per second

Edit: they later say it's 1.78 GHz. I guess "trillion" is just a mistake?

rntz··on “Safe C++ Subset” Is Vapourware
Godel's completeness theorem applies to first-order predicate logic, which is not powerful enough on its own even to express, let alone prove, 1+1=2. First order logic is best thought of as a framework on which other, useful logics may be built. And as soon as you add enough power to first-order-logic to capture Peano arithmetic, you run into incompleteness.

C++ behavior is almost certainly more complex than Peano arithmetic.

rntz··on What If PTSD Is More Physical Than Psychological? Evidence from new study
If a permanent change in your psychology did not correspond with some permanent change in your physical person, then what would there be that was causing the change in your psychology? Some non-physical "soul" or "mind"?

All psychological facts have physical correlates (in philosophy of mind, this is called "supervenience"). The only limit is our ability to measure things. As our ability to measure our own brains and bodies increases, we should expect to uncover more and more physical correlates of psychological conditions.

rntz··on What If PTSD Is More Physical Than Psychological? Evidence from new study
Although this is true, learning that there is a specific physical sign in the brains of those who have suffered blasts at close range, and that this sign is not present in those who have suffered other forms of stress, is a significant breakthrough!

The article presents this as an issue of physical vs. psychological, but even stripped of that misconception it's still an interesting article.

rntz··on Java Generics Are Turing Complete
What it means in practice is that any Java typechecker is either (a) incomplete - it will disallow some programs that should typecheck; (b) unsound - it will allow some programs that shouldn't typecheck; or (c) non-total - it will fail to terminate on some programs. (Or some combination of these three.)
rntz··on Related: Pure Ruby Relational Algebra Engine
Natural joins only require equality testing. General unification is stronger. Prolog can unify [X,3|T] with [2,Y,4,5] to find X = 2, Y = 3, T = [4,5], for example.
rntz··on Related: Pure Ruby Relational Algebra Engine
Prolog allows unification, which doesn't have a parallel in relational algebra. I'm not sure how much more power this gives you without recursion, though.

If you're interested in connections between relational algebra (and SQL, and databases) and logic programming, you should look at Datalog, which is a restricted subset of Prolog that is akin to relational algebra plus fixed points (transitive closure, for example). In particular, Datalog forbids compound terms (like lists) and recursion in a negated position.

I think Datalog without recursion/fixed-points is precisely as powerful as relational algebra, but I don't have a proof handy.

rntz··on A Path to Programming Language Theory
It's basically a certain kind of documentation of design patterns in programming languages. PLT emphasizes the use of formal logic and mathematics. It focuses on systems that can be rigorously defined, and theorems that can be proven about them; as opposed to software engineering, which focuses on the issues and patterns that crop up in the practice of developing software, or HCI, which focuses on human factors.

Of course, all of these are overly broad generalizations, and it's not as if there aren't points of intersection between these different ways of looking at programming languages.

But the kind of stuff you'll see in a book like Types and Programming Languages is super-different in approach from the kind of stuff you'd see in, say, the Gang of Four book, both of which are different again from Bret Victor's approach.

rntz··on Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
Ah, good point! I was thinking of unsigned overflow, but signed overflow is a different matter, as pointed out elsewhere in this thread. I retract my statement about trapping overflow.
rntz··on Show HN: Optimizing Higher Order Functions with Hypothetical Inverses
> And over integers too, in the presence of overflows (in junk languages without bignums)

I don't think this is true. Modular addition is commutative and associative. As long as the behavior of overflow is modular (as it is in 2's complement), order shouldn't matter. And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. I guess if you care about the stack trace you get being the same even under optimizations, then you could argue this isn't a safe optimization. And if the behavior of overflow is undefined, it's undefined whether you reverse the list or not.

Maybe you're thinking of Javascript, which not only doesn't have bignums, but uses floating point even for integers?

rntz··on How do people justify earning more than others?
Goddamit, I downvoted you when I meant to upvote. Sorry.
rntz··on Chez Scheme is now free
Chez is known for being very fast, and for using state-of-the-art compiler technology.
rntz··on I Don't Want to Hire You If You Can't Reverse a Binary Tree
> If you hire using know it or not questions about binary trees

The article author doesn't think of his question as a "know it or not" question, but a "you should be able to figure this out" question:

> Here's the first reason why this question is so good: a skilled programmer can map their intuition to code. You can tell at a glance whether a binary tree is symmetric, but beginners will often struggle with a question like this because they approach this problem from a visual/intuitive angle rather than the logical angle.

I think it's a fair criticism to say that, at this point, "reverse a binary tree" is something a lot of applicants will have simply memorized rather than figuring out on the fly. But (to play Devil's Advocate) isn't the goal of the question - to test a candidate's ability to think logically and problem-solve on the fly - a reasonable one?

It seems to me the real problems with whiteboard-coding interviews aren't that what they're trying to test - problem-solving on the fly - isn't useful or valuable, but that whiteboard coding is confounded by so many irrelevant variables: ability to think under pressure, ability to code "in your head" (without an editor, IDE or REPL), memorizing solutions, and so forth.

rntz··on How Animals Think
> The article seems to push the idea that we think less of animals and that should change, but I don't think it's clear that the motive behind us humans pulverizing the animal kingdom is because we think we're superior to them.

The article doesn't put forward the idea that we should think more of animals for their sake; it's just saying that our understanding is factually incorrect.

rntz··on The Arctic Suicides: It's Not the Dark That Kills You
From the article:

> Like native people all around the Arctic — and all over the world — Greenlanders were seeing the deadly effects of rapid modernization and unprecedented cultural interference. [...] Between 1970 and 1980, the suicide rate there quadrupled to about seven times the U.S. rate (it's still about six times higher).

> Her observations are in line with something psychologists and sociologists think is fundamental to the causes of suicide in Greenland. When communities are disrupted, like Kangeq was, families start to collapse. There's an increase in alcoholism, child neglect and physical abuse, all of which are risk factors for suicide. Later, people who didn't get the love and support they needed as children find it difficult to cope with the routine heartbreak of dating, and a breakup becomes the final insult in a lifetime of hurt.

rntz··on Why does Haskell, in your opinion, suck?
> And I don't even know how to google any one of them. Don't know how to solve this for myself.

https://www.haskell.org/hoogle/ lets you search for functions by name, including symbol-named functions like <$> and co.

(You can also search for functions by type, which is a pretty cool feature, but not what you were asking for.)

rntz··on Time Machines
> I think it would be fair to flip that around: if your philosophy doesn't result in testable predictions, then what's the point?

"Untestable philosophies are pointless" is an untestable philosophy, and therefore pointless by its own standards. This is a well-known problem with logical positivism, which is roughly the position you are advocating.

rntz··on Rust via its Core Values
> That is, suppose I have something that, semantically, I want to move into a function, and which the function later returns. I think I could also pass a `& mut` instead.

That is exactly what `&mut` is for. An &mut gives you an "ownership lease" on an object; you own it as long as you have the &mut.

rntz··on Rust via its Core Values
> I'm guessing aside form a dangling pointer GC doesn't offer much protection form a segfault?

Correct. By using GC and banning free() you avoid use-after-free bugs, but not out-of-bounds accesses.

Out of bounds accesses have to be forbidden in some other fashion; most languages do bounds-checking and throw an exception rather than trying to access the memory and getting a segfault (or, worse, reading some random other object's memory).

rntz··on Rust via its Core Values
Decidability actually is optional; some folks experimenting with dependent type systems are bullish on giving up decidability (allowing type checking to fail to terminate in some cases). Typechecking is already 2^(2^PROGSIZE) for, say, ML. That could easily - in theory - lead to impracticably long compilation times. Yet in practice, it doesn't. So why not go whole hog?
rntz··on Rust via its Core Values
The best possible a language can be for a given situation is that the empty program solves the problem you're trying to solve.

Obviously, in no language can the empty program solve all problems. QED, there is no language that is optimal in all situations.

If you want a more useful answer, you should define what you mean by "best in all situations".

rntz··on Magic is often used to describe confusing code
There is no magic other than the unfamiliar. The problem is not magic or the unfamiliar, it is complexity.

A technique can be understood, and still a pain in the ass to use; then it is bad. This is of course subjective, by comparison with other ways of solving the same problem.

Or, a technique can be useful, but too difficult to learn to justify using it on something simple; then it is inappropriate, and should be replaced by simpler, presumably less concise, code. This is of course subjective, dependent on the code's audience (readers, reviewers, maintainers). This is the root of the article's map vs for-loop example: different levels of familiarity with the technique of mapping functions over something.

rntz··on Computer programmers have the largest gender pay gap
> Women who write the software that runs on mainframe computers earn on average 72 cents per dollar earned by their male counterparts, according to research conducted by Glassdoor Inc., the online job information firm.

Do they really mean mainframe computers? If so, that is a tiny and unrepresentative portion of all computer programming. If not, it's a hell of a typo.

rntz··on Extensional Higher Order Prolog
I've just published a draft paper on an entirely different approach to the same problem: instead of creating a higher-order Prolog, we've discovered a functional (and so higher-order) analogue of Datalog, a more limited language (http://www.rntz.net/files/datafun.pdf, on github at https://www.github.com/rntz/datafun)

This idea of a higher-order Prolog is very interesting! But it's not clear to me how it can be truly extensional without further limiting the language. For there is another reason why Prolog is not extensional: non-termination. As a simple example, consider this program:

    q(X) :- q(X).
    q(adam).
    p(adam).
`p` and `q` are logically equivalent (the line `q(X) :- q(X).` is a no-op; of course a predicate implies itself). But in Prolog, `q` is a useless, nonterminating predicate. This problem is not a simple quirk: provability in even first-order Horn logic is undecidable if you augment it with compound terms & unification (as Prolog does), so there is no general algorithm for deciding Prolog queries.

It looks like extensional higher-order prolog should have the same problem. The article doesn't address it, so I'll go read the papers.

EDIT: The relevant research papers on Higher-Order Prolog, if anybody is interested: http://arxiv.org/abs/1106.3457 "Extensional Higher-Order Logic Programming"; http://arxiv.org/abs/1405.3792 in which they extend it to negation; https://github.com/acharal/hopes the implementation's github repo

rntz··on We only hire the trendiest
> I think my choice of the term "poker face" was a bad way of describing a certain kind of evasiveness which can indicate bad motives or bad people skills, either of which can make the person a bad hire.

As a practical matter, how do you detect this kind of "evasiveness", and differentiate it from (say) plain old introversion or nervousness?

rntz··on We only hire the trendiest
A big long list of relevant but subjective traits is a perfect vector for bias to creep in. Take what you call "poker face", for example - how do you measure openness? By how well they make small talk? What if they're just nervous because of the interview; what if they experience social anxiety; or what if they're just an introvert, and don't tend to be open around new people?

For a less trivial example, take "resourcefulness". To a large extent, resourcefulness is determined by access to resources. Continued learning after college takes more than curiosity: it takes a bunch of free time to burn on reading, hacking, debugging, etc. What if the interviewee has been spending their time outside of work raising a family instead?

← PreviousPage 7 of 15Next →