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

keys, pointing to this site
amorphous art


 

Advanced Computing Course - Lecture #2
Copyright © Constantin S. Chassapis - amorphous.art

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

A random walk on the ontology of rules


Part A - LANGUAGES, GRAMMARS AND COMPILERS


• Languages and Compilers

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.

metronome

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

  1. Machine-level languages (zeros and ones).
  2. Assembly languages (symbolic form of 1).
  3. Higher-level or user-oriented languages.
    1. Procedural languages (f.ex. fortran, C, Pascal).
    2. 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.)
  4. 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 phases of programming

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

the interior of a compiler

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.

click to go to the top click to go to the bottom

• Strings Grammars and Languages

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 = V2 designate all strings of length 2, V ¤ V ¤ V = V3 of length 3 and so on. The closure of V, denoted as V+, is V= V U V2 U V3 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:

  1. The alphabet that can be used to construct correct programs.
  2. The set of all syntactically correct programs.
  3. The “meaning” of all syntactically correct programs.
earth's atmosphere

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 VT, i.e. L belongs to VT*. 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 VT be a finite non empty set of symbols called the terminal alphabet. The symbols in VT 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 VN, and the elements of VN are used to define the syntax (structure) of the language. Furthermore, the sets VT and VN are assumed to be disjoint. The set W = VT U VN is called the vocabulary of the language. From now on, by

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

Definition: A grammar is defined by a 4-tuple G = {VN, VT, S, F}, where S is a distinguished element of VN and is called the starting symbol and F is a finite non empty subset of the relation from W* VN 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 GI= {VN, VT, 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 = {VN, VT, 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 GI 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 j0, j1, ..., jn (n>0) such that y = jn => j1, j1 => ... => jn-1, jn => jn = s.

Returning to grammar GI, 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 VT*}.

Therefore, the language is merely a subset of the set of all terminal strings (sentences) over VT.

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 VN     (3),       (1) & (2) & (3) = context-free grammars,

b has the form aB or a,
where a belongs to VT and B belongs to VN     (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 GI is an example of a context-free grammar.

click to go to the top click to go to the bottom

Part B - ESSENTIAL FORTRAN 77


• Basic Program Structure

burlesk, a small painting of mine 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:

Program name
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
click to go to the top click to go to the bottom

• Arithmetic and Types

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 +,- the lowest.

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 we place the symbols (well, ... the number) 123.88 at the memory-location called 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 GI so to describe an fsn?

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


• Some general guidelines

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.

click to go to the top click to go to the bottom

• Some I/O

The command

print*, something

puts something on the screen

and

read*, something

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 ) various items

where unit is either a * (implying the keyboard), or a number associated with an open statement (which will be described later) and ios is the name of an integer variable which keeps the status of the read operation. The fmt specifier describes the format by which the items will be read. Usually is just a * signifying a standard treatment on the input. It can also be a character constant describing in detail the format. For example the statement

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) and so exit the loop.

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=] untNum, file=charVar, [status='old' or 'new',] err= stnm )

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 operation performed to the opened file. charVar is a character variable which holds the name of the file to be opened. 'old' is the status of a pre-existing file, 'new' is the status of a file which is being created with the open in question. stnm is a statement number (also called “label”) where execution jumps in case something goes wrong during open (for example when you denote 'old' a file which turns up non-existent!).

Take as an example the statement below

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

which opens the'new' file 'NewRes' and associates it with the number 23, so that subsequent writes can be performed to it via a statement of the form:

write (23,*) a, b, c

Let us mention that print*, (the coma is a part of the command) and write(*,*) are practically the same.


• Flow Control Commands

The command:

Pause [ ' message ' ]

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.

a small thing created by me

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 to jump backwards in the code, except possibly when constructing a do-while control structure clearly indicated and commented in the program.


• Statement Function

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, continues, assignments, if-blocks, etc.


• The if-block

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 in the same line, like:

if ( logical expression ) statement

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

click to go to the top click to go to the bottom

• Logical Matters

A logical expression is a proposition that can only be .true. or .false. (pay attention to the dots). It can be formed by logical variables, and the operators .and., .or., .not. (you are obliged to put the dots and don't ask why!). The .not. operator has the highest priority, and .or. the lowest.

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.


• Example 1: Newton’s Method for roots

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 h2, (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

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.


• Arrays

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.

lines, a small painting of mine 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 is an fsn. Type is any of the fortran variable types.

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 reads to store ten values to ten independent storage locations. But what about 100 numbers? It looks (and it is) not smart to do yourself the work that is supposed to be done by the machine. You should not in any way write 100 reads. But you should solve the problem. What do you do? You use an array and a do-loop! The result:

       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.

a small thing created by me

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.

click to go to the top click to go to the bottom

• Example 2: Sorting

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.


• Subprograms and Modular Programming

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. Note that you may call routin as many times as you wish.

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 few additional statements

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 but you are allowed to change during run-time the contents of the variables initialised through data. The syntax is:

       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 not guaranteed to be saved between successive calls to that subroutine unless the variable is declared in a save statement. Syntax:

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 and j=7, then name(i:j) is 'eorges'.

The operation over character strings is concatenation, the operator in fortran being //. It can be described by an example: ‘a’//’b’ is ‘ab’.

click to go to the top click to go to the bottom

• What is left out?

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.

a small thing created by me

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.


• Some Bibliography

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.


• Exercises

granazia ...

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.)

granazia ...

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.

granazia ...

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.

granazia ...

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 click here 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


Click Here for Fine Art Posters at Barewalls.com     88 x 31 Join today  
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