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 Greatest Regex Trick Ever (2014)
The original article already relies on finding multiple matches, in order to ignore the matches that don't contain the group that we're interested in.

Python's regex library, for example, can return multiple matches. It has three functions:

- `re.match`, which checks whether the whole string matches.

- `re.search`, which checks for the first location in the string that matches.

- `re.findall`, which finds "all" non-overlapping matches.

I was simply suggesting that the "non-overlapping" constraint in findall is a "bug", in some sense, because it exposes implementation details of the regex engine.

But, again, given that it is apparently a useful bug, maybe I am wrong. But that leaves open the question what the right spec for regex matching is, anyway.

rntz··on Too often, the government uses its information machinery to try to persuade
Core problem:

> Unfortunately, it otherwise has proven all but impossible to write a law that absolutely differentiates information from advocacy.

rntz··on The Greatest Regex Trick Ever (2014)
I believe it matches in three ways:

- the whole string, grouped as "(aa)(abbb)",

- the whole string, grouped as "(aaa)(bbb)";

- the substring "aabbb", grouped as "(aa)(bbb)".

rntz··on The Greatest Regex Trick Ever (2014)
This "trick" is simply exploiting a bug in regex implementations.

The regex

    "Tarzan"|(Tarzan)
should match the string

    "Tarzan"
in two ways: first, matching the entire string; and second, matching the substring "Tarzan" in the whole string "\"Tarzan\"". But most regex implementations drop extra overlapping matches. I argue this is incorrect behavior, because it complicates understanding what a regex means - you have to understand the /order/ in which your regular expression matcher interprets your regular expression, which is an implementation detail. I conjecture that a DFA-based regex engine would not be able to exhibit this order-biased behavior, at least not with the standard approach.

However, it's interesting that this "bug" turns out to be a "feature" for the case of excluding other behavior. I'm not sure what conclusion to draw from this.

rntz··on Birth of the Moralizing Gods
full article link: http://www.sciencemag.org/content/349/6251/918.full
rntz··on Multiple Vulnerabilities in Pocket
Never attribute to malice what can be adequately explained by incompetence.

Mozilla almost certainly isn't getting any money out of the Pocket integration deal. Mozilla has far more money than Pocket does.

rntz··on Lasp: A language for distributed, coordination-free programming
Since CRDTs are just join-semilattices with a zero element, and the category of join-semilattices with zero is a model for linear logic[1], I suspect that there may be an even cleaner way to write eventually consistent programs, using a linear lambda calculus (or possibly a process calculus, since those also model linear logic). I've been looking into this area in my off-time but haven't managed to get very far, perhaps because I still don't understand category theory well enough. Nice to see there's demand for a language with this property, though :).

[1] Linear logic's "tensor product" corresponds to tensor product of semilattices; linear maps correspond to semilattice-morphisms with a pointwise join operation. Linear "with" and "tensor sum" both correspond to cartesian product of semilattices. It's a rather degenerate model in this respect.

rntz··on An argument for open global immigration
> it's really really good for all the poor people from impoverished, war-stricken countries?

What part of this argument do you disagree with, and why?

rntz··on What we know about the EmDrive and Cannae Drive
Not unless you're experiencing friction.
rntz··on The Beauty of Code
> This leads to bewildered frustration with programming and a general distrust of all programs.

I think this is perhaps a more honest attitude to the state of programming today than those of us who have managed to master it are willing to permit ourselves. We suffer from the sunk cost fallacy: we are tempted to imagine that the complexity we have mastered is necessary, because if it were not, then we would feel our time spent learning it had been wasted.

rntz··on Going “Write-Only”
> The discussion in The Republic maintains that would-be citizens of the ideal republic should be exposed to music that cultivates their good qualities, and prohibited from listening to the bad. Much modern music creates agitation and aggression. I’ll listen to serene and balanced songs like Gregorian chant and neoclassical

