﻿ section4

4 Program Segmentation

4.1 External Function Definition

4.1.1 Necessity of program segmentation

Example 28 generates meaningless Pythagorean numbers such as 6, 8, and 10. In order to prevent this, all we have to do is to exclude x and y whose greatest common divisor is greater than 1, so we can do that by implanting Example 35 directly into Example 28 as shown below.

```100 FOR x=1 TO 100
110    FOR y=x TO 100
120       LET a=x
130       LET b=y
140       DO
150          LET r=MOD(a,b)
160          IF r=0 THEN EXIT DO
170          LET a=b
180          LET b=r
190       LOOP
200       IF b=1 THEN
210          LET z=SQR(x^2+y^2)
220          IF INT(z)=z THEN PRINT x,y,z
230       END IF
240    NEXT y
250 NEXT x
260 END ```

However, it is not easy to make such a program in many case. For example, if Example 28 uses a, b, c instead of x, y, z as variable names, the combined programs will not operate normally.

4.1.2 External function definition

BASIC provides us with many built-in functions, but they are not sufficient.
DEF statements enables us to define a function, but only a function that can be indicated by an expression. BASIC also provides us with facilities with which we can define such a function that can only be found through more complicated processing.
The program shown in the preceding paragraph can be more easily written by denoting the greatest common divisor of 2 numbers a and b as GCD(a,b). To do this, we use an external function definition, so called.
In BASIC, the portion to the END line is called a main program. And the END line is followed by what are called external procedures. An external function definition is one type of a external procedure.
In Example 47, the portion from line 200 to line 280 is the external function definition to define the GCD function. An external function definition starts with an EXTERNAL FUNCTION line and ends with an END FUNCTION line. The EXTERNAL FUNCTION line holds the name of the function and the parameter list, which is parenthesized. If there are two or more parameters, they are delimited with commas.

Example 47

```100 DECLARE EXTERNAL FUNCTION GCD
110 FOR x=1 TO 100
120    FOR y=x TO 100
130       IF GCD(x,y)=1 THEN
140          LET z=SQR(x^2+y^2)
150          IF INT(z)=z THEN PRINT x,y,z
160       END IF
170    NEXT y
180 NEXT x
190 END
200 EXTERNAL FUNCTION GCD(a,b)
210 DO
220    LET r=MOD(a,b)
230    IF r=0 THEN EXIT DO
240    LET a=b
250    LET b=r
260 LOOP
270 LET GCD=b
280 END FUNCTION ```

The main program and external procedures are called program units.
In a program unit that uses an external function, a declaration statement that holds the name of the external function is written. In the above program, such a declaration statement as line 100 is written to use GCD as the external function in the main program. Writing such a declaration statement makes it possible to do correct operation even if there is a built-in function whose name is the same as the name of the external function. The declaration statement is written in a line above where the function is actually used.
As for the syntax, just the needed function name is written succeeding “DECLARE EXTERNAL FUNCTION”.

[Note]
With regard to the present version of Decimal BASIC, we can omit the declaration of the external function that does not agree in name with any built-in function, but declaration statements should be always written because the built-in function names may increase in future. And we are considering to change the syntax so as not to allow the omission of the external function declaration in future version.

In the above program, the GCD function is used in line 130. This is called an invocation of the function. Parameters, such as x and y in the above program, written in an invocation are called arguments.
When the GCD function is invoked, the values of the arguments are substituted for the variables a, b, and then the lines of the function definition are executed. The value of the function is decided by a LET statement in the form of substituting for the function name as in line 270.

Each program unit is independent as to variable names. Even if there is a variable of the same name in another program unit, it is a different variable on the computer. For example, if the variables x, y, z in the main program of Example 47 are changed to a, b, c, the program will operate normally.

4.1.3 Greatest common divisor of 3 numbers

Utilizing the external function definition makes it easy to find the greatest common divisor of 3 numbers. It is done as follows:

