1
$\begingroup$

I am trying to define an If statement, but am stuck because the definition/implementation of If is circular from what I have tried. For example, here is one definition:

class If {
  provide: Condition
  provide: TrueBlock
  body:
    If (Condition) {
      call(TrueBlock)
    }
}

You can then use it like this:

If (true) {
  Something()
}

But the thing is, the definition itself uses If to define it:

class If {
  ...
    If (Condition) {
      call(TrueBlock)
    }
}

The only other way I can think of defining it is by saying that an If statement is an "atomic statement", and so it doesn't have an implementation. (The compiler or whatever would then have special instructions to treat it uniquely).

class If {
  provide: Condition
  provide: TrueBlock 
}

That would be the whole definition of If. No implementation required.

Wondering if this is sort of the right approach to this problem. The problem being that you can't really implement an If statement without resorting to using If itself. And so you define it as atomic.

$\endgroup$
  • 2
    $\begingroup$ The main obstacle is perhaps that you're attempting to define the semantics of a syntactic construct in the very same syntax. This fails often. Other examples of this failure include M Spivey's first book on the Z specification language. (Its essence was that everything meant $\bot$ even though that wasn't intended.) $\endgroup$ – Kai Jul 1 '18 at 12:33
4
$\begingroup$

One general rule of Turing completeness is that you need some form of conditional branching built into your model. A Turing machine, for example, can transition to a new state based on what it sees on the tape. Programming-language-wise, a while loop works, as does an infinite loop with a conditional break statement, or if and goto.

As such, if you have no form of conditional branching built into your model already, you can't create one out of nowhere—if your model isn't Turing complete, you'll need to add something else from outside to the model to make it so.

An "atomic" if statement will do the trick, certainly, as will something like Lisp's conditional. But whatever it is, it'll have to be implemented by the compiler or interpreter, rather than being created within the language itself.

$\endgroup$
  • 2
    $\begingroup$ What is the form of conditional branching in the lambda calculus? (Certainly, you need to be able to mimic conditional branching to some extent.) $\endgroup$ – Derek Elkins left SE Jul 1 '18 at 4:54
  • $\begingroup$ @DerekElkins I would like to know that too (regarding the Lisp conditional comment). $\endgroup$ – Lance Pollard Jul 1 '18 at 4:59
  • $\begingroup$ @Draconis wondering if there is a name for this sort of property/thing: "whatever it is, it'll have to be implemented by the compiler or interpreter". I have run into this in a few cases and if it had a name it would be easier to understand I think. $\endgroup$ – Lance Pollard Jul 1 '18 at 5:00
  • 3
    $\begingroup$ @DerekElkins I'd say that the conditional is λc:λa:λb:c.a.b. In other words, apply the Church boolean c to a and b, returning a if c is true, and b if c is false. $\endgroup$ – Draconis Jul 1 '18 at 5:01
  • 2
    $\begingroup$ @LancePollard "primitives" is sometimes used for the basic building blocks of a language, which are implemented at a lower level. (Sometimes, though, a primitive could be implemented in terms of the other ones, so it's slightly different from what you ask.) $\endgroup$ – chi Jul 1 '18 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.