[ЗМІСТ] [Далі] [Назад]

6. ПІДПРОГРАМИ

6.1. Функції

6.2. Процедури

6.3. Підпрограми у мовах програмування

6.4. Рекурсивні підпрограми

6. ПІДПРОГРАМИ

Починаючи з цього розділу, мова піде про виконавців, які можна було б назвати такими, що навчаються. Виконавець, що навчається здатний сприймати визначення нових об'єктів, операцій, інструкцій, запам'ятовувати їх і використовувати в подальших обчисленнях. Іншими словами можливості виконавців, що навчаються розширяються в процесі їх функціонування. Один з способів розширення, шляхом опису нових типів величин, вже розглядався у попередній частині. Зараз ми зупинимося на проблемах навчання новим діям з допомогою визначення підпрограм.

У практиці програмування підпрограмою називають спеціальним чином оформлену частину програми, що представляє самостійний інтерес: одну і ту ж підпрограму можна використати багато разів в одній або навіть багатьох програмах. Однак механізми використання різних підпрограм можуть розрізнюватися. Один клас підпрограм призначений для визначення нових операцій і відношень. Підпрограми з цього класу отримали назву (програмованих) функцій. Інший клас підпрограм - їх називають процедурами - призначений для визначення нових інструкцій.

Поділ підпрограм на процедури та функції в значній мірі умовний. Визначення будь-якої функції можна перетворити у визначення рівносильної процедури. Сучасні мови програмування істотно відрізняються одна від одної в цій частині, причому збіг позначень для механізмів визначення і використання підпрограм ще не гарантує збігу результатів. У силу сказаного техніка підпрограм вимагає суворого вивчення.

6.1. Функції

Поняття функції є центральним не тільки в програмуванні, але і в математиці загалом. Дійсно, ми вже мали справу з функціями, вивчаючи прості типи даних, оскільки останні являли собою множини, на яких задана система функцій і відношень. Замість слова функція іноді ми користувалися словом операція. Як правило, операція - це двомісна функція, що передбачає інфиксну систему позначень, наприклад, х+у (символ операції записується між своїми аргументами). Що стосується відношень, то тут поняття функції також виявляється корисним. Оскільки серед простих типів даних присутній бульовий тип, то відношення можна окремо не виділяти: всяке відношення може бути представлене деякою бульовою функцією.

Дамо визначення функції. Впорядкована пара <х, у> - це об'єкт з двома компонентами х і y. Тут важливий порядок, так що впорядкована пара <2,3> відмінна від <3,2>. Функцію f можна розглядати як множину впорядкованих пар, в якій значення перших компонент беруться з деякої множини, що називається областю визначення D, а значення других компонент покривають множину, що називається областю значень R. Ми говоримо, що функція f відображає (значення з) D в (значення з) R, і записуємо це у вигляді f: D -> R.

Нехай D={0,1,2,3,4,5}, R={0,1}. Тоді, наприклад, функція f що переводить парні числа в 0, а непарні в 1 - це множина впорядкованих пар f={<0,0>, <1,1>, <2,0>, <3,1>, <4,0>, <5,1>}. Сама ця множина не впорядкована.

У загальному випадку області D і R задовольняють умовам:

"x (х Î D) <=> $у (<х, у> Î f);))

"y (у Î R) <=> $х (<х, у> Î f).))

Умова функціональності

"x, у, z (<х, у> Î f) & (<х, z> Î f) => (у=z).))

Раніше, ніж побудувати виконавець програмованих функцій, розглянемо декілька прикладів.

Приклад 6.1. Множення натуральних чисел.

Наступний алгоритм практично дослівно відповідає визначенню множення двох натуральних чисел m і k багаторазовим додавання

n <- 0;

повт k раз

n <- n+m (6.1)

кц

{ n=m*k }.

Для перетворення алгоритму (6.1) у визначення програмованої функції необхідно: 1) дати їй ім'я, нехай ним буде ідентифікатор Мн; 2) визначити параметри функції, що вважаються аргументами, в нашому випадку k, m, і зафіксувати їх типи; 3) визначити величину, що дає результат, тобто шукане значення функції і зафіксувати його тип. Один з способів відповіді на поставлені питання дає наступний текст

функція Мн (M, K: нат): нат це

змін N: нат;

поч

N <- 0;

повт K раз

N <- N+M

кц;

Мн <- N

кінець_функції.

Допустиме скорочення кф.

Ще декілька прикладів.

Приклад 6.2. Степінь з натуральним показником.

функція Степ (X: дійсн; N: нат): дійсн це

змін Y: дійсн;

поч

Y <- 1;

повт N раз

