Yesno

Hey and welcome to yesno. Gödel proved that any substantial logic (i.e., capable of proving awesome things) can be either consistent or complete, but it can't be both. As there's a direct correspondence between logics/proofs and programming languages/programs, we have a similar choice when designing programming languages. Any universally powerful programming language must either offer consistent semantics, or allow the possibility of programs not halting.

Almost all programming languages to date choose consistency. Consistency is easier to learn and reason about, and anyway incompleteness doesn't show itself very often in well-written programs. But, it does show up. There are cases where programs can be written to not terminate, or where execution takes a very long time, and some results are still needed.

Yesno is an inconsistent and complete programming language, and that every program returns a value. Actually we can say something a bit stronger than that. Consider even nonsensical programs such as return a. will return a value (specifically, that program will yield a value of fail, because the variable a is not bound). We can say that if a program is written such that a variable is never referenced without being assigned a value, and a message is never sent to an object without a method first being assigned to that object, then that program will return a value other than fail, i.e., a useful value. This has yet to be proven, but it was a design consideration.

Further, we can say that if a yesno program does terminate (as if by consistent semantics), it will eventually return the correct answer, and only the correct answer.

The general method of operation for yesno is to immediately return a number of answers—possibly 0 in the case of fail, or possibly hundreds or thousands. If many values are returned, obviously at least some of those must be wrong, and hence the computation must have been inconsistent. However, as time progresses, computation continues, and the correct answer can be "narrowed down". If the program halts, then eventually it will be narrowed down to only the correct answer.

Unfortunately there is no guarantee that one of the values returned is always the correct answer. E.g., it is possible to write a program which initially returns only the value fail, and then after completing successfully, returns the value true. It would be desireable for the program to initially return the value, e.g., {false, true}. However, common yesno programming practices can help ensure that the correct answer is one of those returned at all times.

Downloading and running yesno

By the way, here is my presentation. Yes, a lot has changed since then ;)

There are two ways to get yesno running on an OS X machine (I haven't tried it on any other platforms):

  1. If you have a PPC OS X machine, you can:
    1. Download yesno.tar.gz.
    2. Extract yesno.tar.gz
    3. Run the yesno binary inside of there
  2. Otherwise:
    1. Download yesno.tar.gz.
    2. Extract yesno.tar.gz
    3. Install libgc, e.g., as fink install libgc
    4. make clean
    5. make
    6. Run the yesno binary created

Note that yesno reads its program from standard input.

Known issues

Sadly, the yesno interpreter is not of production quality yet, and is really only useful for playing around with. The biggest problems so far are:

  1. It has only been tested on PowerPC OS X. I can't say for sure how it will react on other platforms. Theoretically, as long as you have gcc (yesno uses some gcc extensions) and libgc, it should work, though.
  2. libgc does not behave properly, at least on PowerPC OS X. Sadly, libgc occasionally reclaims memory which is reachable. This means that in large programs where memory is being reclaimed a lot, variables and methods sometimes disappear. It's been hacked around enough that it will work on toy examples, however.
  3. There appears to be a small bug in the variable assignment semantics, though I haven't been able to separate this from the memory reclamation issue.

Long story short, don't expect complex code to run properly at this time.

More documentation on yesno

  1. Classical semantics
  2. Inconsistent semantics

Future directions

There was one major design decision which complicated development tremenously: the creation of an object-oriented language. This decision was based on the ability to then compare yesno to similar programming languages. As nearly all computer scientists will have great familiarity with object-oriented programming languages, it becomes more apparenty to them the inconsistency present in yesno and its utility. This is in contrast to, for example, logic programming languages, where the existence of inconsistency would be seen more strictly as academic.

That said, even with such a minimalist object-oriented language, the semantics of inconsistency were quite unwieldly, and are still not completely specified. A simpler inconsistent language should be developed, such that its semantics and their implications can be studied more formally.

The other partial failing of yesno is in its allowance to not return the correct value. It would be beneficial if the language itself could force the correct answer to be returned (possibly in addition to a number of incorrect ones). It's not hard to do this: one could imagine that initially we return all values. However, for lack of better formalism, such a language would not be useful in any sense. Yesno was designed first and foremost, if not to be a useful language, at least to be prototypical of one. The intermediate results returned by yesno are supposed to be plausibly returned by the program.

One idea for forcing the return of the correct answer, is to force the programmer to classify variables as being inconsistent or consistent, where only inconsistent variables can be returned from closures. Upon declaring an inconsistent variable, the total set of allowed values must be declared up front. Thus, the language knows which values can be returned. This may become unwieldly for some programs, e.g., where one is dealing with ranges of numbers.

The existence of yesno, however, demonstrates that there is more room for research into inconsistent languages, particularly in determining the balance in the language between the inconsistency and the utility or "usefulness" of its inconsistent answers.