main page (gr) |
home |
main page |

novel (gr) |
selections |
readings |
gallery |
pre-meaning |
advanced computing |
str (gr) |
internet epitome (gr) |
win stuff |

lecture #1 |
lecture #2 |
lecture #3 |
lecture #4 |
lecture #5 |

Advanced Computing Course - Lecture #2

Copyright © Constantin S. Chassapis - amorphous.art

Version 1: 23/11/94. Version 2: 16 April 2000.

Interactions involving humans are most effectively carried out through the medium of language. Language permits the expression of thoughts and ideas, and without it, communication as we know it would be very difficult indeed.

In computer programming, a programming language serves as a means of communication between the person with a problem and the computer used to help solve it. (And not only that! In general, a program will not only be read by its author or by some computer, but, by many other people too. There is a lot of meaning therefore in demanding readability, not only of a specific program, but, of the very structures of a language.) An effective programming language enhances both the development and the expression of computer programs. It must bridge the gap between the often unstructured nature of human thought and the precision required for computer execution.

A program solution to a given problem will be easier and more natural to obtain if the programming language used is close to the problem. That is, the language should contain constructs which reflect the terminology and elements used in describing the problem and are independent of the computer used. Such programming languages are usually high-level. Digital computers, on the other hand, accept and understand only their own special low-level language, consisting typically of long sequences of zeros and ones. These sequences are usually unintelligible to humans.

A hierarchy of computer languages based on increasing machine independence is

- Machine-level languages (zeros and ones).
- Assembly languages (symbolic form of 1).
- Higher-level or user-oriented languages.
- Procedural languages (f.ex. fortran, C, Pascal).
- Non-procedural languages (f.ex. CSMP). (Interchange of any two statements in a non-procedural language program will not affect the results obtained through its execution.)
- Problem-oriented languages (f.ex. SEQUEL).

Some of the advantages of high-level languages over their lower-level counterparts are: they are easier to learn and debug, there are no clerical tasks for the programmer, no need to know internal formats, availability of various control structures, possibility of team work via procedures, machine-independence.

In general, the process of programming and executing a program may be visualised as follows

The compiler is a program that transforms the source program into a particular computer’s machine or assembly language. A model [1] for the components of a compiler may be the following

**Lexical Analyser:** Separates incoming string of characters into pieces, **tokens**, such as variable names, keywords of the language, etc. In essence, low-level syntactic analysis.

**Syntactic Analyser:** Takes the source in the form of tokens and determines the manner in which it is to be decomposed into its constituent parts. Determines, that is, the overall structure of the source. This is analogous to determining the structure of an English sentence, where there we are interested in identifying “subject”, “predicate”, “verb”, “noun” and “adjective”. In syntactic analysis we group tokens in larger synthetic classes such as expression, statement, and, procedure.

**Semantic Analyser:**Determines the meaning (or semantics) of the source program. It works in close co-operation with the parser. In essence, it “understands” what to do when for example, the parser recognises a “+”.

**Code generator:** Produces machine or assembly language.

**Code optimiser:** Produces efficient object program by machine depended and machine independent code optimisations.

We say that a finite non empty set of symbols, like for example, V = { a, b, c, ..., z }, is an **alphabet** [1]. We define an operation over that set, named *concatenation*, as: ‘a’¤‘b’ = ‘ab’. A **string** (or sentence) over an alphabet V, is either a letter from that alphabet, or a sequence of letters derived from the concatenation of zero or more characters from V.

Let V ¤ V = V^{2} designate all strings of length 2, V ¤ V ¤ V = V^{3} of length 3 and so on. The **closure** of V, denoted as V^{+}, is V= V U V^{2} U V^{3} U .... For completeness, a special string, π, called the null or empty string is often combined with Vto form the **closure set** of V, V*, i.e., V* = {π} U V. Note that the string π has the identity property and is called the identity element in the system formed by V* and concatenation. (Identity property: if x belongs to V* then π¤x = x¤π = x.)