Y <- Y*Х

кц;

Степ <- Y

кф.

Приклад 6.3. Найбільший спільний дільник двох натуральних чисел.

функція НСД (M, N: нат): нат це

поч

поки M<>N повт

якщо M>N то M <- M-N

інакше N <- N-M кр

кц;

НСД <- M

кф.

Тепер необхідно навчити виконавець обчисленню програмованої функції так, щоб він надавав, наприклад, виразу Мн(а+b, c) рівно те ж значення, що і (а+b)*c. Розглянемо, як це можна зробити, на прикладі.

Приклад 6.4. Скласти алгоритм обчислення НСД і НСК всіх пар натуральних чисел від 1 до n.

Алг НСДНСК це

змін N, D, K, I, J: нат;

функція НСД (M, N: нат): нат це

поч

поки M<>N повт

якщо M>N то M <- M-N

інакше N <- N-M кр

кц;

НСД <- M

кф;

поч

взяти (N);

для I<-1 до N повт

для J<-1 до I-1 повт

D <- НСД(I, J);

K <- (I div D)*J;

показати (I, J, D, K)

кц кц

ка.

В останньому прикладі ми стикаємося з новою для нас проблемою, яку можна було б назвати проблемою колізії змінних: всередині і поза функцією НСД ідентифікатор N означає різні змінні. Виходом із положення, що склалося, могло б бути перейменування змінних, що вирішують проблему локалізації позначень.

Розглянемо загальний випадок. Нехай програмована функція f задана визначенням

функція f (х : t ;...;х : t ): t це

1 1 n n

[ змін у : s ;...;у : s ; ] (F)

1 1 m m

поч

Р (х, ..., х [, у, ..., у ])

f 1 n 1 m

кф,

де х₁, ..., х_n - імена аргументів типів t₁, ..., t_n, відповідно; t - тип значення функції; у₁, ..., у_m - допоміжні змінні типів s₁, ..., s_m, відповідно; Р_f = Р_f (х₁, ..., х_n [, у₁, ..., у_m ]) – тіло функції, яке є інструкцією, взагалі кажучи, складеною.

Множина аргументів функції називається формальними параметрами.

Формальне правило використання визначення (F) буде дано пізніше. Зараз відмітимо лише, що тіло функції Р_f дає спосіб обчислення значення функції f, виходячи із значень її аргументів х₁, ..., х_n, можливо використовуючи допоміжні змінні у₁, ..., у_m для зберігання проміжних результатів.

Серед інструкцій що входять в Р_f обов'язково повинно бути присутнім присвоєння вигляду

f <- е, (6.2)

де е - вираз типу t.

Будемо вважати, що виконавці, що розглядаються надалі, разом з клітинками, призначеними для зберігання значень змінних, мають в своєму розпорядженні клітинки, здатні зберігати визначення функцій вигляду (F). Зустрівши в програмі визначення (F), виконавець відводить клітинку - назвемо її програмною, - призначену для зберігання визначення функції f.

Зупинимося тепер на правилі обчислення значення функції, яке прийнято називати правилом її виклику.

Виклик функції f при фактичних параметрах е₁, ..., е_n типів t₁,..., t_n, відповідно, має вигляд виразу

f (е , ..., е ). (6.3)

1 n

Правило виклику складається з чотирьох кроків.

F1) Заміна змінних. На цьому кроці виконавець відводить n+m+1 нових клітинок, що іменуються новими іменами x₁',..., x_n', y₁',..., y_m' і f', які не зустрічалися в попередніх обчисленнях. Типи нових змінних - це, відповідно, t₁, ..., t_n, s₁, ..., s_m і t:

x':t ; ...; x':t ; y':s ; ...; y':s ; f':t.

1 1 n n 1 1 m m

F2) Підстановка нових змінних. Виконавець будує модифіковане тіло функції, виконавши в Р_f підстановку нових змінних на

місце старих

x' -> х, ..., x' -> х, y' -> у, ..., y' -> у, f'-> f,

1 1 n n 1 1 m m

причому змінна f замінюється на f' тільки в лівих частинах присвоєнь. Отримаємо

P' = Р (x', ..., x'[, y',..., y']).

f f 1 n 1 m

F3) Обчислення. Виконавець готує і виконує наступний алгоритм

x' <- е ; ...; x' <- е; P',

1 1 n n f

який являє собою ланцюг, що складається з присвоєнь, що ініціалізують аргументи, та перетвореного тіла функції.

Значенням функції вважається значення змінної f'.

F4) Підстановка в алгоритм f' замість (6.3).¦

Покажемо застосування правила виклику на прикладі фрагмента виконання алгоритму з прикладу 6.4.

