Summary of Robert Kowalski work

Algorithm = Logic + Control

Hendrik Martina

Universidad Tecnologica de la Mixteca

February 6, 2019

Introduction

In "Logic + control", Robert Kowalski explains that an algorithm consist of

two components, the logic component gives the meaning of the algorithm and

the control component defines the strategy of the algorithm. Moreover, he

assert that the control component can be modified improving the efficiency

without modifying the meaning of the algorithm. But it can be also improve

by modifying the logic component. This can be reachable if the components

are identified and separated in the program text.

1
Summary

The article begins denoting the equivalency between algorithms with the same

logic components and different control component. He exemplifies it using the

factorial definition. Mentioning that, depending the domain of the problem,

the top-down and bottom-up approaches could improve the performance of

certain algorithm.

As we mention early in the introduction, modifying the control component

does not affect the logic component thus neither the algorithm. Modifying

the logic component will affect the meaning of the algorithm as well as it

behaviour. I agree with his thought due to the strong dependency between

the behaviour and the meaning of an algorithm. In word of Robert Kowalski

The logic component defines the problem-domain-specific part of

an algorithm. It not only determines the meaning of the algorithm

but also influences the way the algorithm behaves. The control

component specifies the problem-solving strategy. It affects the

behavior of the algorithm without affecting its meaning

Subsequently he mention how the control component can be specified

by the programmer or by the system itself. Apparently he is referencing

how the system behave depending the level of abstraction of the language.

Then he made an example when a query is done in database, we have not

to worry about the control component because the system is responsible of

that task. Other example i propose that is contrary of the database example

is, if you have to program in low level programming language like c. You

have almost no restriction over the control components due to the low level

2
implementation of the language. But it also gives the responsibility to the user

that have to pay attention to aspects as data allocation.

But, there is other advantages apart from performance. You can also

improve the code making it more readable, self-documented, scalable and

to debug. As an analogy we imagine the system as house made be pieces of

legos, whenever is required it can be easy to change certain pieces by another.

Also, it can help to reduce complexity when dealing with certain problems.

Because we can generate different formulation for the same algorithm where

the control component is complicated and the logic component it is simple

and straightforward.

There some aspects of the work that i differ from Kowalski for his decision

of taking the data structure as logic component. That conflict with Wirth

terminology. Wirth stated that a program is the union of algorithm and data

structure. As a matter of fact i agree with him. Because it contradict what he

stated in the quote i made above. Considering that changing data structure

in algorithm would not change the meaning of a algorithm but it can change

the behaviour. Taking search algorithms like binary search as an example. In

both approaches we can use an array (contiguous data allocated) but if you

try to implement it using linked-list. It would be impossible to implement

using recursion, although the algorithm by it self is recursive. And if you

make it iterative, the implementation would be troublesome because we must

traverse the elements until we get to the middle. Clearly the behaviour of the

algorithm has changed due to the nature of the linked-list. but the logic has

been preserved.

3
Conclusion

In conclusion, Kowalski made a excellent article. It is very clear and concise.

It was very proper to use predicate logic to exemplify their thoughts. His

definition of the components of an the algorithm was adequate. Exposing how

can it can get a boost in performance in developments thanks to the practices,

But also improving the efficiency of the system in general. Although, i had

problem with his data structure definition. But the text as an whole is a good

source to see the benefit of using predicate logic as tool of analyze, and an

excelent motivation to learn some logic programming language.

References

1. Robert Kowalski. Algorithm = Logic + Control. J. J. Horning Editor, Reading,

England, 1979.

2. How to Write a Summary of an Article

https://owlcation.com/academia/How-to-Write-a-Summary