The problem of ensuring that only the proper set of characters appears in a program is handled by the scanner of a compiler.

Programming languages must be precisely defined. Unfortunately, for some languages (like the old versions of fortran), the existence of a particular compiler finally provided the precise definition of the language.

The proper specification of a programming language involves the definition of the following:

- The alphabet that can be used to construct correct programs.
- The set of all syntactically correct programs.
- The “meaning” of all syntactically correct programs.

Definition 1 is necessary for successful scanning, definition 2 for successful parsing, and 3 for successful semantic analysis and generation of code.

**A language**, L, can be considered as a subset of the closure set of an alphabet V_{T}, i.e. L belongs to V_{T}*. A language therefore may be infinite. But any means of specifying a language should be finite. Such a device is a **grammar**. A grammar consists of a finite non-empty set of rules (also called “productions”) which specify the syntax of the language. A grammar imposes structure on the sentences of a language and this structure is used during parsing.

There are many valid fortran programs (valid syntactically), that do not make sense (a call to a subroutine with incorrect number of arguments for example). But this is so, because it is easier to define a language if certain sentences of questionable validity are allowed by the grammar rules. So, generally, a language is described in full in two parts. The one being the grammar rules and the other the restrictions and reservations of the language.

Let us now formalise the idea of a grammar and how it is used [1]. For this purpose, let V_{T} be a finite non empty set of symbols called the **terminal alphabet**. The symbols in V_{T} are called **terminal symbols**. The **metalanguage** which is used to generate strings in the language is assumed to contain a set of syntactic classes or variables called **nonterminal symbols**. (A language or system that describes another language is called metalanguage). The set of nonterminal symbols is denoted by V_{N}, and the elements of V_{N} are used to define the syntax (structure) of the language. Furthermore, the sets V_{T} and V_{N} are assumed to be disjoint. The set W = V_{T} U V_{N} is called the **vocabulary **of the language. From now on, by

- A, B, C, ..., Z we denote nonterminal symbols,
- a, b, c, ..., z we denote terminal symbols,
- s
_{1}, s_{2}, ..., we denote elements of the vocabulary, - a, b, g, ..., w we denote strings over the vocabulary.

The length of a string a is denoted |a|.

**Definition**: A grammar is defined by a 4-tuple G = {V_{N}, V_{T}, S, F}, where S is a distinguished element of V_{N} and is called the starting symbol and F is a finite non empty subset of the **relation** from W* V_{N} W* to W*. (Any set of ordered pairs defines a relation.) In general, an element (a, b) is written as a -> b and is called a **production rule** or a **rewriting rule**.

For example, defining an identifier we may write the grammar as G_{I}= {V_{N}, V_{T}, S, F}, with, V= { I, L, D }, where I denotes identifier, L denotes letter and D denotes digit, V= { a, b, c, ..., x, y, z, 0, 1, 2, ..., 9 }, S = I, and finally, F = { I -> L, I -> IL, I -> ID, L -> a, L -> b, ..., L -> z, D -> 0, D -> 1, ..., D -> 9 }.

**Definition**: Let G = {V_{N}, V_{T}, S, F} be a grammar. For s, y in W*, s is said to be a **direct derivative** of y, written as y => s, if there are strings j and c (including possibly empty strings) such that y = jac and s = jbc and a -> b is a production rule of G.

If y => s, we also say that y directly produces s. For example, for the case of G_{I} above, using the rule D -> 1, we may write LDL => L1L, that is, LDL directly produces L1L.

**Definition**: Let G be a grammar. The string y produces s (or s is a derivative of y), written as y =+> s, if there are strings j_{0}, j_{1}, ..., j_{n} (n>0) such that y = j_{n} => j_{1}, j_{1} => ... => j_{n-1}, j_{n} => j_{n} = s.

Returning to grammar G_{I}, we show that the string a13 is derived from I by following the derivation sequence: I => ID => IDD => LDD => aDD => a1D => a13.

