Лекції для студентів 2 курсу Консультації: середа, 15-16 год., кімн. 204/1, к афедра мультимедійних систем Torun, Castle Бублик Володимир Васильович Процедурне. - презентация

1 Лекції для студентів 2 курсу Консультації: середа, год., кімн. 204/1, к афедра мультимедійних систем Torun, Castle Бублик Володимир Васильович Процедурне програмування C/C++ Лекція 8. Функції

2 © 2006 Бублик В.В. Процедурне програмування. 8. Функції2 (50) Процедурна парадигма Процедурне програмування парадигма програмування, заснована на концепції виклику процедури (Wikipedia). Питання: програми безпосередньо в машинних кодах чи в асемблері процедурні? Машина Тьюрінга процедурна?

3 © 2006 Бублик В.В. Процедурне програмування. 8. Функції3 (50) Процедурна парадигма Процедурне програмування парадигма програмування, заснована на концепції виклику процедури (Wikipedia). Питання: програми безпосередньо в машинних кодах чи в асемблері процедурні? Машина Тьюрінга – процедурна? Звісно, так. Procedural program describes, step by step, exactly the procedure that should, according to the particular programmer at least, be followed to solve a specific problem. The efficacy and efficiency of any such solution are both therefore entirely subjective and highly dependent on that programmer's experience, inventiveness and ability (теж Wikipedia).

4 © 2006 Бублик В.В. Процедурне програмування. 8. Функції4 (50) Процедурна парадигма Не плутати з функціональною парадигмою. Остання належить до декларативних. Процедурна, точніше було б сказати алгоритмічна, парадигма імперативна. Те, що Річі назвав процедуру функцією, просто справа смаку. Традиційними мовами процедурного програмування замість void f(parameters) пишуть procedure f(parameters), а замість double f(parameters) пишуть real function f(parameters)

5 © 2006 Бублик В.В. Процедурне програмування. 8. Функції5 (50) Визначення функції //Найбільший спільний дільник за алгоритмом Евкліда //1. Заголовок функції int gcd (int m, int n) //2. Тіло функції { while (m != n) if (m>n) m=m-n; else n=n-m; //3. Вихід з функції і повернення результату return m; }

6 © 2006 Бублик В.В. Процедурне програмування. 8. Функції6 (50) Процедури Як таких, процедур немає, але існують функції, що повертають ніщо (його тип void) // Аналог процедури-підпрограми void showPrice (int cost) { cout<<"Hrn "<

7 This page has been inventively left blank

8 © 2006 Бублик В.В. Процедурне програмування. 8. Функції8 (50) Ліричний відступ: #ifndef _TM_DEFINED struct tm { int tm_sec; // seconds after the minute - [0,59] int tm_min; // minutes after the hour - [0,59] int tm_hour; // hours since midnight - [0,23] int tm_mday; // day of the month - [1,31] int tm_mon; // months since January - [0,11] int tm_year; // years since 1900 int tm_wday; // days since Sunday - [0,6] int tm_yday; // days since January 1 - [0,365] int tm_isdst; // daylight savings time flag }; #define _TM_DEFINED #endif

9 © 2006 Бублик В.В. Процедурне програмування. 8. Функції9 (50) Функції без параметрів Самостійно звертаються до оточення: struct Date { int _day, _month, _year; int _hours, _min, _sec; }; Date getDate(); або Date getDate(void);

10 © 2006 Бублик В.В. Процедурне програмування. 8. Функції10 (50) Функції без параметрів Date getDate() { Date myDate; struct tm * today = new tm; time_t timer; time( &timer ); today = gmtime(&timer); myDate._day = today->tm_mday; myDate._month = ++(today->tm_mon); myDate._year = today->tm_year+=1900; myDate._hours = today->tm_hour; myDate._min = today->tm_min; myDate._sec = today->tm_sec; return myDate; }

11 © 2006 Бублик В.В. Процедурне програмування. 8. Функції11 (50) Оголошення функції //Найбільший спільний дільник за алгоритмом Евкліда //Спосіб 1. З іменами параметрів int gcd (int m, int n); //Спосіб 2. Без імен параметрів int gcd (int, int); Як краще?

