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 A Lisp that runs Python (2016)
This article is about Hy, http://docs.hylang.org/en/stable/

"A Lisp that runs Python" is kind of vague. Hy describes itself as "a Lisp-flavored Python". I'd call it "a lisp that compiles to Python".

rntz··on On the Effect of Semantically Enriched Context Models on Software Modularization
I don't really understand what this abstract is saying. Can someone explain it for me?

Are they trying to apply NLP techniques to software source code? To what end?

rntz··on Nearly All Binary Searches and Mergesorts Are Broken (2006)
Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)
rntz··on Nearly All Binary Searches and Mergesorts Are Broken (2006)
Huh, is this the stuff you're talking about:

    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf
    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf
    https://www.youtube.com/watch?v=sz9ZlZIRDAg
    https://hackage.haskell.org/package/discrimination
I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.
rntz··on Nearly All Binary Searches and Mergesorts Are Broken (2006)
I'm tempted to suggest

    (low / 2) + (high / 2)
but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop worrying about overflow altogether.
rntz··on Nearly All Binary Searches and Mergesorts Are Broken (2006)
The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.
rntz··on Manipulate Functions with the J Language
To me the most interesting part of this article is the part that nobody else seems to be commenting on: the ability to automatically invert a function, even a programmer-defined function. That seems magical! What if I define a hash function? How can it possibly invert that? Clearly there's something interesting going on behind the scenes, and I wish the article discussed what it is, and how (and when) it works.

Everything else in the article seems like plain old functional programming to me, with a little syntax sugar here and there.

rntz··on What are covariance and contravariance?
It can mostly be done. The OCaml programming language does exactly this - it infers co/contravariance. However, when describing a generic interface which has as part of it a function on types (usually called a "type constructor"), you need to say whether that type constructor is supposed to be covariant, contravariant, or invariant.

For example, if I were describing a sequence interface, I would write

    module type SEQ =
    sig
      (* the "+" means that seq must be covariant *)
      type +'a seq 
      val empty : 'a seq
      val singleton : 'a -> 'a seq
      val append : 'a seq -> 'a seq -> 'a seq
      val lookup : int -> 'a seq -> 'a option
      exception IndexOutOfBounds
    end;;
See https://blogs.janestreet.com/a-and-a/ for a nice explanation.
rntz··on What are covariance and contravariance?
I use "just" to mean "exactly"; I say "X is just Y" to mean "X is exactly Y; when you have Y, you have X and vice-versa". I guess it might be kind of off-putting, because "just" implies the connection is boring or obvious, which is not what I mean to say.
rntz··on What are covariance and contravariance?
> In computer science a lot of the things we are interested in are already reflected in the partial order induced by a category (i.e., subtyping).

If by "the partial order induced by a category", you mean 'let A <= B iff Hom(A,B) is nonempty', then that's not subtyping. That's "does there exist a function from A to B". Just because I can write a function from Int to String doesn't mean Int is a subtype of String.

I tend to think of subtyping as an additional structure: a PL comes equipped with a particular notion of subtype. Say C is the category of types and functions. Then subtyping is a partial order on types equipped with an inclusion functor into C. That is, a map (coerce : (A <: B) -> Hom(A,B)) that chooses for any pair A,B of types such that A <: B a coercion function from A to B. Moreover, coercing from A to A must be the identity, and if A <: B <: C, then coercing from A to C is the same as coercing from A to B and then from B to C.

rntz··on What are covariance and contravariance?
> Wow, that's a new word, "posetal". Does that mean "can be partially ordered"?

Posetal means that Hom(A,B) has at most one element (the category is "thin"), and that any two isomorphic objects are equal (the category is "skeletal"; corresponds to antisymmetry). So the category can be seen as a poset, where (A <= B) iff Hom(A,B) is nonempty.

> What is "Int"? Integers? Integral? Int... ernal? ... types?

Integers. I was just picking an example type, as lmm says. I could have said: "Fix a type A, and consider f(B) = A -> B".

> What's with the notation, anyway? Why use "<:" instead of "<" like you would for any other transitive anti-symmetric relation?

Tradition. <= is also perfectly fine. Why do set theorists write \subseteq instead of \leq? \subseteq is also a reflexive, transitive, antisymmetric relation.