We write y =*> s denoting either y =+> s or y => s.

**Definition**: A **sentential form** is any derivative of the unique nonterminal symbol S.

**Definition**: The language L generated by a grammar G is the set of all sentential forms whose symbols are terminal, i.e., L(G) = {s: S =*> s & s belongs to V_{T}*}.

Therefore, the language is merely a subset of the set of all terminal strings (sentences) over V_{T}.

**Classification of Grammars**: Noam Chomsky in 1959 classified grammars into four classes by imposing different sets of restrictions on the productions:

a -> b (1), (1) = **unrestricted** grammars,

|a| =< |b| (2), (1) & (2) = **context-sensitive** grammars,

a belongs to V_{N} (3), (1) & (2) & (3) = **context-free** grammars,

b has the form aB or a,

where a belongs to V_{T} and B belongs to V_{N} (4), (1) & (2) & (3) & (4) = **regular** grammars.

and he also showed that:

L(regular) is a subset of L(context-free) is a subset of L(context-sensitive) is a subset of L(unrestricted).

For regular grammars very efficient parsers exist. Context-free and regular grammars cannot describe any natural language. However they can specify most of the syntax of computer languages.

Grammar G_{I} is an example of a context-free grammar.

A quick overview of a minimal core of fortran 77 will be given in this lecture. This minimal selection is made directly from the standard [2], and is based ofcourse on personal taste and experience. A basic assumption made is that the reader has some familiarity with fortran so we will try to skip some trivial things. This text is more a biased reminder than a textbook. Don't ask me why I do not present fortran 90. Maybe in the future.

Everything in the actual fortran language will be typed as ** fortran material ** to ease the eye. The metalanguage items will be typed like the main text.

A program in fortran should have the following basic structure:

name`Program` specification statements executable statements `end` |

The following table shows the physical constrains of a fortran line:

column(s) | contents | comments |

1 | c or * | only used for comment lines |

2 - 5 | arithmetic labels | only used for labelling |

6 | any non-zero character | only used for line continuation |

7 - 72 | fortran 77 sentenses | used for the actual program sentenses |

The arithmetic is performed by the operators ` + - * / ** `

that stand for Addition, subtraction, multiplication, division and raise to a power. The ** **** operator has the highest priority and

` +,- `

Never forget the limitness of the computer arithmetic. Operations involving Real numbers is limited to machine precision. Operations involving Integer numbers are exact up to the maximum integer number the machine can handle.

We may put a number or the result of an operation on a storage position using ** =**. This action is called assignment. Example with

`a = 123.88 `

`a`

There exist the following types of variables or arrays or functions in fortran:

`Real, Integer, Logical, Character, Double Precision, Complex`

The above, constitute also specification statements, (assumed well known).

Note the following rules:

A Fortran variable name: 1. Starts with a letter, 2. Contains only letters and numbers, 3. Is at most 6 characters long.

The same rules apply for the more general item called fortran symbolic name (**fsn** hereon).

Question: How can we restrict G_{I} so to describe an fsn?

It is advisable to use meaningful names for all fsn whenever possible and avoid cryptic or unclear abbreviations.

Here are some good programming practices:

1. Always strive for simplicity and clarity.

2. Write a lot of comments and documentation. Write prologues on all modules. Pay attention though, that the comments do not get out of date with the code.

3. Intent to highlight the nesting depth of a group of control statements or do-loops.

4. Always validate input for legality and plausibility and echo print the input. Your goal should be to write a module that is protected against improper data.

5. Pay attention to potential run-time errors such as division by zero or array-boundary violation.

6. Always declare your variables and use the non-standard but very useful statement: ** implicit none**.

The command

`print*, `

puts something on the screen

and

`read*,`

gets something from the keyboard.

A more complicated (but extremely more powerful) form of the above two operations, involves the notion of file and the notion of format. We will not delve here in either items. We will mention though the command