12 © 2006 Бублик В.В. Процедурне програмування. 8. Функції12 (50) Промовисті імена У випадку int gcd (int, int); параметри рівноцінні, а тому їх іменування зайве Різні за призначенням, але однотипні параметри корисно іменувати double root (double x, double epsilon); При заголовку double root (double, double) як розуміти виклик root (2.0е-10, 1.0е-10)?

13 © 2006 Бублик В.В. Процедурне програмування. 8. Функції13 (50) Формальні параметри Параметри, вжиті у визначенні функції називаються формальними. Ними служать імена, призначені для позначення аргументів і результатів функції. Формальні параметри локалізовані в тілі функції, вони існують лише протягом її виконання У заголовках int gcd (int m, int n) double exp (double x, double epsilon) параметри int m, int n, double x, double epsilon формальні

14 © 2006 Бублик В.В. Процедурне програмування. 8. Функції14 (50) Фактичні параметри Об'єкти, вжиті у виклику функції, називаються фактичними параметрами. Вони служать для передачі значень аргументів. У цьому випадку вживаються довільні вирази підхожого типу. gcd (a, b); gcd (100, 250); exp (x+y, 1.0e-10); Фактичні параметри можуть також приймати результати виконання функції, якщо це дозволяють формальні параметри (відсилки або указники). В цьому випадку фактичні параметри повинні бути іменами. swap(x,y);

15 © 2006 Бублик В.В. Процедурне програмування. 8. Функції15 (50) Виклик функції int a, b, c; cin>>a>>b; c = gcd (a, b);//1. Ініціалізація параметрів // int m=a; int n=b; //2. Виконання тіла фукції //3. Обчислення результату (c=m;) Взагалі кажучи, виклик функції полягає в припиненні нормального ходу виконання об'єктного коду, що містить виклик. Відбувається ініціалізація параметрів і починає виконуватись об'єктний код функції. Після повернення результату виконання основного коду відновлюється

16 © 2006 Бублик В.В. Процедурне програмування. 8. Функції16 (50) Способи виклику функцій Закрита функція До стеку заносяться значення параметрів і адреса місця продовження обчислень після виходу із функції. Виконується команда переходу в місце розміщення коду функції з наступним поверненням. Власний код функції доповнюється командами роботи зі стеком. Відкрита (вбудована) функція Код функції підставляється в кожне місце виклику, продовжуючи в такий спосіб нормальний хід виконання об'єктного коду

17 © 2006 Бублик В.В. Процедурне програмування. 8. Функції17 (50) Взаємодія функцій шляхом виклику Функція-клієнт і функція-сервер

18 © 2006 Бублик В.В. Процедурне програмування. 8. Функції18 (50) Виклик закритої функції Підготовка до виклику функції: передача параметрів NB. Компілятор знає лише інтерфейс, а не код функції

19 © 2006 Бублик В.В. Процедурне програмування. 8. Функції19 (50) Виклик закритої функції Підготовка до виконання функції: зчитування параметрів NB. Функція не знає, хто її викликав

20 © 2006 Бублик В.В. Процедурне програмування. 8. Функції20 (50) Виконання закритої функції Виконується тіло функції

21 © 2006 Бублик В.В. Процедурне програмування. 8. Функції21 (50) Вихід із закритої функції Підготовка результату

22 © 2006 Бублик В.В. Процедурне програмування. 8. Функції22 (50) Повернення в точку виклику Зчитування результату

23 © 2006 Бублик В.В. Процедурне програмування. 8. Функції23 (50) Продовження виконання програми Зчитування результату

24 © 2006 Бублик В.В. Процедурне програмування. 8. Функції24 (50) Переваги закритих функцій Об'єктний код закритої функції присутній в програмі один раз, а викликатися може із різних місць: уникаємо дублювання коду. Компілятор автоматично генерує відповідні команди керування, що приведуть до активації функції, виконання її коду і наступного повернення в місце виклику для продовження обчислень.

25 © 2006 Бублик В.В. Процедурне програмування. 8. Функції25 (50) Накладні витрати виклику закритої функції 1.Запам'ятовування точки повернення 2.Занесення до стеку значень фактичних параметрів 3.Перехід за місцем знаходження коду функції 4.Зчитування значень формальних параметрів 5.Зчитування точки повернення 6.Занесення до стеку результату 7.Повернення в точку виклику 8.Зчитування результату

