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 Prolog Story (2010)
I would like to know what Prolog implementation the author used. In particular, the article claims:

1. > An initial analysis found that we would need to implement a complex depth/breadth search algorithm either in the client application or in SQL.

2. The Prolog runtime would efficiently solve this problem given rules that naively described it.

I am skeptical, as this is emphatically not my experience with Prolog. In my experience, for any problem requiring a complex search strategy, Prolog is not your friend. Most Prologs do something approximating a naive depth-first search with unification, and on complex search problems this approach rapidly blows up. This can _sometimes_ be fixed by:

1. Making careful use of cut (`!`) or other non-declarative operators to change the search order.

2. Using tabling, essentially an advanced form of memoization. But only some Prologs support tabling, and it's useful only for some sorts of problem.

However, the author mentions none of these. Are they glossing over something, or is my (probably more limited) Prolog experience uncharacteristic? Are there "smart" Prologs out there I'm unaware of?

rntz··on K-map, the weird cousin of k-anonymity (2017)
The article gives the hypothetical example of redacting a table row

  {zip: 85535, age: 79}
to

  {zip: 85xxx, age: 79}
on the grounds that there are fewer than k (for some tunable constant k, larger = more anonymity) 79-year-olds in zip code 85535, but many more in zip 85xxx. However. If I see the second record, because it has been redacted, I also know that whatever zip code the person actually had, there were fewer than k 79-year olds in it! This may narrow the set of candidates considerably.

So it doesn't seem sufficient to count the mere number of people a redacted row could possibly match. You have to consider the meta-level information that knowing the row had to be redacted gives the attacker.

rntz··on The algebra and calculus of algebraic data types
This algebraic approach to program semantics is basically how categorical semantics works. The syntactic equational theory of the simply typed lambda calculus with pairs, for example, is that of the "free" cartesian closed category. It can be mapped (in a way that respects the cartesian closed structure) into any cartesian closed category, giving you a semantics.

A monoid can be seen as a one-object category (the monoid elements are the morphisms on that object, and the monoid operator is morphism composition), so perhaps concatenative languages have categorical semantics too. (Although it seems like the semantics of "quote", or whatever [ foo bar baz ] is in forth, might make things a little interesting - ie. require more structure than a monoid homomorphism. I expect you really want cartesian closed categories, and quote is probably curry or apply.)

rntz··on The Chinese were solving 14th degree polynomials in 1303. Why?
The Halting Number. The i'th digit after the decimal point of the Halting Number is 0 if the i'th Turing Machine halts given an empty tape, and 1 otherwise. (The integral part of the Halting Number is 0.)

This number is not computable; if it were, you could solve the halting problem.

rntz··on What You Need to Know Before Considering a PhD
In computer science in the US, this is just false. Four years is the usual "officially expected" length of a PhD straight out of a bachelors' (which is the most common way to do a PhD in CS in the US). In practice it usually takes longer, sometimes much longer (seven+ years is not unheard of).

In the UK and Europe, shorter PhDs are much more common, in part because you're expected to do a master's before a PhD.

Even for two or three years, I don't think getting a computer science PhD is a good bet if your primary goal is making more money.

rntz··on The Xi Text Engine CRDT
CRDTs and semilattices are definitely connected, but they're not quite the same thing. A CRDT is a data structure that can be merged across the network in a way that's commutative, associative, and idempotent. That much is exactly the same as a semilattice.

But when people talk about "string CRDTs", the underlying semilattice, the data structure that gets merged, isn't a string; it's usually something rather more complicated. Then there's a _function_ which interprets that more complex data structure as the string that the user or application really cares about.

So a CRDT is a semilattice equipped with an interpretation function.

But it gets even more complicated, because there are many ways to do CRDTs in practice. Rather than gossiping your _entire_ complex data structure across the network ("state-based CRDTs"), usually CRDTs try to only send what's necessary. This leads to optimisations like delta-based and operation-based CRDTs. These optimisations are crucial for real-world use of CRDTs, but their connection to semilattice theory is not immediately clear to me. (That doesn't mean there isn't one, though!)

In any case, the story is a little more complicated than "CRDTS are just a semilattice". I do wish more people knew about the connection, though.