`read ( unit, fmt, iostat = ios ) `

where ** unit ** is either a

`* `

`open`

`ios`

`fmt`

` * `

`read (*, '(a)', iostat = ios ) Name`

will read from the keyboard the character variable ** Name**. Everything you type is supposed to be character data for the variable and is digested.

By using this more powerful form of ** read**, we can have the reading being performed (in a loop for example) continuously until an erroneous situation occurs (signalled by

`ios`

The ** open** statement implies an operation performed by the program at execution time, which connects a file with the program through a number. A restricted form of the syntax is

`open (`

`unit=`

`, file=charVar, `

`status='old'`

`'new',`

` err=`

`)`

All items enclosed in [ ] can be absent, and, or is exclusive-or.

untNum is a number, the same number which appears in a ** read** or

`write`

`charVar`

`'old'`

`'new'`

`open`

`open`

`'old'`

Take as an example the statement below

`open ( unit=23, file='NewRes', status='new', err=99 )`

which opens the** 'new'** file

`'NewRes'`

`23`

`write`

`write (23,*) a, b, c`

Let us mention that ** print*,** (the coma is a part of the command) and

` write(*,*)`

The command:

** Pause ** [

`'`

`'`

pauses the machine until carriage-return is pressed and displays 'message' on the screen.

The command:

** goto ** label

makes the program during execution to jump to the position marked by label.

The correct use of ** goto ** implies that you do not use it too often. You should use it to handle errors or other abnormalities in the logic of your algorithm. Your program will not be readable if you use

`goto `

A statement function is an one-line function definition, like

`f(x) = sin(exp(abs(x)))`

It appears exactly before any executable statement. Executable statements are ** do**-loops,

`continue`

`if`

An ** if**-block is something like:

** if ( ** logical expression

` ) then`

block of executable statements

[

`elseif`

another block of executable statements ]

...

[

`elseif`

another block of executable statements ]

[

`else`

another block of executable statements ]

`endif`

The simplest form of ** if **, when the block consists of only one statement, is to write that statement after

` if `

** if ( **logical expression

` )`

Learn to use all structured variations of ** if**. Your program will be more readable and understandable and easier to test and debug.

A logical expression is a proposition that can only be ** .true.** or

`.false.`

` logical`

`.and.`

`.or.`

`.not.`

`.not.`

`.or.`

You form simple logical expressions most frequently using the relational operators shown at the table

Fortran equivalent | Algebraic form |

`.eq.` |
= |

`.ne.` |
≠ |

`.lt.` |
< |

`.le.` |
≤ |

`.gt.` |
> |

`.ge` |
≥ |

It is evident that one can perform “arithmetic” with logical variables, assignments and operators. For example:

`program strange`

...

logical B

...

B = (x.lt.3.) .and. (y.gt.2)

if(B)then

...

end

When all types of operators are combined, the highest priority goes to arithmetic, next to character, next to relational, and finally to logical operators.

We use all the above notions into a simple but powerful program which finds the real roots (if there exist) of (almost) any one-variable function which has a first and a second derivative in a given interval. The method is based on the mean value theorem. It is the well known “Newton's Method”.

We have:

f(b) - f(a) = (b-a) f'(u), u belongs to (a,b).

Setting g=f' we similarly obtain

g(u) - g(a) = (u-a) g'(s), s belongs to (a,u).

Combining the two equations, we get

f(b) - f(a) = (b-a) [f'(a) + (u-a) f''(s)]

consequently

f(b) = f(a) + (b-a) f'(a) + (b-a) (u-a) f''(s)

or

f(b) = f(a) + (b-a) f'(a) + very small error.

We will neglect the very small error because it is a quantity of order h^{2}, (where h=b-a). So

f(b) ≈ f(a) + (b-a) f'(a).

What does this approximation tells us? Let's say that we are at point x=a and observe that f(a)≠0. We seek a correction to a, da which will give b = a + da with f(b) ≈ 0. We use our formula and obtain

0 ≈ f(a) + (b-a) f'(a)

If one solves for b,

b ≈ a - f(a)/f'(a)

This is the equation that we use repetitively until two approximations to the final b are so similar that there is no reason to continue.

`program newt c a program to find the real roots of f(x) c using Newton's method. real x, f, fp, savex f(x)=3.*x**2-15.*x+18. fp(x)=6.*x-15. print*,'ready, enter initial x' read*,x 1 continue savex = x x = x - f(x)/fp(x) if(abs(x-savex).le.0.001*abs(x))then print*,x,f(x) stop endif goto 1 end`

The reader is welcomed to improve this program, especially to expand the criteria for ending the repeat-until loop.

The do-loop is an essential fortran repetitive structure that satisfies the following syntax:

** do** label [ , ] dovar = initial, limit [ , increment ]

loop body (you may use (but not change) dovar in the loop body)

label `continue`

The number of times the loop body will be repeated is determined by the following expression

max ( int(limit-initial+increment)/increment, 0 )

where initial, limit, increment can be integer, real or double precision. The test of completition is done at the beginning of the loop.

The data of a given problem, very rarely are just an amorphous collection of symbols or numbers. Most of the times, there are hidden or less hidden relations between them. The random set, for example, {9,2,7,5,6,3} gains very different meaning if considered ordered (for example a vector), or if considered a 2x3 matrix. It is therefore evident that in forming and executing an algorithm, the structure of the data involved is fundamentaly involved.

In any (somewhat organised) activity in our everyday life, that involves information processing, we keep that information in a form of catalog or table. That is our essential organising construct. On the other hand, the data that we are handling everyday, do not always posses the same degree of organization or complexity. Some of these data can be analysed to more elementary units, some other, not. If we name the non-analyzable data "elementary", then "data-structures", in general, are ensembles of elementary data that combine according to very specific rules in order to form complex but organised data. (The specific rules just mentioned, constitute the additional information that leads the organizing costruct to the higher level of a data-structure).

The simplest data-structure is the array. Based on arrays we can build all other data structures. In this lecture we will only discuss the one-dimensional array. The generalization is very simple, if one imagines a two-dimensional array, for example, as an array of arrays.

Before continuing and linking all we just said with fortran 77, we have to point out one essential concept: Organisation is not unique! This seems obvious, but it is not always evident. Think for a moment the relation between organization and representation ...

The method which is most commonly used in programs that require a large number of data items to be retained in memory employs an array. An array is a block of memory cells that is assigned a name just as a single memory word is assigned a variable name. This block of memory consists of a sequence of consecutive memory cells each of which contains one data item. Each data item can be referenced by the name of the array and a number (subscript) that indicates its position in the array.

In order to use an array the computer must be informed of the size and name of the block of memory cells that constitute the array. This is accomplished by the array declarative statement. The computer must also be able to distinguish one data item from another in a block and this is accomplished by the use of subscripts.

An array is declared at the beginning of the program using a type declaration sentence. For example,

`Real Cave (1:6)`

is an order to the program that six places are to be grouped together under the name ** Cave**. It is not obligatory to use 1 up to 6. One can use any pair of numbers for which UpperLimit - LowLimit + 1 = 6. This depends on the algorithm that uses the array.

Generally we declare one-dimensional arrays as

`Type Name(`

`lowLimit :`

`upLimit)`

The part into [ ] may be absent. In that case ** lowLimit** is taken to be 1.

`Name`

`Type`

Now, what is the real need for the symbolic form called array? The hardware locations remain the same any way. We just alter the way we name them. But be suspicious. There is huge power in the act of naming. The whole construct of analysis is based on the generalising power of treating f(x) instead f(1.1), f(1.2), ...,etc. Remember, ... **representation is the essence of programming.**

So, returning to our theme, what is hidden behind the above syntactic discipline? well, just think of the following situation: You are asked to read the scores in History of 100 pupils and store them for later processing. One easily writes a command to ** read** a single item and place it in a memory-position named a. With the same degree of effort one even writes ten such

`read`

`read`

program history
real score(100)
do 1, i = 1, 100
read*, Score(i)
1 continue
...
end

There is no comparison, you have 5 lines against 102. After those 5 lines you may process the data in anyway you like, to find averages, deviations, etc.

The resumé: You name a group of memory-locations. Then you access them either to read or to store individually by an index, i.e., an address, in the same way you name the street Kifissias and the postman accesses your mailbox through some number. The gain is elegance, speed, portability, and maintainability of your code. The moral: **don't write a big program when a little one will do**.

**Multidimensional Arrays:** Fortran allows as many as seven dimensions for arrays. We can easily visualise a 3D array as a cube, a 4D array as a row of cubes, and so on. Generally we declare multidimensional arrays as

`Type Name(`

`lowLimit :`

`upLimit`

`lowLimit :`

`upLimit,`

`)`

The part into [ ] may be absent and ... denotes repetition.

Important note: Pay attention when you pass a multidimensional array in a subprogram. You should pass both physical (declared) and logical (actual) dimensions.

Question: Explain why.

Its time now to see how we can combine all the above ideas to construct a working program. The question is the following: Given a randomly filled array with reals, figure out a program that will sort them out, that is, it will rearrange the array so that the numbers will be ordered and the first item will be the biggest real, and the final one the smallest.

We will build our solution, step-by-step. First lets do a program to find the biggest number of an array and its position in it.

The key to this simple program is to check each time two numbers: the maximum up to now and the i-th array element (with i running over all the indexes). The result of each comparison will be a new maximum. At the end we will have the global maximum.

program findMax
c this program finds the maximum of an array
real fly(1:100), x, xmax
integer n, ttm, ttp
print*,'Ready. Enter n, n<100 (put n=0 to end)'
read*,n
if (n.le.0.or.n.gt.100) stop
do 12, i = 1, n
read*, fly(i)
12 continue
xmax = fly(1)
ttm = 1
do 33, i = 2, n
if (fly(i).ge.xmax) then
xmax = fly(i)
ttm = i
endif
9 continue
print*, xmax,' in the position:',ttm
end

Now is evident that, if we keep somewhere that maximum and then repeat the whole process excluding the maximum just found, we will find the biggest number which is smaller than the excluded one, or in other words, the second from the top. We exploit next this idea making some refinements.

First, the aux-positions will exist in the same array we work on: we will use the top positions for storing the maxima found every time. That is, when we find a maximum we will exchange it with the top element of the array and at the next step we will start our work from the next array element. In that way there is no “fixed” top element, but a virtual top element which in every iteration moves down to the end. When it will reach the end we will stop.

Here is the program. Note how we incorporate the main part (loop 33) of the previous program into a do-loop over all sub-arrays (loop 22):

program sortIt
c this program sorts an array in descending order.
real fly(1:100), x, xmax
integer n, ttm, ttp, i, k
11 print*,'Ready. Enter n (n<100) and x. (n=0 to end)'
read*,n
if (n.le.0.or.n.gt.100) stop
do 12, i = 1, n
read*, fly(i)
12 continue
do 22, ttp = 1, n-1
xmax=fly(ttp)
ttm=ttp
do 33, i = ttp+1, n
if (fly(i).ge.xmax) then
xmax = fly(i)
ttm = i
endif
33 continue
x = fly(ttp)
fly(ttp) = fly(ttm)
fly(ttm) = x
22 continue
do 88, k = 1, n
print*, fly(k)
88 continue
go to 11
end

Note: the above program is not the most efficient way to sort an array. It is just a good way to show how things work. We will see in a future lecture sorting in more detail.

Here is another large issue in computing: the “divide and conquer” strategy. You keep the method in a different place than the other minor aspects of the solution. That place is a routine (also called a “module”). This is called modular programming.

Good practices:

A module should be coherent (i.e. perform a single logical task).

A module should not do operations of lower or higher levels.

Modules should be orthogonal to each other (i.e. a module should be uncoupled to its surroundings a much as possible).

A fortran module is allowed to call other modules any time this is needed. A fortran module is not allowed to call itself.

A subprogram in fortran can be either a subroutine or a function. The subroutine-call syntax is:

program callrout
real a
integer b(-3:3)
character c*12
...
call routin (a,b,c)
...
end

The subroutine syntax is like

subroutine routin (x,y,z)
real x
integer y(-3:3)
character z*12
...
end

There is one-to-one mapping of the arguments, i.e. a to x, b to y and c to z. Be careful (a) to have the same number of arguments, (b) to have the correct type of arguments in the calling program and in the routine!! Otherwise the rule "garbage in garbage out" will (unfortunately) apply.

As the program is running and meets ** call routin**, execution jumps into the routine, and when routine completes, control returns to the next statement after the

`call`

`routin`

Pay attention to:

Test input parameters for consistency,

Protect input parameters for unwanted change inside the module,

Avoid if possible halting inside a module,

Use appropriate signal-flags to return the status of the module.

Routines are powerful because are flexible. You may build today a routine which is part of the solution to a very special problem, and tomorrow, if you have constructed the routine with enough generality, you will be able to paste it into a program attacking a totally different problem. Working this way, you form little by little libraries of routines. Remember, ...**The processor is expandable. **

There is another type of module in fortran, the function subprogram. It is something like

function nam ( a, b )
...
end

that is called like

y = nam ( x, z )

Below follows example 2, but now using a subroutine.

program Sort_it
c reads numbers from the keyboard
c and sorts them in descending order
real fly(1:100), x, xmax
integer n, ttm, ttp, k, i
11 print*,'Ready. Enter n (n<100) and x. (put n=0 to end)'
read*,n
if (n.le.0.or.n.gt.100) stop
do 12, i = 1, n
read*, fly(i)
12 continue
call sort (fly,n)
do 88, k = 1, n
print*, fly(k)
88 continue
go to 11
end
subroutine sort(fly,n)
c attention: fly is coming in unsorted and
c goes out sorted !!
integer n, ttp, ttm, i
real fly(n), x, xmax
do 22, ttp = 1, n
xmax=fly(ttp)
ttm=ttp
do 33, i = ttp+1, n
if (fly(i).ge.xmax) then
xmax = fly(i)
ttm = i
endif
33 continue
x = fly(ttp)
fly(ttp) = fly(ttm)
fly(ttm) = x
22 continue
end

**a) The parameter statement**

You use ** parameter** to name constants. By doing so, you protect yourself of changing by mistake the values of certain constants (it is not allowed to change a constant declared in a parameter statement), and you make your program more readable. The association of the constants with the names is being done during compilation.

Example:

real pi
character Mesg*(*)
parameter (pi = 3.14, Mesg = 'hello World')

**b) The data statement**

The ** data** statement is similar to

`parameter`

`data`

integer n
character name*6
real a(1:2)
data n / 100 / , name / 'George' / , a / 16., 25./

The initial association is being done during compilation.

**c) The stop statement**

The ** stop** statement stops execution and displays a message. Syntax (the 'message' may be absent):

stop [ 'message' ]

**d) The return statement**

The ** return** statement stops execution of a sub-module and returns control to the calling module. As obvious, this statement is only used inside a module and not inside a main program. Syntax:

return

**e) The save statement**

