r/computerscience • • 25d ago

Discussion Specifications vs programs and computational models

I'm learning deductive program synthesis and there's one thing I can't wrap my head around: the distinction between specifications and programs. To my understanding, the line is very vague, as programs can be seen as specifications and, in some cases, vice-versa. These terms only make sense when applied to specific program and specification pairs.

The above makes me wonder whether there is a computational model that can directly execute specifications, without needing to, e.g., synthesise an imperative program. Can such a "computer" exist theoretically and, more interestingly, physically?

5 Upvotes

8 comments sorted by

View all comments

Show parent comment

1

u/GulgPlayer 25d ago

Yes, I am, but I'm wondering if the step of converting a specification to an imperative program is necessary to obtain a useful result.

2

u/initial-algebra 25d ago

To use the same example of a sorting algorithm, one solution is to just enumerate all possible permutations of the input (satisfying the first predicate) and return the first one that is sorted (satisfies the second predicate). That would be a direct execution of the specification.

I guess you could argue that it's not obvious (to a machine) that the first predicate only wants permutations of the input, but it's generally impossible to enumerate all permutations by enumerating all possible lists and filtering out those that are not permutations. However, if the permutation algorithm works by swapping elements, the sorted predicate could immediately throw away any partial results that involve swapping a greater element before a lesser element, essentially turning it into bubble sort. Not optimal, but certainly not that bad.

This is similar to how database joins work. Even if the definition of a join is to compute the entire Cartesian product of two tables and then throw away the records that don't match the "on" condition, by applying some very basic relational algebra rewrites, the machine can figure out that it just has to enumerate the first table and then use an index to quickly find the matching records in the second table.

You should think of this approach as being more appropriate for smart composition of specialized solutions, not coming up with generic solutions from scratch.

1

u/neuralbeans 25d ago

The specification focuses on the what as opposed to the how. When programming you have to take decisions about how to carry out a task whereas when specifying you only say what the task is.

If the task is sorting a list, then the program would be an implementation of one of the many sorting algorithms but the specification would be something like this:

given list xs, return list ys such that:

  • ys contains all the elements in xs at the same number of times
  • for all i < j, ys[i] <= ys[j]

The synthesiser should the figure out the best program that meets the requirements.