26 © 2006 Бублик В.В. Процедурне програмування. 8. Функції26 (50) Об'єктний код закритої функції int max (int x, int y) { 00402A90 push ebp 00402A91 mov ebp,esp 00402A93 push ecx 00402A94 mov dword ptr [ebp-4],0CCCCCCCCh return (x>y)? x :y; 00402A9B mov eax,dword ptr [x] 00402A9E cmp eax,dword ptr [y] 00402AA1 jle max+1Bh (402AABh) 00402AA3 mov ecx,dword ptr [x] 00402AA6 mov dword ptr [ebp-4],ecx 00402AA9 jmp max+21h (402AB1h) 00402AAB mov edx,dword ptr [y] 00402AAE mov dword ptr [ebp-4],edx 00402AB1 mov eax,dword ptr [ebp-4] } 00402AB4 mov esp,ebp 00402AB6 pop ebp 00402AB7 ret

27 © 2006 Бублик В.В. Процедурне програмування. 8. Функції27 (50) Код виклику закритої функції int c = max (a, b); 00402AE4 mov eax,dword ptr [b] 00402AE7 push eax 00402AE8 mov ecx,dword ptr [a] 00402AEB push ecx 00402AEC call max (40100Ah) 00402AF1 add esp, AF4 mov dword ptr [c],eax

28 © 2006 Бублик В.В. Процедурне програмування. 8. Функції28 (50) Код основного оператора int c =(a>b)? a :b; mov edx,dword ptr [a] cmp edx,dword ptr [b] jle main+93h (4010A3h) B mov eax,dword ptr [a] E mov dword ptr [ebp-48h],eax A1 jmp main+99h (4010A9h) A3 mov ecx,dword ptr [b] A6 mov dword ptr [ebp-48h],ecx A9 mov edx,dword ptr [ebp-48h] AC mov dword ptr [c],edx

29 © 2006 Бублик В.В. Процедурне програмування. 8. Функції29 (50) Порівняння кодів 00402A91 mov ebp,esp 00402A93 push ecx 00402A94 mov dword ptr [ebp-4],0CCCCCCCCh return(x>y)? x :y; 00402A9B mov eax,dword ptr [x] 00402A9E cmp eax,dword ptr [y] 00402AA1 jle max+1Bh (402AABh) 00402AA3 mov ecx,dword ptr [x] 00402AA6 mov dword ptr [ebp-4],ecx 00402AA9 jmp max+21h (402AB1h) 00402AAB mov edx,dword ptr [y] 00402AAE mov dword ptr [ebp-4],edx 00402AB1 mov eax,dword ptr [ebp-4] } 00402AB4 mov esp,ebp 00402AB6 pop ebp 00402AB7 ret 00402AE4 mov eax,dword ptr [b] 00402AE7 push eax 00402AE8 mov ecx,dword ptr [a] 00402AEB push ecx 00402AEC call max (40100Ah) 00402AF1 add esp, AF4 mov dword ptr [c],eax // Основне обчислення c =(a>b)? a :b; mov edx,dword ptr [a] cmp edx,dword ptr [b] jle main+93h (4010A3h) B mov eax,dword ptr [a] E mov dword ptr [ebp-48h],eax A1 jmp main+99h (4010A9h) A3 mov ecx,dword ptr [b] A6 mov dword ptr [ebp-48h],ecx A9 mov edx,dword ptr [ebp-48h] AC mov dword ptr [c],edx

30 © 2006 Бублик В.В. Процедурне програмування. 8. Функції30 (50) Вбудовані функції Накладні витрати виклику закритих функцій можна зменшити, якщо розміщувати код функції безпосередньо в місці виклику. Накладними витратами в цьому разі стане дублювання коду в кожному місці виклику. Компілятор сам (при відповідних налаштуваннях) приймає рішення, як реалізувати функцію (inline лише порада). inline double max(double x, double y) { return (x>y)?x:y; }

31 © 2006 Бублик В.В. Процедурне програмування. 8. Функції31 (50) Приблизна схема викликів вбудованих функцій z= max (5, 6); z= max(max(1,2),3); double x = 5; double y = 6; z = (x>y)?x:y; double x = 1; double y = 2; double x1 = (x>y)?x:y; double y1 = 3; z = (x1>y1)?x1:y1;