The ** save** statement is used inside a sub-module to keep some variables or arrays well defined upon exit and re-entry. The standard [2] says that variables inside a sub-module are

`save`

save [ fsn, ... ]

**f) The rewind statement**

The ** rewind** statement is used to put the pointer for reading of, or, writing on a file to the start of that file. Syntax:

rewind ( [ unit = ] integer expression )

unit is the number associated to the file.

**g) The common statement**

The ** common** statement is used to declare global variables. Global either to the whole program or global (i.e. common) to some sub-modules. There are two syntactic forms:

common a, b, c [, ...]
common / fsn / a, b, c [, ...]

The first declares global ** a, b, c** to the whole program, the second, only to the modules that they contain it. The common is a means to shorten the argument lists of sub modules.

**h) Some details on characters**

The ** character** type is useful for string processing. The declaration is something like:

character name*9, array(1:100)*8

A character substring is an expression of the form name(i:j). As an example, if ** name**
is

`'Georges'`

`i=1`

`j=7`

`name(i:j)`

`'eorges'`

The operation over character strings is concatenation, the operator in fortran being ** //**. It can be described by an example:

`‘a’//’b’`

`‘ab’`

We are not leaving out something which will prevent us from thinking and working with clarity and structure. In contrast, we have omitted material which is not considered to be good programming habit using it, at least for beginners. (Assigned goto, arithmetic-if, equivalence, entry, etc.)

