Parametr proceduralny

W informatyce parametr proceduralny jest parametrem procedury , która sama jest procedurą.

Ta koncepcja jest niezwykle potężnym i wszechstronnym narzędziem programistycznym , ponieważ pozwala programistom modyfikować pewne kroki procedury bibliotecznej w dowolnie skomplikowany sposób, bez konieczności rozumienia lub modyfikowania kodu tej procedury.

To narzędzie jest szczególnie skuteczne i wygodne w językach obsługujących lokalne definicje funkcji , takich jak Pascal i współczesny dialekt GNU języka C. Jest jeszcze bardziej, gdy dostępne są domknięcia funkcji . Tę samą funkcjonalność (i więcej) zapewniają obiekty w obiektowych językach programowania , ale za znacznie wyższą cenę.

Parametry proceduralne są w pewnym stopniu związane z koncepcjami funkcji pierwszej klasy i funkcji anonimowej , ale różnią się od nich. Te dwie koncepcje mają więcej wspólnego ze sposobem definiowania funkcji niż z tym, jak są używane.

Podstawowy pomysł

W większości języków, które zapewniają tę funkcję, parametr proceduralny f podprogramu P można wywołać wewnątrz ciała P , tak jakby to była zwykła procedura:

   procedura  P  (  f  ):  powrót  f  (6,3) *  f  (2,1)

Wywołując podprogram P , należy podać mu jeden argument, którym musi być jakaś wcześniej zdefiniowana funkcja zgodna ze sposobem, w jaki P używa swojego parametru f . Na przykład, jeśli zdefiniujemy

   procedura  plus  (  x  ,  y  ):  powrót  x  +  y

wtedy możemy nazwać P ( plus ), a wynikiem będzie plus (6,3) * plus (2,1) = (6 + 3)*(2 + 1) = 27. Z drugiej strony, jeśli zdefiniujemy

   procedura  quot  (  u  ,  v  ):  powrót  u  /  v

wtedy wywołanie P ( quot ) zwróci quot (6,3)* quot (2,1) = (6/3)*(2/1) = 4. Wreszcie, jeśli zdefiniujemy

  procedura  zło  (  z  )  powrót  z + 100

wówczas wywołanie P ( zły ) nie będzie miało większego sensu i może zostać oznaczone jako błąd.

Szczegóły składniowe

Niektóre języki programowania, które mają tę cechę, mogą zezwalać lub wymagać pełnej deklaracji typu dla każdego parametru proceduralnego f , w tym liczby i typu jego argumentów oraz typu wyniku, jeśli taki istnieje. Na przykład w języku programowania C powyższy przykład można zapisać jako

      
       
 int  P  (  int  (  *  fa  ) (  int  a  ,  int  b  ))  {  return  fa  (  6  ,  3  )  *  fa  (  2  ,  1  );  }

W zasadzie rzeczywista funkcja actf , która jest przekazywana jako argument podczas wywoływania P , musi być zgodna typu z zadeklarowanym typem parametru procedury f . Zwykle oznacza to, że actf i f muszą zwracać ten sam typ wyniku, muszą mieć taką samą liczbę argumentów, a odpowiednie argumenty muszą być tego samego typu. Nazwy argumentów nie muszą być jednak takie same, na co wskazują znaki plus i quot przykłady powyżej. Jednak niektóre języki programowania mogą być bardziej restrykcyjne lub bardziej liberalne w tym zakresie.

Określanie zakresu

W językach, które dopuszczają parametry proceduralne, reguły określania zakresu są zwykle definiowane w taki sposób, że parametry proceduralne są wykonywane w ich natywnym zakresie. Dokładniej, załóżmy, że funkcja actf jest przekazywana jako argument do P , jako jej parametr proceduralny f ; i f jest następnie wywoływana z wnętrza ciała P . Podczas wykonywania actf widzi środowisko swojej definicji. ^{[ potrzebny przykład ]}

Wdrożenie tych zasad określania zakresu nie jest trywialne. Do czasu ostatecznego wykonania actf rejestry aktywacji , w których znajdują się zmienne środowiskowe, mogą znajdować się dowolnie głęboko w stosie. Jest to tak zwany problem funargu skierowanego w dół .

Przykład: ogólne sortowanie przez wstawianie

Pojęcie parametru proceduralnego najlepiej wyjaśnią przykłady. Typowym zastosowaniem jest następująca ogólna implementacja sortowania przez wstawianie , który przyjmuje dwa parametry całkowite a , b i dwa parametry proceduralne prec , swap :

    
           
             procedura  isort  (  a  ,  b  ,  prec  ,  swap  ):  liczba całkowita  i  ,  j  ;  ja  ←  za  ;  podczas gdy  ja  ≤  b  zrobić  j  ←  ja  ;  podczas gdy  j  >  a  i  prec  (  j  ,  j  −1)  zamień  miejscami  (  j  ,  j  −1);  jot  ←  jot  -1;  ja  ←  ja  +1;