32 © 2006 Бублик В.В. Процедурне програмування. 8. Функції32 (50) Об'єктний код відкритої функції inline int max(int x, int y) { return(x>y)? x :y; } немає

33 © 2006 Бублик В.В. Процедурне програмування. 8. Функції33 (50) Виклик відкритої функції int c=max (a, b); // Не відрізняється від коду int c =(a>b)? a :b; 00402AB4 mov eax,dword ptr [a] 00402AB7 cmp eax,dword ptr [b] 00402ABA jle main+34h (402AC4h) 00402ABC mov ecx,dword ptr [a] 00402ABF mov dword ptr [ebp-40h],ecx 00402AC2 jmp main+3Ah (402ACAh) 00402AC4 mov edx,dword ptr [b] 00402AC7 mov dword ptr [ebp-40h],edx 00402ACA mov eax,dword ptr [ebp-40h] 00402ACD mov dword ptr [c],eax

34 © 2006 Бублик В.В. Процедурне програмування. 8. Функції34 (50) Макровизначення Макровизначення на перший погляд дуже схожі на вбудовані функції, вони теж підставляються в місця виклику, але відрізняються від вбудованих функцій способом передачі параметрів текстовою підстановкою. Приклад макровизначення #define MAX(x,y) (((x)>(y))?(x):(y)) Приклади макровикликів MAX(1,2); MAX(a+b, c-d);

35 © 2006 Бублик В.В. Процедурне програмування. 8. Функції35 (50) Текстова підстановка #define MAX(x,y) (((x)>(y))?(x):(y)) MAX(1,2) перетвориться на (((1)>(2))?(1):(2)) На що перетвориться MAX(++a, b)? ((++a)>(b))?(++a):(b) int a =5, int b = 1; MAX(++a, b) ==7;

36 © 2006 Бублик В.В. Процедурне програмування. 8. Функції36 (50) Порівняння макровизначень і вбудованих функцій #define SQR(x) ((x)*(x)) k=SQUARE(i); mov edx,dword ptr [i] imul edx,dword ptr [i] C mov dword ptr [k],edx inline sgr(double x) {return x*x;} k=square(i); mov eax,dword ptr [i] imul eax,dword ptr [i] B mov dword ptr [k],eax

37 © 2006 Бублик В.В. Процедурне програмування. 8. Функції37 (50) Порівняння макровизначень і вбудованих функцій #define SQR(x) ((x)*(x)) k=SQUARE(++i); F mov eax,dword ptr [i] A2 add eax, A5 mov dword ptr [i],eax A8 mov ecx,dword ptr [i] AB add ecx, AE mov dword ptr [i],ecx B1 mov edx,dword ptr [i] B4 imul edx,dword ptr [i] B8 mov dword ptr [k],edx inline sgr(double x) {return x*x;} k=square(++i); F mov eax,dword ptr [i] A2 add eax, A5 mov dword ptr [i],eax B1 mov edx,dword ptr [i] B4 imul edx,dword ptr [i] B8 mov dword ptr [k],edx

38 © 2006 Бублик В.В. Процедурне програмування. 8. Функції38 (50) Вбудовані функції і безпосередні обчислення k=i*і; mov edx,dword ptr [i] imul edx,dword ptr [i] C mov dword ptr [k],edx inline sgr(double x) {return x*x;} k=square(i); mov eax,dword ptr [i] imul eax,dword ptr [i] B mov dword ptr [k],eax

39 © 2006 Бублик В.В. Процедурне програмування. 8. Функції39 (50) Висновок Текстова підстановка приводить до повторних обчислень При текстовій підстановці відсутній контроль типів Вбудовані (inline) функції коректно передають параметри, гарантують контроль типів і вільні від накладних витрат виклику Текстова підстановка параметрів некоректна, а тому слід віддавати перевагу вбудованим функціям перед макровизначеннями

40 © 2006 Бублик В.В. Процедурне програмування. 8. Функції40 (50) Виклик функції inline double max(double x, double y) { return (x>y)?x:y; } double a = max(1,2); //double x=1; double y=2; //ініціалізація параметрів //return (1>2)?1:2 == 2 виконання тіла і повернення cout<2)?3:2 == 3

