Programování pro fyziky 2022/23 – přednáška č. 7

Dnešní téma nás vyzbrojí k procedurálnímu programování. Chápejme jej jako vítanou možnost, jak pomocí procedur a funkcí rozšířit možnosti imperativního strukturovaného programování. Funkcionální programování jde ještě dále, možnost tlačí spíš až k nutnosti, snaží se nahradit i samotný imperativní strukturovaný styl.

Funkce a procedury

Členění zdrojového kódu do menších úseků (jednotek, program units) má řadu výhod: oddělenost jednotek přináší lepší srozumitelnost a testovatelnost; zřetelné hranice jednotek (lokalita, scoping) umožňují přesné definování vstupních a výstupních dat a zapouzdření lokálních dat; dobře navržené procedury lze používat opakovaně, mohou se sdružovat do knihoven (libraries). Funkce (functions) se podobně jako v matematice používají pro získání jedné návratové hodnoty, procedury (procedures, subprograms, subroutines) jsou určeny pro ostatní účely; některé jazyky procedury nemají a simulují je pomocí funkcí. Voláním jména funkce ve výrazu, resp. příkazem volání procedury se provede odskok na začátek funkce či procedury, po jejím vykonání se chod programu vrací zpět na místo volání. S volající programovou jednotkou komunikují funkce/procedury jednak prostřednictvím svého rozhraní, tj. svých argumentů (parametrů), jednak prostřednictvím dat známých oběma jednotkám (globální data). Data deklarovaná ve funkci/proceduře jsou zapouzdřená, vně nedostupná (lokální data).

Pascal nabízí funkce i procedury. Jednoduchou možností strukturování programu je jejich vnoření do hlavního programu. Data deklarovaná nad funkcí/procedurou jsou vůči nim globální, přístupná, data deklarovaná pod nimi jsou jim nedostupná.

// Pascal: funkce, procedury, globální proměnné
program p01;
var
  defaultValue : real = 0;           // globální proměnná
  nmax : integer = 3;

// funkce
function f(n : integer) : real;      // result předdefinováno pro návratovou hodnotu funkce
begin
  if n>0 then result:=1/n else result:=defaultValue;
end;

// procedura
procedure p(n : integer);
var result : real;                   // lokální proměnná procedury
begin
  if n>0 then result:=1/n else result:=defaultValue;
  write(result);
end;

var n : integer;                     // lokální proměnná hlavního programu
begin
  for n:=-1 to nmax do write(f(n));  // volání funkce je výraz
  writeln;
  for n:=-1 to nmax do p(n);         // volání procedury je příkaz
  writeln;
end.

Ve Fortranu je to podobné: používají se funkce a podprogramy (subroutines). Mohou být řazeny sekvenčně nebo, jako zde, vnořeny na konec hostitelské programové jednotky. Data hostitele jsou pro vnořené jednotky globální.

! Fortran: funkce, podprogramy, globální proměnné
program p01
real :: defaultValue=0                       ! globální proměnná
integer :: nmax=3

do n=-1,nmax; print '(x,f0.5$)',f(n); enddo  ! volání funkce je výraz
print *
print '(*(x,f0.5))',(f(n),n=-1,nmax)         ! alternativa: implied-do list (cyklický seznam)
do n=-1,nmax; call p(n); enddo               ! volání procedury je příkaz
print *

contains

! funkce
function f(n) result (result)                ! klauzule result pro návratovou hodnotu funkce
  ! print *,'in f'                           ! ukázka problematického vedlejšího účinku funkce
  result=merge(1./n,defaultValue,n>0)
end function

! podprogram
subroutine p(n)
  print '(x,f0.5$)',merge(1./n,defaultValue,n>0)
end subroutine

end program

V Pythonu se žije bez procedur, ale snadno, procedury se simulují funkcemi bez návratové hodnoty (neboli s prázdnou návratovou hodnotou, return None). Funkce mohou být řazeny sekvenčně, mohou se i vnořovat, význam globálních dat mají data existující při odskoku do funkce. Pro zápis do nich je třeba je ve funkci uvést v popisu global.

# Python: funkce, procedury, globální proměnné
defaultValue=0.                                 # globální proměnná
nmax=3

# funkce
def f(n):
  return 1/n if n>0 else defaultValue

# funkce bez návratové hodnoty (ekvivalent procedury)
def p(n):
  print(1/n if n>0 else defaultValue,end=' ')

