Monday, April 18, 2011

Is vs Ought in Computer Science

In philosophy, we debate what something is versus what it ought to be.  And often the usage is confounded.  In thinking about functional programming, I recalled this debate.

A functional program declares what ought to occur.  The computer has large leeway in how it will successfully execute this program.  In contrast, an imperative program declares what will occur.  The computer has little leeway in executing this program.

In programming imperatively, we can more clearly reason about the specific execution time / space required, as we can know the fullest details about the program.  Each step and instruction is clear, along with the specific allocation points to comprehend the memory usage.  Yet, this model effectively went away over 20 years ago, with superscalar processors and overall program complexity.

A common fallacy that programmers make is to try to reason about the details of execution time.  Questions are pondered like should an increment be "++" or "+= 1"?  Would it make you feel better to know I can construct cases where one executes faster than the other?  Most programmers who want to reason about their program are not sufficiently equipped to do so.

Lest we discard this benefit of imperative programming entirely, there are other decisions that are still within reason.  For example, the specific layout of the data in a structure can have impact on execution time.  And while it is doable by hand, the response I received from other programmers is "can't the compiler do this for me?"

Fine.  Let's only program with what the application ought to be doing.  The compiler / run-time / operating system all serve to take these statements of ought and make them be.  Still someone must reason about the is of programs, unless we have a processor that directly takes the functional statements.

I shall continue to be skeptical about programming functionally; however, I advocate further support for stating the "ought" of program statements to aid the verification, etc that is so highly lauded.  Imperative programs need to contain more details about what the program ought to be doing, which can be used in interesting ways beyond mere verification of correct execution.  This direction is part of my research, which I look forward to discussing at HotPar 2011 - "Parallel Pattern Detection for Architectural Improvement".  The specifics of which I'll wait to discuss with the proceedings.