Tej procedury można użyć do sortowania elementów od x [ a ] do x [ b ] jakiejś tablicy x dowolnego typu w kolejności określonej przez użytkownika. Parametry prec i swap powinny być dwiema funkcjami zdefiniowanymi przez klienta, obie przyjmujące dwie liczby całkowite r , s z przedziału a i b . Funkcja prec powinna zwracać wartość true wtedy i tylko wtedy, gdy dane przechowywane w x [ r ] powinno poprzedzać dane przechowywane w x [ s ], w kolejności określonej przez klienta. Funkcja zamiany powinna wymieniać zawartość x [ r ] i x [ s ] i nie zwracać żadnego wyniku.

Dzięki odpowiedniemu doborowi funkcji prec i swap ta sama procedura isort może być wykorzystana do zmiany kolejności tablic dowolnego typu, przechowywanych na dowolnym nośniku i zorganizowanych w dowolną strukturę danych, która zapewnia indeksowany dostęp do poszczególnych elementów tablicy. (Należy jednak pamiętać, że istnieją algorytmy sortowania , które są znacznie bardziej wydajne niż sortowanie przez wstawianie w przypadku dużych tablic).

Sortowanie liczb zmiennoprzecinkowych

Na przykład, możemy posortować tablicę z 20 liczb zmiennoprzecinkowych, od z [1] do z [20] w porządku rosnącym, wywołując isort (1, 20, zprec , zswap ), gdzie funkcje zprec i zswap są zdefiniowane jako

    procedura  zprec  (  r  ,  s  ):  powrót  (  z  [  r  ] <  z  [  s  ]);  procedura  zswap  (  r  ,  s  ):  float  t  ;  t  ←  z  [  r  ];  z  [  r  ] ←  z  [  s  ];  z  [  s  ] ←  t

Sortowanie wierszy macierzy

Dla innego przykładu, niech M będzie macierzą liczb całkowitych z 10 wierszami i 20 kolumnami, z indeksami zaczynającymi się od 1. Poniższy kod przestawi elementy w każdym wierszu, tak aby wszystkie parzyste wartości były przed wszystkimi nieparzystymi:

    liczba całkowita  i  procedura  eoprec  (  r  ,  s  ):  return  (  M  [  i  ,  r  ]  mod  2) < (  M  [  i  ,  s  ]  mod  2);  procedura  eoswap  (  r  ,  s  ):  liczba całkowita  t  ;  t  ←  M  [  ja  ,  r  ];  M  
     [  ja  ,  r  ] ←  M  [  ja  ,  s  ];  M  [  ja  ,  s  ] ←  t  ;  dla  i  od 1  do  10  do  isort  (1, 20, eoprec, eoswap);

Zauważ, że efekty eoprec i eoswap zależą od numeru wiersza i , ale procedura isort nie musi o tym wiedzieć.

Procedura sortowania wektorów

Poniższy przykład używa isort do zdefiniowania procedury vecsort , która pobiera liczbę całkowitą n i wektor liczb całkowitych v z elementami od v [0] do v [ n −1] i sortuje je w kolejności rosnącej lub malejącej, w zależności od tego, czy trzeci parametr incr jest odpowiednio prawdą lub fałszem :

    
             
               procedura  vecsort  (  n  ,  v  ,  incr  ):  procedura  vprec  (  r  ,  s  ):  jeśli  incr  to  zwróć  v  [  r  ] <  v  [  s  ];  w przeciwnym razie  zwróć  v  [  r  ] >  v  [  s  ];  procedura  vswap  (  r  ,  s  

     ):  liczba całkowita  t  ;  t  ←  v  [  r  ];  v  [  r  ] ←  v  [  s  ];  v  [  s  ] ←  t  issort  (0,  n  −1,  vprec  ,  vswap  );

Zwróć uwagę na użycie definicji funkcji zagnieżdżonych w celu uzyskania funkcji vprec , której efekt zależy od parametru incr przekazanego do vecsort . W językach, które nie pozwalają na zagnieżdżone definicje funkcji, takich jak standard C, uzyskanie tego efektu wymagałoby raczej skomplikowanego i/lub niebezpiecznego dla wątków kodu.

Przykład: połączenie dwóch sekwencji