> The etching, and even the pressing and collating of pages were difficult processes but somehow the artists outdid us, we who can so easily create, modify and distribute images. Goodbye cartoonish web images, let me be immersed in nature and see uninhibited art instead.

The author should be careful not to confuse a desire for focus and on the lasting rather than the ephemeral with a fetishisation of the past, of the "authentic", and of the "natural". It is all too tempting to step from use of survivorship bias as a tool, as a filter, into a false belief in the superiority of things past.

> the (false?) feeling of connectedness through a glowing rectangle

This particularly gets to me. I know people who would not be here on this earth today if not for the ability to connect with others through the internet. If you feel like disconnecting makes your life more fulfilling, great! But don't project that onto others by saying that what makes their life meaningful is false. (At least he had the self-awareness to throw in a question-mark.)

rntz··on Fearless concurrency with Rust
I mostly know about the linear logic side of session types; I'm not super familiar with the older line of research starting with Honda. I'll have to read up on it!

I'm not sure what the equivalent in my world of "session initiation" is. If by "replicated inputs" you mean what in linear logic is expressed by the "!" connective (often called "replication"), it's definitely possible to have ! without deadlocks or any observable nondeterminism. See Caires & Pfenning, "Session Types as Intuitionistic Linear Propositions", for example.

I already listed a few of the limitations of this approach (limited process topologies, and no `select()` analogue). I'm not sure whether these qualify as "completely inexpressive", but I do think the lack of any `select()` analogue is pretty limiting in practice. I'm not sure how hard it might be to remove that limitation, but it wouldn't surprise me if that were a major sticking point. Still, overall I think I'm more optimistic about the possibility of capturing most reasonable forms of concurrent programming in a deadlock & race-free manner.

rntz··on Fearless concurrency with Rust
I'm not sure what you mean when you say that race conditions can be the same kind of error as logic errors.

I would define a race condition as "an error due to nondeterministic concurrency". If you ban nondeterminism, for example, race conditions are impossible. In practice, nobody wants to ban nondeterminism, so races creep in. There might be smarter ways to eliminate races (ways of only allowing benign nondeterminism), though. So I'm not sure that practical languages without race conditions are an unachievable goal, just a difficult one. Give it another 20 years and we'll see where we're at. :)

rntz··on Fearless concurrency with Rust
Preventing deadlocks is not an unsolvable problem. Linear-session-typed process calculi are guaranteed deadlock-free and race-free. (The connection with Rust's ownership type-system makes me wonder if there might be some way to backport this guarantee to Rust, but I suspect the connection doesn't go far enough.) This comes at a price, however: certain process topologies are impossible to construct, and there's no way to ask "give me the first message to arrive on either of these two channels" (no Unix `select()` analogue). The latter in particular bugs me, because `select()` is a necessity in practice.

In general, problems of "guarantee property X" can almost always be solved with a sufficiently advanced type system, but at the cost of (a) inventing and using a sufficiently advanced type system and (b) disallowing some perfectly good programs.

rntz··on Fearless concurrency with Rust
This post observes that

> the same tools that make Rust safe also help you tackle concurrency head-on.

The tools that make Rust safe, in this instance, being its ownership type system. Why on earth should that be the case? Why would ownership types make concurrency easier? The post gives plenty of in-depth answers to this question, but to my mind it misses the bigger picture.

The big-picture reason why ownership types and concurrency match so well is the Curry-Howard correspondence.

Ownership types are known as linear[1] types in the PL theory literature. Linear types are so-called because they correspond to linear logic, a logic sometimes described as "the logic of resources" rather than "a logic of truth". In linear logic, instead of reasoning about eternal truths like "1 + 1 = 2", you reason about resources, like "I have an apple and a banana". If you also happen to know that "from an apple, I can make applesauce", then linear logic lets you reason that you can obtain the state "I have applesauce, and a banana" (but no longer an apple).