────────────────────────────────────────────────────────────────────

N I J D K НСД' M' N' НСД'' M'' N''

────────────────────────────────────────────────────────────────────

.......................... 25 15 9

D <- НСД(I, J)

------------------------

¦ M' <- I; N' <- J 15 9

¦ M'<>N'(так), M'>N'(так)

¦ M' <- M'-N' 6

¦ M'<>N'(так), M'>N'(ні)

¦ N' <- N'-M' 3

¦ M'<>N'(так), M'>N'(так)

¦ M' <- M'-N' 3

¦ M'<>N'(ні)

¦ НСД' <- M' 3

------------------------ 3

K <- (I div D)*J 45

J <- J+1 10

D <- НСД(I, J)

------------------------

¦ M''<- I; N''<- J 15 10

¦ M''<>N''(так), M''>N''(так)

¦ M''<- M''-N'' 5

¦ M''<>N''(так), M''>N''(немає)

¦ N''<- N''-M'' 5

¦ M''<>N''(немає)

¦ НСД'' <- M'' 5

------------------------ 5

.............................

Приклад 6.5. Корінь n-ї степені для числа а_i з послідовності додатніх дійсних чисел а₁, а₂, ..., а_m, ... що передують першому недодатньому числу. Використовуючи алгоритм з прикладу 5.4 Р і функцію 6.2 можна записати

алгоритм Корені це

змін А, Eps: дійсн;

K, N: нат;

функція Корінь (N, K: нат; А, Eps: дійсн): дійсн це

змін Y, Z, X: дійсн;

функція Степінь (X: дійсн; N: нат): дійсн це

змін Y: дійсн;

поч

Y <- 1;

повт N раз

Y <- Y*Х

кц;

Степінь <- Y

кф;

поч

Y <- 0.; X <- (А+K)/2.;

поки ¦X-Y¦>=Eps повт

Y <- X; Z <- Степінь(X, K);

X <- (K*Х+А/Z)/N

кц;

Корінь <- X

кф;

поч

взяти (N, Eps); K <- N-1;

цикл

взяти (А);

якщо А<=0 то вихід;

показати (А,'^1/', N,'=', Корінь(N, K, А, Eps))

кц

ка.

Тут передбачається, що виконавець ABRN наділений можливостями обчислення модуля числа (¦.¦).

Зверніть увагу на опис функцій в останньому прикладі. Функція Степінь описана всередині функції Корінь, тому перша з них доступна тільки в тілі другої функції і вона повністю закрита для звертання в тілі всього алгоритму Корені.

6.2. Процедури

Спочатку розглянемо дві програмовані функції.

Приклад 6.6. Остача від ділення натуральних чисел.

функція Modn (M, N: нат): нат це

змін R: нат;

поч

R <- M;

поки R>=N повт

R <- R-N

кц;

Modn <- R

кф.

Приклад 6.7. Частка від ділення натуральних чисел.

функція Divn (M, N: нат): нат це

змін R, Q: нат;

поч

R <- M; Q <- 0;

поки R>=N повт

R <- R-N; Q <- Q+1

кц;

Divn <- Q

кф.

Відмітимо, що функція з другого прикладу містить також обчислення остачі, оскільки вона фігурує в умові повторення циклу. Однак, згідно з правилом виклику функції, після закінчення обчислень значення R втрачається, оскільки єдиною доступною величиною залишається значення функції.

Розглянемо тепер інший тип підпрограм, що можуть виробляти відразу декілька величин.

Приклад 6.8. Частка та остача від ділення натуральних чисел.

процедура DivModn (арг M, N: нат; рез Q, R: нат) це

поч

R <- M; Q <- 0;

поки R>=N повт (6.4)

R <- R-N; Q <- Q+1

кц;

кп.

Тут змінні M та N є аргументами, а Q і R - результатами підпрограми.

Тепер, наприклад, запис DivModn(15,6, А, В) означав би дію, внаслідок виконання якого змінна А отримала б значення 2, а змінна В - значення 3. Тому запис, що розглядається, природно вважати новою інструкцією, яку називають інструкцією виклику процедури.

Перш ніж дати загальне визначення процедури, розглянемо ще один приклад.

Приклад 6.9. Обмін значень.

Як відомо, наступна послідовність присвоєнь

z <- х; х <- у; у <- z

приводить до взаємного обміну значеннями змінних х та y. Щоб перетворити цей ланцюг у процедуру, необхідно виділити аргументи - ними повинні бути значення змінних х та у - і результати, - а ними знов же є ті ж змінні х та y. В цьому прикладі ми маємо справу з особливим випадком: одні і ті ж змінні доставляють значення аргументів і отримують результати. Отримуємо новий тип величин - величини, що змінюються у процедурі, або модифіковані параметри.

