Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is there a phrase or word to describe an algorithim or programme is complete in that given any value for its arguments there is a defined outcome? i.e. all the ramifications have been considered whatever the context?

A simple example would be the below function:

function returns string get_item_type(int type_no)
{
  if(type_no < 10)
    return "hockey stick"
  else if (type_no < 20)
    return "bulldozer"
  else
    return "unknown"
}

(excuse the dismal pseudo code)

No matter what number is supplied all possibiblites are catered for. My question is: is there a word to fill the blank here:

"get_item_type() is ______ complete"

?

(The answer is not Turing Complete - that is something quite different - but I annoyingly always think of something as "Turing Complete" when I am thinking of the above).

share|improve this question
6  
"It's working"? –  KingCrunch Jun 11 '12 at 8:29
5  
If I remember my CS correctly that's actually a requirement for anything to be called an "algorithm" in the strict sense: it must finish in finite time with a defined result on every possible input. –  Joachim Sauer Jun 11 '12 at 8:33
    
how about "functional complete"? –  user281377 Jun 11 '12 at 8:34
    
I am actually struggling to find out what would be an algorithm where it is false that "given any possible value for its arguments there is a predicatable outcome". Ok, the C specification sometimes uses undefined behaviour, but even in this case implementations actually define one. Even random number generators can only be pseudo random, and look random because we do not consider in the input state such as the computer clock. –  Andrea Jun 11 '12 at 9:42
    
To be more precise, even if your example lacked the else clause, you still would have a pretty well-defined behaviour: either a compilation error, which means that you failed to specify correctly your algorithm after all, or some default return value, such as nil, depending on the language –  Andrea Jun 11 '12 at 9:44
show 9 more comments

3 Answers

up vote 13 down vote accepted

you could say it is a pure function

or if there is state to be considered besides the arguments you could say it is deterministic

share|improve this answer
14  
I'd go with deterministic. –  Berry Langerak Jun 11 '12 at 8:43
6  
For me pure function means that it does not have any other side-effects apart from the return value. I don't think that's required for the word the OP looks for. "deterministic" sounds more like it. –  Joachim Sauer Jun 11 '12 at 8:44
    
I thought about "deterministic" too, but IMO deterministic means more: a deterministic function's result only depends on the arguments, not on state. –  user281377 Jun 11 '12 at 9:00
    
having read up on deterministic - is does depend on the arguments - but also each state thereon is pre-determined: i.e. deterministic! –  markmnl Jun 11 '12 at 9:20
2  
Neither of these cover the meaning of being well-defined for all possible inputs. "Pure" means the function does not have any side effects, so that the same set of input invariably produces the same output; "deterministic" means that the function always has the same effect, given identical program state and inputs. –  tdammers Jun 11 '12 at 20:02
show 1 more comment

In Your Case...

In your particular example, what we have is a pure surjective (partial) function.

(Don't be mislead by the "partial". See below.)


To answer your question, we need to consider these:

Algorithms and Functions

Algorithms are implemented using either:

Functions

Functions can also considered as being either:

Function Types

Furthermore, consider the following types of functions from a mathematical perspective:

An Injective Function

A partial function where results are unique.

An Injective Function's Domain Correspondance

A Surjective Function

A partial function where results can overlap.

A Surjective Function's Domain Correspondance

A Bijective Function

A Total Function, both injective and surjective, where there's an output for all possible inputs, and where all possible outputs are distinct and obtained by a unique input, thus being perfectly paired.

A Bijective Function's Domain Correspondance

share|improve this answer
add comment

Mathematically speaking, the term you are looking for is "Total Function" (a function that is defined for every possible value in some domain), as opposed to a "partial function", which is only defined for a subset of the possible input values.

Note that, strictly speaking, mathematical functions are always total on their own domain; calling a function "partial" only makes sense if you offset it against another domain, such as the function f(x) = 1/x: the domain of this function is the domain of all real numbers except zero, but against the domain of all real numbers (including zero), it is partial.

In programming, the types of a function's inputs state a domain already, and by not defining the function for all of them, you could say that the function is partial. However, many programming languages fall back to a default behavior when you don't explicitly return anything - they may return 0, null, undefined, etc. Technically speaking, such functions are still total - they return a value for all possible inputs -, but conceptually, there are gaps in the definition. And not all programming languages feature such fallbacks; the alternatives are refusing to compile, responding with "undefined behavior", raising an exception, etc.

BTW, note that neither determinism nor purity have anything to do with this. A deterministic function is one that always has the same effect given the same context (relevant system state and inputs); a pure function is a function that does not have any side effects (so that it always returns the same value given the same inputs, regardless of any outside state, and without influencing outside state in any way). You can easily come up with a function that is partial, yet fully deterministic (provided that partial functions are legal in your programming language, and definition gaps are handled in a predicatable way); and conversely, if you manage to write a non-deterministic function, e.g. by reading from a hardware entropy source, there is no reason why it would have to be total (nor partial). The same goes for purity, unless a definition gap automatically introduces side effects (then all pure functions must also be total).

share|improve this answer
1  
+1. BTW any Turing complete language allows you to write a partial function by implementing an algorithm that will not terminate for at least some of the possible input values. (Still they are completely deterministic.) –  scarfridge Jun 11 '12 at 20:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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