Type, operation and function, and their limits

First of all, sorry for my English.

I would like to know, when I want to define a new type (I'm currently developing a computer interpreted language), how can I determine which "functions" are fundamental operations for a particular type, and which "function" are external, in the sense that, I don't need this function to define the characterization of the type?.

Let me call "operations" to the "essential functions" of the type and "functions" to anything else that simply uses the type.

For example, we all agree (I suspect), that the sum, difference, product and division are good examples of "operations" that defines the type integer for example, or number in general, but an operation like factorial is more a function.

The question is, in a more general or theoretical point of view, where is the line between "function" and "operation" for the intended purpose? For example, for more abstract types like domain-specifics data structures, auxiliary classes or something more difficult than a "number", how or which test can I perform to say: that's a good as operation, or that's better being a function.

• The Church-Turing thesis shows us that no particular choice of operators is fundamental. There are many ways to achieve computation. The $\lambda$-calculus does this with just variables, abstraction and application. The $\pi$-calculus uses parallel composition, hiding and (asynchronous) pure message passing. Conways's game of life has an infinite number of cells continually exchanging one bit of information with it's 8 neighbours etc. – Martin Berger Aug 14 '13 at 13:19
• My question is more like thinking about types as an algebraic structure. Set of data + operations that work over elements in this set. For example, set of natural numbers and operations that performs an arithmetic, being this "arithmetic" the fundamental set of operations to define the nature of a "natural". I don't try to define "fundamentals of computation" or something like that, but "domains of computation"; more or less as 'axiom' does (axiom-developer.org). – Peregring-lk Aug 14 '13 at 14:30
• But you can typically set up data and operations in different ways. For example arithmetic (understood as Peano arithmetic) can be set up using ZF set-theory with the Axiom of Infinity negated (IIRC, please correct me if I'm wrong). That's a theory that doesn't have addition or multiplication as primitive operations. Algebraic operators and axioms can usually be defined in different ways. The choice is usually based on preference. – Martin Berger Aug 14 '13 at 18:24
• That's mean, there are no criteria to create a frontier between "function" and "operation" from a more algebraic point of view? For example, is there no criteria to say "the function/algorithm that performs the calculation of the minimum spanning tree of a graph, isn't a defining operation of the type graph because of ..."? Are there no criteria to complete the "..." part? Not even for practical purposes? – Peregring-lk Aug 14 '13 at 19:17
• You can impose constraints, like minimal number of algebraic operators to achieve this/that/the other degree of expressivity. But I doubt it's easy to show that any chosen non-trivial algebra is minimal in this sense, and I also doubt that there's always a unique minimal axiomatisation. Please think about complexity theory and in particular complete problems and reductions for a given complexity class: for example there are 1000s of NP-complete problems that are poly-time or log-space reducible to each other. – Martin Berger Aug 15 '13 at 10:24

Depends on your definition of "fundamental". As Martin said, you can do pretty much anything with the few primitives in lambda calculus, for instance, or simply anything that is Turing complete. However, would that be useful in your problem domain?

I don't know the specifics of your language, but you should have some use in mind for it. Depending on its intended use, you may want to have certain operations as builtins. For instance, MATLAB is specialised to work with matrices, so it has a lot of built-in operations for them.

In summary: decide what is your language supposed to be good for, and tweak your types and operations to that effect.

There are two kinds of operations that I'd make into built-ins:

• those that can't be implemented by the user of your language without breaking the intended abstraction (i.e. accessing implementation details). For instance, I'd need something to increment an integer variable by 1.

• the operations that are commonly used and that can be made much more efficient and/or convenient by taking advantage of implementation details. I could use a loop to increment something by 5, but it'd normally be much more efficient to do it in one go.