We have also left out many useful but not absolutely necessary things, like computed goto (for selecting between many ways), or detailed format.

It is my belief that the reader is now capable of reading that material in any good textbook and understanding its potential.

The only way to learn computing is by constructing as many programs as possible. So, ... Good luck!

But, ... *Resist that urge of start coding.*

Henry Ledgard in “Programming proverbs” (Hayden Book Co. 1975), introduced a corollary to Murphy's law. "Murphy's law of Programming" states that ...

*"The sooner you start coding your program, the longer it is going to take"*.

Trying to write anything but the simplest program without a well organised outline and an overall design plan is like building a house without a blueprint.

1. “The theory and practice of compiler writing”, J.-P. Tremblay & P. G. Sorenson, McGraw-Hill, New York, 1985.

2. “Programming Language Fortran - ANSI X3.9-1978” (Fortran 77), American National Standards Institute, New York, 1978.

3. “Structured fortran 77 for scientists and engineers”, D. M. Etter, 3rd ed., The Benjamin/Cummings Publishing Co., California, 1990.

4. “Mathematics of programming”, C.A.R. Hoare, Byte, August 1986.

5. “Advanced programming and problem solving with Pascal”, G.M. Schneider & S.C. Bruell, John Wiley & Sons, 1981.

6. “Truth and proof”, Alfred Tarski, Sci. Amer., June 1969.