rntz··on Earth at risk of becoming 'hothouse' if tipping point reached, report warns
> "hothouse" temperatures could stabilize 4°C to 5°C (39 to 41 Fahrenheit) higher than pre-industrial levels.

A change of 4-5°C is a change of 7-9 degrees Fahrenheit, not 39-41.

rntz··on Confessions of an Ex-Prosecutor (2016)
Why is it that the legal profession is split between prosecutors and defense lawyers? I ask this question in two senses: first, historical - how did it come about? and second, moral - what is the justification? After all, doesn't this division promote exactly the kind of tribalism based on prejudice (an assumption of the guilt or innocence of the defendant) we wouldn't want in a legal system - the kind of tribalism this article points out when it talks of "the brotherhood of prosecutors"? Why don't we require those who prosecute to also sometimes defend; those who defend, also to prosecute?
rntz··on Undershoot: Parsing theory in 1965
On the one hand, you're right. Python takes exactly this approach: it disambiguates using "for" and "if":

    LISTCOMP ::= [ EXPR STMT* ]
    STMT ::= "if" EXPR | "for" PAT "in" EXPR
This is LL(1) and trivial to parse recursively.

On the other hand, Haskell list comprehensions really aren't hard to parse... for humans! Most people I've talked about this have no idea that Haskell comprehensions are formally so much harder to parse than Python list comprehensions. The difficult cases just don't arise in practice.

And there are plenty of places where we accept problems or algorithms which are ridiculously inefficient in theory, but fine in practice. Damas-Milner type inference, for example, takes time O(2^2^PROGSIZE) in the worst case - doubly exponential! Far worse (in theory) than the O(n^3) of general CFG parsing algorithms (which can be quite simple to implement!).

And this problem doesn't just come up in Haskell list comprehensions, but also with monadic do-notation. I'd much rather write:

    do (x,y) <- foo
       z <- bar x
       return (x + y + z)
than:

    do for (x,y) <- foo
       for z <- bar x
       return (x + y + z)
The extra "for" (or whatever keyword you want to put there) is just syntactic noise to a human, however much easier it makes it for a computer to parse it.

So I'm of two minds, really.

rntz··on Undershoot: Parsing theory in 1965
This does work, and is available in e.g. the Parsec library for Haskell, but

(1) can lead to exponential worst-case backtracking behavior.

(2) can produce very unhelpful error messages without careful engineering.

In this case, for list comprehensions, I think you can show that you won't have exponential backtracking behavior. But it involves carefully thinking about whether patterns can nest inside of expressions nesting inside of patterns nesting... etc.

It's probably still the best solution if you're writing your own parser, though.

rntz··on Undershoot: Parsing theory in 1965
I have a toy problem that I throw at anyone who thinks they've "solved" parsing: Haskell list comprehensions. A list comprehension takes the form

    "[" EXPR "|" STMT["," STMT]* "]"
Where STMT is given by:

    STMT ::= EXPR | PAT "<-" EXPR
The problem is that, until you see that "<-", you don't know whether you're supposed to be parsing a pattern PAT or an expression EXPR. This is extra hard because patterns and expressions overlap significantly; for example, "(x, Left 2)" could be either a pattern or expression. But "(x, Left (2+3))" is definitely an expression. You can get arbitrarily deep into parsing a pattern before you realize it's actually an expression!

Recursive descent parsers, even with precedence climbing, can't really handle this nicely. Neither can LL or LR parsers. In fact, GHC's actual parser uses a hack: it parses patterns as expressions, and as a post-processing step checks that the expression it parsed actually was a valid pattern! This works IF your patterns are a subset of your expressions. But if there are patterns that aren't valid expressions (Racket's match-patterns have this property), then you need to get even cleverer.

General-purpose parsing algorithms like GLR, GLL, parsing with derivatives, and Earley parsing (which Kegler advocates) can handle this, of course, although I'm not sure how efficiently they do it.

rntz··on Fibonacci Hashing: The Optimization That the World Forgot
Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the common solution, masking off the high bits, because it discards information, and proposes Fibonacci hashing: multiply by the golden ratio and shift down. It gives measurements suggesting this gives better performance in practice, and some theory as to why this might be.