Poniższy przykład ilustruje użycie parametrów proceduralnych do przetwarzania abstrakcyjnych struktur danych niezależnie od ich konkretnej implementacji. Problem polega na połączeniu dwóch uporządkowanych ciągów rekordów w jeden posortowany ciąg, gdzie charakter rekordów i kryterium uporządkowania może wybrać klient. Poniższa implementacja zakłada tylko, że do każdego rekordu można się odwoływać za pomocą adresu pamięci i istnieje „adres zerowy” Λ, który nie jest adresem żadnego ważnego rekordu. Klient musi podać adresy A , B pierwszych rekordów w każdej sekwencji oraz funkcje prec , next i append , które zostaną opisane później.

  
     
            procedura  scalania  (  A  ,  B  ,  prec  ,  nextA  ,  appendA  ,  nextB  ,  appendB  ):  adres  ini  ,  fin  ,  tini  ←  Λ;  fin  ← Λ  podczas gdy  A  ≠ Λ lub  B  ≠ Λ  zrobić  , jeśli  B  = Λ  lub  (  A  ≠ Λ  i  B  ≠ Λ  i  prec 
              
            
        
              (  A  ,  B  ))  następnie  t  ←  następny A  (  A  )  koniec  ← dołącz A (  A  ,  koniec  );  jeśli  ini  = Λ  to  ini  ←  koniec  A  ←  t  inaczej  t  ←  następnyB  (  B  )  koniec  ←  dołączB  (  B  ,  koniec  );  jeśli  ini  
            
      = Λ  wtedy  ini  ←  fin  B  ←  t  return  ini

Funkcja prec powinna przyjąć adresy r , s dwóch rekordów, po jednym z każdej sekwencji, i zwrócić prawdę , jeśli pierwszy rekord powinien wystąpić przed drugim w sekwencji wyjściowej. Funkcja nextA powinna pobrać adres rekordu z pierwszej sekwencji i zwrócić adres następnego rekordu w tej samej sekwencji lub Λ, jeśli go nie ma. Funkcja appendA powinna dołączyć pierwszy rekord z sekwencji A do sekwencji wyjściowej; jego argumentami są adresy A rekordu, który ma zostać dołączony, oraz adres fin ostatniego rekordu listy wyjściowej (lub Λ, jeśli ta lista jest jeszcze pusta). Procedura appendA powinna zwrócić zaktualizowany adres ostatniego elementu listy wyjściowej. Procedury nextB i appendB są analogiczne dla drugiej sekwencji wejściowej.

Scalanie połączonych list

Aby zilustrować użycie ogólnej procedury łączenia, oto kod służący do łączenia dwóch prostych połączonych list , zaczynając od węzłów pod adresami R , S . Tutaj zakładamy, że każdy rekord x zawiera pole liczb całkowitych x . INFO i pole adresowe x . NEXT , który wskazuje następny węzeł; gdzie informacyjne są w porządku rosnącym na każdej liście. Listy wejściowe są demontowane przez scalanie, a ich węzły są używane do budowania listy wyjściowej.

   

      

        procedura  listmerge  (  R  ,  S  ):  procedura  prec  (  r  ,  s  ):  powrót  r  .  INFORMACJE  <  s  .  Procedura  INFO  następna  (  x  ):  powrót  x  .  NASTĘPNA  procedura  dodaj  (  x  ,  fin  )  jeśli  fin  ≠ Λ  to  fin  . 
         
     
      DALEJ  ←  x  x  .  NEXT  ← Λ  return  x  return  scalanie  (  R  ,  S  ,  prec  ,  next  ,  append  ,  next  ,  append  )

Scalanie wektorów

Poniższy kod ilustruje niezależność ogólnej procedury scalania od rzeczywistej reprezentacji sekwencji. Łączy elementy dwóch zwykłych tablic U [0] do U [ m −1] i od V [0] do V [ n −1] liczb zmiennoprzecinkowych w kolejności malejącej. Tablice wejściowe nie są modyfikowane, a połączona sekwencja wartości jest przechowywana w trzecim wektorze W [0] do W [ m + n −1]. Podobnie jak w języku programowania C, zakładamy, że wyrażenie „& V ” daje adres zmiennej V , „* p ” zwraca zmienną, której adresem jest wartość p , a „&( X [ i ])” to odpowiednik "&( X [0]) + i " dla dowolnej tablicy X i dowolnej liczby całkowitej i .

        procedura  arraymerge  (  U  ,  m  ,  V  ,  n  ,  W  ):  procedura  prec  (  r  ,  s  ):  powrót  (*  r  ) > (*  s  )  procedura  nextU  (  x  ):  if  x  = &(  U  [  m  −1])  następnie  zwróć  Λ,  w przeciwnym razie  zwróć  x           + 1  procedura  nextV  (  x  ):  jeśli  x  = &(  V  [  n  −1])  to  zwróć  Λ  w przeciwnym razie  zwróć  x  + 1  procedura  dołącz  (  x  ,  fin  )  jeśli  fin  = Λ  to  fin  ← &(  W  [0]) ( *  płetwa  ) ← (*  x  )  powrót  płetwa     + 1  jeśli  m  = 0 to  U  ← Λ  jeśli  n  = 0 to  V  ← Λ  powrót  scalanie  (  U  ,  V  ,  prec  ,  nextU  ,  append  ,  nextV  ,  append  )