**1. Reverse a string of characters.**

Suppose you have at hand a string of characters, named str. You also have the *minimum of space available* and you are asked to reverse that string, so that the first character becomes the last one, the second becomes the second from the end,...,the last becomes the first. Write a routine (and the corresponding test-program), that will accept a string as input and will give out the same string reversed. Then use this routine in a program which will read strings and print their reverses. (The algorithm should take two characters each time and swap their positions in the same string.)

**2. Differentiate a function.**

Use the formula (f(a+h)-f(a-h))/(2h) to approximate the derivative of a given function f(x) at point a. Test the results on many functions and points. Is the formula satisfactory? *Which parameter appears to be the most critical* of the problem, for a given function f(x), the point a or the step h? You may test the results with the analytic derivative so to understand better the behaviour of the formula. You may even compare it with the formula (f(a+h)-f(a))/h. Ofcourse, you are expected to build a separate module for each differentiation formula.

**3. Build a Word counter.**

Build a routine (and the corresponding test-program), that counts the words inside a document. You may use command wc of unix to test your results on given files. Note that you are expected to find a simple way to *define what a word is*.

**4. Build a number base converter.**

Build a routine (and the corresponding test-program), that will accept a decimal integer, and will convert it in *any other* given base.

Click to see the answers, but, try to solve them first!

If you have something to say about anything in this site, please, communicate! Contact me at cschassapis@acm.org. But, if you download and save this page to your machine, or print this page, then, please send me an e-mail saying that you did that. Thanks.

Last updated: June 7, 2008