Software Development

Friday, November 27, 2020

Generating Bit Strings - Recursion Tree

Generating Permutations - Recursion Tree

Identifying Levels of Proficiency

Problem Solving Process Awareness Scale

Asking the SMIQ on Social Media

Execution Times of Sorting Algorithms

Insertion in Ordered Binary Tree

Multiple Representation of a Tree Structure

Solving a Problem using Data Structures or Sorting

Encapsulation and explicit state are most useful when used together. Adding state to declarative programming makes reasoning about the program much harder, because the program's behavior depends on its state. For example, a procedure can do a side effect, i.e., it modifies state that is visible to the rest of the program.

Side effects make reasoning about the program extremely difficult. Bringing in encapsulation does much to make reasoning tractable again. This is because stateful systems can be designed so that a well defined property, called an invariant, is always true when viewed from the outside. This makes reasoning about the system independent of reasoning about its environment. This partly gives us back one of the properties that makes declarative programming attractive.

An invariant says that the component is not behaving incorrectly; it does not guarantee that the component is making progress toward some goal. For that, a second property is needed to mark the progress. This means that even with invariants, programming with state is not quite as simple as declarative programming. A good rule of thumb for complex systems is to keep as many components as possible declarative. State should not be smeared out over many components. It should be concentrated in just a few carefully selected components.

The Principle of Abstraction

Any system can be thought of as having two parts: a specification and an implementation. The specification is a contract. The contract defines how the system should behave. We say a system is correct if the actual behavior of the system is in accord with the contract. If the system behaves differently, then we say it fails.

The specification defines how the rest of the world interacts with the system, as seen from the outside. The implementation is how the system is constructed, as seen from the inside. The specification is usually much simpler to understand than the implementation.

This means that it is possible to build a system as a concentric series of layers. Once can proceed step by step, building layer upon layer. At each layer, build an implementation that takes the next lower specification and provides the next higher one. It is not necessary to understand everything at once.

There are three properties a system should have to support the principle of abstraction.

Encapsulation

It should be possible to hide the internals of a part.

Compositionality

It should be possible to combine parts to make a new part.

Instantiation/Invocation

It should be possible to create many instances of a part based on a single definition. These instances plug themselves into their environment (the rest of the system in which they will live) when they are created.

Lexical scoping supports encapsulation and higher order programming supports instantiation. The properties do not require state; they can be used in declarative programming as well. For example, encapsulation is orthogonal to state. On the one hand, it is possible to use encapsulation in declarative programs without state.

State

A state is a sequence of values in time that contains the intermediate results of a desired computation.

Implicit (declarative) State

The sequence need only exist in the mind of the programmer. It does not need any support from the computation model. This kind of state is called implicit state or declarative state.

For example, if we write a recursive program to compute the sum of these numbers: [1,2,3,4], we will have two arguments to the recursive method, one that consists of the unexamined rest of the input list and the other for sum, which is the sum of the examined part of the input list. While calculating the sum of a list, the method calls itself many times. If we print the values of these variables in each call:

[1,2,3,4] # 0

[2,3,4] # 1

[3,4] # 3

[4] # 6

[] #10

This sequence is a state. When looked at in this way, the method calculates with state. The state is completely in the mind of the programmer.

How to Design a Program?

Designing a program is a mixture of creativity and rigorous thinking.

Informal Specification

Write down as precisely as we can what the program should do. What are the inputs and outputs? How do the outputs relate to the inputs? This description is called an informal specification. We call it informal because it is written in English. Formal specifications are written in a mathematical notation.

Examples

To make the specification clear, come up with examples of what the program does in particular cases. The examples should stress the program: use it in boundary conditions and in the most unexpected ways we can imagine.

Exploration

To find out what programming techniques we will need, a good way is to use the interactive interface to experiment with program fragments. The idea is to write small operations that we think might be needed for the program. We use the operations that the system already provides as a basis. This step gives us a clearer view of what the program's structure should be.

Structure and Coding

At this point we can lay out the program's structure. We make a rough outline of the operations needed to calculate the outputs from the inputs and how they fit together. We then fill in the blanks by writing the actual program code. The operations should be simple: each operation should do just one thing. To improve the structure we can group related operations in modules.

Testing and Reasoning

Now that we have a program, we must verify that it does the right thing. We try it on a series of test cases, including the examples we came up with before. We correct errors until the program works well. We can also reason about the program and its complexity, using the formal semantics for parts that are not clear. Testing and reasoning are complementary: it is important to do both to get a high quality program.

Judging the Quality

The final point is to step back and judge the design's quality. There are many factors involved in quality:

Does the design solve the right problem?
Is it correct?
Is it efficient?
Is it maintainable?
Is it extensible?
Is it simple?

Simplicity is especially important, since it makes many of the other factors easier to achieve. If a design is complex, the best we can say is that it is not yet in its definitive form. Next to simplicity is completeness, that is, the design has all the functionality it needs, so that it can be used as a building block.

When coming up with examples it can be clear that the specification has to be changed. The most important step is testing. It closes the loop: it gives feedback from the coding step back to the specification step.