But later it mentions, in passing, a simpler approach: just shift the high bits down and xor! The author only tries doing this as a preprocessing step in front of Fibonacci hashing to avoid "bad patterns". So I'm left wondering: might shift-down-and-xor be good enough on its own?

rntz··on Programming Language Theory in Agda
> Most of the type systems studied are not used in the wild, so they can't be interesting because they describe something people are already interested in. The only other possible explanation for the relevance of these papers is that the authors hope to improve upon what already exists.

Your argument here amounts to: if it's not descriptive, it must be prescriptive. By this argument, the entirety of pure mathematics is prescriptive. Is the idea of a semiring a description of a particular natural object? But it makes little sense to claim the idea of semirings is normative. After all, math studies many structures that don't satisfy the semiring laws, as well!

Likewise, computer science studies many forms of "computation" which aren't physically realistic. Is computational complexity theory "normative" in studying Turing machines, or PRAM machines? No, they are merely convenient abstractions which get at the essence of a particular problem.

The lambda calculus is similar: it is a convenient abstraction which gets at the essence of a particular way of computing. It's a useful starting point for a certain kind of PL theory because its semantics are relatively simple. But it's certainly not the case that all PL theory studies the lambda calculus. PL theory includes work on verification of imperative programs; on macro expanders; on compilation techniques; and on pure logic.

What is certainly true is that many people who study PL theory do have normative (usually aesthetic) ideas about PL design, and these seep into the kinds of systems they tend to study. I agree that computer science isn't a natural science. But it isn't as simple as "anything not descriptive is normative", or that (quoting a sibling comment) PL theory is just "a theory of some variant of the lambda calculus".

rntz··on National Identity Is Made Up [video]
> This has happened over and over again in human history, native American civilizations serve as a great example.

A crucial point of contention here is: what counts as a "nation-state"?

States of various forms have certainly existed and come into existence repeatedly through human history, since about ~11,000 years ago. (That said, it's an interesting question why exactly states formed; there's some reason to think it required rather unusual conditions. The book Against the Grain by James Scott tries to tackle this topic.)

On the other hand, as the video describes it, a nation state is a state with a collective identity tied to a shared language, "race", and set of borders, usually maintained by a collective mythology which imagines this shared identity has deeper roots than it actually has. (For example, Joan of Arc is an important figure in the mythos of the French nation-state; but would most people living in what is now France in the 15th century have identified themselves primarily as "French"?)

I don't know much about native American history. Do you think most native American civilisations fit this description? I can think of plenty of states which don't. Examples of states which are not nation states would include: feudal states (medieval Europe); city-states (ancient Greece); empires of conquest (the Alexandrian empire, the Mongol Khanates); and empires united by religion (the early Caliphates).

rntz··on National Identity Is Made Up [video]
You define 'real' as: "likely to arise in any culture, perhaps in any species that's able". That's a strong claim. Look at your arguments supporting it:

> You have a greater interest in reaching consensus with people in the same democracy as you...

> People who live in the same country as you fund the same programs and projects...

> People who live in the same (democratic) country are co-responsible with you...

These all have the form: if democratic nation-states already exist, people will have reason to identify with them. This is plausible, but does not prove that nation-states are "likely to arise in any culture, perhaps in any species that's able".

What it means is that nation-states are a relatively stable arrangement - that, once extant, they by and large convince people to go along with their existence. But there have been many forms of social organization which were stable for long periods of time before modern nation-states came along. Why shouldn't there be many others succeeding it?

rntz··on National Identity Is Made Up [video]
Most people will admit that laws are made up; that they are only good insofar as they produce a good society; that laws serve society, rather than society existing to serve law.

Money is a little harder, but IME most people eventually acknowledge that the value of money is simply that we all acknowledge it has value.

Whether people admit that nations are "made up" depends on how you press the point. That the precise boundaries of nations are a product of messy history rather than some ideal truth, most people will admit. But most people will push back if you insist on a broad sense of "made up"; for example, that no privilege ought to be given to "what's good for the country" in national policy, but only what is good for humanity, is a fairly unusual position.

Consider Kennedy's famous line, "Ask not what your country can do for you; ask what you can do for your country". To someone who thinks countries are made up, this is nonsense. Countries are valuable if they serve humanity, not vice-versa.

