Dlaczego NASA banuje rekurencje?

0

Jest coś takiego jak standardy kodowania w NASA

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

Przechwytywanie.PNG

3.PNG

Mógłby ktoś to wytłumaczyć jakoś prosto?:P

4

Przypuszczam że chodzi o bezpieczeństwo, rekurencja może łatwo wyjść poza kontrolę całkowicie zatrzymując system, wystarczy drobna nieuwaga programisty. Co więcej, ciężko czasami znaleźć przyczynę błędu. Zresztą napisałem chyba to, co w tekście załączonym przez ciebie.

0
EntityPamerano napisał(a):

Przypuszczam że chodzi o bezpieczeństwo, rekurencja może łatwo wyjść poza kontrolę całkowicie zatrzymując system, wystarczy drobna nieuwaga programisty. Co więcej, ciężko czasami znaleźć przyczynę błędu. Zresztą napisałem chyba to, co w tekście załączonym przez ciebie.

Mogę wnioskować, że powinienem unikać używania rekurencji?

5

Jeśli piszesz programy dla NASA to oczywiście powinieneś unikać. W przeciwnym wypadku użyj zdrowego rozsądku dla konkretnego przypadku.

2

Największym problemem rekurencji jest ograniczona wielkość stosu. Twój algorytm może działać do n = 1000, ale już dla n = 10000 dostaniesz StackOverflowError.

4

Mogę wnioskować, że powinienem unikać używania rekurencji?

Raczej ważne jest, żeby znać koszt/wady danych rozwiązań. Rekurencja wcale nie jest taka fajna, bo może spowodować przepełnienie stosu (tzw. "stack overflow").
Jak wywołujesz funkcje to zwykle jest ona odkładana na jakimś tam stosie wywołań, każda kolejne wywołanie powoduje, że stos rośnie (no chyba, że w języku jest "tail call optimization", to można jakoś tego uniknąć). Poza tym zaciemnia się przepływ sterowania w programie (tak jak napisali w tym fragmencie, nie panujesz nad tym).

Dlatego zwykłe pętle for czy while bywają bardziej wydajne i przewidywalne od rekurencji .

Natomiast wydaje mi się, że głównymi zaletami rekurencji jest cukier składniowy (jest bardziej przyjemna dla człowieka) i to, że można opakować coś tam w jakąś prostą funkcję, jest to często bardziej eleganckie od strony kodu bym powiedział (o ile jest to prosta rekurencja, bo czasem rekurencyjne funkcje się tak komplikują, że przestaje mieć to sens nawet od strony elegancji kodu).

0

Jeszcze jedna ważna rzecz, to są wytyczne JPL (Jet Propulsion Labolatory) więc dotyczą one tylko kodu używanego w sterownikach rakiet. Oczywiście kod, który nie obsługuje istotnych systemów (podtrzymanie życia, sterowniki rakiet, etc.) nie wymaga wszystkich tych zasad i rekurencja zakładam jest jak najbardziej dozwolona (np. w ekspresie do kawy ;)).

2

Rekurencja jest wygodna, ale jej skutki są trudne do perfekcyjnego oszacowania. Jak Windows zawiesi Ci się podczas przeszukiwania folderu to jakoś to ujdzie, ale w momencie gdy rakieta zawiesza się podczas przeszukiwania przestrzeni kosmicznej...

0
  1. Zwróć uwagę że powołują się na standard kodowania dla branży automotive czyli MISRA. Na platformach wbudowanych może być dostępny kompilator C bardzo różnej jakości a sam standard ma jeszcze inne obostrzenia (np. 1 punkt wyjścia z funkcji, brak modyfikacji zmiennych indeksowych w pętli, obowiązkowe otaczanie wyrażeń logicznych nawiasami i wiele innych).
  2. W samym standardzie C tak (hosted jak i freestanding) nie ma wymagania stosowania rekurencji ogonowej która oszczędza stos. To że "gcc ma i VS także" to tylko uprzejmość tych dostawców narzędzi. Tak więc bezpieczny rekurencyjny kod może być nierozerwalnie związany z dedykowanym kompilatorem co może uniemożliwić w przyszłości zmianę platformy sprzętowej na inną.
  3. Algorytm rekurencyjny może łatwo wymknąć się spod kontroli zapisując dane na stosie aż do jego przepełnienia a nie każda platforma sprzętowa lub sprzętowo-programowa, potrafi taki fakt wykryć i prawidłowo zareagować.
  4. Narzędzia analizy statycznej kodu nie zawsze radzą sobie poprawnie z kodem rekurencyjnym.