процедура Обмін (мод X, Y: дійсн) це

змін Z: дійсн;

поч

Z <- X; X <- Y; Y <- Z

кп.

Дамо визначення. Процедурою назвемо підпрограму, що визначається наступним текстом

процедура Q (арг х: t; ...; х: t;

1 1 n n

мод у: s; ...; у: s;

1 1 m m

рез z: r; ...; z: r ) це (Pr)

1 1 k k

[ змін u: р; ...; u: р; ]

1 1 l l

поч

Р (х, ..., х, у, ..., у, z, ..., z [, u, ..., u ])

Q 1 n 1 m 1 k 1 l

кп.

Тут Q - ім'я процедури; х₁: t₁, ..., х_n: t_n - її аргументи, у₁: s₁, ..., у_m: s_m - модифіковані параметри, z₁: r₁, ..., z_k: r_k - результати, u₁: р₁, ..., u_l: р_l - допоміжні змінні, призначені для зберігання проміжних величин; інструкція Р_Q = Р_Q (х₁, ..., х_n, у₁, ..., у_m, z₁, ..., z_k [, u₁, ..., u_l ]) - тіло процедури - показує спосіб обчислення результатів і нових значень модифікованих параметрів, виходячи з їх початкових значень і значень аргументів.

Зустрівши визначення (Pr), виконавець заносить його в програмну клітинку помічену ім'ям Q.

Аргументи, модифіковані параметри та результати, що фігурують у визначенні (Pr), називаються всі разом формальними параметрами.

Викликом процедури Q називається інструкція

Q (е,. .., е, v,. .., v, w,. .., w ), (6.5)

1 n 1 m 1 k

де е₁, ..., е_n - вирази типів t₁, ..., t_n, відповідно; v₁, ..., v_m; w₁, ..., w_k - змінні типів s₁, ..., s_m; r₁, ..., r_k, відповідно. Разом е₁, ..., е_n; v₁, ..., v_m; w₁, ..., w_k називаються фактичними параметрами процедури. При цьому фактичні параметри е₁, ..., е_n надають значення аргументів; v₁, ..., v_m - модифіковані параметри; w₁, ..., w_k призначені для отримання результатів, як це видно з наступного правила виклику.

Правило виклику процедури (Pr) складається з наступних трьох кроків.

P1) Заміна змінних. На цьому кроці виконавець відводить n+m+k+l нових клітинок, які іменуються новими іменами

x',..., x', y',..., y', z',..., z', u',..., u'

1 n 1 m 1 k 1 l

що не зустрічалися в попередніх обчислннях. Типи нових змінних - це, відповідно:

x':t; ...; x':t;

1 1 n n

y':s; ...; y':s;

1 1 m m

z':r; ...; z':r;

1 1 k k

u':р; ...; u':р.

1 1 l l

P2) Підстановка нових змінних. Виконавець будує модифіковане тіло процедури, виконавши в Р_Q підстановку нових змінних на місце старих

P' = Р (x', ..., x', y',..., y', z',..., z'[, u',..., u']).

Q Q 1 n 1 m 1 k 1 l

P3) Виконання. Виконавець готує і виконує наступний алгоритм, який представляє собою ланцюг ініціалізації аргументів

x' <- е; ...; x' <- е;

1 1 n n

ініціалізації модифікованих параметрів

y' <- v; ...; y' <- v;

1 1 m m

виконання модифікованого тіла процедури

P';

Q

передачі модифікованих параметрів

v <- y'; ...; v <- y';

1 1 m m

і передачі результатів

w <- z'; ...; w <- z'.¦

1 1 k k

Покажемо застосування правила виклику на прикладі алгоритму, що складається з двох викликів

X <- 1; Y <- 2; U <- 3; V <- 4;

Обмін (X, Y);

Обмін (U, V).

─────────────────────────────────────────────────────────

X Y U V X1 Y1 Z1 X2 Y2 Z2

─────────────────────────────────────────────────────────

1 2 3 4

Обмін (X, Y)

-------------------

¦ X1 <- X; Y1 <- Y 1 2

¦ Z1 <- X1 1

¦ X1 <- Y1 2

¦ Y1 <- Z1 1

¦ X <- X1; Y <- Y1 2 1

-------------------

Обмін (U, V)

-------------------

¦ X2 <- U; Y2 <- V 3 4

¦ Z2 <- X2 3

¦ X2 <- Y2 4

¦ Y2 <- Z2 3

