Speaking computer science in mathematicalese

Question

I am in the process of writing a fairly long monograph on a computer science topic. However, I usually find myself in a position of having to write some computer science concept in mathematical terms, and it is difficult to me. For instance, say I want to write a for-loop or a void function. I do most of the time go to my Knuth or Cormen or Sedgewick, but they are not enough now. Is there a "manual" or some text I can take as example to translate computer science into mathematics?

EDIT: Let me be more specific (thanks, Uri). What I mean is: For example, I have a function that is void, and it returns a random string of length n. This caused my curiosity, I dont even know how to represent void function in in math... but again, this is just an example. I'm plagued by these kinds of questions. Thank you.

Answer 1

I think you have to be more specific. Are you talking about translating algorithms? Writing code as pseudocode?

There are many more "mathematical" formalisms, many of them are used in formal verification of programs. They are usually based on discrete mathematics.

Depending on what you're trying to do, Hoare Logic is a good way of representing the steps of algorithms, IMHO.

You could also formally specify some architectures and protocols using the Z notation.

Answer 2

Summation or product notation can probably replace some for-loops. Others can probably be expressed as logical quantifiers ("There exists i such that a[i] has some property" or "a[i] has some property for all i"). (Sorry I don't know how to render these in Markdown...hope you get the idea.)

"Void functions"...hmmm, maybe some convenient logical notation to state preconditions and postconditions, since such functions are only useful for their side effects?

But I think most mathematicians will be familiar enough with descriptions of algorithms to understand any halfway reasonable pseudocode convention. Just try to stay away from anything that requires a "language-lawyer" skill level in some particular programming language.

Answer 3

To address your specific question: in mathematics, if it takes no arguments and returns a random string of length n, it probably isn't a function at all! That is, if f() is not equal to f() (e.g., with f() = rand()) then by definition f() isn't a function. You can solve this in different ways, depending on your preferences: you could pass it the state parameter and have it return the modified state parameter, or you could make it a multivalued function and return all possible values, or you could use two functions: f(n, state) gives the next random string of length n while g(n, state) gives the new state after generating f(n, state).

Answer 4

You could look into Elements of Programming by Alexander Stepanov and Paul McJones :

This book applies the deductive method to programming by affiliating programs with the abstract mathematical theories that enable them to work. Specification of these theories, algorithms written in terms of these theories, and theorems and lemmas describing their properties are presented together. The implementation of the algorithms in a real programming language is central to the book. While the specifications, which are addressed to human beings, should, and even must, combine rigor with appropriate informality, the code, which is addressed to the computer, must be absolutely precise even while being general.