A computer program is a description of a process which is formal enough to be carried out by a machine.Most of the other definitions describe a program as a ‘set of instructions’. Some of the definitions suggest that these instructions should be organized in some way, perhaps as a (linear) list. These instructions ‘make the computer do things’, ‘bring about a certain result’, ‘cause the computer to behave in a predetermined manner’, or ‘alter the contents of memory’. But these definitions have an explicit or implicit assumption: a sequential, imperative mode of thought.
Look at this Prolog code:
append(c(H,T), B, c(H,TB)) <= append(T, B, TB). append(nil, B, B).This code describes relationship of appending lists, but it doesn't specify how to accomplish the appending. Is the first clause an ‘instruction’ to build a list, or to take one apart? Are the clauses to be run in any particular order? Is there a deterministic ‘answer’?
That’s interesting. I suppose—if you wanted to stick to those other definitions—you could say that the Prolog code isn’t actually a program but a specification of a program. The interpreter is a program that creates another program from that specification. Or something like that.
ReplyDeletePardon the really late reply, but I missed this article the first time around.
ReplyDelete> This code describes relationship of appending lists, but it doesn't specify _how_ to accomplish the appending.
I'm going to claim this to be patently false, as you said earlier:
> Look at this _Prolog_ code
(emphasis mine) By saying it's Prolog code, you've tied some semantics to the code; not only about the relationships, but how those relationships are to be _executed_. Prolog specifies a unification algorithm, which paired with any Prolog program, specifies an algorithm for computing results.
If that were not the case, I could claim equally, that the following Scheme code also specified only relationships, and not how to compute the results:
(define (append L1 L2) (if (null? L1) L2 (cons (car L1) (append (cdr L1) L2)))
; the other functions specified by the Prolog program are left as an exercise for the reader.
See, my Scheme program doesn't specify how -- I didn't provide a specification of how Scheme is to interpret execution of the 'if' form for instance. All I specified was a relationship between the form (append _ _) and two legal substitutions such an interpreter could make.
~~~
Don't take this as a disagreement though. I think your argument is really more universal. _All_ code can be seen as specifications for programs, rather than the programs themselves. For instance, A Scheme interpreter might look at my append and realize it could implement it in constant space. I've only specified constraints on the observable behavior of the program, and "call stack" space is not one of them. :-)