Live data from Hacker News

I hate the Pumping Lemma

bosker.wordpress.com

21–30 of 52 posts

Re: I hate the Pumping Lemma

#21
And that's one of the reasons I think mathematicians overcomplicate things.

They use "for all X" "of type" Y (being "of type" meaning: has these properties) then Z happens in place of "if you have something that has these properties Z happens"

Yes, they are equivalent, but the first order logic version looks like "strongly typed" and the second version looks like "duck typed"

This is just my 2 cents.

Re: I hate the Pumping Lemma

#22

And that's one of the reasons I think mathematicians overcomplicate things. They use "for all X" "of type" Y (being "of type" meaning: has these properties) then Z happens in place of "if you have something that has these properties Z happens" Yes, they are equivalent, but the first order logic version looks like "strongly typed" and the second version looks like "duck typed" This is just my 2 cents.

More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.

Re: I hate the Pumping Lemma

#23
post #22

And that's one of the reasons I think mathematicians overcomplicate things. They use "for all X" "of type" Y (being "of type" meaning: has these properties) then Z happens in place of "if you have something that has these properties Z happens" Yes, they are equivalent, but the first order logic version looks like "strongly typed" and the second version looks like "duck typed" This is just my 2 cents.

More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.

True

However, the evolution of math often goes towards generalising a certain behaviour, operation or set.

For example, first we had the natural numbers and the addition operation. Then addition was generalised as an operation on different 'objects' like matrices, equations, etc

So, yes, the strong typing idea makes sense, maybe someday math will be able to generalise addiction for any set and any object based only on their properties, regardless of what they are.

Re: I hate the Pumping Lemma

#24

Here's what I think is a fun explanation of the pumping lemma, using no special terminology. As many people on here know, the phrase "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo" is a complete sentence[0]. What many people may not know is that you can add (but not subtract) as many "buffalo" as you want and still have it be a complete sentence. Why's that? Well, an easier sentence to look at is "J…

"Buffalo Buffalo Buffalo"?

Re: I hate the Pumping Lemma

#25
post #9

Earlier quoted context omitted.

Some regexp dialects are actually Turing complete from what I've heard. EDIT: Yes this seems to be wrong

I'm not sure if they're turing complete, however many many many common regexp dialects (as seen in perl, ruby, python, etc.) are more powerful than what you learned as "regular expressions" in CS class, they're at least as powerful as a PDA.

Do you mean that some regex implementations allow you to parse context-free grammars?

Re: I hate the Pumping Lemma

#26
I remember a professor teaching parser construction and trying to explain the various sets (tokens, states, actions, followers) with triple nested set notation in mathematical notation. E.g. {x of {y of {z of Z| z > 0} | y != x | ...}. Completely incomprehensible.

And that while parsing languages is actually a really nice topic, and the various parsing modes are very easy to understand if you talk through them from the implementation perspective (LL in particular, but also LR, LALR). It's very intuitive how parsing has to make a decision given a certain lookahead and thus has to pick the correct rule to descend into, how that relates to the runtime efficiency, and it also makes other solutions understandable, e.g. packrat parsing.

Nothing against getting a strong formal model for a problem, but I think Academia's approach is often the wrong way around. It's much easier to understand these solutions from the code, and then develop a theoretical model around them (this is how all of them were invented anyway).

Re: I hate the Pumping Lemma

#27
I think one reason the Pumping Lemma is emphasized so much is that it is a good exercise in logic. We often find that students have difficulties with quantifier alternations (there exists x, such that for all y, there exists z, such that...). I think it is a good idea to practise such reasoning (e.g. for complicated module abstractions in software systems). The Pumping Lemma is a good example to exercise such reasoning.

Re: I hate the Pumping Lemma

#28
post #22

And that's one of the reasons I think mathematicians overcomplicate things. They use "for all X" "of type" Y (being "of type" meaning: has these properties) then Z happens in place of "if you have something that has these properties Z happens" Yes, they are equivalent, but the first order logic version looks like "strongly typed" and the second version looks like "duck typed" This is just my 2 cents.

More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.

Interesting argument, though I currently think correctness is more important in programming. Their proofs are hand-wavy compared to our programs.

Thurston expands, "It’s just that the reliability does not primarily come from mathematicians formally checking formal arguments; it comes from mathematicians thinking carefully and critically about mathematical ideas." (http://arxiv.org/abs/math/9404236)

But I could also accept the claim that mathematics is more intellectually gratifying, if they're not so much at the mercy of standardization and other boring fiddly issues. I don't know.

Re: I hate the Pumping Lemma

#29
post #22

Earlier quoted context omitted.

More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.

True However, the evolution of math often goes towards generalising a certain behaviour, operation or set. For example, first we had the natural numbers and the addition operation. Then addition was generalised as an operation on different 'objects' like matrices, equations, etc So, yes, the strong typing idea makes sense, maybe someday math will be able to generalise addiction for any set and any object based only o…

If you want to see generalization look no further than Category Theory. But it's all done "safely": you define what a category is, and prove things about it, and then declare how certain objects can be viewed as categories (somewhat like the typeclass pattern).

Re: I hate the Pumping Lemma

#30

Here's what I think is a fun explanation of the pumping lemma, using no special terminology. As many people on here know, the phrase "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo" is a complete sentence[0]. What many people may not know is that you can add (but not subtract) as many "buffalo" as you want and still have it be a complete sentence. Why's that? Well, an easier sentence to look at is "J…

"Buffalo Buffalo Buffalo"?

Actually even "Buffalo buffalo." is a complete sentence.
Post reply on HN