Computer Science notes ⇒ System Design

Methodologies
This minisite contains notes taken by Chris Northwood whilst studying Computer Science at
the University of York between 2005-09 and the University of Sheffield 2009-10.

They are published here in case others find them useful, but I provide no warranty for their
accuracy, completeness or whether or not they are up-to-date.

The contents of this page have dubious copyright status, as great portions of some of my
revision notes are verbatim from the lecture slides, what the lecturer wrote on the board, or
what they said. Additionally, lots of the images have been captured from the lecture slides.

Methodologies
The term methodology is used confusingly in software systems engineering.

A method is a set of procedures to follow to accomplish a set of goals within a

particular domain.

A methodology involves the study of methods in a particular domain.

In software engineering, these two terms are often used (incorrectly)

interchangeably.

Descriptions
A description is a statement about phenomena of interest. It may be a program, a
model, or even a picture scribbled on a whiteboard.

Descriptions may be precise (i.e., there are notational rules that must be obeyed), or
they may be rough sketches.

System design involves constructing and manipulating many forms of descriptions;

these descriptions help us formulate and understand the requirements and constraints
underlying software system design.

Systems
A system is a set of interacting entities/things.

Systems are organised, that is, they have an architecture. Systems produce something something
that the individual interacting entities can not (that is, a system integrates individual entities).
Systems have boundaries, which separates its own entities from those in its environment.
Different types of system have different kinds of boundaries, and relationships with their
environment.

If we recall sets, we say a set is closed under an operation if the result of an operation gives you a
member of the set. We can apply the same thinking to systems. A closed system is one that is
isolated from its environment.

Closed systems are sometimes called self-describing systems. That is, they not only describe a
truth, but also describe what truth is, and how it can be recognised. (i.e., everything you want to
know about a system can be learned by studying it, and only it).

This notion of closure can be applied to different kind of systems. UML is an example of a closed
language, it is determined in terms of a meta-model, which is defined in terms of itself.

A closed system has communicating entities, but no connection to its environment, therefore we
need to consider if any reasonable system is in fact closed.

An open system has communicating entities, but also interacts with the environment and other
systems. Theoretically, an open system communicates constantly with its environment.

If we recall logic, a description of a system can be said to be complete if all of its propositions can
be derived only from the axioms of the system (e.g., first-order predicate logic).

Complete systems allow the truth of any statement in a description to be verified by referring to
the basic axioms and definitions of the systems. We can apply this to software by assuming that
our requirements are axioms (the assumed truths), and that our design and how it satisfies its
requirements is a set of propositions.

Incomplete systems come around when the description of the propositions can not be deduced
from the systems basic axioms. The information about those propositions may come from
elsewhere (e.g., if the system is open). Incompleteness is not necessarily bad.

Using these descriptions, we can group systems into four categories:

Complete and Closed

Complete and Open
Incomplete and Closed
Incomplete and Open

In reality, however, most systems do not fit exactly into one of these pigeonholes (i.e., systems are
more or less complete, or more or less closed, than other systems).

Programs and Software

We already know how to design programs - algorithms and data structure design. To know how to
design software we should first know what the difference between a program and software is.
Both involve descriptions (or are themselves descriptions).

A program is a sequence of operations that a machine can be set to perform automatically.

Formal Languages

Early programs required machine operators to change the physical order of the machine to change
the program. Reprogramming was a long, drawn out manual process. No such thing as program
design methods existed at this very early experimental stage.

When the von Neumann architecture was introduced, computers became more flexible, and the
idea of description became very important. This architecture began to impose methodology on to
how programs were designed.

Von Neumann did not use natural language to describe programs, he borrowed from the
mathematic theory developed by Turing, Post and Church in 1936. The languages proposed by
these theories relied heavily on formal logic, and consequently the languages themselves became
known as formal languages. Using these formal languages for description is only sensible under
certain assumptions.

Formal languages are covered

in more details in
Formal Specification of Systems.

Formal languages are mathematically defined description languages, containing a finite number of
symbols, and rules for combining symbols. Atomic symbols can not be decomposed into other
symbols and form the alphabet of the language, and non-atomic symbols are created by
combining atomic symbols, following the set of rules that define precisely how they are created.
These atomic symbols, and the rules to create non-atomic symbols constitute the syntax
(grammar, meta-model) of the language.

