Comment by stcredzero | Hacker News Reader

Comment by stcredzero | Hacker News Reader

Parent Full thread

Just study the following:

    - Understand time & space complexity
    - Security & Encryption
    - Concurrency & why ACID transactions are hard

That will save you from most of the most embarrassing and costly mistakes of programmers without a formal education.

I've actually worked at a company that wasted millions on a fruitless project because management didn't understand basic automata theory:

    - Finite State Machines / Regular Expressions
    - Stack Machines / Context Free Grammars
    - Turing Machines / Anything Computable

I've been thinking of doing a presentation: Everything I still actually use from my CS education in less than an hour. (It will take you a bit longer to study and really absorb, but it will probably take a lot less than 4 years of college and cost much less.)

EDIT: Another good thing to study, though I'm not sure if there's a good single source: Why distributed systems are Hard and why distributed transactions are Really Hard. I really didn't care for the teaching style of the professor who staked out that whole area as "turf" so none of my materials were particularly memorable or good, but the information was valuable.

     management didn't understand basic automata theory

Do tell more about it; as I feel that's not why they wasted millions.

IMHO management isn't required to understand much about CS, as long as the relationship with the developers is as between a customer and an engineer (i.e. customer asks for stuff, engineer explains what he can and cannot do).

Most problems with management comes from a disconnect with reality. Even when they know CS theory and/or could understand the complexity involved (ex developers); having bikeshed-style opinions and making demands with an iron fist in spite of developers advising otherwise (or the reverse, having developers on the team without an engineering mindset that can't think for themselves) ... that's the real poison.

    management didn't understand basic automata theory

Do tell more about it; as I feel that's not why they wasted millions.

That company tried to translate code from one programming language to another using only regular expressions. (This was a long time ago when you couldn't almost count on most "regular expression" implementations being Turing Complete.)

Perhaps the problem was really that engineers who understood the futility of the approach didn't speak up or weren't listened to. Still, I'd expect people managing an engineering firm that builds bridges to have some basic grasp of physics. So I don't think it's going too far to have those running a software company to have some basic grasp of the basic laws governing their field.

I'm going to play devil's advocate here, and point out that you can actually construct the proper automaton where the transition conditions are decided by regular expressions.

It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call. Repeat until the programmers are satisfied with the number of conditions they can handle. I've seen software that was actually written like this. Fortunately, the language it was designed to parse was pretty simple.

I'm going to play devil's advocate here, and point out that you can actually construct the proper automaton where the transition conditions are decided by regular expressions.

It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call

In this case, you've created an "Augmented Transition Network" which is equivalent in power to a stack machine or a Context Free Grammar. Is this really playing devil's advocate? That would imply setting up something that isn't a straw man whose solution isn't basic automata theory.

This also gives you an idea of how broken the project was, since my understanding is that they'd fix "that particular bug" and keep writing more regular expressions.

The implication was that the project couldn't succeed because the management didn't understand basic automata theory, and insisted the programmers use only regular expressions. Presumably the regular expressions were being invoked by a Turing-complete programming language. Unless management decided that Turing-complete programming languages were not allowed, as well.

Amazing how often Turing-complete programming languages aren't utilized to their full potential. (And for the record, no I wasn't on that project. I have a CS degree and I remember automata.)

Wouldn't that still be a finite state automata?

You can create a submachine representing the regular expression transition conditions, and just attach that at the state you wanted, resulting in a finite state machine.

Of course this doesn't hold when you are talking about non-standard regular expressions, and it's probably a nice feature to have when creating the automata, but IMHO it still sounds like a silly idea when CFG-tools like ANTLR and YACC are available.

Wouldn't that still be a finite state automata?

The key is the bit about the "recursive call."

It doesn't have to be recursive. Iteration can also be non-finite-state. In fact, all recursive programs can be transformed to iterative ones.

Yes, thanks for exposing yet another Comp Sci fundamental tidbit. Any word deriving from "recursive" should be a red flag in this case.

Actually recursion in CS is equivalent to using a stack that keeps intermediate values and that grows in relation to the input.

If you've got an algorithm that does that, then it cannot be called "iterative".

I.e. backtracking is recursive, no matter how you implement it.

In school textbooks they do differentiate between "recursive" and "iterative" backtracking, to teach you how to get rid of the call-stack and manage your own. But that's another story.

      Wouldn't that still be a finite state automata?

He mentioned recursion, so no :-)

I also hate working with ANTLR/YACC ... heavy, hard to start with, steep learning curve. These tools are designed for industrial-strength compilers, where performance / flexibility matters.

And PEGs are better than CFGs (that's teeshirt material right there :))

Aaahhh, ofc, now I see why that wouldnt work. Guess I learn something every day :)

@stcredzero, that was exactly my point ... as a software developer I would never bend over and do as being told in that manner, because it is impossible to finish the task.

It wasn't just the management to be blamed: it the case of building bridges, engineers / architects can even go to prison if a bridge collapses.

"That company tried to translate code from one programming language to another using only regular expressions."

Ha! I know a guy who essentially got a US patent for roughly the same idea. His non technical bosses were so impressed that they gave him a raise and made him "Director of Analytics" at what was (or rather should have been) an Analytics heavy company.

That's a very interesting answer. I'm a self-learner, so can you kindly recommend good resources on "- Concurrency & why ACID transactions are hard"

That will be really helpful. Thanks.

Do you have any preferred links or book titles?

The following are books from my student days. These are sources from which I happened to learn the "everything in an hour, but longer to absorb" subject matter. I'd recommend Applied Cryptography as excellent, the other is just good.

Algorithms: Introduction to Algorithms (Cormen, Leiserson, & Rivest) http://amzn.com/0262033844

Security: Applied Cryptography (Schneier) http://amzn.com/0471117099

I cannot find my automata book just now. It's down in the garage, and I want to stay inside where it is warm now. As for concurrency, I got part of that from the Tannenbaum OS book:

http://amzn.com/0131429388

But the rest, I actually got from a coworker on the job! We did cover databases and ACID transactions in school, but that wasn't taught very well and I didn't really get it until I was doing real work.

Do some assembly language. It will give you a key advantage over everyone who is too scared to touch it.

Write a compiler and/or interpreter. This can actually be pretty small, and it will also give you an advantage over those too scared of something so seemingly "esoteric."

Shining my tptacek light re: Applied Cryptography

http://news.ycombinator.com/item?id=639786

Thomas recommends Practical Cryptography instead.

I actually read Applied Cryptography when it first came out. My experience is that it convinced me that crypto is hard to do right not that it's easy.

"Practical" will be my next technical read.

It came out in, like, 1995 didn't it? I remember that because all my IRC friends immediately got to work on crazy crypto tools with algorithms and ideas cadged from that book. It definitely didn't teach them that crypto was hard.

It came out in, like, 1995 didn't it?

That would be about right.

I remember that because all my IRC friends immediately got to work on crazy crypto tools with algorithms and ideas cadged from that book. It definitely didn't teach them that crypto was hard.

It's one thing to do some fun project. It's another thing to do something for production. It's yet another thing to read such a book and realize it means there's people who know a lot more about this than you. At the same time, it is a fun read for a techie.

Reply on news.ycombinator.com