Przykład: Całka oznaczona

Całkowanie po przedziale

Poniższa procedura oblicza przybliżoną całkę ${\ Displaystyle \ textstyle \ int _ {a} ^ {b}}$ fa ( x ) re x danej funkcji o wartościach rzeczywistych f w danym przedziale [ a , b ] z prawdziwa linia . Stosowaną metodą numeryczną jest reguła trapezu z zadaną liczbą n kroków; liczby rzeczywiste są aproksymowane liczbami zmiennoprzecinkowymi.

   
        0
     
         procedura  Intg  (  f  ,  a  ,  b  ,  n  ):  float  t  ,  x  ,  s  ;  liczba całkowita  i  jeśli  b  =  a  to  zwróć  x  ←  a  ;  s  ←  fa  (  za  ) / 2;  dla  i  od  1  do  n  −1  do  t  ←  ja  / (  n  +1);  x  ← (1−  t  ) *  za  +  t  *  b  ;  s  ←  s  +  fa  (  x  )  s  ←  fa  (  b  ) / 2  powrót  (  b  -  za  ) *  s  /  n

Całkowanie na dysku

$xc, yc}$ problem całkowania danej funkcji $dwoma$ argumentami na dysku z danym środkiem ( $displaystyle$ ) i danym promieniem ${\ Displaystyle R}$ . Ten problem można sprowadzić do dwóch zagnieżdżonych całek z pojedynczą zmienną poprzez zmianę zmiennych

{\ Displaystyle \ int \! \ int _ {D} g (x, y) \ \ operatorname {d} x \ \ operatorname {d} y = \ int _ {0} ^ {R} z \ lewo ( \int _{0}^{2\pi }g({\mathit {xc}}+z\cos t,{\mathit {yc}}+z\sin t)\,\mathrm {d} t\right )\,\mathrm {d} z}

Poniższy kod implementuje formułę prawostronną :

    
             procedura  DiskIntg  (  g  ,  xc  ,  yc  ,  R  ,  n  )  procedura  gring  (  z  ):  procedura  gpolar  (  t  ):  float  x  ,  y  x  ←  xc  +  z  *  cos  (  t  )  y  ←  yc  +  z  *  sin  (      t  )  return  g  (  x  ,  y  )  liczba całkowita  m  ←  zaokrąglenie  (  n  *  z  /  R  )  return  z  *  Intg  (  gpolar  , 0, 2*π,  m  )  return  Intg  (  gring  , 0,  R  ,  n  )

Ten kod wykorzystuje procedurę integracji Intg na dwóch poziomach. Poziom $ostatnia$ $($ ) Intg $obliczenia$ całki dla . The inner level (next-to-last line) defines $gring(z)$ as being the sol ${\ Displaystyle g (x, y)}$ $}$ okręgu o środku i promieniu ( $\ Displaystyle (xc, yc)$ .

Historia

Parametry proceduralne zostały wynalezione przed erą komputerów elektronicznych przez matematyka Alonzo Churcha jako część jego modelu obliczeniowego rachunku lambda .

Parametry proceduralne jako cecha języka programowania zostały wprowadzone przez ALGOL 60 . W rzeczywistości ALGOL 60 miał potężny mechanizm przekazywania parametrów „ wywołania według nazwy ”, który mógł uprościć niektóre zastosowania parametrów proceduralnych; zobacz Urządzenie Jensena .

Parametry proceduralne były istotną cechą języka programowania LISP , który wprowadził również koncepcję domknięcia funkcji lub funarg . Język programowania C umożliwia przekazywanie wskaźników funkcji jako parametrów, które osiągają ten sam cel i są często używane jako wywołania zwrotne w programowaniu sterowanym zdarzeniami i jako procedury obsługi błędów. Jednak tylko kilka nowoczesnych kompilatorów C pozwala na zagnieżdżone definicje funkcji, więc inne zastosowania są stosunkowo rzadkie. Parametry proceduralne zostały podane również w Pascalu wraz z zagnieżdżonymi definicjami procedur; jednakże, ponieważ standardowy Pascal nie pozwalał na oddzielną kompilację, funkcja ta była również rzadko używana w tym języku.

Zobacz też