Some basic assumptions can be made when we construct descriptions using formal languages -
the description language is complete (i.e., no new symbols or operations can be introduced), and
that the systems they describe are closed (i.e., a system can not behave in such a way that the
behaviour exhibited can not be described by the language).

Formal languages, and hence program design methods, target complete and closed systems. For a
complete and closed system, given a written description (e.g., a program), it is possible to work
out exactly what sequence of actions the machine will produce. Similarly, given a sequence of
actions by the machine, it is possible to work out exactly what the written description (program)
must have been. That is, the actions of the machine and the system description are equivalent
(actions = instructions).

This is important for distinguishing programs and software.

Software

Before the 1960s, a separate notion of software to programs did not really exist, but as computer
use became more widespread, the need for separate terms became apparent.

There is often a mismatch between the needs of the machine and the needs of the business. The
actions of the machine and the system description are no longer equivalent - the system
description (business needs) must somehow be translated into machine actions.

Formal languages are not well suited to describing sensible and long established business rules, in
part because formal languages work well with closed and complete systems. Something else was
needed, and this something began to be called software.

Software has been given multiple definitions, including: "the printed materials supplied by a
computer manufacturer to its customers" (1972), "computer programs, procedures, rules and any
associated documentation concerned with the operation of a data processing system" (1982), and
"those components of a computer system that are intangible, rather than physical" (1996).

Program design methods were developed before software design methods. Structured code led to
structured design methods, and object-oriented languages led to object-oriented design methods.

Software design must lead to a software implementation (i.e., a program), so this so called
"seamless development" (i.e., applying the same idea to both software and program design) has
some obvious attractions.

History and expediency can lead to the assumption that program design methods are always right,
but it can sometimes be a struggle to make software descriptions fit into the confines of formal
languages.

Validation and Verification

One of the main differences between software and programs is the relative importance of
validation and verification.

Validation and verification address the problem of demonstrating the suitability of a software
description.

Validation: are we building the right product? Validation is concerned with demonstrating that the
software description is based on the right assumptions.

Verification: are we building the product right? Verification is concerned with demonstrating the
internal consistency of the software description.

Validation is particularly important for software designers because it lets them assess closure -
does the design correspond to the requirements specified by the customer? If a design is valid
(and the system is closed), then the requirement descriptions can be composed and decomposed
without introducing errors. This allows the designer to reduce one large problem into several
smaller ones, and structure those problems in such a way that they are capable of being described
in a formal language.

Verificiation is important for software designers because it lets them check completeness - is the
software correct in terms of the design established at the beginning of the activity? If verified, a
designer can claim that the relationship between the description and the thing being described is
completely and unambiguously defined. This allows the designer to ignore differences between
conceptual descriptions and the thing it describes within the scope of the software.

Closed and complete descriptions mean that a designer can claim the description and the thing
being described are equivalent. This allows the designer to treat the descriptions and things they
describe as being interchangeable. Because the of the unique environment of programs, program
designers can do this (at least in theory), but software designers (at least in practice), never can.

When you apply formal languages to describe things, you are working under assumptions of
closure and completeness. The problem is, software, and software design methods, only partially
conforms to the closure/completeness assumptions of formal languages. Software is not usually
closed, it must satisfy customers, and neither is it usally complete, it's enver fully implemented.

Program design methods are totally bounded by the completeness and closure assumptions of
formal languages, so software designers must go some way towards finding a complete and
closed description of the software system (i.e., of the requirements and the design), otherwise,
program designers can not design programs. This is, funamentally, what a software design method
tries to do.

Software must describe something of the communities that design, use and form the environment
for the programs. But there are some difficulties for software designers, like: where do the
boundaries of these communities lie; what is the relationship between these communities and the
computers attached to them, and; how can we form closed or complete descriptions under these
conditions.
Program descriptions are special cases of software descriptions.

Software descriptions are special cases of the full complexity of the relationships and associated
communities that have interest in the system. Thus, software is a description a special case of the
relationships among human communities, the environment of those communities, and machines
associated with them. By assuming that complete or closed descriptions exist, software design
methods may fail to create an adequate description of reality.