> "Anti-monotone" is weird language. I would say "monotone" in general and "increasing" or "decreasing" in particular.

Yeah, in analysis "monotonically increasing/decreasing" is more common. I find it more useful to explicitly draw out the fact that one is the reversal of the other; also "monotone" is more concise than "monotonically increasing". shrug

> What does any of this have to do with programming languages? I mean, types are purely abstract, right? Do they have to be part of a programming language? I thought types were merely sets ordered by inclusion.

Well, the OP was about types in programming languages. Types in PLs are not always best thought of as sets; for example, the equation

    a = (a -> Bool) -> Bool
has solutions in some type theories! Interpreted in the naive way, this would be a set equal to the powerset of its powerset, which is impossible. This conundrum leads to the study of Scott domains, for example.

> If programming languages are not something that can be abstracted away, what's a programming language in this context? A set (class?) of types and functions on those types?

I'm being deliberately vague on that front. How to define "programming language" is not something widely agreed upon. But similar patterns, such as co- and contra-variance, recur.

> What is a definable function? Are some functions not definable? Is it something like "there exists a Turing machine such that..."?

I just meant "any function you can write in the programming language you're considering". As robinhouston points out, not all functions will be definable, and "Turing-computability" is a bit vague when talking about functions that take other functions as arguments (since TMs operate on bitstrings, so how you encode functions becomes relevant). Constructive mathematics studies which things are still definable/provable if you insist on computability; "constructible" and "computable" usually mean the same thing.

> I don't know why computer people's category theory always looks so foreign to me. Sometimes I feel like we're in completely different worlds with vaguely similar-looking language. Category theory for me was mostly about homological algebra, but I don't think computer people care very much about the snake lemma or chasing elements across kernel and cokernel diagrams.

Yes. Category theory is a very general framework, and different bits of it become relevant depending on what you're studying. Although there are sometimes deep connections between unexpected regions, such as between computation and topology; I don't really understand that one myself.

rntz··on What are covariance and contravariance?
See my other comment about co/contravariance as monotonocity/antimonotonicity. Since monotonicity is just functoriality when your categories are posetal, covariance is a special case of functoriality.

More generally, you can see

   f(x) = Int -> x
   g(x) = x -> Int
as, respectively, co- and contra-variant endofunctors on the category whose objects are types and whose arrows are definable functions in your programming language. And they're both just special-cases of the internal hom functor,

   hom : C^op * C -> C
   hom(x,y) = x -> y
rntz··on What are covariance and contravariance?
Covariance and contravariance are just monotonicity and anti-monotonicity, applied to types ordered by subtyping.

That is: if we have a function on types, say, the function `f` defined by:

    f(x) = Int -> x
Then we say `f` is covariant because it is monotone: it preserves the subtype ordering on its argument. That is:

    if x <: y, then f(x) <: f(y)
Similarly, if we consider `f` defined by:

    f(x) = x -> Int
then this `f` is contravariant because it is anti-monotone: it reverses the subtype ordering on its argument. That is:

    if x <: y, then f(y) <: f(x)
People tend to find covariance more intuitive than contravariance; unless the issue is pointed out, they tend to assume everything is covariant. They see a type, say:

    dog -> dog