```100 DECLARE EXTERNAL FUNCTION GCD
110 INPUT a,b,c
120 PRINT GCD(GCD(a,b),c)
190 END
200 EXTERNAL FUNCTION GCD(a,b)
…………
… Same as Example 47　…
…………
280 END FUNCTION
```

4.1.4 Recursive invocation

As to a factorial n!, the recurrence formula` 0!=1, n!=n•(n－1)!` holds. Therefore 7! can be found by multiplying 6! by 7. Then 6! can be found by multiplying 5! by 6. When we decrease the numerical values like the above, finally we reach the formula `0!=1` to solve the problem.
The method to solve a problem by repeatedly recurring to a problem similar but smaller in this manner is called recurrence.
In BASIC it is allowed to invoke itself in a function definition. In the following program, the function FACT uses itself to calculate the factorial in its definition.

Example 48. Factorial

```10 DECLARE EXTERNAL FUNCTION FACT
20 INPUT n
30 PRINT FACT(n)
40 END
100 EXTERNAL FUNCTION FACT(n)
110 IF n=0 THEN
120    LET FACT=1
130 ELSE
140    LET FACT=n*FACT(n-1)
150 END IF
160 END FUNCTION
```

In computer programming, invoking itself in a function defining is known as a recursive invocation. The reason why the recursive invocation goes well in BASIC is that the variables are allocated anew each time the function is invoked. For example, even if line 140 is replaced with ` LET FACT=FACT(n－1)*n`, the program actually operates correctly. But if the value of n changes in the course of calculation of `FACT(n－1)`, it should not correctly operate. That is, each time the function FACT is invocated, the variable n valid only for that invocation is allocated anew to a different place in the memory.

4.1.5 Euclidean algorithm

The Euclidean algorithm, which finds the greatest common divisor, is also a typical example of recursive algorithm. This algorithm can be written in BASIC as follows.

Example 49

```10 DECLARE EXTERNAL FUNCTION GCD
20 INPUT a,b
30 PRINT GCD(a,b)
40 END
100 EXTERNAL FUNCTION GCD(a,b)
110 LET r=MOD(a,b)
120 IF r=0 THEN LET GCD=b ELSE LET GCD=GCD(b,r)
130 END FUNCTION ```

4.2 External Picture Definition and External Subprogram

4.2.1 External picture definition

Full BASIC is not provided with an instruction to draw a circle, but it is provided with means to define the instruction to draw a circle. That is called a picture definition.

Example 50

```10 DECLARE EXTERNAL PICTURE circle
20 OPTION ANGLE DEGREES
30 SET WINDOW -8,8,-8,8
40 DRAW circle
50 DRAW circle WITH SCALE(2)
60 DRAW circle WITH SCALE(3,2)
70 DRAW circle WITH SCALE(3,2)*SHIFT(3,4)
80 DRAW circle WITH SCALE(5,3)*ROTATE(60)
90 END
100 EXTERNAL PICTURE circle
110 OPTION ANGLE DEGREES
120 FOR t=0 TO 360
130    PLOT LINES:COS(t),SIN(t);
140 NEXT t
150 END PICTURE ```

The portion from line 100 to line 150 is called an external picture definition. In the first line of the external picture definition, the picture name is written following “EXTERNAL PICTURE”. In the above program, “circle” is the picture name. An parameter list part can be written as in the case of external function definitions, if necessary.
The picture circle draws a circle of radius 1 with center the origin. to be exact, a regular 360-gon is drawn, but it looks like a circle on the display of the computer.
Each program unit is independent as to OPTION statements. Even if OPTION ANGLE DEGREES is written in the main program, the unit of angle measure is not changed in an external picture definition.
A DRAW statement is used for executing a picture. Such transformation as rotating or scaling with center the origin, or translation can be specified in a DRAW statement.
SCALE(a,b) stands for an expansion of a-fold in the x-axis direction and b-fold in the y-axis direction with the center at the origin, where a and b can be negative numbers. In the case of a=b, it can be written as SCALE(a).
SHIFT(a,b) stands for a translation that moves the origin to the point (x, y).
ROTATE(α) stands for a rotation of angle α with the center at the origin.
Transformations can be composed with *. The composing transformations are executed from the left. For example, SCALE(3,2)*SHIFT(3,4) is scaling first and then parallel shifting.