To jest to co mi przychodzi jako pierwsze na myśl "dlaczego nie" :-)

0
Mokrowski napisał(a):
  1. Zwróć uwagę że powołują się na standard kodowania dla branży automotive czyli MISRA. Na platformach wbudowanych może być dostępny kompilator C bardzo różnej jakości a sam standard ma jeszcze inne obostrzenia (np. 1 punkt wyjścia z funkcji, brak modyfikacji zmiennych indeksowych w pętli, obowiązkowe otaczanie wyrażeń logicznych nawiasami i wiele innych).

Te ograniczenia to akurat dobre praktyki, więc albo mówisz o jakichś dodatkowych - statycznych - weryfikacjach kodu, albo w niektórych kompilatorach te dobre praktyki ktoś zaimplementował w formie warningów / errorów (tak jak np. dla C++ zaimplementowali "-Weffc++").

  1. Algorytm rekurencyjny może łatwo wymknąć się spod kontroli zapisując dane na stosie aż do jego przepełnienia a nie każda platforma sprzętowa lub sprzętowo-programowa, potrafi taki fakt wykryć i prawidłowo zareagować.

A jak można prawidłowo zareagować na przepełnienie stosu?

1
vpiotr napisał(a):
Mokrowski napisał(a):

Te ograniczenia to akurat dobre praktyki, więc albo mówisz o jakichś dodatkowych - statycznych - weryfikacjach kodu, albo w niektórych kompilatorach te dobre praktyki ktoś zaimplementował w formie warningów / errorów (tak jak np. dla C++ zaimplementowali "-Weffc++").

Ba, dla clang++ interesujące jest -Weverything na tyle że trzeba z niego wyłączać jawnie np. kompatybilność wsteczną z C++98 :-)

MISRA to dodatkowe wymagania stawiane przy tworzeniu kodu dla branży automotive które często są "przejmowane do innych branż". Część narzędzi na platformy wbudowane ma je zaimplementowane (np. toolchain Keil) i łatwo włączyć raportowanie łamania poszczególnych reguł. Są także dostępne w narzędziach nie związanych z samym kompilatorem C lub C++ (MISRA ma wytyczne dla C i C++). VS jak i gcc do nich nie należy. Te kompilatory nie posiadają odpowiednich ostrzeżeń łamania reguł MISRA :-(

Tu trochę więcej o narzędziach: https://en.wikipedia.org/wiki/MISRA_C
Tu sam standard: https://www.misra.org.uk/Buyonline/tabid/58/Default.aspx
Forum MISRA: https://www.misra.org.uk/forum/index.php

Sama "samodzielna" MISRA zabrania rekurencji.

Sam standard bywa zresztą także przeceniany przez zarządzających którzy traktują go jako jeszcze jedną "złotą kulę" :-/

  1. Algorytm rekurencyjny może łatwo wymknąć się spod kontroli zapisując dane na stosie aż do jego przepełnienia a nie każda platforma sprzętowa lub sprzętowo-programowa, potrafi taki fakt wykryć i prawidłowo zareagować.

A jak można prawidłowo zareagować na przepełnienie stosu?

A to już zależy od samego systemu (sprzęt-oprogramowanie) To może być restart w innym trybie działania (oprogramowanie może działać w trybie nadzorowanym co wspiera teraz w zasadzie każdy większy MCU ARM), wyłączenie systemu i fizyczne zablokowanie w bezpiecznym stanie (np. zaciśniecie uchwytów wind bazujące układzie siłowników lub sprężyn), udostępnienie obejścia uszkodzonego systemu w trybie sterowania ręcznego. To czy taki wypadek jest przewidywany, zależy od konkretnego przypadku systemu, branży lub reperkusji jego złego działania. Dość że z wielką pieczołowitością usuwa się rekurencję z potencjalnych czynników prowadzących do awarii i wskazuje praktyki które nie są bezpieczne.

Np. jedną z reguł kodowania i budowy architektury oprogramowania dla łazików marsjańskich (C++) było alokowanie niezbędnej pamięci przed wejściem do main() głównego programu a ew. alokacje w trakcie wykonywane były wyłącznie z już dostępnej puli a nie "gołym new".

1 użytkowników online, w tym zalogowanych: 0, gości: 1