[tonyg]

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 conditionals, though - even without data, as such! An example is the lambda calculus. If you want to learn more about this, read up on "Church encoding" and "Scott encoding".

The basic idea is to use functions and the visitor pattern to encode a kind of conditional behaviour that varies with the input supplied to it.

  True = (lambda (t f) (t))
  False = (lambda (t f) (f))
  If = (lambda (b tr fa) (b tr fa))

  (lambda (x)
    (If x
        (lambda () (display "It was true!"))
        (lambda () (display "It was false!"))))

Desk check the reductions of applying that function to True and to False. The "t" and "f" arguments to the boolean values act as a kind of "menu" (the visitor pattern), from which the datum selects in order to communicate what variant of data it is. The pattern extends readily to natural numbers, lists, and so on, giving a straightforward encoding of not only conditionals, but also (one-layer-deep) pattern matching.

[AnimalMuppet]

> There are Turing-complete languages without conditionals, though...

> ... giving a straightforward encoding of not only conditionals, but also (one-layer-deep) pattern matching.

So you wrote a conditional out of something that didn't have one? But for that to work, something in the "If" has to decide whether to evaluate the first one or the second one. That is, there is something that is equivalent to a conditional somewhere in the parts that you use to build the "If".

This may come down to what the definition of "conditional" is, though...

[q_eng_anon]

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)

[tonyg]

Yes, because the machine language of ordinary CPUs uses a specific model of computation where branch instructions are the only way to effect conditional control transfer. But the idea of conditional control transfer is there in every interesting programming language to allow a program to react to its inputs.

[q_eng_anon]

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.

[cardiffspaceman]

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.

[tonyg]

Yes, this is right except that the language as written is eager Scheme. You don't need a lazy system. The second and third arguments to If are nullary procedures. Their effects are delayed until invoked by whichever of True or False is supplied. Scheme's notation for invoking a nullary procedure -- `(t)`, vs `t` which just refers to the procedure -- doesn't help matters here :-)

[tonyg]

The syntax is close to Scheme and with small changes will run in a Scheme interpreter. For example, here's a session at the REPL of Racket:

  ~$ racket
  Welcome to Racket v7.2.0.6.
  > (define True (lambda (t f) (t)))
  > (define False (lambda (t f) (f)))
  > (define If (lambda (b tr fa) (b tr fa)))
  > (define P (lambda (x)
                (If x
                    (lambda () (display "It was true!"))
                    (lambda () (display "It was false!")))))
  > (P True)
  It was true!
  > (P False)
  It was false!
  > 

Seen differently, it's also close to the mathematical notation of the lambda calculus.

To learn about the lambda calculus, check out chapter 5 of "Types and Programming Languages", Benjamin C. Pierce, MIT Press 2002. You might also get something out of "Semantics Engineering with PLT Redex", Felleisen, Findler & Flatt, MIT Press 2009.

[tonyg]

Oh, see also https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin... for a quick overview of Church and Scott encodings. (Ignore the stuff about Mogensen-Scott. Also, you'll need to have played around with lambda calculus a bit for this stuff to make sense. This kind of thing might be helpful: https://jacksongl.github.io/files/demo/lambda/index.htm)