4.2.2 External subprogram

All of the functionalities of an external subprogram are included in those of an external picture definition, provided that subprograms have no ability of transformation of graphics.

Example 51.

```  100  DECLARE EXTERNAL SUB circle
120  SET WINDOW -4,4,-4,4
130  CALL circle(1,-1,2)
140  END
200  EXTERNAL SUB circle(a,b,r)
210  OPTION ANGLE DEGREES
220  FOR t=0 TO 360
230      PLOT LINES: a+r*COS(t),b+r*SIN(t);
240  NEXT t
250  END SUB
```

Example 51 defines a subprogram circle (a,b,r) that draws a circle of radius r with center at (a, b).
Use a CALL statement to invoke a subprogram. If a subprogram has parameters, the parameters list is described in the same format as for a function.

4.2.3 Variable parameter (pass by reference)

The picture and subprogram have some characteristics different from the function definition.
One of those is variable parameter (pass by reference).

Example 52

```10 DECLARE EXTERNAL SUB double
20 LET a=3
30 CALL double(a)
40 PRINT a
50 END
100 EXTERNAL SUB double(x)
110 LET x=x*2
120 END SUB
```

In Example 52, the subprogram double(x) doubles the value of the variable written as an argument.
If a variable is written as an argument of a CALL statement, the invoked subprogram uses the actual area of the variable on the memory as the memory area for the parameter to which the variable has been assigned. Therefore, if the value of the parameter is changed during the execution of the subprogram, the value of the variable also changes.
If the argument is not a variable, for example, a constant, an arithmetic operation or a parenthesize variable, the parameter to which the argument is assigned is allocated to a new memory area and the value of the argument is substituted for it.
For example, if line 30 is changed to “`CALL double (1*a)`”, just the numerical value of the calculation result of 1*a is passed to the subprogram and the value of the variable a does not changes.

4.2.4 Extended Euclidean algorithm

We consider a problem to find an integer solution of an equation ax+by = c, where a, b, c are integer constants.
When b=0, the solution is obvious. If c can be divided by a, the solution is x=c/a, y can be any, so let y=0.
Conversely, if c cannot be divided by a, there is no solution.
When b≠0, let q be the quotient when a is divided by b, and r the remainder.
Since a=bq+r, the original equation can be replaced by b(qx+y)+rx=c.
Then, if the solution of the equation bu+rv=c is obtained, the solution is x=v, y=uqv, and if there is no solution for bu+rv=c, the equation has no solution.
Here the solution of bu+rv=c is always fixed. This is because when ax+by = c and bx+ry=c are compared, the coefficient of y is surely close to 0. Since the coefficient of y is an integer, it will surely become 0 after several repetitions.

Example 53.

```10 DECLARE EXTERNAL SUB solve
20 INPUT a,b,c
30 WHEN EXCEPTION IN
40    CALL solve(a,x,b,y,c)
50    PRINT x,y
60 USE
70    PRINT "no solution"
80 END WHEN
90 END
100 EXTERNAL SUB solve(a,x,b,y,c)
110 IF b=0 THEN
120    IF MOD(c,a)=0 THEN
130       LET x=c/a
140       LET y=0
150    ELSE
160       CAUSE EXCEPTION 999
170    END IF
180 ELSE
190    LET q=INT(a/b)
200    LET r=MOD(a,b)
210    CALL solve(b,u,r,v,c)
220    LET x=v
230    LET y=u-q*v
240 END IF
250 END SUB
```

A CAUSE EXCEPTION statement (in line 160) causes an exception of the specified number. The exception numbers of 1 to 999 are reserved for users.
If the statement that has caused the exception is not enclosed by a WHEN EXCEPTION ～ USE, the exception is propagated to the invoking statement.