for n in range(-1,nmax+1): print(f(n),end=' ')  # volání funkce
print()
print(*[f(n) for n in range(-1,nmax+1)])        # alternativa: list comprehension
for n in range(-1,nmax+1): p(n)                 # volání procedury
print()

Existují-li v programovacím jazyce procedury, patří k dobrému stylu omezit používání funkcí výhradně k přípravě návratové hodnoty, tedy vyhýbat se vedlejším účinkům funkcí. Těmi mohou být změny argumentů promítající se vně funkce, změny globálních proměnných, výpisy na obrazovku nebo do souborů aj. Riziko vedlejších účinků je v jejich zrádnosti: často nevadí, stačí ale mírná změna kontextu a projeví se chybou nebo problémem, jejichž vystopování je pak spíše obtížné. Pěknou ukázkou může být vložení (rekurzivního) výpisu do fortranské funkce použité v příkazu výpisu: program zhavaruje, někdy dokonce i zcela mlčky. Nebo: modifikovat globální data v pythonských funkcích lze, ale znemožní se tím překlad a zrychlení funkcí pomocí modulu Numba.

V objektově orientovaném programování (OOP) se mohou funkce a procedury (zde: metody) vázat na strukturovaný typ (třídu) a potažmo na proměnnou tohoto typu (objekt). Objekt je typicky argumentem metod, což inspirovalo alternativní syntaxi volání: místo method(object,other_arguments) lze volat object.method(other_arguments). V Pythonu je často v nabídce obojí volání, ale někdy jen procedurální, jindy jen objektové, anebo je omezena jejich použitelnost. Např. dotaz na velikost NumPy polí size má obě podoby, ale spolu s Numbou lze použít jen objektový zápis A.size:

# Python: OOP syntaxe
import numpy as np
from numba import njit
def test1():
  A=np.zeros((2,2))
  print(np.size(A),A.size,np.shape(A),A.shape)  # výpis: 4 4 (2, 2) (2, 2)
  B=np.ones(A.shape)
  print(sum(sum(B)),B.sum())                    # výpis: 4.0 4.0
@njit
def test2():
  A=np.zeros((2,2))
  print(A.size,np.shape(A),A.shape)  # njit nekompatibilní s np.size(A)
  B=np.ones(A.shape)
  print(B.sum())                     # njit nekompatibilní se sum(B)
test1()
test2()

Předávání argumentů

Úkolem je zajistit jednak jednosměrné předávání vstupních argumentů (z místa volání do funkce/procedury) a výstupních argumentů (z funkce/procedury ven), jednak obousměrné předávání argumentů, které tak jsou vstupně-výstupní. Snahou též bývá zajistit efektivní předávání rozměrnějších dat, tj. polí a struktur. V klasických programovacích jazycích se to děje tzv. předáváním hodnotou nebo odkazem (call by value/by reference). Předání hodnotou znamená vytvoření nového paměťového místa, do kterého je zkopírována hodnota argumentu z volající jednotky (tím může být proměnná nebo hodnota vypočteného výrazu); při návratu se hodnota zpět nekopíruje. Předání odkazem předpokládá, že předávaný argument má své paměťové místo (musí být adresovatelný). Do volané jednotky se předá adresa argumentu; případné změny argumentu prováděné uvnitř procedury se pak realizují vně, v paměťovém místě předaného argumentu. Pokud se vstupní argumenty v proceduře nemění, je vhodnější je výslovně označit jako konstantní. Zvláště vhodné je předávat odkazem paměťově náročné argumenty, např. velká pole.

V Pascalu je defaultem předávání hodnotou, použitelné pro vstupní argumenty; pokud se vstupní argument v jednotce nemění, je vhodnější uvést jej klauzulí const. Výstupní argumenty se značí klauzulí out a vstupně-výstupní klauzulí var pro předání odkazem. Následující procedura načte svůj první a druhý argument a změní a vrátí druhý a třetí argument. Volba způsobu předání prvního argumentu (hodnotou nebo odkazem) je na překladači, druhý i třetí argument se předají odkazem.

// Pascal: předávání argumentů (vstupní: xin, x, výstupní: x, xout)
program p02;
  procedure p(const xin : real; var x : real; out xout : real);
  begin
    x:=xin+x;
    xout:=xin+x;
  end;
var x1,x2,x3 : real;
begin
  x1:=1; x2:=1;
  p(x1,x2,x3);
  writeln(x1,x2,x3);  // výpis: 1. 2. 3.