However! Linear logic has another interpretation, a Curry-Howard interpretation. You can also view it as a type system for a concurrent language based on message-passing, where your types describe the protocols message-channels obey. "I have an apple and a banana" corresponds to a channel which will first produce an apple, then a banana, then close. This is known as the session-types interpretation[2].

At first glance it may seem that this interpretation of linear logic and Rust's interpretation are unconnected. I doubt it; in logic, everything connects to everything else. It's no coincidence, for example, that ownership (linearity) is what you need in order to send mutable values across a channel without copying. There is a deeper structure waiting here to be discovered, and I for one am deeply excited about it.

[1] In Rust's case, technically they are affine types. An affine type is a linear type whose values can be freely dropped, i.e. deallocated.

[2] Session types have been around for a long time, but only fairly recently was the connection to linear logic discovered.

Links/papers on session types:

1."Propositions as Sessions" by Wadler (http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-...)

2. Caíres and Pfenning, "Session types as intuitionistic linear propositions" (http://www.cs.cmu.edu/~fp/papers/concur10.pdf)

3. Pfenning's published works page (http://www.cs.cmu.edu/~fp/publications.html).

rntz··on Not everything is an expression
I'm sorry, I don't really understand what you're getting at when you say that I'm confusing "how macros are used" and "what macros are". Perhaps we're just disagreeing about terminology?

What I mean by a "macro" is: a convenient way to extend the syntax of a particular syntax class by telling my language how to translate the syntactic construct I want to add into constructs it already understands. In this sense one definitely can have expression-macros and pattern-macros. Is there some reason you think one shouldn't have this in a language?

Your new proposed `if-match' is strange. I'm not sure how I'd use it to, for example, implement a "list" pattern-macro, such that `(list p1 p2 p3)' matches any list of three elements, whose first element matches p1, second matches p2, and third matches p3. You seem to intend that `((list p1 p2 p3) expr then else)` should macro-expand to the code that performs this pattern match. This is difficult for two reasons:

1. I'd need to shadow the definition of `list' with a macro that usually behaves like the list function, but if used inside of if-match behaves differently. This seems difficult, and is conceptually ugly.

2. AIUI, to get `((list p1 p2 p3) expr then else)' to macro-expand specially, `(list p1 p2 p3)' has to macro-expand to a symbol naming a macro, call it MAGIC, such that `(MAGIC expr then else)` expands to the desired result. This is difficult, because MAGIC needs to know about p1, p2, and p3. So `(list p1 p2 p3)' will need to dynamically define a new macro (with a gensym'ed name) that knows specifically about p1, p2, and p3, and return that. This may be possible, but is gnarly as fuck.

This is certainly very far from being "the obvious way to do it" to anyone but a wizard.

Maybe I'm misunderstanding you, or you made a typo?

rntz··on The poor, misunderstood innerText
The first live example doesn't work in Firefox, for a reason the article already mentioned: Firefox doesn't support innerText.
rntz··on Not everything is an expression
Regarding 2: The article punts on the question of how to implement such a system, because I think it's a hard question. I could have been clearer about that, and maybe in future I'll write an article speculating on some ways one could approach the problem. But I think it's an underappreciated problem, and I hope this article will spur other people to consider it.

Re 1:

In a.clj:

    (ns a (:refer-clojure))

    (defmulti if-match*
      (fn [pat _ _ _] (if (list? pat) (first pat) (type pat))))

    (defmacro if-match [pat expr then else]
      (if-match* pat expr then else))

    (defmethod if-match* clojure.lang.Symbol
      [pat expr then else]
      `(let [~pat ~expr] ~then))
In b.clj:

    (ns b (:refer-clojure) (:require a))

    ;; a 'foo pattern-macro that does negation
    (defmethod a/if-match* 'foo [pat expr then else]
      `(a/if-match ~(second pat) ~expr ~else ~then))
In c.clj:

    (ns c (:refer-clojure) (:require a))

    ;; a 'foo pattern-macro that is the identity pattern
    (defmethod a/if-match* 'foo [pat expr then else]
      `(a/if-match ~(second pat) ~expr ~then ~else))
Now, at the repl:

     user=> (use 'a)
     nil
     user=> (require 'b)
     nil
     user=> (if-match (foo x) 'yes x 'no)
     no
     user=> (require 'c)
     nil
     user=> (if-match (foo x) 'yes x 'no)
     yes
Note that 'require doesn't actually import the symbols defined by b.clj or c.clj, and despite that we're able to use the pattern-macro 'foo they define, because they're modifying if-match's dispatch-table. So our pattern-macros aren't being scoped the same way our regular macros are. I think this is wrong. Moreover, our pattern-macros have a single namespace, so we get collisions between what b.clj defines 'foo to mean and what c.clj defines it to mean, which is why (if-match (foo x) 'yes x 'no) changes behavior after the (require 'c).
rntz··on Not everything is an expression
That's a very clever use of defmulti that I hadn't considered --- consider that you may know more about writing extensible macros than the average lisper :P. My article was also aimed at being language-agnostic, so a Clojure-specific feature like defmulti wouldn't have been appropriate to introduce. (Although of course CLOS does have multimethods as well, but that's an even more complicated subject!)

However:

1. The code you give still isn't smart enough. It dispatches on the symbol at the head of the list, but that doesn't account for namespacing. So your pattern-macros will all end up in one giant namespace. You could probably invent something clever to account for this but...

2. My overall point[1] was that writing a macro-extensible macro shouldn't require cleverness or new code - it should be in the standard library! Indeed, ideally defining a "pattern-macro" should be accomplished via the same mechanism as defining an "expression-macro"; you shouldn't need separate, custom macro-defining-macros for each syntax class. I'd settle for it just being easy to define an extensible syntax class along with a macro-defining-macro for it, though.

[1] Admittedly, this point could have been far clearer.

rntz··on Not everything is an expression
Yes, my discussion of the notion of syntax-classes is definitely a brief gloss, not an in-depth examination. I deliberately ignored the fact that Python merges statements & declarations in order to be able to demonstrate all four syntax classes in a single small example.

I'm not sure it's appropriate to say that declarations are "executed at" compile time in a statically-typed language. In SML, for example, there's a notion of "phase separation" by which you can split the meaning of a program into its compile-phase and its run-phase meanings. Many declarations end up having both compile- and run-time components. In Haskell you might say that declarations are executed at compile time, but this means nothing more than that name-resolution and type-checking happen at compile time.

rntz··on Not everything is an expression
Yup, I pretty much want it to be trivially easy for define macros that are themselves macro-extensible. It's definitely possible to do this in Lisp, but:

(a) it's not a well-known technique

(b) it's not in the standard library of any Lisp I know of

(c) there are interesting open design questions to be answered in the implementation of such a system

I hope this article will get folks thinking about these issues.

For example, walking the AST and calling macroexpand will work, but then you can't have a macro that expands differently in different contexts - when interpreted as an expression versus as a pattern, for example. I think this is an important feature.

rntz··on Not everything is an expression
Often you want the same code to expand differently depending on context, so I think it's still important to have explicit support for different syntax classes in a macro system.

Declarations are definitely a syntactically distinct class in, for example, Haskell or SML or C. Not so much in Lisp, Python, Javascript, and so forth.

I think the question of what an extensible extension mechanism would look like is a tough one, which is why I punted on it. I have worked on it a bit myself, as mentioned in another comment, but not in Lisp. I definitely might try my hand at a Lisp version in future, though, and I'm interested to see what other people might come up with!

rntz··on Not everything is an expression
Author here. I have created a language, called moxy (https://www.github.com/rntz/moxy), which supports not just extensible pattern-matching but defining extensible extensions in general (of which pattern matching is one example, LINQ might be another, and so on and so forth). However, it wasn't a lisp, because I also wanted to see whether I could support syntactic extensibility in a non-lisp language.

The really important point, that moxy explored and that I think I didn't make clear in the article, is that patterns are just one example of where you want extensibility of a non-expression syntax class. Really you want to be able to define your own syntax classes and be able to extend them!

I only mentioned moxy in a footnote in the article because it's "research-quality" at the moment - it's not well documented and I'm still having second thoughts about its design. I've moved on to other thing and am busy with work, so I don't imagine I'll be working on it in the immediate future.

rntz··on Not everything is an expression
Author here!

syntax-rules is a form of pattern matching (mentioned in footnote 2). But it's only for matching on syntax, not on ordinary values. I can't write the fibonacci function using syntax-rules.

The idea behind "not everything is an expression" is that ordinary macros only extend the expressions in a language. But languages have more than expressions to them - they also have patterns, and possibly other syntax classes (loop formats, LINQ, monadic do-syntax). I think those syntax classes ought to be macro-extensible as well. That's what I mean when I say that ordinary macros don't acknowledge that not everything is an expression.

It's rather a roundabout way to say it, I guess.

rntz··on ArchieML is a structured text format optimized for human writeability
The live demos aren't appearing for me in Firefox, which makes the page nearly useless in understanding what ArchieML actually looks like.

The relevant error appears to be:

    TypeError: aml.innerText is undefined archieml.org:364:6
Firefox 36.0, Ubuntu 14.10
rntz··on The Likely Cause of Addiction
So what you're suggesting is simply that alcohol addiction has different underlying causes than opiate addiction?

If so, that doesn't undermine the whole of the article's point; it merely suggests that the best policy for getting people off opiates isn't necessarily the best for dealing with alcoholism. The "Drug War" isn't a war on alcohol, after all.

> The other thing is that opiates don't help rats being rats. Anyone who has ever interacted with rat knows they are curious and social animals, they like to explore, fight and have sex.

Sounds pretty human to me.

rntz··on A Software Engineer’s Adventures in Learning Mathematics
Thanks! That's quite illuminating.
rntz··on What Color Is Your Function?
> I think that I don't understand the definition. Isn't encountering a runtime error precisely getting 'stuck' (in the "opposite-of-progress" sense)?

Sorry, perhaps I should have said "exception" rather than "error". Raising an exception is absolutely "safe"/progress-obeying, as long as your language specifies the behavior of exceptions. That the exception happens to be called a "TypeError" doesn't change anything.

Getting "stuck" means being in a state such that there's no defined next state - a state which the language spec doesn't cover. So most "dynamically-typed" languages are in fact safe in progress-and-preservation terms, because they have well-defined behavior in all cases. C, otoh, is "statically-typed" but unsafe, because you can write C code with undefined behavior.

(That dynamically typed languages can be (statically) typesafe should be unsurprising, since they're just statically-unityped languages. Nothing says a unityped language can't be typesafe, it's just a very uninteresting property!)

rntz··on What Color Is Your Function?
Do you consider any function which may raise an error to be "dynamically typed", then? (For example, any function which performs an array index; or any function which performs I/O; or, to be absurd, any function which allocates memory (since memory is a finite resource that may run out).) If so, I understand the distinction you're making, but it's a very strong position; most people do not mean that when they say "statically typed". If not, I don't understand the distinction you're making.

Admittedly, gradual typing does not mean that calling into untyped code from typed code is "safe" from runtime type errors (although it is safe in the technical preservation-and-progress sense). But it gives you a partial guarantee: if a type error occurs, you know that the fault does not lie in the typed code. This aids debugging, and helps you port over existing codebases gradually. So it's still quite useful.

rntz··on A Software Engineer’s Adventures in Learning Mathematics
Number theory. Set theory. Category theory. Combinatorics. Graph theory.

Linear algebra certainly has applications in some of the above. But I don't think that calculus & linear algebra can be fairly described as "father & mother" to these areas. (Am I wrong? I could be missing some connections; I'm not a mathematician.)

← PreviousPage 10 of 15Next →