Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Programmers are bad at managing state (2020)

nolanlawson.com

Post reply on HN
Print view View original

51–60 of 60 posts

Re: Programmers are bad at managing state (2020)

#51

Post by pdimitar »

crq-yml wrote: post #17

When state gets out of hand, I know of three options: 1. Put a constraint solver over it so that the programmer describes rulesets instead of state "paths". Regex rules like the Kleene star's backtracking are a simple example of such. 2. Put a compiler over it so that boilerplate "if" statements are generated from a smaller description. E.g. FSM compilers are one way of doing this. Years ago I read of an implementati…

> Years ago I read of an implementation of TCP/IP (which I can no longer find) built from a custom parser that read the actual text of the RFC spec and generated output source code.

OMFG! I thought of doing this a hundred times and never got around to it. Are you 100% sure you can't find it? I think such a piece of technology is extremely important!

Re: Programmers are bad at managing state (2020)

#52

Post by RangerScience »

btschaegg wrote: post #45
RangerScience wrote: post #19

Popped in here to say that AFAIK/IMO, most of the things people treat as "state" is actually "data". And then I started thinking myself in circles around "okay, so what is state?". Rather than /keep/ thinking myself in circles, I'll ask: What do y'all think "state" is ?

Okay, I'll have a go: State is the data required to continue the operation of a program. That's always the case (also in non-FP contexts), but state is often smeared all over a program as only loosely and implicitly connected pieces whereas FP is mainly concerned with how to manage state (and thus also with how to compose such pieces of state into a greater whole so it's easier to manage). Edit: Note that there is al…

I like it! I don't know if I agree, but, the category of "data required to continue the operation of the program" is a pretty excellent category, thank you for pointing it out!

Maybe... As you say, state is the information required for continued execution. Which would make "data" the information that's carried through the program. Like - parts of an HTTP request are "state" because they're what you use to route the packet through the internet. The other parts are "data", because all the intermediate programs don't use it during their operation; it's just passed through.

Re: Programmers are bad at managing state (2020)

#53

Post by RangerScience »

azornathogron wrote: post #23
RangerScience wrote: post #19

Popped in here to say that AFAIK/IMO, most of the things people treat as "state" is actually "data". And then I started thinking myself in circles around "okay, so what is state?". Rather than /keep/ thinking myself in circles, I'll ask: What do y'all think "state" is ?

State is data that you use in control flow decisions. (This is a 5-second reaction, not a deeply considered opinion, don't take it too seriously)

I like it! I don't know if I agree, but, the category of "data used in control flow" is a good one.

I think... maybe this definition needs a narrower category of control flow? Like, technically, if you're converting 24-hour time to 12-hour AM/PM time, you have control flow (if > 12 hours). IMO that seems like it shouldn't be state. But, "we've delivered this message, so don't try to deliver it again" definitely involves control flow and definitely feels like state. Something like "this list is sorted" is in-between; it's re-computable (easily, depending on list size), if it's not done you want to do it, but after that it doesn't affect control flow.

Maybe the difference is "control flow that modifies other data"?

Re: Programmers are bad at managing state (2020)

#54

Post by rsc »

rhelz wrote: post #20

We actually have a great tool to manage state, but nobody seems to have used it to its full potential: regular expressions. Imagine your program is a big state machine, and inputs and other events are making it transition from one state to another, and when in a state the apropos actions are performed. On this view, your program just is a regular expression parser--the tokenized stream of input events is what it is p…

Perhaps this comment was meant as a joke, but this is exactly what lex does for regexps and yacc does for LALR(1) grammars. For the right job, they are both great.

I watched Ken Thompson write a Paxos implementation in yacc once.

Re: Programmers are bad at managing state (2020)

#55

Post by rhelz »

rsc wrote: post #54
rhelz wrote: post #20

We actually have a great tool to manage state, but nobody seems to have used it to its full potential: regular expressions. Imagine your program is a big state machine, and inputs and other events are making it transition from one state to another, and when in a state the apropos actions are performed. On this view, your program just is a regular expression parser--the tokenized stream of input events is what it is p…

Perhaps this comment was meant as a joke, but this is exactly what lex does for regexps and yacc does for LALR(1) grammars. For the right job, they are both great. I watched Ken Thompson write a Paxos implementation in yacc once.

> Perhaps this comment was meant as a joke

Nope, not a joke. As you say, this is just the application of parsing technology to a tokenized stream of input events.

its super-useful in creating state machines to do parsing---and it can be super-useful to create state machines for other things as well.

> I watched Ken Thompson write a Paxos implementation in yacc once.

In real time? dude, you gotta post video to youtube or post a "Tell HN" story about it.

Re: Programmers are bad at managing state (2020)

#56

Post by rhelz »

jonstewart wrote: post #47
rhelz wrote: post #20

We actually have a great tool to manage state, but nobody seems to have used it to its full potential: regular expressions. Imagine your program is a big state machine, and inputs and other events are making it transition from one state to another, and when in a state the apropos actions are performed. On this view, your program just is a regular expression parser--the tokenized stream of input events is what it is p…

Regex with callbacks? Congrats, you’ve reinvented lex.

Wow, you are right. The first sentence of the abstract of Lesk & Schmidt's paper:

"Lex helps write programs whose control flow is directed by instances of regular expressions in the input stream."

Exactly what I was talking about. There's no reason to suck at state management, guys....

Re: Programmers are bad at managing state (2020)

#57

Post by rsc »

rhelz wrote: post #55
rsc wrote: post #54

Earlier quoted context omitted.

Perhaps this comment was meant as a joke, but this is exactly what lex does for regexps and yacc does for LALR(1) grammars. For the right job, they are both great. I watched Ken Thompson write a Paxos implementation in yacc once.

> Perhaps this comment was meant as a joke Nope, not a joke. As you say, this is just the application of parsing technology to a tokenized stream of input events. its super-useful in creating state machines to do parsing---and it can be super-useful to create state machines for other things as well. > I watched Ken Thompson write a Paxos implementation in yacc once. In real time? dude, you gotta post video to youtube…

It's not as exciting as it sounds. He wanted to play around with learning Paxos, which is a big state machine, and he used yacc to do it. I shared an office with him for a couple years in the early days of Go, and he was working on it while I was working on other things. I helped him track down at least one bug in the Go port of yacc that way. I think the grammar he was writing was completely regular, but yacc is nicer to use than lex.

Ken discussed yacc briefly in Coders at Work, which I quoted at https://research.swtch.com/yyerror:

Seibel: And are there development tools that just make you happy to program?

Thompson: I love yacc. I just love yacc. It just does exactly what you want done. Its complement, lex, is horrible. It does nothing you want done.

Seibel: Do you use it anyway or do you write your lexers by hand?

Thompson: I write my lexers by hand. Much easier.

Re: Programmers are bad at managing state (2020)

#58

Post by rhelz »

rsc wrote: post #57
rhelz wrote: post #55

Earlier quoted context omitted.

> Perhaps this comment was meant as a joke Nope, not a joke. As you say, this is just the application of parsing technology to a tokenized stream of input events. its super-useful in creating state machines to do parsing---and it can be super-useful to create state machines for other things as well. > I watched Ken Thompson write a Paxos implementation in yacc once. In real time? dude, you gotta post video to youtube…

It's not as exciting as it sounds. He wanted to play around with learning Paxos, which is a big state machine, and he used yacc to do it. I shared an office with him for a couple years in the early days of Go, and he was working on it while I was working on other things. I helped him track down at least one bug in the Go port of yacc that way. I think the grammar he was writing was completely regular, but yacc is nic…

> It's not as exciting as it sounds.

De Gustibus. Some of us are into that sort of thing. Thanks for the link.

> Thompson: I write my lexers by hand. Much easier.

LMAO. If you've been doing it since the 60's, I suppose you get the hang of it:

Ken Thompson, “Regular expression search algorithm,” Communications of the ACM 11(6) (June 1968), pp. 419–422

Re: Programmers are bad at managing state (2020)

#59

Post by rhelz »

glangdale wrote: post #46
rhelz wrote: post #20

We actually have a great tool to manage state, but nobody seems to have used it to its full potential: regular expressions. Imagine your program is a big state machine, and inputs and other events are making it transition from one state to another, and when in a state the apropos actions are performed. On this view, your program just is a regular expression parser--the tokenized stream of input events is what it is p…

This would be, speaking as someone who has dealt with his share of state machines, quite confusing. The uncomfortable thing about regular expression implementation as automata is either (a) non-determinism (i.e. "being in many states at once" a la Glushkov or Thompson NFAs, not "non-determinism meaning something different might happen on any given execution") or (b) state explosion (in a DFA, to represent non-determi…

re: nondeterministic implementations: Detecting and resolving nondeterminism is something every method of implementing state machines has to consider. Even when implementing a state machine by hand coding switch statements, you have to worry about whether or not you have inadvertently specified an indeterminism.

> interesting things beyond the finite automata space

State machines certainly can be glorified into LR parsers, or even into Turing machines by adding various bells and whistles. So sure, this idea shouldn't be limited to just regular expressions--we've got good methods of specifying even very complicated state handling.

I hope you saw the excellent comment on this thread where somebody talked about how Ken Thompson implemented paxos using yacc for state management. I've been around the block with state management too, but using yacc for state management is something that never occurred to me, and frankly, opens up a whole new world of possibilities.

BTW, it's also an answer to your point about the pitfalls of nondeterminism: yacc is a great example of how to specify a state machine while detecting, reporting, and resolving nondeterminism.

Re: Programmers are bad at managing state (2020)

#60

Post by 0xbadcafebee »

paulddraper wrote: post #49
0xbadcafebee wrote: post #43

Earlier quoted context omitted.

Those aren't really like building codes. Building codes are effectively minimum specifications for safety, with the requirement that they can be inspected and approved. The codes eventually became more uniform, but their original intent was to prevent shoddy workmanship from creating hazardous conditions. SOC II and ISO 27001 have to do with security, which is close to safety, but not the same. GDPR and HIPAA are con…

> their original intent was to prevent shoddy workmanship from creating hazardous conditions And therein lies the difference...a building collapsing will kill its tenants. Software collapsing will make someone late for dinner. When software is critical, there are safety standards: DO-178C, DO-330, ISO 13485, ISO 14971, etc.

Software has significant effects on people that isn't immediately apparent to the designers.

I'm sure that the contractors who designed accounting software for the UK Post Office didn't expect to ruin the lives of hundreds of people. https://www.bbc.com/news/business-56718036

I'm sure the designers of Facebook didn't mean to inspire a mental health crisis for young people. https://www.sciencenews.org/article/social-media-teens-menta...

I'm sure the designers of GPS software didn't mean for hundreds of people to drive into lakes while blindly following the GPS. https://duckduckgo.com/?t=ftsa&q=google+maps+errors+lead+to+...

I'm sure the designers of predictive policing software didn't mean to racially discriminate. https://www.technologyreview.com/2020/07/17/1005396/predicti... Same for facial recognition software. https://jolt.law.harvard.edu/digest/why-racial-bias-is-preva...

The longer that we continue to be flippant about the impact of software on the lives of people, the longer people will suffer due to our laziness and unprofessionalism.

Post reply on HN