and they assume "oh, every dog is an animal, so I can put 'animal' in place of 'dog' and it'll be more general (i.e. a supertype)". This is false, as the article points out.
rntz··on The language of programming
Yes, but they are familiar - or at least, not entirely unfamiliar - to English speakers because English has inherited a lot of vocabulary from Latin. Other European languages have, too, so maybe names like "reify" or "transduce" might be somewhat approachable to a Portuguese speaker (although I wouldn't bet on it); but are they approachable to a Mandarin speaker?
rntz··on Where Do Type Systems Come From?
It seems to me Frege understood the need in mathematics to talk about many different kinds of thing - numbers, truth-values, functions, and so forth - and to distinguish which kind of thing you are talking about; but not the necessity to use types (or other methods) to avoid circularity. Indeed, it is precisely the mistake Frege made in his attempt to axiomatise logic and mathematics and which led to Russell's paradox, that motivated Russell (and Whitehead)'s theories of types.

Frege certainly articulated a clear notion of what a function is, which is significant.

rntz··on A Study That Bolsters the Lead-Crime Hypothesis
The article title on the original site was changed from "... Confirms the Lead-Crime Hypothesis" to "... Bolsters the Lead-Crime Hypothesis", since "It's a good study, but it's still just one more study." Title here should be changed likewise.
rntz··on Remaining Trouble Spots with Computational Thinking
Is there any reason not to teach children religious thinking? I would say there is no such reason. We should teach children many ways of thinking so that they can be versatile thinkers. I do not see how an argument beyond that point is needed.

Or, substitute for "religious" anything you dislike - "superstitious", "homeopathic", "racist", "left-wing", "right-wing". Or more fairly, as the article suggests, compare teaching "computational thinking" to teaching Latin. Clearly there is at least some reason you think "computational thinking" is worthwhile. What is it?

We cannot, after all, teach children everything. There is simply too much it is possible to learn.

rntz··on Why is Russia so good at encouraging women into tech?
If this were true - if needing a good job for a good life predicted going into STEM among women - you'd expect poor women in western countries to flock to STEM training as well. Do they?
rntz··on Why is Russia so good at encouraging women into tech?
> According to Unesco, 29% of women worldwide are in science research, compared with 41% in Russia. In the UK, about 4% of inventors are women, whereas the figure is 15% in Russia.

These numbers seem ludicrously high regardless of gender. I'd be surprised to hear that 29% - almost 3 of 10 - men were scientists. Is what they're actually saying that 29% of scientists are women worldwide, but in russia it's 41%? That would make more sense.

rntz··on The Utter Uselessness of Job Interviews
The trouble with this advice is that, while it's accurate if your one and only goal is to predict the likelihood of someone divorcing or cheating on you, it seems profoundly unfair.

To examine this "unfairness", let's imagine it at its most extreme: a society in which divorcees are so stigmatized that it's practically impossible to ever re-marry; in which children of divorcees are likewise stigmatized; in which victims of child-abuse are further victimized by a society that considers them potential "snakes-in-the-grass". Do we really want to live in such a society?

Obviously I don't think you were advocating this. But it's a thought experiment which demonstrates a classic class of problem: what's good for the individual isn't always good for society, especially taken to extremes.

rntz··on On the Impossibility of Supersized Machines
I'm familiar with Turing-equivalence, but the argument in that section didn't seem analogous to me. In the first place, it's about human universality, not computer universality; so an implicit premise of the "parodied argument" would have to be something like "human intelligence is Turing-complete" - I've seen no argument against machine superintelligence that starts from this premise (although not all arguments depend on rejecting it, either).
rntz··on On the Impossibility of Supersized Machines
Summary: This is a parody of various arguments about superintelligent AI.

It opens by parodying the classic futurist parable of history as exponential growth in intellect and technology, recasting history as a tale of growth in size (after all, the earliest organisms were tiny). It recasts fears about superintelligent AI as fears about super-large beings (wouldn't you be afraid of something that could step on you as easily as you step on an ant?).

Then it switches to parodying some arguments against the possibility of superintelligence, in order:

1. That intelligence is "irreducibly complex"; since we don't understand what makes people smart, we can't expect to make smarter machines. This, to me, is the weakest of the parodies in the article. We definitely understand size better than intelligence, and lack of fundamental understanding has absolutely impeded our ability to engineer things in the past. To get to the Moon, we had to understand gravitation at a much deeper level than "things fall down", or even than "things fall in parabolas". That said, total understanding of natural phenomena is not always necessary to replicate them: the Wright brothers didn't need to understood how exactly bird flight worked to build the first plane.

2. That intelligence is poorly defined ("human-level" AI is "meaningless"). "Largeness" is similarly vague, but an Airbus is still obviously bigger than a human. Vague goals can still be met.

3. That human intelligence is in some way "universal". I don't understand this argument enough to explain the parody. Can someone else chime in?

4. Psychological arguments against superintelligence, which says that the origin of belief-in and fear-of superintelligent machines is really evolutionary, not logical. This is a classic non-sequitur; if evolution predisposes humans to be afraid of wolves, it does not follow that humans have no reason to be afraid of wolves.

5. That the goal of AI research is to augment human intelligence, not supplant it. Another non-sequitur.

6. Arguments from the hard problem of consciousness, and philosophical questions like "can a machine ever be conscious?". Yet another non sequitur: even if you think a machine fundamentally can't be conscious, it doesn't follow that it can't be functionally superintelligent.

7. Bullshit arguments involving quantum mechanics, Godelian incompleteness, and other things with pop-cultural cachet that most people who invoke them don't have the technical chops to understand.

rntz··on Republicans didn’t just strip away Internet privacy rights
The original title is clearer: "No, Republicans didn't just strip away your Internet privacy rights".

The leading "No," makes it clear that it's denying that Republicans took away rights; without it, the "just" suggests it's saying Republicans did more than "just" take away privacy rights.

The underlying problem is, of course, the English language. "just" can mean either "immediately prior" (just now) or "merely" (just a friend).

rntz··on The Case for More Intellectual Humility
To me that sounds almost hypocritical. You should be uncertain of your beliefs, but act like you're not? What am I missing?
rntz··on The New ‘Absent Operator’ in Ruby’s Regular Expressions
Huh! Now I am super confused.
rntz··on Ask HN: A question for those who went to MIT/Stanford/CMU
CMU grad here, working on a PhD.

First, don't put too much emphasis on school. Great programmers can come from anywhere.

Many other commenters are emphasizing the role of selection effect: top-tier schools select good students, rather than teaching well. I think the effect of good teaching shouldn't be undervalued. Although, again, good teachers and courses can come from anywhere, here are some things CMU does or did in the way of pedagogy:

1. Focus on concepts and skills, not specific technologies. Many of CMU's intro courses are taught in Standard ML, a language used by basically nobody. This levels the playing field, forcing people who think they already know everything to learn things from a different perspective. It puts the focus on how to design and reason about programs, rather than the minutiae of popular languages.

2. Have project-based courses. The star example here is CMU's operating systems course, which is a thing of beauty and terror. At many schools OS courses teach you trivia about hardware. CMU's OS course involves some of that, but is mostly about (a) working with a partner (b) time management (c) designing concurrent programs. The compilers course is of similar quality.

3. Teach math-as-problem-solving. CMU has a course, 15-251, which is notoriously difficult, because it introduces you to a lot of discrete math very quickly. This is partly because discrete math is the core of CS theory; most programs will never need this, but when you do need it, knowing a bit of theory can save you days or months. But the other goal is to simply practice solving difficult conceptual problems.

rntz··on Ask HN: A question for those who went to MIT/Stanford/CMU
CMU grad here, currently working on a PhD. All I can say is, this description doesn't apply to me. I'm definitely of the "work smart, not hard" persuasion. Persistence, I guess I have; but not an unbounded work ethic, or the focus to work on ten things at a time. Persistence for me means finding a new way to attack a problem, not pushing as hard as possible, John Henry style.
rntz··on The New ‘Absent Operator’ in Ruby’s Regular Expressions

    (?=((?!exp).)*a.*)
is also wrong; it doesn't match "expba", but

    (?~exp)a.*
does.
rntz··on The New ‘Absent Operator’ in Ruby’s Regular Expressions
This isn't about negative lookaheads or lookbehinds. It's about negation proper. It is perfectly declarative: the language matched by (?~E) is the complement of the language matched by E.
rntz··on The New ‘Absent Operator’ in Ruby’s Regular Expressions
You propose:

    (?=((?!exp).)*$)
I don't believe you're right, but can't be sure, because you haven't given a method of translating an arbitrary regular expression containing a negation (?~E) into one without.

For example, how would you translate:

    (?~exp)a.*
which asks for "anything not exp, then an `a`, then anything"?

    (?=((?!exp).)*$).*a.*
is wrong, since it doesn't match "aexp".

    (?=((?!exp).)*$)a.*
is also wrong, for the same reason.

    (?=((?!exp).)*a)a.*
is wrong, because it doesn't match "expba".

EDIT: argh, HN formatting rules about asterisks.

← PreviousPage 4 of 15Next →