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

Ask HN: Why Are Conditionals Important?

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 35 posts

Re: Ask HN: Why Are Conditionals Important?

#11

Post by ktpsns »

Conditionals actually destroy information. The way they are written does not even matter; Consider the evaluation of this functional pseudocode:

   min(a,b) := if(a
Obviously, the evaluation of this function looses information about either a or b. This is of course by intention. But this is incompatible to a closed (quantum) system where information must be preserved.

Interestingly (but I think there is no deeper connection), vectorization uses masks to avoid branching. Programmatically, one implements then both branches at the same time, and on a per-data level different operations are performed. A simple pseudo-numpy example would be

   B[where(A
One can write long programs following this paradigm which frequently excel at performance at GPUs and modern day CPUs (which are actually vector machines).

Re: Ask HN: Why Are Conditionals Important?

#12

Post by q_eng_anon »

tonyg wrote: post #9

Conditionals allow a program to react to the data it is presented with. This can be data from the outside world, or data from some other module internal to a program composed out of modules (i.e. subroutines, for example). Without conditionals - or their moral equivalent - programs would not be able to react to their inputs or to changes in their internal state. -- There are Turing-complete languages without conditio…

this is interesting - thanks for your response.

I'm having a hard time understanding the program you supplied though, the subsequent description did not really help (probs more my fault than your own). I certainly understand the visitor pattern (and have had a sneaky suspicion it is important) but the lambda calculus, not so much.

What type of syntax is the program you supplied in - is it more of a pseudocode or an actual formal language?

thanks for the search keywords - definitely helped - if you have a favorite textbook/arxiv reference/author on this stuff, those would be greatly appreciated as well.

Re: Ask HN: Why Are Conditionals Important?

#13

Post by q_eng_anon »

ktpsns wrote: post #11

Conditionals actually destroy information. The way they are written does not even matter; Consider the evaluation of this functional pseudocode: min(a,b) := if(a Obviously, the evaluation of this function looses information about either a or b. This is of course by intention. But this is incompatible to a closed (quantum) system where information must be preserved. Interestingly (but I think there is no deeper connec…

thanks for tying it back into quantum - also for the clarification that the way you write them doesn't matter - whether that be in terms of if/else, switch statements or actual CPU-level branch instructions.

Re: Ask HN: Why Are Conditionals Important?

#14

Post by saltcured »

rowanG077 wrote: post #10
tlb wrote: post #7

Earlier quoted context omitted.

It's not as much of a limitation as people think. One pattern is for the program to update a state every (fixed-length) iteration. You can build any arbitrary computation on top of that.

Can you provide an example? I have a hard time believing any arbitrary computation can be build without conditionals.

I suspect they are thinking about things like cellular automata.

If you squint just right, you may think there are no conditionals. Just straight-line data flow to compute cell values based on a fixed neighborhood of the preceding state. A big fluid dynamics simulation has a similar characteristic.

However, this squinty interpretation can just as simply show you that the whole thing is just a DFA, as mentioned a few posts up! The finite mutable register just encodes the name of each state in the state machine, and each simulation cycle is just computing the next state transition within that large but finite state space.

Re: Ask HN: Why Are Conditionals Important?

#15

Post by q_eng_anon »

tonyg wrote: post #9

Conditionals allow a program to react to the data it is presented with. This can be data from the outside world, or data from some other module internal to a program composed out of modules (i.e. subroutines, for example). Without conditionals - or their moral equivalent - programs would not be able to react to their inputs or to changes in their internal state. -- There are Turing-complete languages without conditio…

Also, say I implement the visitor pattern in some language on a classical machine - aren't there branch instructions being used under the covers anyway?

(the code will probably be more optimized / easier to optimize for the compiler but you get my point)

Re: Ask HN: Why Are Conditionals Important?

#16

Post by psv1 »

To simplify, software (generally) does this:

    input >>> output
By definition the output is conditional on the input, at least if the program works correctly. That's why conditional statements are important - they express the relationship between input and output.

Isn't this really basic stuff? Or am I missing something?

Re: Ask HN: Why Are Conditionals Important?

#17

Post by rowanG077 »

saltcured wrote: post #14
rowanG077 wrote: post #10

Earlier quoted context omitted.

Can you provide an example? I have a hard time believing any arbitrary computation can be build without conditionals.

I suspect they are thinking about things like cellular automata. If you squint just right, you may think there are no conditionals. Just straight-line data flow to compute cell values based on a fixed neighborhood of the preceding state. A big fluid dynamics simulation has a similar characteristic. However, this squinty interpretation can just as simply show you that the whole thing is just a DFA, as mentioned a few…

But cellular automata have conditionals. That is the entire point of having a state in each cell and then doing something based on that state.

Re: Ask HN: Why Are Conditionals Important?

#18

Post by q_eng_anon »

psv1 wrote: post #16

To simplify, software (generally) does this: input >>> output By definition the output is conditional on the input, at least if the program works correctly. That's why conditional statements are important - they express the relationship between input and output. Isn't this really basic stuff? Or am I missing something?

mind bottling stuff here man thanks

Re: Ask HN: Why Are Conditionals Important?

#19

Post by cardiffspaceman »

q_eng_anon wrote: post #12
tonyg wrote: post #9

Conditionals allow a program to react to the data it is presented with. This can be data from the outside world, or data from some other module internal to a program composed out of modules (i.e. subroutines, for example). Without conditionals - or their moral equivalent - programs would not be able to react to their inputs or to changes in their internal state. -- There are Turing-complete languages without conditio…

this is interesting - thanks for your response. I'm having a hard time understanding the program you supplied though, the subsequent description did not really help (probs more my fault than your own). I certainly understand the visitor pattern (and have had a sneaky suspicion it is important) but the lambda calculus, not so much. What type of syntax is the program you supplied in - is it more of a pseudocode or an a…

The syntax is concise definition of named values where the values are all anonymous functions.

True = (lambda (t f) (t))

-- Let True be the function that takes two parameters t and f and returns the first, t. --

False = (lambda (t f) (f))

-- Let False be the function that takes two parameters t and f and returns the second, f. --

If = (lambda (b tr fa) (b tr fa))

-- Let If be the function that takes three parameters, and applies the first parameter b to the second and third parameters. --

Notice that if the parameter b is the True value above, 'b tr fa' will return 'tr'. If 'b' is False, 'b tr fa' will return 'fa'

  (lambda (x)
    (If x
        (lambda () (display "It was true!"))
        (lambda () (display "It was false!"))))
So it follows that this will pass either "It was true!" or "It was false!" to 'display', waving aside all the stuff you have to define that makes 'display' and STRINGS work as you'd expect.

This is where it becomes clear that you need a lazy system for this to make sense. In an eager system all three of the parameters to 'If' are evaluated and then their values are substituted into the body of 'If'. In a lazy system the expressions for the values are substituted for the parameters in the body, so only the parameter 'b' and one of the other parameters will be evaluated.

When I play around with functional languages I would just write

  True t f = t
  False t f = f
  If b tr fa = b tr fa
  ShowIt x = If x (display "It was true!") (display "It was false!")
You could also write this in (I think this is) Scheme:

  (define True (t f) (t))
  (define False(t f) (f))
  (define If (b tr fa) (b tr fa))
  (define ShowIt (x) (If (x (display "It was true!") (display "It was false!"))))
Except that Scheme isn't usually lazy.
Post reply on HN