41 © 2006 Бублик В.В. Процедурне програмування. 8. Функції41 (50) Параметри арифметичних типів Розглянемо оголошення функції void f (T); де f ім'я функції, T арифметичний тип Розглянемо виклик цієї функції f(e); де e вираз підходящого типу (фактичний параметр) Виконання функції починається визначенням формального параметру x з його одночасною ініціалізацією T x = e;

42 © 2006 Бублик В.В. Процедурне програмування. 8. Функції42 (50) Передача параметрів значенням Ініціалізація T x = e; говорить про те, що перед виконанням функції обчислюється значення фактичного параметру е (r- value) Кажуть, що параметри передаються значенням

43 © 2006 Бублик В.В. Процедурне програмування. 8. Функції43 (50) Замовчувані значення параметрів Розглянемо визначення функції double power (double x, int n) { double y=1; for (int i=0; i

44 © 2006 Бублик В.В. Процедурне програмування. 8. Функції44 (50) Замовчувані значення параметрів Скрізь, де доступне оголошення double power (double x, int n=3); функцію power () можна викликати як з двома, так і з одним фактичним параметром power (10, 5); power (10); Має те ж саме значення, що power (10, 3);

45 © 2006 Бублик В.В. Процедурне програмування. 8. Функції45 (50) Зауваження Мова дозволяє замовчувані параметри не тільки в оголошеннях, але й визначеннях. НЕ ВАРТО задавати замовчування у визначенні: ним можна користуватися лише у випадку вбудованих функцій. Визначення закритих функцій можуть бути недоступними в точці виклику, а тому компілятор при обробці виклику замовчувань не побачить

46 © 2006 Бублик В.В. Процедурне програмування. 8. Функції46 (50) Замовчувані значення параметрів Більше того, можна взяти оголошення double power (double x = 2, int n=3); Тепер функцію power () можна викликати з двома, з одним фактичним параметром або зовсім без параметрів power (2, 3); те ж саме, що power (2); і те ж саме, що power ();

47 © 2006 Бублик В.В. Процедурне програмування. 8. Функції47 (50) Формальні параметри і локальні змінні Формальні параметри дозволяється застосовувати для проміжних обчислень краще б не дозволялось //Greatest Common Divider int gcd (int m, int n) { while (m != n) if (m>n) m=m-n; else n=n-m; // Початкові значення втрачено // Перевірка правильності результату неможлива // Оцінка 2- return m; }

48 © 2006 Бублик В.В. Процедурне програмування. 8. Функції48 (50) Сталий параметр //Greatest Common Divider int gcd (const int m0, const int n0) { int m = m0, n = n0; while (m != n) if (m>n) m=m-n; else n=n-m; //m == n //Початкові значення не втрачено assert((m0%m==0) && (n0%n==0) ); return m; }

49 © 2006 Бублик В.В. Процедурне програмування. 8. Функції49 (50) Висновок Формальні параметри доцільно визначати як сталі величини. Тоді протягом всього виконання тіла функції точно відомі значення переданих до неї аргументів

50 © 2006 Бублик В.В. Процедурне програмування. 8. Функції50 (50) Повернення результату Результат арифметичного типу, створений у тілі функції, передаємо значенням Для арифметичних типів результат сталого типу не відрізняється від несталого. Для складніших типів це не так Звикайте до сигнатур виду const int gcd (const int, const int)

51 © 2006 Бублик В.В. Процедурне програмування. 8. Функції51 (50) Рекурсія Перетворює визначення в програму const int gcd (const int m, const int n) { if (m>n) return gcd (m, m-n); else return gcd (n, n-m); }

52 © 2006 Бублик В.В. Процедурне програмування. 8. Функції52 (50) Неефективність невдало організованої рекурсії int BadFib(int n) { //Так не варто рахувати!!! if (n==0) return 0; if (n==1) return 1; return BadFib(n-1)+BadFib(n-2); }

53 © 2006 Бублик В.В. Процедурне програмування. 8. Функції53 (50) Висновки 1.Не бійтеся функцій. Всі однотипні обчислення заміняйте викликом функції 2.Пам'ятайте, що параметри передаються значеннями, а тому модифікація формального параметру арифметичного типу взагалі не впливає на фактичний 3.Тому захищайте формальний параметр кваліфікатором const 4.Звикайте те ж саме робити з типом результату 5.Не бійтеся рекурсії. Бійтеся розгалуженої рекурсії, яка приводить до експоненціальної складності