Język schematu blokowego

Język schematu blokowego (FCL)

Paradygmat	pilny
Zaprojektowany przez	Carsten K. Gomard, Neil D. Jones, John Hatcliff
Po raz pierwszy pojawiły się	1989, 1993, 1998

Język schematów blokowych (FCL) to prosty imperatywny język programowania przeznaczony do wyjaśniania podstawowych pojęć analizy i specjalizacji programów , w szczególności oceny częściowej . Język został po raz pierwszy zaprezentowany w 1989 roku przez Carstena K. Gomarda i Neila D. Jonesa. Później pojawił się ponownie w ich książce z Peterem Sestoftem w 1993 r. Oraz w notatkach z wykładów Johna Hatcliffa w 1998 r. Poniżej opisano FCL tak, jak pojawił się w notatkach z wykładów Johna Hatcliffa.

FCL jest imperatywnym językiem programowania zbliżonym do sposobu, w jaki komputer Von Neumanna wykonuje program. Program jest wykonywany sekwencyjnie, wykonując sekwencję poleceń, przy jednoczesnym zachowaniu stanu niejawnego, tj. pamięci globalnej. FCL nie ma koncepcji procedur, ale zapewnia skoki warunkowe i bezwarunkowe. FCL zasługuje na swoją nazwę, ponieważ abstrakcyjny wykres wywołań programu FCL jest prostym schematem blokowym.

Program FCL przyjmuje jako dane wejściowe skończoną serię nazwanych wartości jako parametry i jako wynik generuje wartość.

Składnia

Określamy składnię FCL za pomocą formularza Backusa-Naura .

Program FCL to lista formalnych deklaracji parametrów, etykieta wpisu i sekwencja podstawowych bloków :

  <  p  >  ::=  "("  <  x  >  * ")" "("  <  l  >  ")"  <  b  >  + 

Początkowo język dopuszcza tylko nieujemne zmienne całkowite.

Podstawowy blok składa się z etykiety, listy przypisań i skoku.

   <  b  >  ::=  <  l  >  ":"  <  a  >  *  <  j  > 

Przypisanie przypisuje zmienną do wyrażenia. Wyrażenie może być stałą, zmienną lub zastosowaniem wbudowanego operatora n-argumentowego:

 <  a  >  :=  <  x  >  ":="  <  e  >  <  e  >  :=  <  c  >  |  <  x  >  |  <  o  >  "("  <  e  >  * ")" 

Uwaga: nazwy zmiennych występujące w całym programie nie muszą być deklarowane na początku programu. Zmienne zadeklarowane na początku programu wyznaczają argumenty dla programu.

Ponieważ wartości mogą być tylko nieujemnymi liczbami całkowitymi, tak samo jak stałe. Lista operacji w ogóle nie ma znaczenia, o ile nie mają one skutków ubocznych , co obejmuje wyjątki, np. dzielenie przez 0:

   <  c  >  ::=  "0" | "1" |  "2" |  ...   <  o  >  ::=  "+" | "-" |  "*" |  "=" |  "   <  " | "   >  " | ...  

Gdzie = , < , ... mają semantykę jak w C. Semantyka - jest taka, że ​​jeśli xy<0, to xy=0.

Przykład

Piszemy program, który oblicza n- ^tą liczbę Fibonacciego dla n>2:

(n) (init) init: x1 = 1 x2 = 1 fib: x1 = x1 + x2 t = x1 x1 = x2 x2 = t n = -(n 1) if >(n 2) to fib else wyjdź wyjdź: zwróć x2

Gdzie niezmiennikiem pętli fib jest to, że x1 to (i+2-1) ^th , a x2 to (i+2) ^th liczba Fibonacciego, gdzie i to liczba przeskoków fib .

Poprawność metody możemy sprawdzić dla n=4 prezentując ślad wykonania programu:

${\ Displaystyle {\ rozpocząć {wyrównane} i \ lewo ({\ mathtt {init}}, \ \ lewo [n \ mapsto 4, \ x1 \ mapsto 0, \ x2 \ mapsto 0, \ t \ mapsto 0 \right]\right)\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 4,\ x1\mapsto 1,\ x2\mapsto 1,\ t\mapsto 0\right ]\right)\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 3,\ x1\mapsto 1,\ x2\mapsto 2,\ t\mapsto 0\right]\ w prawo)\\\strzałka w prawo &\left(\left\langle {\mathtt {halt}},\ 3\right\rangle ,\ \left[n\mapsto 2,\ x1\mapsto 2,\ x2\mapsto 3, \ t\mapsto 0\right]\right)\end{aligned}}}$

Gdzie ${\ Displaystyle \ lewo \ langle {\ mathtt {zatrzymanie}}, \ v \ prawo \ rangle}$ oznacza końcowy stan programu, z wartością zwracaną ${\ displaystyle v}$ .