People are least likely to admit that their own religion is made-up; almost all religions claim legitimacy by asserting they reveal some sort of fundamental truth.

rntz··on Mysterious origin of domesticated horses ‘turned upside down' by DNA analysis
That's almost right, but you have the Botai horse and Przewalski's horse confused. The Botai were a human culture living in what is now Kazakhstan, approximately 3700-3100 BCE. They kept domesticated horses, and are the earliest culture known to have done so, so "Botai horse" would be a name for whatever kind of horses they had.

Przewalski's horse is a population of horses that exists today. It was considered the last wild horse (meaning: neither domesticated nor descended from domesticated horses), but the article says it is merely a feral population descended from Botai horses.

rntz··on RustBelt: securing the foundations of the Rust programming language
We regard "this program is hard to test" as a problem that's worth refactoring to fix; why shouldn't we regard "this program is hard to verify" the same way?
rntz··on Ask HN: What's the most underrated programming language?
If SQL deserves consideration for being "underrated", Datalog certainly does.

Compared to SQL, Datalog makes recursive queries very natural[1], making it good for manipulating graph-like structures. For example, here's reachability in a graph:

  reaches(X,Y) :- edge(X,Y).
  reaches(X,Z) :- edge(X,Y), reaches(Y,Z).
That was easy!

Variants of Datalog pop up in unexpected places. Datalog dialects are often used for implementing code analysers (e.g. Semmle). Datomic's product is a variety of Datalog with S-expression syntax. UC Berkeley has a Datalog-based research language called bloom (http://bloom-lang.net/faq/) aimed at implemented distributed systems. Datalog was also an influence on the recently-shuttered Eve (http://witheve.com/) project.

In its original form Datalog lacks aggregations, which is probably a big part of why it didn't catch on - aggregations are important! Still, some Datalog implementations add support for aggregations. Unlike SQL, Datalog never really became a standard; more an academic ideal than a practical tool. I think this is a shame.

While Datalog doesn't have a canonical practical implementation, in terms of impact on how people think about data query languages, I think it's an academic gem.

[1] SQL has recursive queries ("Recursive CTEs"), but they're neither widely used nor particularly well-supported in most SQL implementations - they're basically tacked on. This is partly because they're hard to optimize due to a lack of restrictions; with Recursive CTEs, SQL is Turing-complete. Datalog deliberately isn't, and there's a large literature on optimizing evaluation of recursive Datalog.

rntz··on Ask HN: What's the most underrated programming language?
I think Racket is underrated. (Dunno about "most underrated".)

It's a batteries-included Scheme/Lisp dialect with the best documentation I've ever seen, a state-of-the-art macro system, and a very friendly community. It has performance better than your typical dynamic language (Python, Ruby) though not as good as the highly optimized ones (Javascript V8, LuaJIT).

rntz··on The Eve programming language project is winding down
> Humans aren't getting much smarter in general.

It's actually possible that we are: https://en.wikipedia.org/wiki/Flynn_effect ; summary: "The Flynn effect is the substantial and long-sustained increase in both fluid and crystallized intelligence test scores measured in many parts of the world from roughly 1930 to the present day." (But both the reality and the interpretation of this are matters of some dispute.)

Moreover, without any computer assistance until very recently, our ability to do mathematics has advanced marvelously over the past few thousand years. We shouldn't underestimate the power of education, culture, better notation, and accumulated wisdom to advance human capacities even at purely intellectual endeavours such as math (or, for another example, chess).

Of course, none of this says that computers themselves can't help us program, which is your primary point. I just think you're being a little pessimistic about "merely human" ways of improving ourselves.

rntz··on Show HN: Observable Notebooks
This works by executing Javascript code written by the user. Since these notebooks are shareable, and there is also a log-in feature, do any security features need to be put in place to prevent, say, someone linking me to a notebook that sends my login credentials for observablehq.com to a malicious host? That is, is the javascript inside the notebook sandboxed in any way?

I don't fully understand how modern web security works. But "executing arbitrary javascript written by user A on website B viewed by user C" seems worrying.

rntz··on The Eve programming language project is winding down
> we don't have institutions at present that will allow people to explore the problem thoroughly