end.

Ve Fortranu se implicitně předává odkazem. Pokud se předávají argumenty bez adresy (např. literály nebo vyčíslené výrazy), nesmí se modifikovat. Vhodné je označit vstupní argumenty atributem intent(in), čímž se zajistí jejich nezměnitelnost v proceduře, a mohou pak přijmout i argumenty bez adresy. Výstupní argumenty s intent(out) a vstupně-výstupní s intent(inout) se předávají odkazem a překladač ověří, že příslušné skutečné argumenty jsou adresovatelné.

! Fortran: předávání argumentů (vstupní: xin, x, výstupní: x, xout)
program p02
x1=1.; x2=1.
call p(x1,x2,x3)
print *,x1,x2,x3       ! výpis: 1. 2. 3.

contains

subroutine p(xin,x,xout)
real,intent(in) :: xin
real,intent(inout) :: x
real,intent(out) :: xout
x=xin+x
xout=xin+x
end subroutine

end program

V Pythonu můžeme předávání argumentů shrnout tak, že všechny argumenty jsou vstupní, nemohou být zaměněny za jiné, ale jsou-li modifikovatelné (mutable), tedy např. seznamy, slovníky nebo NumPy pole, může být změněn jejich obsah. Měnit nelze neměnné (immutable) argumenty, což jsou skaláry standardních typů, n-tice (tuples) aj. Návratová hodnota funkce je vlastně výstupním argumentem, a protože návratových hodnot v Pythonu může být více, realizuje se tak i možnost více výstupních argumentů.

# Python: předávání argumentů (vstupní: xin, x, výstupní: x, xout)
def p(xin,x):
  x=xin+x
  xout=xin+x
  return (x,xout)
x1=1.; x2=1.
(x2,x3)=p(x1,x2)
print(x1,x2,x3)        # výpis: 1. 2. 3.

Předávat lze i odkazy na funkce a procedury – procedurální argumenty. Lze vyznačit nepovinné, volitelné argumenty. Přiřazovat skutečné argumenty (použité ve volání funkce/procedury) k formálním argumentům (uvedeným v hlavičce funkce/procedury) se může pozičně nebo pomocí jmen formálních argumentů.

// Pascal: procedurální a volitelné argumenty, přiřazení jen poziční
program p02_opt;

type tF=function (const x : real) : real;               // typ pro procedurální argument
function f1(const x : real) : real; begin f1:=x end;
function f2(const x : real) : real; begin f2:=x*2 end;
procedure p(f : tF; var x : real; const d : real = 1);  // první argument procedurální, třetí volitelný
begin x:=f(x); x:=x+d end;

var x : real;
begin                            // výpis: 2. 4.
  x:=1; p(@f1,x); writeln(x);    // procedurální argument s adresním operátorem, bez třetího argumentu
  x:=1; p(@f2,x,2); writeln(x);
end.
! Fortran: procedurální a volitelné argumenty, přiřazení poziční nebo jménem
program p02_opt                         ! výpis: 2. 4.
x=1.; call p(f1,x); print *,x           ! bez třetího argumentu
x=1.; call p(x=x,d=2.,f=f2); print *,x  ! argumenty přiřazeny pomocí formálních jmen
contains

function f1(x); f1=x; end function
function f2(x); f2=x*2; end function
subroutine p(f,x,d)
real,optional :: d                      ! volitelný argument testovatelný funkcí present
real :: default=1.
x=f(x); if (present(d)) then; x=x+d; else; x=x+default; endif
end subroutine
end program
# Python: procedurální a volitelné argumenty, přiřazení poziční nebo jménem
def f1(x): return x
def f2(x): return x*2
def p(f,x,d=1.):
  x=f(x); x=x+d
  return x
                                        # výpis: 2. 4.
x=1.; x=p(f1,x); print(x)               # bez třetího argumentu
x=1.; x=p(x=x,d=2.,f=f2); print(x)      # argumenty přiřazeny pomocí formálních jmen

Přiřazení argumentu jménem formálního argumentu je možné i pro standardní funkce jazyka. Jaká výhoda, když je editor (např. VS Code) poučený a popis rozhraní standardních i vlastních funkcí a procedur při editaci nabízí.

Rekurzivní funkce

Rekurzivní neboli na sebe se odvolávající zápisy jsou v matematice běžné s účelem převést úlohu na obdobnou, ale jednodušší. Např. pro n-faktoriál píšeme:

\[\begin{split}\begin{array}{rcl} 0! & = & 1\\ N! & = & N(N-1)! \quad\mbox{ pro }\quad N=1,\dots \end{array}\end{split}\]

V leckterých případech (i zde) existuje sice i alternativní nerekurzivní zápis, \(N!=\prod_{n=1}^N n\), ne však vždy. Rekurzivní algoritmy se často používají např. při práci s dynamickými datovými strukturami nebo při řešení úlohy půlením. (Př. Setřídit pole? Setřiď obě poloviny a vhodně je sluč.) Programovací jazyky rekurzivní volání funkcí a procedur umožňují, přímo (jednotka volá sama sebe) i nepřímo (první jednotka volá druhou, druhá volá první). Nezbytnou součástí rekurzivní funkce/procedury je podmíněný příkaz s testem ukončení (zde: nerekurzivní větev pro 0-faktoriál).

Ukázka: nerekurzivní a rekurzivní implementace výpočtu součtu řady (raději než součinu ve faktoriálu, který brzy přeteče). V nerekurzivní funkci je počet aritmetických operací úměrný nmax, jak vidíme přímo z mezí cyklu. V rekurzivní funkci to bude také tak, a navíc se přičítá režie pro opakované volání (zanořování se do) funkce. To stojí nejen čas, ale i paměť, a zanoříme-li se hlouběji, snadno narazíme na limity systému. Nejhlouběji (ve Windows) je ochoten se zanořit Free Pascal (100000×), méně GNU Fortran a Python s Numbou (řádově 10000×, pak běh tiše spadne), nejméně Python bez Numby (řádově 1000×).

// Pascal: součet řady v cyklu vs. rekurzivně
program p03;
const
  imax = 1000;                    // počet opakování výpočtu
  nmax = 100000;                  // argument pro výpočet

// sčítání v cyklu
function Sum(const nmax : integer) : real;
var n : integer;
begin
  result:=0;
  for n:=1 to nmax do result:=result+n;
end;

// rekurzivní funkce
function SumRec(const n : integer) : real;
begin
  if n<=0 then result:=0          // test ukončení
  else result:=n+SumRec(n-1);     // rekurzivní volání
end;

var
  result : real;
  i : integer;
begin
  write('V cyklu...    ');
  for i:=1 to imax do result:=Sum(nmax);
  writeln(nmax,' ',result);
  write('Rekurzivne... ');
  for i:=1 to imax do result:=SumRec(nmax);
  writeln(nmax,' ',result);
end.
! Fortran: součet řady v cyklu vs. rekurzivně
program p03
real(8) result
imax = 10000                       ! počet opakování výpočtu
nmax = 10000                       ! argument pro výpočet
print '(a$)','V cyklu...    '
do i=1,imax; result=Sum(nmax); enddo
print *,nmax,result
print '(a$)','Rekurzivne... '
do i=1,imax; result=SumRec(nmax); enddo
print *,nmax,result

contains

! sčítání v cyklu
real(8) function Sum(nmax) result (result)
result=0
do n=1,nmax; result=result+n; enddo
end function

! rekurzivní funkce
real(8) recursive function SumRec(n) result (result)
if (n<=0) then; result=0           ! nerekurzivní větev
else; result=n+SumRec(n-1); endif  ! rekurzivní volání
end function

end program
# Python: součet řady v cyklu vs. rekurzivně
import sys
from numba import njit
sys.setrecursionlimit(1000000)
imax = 10000                       # počet opakování výpočtu
nmax = 10000                       # argument pro výpočet (s Numbou lze více než bez ní)

# sčítání v cyklu
@njit
def Sum(nmax):
  result=0
  for n in range(1,nmax+1): result+=n
  return result

# rekurzivní funkce
@njit
def SumRec(n):
  if n<=0:
    result=0                       # nerekurzivní větev
  else:
    result=n+SumRec(n-1)           # rekurzivní volání
  return result

print('V cyklu...   ',end='')
for i in range(1,imax+1): result=Sum(nmax)
print(nmax,result)
print('Rekurzivne...',end='')
for i in range(1,imax+1): result=SumRec(nmax)
print(nmax,result)

Citlivé je užívání procedur s vícenásobným rekurzivním voláním. Je to v pořádku, pokud vícenásobná rekurze odpovídá vnitřní struktuře algoritmu nebo dat (např. při průchodu binárním stromem). Vícenásobná rekurze nad lineární strukturou (např. nad posloupností) ovšem hrozí plýtváním. Ukázka pro Fibonacciho posloupnost:

\[\begin{split}\begin{array}{rcl} F_0 & = & 0\\ F_1 & = & 1\\ F_N & = & F_{N-1}+F_{N-2} \quad\mbox{ pro }\quad N=2,\dots \end{array}\end{split}\]

Při volání podle definice, result:=FibRec(N-1)+FibRec(N-2), roste výpočetní složitost s N exponenciálně, neboť FibRec(N-2) se vyčísluje dvakrát – explicitně i v rámci volání Fibrec(N-1), a tyto duplicitní výpočty přibývají pořád dál. Např. pro nmax=40 se v jedenkrát volané funkci Fib provede necelých 40 sčítání a kolem stovky přiřazení, zatímco funkce FibRec s testem, sčítáním a přiřazením se volá 204668309×:

// Pascal: Fibonacciho posloupnost
program p03_fib;
const
  nmax = 45;                             // limit

// výpočet v cyklu
function Fib(const nmax : integer) : integer;
var
  n,F1,F2 : integer;
begin
  result:=1; F1:=1; F2:=1;
  for n:=3 to nmax do begin
    result:=F1+F2; F2:=F1; F1:=result;
  end;
end;

// rekurzivní funkce
function FibRec(const n : integer) : integer;
begin
  if n<3 then result:=1                  // test ukončení
  else result:=FibRec(n-1)+FibRec(n-2);  // rekurzivní volání
end;

var
  result : integer;
  n : integer;
begin
  writeln('V cyklu...');
  for n:=1 to nmax do begin
    result:=Fib(n);
    writeln(n,' ',result);
  end;
  writeln('Rekurzivne...');
  for n:=1 to nmax do begin
    result:=FibRec(n);
    writeln(n,' ',result);
  end;
end.

Populární aplikací rekurzivní procedury je přesouvání hanojské věže. Wikipedie přináší odstavec o rekurzi v umění i humoru.

Modularizace

Některé jazyky umožňují poskládat procedury do zdrojového kódu sekvenčně v libovolném pořadí, jindy je možné procedury vnořovat do těla programu (nebo jiné procedury), jindy sdružovat do samostatných modulů, které se pak k programům explicitně připojují. Sekvenční řazení a vnořování jsme viděli výše, teď jsou na řadě ukázky modularizace.

Pascalský modul (unit) slouží jako kolekce (souvisejících) dat, funkcí a procedur. Moduly mohou obsahovat veřejná (public) i soukromá (private) data a jednotky procedury. Veřejná data a jednotky se vyjmenují v rozhraní modulu (interface), všechny jednotky se pak umístí do implementační části modulu (implementation). Modul se připojí pomocí příkazu uses:

// Pascalský modul (soubor m.pas)
unit m;

interface                    // rozhraní modulu
var nmax : integer = 100;    // modulová proměnná
procedure p();               // rozhraní veřejné procedury
function f(x : real) : real; // rozhraní veřejné funkce

implementation               // implementační část
procedure p();               // definice procedury
  begin writeln('in p') end;
function f(x : real) : real; // definice funkce
  begin result:=x end;
end.
// Program připojující pascalský modul (samostatný soubor)
program p04;
uses m;                      // připojení modulu
begin
  p();
  writeln(f(1),' ',nmax)
end.

Ekvivalentní postup ve Fortranu lze zapsat do jediného souboru:

! Fortranský modul
module mProcedures
integer :: nmax=100           ! modulová proměnná
contains
subroutine p()                ! modulový podprogram
  print *,'in p'
end subroutine
function f(x)                 ! modulová funkce
  f=x
end function
end module

! Program připojující fortranský modul
program p04
use mProcedures               ! připojení modulu
call p()
print *,f(1.),nmax
end program

V Pythonu se modul vytvoří shrnutím funkcí do samostatného souboru a ten se pak na vhodném místě skriptu importuje:

# Pythonský modul (soubor m.py)
nmax=100
def p():                      # modulová procedura
  print('in p')
def f(x):                     # modulová funkce
  return x
# Skript připojující pythonský modul (samostatný soubor)
import m                      # připojení modulu
m.p()
print(m.f(1.),m.nmax)

Modulové proměnné jsou další cestou, jak realizovat globální proměnné.

Na závěr shrnujeme zdrojové soubory ukázek.