¦ U <- X2; V <- Y2 4 3

-------------------

Визначення (Pr) і правило виклику P1) - P3) назвемо системою визначення процедур, які взаємодіють за допомогою аргументів та результатів. Нарівні з нею, існують інші, більш практичні (з точки зору економії пересилок) системи, наприклад, система визначення процедур, які взаємодіють за допомогою аргументів і параметрів-змінних, що суміщають в собі функції модифікованих параметрів та результатів. У цій системі визначення процедури має вигляд

процедура Q (арг х: t; ...; х: t;

1 1 n n

змін у: s; ...; у: s ) це (Pv)

1 1 m m

[ змін u: р; ...; u: р; ]

1 1 l l

поч

R (х, ..., х, у, ..., у [, u, ..., u ])

Q 1 n 1 m 1 l

кп.

Як і раніше, викликом процедури Q називається інструкція

Q (е, ..., е, v, ..., v ),

1 n 1 m

де е₁, ..., е_n - вирази типів t₁, ..., t_n, відповідно; v₁, ..., v_m - змінні типів s₁, ..., s_m, відповідно.

Правило виклику процедури (Pv) складається з наступних трьох кроків.

R1) Заміна змінних. На цьому кроці виконавець відводить n+l нових клітинок, які іменуються новими іменами

x',..., x', u',..., u',

1 n 1 l

що не зустрічалися в попередніх обчисленнях. Типи нових змінних - це, відповідно:

x':t; ...; x':t;

1 1 n n

u':р; ...; u':р.

1 1 l l

R2) Підстановка нових змінних та підстановка фактичних параметрів-змінних. Виконавець будує модифіковане тіло процедури, виконавши в R_Q підстановку нових змінних на місце старих, а також підстановку фактичних параметрів-змінних

R' = R (x', ..., x', v, ..., v [, u',..., u']).

Q Q 1 n 1 m 1 l

R3) Виконання. Виконавець готує і виконує наступний алгоритм, що представляє собою ланцюг ініціалізації аргументів

x' <- е; ...; x' <- е;

1 1 n n

та модифікованого тіла процедури R_Q'.

Наступні два приклади показують істотні відмінності між розглянутими системами.

Приклад 6.10. Параметри, що повторюються.

Розглянемо процедуру

процедура Плюс1 (мод X, Y: нат) це

поч

X <- X+1; Y <- Y+1

кп

і виклик Плюс1(X, X) при X=0 в першій системі. Отримаємо результат X=1.

Переписавши цю ж процедуру в іншу систему в результаті аналогічного виклику отримаємо X=2.

Приклад 6.10 звертає нашу увагу на той факт, що фактичні параметри-змінні не повинні повторюватися, оскільки кожний з них при складанні процедури призначався для отримання свого результату.

Приклад 6.11. Подвійне іменування.

Внаслідок виконання алгоритму

алгоритм Двійник це

змін Y: нат;

процедура Плюс1y (мод X: нат) це

поч

X <- X+1; X <- X+Y

кп;

поч

Y <- 1; Плюс1y(Y);

показати (Y)

ка.

буде показане значення Y, рівне 3.

У той же час, виконання цього ж алгоритму у другій системі визначення процедур при описі X як параметра-змінної дасть результат 4.

Приклад показує, що остання система більш чутлива до побічних ефектаів.

Нарешті розглянемо приклад алгоритму, що використовує як процедури, так і функції.

Приклад 6.12. Сума гармонічного ряду

1 1 1

Н = 1 + - + - +... + -

n 2 3 n

у вигляді раціонального числа Р/Q.

алгоритм Сума_Гармонік це

змін Ch, Zn, N, J: нат;

процедура Сл_Др (арг Ch1, Zn1: нат;

змін Ch2, Zn2: нат) це

поч

Ch2 <- Ch1*Zn2+Ch2*Zn1;

Zn2 <- Zn1*Zn2

кп;

процедура Скор_Др (змін Ch, Zn: нат) це

змін K: нат;

функція НСД (M, N: нат): нат це

поч

поки M<>N повт

якщо M>N то M <- M-N

інакше N <- N-M кр

кц;

НСД <- M

кф;

поч

K <- НСД (Ch, Zn);

якщо K>1 то

Ch <- Ch div K; Zn <- Zn div K

кр

кп;

поч

Ch <- 1; Zn <- 1;

повт

показати (' n (n>1)=? '); взяти (N)

до N>1;

для J<-2 до N повт

Сл_Др (1, J, Ch, Zn);

Скор_Др (Ch, Zn);

показати(Ch,'/', Zn)

кц

ка.

[ЗМІСТ] [Далі] [Назад]