What about academia?

Academia is not a great environment for creating tools that people will actually use, which Eve was definitely trying to be; but "exploring a problem thoroughly" is exactly what academia is for.

rntz··on The Eve programming language project is winding down
Building bridges is hard. But it's a lot easier now than it was five hundred years ago.

There's no general reason to think hard things can't get easier.

rntz··on The Eve programming language project is winding down
Your comment is inconsistent with itself.

If LightTable's features "had been standard in IntelliJ, Visual Studio, and even Eclipse for years", how is that evidence that Granger et al were being overly ambitious? Wouldn't it suggest exactly the opposite?

Vice-versa, if LightTable was overly ambitious, wouldn't that mean it tried to do things that were (too far) beyond the scope of existing technology?

rntz··on LLVM patch to fix half of Spectre attack
This mitigates spectre variant #2, branch target injection. We also have a mitigation for meltdown, namely KPTI. Is there a known mitigation for spectre variant #1, bounds check bypass?

Maybe I'm being naive, but would a simple modulo instruction work? Consider the example code from https://googleprojectzero.blogspot.com/2018/01/reading-privi...:

    unsigned long untrusted_offset_from_caller = ...;
    if (untrusted_offset_from_caller < arr1->length) {
     unsigned char value = arr1->data[untrusted_offset_from_caller];
     ...
    }
If instead we did:

    unsigned char value = arr1->data[untrusted_offset_from_caller % arr1->length];
Would this produce a data dependency that prevents speculative execution from reading an out-of-bounds memory address? (Ignore for the moment that a sufficiently smart compiler might "optimize" out the modulo here.)
rntz··on High-Level Problems with Git and How to Fix Them
Could you elaborate for those of you who don't quite understand?

I understand the reference, but is there more to this comment than a joke?

rntz··on Political theorist James Scott thinks civilization is overrated
I'm reading "Against the Grain" at the moment. It's good, but James Scott (the author) is also clearly a little out of his academic comfort zone in it - Scott is a political scientist & anthropologist, not an archaeologist. He also tends to repeat himself a lot.

Scott has also written "Seeing Like A State", a great book about, in its own words, "how certain schemes to improve the human condition have failed" - in particular, grand schemes by powerful central governments which forced pre-existing social and ecological arrangements into a form more understandable to central management, but in the process lost some essential flexibility.

Also related, an older piece in the same vein as "Against the Grain" is Jared Diamond's short essay "The Worst Mistake in the History of the Human Race": http://www.ditext.com/diamond/mistake.html (Jared Diamond is also not an archaeologist, however. I'm curious what archaeologists have to think about this line of reasoning in general.)

rntz··on “Beautiful” in the Constitution of the Chinese Communist Party
It's not common in ordinary English, but perhaps it is common jargon among linguists?
rntz··on Monotonicity Types: Towards a Type System for Eventual Consistency
I'm actually the Datafun paper's other author, so folks can AMA if they're interested in Datafun.

It's very interesting to me to see the connections and differences here:

- Monotonicity Types and Datafun both track monotonicity, but for entirely different purposes; MT for CRDTs & distributed programming, Datafun for enforcing termination on recursive queries.

- MT uses a refinement-type-style system, while Datafun uses a modal type system. It's not clear to me whether this is related to their different use-cases, or just an accident of history.

- Relatedly, MT builds on an existing language (Lasp, which itself builds on Erlang), while Datafun is entirely new. MT is definitely more practical in this respect. My hope is that Datafun, while not practical to use directly yet, will have a big impact in the long run, as its namesake Datalog did, but that's just a dream :).

- MT and Datafun both care about semilattices: MT because CRDTs are based on semilattices, and Datafun because they give a natural and general way to comprehend over sets, and also guarantee a "bottom element" for our fixed-points to start computing from.

- Datafun has two kinds of function: monotone (preserves ordering) and discrete (could do anything). MT has five qualifiers on function arguments, representing whether the function respects the ordering, inverts the ordering, disrespects the ordering, ignores the argument entirely, or returns that argument unchanged. Wow! Are all those qualifiers really necessary? Maybe. Antitone functions (order-inverting) are something we're considering adding to Datafun, at least.

← PreviousPage 3 of 15Next →