Podnoszenie lambdy

Podnoszenie lambda to metaproces , który restrukturyzuje program komputerowy , tak aby funkcje były definiowane niezależnie od siebie w zasięgu globalnym . Pojedyncza „winda” przekształca funkcję lokalną w funkcję globalną. Jest to proces dwuetapowy, składający się z;

• Eliminacja wolnych zmiennych w funkcji poprzez dodanie parametrów.
• Przenoszenie funkcji z zakresu ograniczonego do zakresu szerszego lub globalnego.

Termin „podnoszenie lambda” został po raz pierwszy wprowadzony przez Thomasa Johnssona około 1982 roku i był historycznie uważany za mechanizm wdrażania funkcjonalnych języków programowania . Jest używany w połączeniu z innymi technikami w niektórych nowoczesnych kompilatorach .

Podnoszenie lambda to nie to samo, co konwersja domknięcia. Wymaga dostosowania wszystkich witryn wywołań (dodania dodatkowych argumentów do wywołań) i nie wprowadza domknięcia dla podniesionego wyrażenia lambda. W przeciwieństwie do tego konwersja domknięcia nie wymaga dostosowania miejsc wywołań, ale wprowadza domknięcie wyrażenia lambda odwzorowującego wolne zmienne na wartości.

Technika ta może być stosowana na poszczególnych funkcjach, w refaktoryzacji kodu , aby funkcja była użyteczna poza zakresem, w którym została napisana. Wyciągi lambda mogą być również powtarzane w celu przekształcenia programu. Powtarzane windy mogą być użyte do przekształcenia programu napisanego w rachunku lambda w zestaw funkcji rekurencyjnych , bez lambd. Pokazuje to równoważność programów napisanych w rachunku lambda i programów napisanych jako funkcje. Jednak nie dowodzi to przydatności rachunku lambda do dedukcji, jak redukcja eta używany w podnoszeniu lambda jest krokiem, który wprowadza problemy liczności do rachunku lambda, ponieważ usuwa wartość ze zmiennej, bez uprzedniego sprawdzenia, czy istnieje tylko jedna wartość, która spełnia warunki zmiennej (patrz paradoks Curry'ego ).

Podnoszenie lambda jest kosztowne w czasie przetwarzania dla kompilatora. Wydajna implementacja podnoszenia lambda $zależy$ kompilator

W nietypowanym rachunku lambda , gdzie podstawowymi typami są funkcje, podniesienie może zmienić wynik redukcji beta wyrażenia lambda. Wynikowe funkcje będą miały to samo znaczenie w sensie matematycznym, ale nie są uważane za tę samą funkcję w nietypowanym rachunku lambda. Zobacz także równość intencjonalna i ekstensjonalna .

Operacją odwrotną do podnoszenia lambda jest opuszczanie lambda .

Upuszczanie lambda może przyspieszyć kompilację programów dla kompilatora, a także może zwiększyć wydajność wynikowego programu poprzez zmniejszenie liczby parametrów i zmniejszenie rozmiaru ramek stosu. Jednak utrudnia to ponowne użycie funkcji. Upuszczona funkcja jest powiązana ze swoim kontekstem i może być użyta w innym kontekście tylko wtedy, gdy zostanie najpierw podniesiona.

Algorytm

Poniższy algorytm jest jednym ze sposobów podnoszenia lambda dowolnego programu w języku, który nie obsługuje domknięć jako obiektów pierwszej klasy :

1. Zmień nazwy funkcji, aby każda funkcja miała unikalną nazwę.
2. Zastąp każdą wolną zmienną dodatkowym argumentem funkcji otaczającej i przekaż ten argument przy każdym użyciu funkcji.
3. Zastąp każdą definicję funkcji lokalnej, która nie ma wolnych zmiennych, identyczną funkcją globalną.
4. Powtarzaj kroki 2 i 3, aż wszystkie wolne zmienne i funkcje lokalne zostaną wyeliminowane.

Jeśli język ma domknięcia jako obiekty pierwszej klasy, które mogą być przekazywane jako argumenty lub zwracane z innych funkcji, domknięcie będzie musiało być reprezentowane przez strukturę danych, która przechwytuje powiązania wolnych zmiennych.

Przykład

Poniższy program OCaml oblicza sumę liczb całkowitych od 1 do 100:

    
      
    
  
       
         
         
  niech  rec  suma  n  =  jeśli  n  =  1  to  1  inaczej  niech  f  x  =  n  +  x  in  f  (  suma  (  n  -  1  ))  w  sumie  100 

( Let rec deklaruje sum jako funkcję, która może wywoływać samą siebie.) Funkcja f, która dodaje argument sumy do sumy liczb mniejszych od argumentu, jest funkcją lokalną. W definicji f n jest zmienną wolną. Zacznij od konwersji wolnej zmiennej na parametr:

    
      
    
  
        
         
          
  niech  rec  suma  n  =  jeśli  n  =  1  to  1  inaczej  niech  f  w  x  =  w  +  x  in  f  n  (  suma  (  n  -  1  ))  w  sumie  100 

Następnie podnieś f do funkcji globalnej:

     
    
   
      
    
  
          
 niech  rec  f  w  x  =  w  +  x  i  suma  n  =  jeśli  n  =  1  to  1  inaczej  f  n  (  suma  (  n  -  1  )  )  suma  100  

Poniżej znajduje się ten sam przykład, tym razem napisany w JavaScript :

  
      
           
    

       
         
    
           




  // Wersja początkowa  function  sum  (  n  )  {  function  f  (  x  )  {  return  n  +  x  ;  }  jeśli  (  n  ==  1  )  zwróć  1  ;  w przeciwnym razie  zwróć  f  (  suma  (  n  -  1  ));  }  // Po przekonwertowaniu zmiennej wolnej n na parametr formalny w  funkcji  sum  (  n  
       
           
    

       
         
    
            




    )  {  funkcja  fa  (  w  ,  x  )  {  powrót  w  +  x  ;  }  jeśli  (  n  ==  1  )  zwróć  1  ;  w przeciwnym razie  zwróć  f  (  n  ,  suma  (  n  -  1  ));  }  // Po podniesieniu funkcji f do globalnego zasięgu  function  f  (  w  ,  x  )  { 
       


  
       
         
    
            
 powrót  w  +  x  ;  }  funkcja  suma  (  n  )  {  jeśli  (  n  ==  1  )  powrót  1  ;  w przeciwnym razie  zwróć  f  (  n  ,  suma  (  n  -  1  ));  } 

Podnoszenie lambdy a domknięcia

zamykanie lambda to metody wdrażania programów o strukturze blokowej . Implementuje strukturę blokową, eliminując ją. Wszystkie funkcje są podniesione do poziomu globalnego. Konwersja zamknięcia zapewnia „zamknięcie”, które łączy bieżącą ramkę z innymi ramkami. Konwersja zamknięcia zajmuje mniej czasu kompilacji.

Funkcje rekurencyjne i programy o strukturze blokowej, z podnoszeniem lub bez, mogą być implementowane przy użyciu implementacji opartej na stosie , która jest prosta i wydajna. Jednak implementacja oparta na ramkach stosu musi być ścisła (chętna) . Implementacja oparta na ramkach stosu wymaga, aby czas życia funkcji był ostatni na wejściu, pierwszy na wyjściu (LIFO). Oznacza to, że najnowsza funkcja, która rozpoczęła obliczenia, musi być pierwszą do końca.

Niektóre języki funkcjonalne (takie jak Haskell ) są implementowane przy użyciu leniwej oceny , która opóźnia obliczenia do momentu, gdy wartość jest potrzebna. Strategia leniwej implementacji daje programiście elastyczność. Ocena z opóźnieniem wymaga opóźnienia wywołania funkcji do momentu żądania wartości obliczonej przez funkcję. Jedną z implementacji jest zapisanie odniesienia do „ramki” danych opisujących obliczenie zamiast wartości. Później, gdy wartość jest wymagana, ramka jest używana do obliczenia wartości, dokładnie na czas, kiedy jest potrzebna. Następnie obliczona wartość zastępuje odniesienie.

„Ramka” jest podobna do ramki stosu , z tą różnicą, że nie jest przechowywana na stosie. Leniwa ocena wymaga zapisania w ramce wszystkich danych wymaganych do obliczeń. Jeśli funkcja jest „podnoszona”, wówczas ramka wymaga jedynie zapisania wskaźnika funkcji i parametrów funkcji. Niektóre współczesne języki używają wyrzucania elementów bezużytecznych zamiast alokacji opartej na stosie do zarządzania życiem zmiennych. W zarządzanym, usuwanym bezużytecznie środowisku, zamknięcie rejestruje odniesienia do ramek, z których można uzyskać wartości. Natomiast podniesiona funkcja ma parametry dla każdej wartości potrzebnej do obliczenia.

Niech wyrażenia i rachunek lambda

Wyrażenie Let jest przydatne do opisywania podnoszenia i upuszczania oraz do opisywania relacji między równaniami rekurencyjnymi a wyrażeniami lambda. Większość języków funkcjonalnych ma wyrażenia let. Również języki programowania o strukturze blokowej, takie jak ALGOL i Pascal , są podobne, ponieważ również pozwalają na lokalną definicję funkcji do użycia w ograniczonym zakresie .

wyrażenie let jest w pełni wzajemnie rekurencyjną wersją let rec zaimplementowaną w wielu językach funkcjonalnych.

Niech wyrażenia są powiązane z rachunkiem Lambda . Rachunek lambda ma prostą składnię i semantykę i jest dobry do opisywania podnoszenia lambda. Wygodnie jest opisać podnoszenie lambda jako translację z lambda na let , a opuszczanie lambda jako odwrotność. Dzieje się tak, ponieważ let pozwalają na wzajemną rekurencję, która jest w pewnym sensie bardziej zniesiona niż jest obsługiwana w rachunku lambda. Rachunek lambda nie obsługuje rekurencji wzajemnej i tylko jedna funkcja może być zdefiniowana w najbardziej zewnętrznym zasięgu globalnym.

Reguły konwersji , które opisują translację bez podnoszenia, podano w artykule Let expression .

Poniższe reguły opisują równoważność wyrażeń lambda i let,

Nazwa	Prawo
Równoważność redukcji eta	${\ Displaystyle f \ x = y \ równoważnik f = \ lambda xy}$
Równoważność Let-Lambda	${\ Displaystyle f \ notin FV (E) \ do ( \operatorname {let} f:f=E\operatorname {in} L\equiv (\lambda fL)\ E)\ {\text{(gdzie }}f{\text{ to nazwa zmiennej.)}}}$
Niech kombinacja	${\ Displaystyle x \ notin FV (E) \ do (\ nazwa operatora {niech} v, \ kropki, w, x: E \ ziemia F \ nazwa operatora {w} L \ odpowiednik \ nazwa operatora {niech} v, \ kropki, w :E\nazwa_operatora {w} \nazwa_operatora {let} x:F\nazwa_operatora {w} L)}$

Podane zostaną metafunkcje opisujące podnoszenie i opuszczanie lambda. Meta-funkcja to funkcja, która przyjmuje program jako parametr. Program jest danymi dla metaprogramu. Program i metaprogram znajdują się na różnych metapoziomach.

Następujące konwencje będą używane do odróżnienia programu od metaprogramu,

• Nawiasy kwadratowe [] będą używane do reprezentowania zastosowania funkcji w metaprogramie.
• Wielkie litery będą używane dla zmiennych w metaprogramie. Małe litery reprezentują zmienne w programie.
• ${\ displaystyle \ equiv}$ będzie używane dla równości w metaprogramie.
• $fikcyjną$ lub nieznaną wartość.

Dla uproszczenia zastosowana zostanie pierwsza reguła, zgodnie z którą zostaną zastosowane dopasowania. Reguły zakładają również, że wyrażenia lambda zostały wstępnie przetworzone, dzięki czemu każda abstrakcja lambda ma unikalną nazwę.

Operator podstawienia jest szeroko stosowany. Wyrażenie oznacza $G$ wystąpienia w L S . _ Zastosowana definicja została rozszerzona o podstawianie wyrażeń, z definicji podanej na stronie rachunku Lambda . Dopasowywanie wyrażeń powinno porównywać wyrażenia pod kątem równoważności alfa (zmiana nazw zmiennych).

Podnoszenie lambda w rachunku lambda

Każda winda lambda pobiera abstrakcję lambda, która jest podwyrażeniem wyrażenia lambda i zastępuje ją wywołaniem funkcji (aplikacją) do funkcji, którą tworzy. Wolne zmienne w wyrażeniu podrzędnym są parametrami wywołania funkcji.

Podnośniki lambda mogą być używane w poszczególnych funkcjach, w refaktoryzacji kodu , aby funkcja była użyteczna poza zakresem, w którym została napisana. Takie windy mogą być również powtarzane, dopóki wyrażenie nie ma abstrakcji lambda, w celu przekształcenia programu.

Winda lambdy

Winda otrzymuje podwyrażenie w wyrażeniu, które ma podnieść na górę tego wyrażenia. Wyrażenie może być częścią większego programu. Pozwala to kontrolować, gdzie podwyrażenie jest podnoszone. Operacja podnoszenia lambda używana do wykonywania podnoszenia w programie to:

${\ Displaystyle \ operatorname {lambda-lift-op} [S,L,P]=P[L:=\operatorname {lambda-winda} [S,L]]}$

Wyrażenie podrzędne może być abstrakcją lambda lub abstrakcją lambda zastosowaną do parametru.

Możliwe są dwa rodzaje windy.

• Anonimowa winda
• Nazwana winda

Anonimowa winda ma wyrażenie windy, które jest tylko abstrakcją lambda. Jest to traktowane jako definiowanie funkcji anonimowej. Dla funkcji należy utworzyć nazwę.

Nazwane wyrażenie podnoszenia ma abstrakcję lambda zastosowaną do wyrażenia. Ten wzrost jest traktowany jako nazwana definicja funkcji.

Anonimowa winda

Anonimowa winda pobiera abstrakcję lambda (zwaną S ). dla S ;

• Utwórz nazwę funkcji, która zastąpi S (zwanej V ). Upewnij się, że nazwa identyfikowana przez V nie została użyta.
• Dodaj parametry do V , dla wszystkich wolnych zmiennych w S , aby utworzyć wyrażenie G (zobacz make-call ).

Podniesienie lambda to zastąpienie abstrakcji lambda S w aplikacji funkcji wraz z dodaniem definicji funkcji.

${\ Displaystyle \ operatorname {lambda-lift} [S, L] \ równoważnik \ operatorname {let} V: \ operatorname {de-lambda} [G = S] \ operatorname {w} L [S: = G]}$

Nowe wyrażenie lambda ma S podstawione na G. Zauważ, że L [ S := G ] oznacza podstawienie S na G w L. Do definicji funkcji dodano definicję funkcji G = S.

W powyższej regule G jest aplikacją funkcji, która zastępuje wyrażenie S . jest określony przez,

${\ Displaystyle G = \ nazwa operatora {połącz} [V, \ nazwa operatora {FV} [S]]}$

gdzie V to nazwa funkcji. Musi to być nowa zmienna, czyli nazwa nie używana jeszcze w wyrażeniu lambda,

${\ Displaystyle V \ nie \ w \ nazwa operatora {vars} [\ nazwa operatora {niech} F \ nazwa operatora {w} L]}$

gdzie ${\ displaystyle \ operatorname {vars} [E]}$ jest metafunkcją, która zwraca zestaw zmiennych używanych w E .

Przykład anonimowej windy.

Na przykład ${\ Displaystyle {\ rozpocząć {wyrównane} F & = \ nazwa operatora {prawda} \\ L & = \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) \\ S & =\lambda xf\ (x\ x)\\G&=p\ f\end{wyrównane}}}$ ${\ Displaystyle \ nazwa operatora {de-lambda} [p \ f = \ lambda xf \ (x \ x)] \ równoważnik p \ f \ x = f \ (x \ x)}$ Zobacz de-lambda w Conversion from lambda to let expressions . Wynik to, ${\ Displaystyle \ operatorname {lambda-lift} [\ lambda xf \ (x \ x), \ operatorname {niech} \ operatorname {true} \ operatorname {in} \ lambda f. (\ lambda xf\ (x\ x))\ (\lambda xf\ (x\ x))]\equiv \operatorname {let} p\ f\ x=f\ (x\ x)\operatorname {in} \lambda f .(p\ f)\ (p\ f)}$

Konstruowanie połączenia

Wywołanie funkcji G jest konstruowane przez dodanie parametrów dla każdej zmiennej w zbiorze zmiennych wolnych (reprezentowanym przez V ) do funkcji H ,

• ${\ Displaystyle X \ w V \ do \nazwa_operatora {połącz-połącz} [H,V]\equiv \nazwa_operatora {połącz-połącz} [H,V\cap \neg \{X\}]\ X}$
• $\ Displaystyle \ nazwa operatora {nawiązać połączenie} [H, \ {\}] \ równoważnik H}$

Przykład konstrukcji wywołania.
${\ Displaystyle S = \ lambda xf \ (x \ x)}$ ${\ Displaystyle \ operatorname {FV} (S) = \ {f \}}$ ${\ Displaystyle G \ równoważnik \ nazwa operatora {połącz} [p,\nazwa_operatora {FV} [S]]\equiv \nazwa_operatora {połączenie} [p,\{f\}]\equiv \nazwa_operatora {połączenie} [p,\{\}]\ f\ odpowiednik p\ f}$

Nazwana winda

Nazwana winda jest podobna do windy anonimowej, z tą różnicą, że podano nazwę funkcji V.

${\ Displaystyle \ operatorname {lambda-lift} [(\ lambda VE) \ S, L] \ równoważnik \ operatorname {let} V: \ operatorname {de-lambda} [G =S]\nazwaoperatora {w} L[(\lambda VE)\ S:=E[V:=G]]}$

Jeśli chodzi o wzrost anonimowy, wyrażenie G jest konstruowane z V przez zastosowanie wolnych zmiennych S . jest określony przez,

${\ Displaystyle G = \ nazwa operatora {połącz} [V, \ nazwa operatora {FV} [S]]}$

Przykład dla nazwanej windy.

Na przykład, ${\ Displaystyle {\ rozpocząć {wyrównane} V & = x \\ E & = f \ (x \ x) \\ S & = (\ lambda xf \ (x \ x)) \\ L & = \ lambda f. (\ lambda xf \ (x\ x))\ (\lambda xf\ (x\ x))\\G&=x\ f\end{wyrównane}}} E [$ ${\ Displaystyle E [V: = G] = f \ (x \ x) [x: = x \ f] = f \ ((x \ f) \ (x\ f))}$ ${\ Displaystyle L [(\ lambda VE) \ F: = E [V: = G]] = L [(\ lambda xf \ (x \ x)) \ (\ lambda xf\ (x\ x)):=f\ ((x\ f)\ (x\ f))]=\lambda ff\ ((x\ f)\ (x\ f))}$ ${\ Displaystyle \ nazwa operatora {de-lambda} [x \ f = \ lambda yf \ (y \ y)] \ równoważnik x \ f \ y = f \ (y \ y)}$ Zobacz de-lambda w Conversion from lambda to let expressions . Wynik to, daje, ${\ Displaystyle \ operatorname {winda lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)), \ lambda f. (\ lambda xf\ (x\ x))\ (\lambda xf\ (x\ x))]\equiv \operatorname {let} x\ f\ y=f\ (y\ y)\operatorname {in} \lambda f. (x\ f)\ (x\ f)}$

Transformacja wzniosu lambda

Transformacja wyciągu lambda pobiera wyrażenie lambda i podnosi wszystkie abstrakcje lambda na początek wyrażenia. Abstrakcje są następnie tłumaczone na funkcje rekurencyjne , co eliminuje abstrakcje lambda. Rezultatem jest funkcjonalny program w postaci

• ${\ Displaystyle \ nazwa operatora {niech} M \ nazwa operatora {w} N}$

gdzie M to seria definicji funkcji, a N to wyrażenie reprezentujące zwróconą wartość.

Na przykład,

${\ Displaystyle \ operatorname {lambda-lift-tran} [\ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf\ (x\ x))]\equiv \nazwa_operatora {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\nazwa_operatora {w} q\ p}$

Metafunkcja de-let może być następnie użyta do przekształcenia wyniku z powrotem w rachunek lambda.

${\ Displaystyle \ nazwa operatora {de-let} [\ nazwa operatora {lambda-lift-tran} [\ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]] \equiv (\lambda p.(\lambda qq\ p)\ \lambda p.\lambda f.(p\ f)\ (p\ f))\ \lambda f.\lambda xf\ (x\ x)}$

Przetwarzanie przekształcania wyrażenia lambda to seria wyciągów. Każda winda posiada

• Podwyrażenie wybrane dla niego przez funkcję lift-choice . Podwyrażenie powinno być tak dobrane, aby można je było przekształcić w równanie bez lambd.
• Winda jest wykonywana przez wywołanie metafunkcji lambda-lift , opisanej w następnej sekcji,

${\ Displaystyle {\ rozpocząć {przypadki} \ operatorname {lambda-lift-tran} [L] = \ operatorname {drop-params-tran} [\ operatorname {merge-let} [\ operatorname {lambda-apply} [L] ]]\\\operatorname {lambda-apply} [L]=\operatorname {lambda-process} [\operatorname {lift-choice} [L],L]\\\operatorname {lambda-process} [\operatorname {none } ,L]=L\\\operatorname {lambda-process} [S,L]=\operatorname {lambda-apply} [\operatorname {lambda-lift} [S,L]]\end{przypadki}}}$

Po zastosowaniu wyciągów, płaty są łączone w jeden.

${\ Displaystyle {\ rozpocząć {przypadki} \ nazwa operatora {merge-let} [\ nazwa operatora {niech} V: E \ nazwa operatora {w} \ nazwa operatora {niech} W:F\operatorname {in} G]=\operatorname {merge-let} [\operatorname {let} V,W:E\land F\operatorname {in} G]\\\operatorname {merge-let} [E ]=E\end{przypadki}}}$

Następnie stosowane jest usuwanie parametrów w celu usunięcia parametrów, które nie są konieczne w wyrażeniu „let”. Wyrażenie let umożliwia definicjom funkcji bezpośrednie odwoływanie się do siebie, podczas gdy abstrakcje lambda są ściśle hierarchiczne, a funkcja może nie odnosić się bezpośrednio do siebie.

Wybór wyrażenia do podnoszenia

Istnieją dwa różne sposoby wybierania wyrażenia do podnoszenia. Pierwsza traktuje wszystkie abstrakcje lambda jako definiujące funkcje anonimowe. Drugi traktuje abstrakcje lambda, które są stosowane do parametru, jako definiujące funkcję. Abstrakcje lambda zastosowane do parametru mają podwójną interpretację jako wyrażenie let definiujące funkcję lub definiujące funkcję anonimową. Obie interpretacje są prawidłowe.

Te dwa predykaty są potrzebne dla obu definicji.

lambda-free — wyrażenie nie zawierające abstrakcji lambda.

${\ Displaystyle {\ rozpocząć {przypadki} \ nazwa operatora {bez lambda} [\ lambda FX] = \ nazwa operatora {fałsz} \\\ nazwa operatora {bez lambda} [V] = \ nazwa operatora {true} \\\ nazwa operatora { lambda-free} [M\ N]=\operatorname {lambda-free} [M]\land \operatorname {lambda-free} [N]\end{cases}}}$

lambda-anon — funkcja anonimowa. Wyrażenie takie jak $lambda$ gdzie X jest wolny od

${\ Displaystyle {\ rozpocząć {przypadki} \ nazwa operatora {lambda-anon} [\ lambda FX] = \ nazwa operatora {lambda-free} [X] \ lor \ nazwa operatora {lambda-anon} [X] \\\ nazwa operatora {lambda -anon} [V]=\nazwa_operatora {false} \\\nazwa_operatora {lambda-anon} [M\ N]=\nazwa_operatora {false} \end{przypadki}}}$

Wybieranie anonimowych funkcji tylko do podnoszenia

Szukaj najgłębszej anonimowej abstrakcji, aby po zastosowaniu windy podniesiona funkcja stała się prostym równaniem. Ta definicja nie uznaje abstrakcji lambda z parametrem za definicję funkcji. Wszystkie abstrakcje lambda są uważane za definiujące funkcje anonimowe.

lift-choice — Pierwszy anonim znaleziony podczas przechodzenia przez wyrażenie lub żaden , jeśli nie ma funkcji.

1. ${\ Displaystyle \ nazwa operatora {lambda-anon} [X] \ do \ nazwa$
2. ${\ Displaystyle \ nazwa operatora {wybór windy} [\ lambda FX] = \ nazwa operatora {wybór windy} [X]$
3. ${\ Displaystyle \ nazwa operatora {wybór windy} [M] \ neq \ nazwa operatora {brak} \ do \ nazwa operatora {wybór windy} [M \ N] = \ nazwa operatora {wybór windy} [M]}$
4. ${\ Displaystyle \ nazwa operatora {wybór windy} [M \ N] = \$
5. $\ Displaystyle \ nazwa operatora {wybór windy} [V] = \ nazwa operatora {brak}}$

Na przykład,

Wybór lambdy na ${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda yf \ (y \ y)) }$ to ${\ Displaystyle \ lambda xf \ (x \ x)}$

Reguła	typ funkcji	wybór
2		${\ Displaystyle \ operatorname {wybór windy} [\ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda yf\ (y\ y))]}$
3		$operatorname {lift-choice} [(\ lambda xf \ (x\ x))\ (\lambda yf\ (y\ y))]}$
1	zaraz	${\ Displaystyle \ nazwa operatora {wybór windy} [\ lambda xf \ (x \ x)]}$
		${\ Displaystyle \ lambda xf \ (x \ x)}$

Wybór lambdy na ${\ Displaystyle \ lambda f (p \ f) \ (p \ f)}$ jest ${\ Displaystyle \ lambda f. (p \ f) \ (p \ f)}$

Reguła	typ funkcji	wybór
2	zaraz	${\ Displaystyle \ nazwa operatora {wybór windy} [\ lambda f. (p \ f) \ (p \ f)]}$
2		${\ Displaystyle \ lambda f. (p \ f) \ (p \ f)}$

Wybór funkcji nazwanych i anonimowych do podnoszenia

Wyszukaj najgłębszą nazwaną lub anonimową definicję funkcji, tak aby po zastosowaniu windy funkcja podniesiona stała się prostym równaniem. Ta definicja rozpoznaje abstrakcję lambda z rzeczywistym parametrem jako definiującą funkcję. Tylko abstrakcje lambda bez aplikacji są traktowane jako funkcje anonimowe.

lambda-named

Nazwana funkcja. Wyrażenie takie jak ${\ Displaystyle (\ lambda FM) \ N}$ gdzie M jest wolne od lambda, a N jest wolne od lambda lub funkcja anonimowa.

$\ Displaystyle {\ rozpocząć {tablica} {l} \ nazwa operatora {nazwa lambda} [(\ lambda FM) \ N] = \ nazwa operatora {wolna od lambda} [M] \ ziemia \operatorname {lambda-anon} [N]\\\operatorname {lambda-named} [\lambda FX]=\operatorname {false} \\\operatorname {lambda-named} [V]=\operatorname {false} \end {szyk}}}$

wybór windy

Pierwsza anonimowa lub nazwana funkcja znaleziona podczas przechodzenia przez wyrażenie lub brak , jeśli nie ma żadnej funkcji.

1. ${\ Displaystyle \ nazwa operatora {lambda-nazwa} [X] \ lor \ nazwa operatora {lambda-anon} [X] \ do \ nazwa operatora {wybór windy} [X] = X}$
2. ${\ Displaystyle \ nazwa operatora {wybór windy} [\ lambda FX] = \ nazwa operatora {wybór windy} [X]$
3. ${\ Displaystyle \ nazwa operatora {wybór windy} [M] \ neq \ nazwa operatora {brak} \ do \ nazwa operatora {wybór windy} [M \ N] = \ nazwa operatora {wybór windy} [M]}$
4. ${\ Displaystyle \ nazwa operatora {wybór windy} [M \ N] = \$
5. $\ Displaystyle \ nazwa operatora {wybór windy} [V] = \ nazwa operatora {brak}}$

Na przykład,

Wybór lambdy na ${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda yf \ (y \ y)) }$ jest ${\ Displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda yf \ (y \ y))}$

Reguła	typ funkcji	wybór
2		${\ Displaystyle \ operatorname {wybór windy} [\ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda yf\ (y\ y))]}$
1	o imieniu	$operatorname {lift-choice} [(\ lambda xf \ (x\ x))\ (\lambda yf\ (y\ y))]}$
		${\ Displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda yf \ (y \ y))}$

Wybór lambdy na ${\ Displaystyle \ lambda ff \ ((x \ f) \ (x \ f))}$ jest ${\ Displaystyle \ lambda ff \ ((x \ f) \ (x \ f)}}$

Reguła	typ funkcji	wybór
1	zaraz	${\ Displaystyle \ nazwa operatora {wybór windy} [\ lambda ff \ ((x \ f) \ (x \ f))]}$
		${\ Displaystyle \ lambda ff \ ((x \ f) \ (x \ f)}}$

Przykłady

Na przykład kombinator Y ,

${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) }$

podnosi się jako,

${\ Displaystyle \ operatorname {niech} x \ f \ y = f \ (y \ y)\land q\ x\ f=f\ ((x\ f)\ (x\ f))\operatorname {in} q\ x}$

i po opuszczeniu parametru ,

${\ Displaystyle \ operatorname {niech} x \ f \ y = f \ (y \ y) \land q\ f=f\ ((x\ f)\ (x\ f))\operatorname {in} q}$

Jako wyrażenie lambda (patrz Konwersja wyrażeń let na lambda ),

${\ Displaystyle (\ lambda x. (\ lambda qq) \ \ lambda ff \ (x \ f) \ (x \ f)} \ \ lambda f. \ lambda yf \ (y \ y)}$

Podnoszenie funkcji nazwanych i anonimowych

	Wyrażenie lambda	Funkcjonować	Z	Do	Zmienne
1	${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) }$	PRAWDA	${\ Displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}$	${\ displaystyle x \ f}$	${\ Displaystyle \ {x, f \}}$
2	${\ Displaystyle (\ lambda f. (\ lambda xf \ (x \ x)) (\ lambda xf \ ( x\ x))}}$ ${\ Displaystyle [(\ lambda xf \ (x \ x)) \ (\lambda xf\ (x\ x)):=f\ ((x\ f)\ (x\ f))]}$	${\ Displaystyle x \ f = \ lambda yf \ (y \ y)}$			${\ Displaystyle \ {x, f, p \}}$
3	${\ Displaystyle \ lambda ff \ ((x \ f) \ (x \ f)}}$	${\ Displaystyle x \ f \ y = f \ (y \ y)}$	${\ Displaystyle \ lambda ff \ ((x \ f) \ (x \ f)}}$	${\ displaystyle q \ x}$	${\ Displaystyle \ {x, f, p \}}$
4	${\ Displaystyle \ lambda ff \ ((x \ f) \ (x \ f)} [\ lambda ff \ ((x \ f) \ (x \ f)):=q\ x]}$	${\ Displaystyle x \ f \ y = f \ (y \ y) \ ziemia q \ x = \ lambda ff \ ((x \ f) \ (x \ f)) }$			${\ Displaystyle \ {x, f, p, q \}}$
5	${\ displaystyle q \ x}$	${\ Displaystyle x \ f \ y = f \ (y \ y) \ ziemia q \ x \ f = f \ ((x\ f)\ (x\ f))}$			${\ Displaystyle \ {x, f, p, q \}}$

W przypadku podnoszenia tylko funkcji anonimowych kombinatorem Y jest:

${\ Displaystyle \ operatorname {niech} p \ f \ x = f \ (x \ x) \ ląd q\ p\ f=(p\ f)\ (p\ f)\nazwa_operatora {w} q\ p}$

i po zrzuceniu parametru ,

${\ Displaystyle \ nazwa operatora {niech} p \ f \ x = f \ (x \ x) \ ziemia q \ f=(p\ f)\ (p\ f)\nazwa_operatora {w} q}$

Jako wyrażenie lambda,

${\ Displaystyle (\ lambda p. (\ lambda qq) \ \ lambda f. (p \ f) \ (p \ f)} \ \ lambda f. \ lambda xf \ (x \ x)}$

Podnoszenie tylko funkcji anonimowych

	Wyrażenie lambda	Funkcjonować	Z	Do	Zmienne
1	${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) }$	PRAWDA	${\ Displaystyle \ lambda xf \ (x \ x)}$	${\ displaystyle p \ f}$	${\ Displaystyle \ {x, f \}}$
2	${\ Displaystyle (\ lambda f. (\ lambda xf \ (x \ x)) (\ lambda xf \ (x \ x)}) [\ lambda xf \ (x \ x) ):=p\ f]}$	${\ Displaystyle p \ f = \ lambda xf \ (x \ x)}$			${\ Displaystyle \ {x, f, p \}}$
3	${\ Displaystyle \ lambda f. (p \ f) \ (p \ f)}$	${\ Displaystyle p \ f \ x = f \ (x \ x)}$	${\ Displaystyle \ lambda f. (p \ f) \ (p \ f)}$	${\ displaystyle q \ p}$	${\ Displaystyle \ {x, f, p \}}$
4	${\ Displaystyle \ lambda f. (p \ f) \ (p \ f) [\ lambda f. (p \ f) \ (p \ f): = q \ P]}$	${\ Displaystyle p \ f \ x = f \ (x \ x) \ ziemia q \ p = \ lambda f. (p \ f) \ (p \ f)}$			${\ Displaystyle \ {x, f, p, q \}}$
5	${\ displaystyle q \ p}$	${\ Displaystyle p \ f \ x = f \ (x \ x) \ ziemia q \ p \ f = (p \ f )\ (p\ f)}$			${\ Displaystyle \ {x, f, p, q \}}$

Pierwszym podwyrażeniem, które należy wybrać do podnoszenia, jest ${\ Displaystyle \ lambda xf \ (x \ x)}$ . To przekształca wyrażenie lambda na ${\ Displaystyle \ lambda f. (p \ f) \ (p \ f)}$ i tworzy równanie ${\ Displaystyle p \ f \ x = f (x\ x)}$ .

Drugim podwyrażeniem, które należy wybrać do podnoszenia, jest ${\ Displaystyle \ lambda f. (p \ f) \ (p \ f)}$ . To przekształca wyrażenie lambda w ${\ Displaystyle q \ p}$ i tworzy równanie ${\ Displaystyle q \ p \ f = (p \ f) \ (p \ f )}$ .

A rezultatem jest,

${\ Displaystyle \ operatorname {niech} p \ f \ x = f \ (x \ x) \ ląd q\ p\ f=(p\ f)\ (p\ f)\nazwa_operatora {w} q\ p\ }$

Co zaskakujące, ten wynik jest prostszy niż ten uzyskany z podnoszenia nazwanych funkcji.

Wykonanie

Zastosuj funkcję do K ,

${\ Displaystyle {\ rozpocząć {przypadki} \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) \ K & \ \ nazwa operatora {niech} \ p \ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ q\ p\ K\\(\lambda xK\ ( x\ x))\ (\lambda xK\ (x\ x))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f )\ (p\ f)\ \operatorname {in} \ p\ K\ (p\ K)\\K\ ((\lambda xK\ (x\ x))\ (\lambda xK\ (x\ x) ))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=p\ f\ (p\ f)\ \operatorname {in} \ K\ ( p\ K\ (p\ K))\\\koniec {przypadków}}}$

Więc,

${\ Displaystyle (\ lambda xK \ (x \ x)) \ (\ lambda xK \ (x \ x)) = K \ ((\ lambda xK \ (x \ x)) \ (\ lambda xK \ (x \ X))))\ }$

Lub

${\ Displaystyle p \ K \ (p \ K) = K \ (p \ K \ (p \ K)}}$

Kombinator Y wielokrotnie wywołuje swój parametr (funkcję) na sobie. Wartość jest zdefiniowana, jeśli funkcja ma punkt stały . Ale funkcja nigdy się nie zakończy.

Spadająca lambda w rachunku lambda

Upuszczanie lambdy polega na zmniejszaniu zakresu funkcji i wykorzystywaniu kontekstu ze zmniejszonego zakresu do zmniejszenia liczby parametrów funkcji. Zmniejszenie liczby parametrów ułatwia zrozumienie funkcji.

W części podnoszącej Lambda została opisana metafunkcja służąca najpierw do podnoszenia, a następnie przekształcania wynikowego wyrażenia lambda na równanie rekurencyjne. Metafunkcja Lambda Drop wykonuje działanie odwrotne, najpierw konwertując równania rekurencyjne na abstrakcje lambda, a następnie upuszczając wynikowe wyrażenie lambda do najmniejszego zakresu, który obejmuje wszystkie odniesienia do abstrakcji lambda.

Spuszczanie lambdy odbywa się w dwóch krokach,

• Tonący
• Spadek parametrów

Spadek lambdy

Kropla Lambda jest stosowana do wyrażenia, które jest częścią programu. Upuszczanie jest kontrolowane przez zestaw wyrażeń, z których upuszczanie zostanie wykluczone.

${\ Displaystyle \ nazwa operatora {lambda-drop-op} [L, P, X] = P [L: = \ nazwa operatora {drop-params-tran} [\ nazwa operatora {sink-test } [L, X]]]}$

Gdzie,

L jest abstrakcją lambda, którą należy usunąć.

P to program

X to zbiór wyrażeń, które mają być wykluczone z usuwania.

Transformacja kropli lambda

Transformacja kropli lambda zatapia wszystkie abstrakcje w wyrażeniu. Sinking jest wykluczony z wyrażeń w zbiorze wyrażeń,

${\ Displaystyle \ nazwa operatora {lambda-drop-tran} [L, X] = \ nazwa operatora {drop-params-tran} [\ nazwa operatora {sink-tran} [\ nazwa operatora {de-let} [L, X]]]}$

Gdzie,

L jest wyrażeniem do przekształcenia.

X to zestaw wyrażeń podrzędnych, które mają być wykluczone z upuszczania.

sink-tran pochłania każdą abstrakcję, zaczynając od najgłębszej,

${\ Displaystyle {\ rozpocząć {przypadki} \ operatorname {sink-tran} [(\ lambda NB) \ Y, X] = \ operatorname {sink-test} [(\ lambda N .\operatorname {sink-tran} [B])\ \operatorname {sink-tran} [Y],X]\\\operatorname {sink-tran} [\lambda NB,X]=\lambda N.\operatorname { sink-tran} [B,X]\\\operatorname {sink-tran} [M\ N,X]=\operatorname {sink-tran} [M,X]\ \operatorname {sink-tran} [M,X ]\\\operatorname {sink-tran} [V,X]=V\end{cases}}}$

Zatonięcie abstrakcji

Tonięcie to przesuwanie abstrakcji lambda tak daleko, jak to możliwe, tak aby nadal znajdowała się poza wszelkimi odniesieniami do zmiennej.

Aplikacja - 4 przypadki.

${\ Displaystyle {\ rozpocząć {przypadki} E \ nie \ w \ nazwa operatora {FV} [G] \ ląd E \ nie \ w \ nazwa operatora {FV} [H] \ do \ nazwa operatora {sink} [(\ lambda EG \ H)\ Y,X]=G\ H\\E\not \in \nazwa_operatora {FV} [G]\land E\in \nazwa_operatora {FV} [H]\to \nazwa_operatora {sink} [(\lambda EG\ H)\ Y,X]=\operatorname {sink-test} [G\ \operatorname {sink-test} [(\lambda EH)\ Y,X]]\\E\in \operatorname {FV} [ G]\land E\not \in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda EG\ H)\ Y,X]=(\operatorname {sink-test} [(\lambda EG)\ Y,X])\ H\\E\in \nazwa_operatora {FV} [G]\land E\in \nazwa_operatora {FV} [H]\to \nazwa_operatora {sink} [(\lambda EG\ H )\ Y,X]=(\lambda EG\ H)\ Y\end{przypadki}}}$

Abstrakcja . Użyj zmiany nazwy, aby upewnić się, że nazwy zmiennych są różne.

${\ Displaystyle V \ neq W \ do \ nazwa operatora {umywalka} [(\ lambda V. \ lambda MY) \ Y, X] =\lambda W.\nazwa_operatora {sink-test} [(\lambda VE)\ Y,X]}$

Zmienna - 2 przypadki.

${\ Displaystyle E \ neq V \ do \ nazwa operatora {umywalka} [(\ lambda EV) \ Y, X] = V}$

${\ Displaystyle E = V \ do \ nazwa operatora {umywalka} [(\ lambda EV) \ Y, X] = Y}$

Sink test wyklucza odrzucanie wyrażeń,

${\ Displaystyle L \ w X \ do \ nazwa operatora {test zlewu} [L, X] = L}$

${\ Displaystyle L \ nie \ w X \ do \ operatorname {sink-test} [L, X] = \ operatorname {sink} [L, X]}$

Przykład

Przykład zatonięcia

Na przykład, Reguła Wyrażenie anulować ${\ Displaystyle \ nazwa operatora {sink-tran} [\ nazwa operatora {de-let} [\ nazwa operatora {niech} p \ f \ x = f \ (x \ x) \ ziemia q \ p \ f = (p \ f) \ (p\ f)\nazwa_operatora {w} q\ p]]}$ zlew-trans ${\ Displaystyle \ operatorname {sink-tran} [(\ lambda p. (\ lambda qq \ p) \ (\ lambda p. \ lambda f. (p \ f) \ (p \ f)}) \ (\ lambda f.\lambda xf\ (x\ x))]}$ Aplikacja ${\ Displaystyle \ operatorname {sink} [(\ lambda p. \ operatorname {sink} [(\ lambda qq \ p) \ (\ lambda p. \ lambda f. (p \ f) \ (p \ f))] )\ (\ lambda f. \ lambda xf \ (x\ x))]}$ ${\ Displaystyle \ nazwa_operatora {sink} [(\lambda qq\ p)\ (\lambda p.\lambda f.(p\ f)\ (p\ f))]}$ ${\ Displaystyle E \ w \ nazwa operatora {FV} [G] \ ziemia E \ nie \ w \ nazwa operatora {FV } [H]\to \nazwa_operatora {sink} [(\lambda EG\ H)\ Y,X]}$ ${\ Displaystyle E = q, G = q, H = p, Y = (\ lambda p. \ lambda f. (p \ f) \ (p \ f )), X = \ {\}}$ ${\ Displaystyle (\ nazwa operatora {zlew} [(\ lambda EG) \ Y, X]) \ H}$ ${\ Displaystyle (\ operatorname {sink} [(\ lambda qq) \ (\ lambda p. \ lambda f. (p \ f)\ (p\ f)),X])\ p}$ Zmienny ${\ Displaystyle \ nazwa operatora {umywalka} [(\ p. lambda \ nazwa operatora {umywalka} [(\ lambda qq) \ (\ p. lambda \ lambda f. (p \ f) \ (p \ f))] \ p )\ (\ lambda f. \ lambda xf \ (x\ x))]}$ ${\ Displaystyle \ nazwa operatora {umywalka} [(\lambda qq)\ (\lambda p.\lambda f.(p\ f)\ (p\ f))]}$ ${\ Displaystyle E = V \ do \ nazwa operatora {umywalka} [(\ lambda EV) \ Y, X]}$ ${\ Displaystyle E = q, V = q, Y = (\ p. lambda \ lambda f. (p \ f) \ (p \ f)), X = \ {\}} Y {\ Displaystyle$ $}$ ${\ Displaystyle (\ lambda p. \ lambda f. (p \ f) \ (p \ f)}}$ Aplikacja ${\ Displaystyle \ nazwa operatora {umywalka} [(\ lambda p.(\lambda p.\lambda f.(p\ f)\ (p\ f))\ p)\ (\lambda f.\lambda xf\ (x\ x))]}$ ${\ Displaystyle E \ nie \ w \ nazwa operatora {FV} [G] \ ziemia E \ w \ nazwa operatora { FV} [H]\to \operatorname {sink} [(\lambda EG\ H)\ Y,X]}$ ${\ Displaystyle E = p, G = (\ lambda p. \ lambda f. (p \ f) \ (p\ f)),H=p,Y=(\lambda f.\lambda xf\ (x\ x))}$ ${\ Displaystyle \ nazwa operatora {umywalka} [G \ \ nazwa operatora {umywalka} [(\ lambda EH) \ Y, X]]}$ Zmienny ${\ Displaystyle \ operatorname {sink} [(\ lambda p. \ lambda f. (p \ f) \ (p \ f)} \ \ operatorname {sink-test} [(\ lambda pp) \ (\ lambda f. \ lambda xf \ (x \ x)), X]]}$ ${\ Displaystyle \ nazwa operatora { umywalka} [( \lambda pp)\ (\lambda f.\lambda xf\ (x\ x)),X]}$ ${\ Displaystyle E = V \ do \ nazwa operatora {umywalka} [(\ lambda EV) \ Y, X]}$ ${\ Displaystyle E = p, V = p, Y = (\ lambda f. \ lambda xf \ (x \ x)), X = \ {\}} Y {\$ $Y }$ ${\ Displaystyle (\ lambda f. \ lambda xf \ (x \ x))}$ Abstrakcja ${\ Displaystyle \ nazwa operatora {umywalka} [(\ lambda p. \ lambda f .(p\ f)\ (p\ f))\ (\lambda f.\lambda xf\ (x\ x))]}$ ${\ Displaystyle V \ neq W \ do \ nazwa operatora {umywalka} [(\ lambda V. \ lambda WE) \ Y, X]}$ ${\ Displaystyle V = p, W = f, E = (p \ f) \ (p \ f), Y = (\ lambda f. \ lambda xf \ (x \ x))}$ ${\ Displaystyle \ lambda W. \ nazwa operatora {zlew} [(\ lambda VE) \ Y, X]}$ Aplikacja ${\ Displaystyle \ lambda f. \ nazwa operatora {umywalka} [(\ lambda p. (p\ f)\ (p\ f))\ (\lambda f.\lambda xf\ (x\ x)),X]}$ ${\ Displaystyle \ operatorname {sink} [(\ lambda p. (p \ f) \ (p \ f)} \ (\lambda f.\lambda xf\ (x\ x)),X]}$ ${\ Displaystyle E \ w \ nazwa operatora {FV} [G] \ ziemia E \ w \ nazwa operatora {FV} [H] \ do \ nazwa operatora {sink} [(\ lambda EG \ H) \ Y,X]}$ ${\ Displaystyle E = p, G = (p \ f), H = (p \ f), Y = (\ lambda f. \ lambda xf \ (x \ x))}$ ${ \ Displaystyle (\ lambda EG \ H) \ Y}$ ${\ Displaystyle (\ lambda p. (p \ f )\ (p\ f))\ (\lambda f.\lambda xf\ (x\ x))}$ ${\ Displaystyle \ lambda f. (\ lambda p. (p \ f) \ (p \ f)) \ (\lambda f.\lambda xf\ (x\ x))}$

Spadek parametrów

Upuszczanie parametrów optymalizuje funkcję pod kątem jej pozycji w funkcji. Podnoszenie lambda dodało parametry, które były niezbędne do wyjęcia funkcji z kontekstu. Podczas usuwania proces ten jest odwracany, a dodatkowe parametry zawierające zmienne, które są wolne, mogą zostać usunięte.

Upuszczenie parametru polega na usunięciu niepotrzebnego parametru z funkcji, gdzie rzeczywisty parametr przekazywany jest zawsze tym samym wyrażeniem. Wolne zmienne wyrażenia muszą być również wolne tam, gdzie zdefiniowana jest funkcja. W tym przypadku usuwany parametr jest zastępowany wyrażeniem w treści definicji funkcji. To sprawia, że ​​parametr jest zbędny.

Weźmy na przykład pod uwagę,

${\ Displaystyle \ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ p \ n) \ (g \ q \ p \ n)}} \ \ lambda x.\lambda o.\lambda yo\ x\ y}$

W tym przykładzie aktualnym parametrem formalnego parametru o jest zawsze p . Ponieważ p jest zmienną wolną w całym wyrażeniu, parametr może zostać usunięty. Właściwym parametrem formalnego parametru y jest zawsze n . Jednak n jest związane w abstrakcji lambda. Dlatego ten parametr nie może zostać usunięty.

Rezultatem upuszczenia parametru jest,

${\ Displaystyle \ nazwa operatora {drop-params-tran} [\ lambda m, p, q. (\ lambda g. \ lambda nn \ (g \ m \ p \ n) \ (g \ q \ p \ n))\ \lambda x.\lambda o.\lambda yo\ x\ y}$

${\ Displaystyle \ równoważnik \ lambda m, p, q. (\ lambda g. \ lambda nn \ (g \ m \ n) \ (g \ q \ n)) \ \ lambda x. \ lambda yp \ x \ y }$

Dla głównego przykładu

${\ Displaystyle \ nazwa operatora {drop-params-tran} [\ lambda f. (\ lambda p. (p \ f) \ (p \ f)} \ (\ lambda f. \ lambda xf \ (x \ x)) ]}$

${\ Displaystyle \ równoważnik \ lambda f. (\ lambda pp \ p) \ (\ lambda xf \ (x \ x))}$

Definicja drop-params-tran to:

${\ Displaystyle \ operatorname {drop-params-tran} [L] \ równoważnik (\ operatorname {drop-params} [L, D, FV [L], []])}$

Gdzie,

${\ Displaystyle \ operatorname {build-param-list} [L, D, V, \ _]}$

Zbuduj listy parametrów

Dla każdej abstrakcji, która definiuje funkcję, zbuduj informacje wymagane do podjęcia decyzji o porzuceniu nazw. Ta informacja opisuje każdy parametr; nazwa parametru, wyrażenie określające rzeczywistą wartość oraz wskazanie, że wszystkie wyrażenia mają tę samą wartość.

Na przykład w

${\ Displaystyle \ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ p \ n) \ (g \ q \ p \ n)}} \ \ lambda x.\lambda o.\lambda yo\ x\ y}$

parametry funkcji g to,

Parametr formalny	Wszystkie te same wartości	Rzeczywiste wyrażenie parametru
X	FAŁSZ	_
o	PRAWDA	P
y	PRAWDA	N

Każda abstrakcja otrzymuje unikalną nazwę, a lista parametrów jest powiązana z nazwą abstrakcji. Na przykład g istnieje lista parametrów.

${\ Displaystyle D [g] = [[x, \ nazwa operatora {fałsz}, \_ ],[o,\_,p],[y,\_,n]]}$

build-param-lists buduje wszystkie listy dla wyrażenia, przechodząc przez wyrażenie. Ma cztery parametry;

• Analizowane wyrażenie lambda.
• Lista parametrów tabeli dla nazw.
• Tabela wartości parametrów.
• Zwrócona lista parametrów, która jest używana wewnętrznie przez program

Abstrakcja $- Wyrażenie lambda$ postaci nazw parametrów funkcji

${\ Displaystyle {\ rozpocząć {przypadki} \ operatorname {build-param-lists} [(\ lambda NS) \ L, D, V, R] \ equiv \ operatorname {build-param-lists} [S, D, V ,R]\land \operatorname {build-list} [L,D,V,D[N]]\\\operatorname {build-param-lists} [\lambda NS,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\end{cases}}}$

Znajdź nazwę i rozpocznij tworzenie listy parametrów dla nazwy, wypełniając formalne nazwy parametrów. Odbierz również rzeczywistą listę parametrów z treści wyrażenia i zwróć ją jako rzeczywistą listę parametrów z tego wyrażenia

${\ Displaystyle {\ rozpocząć {przypadki} \ nazwa operatora {lista kompilacji} [\ lambda PB, D, V, [X, \ _, \ _]:: L] \ odpowiednik \ nazwa operatora {lista kompilacji} [B, D,V,L]\\\operatorname {build-list} [B,D,V,[]]\equiv \operatorname {build-param-lists} [B,D,V,\_]\end{cases }}}$

Zmienna — wywołanie funkcji.

${\ Displaystyle \ operatorname {build-param-lists} [N, D, V, D [N]]}$

W przypadku nazwy funkcji lub parametru zacznij zapełniać rzeczywistą listę parametrów, wyświetlając listę parametrów dla tej nazwy.

Aplikacja — aplikacja (wywołanie funkcji) jest przetwarzana w celu wyodrębnienia rzeczywistych szczegółów parametrów.

${\ Displaystyle \ nazwa operatora {listy parametrów kompilacji} [E \ P, D, V,R]\equiv \operatorname {build-param-lists} [E,D,V,T]\land \operatorname {build-param-lists} [P,D,V,K]}$

${\ Displaystyle \ ziemia T = [F, S, A]:: R \ teren (S\implikuje (\operatorname {equate} [A,P]\kraj V[F]=A))\kraj D[F]=K}$

Pobierz listy parametrów dla wyrażenia i parametru. Pobierz rekord parametru z listy parametrów z wyrażenia i sprawdź, czy bieżąca wartość parametru jest zgodna z tym parametrem. Zapisz wartość nazwy parametru do późniejszego wykorzystania podczas sprawdzania.

${\ Displaystyle {\ rozpocząć {przypadki} \ nazwa operatora {zrównać} [A, N] \ równoważnik A = N \ lor (\ nazwa operatora {def} [V [N]] \ ziemia A = V [N]) i {\ text{if }}N{\text{ jest zmienną.}}\\\operatorname {equate} [A,E]\equiv A=E&{\text{inaczej.}}\end{przypadki}}}$

Powyższa logika jest dość subtelna w sposobie, w jaki działa. Ten sam wskaźnik wartości nigdy nie jest ustawiony na wartość true. Jest ustawiana na false tylko wtedy, gdy nie można dopasować wszystkich wartości. Wartość jest pobierana przy użyciu S w celu zbudowania zestawu wartości logicznych dozwolonych dla S . Jeśli true jest członkiem, wszystkie wartości tego parametru są równe i parametr może zostać usunięty.

${\ Displaystyle \ nazwa operatora {zapytaj} [S] \ odpowiednik S \ w \ {X: X = S \}}$

Podobnie, def używa teorii mnogości do sprawdzenia, czy zmiennej nadano wartość;

${\ Displaystyle \ nazwa operatora {def} [F] \ równoważnik |\ {X: X = F \} |}$

Let - Let wyrażenie.

${\ Displaystyle \ operatorname {build-param-list} [\ operatorname { let} V:E\operatorname {in} L,D,V,\_]\equiv \operatorname {build-param-list} [E,D,V,\_]\land \operatorname {build-param-list } [L,D,V,\_]}$

I - Do użytku w „niech”.

$operatorname {build-param-lists} [E \ ziemia F, D,V,\_]\equiv \operatorname {build-param-lists} [E,D,V,\_]\land \operatorname {build-param-lists} [F,D,V,\_]}$

Przykłady

Na przykład budowanie list parametrów dla,

${\ Displaystyle \ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ p \ n) \ (g \ q \ p \ n)}} \ \ lambda x.\lambda o.\lambda yo\ x\ y}$

daje,

${\ Displaystyle D [g] = [[x, \ nazwa operatora {fałsz}, \_ ],[o,\nazwa_operatora {prawda} ,p],[y,\nazwa_operatora {prawda} ,n]]}$

a parametr o jest odrzucany, aby dać,

${\ Displaystyle \ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ n) \ (g \ q \ n)}} \ \ lambda x. \ lambda yp\ x\ y}$

Zbuduj listę parametrów dla ${\ Displaystyle \ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ p \ n) \ (g \ q \ p \ n)}} \ \ lambda x. \ lambda o.\lambda yo\ x\ y}$
Przykład tworzenia listy parametrów
${\ Displaystyle \ operatorname {build-param-list} [\ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ p \ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda yo\ x\ y,D,V,\_]}$ Reguła Wyrażenie Abstrakcja ${\ Displaystyle \ operatorname {build-param-list} [\ lambda m, p, q. (\ lambda g. \ lambda n. (n \ (g \ m \ p \ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda yo\ x\ y,D,V,\_]}$ Abstrakcja ${\ Displaystyle \ operatorname {build-param-list} [(\ lambda g. \ lambda n. (n \ (g \ m \ p \ n) \ (g \ q \ p \ n )))\ \lambda x.\lambda o.\lambda yo\ x\ y,D,V,\_]}$ ${\ Displaystyle \ operatorname {build-param-lists} [n \ (g \ m \ p \ n) \ (g \ q \ p \ n), re, V,R]\land \operatorname {lista-kompilacji} [\lambda x.\lambda o.\lambda yo\ x\ y,D,V,D[g]]}$ ${\ Displaystyle \ nazwa operatora {lista kompilacji} [\ lambda x. \ lambda o. \ lambda yo \ x \ y, D, V, D [g]]}$ Reguła Wyrażenie Dodaj parametr ${\ Displaystyle \ operatorname {build-list} [\ lambda x. \ lambda o. \ lambda yo \ x \ y, re, V,D[g]]\kraj D[g]=L_{1}}$ Dodaj parametr ${\ Displaystyle \ nazwa operatora {lista kompilacji} [\ lambda o. \ lambda yo \ x \ y, D, V, L_ {1}] \ ziemia D [g] = [x, \ _, \ _]:: L_{1}}$ Dodaj parametr ${\ Displaystyle \ nazwa operatora {lista kompilacji} [\ lambda yo \ x \ y, D, V, L_ {2}] \ ziemia D [g] = [x, \ _, \ _]:: [o, \ _,\_]::L_{2}}$ Lista końcowa ${\ Displaystyle \ nazwa operatora {lista kompilacji} [o \ x \ y, D, V, L_ {3}] \ ziemia D [g] = [x, \ _, \ _]:: [o, \ _,\_]::[y,\_,\_]::L_{3}}$ ${\ Displaystyle \ operatorname {build-param-lists} [o \ x \ y, D, V, []] \ ląd D [g] = [x, \ _, \ _]::[o,\_,\_]::[y,\_,\_]::[]}$ ${\ Displaystyle \ operatorname {build-param-lists } [n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,V,R]}$ Reguła Wyrażenie Aplikacja ${\ Displaystyle \ operatorname {build-param-lists } [n\ (g\ m\ p\ n)\ (g\ q\ p\ n),D,V,R]}$ Aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [n \ (g \ m \ p \ n), D, V, T_ {1}] \ ziemia \ nazwa_operatora {listy_parametrów_kompilacji} [g\ q\ p\ n,D,V,K_{1}]}$ ${\ Displaystyle \ ziemia ((T_ {1} = [F_ {1}, S_ {1}, A_ {1}]:: R }$ ${\ Displaystyle \ ziemia (S_ {1} \ implikuje (\ operatorname {zrównać} [A_ {1}, g \ q \ p \ n] \ ziemia V [F_ {1} ]=g\ q\ p\ n))\land D[F_{1}]=K_{1})}$ Zmienny ${\ displaystyle \ operatorname {build-param-lists} [n, D, V, T_ {2}] \ land \ operatorname {build-param-lists} [g \ m \ p \ n, D, V, K_ { 2}]\land \operatorname {build-param-lists} [g\ q\ p\ n,D,V,K_{1}]}$ ${\ Displaystyle \ ziemia ((T_ {2} = [F_ {2}, S_ {2},A_{2}]::[F_{1},S_{1},A_{1}]::R}$ ${\ Displaystyle \ ziemia (S_ {1} \ implikuje (\ operatorname {zrównać} [A_ {1}, g \ q \ p\ n]\land V[F_{1}]=g\ q\ p\ n))\land D[F_{1}]=K_{1})}$ ${\ Displaystyle \ ziemia (S_ {2} \ implikuje (\ operatorname {równać} [A_ {2}, g \ m \ p \ n]\kraina V[F_{2}]=g\ m\ p\ n)}\kraina D[F_{2}]=K_{2})}$ Zmienny ${\ Displaystyle \ operatorname {build-param-lists} [g \ m \ p \ n, D, V, K_ {2}] \ land \ operatorname {build-param-lists } [g\ q\ p\ n,D,V,K_{1}]}$ ${\ Displaystyle \ ziemia ((D [n] = [F_ {2} ,S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::R}$ ${\ Displaystyle \ ziemia (S_ {1} \ implikuje (\ nazwa operatora {równa} [A_ {1}, g \ q\ p\ n]\land V[F_{1}]=g\ q\ p\ n))\land D[F_{1}]=K_{1})}$ ${\ Displaystyle \ ziemia (S_ {2} \ implikuje (\ nazwa operatora {równać} [A_ {2}, g \ m \ p\ n]\kraina V[F_{2}]=g\ m\ p\ n)}\kraina D[F_{2}]=K_{2})}$ daje, ${\ Displaystyle D [n] = [\ _, \ _, g \ m \ p \ n]::[\_,\_,g\ q\ p\ n]::R}$ ${\ Displaystyle \ operatorname {build-param-lists} [g \ m \ p \ n,D,V,K_{2}]}$ Reguła Wyrażenie aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [g \ m \ p \ n,D,V,K_{2}]}$ ${\ Displaystyle \ operatorname {build-param-lists} [g \ m \ p, D, V, T_ {3}] \ land \ operatorname {build-param-lists} [n, D, V,K_{3}]}$ ${\ Displaystyle \ ziemia ((T_ {3} = [F_ {3}, S_ {3}, A_ {3}]:: K_ {2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ nazwa operatora {równać} [A_ {3}, n] \ ziemia V [F_ {3}] = n)) \ ziemia D [ F_{3}]=D[n])}$ aplikacja, zmienna ${\ Displaystyle \ operatorname {build-param-lists} [g \ m, D, V, T_ {4}] \ land \ operatorname {build-param-lists} [p, D, V, K_ {4}]}$ ${\ Displaystyle \ ziemi T_ {4} = [\_, S_ {4}, A_ {4} }]::[\_,S_{3},A_{3}]::K_{2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ nazwa operatora {równać} [A_ {3}, n] \ ziemia V [F_ {3}] =n))\land D[F_{3}]=D[n])}$ ${\ Displaystyle \ ziemia (S_ {4} \ implikuje (\ nazwa operatora {równać} [A_ {4}, p] \ ziemia V [F_ {4}] = p)} \ ziemia D [F_ {4}]=D[p]}$ aplikacja, zmienna $\ Displaystyle \ operatorname {build-param-lists} [g, D, V, T_ {5}] \ land \ operatorname {build-param-lists} [m, D, V, K_ {5} ]}$ ${\ Displaystyle \ ziemia T_ {5 }=[F_{5},S_{5},A_{5}]::[F_{4},S_{4},A_{4}]::[F_{3},S_{3},A_ {3}]::K_{2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ operatorname {zrównać} [A_ {3},n]\kraina V[F_{3}]=n)}\kraina D[F_{3}]=D[n])}$ ${\ Displaystyle \ ziemia (S_ {4} \ implikuje (\ operatorname {równać} [A_ {4}, p] \ ziemia V[F_{4}]=p)}\land D[F_{4}]=D[p]}$ ${\ Displaystyle \ ziemia (S_ {5} \ implikuje (\ nazwa operatora {równać} [A_ {5}, m] \ ziemia V [F_ {5}] = m ))\kraina D[F_{5}]=D[m]}$ Zmienny ${\ Displaystyle D [g] = [x ,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_{2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ nazwa operatora { zrównać} [A_{3},n]\kraj V[y]=n)}\kraj D[y]=D[n])}$ ${\ Displaystyle \ ziemia (S_ {4} \ implikuje (\ nazwa operatora {równać} [A_ {4}, p] \ ziemia V[o]=p)}\ ziemia D[o]=D[p]}$ ${\ Displaystyle \ ziemia (S_ {5} \ implikuje (\ operatorname {równać} [A_ {5}, m] \ ziemia V [x] = m}} \ ziemia D[x]=D[m]}$ ${\ Displaystyle \ operatorname {build-param-lists} [g \ q \ p \ n,D,V,K_{1}]}$ Reguła Wyrażenie aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [g \ q \ p \ n,D,V,K_{1}]}$ ${\ Displaystyle \ operatorname {build-param-lists} [g \ q \ p, D, V, T_ {6}] \ land \ operatorname {build-param-lists} [n, D, V,K_{6}]}$ ${\ Displaystyle \ ziemia ((T_ {6} = [F_ {6}, S_ {6}, A_ {6}]:: K_ {1}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ nazwa operatora {równać} [A_ {6}, n] \ ziemia V [F_ {6}] = n)) \ ziemia D [ F_{6}]=D[n])}$ aplikacja, zmienna ${\ Displaystyle \ operatorname {build-param-lists} [g \ q, D, V, T_ {7}] \ land \ operatorname {build-param-lists} [p, D, V, K_ {7}]}$ ${\ Displaystyle \ ziemia T_ {7} = [\_, S_ {7}, A_ {7 }]::[\_,S_{6},A_{6}]::K_{1}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ nazwa operatora {równać} [A_ {6}, n] \ ziemia V [F_ {6}] =n))\land D[F_{6}]=D[n])}$ ${\ Displaystyle \ ziemia (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, p] \ ziemia V [F_ {7}] = p)} \ ziemia D [F_ {7}]=D[p]}$ aplikacja, zmienna $\ Displaystyle \ operatorname {build-param-lists} [g, D, V, T_ {8}] \ land \ operatorname {build-param-lists} [m, D, V, K_ {8} ]}$ ${\ Displaystyle \ ziemia T_ {8 }=[F_{8},S_{8},A_{8}]::[F_{7},S_{7},A_{7}]::[F_{6},S_{6},A_ {6}]::K_{1}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ operatorname {zrównać} [A_ {6},n]\kraina V[F_{6}]=n)}\kraina D[F_{6}]=D[n])}$ ${\ Displaystyle \ ziemia (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, p] \ ziemia V[F_{7}]=p)}\land D[F_{7}]=D[p]}$ ${\ Displaystyle \ ziemia (S_ {8} \ implikuje (\ nazwa operatora {równać} [A_ {8}, q] \ ziemia V [F_ {8}] = q ))\kraina D[F_{8}]=D[q]}$ Zmienny ${\ Displaystyle D [g] = [x ,S_{8},A_{8}]::[o,S_{6},A_{7}]::[y,S_{6},A_{6}]::K_{1}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ nazwa operatora { zrównać} [A_{6},n]\kraj V[y]=n)}\kraj D[y]=D[n])}$ ${\ Displaystyle \ ziemia (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, p] \ ziemia V[o]=p)}\ ziemia D[o]=D[p]}$ ${\ Displaystyle \ ziemia (S_ {8} \ implikuje (\ nazwa operatora {równać} [A_ {8}, q] \ ziemia V [x] = q}} \ ziemia D[x]=D[q]}$ Ponieważ nie ma definicji, ${\ Displaystyle V [n], V [p], V [q], V [m]}$ , wtedy równanie można uprościć do, ${\ Displaystyle \ operatorname {zrównać} [A, N] \ równoważnik A = N\lor (\nazwa operatora {def} [V[N]]\land A=V[N])\równoważnik A=N}$ Usuwając niepotrzebne wyrażenia, ${\ Displaystyle D [g]=[x,S_{5},A_{5}]::[o,S_{4},A_{4}]::[y,S_{3},A_{3}]::K_ {2}}$ ${\ Displaystyle \ ziemia S_ {3} \ implikuje A_ {3} = n}$ ${\ Displaystyle \ ziemia S_ {4} \ implikuje A_ {4} = p}$ ${\ Displaystyle \ ziemia S_ {5} \ implikuje A_ {5} = m}$ ${\ Displaystyle D [g] = [x ,S_{8},A_{8}]::[o,S_{6},A_{7}]::[y,S_{6},A_{6}]::K_{1}}$ ${\ Displaystyle \ ziemia S_ {6} \ implikuje A_ {6} = n}$ ${\ Displaystyle \ ziemia S_ {7} \ implikuje A_ {7} = p}$ ${\ Displaystyle \ ziemia S_ {8} \ implikuje A_ {8} = q}$ Porównując dwa wyrażenia dla , pobierz, ${\ Displaystyle D [g]}$ ${\ Displaystyle S_ {5} = S_ {8}, A_ { 5}=A_{8},S_{4}=S_{7},A_{4}=A_{7},S_{3}=S_{6},A_{3}=A_{6}}$ Jeśli $_$ ; ${\ Displaystyle n = A_ {3} = A_ {6} = n}$ Jeśli $,$ nie ma implikacji Więc ${\ displaystyle S_ {3} = \ },$ co oznacza, że ​​może to być prawda lub fałsz. Jeśli $_$ prawdą ${\ Displaystyle p = A_ {4} = A_ {7} = p}$ Jeśli $_$ prawdą ${\ Displaystyle m = A_ {5} = A_ {8} = q}$ Więc ${\ displaystyle S_ {5}}$ jest fałszywe. Wynik jest następujący: ${\ Displaystyle D [g] = [x, \ nazwa operatora {fałsz} ,\_]::[o,\_,p]::[y,\_,n]::\_}$ ${\ Displaystyle \ operatorname {build-param-lists} [o \ x \ y, D, V,L]}$ Reguła Wyrażenie aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [o \ x \ y, D, V,L]}$ aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [o \ x, D, V, T_ {9}] \ land \ operatorname {build-param-lists} [y, D, V, K_ {9}]}$ ${\ Displaystyle \ ziemia T_ {9} = [F_ {9}, S_ {9}, A_ {9}]:: L}$ ${\ Displaystyle \ ziemia (S_ {9} \ implikuje (\ nazwa operatora {równać} [A_ {9}, y] \ ziemia V [F_ {9}] = A_ {9}) \ ziemia K_ {9} = D [F_{9}]}$ zmienny ${\ Displaystyle \ operatorname {build-param-lists} [o, re, V,T_{10}]\land \operatorname {build-param-lists} [x,D,V,K_{10}]\land \operatorname {build-param-lists} [y,D,V,K_{ 10}]}$ ${\ Displaystyle \ ziemia T_ {10} = [F_ {10}, S_ {10}, A_{10}]::[F_{9},S_{9},A_{9}]::L}$ ${\ Displaystyle \ ziemia (S_ {9} \ implikuje (\ operatorname {zrównać} [A_ {9}, y] \ ziemia V [F_ {9}] = A_ {9})\land K_{9}=D[F_{9}]}$ ${\ Displaystyle \ ziemia (S_ {10} \ implikuje (\ nazwa operatora {równać} [A_ {10}, y] \ ziemia V [F_ {10}] = A_ {10}) \ ziemia K_ {10 }=D[F_{10}]}$ ${\ Displaystyle \ ziemia D [o] = [F_ {10}, S_ {10 },A_{10}]::[F_{9},S_{9},A_{9}]::L}$ ${\ Displaystyle \ ziemia (S_ {9} \ implikuje (\ nazwa operatora {równać} [A_ {9}, y] \ ziemia V [F_ {9} ]=A_{9})\land K_{9}=D[F_{9}]}$ ${\ Displaystyle \ ziemia (S_ {10} \ implikuje (\ operatorname {równać} [A_ {10}, y] \ ziemia V [F_ {10}] = A_ {10}) \ ziemia K_ {10}=D[F_{10}]}$ Za pomocą podobnych argumentów, jak użyte powyżej, get, ${\ Displaystyle D [o] = [\ _, \ _, x]:: [\_, \ _, y]::\_}$ i z poprzednio ${\ Displaystyle D [g] = [[x, \ operatorname {fałsz}, \_ ],[o,\nazwa_operatora {prawda} ,p],[y,\nazwa_operatora {prawda} ,n]]}$ ${\ Displaystyle D [n] = [[\ _, \ _, (g \ m \ p \ n)], [\ _, \ _, (g \ q \ p \ n)]]}$ ${\ Displaystyle D [m] = \ _}$ ${\ Displaystyle D [p] = \ _}$ ${\ Displaystyle D [q] = \ _}$

Innym przykładem jest

${\ Displaystyle \ lambda f. ({\ lambda pf \ (p \ p \ f)) \ (\ lambda q.\lambda xx\ (q\ q\ x))}$

Tutaj x jest równe f. Mapowanie listy parametrów to,

${\ Displaystyle D [p] = [[q, \ _, p], [x, \ _, f]]}$

a parametr x jest odrzucany, aby dać,

${\ Displaystyle \ lambda f. ((\ lambda qf \ (q \ q)) \ (\ lambda qf \ (q \ q ))}$

Zbuduj listę parametrów dla ${\ Displaystyle \ lambda f. ({\ lambda pf \ (p \ p \ f)) \ (\ lambda q.\lambda xx\ (q\ q\ x))}$

W tym trudniejszym przykładzie zastosowano logikę in equate . ${\ Displaystyle \ operatorname {build-param-list} [\ lambda f. ((\ lambda pf \ (p \ p \ f)) \ (\ lambda q. \ lambda xx \ (q \ q \ x)) ,D,V,\_]}$ Reguła Wyrażenie Abstrakcja ${\ Displaystyle \ operatorname {build-param-list} [\ lambda f. ((\ lambda pf \ (p \ p \ f)) \ (\ lambda q. \ lambda xx \ (q \ q \ x)) ,D,V,\_]}$ Abstrakcja ${\ Displaystyle \ operatorname {build-param-list} [(\ lambda pf \ (p \ p \ f)) \ (\ lambda q. \ lambda xx \ (q \ q \ x)), D, V, \ _]}$ ${\ Displaystyle \ operatorname {build-param-lists} [f \ (p \ p \ f), D, \ _] \ land \ operatorname {build-list} [\ lambda q.\lambda xx\ (q\ q\ x),D,D[p]]}$ ${\ Displaystyle \ operatorname {build-param-lists} [f \ (p \ p \ f), D, \ _] \ ziemia \ operatorname {build-list } [\lambda q.\lambda xx\ (q\ q\ x),D,D[p]]}$ ${\ Displaystyle \ nazwa operatora {lista kompilacji} [\ lambda q. \ lambda xx \ (q \ q \ x), D, D [p]]}$ Reguła Wyrażenie Dodaj parametr ${\ Displaystyle \ operatorname {build-list} [\ lambda q. \ lambda xx \ (q \ q \ x), re ,D[p]]\kraj D[p]=L_{1}}$ Dodaj parametr ${\ Displaystyle \ operatorname {build-list} [\ lambda xx \ (q \ q \ x ),D,L_{2}]\land D[p]=[q,\_,\_]::L_{2}}$ Lista końcowa ${\ Displaystyle \ nazwa operatora {lista kompilacji} [x \ (q \ q \ x), D, L_ {3}] \ ziemia D [p] = [q, \ _, \ _]:: [x, \ _,\_]::L_{3}}$ ${\ Displaystyle \ operatorname {build-param-lists} [x \ (q \ q \ x), D, []] \ ląd D [p] = [q, \ _, \ _]:: [x ,\_,\_]::[]}$ ${\ Displaystyle \ operatorname {build-param-lists} [\ lambda pf \ (p \ p \ f), D, V, T_ {1}]}$ Reguła Wyrażenie Abstrakcja ${\ Displaystyle \ operatorname {build-param-lists} [\ lambda pf \ (p \ p \ f), D, V, T_ {1}]}$ Aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [f \ (p \ p\ f),D,V,T_{1}]}$ Nazwa ${\ Displaystyle \ operatorname {build-param-lists} [f, D, V, T_ {2}] \ land \ operatorname {build-param-lists} [p \ p \ f, D, V, K_ {2}]}$ ${\ Displaystyle \ ziemi T_ {2} = [F_ { 2},S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_}$ ${\ Displaystyle \ ziemia (S_ {2} \ implikuje (\ operatorname {zrównać } [A_{2},p\ p\ f]\kraina V[F_{2}]=A_{2}))\kraina D[F_{2}]=K_{2}}$ Nazwa ${\ Displaystyle \ operatorname {build-param-lists} [p \ p \ f, D ,V,K_{2}]}$ ${\ Displaystyle \ ziemia D [f] = [F_ {2}, S_ {2 },A_{2}]::[F_{1},S_{1},A_{1}]::\_}$ ${\ Displaystyle \ ziemia (S_ {2} \ implikuje (\ nazwa_operatora {equate} [A_{2},p\ p\ f]\land V[F_{2}]=A_{2}))\land D[F_{2}]=K_{2}}$ Nazwa ${\ Displaystyle \ operatorname {build-param-lists} [p \ p, D, V, T_ {3}] \ land \ operatorname {build-param-lists} [f, D, V, K_ {3}]}$ ${\ Displaystyle \ ziemia T_ {3} = [F_ {3}, S_ {3}, A_ {3}]: :K_{2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ nazwa operatora {równać} [A_ {3}, f] \ ziemia V [F_$ Aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [p \ p, D, V, T_{3}]}$ ${\ Displaystyle \ ziemia T_ {3} = [F_ {3}, S_ {3}, A_ {3}] :: K_ {2}}$ ${\ Displaystyle \ ziemia (S_ {2} \ implikuje (\ nazwa operatora {równać} [A_ {2}, p \ p \ f]$ ${\ Displaystyle \ land (S_ {3} \ implikuje (\ operatorname { równać} [A_{3},f]\kraina V[F_{3}]=A_{3})}\kraina D[F_{3}]=D[f]}$ Nazwa $\ Displaystyle \ operatorname {build-param-lists} [p, D, V, T_ {4}] \ land \ operatorname {build-param-lists} [p, D, V, K_ {4} ]}$ ${\ Displaystyle \ ziemi T_ {4} = [F_ {4}, S_ { 4},A_{4}]::[F_{3},S_{3},A_{3}]::K_{2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ operatorname {zrównać} [ A_{3},f]\land V[F_{3}]=A_{3}))\land D[F_{3}]=D[f]}$ ${\ Displaystyle \ ziemia (S_ {4} \ implikuje (\ operatorname {zrównać} [A_ {4}, p] \ ziemia V[F_{4}]=A_{4}))\kraina D[F_{4}]=K_{4}}$ ${\ Displaystyle D [p] = [F_ {4}, S_ {4}, A_{4}]::[F_{3},S_{3},A_{3}]::K_{2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ nazwa operatora {równać} [A_ {3}, f] \ ziemia V [F_ { 3}]=A_{3}))\land D[F_{3}]=D[f]}$ ${\ Displaystyle \ ziemia (S_ {4} \ implikuje (\ nazwa operatora {równać} [A_ {4}, p] \ ziemia V [F_ {4}] = A_ {4} ))\kraj D[F_{4}]=D[p]}$ ${\ Displaystyle \ operatorname {build-param-lists} [x \ (q \ q\ x)),D,V,\_]}$ Reguła Wyrażenie Abstrakcja ${\ Displaystyle \ operatorname {build-param-lists} [\ lambda q. \ lambda xx \ (q \ q \ x)), D, V, \ _ ]}$ Aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [x \ ( q\ q\ x)),D,V,K_{1}]}$ Nazwa ${\ Displaystyle \ operatorname {build-param-lists} [x, D, V, T_ {5}] \ land \ operatorname {build-param-lists} [q \ q \ x, D, V, K_ {5}]}$ ${\ Displaystyle \ ziemia T_ {5} = [F_ {5}, S_ {5}, A_ {5} ]::\_}$ ${\ Displaystyle \ ziemia (S_ {5} \ implikuje (\ nazwa operatora {równać} [A_ {5}, q \ q \ x] \kraj V[F_{5}]=A_{5}))\kraj D[F_{5}]=K_{5}}$ Nazwa ${\ Displaystyle \ operatorname {build-param-lists} [q \ q \ x, D ,V,K_{5}]}$ ${\ Displaystyle \ ziemia D [x] = [F_ {5}, S_ {5}, A_ {5}] :: \ }$ ${\ Displaystyle \ ziemia (S_ {5} \ implikuje (\ nazwa operatora {równać} [A_ {5}, q \ q \ x] \$ Nazwa ${\ Displaystyle \ nazwa operatora {listy parametrów kompilacji} [q \ q, D, V, T_ {6}] \ ziemia \ nazwa operatora {listy parametrów kompilacji} [x, D, V, K_ {6}]}$ ${\ Displaystyle \ ziemia T_ {6} = [F_ {6}, S_ {6}, A_ {6}]: :K_{5}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ nazwa operatora {równać} [A_ {6}, x] \ ziemia V [F_$ Aplikacja ${\ Displaystyle \ operatorname {build-param-lists} [q \ q, D, V, T_{6}]}$ ${\ Displaystyle \ ziemia T_ {6} = [F_ {6}, S_ {6}, A_ {6}] :: K_ {5}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ nazwa operatora {równać} [A_ {6}, x] \ ziemia V [F_ {6}]=A_{6}))\kraj D[F_{6}]=D[x]}$ Nazwa $\ Displaystyle \ operatorname {build-param-lists} [q, D, V, T_ {7}] \ land \ operatorname {build-param-lists} [q, D, V, K_ {7} ]}$ ${\ Displaystyle \ ziemia T_ {7} = [F_ {7}, S_ { 7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ operatorname {zrównać} [ A_{6},x]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ ${\ Displaystyle \ ziemia (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, q] \ ziemia V[F_{7}]=A_{7}))\kraina D[F_{7}]=K_{7}}$ Nazwa ${\ Displaystyle \ operatorname {build-param-lists} [q, D, V, K_ {7 }]}$ ${\ Displaystyle \ ziemia D [q] = [F_ {7}, S_ {7}, A_ {7}]:: [F_ {6}, S_ {6}, A_ {6}]::K_{5}}$ ${\ Displaystyle \ ziemia (S_ {6} \ implikuje (\ nazwa operatora {równać} [A_ {6}, x] \ ziemia V [F_ {6}] = A_ {6})) \ ziemia D [F_ {6} ] = re[x]}$ ${\ Displaystyle \ ziemia (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, q] \ ziemia V [F_ {7}] = A_ {7}}) \ ziemia D [F_ {7} ]=D[q]}$ Po wspólnym zebraniu wyników ${\ Displaystyle D [p] = [q, \ _, \ _]:: [x, \ _, \_]::L_{3}}$ ${\ Displaystyle D [p] = [F_ {4}, S_ {4}, A_ {4}]:: [F_ {3}, S_ {3}, A_ {3}]:: K_ { 2}}$ ${\ Displaystyle \ ziemia (S_ {3} \ implikuje (\ nazwa operatora {równać} [A_ {3}, f] \ ziemia V [F_ {3}] = A_ {3})) \ ziemia D [F_ {3} ] = re[f]}$ ${\ Displaystyle \ ziemia (S_ {4} \ implikuje (\ nazwa operatora {równać} [A_ {4}, p] \ ziemia V [F_ {4}] = A_ {4})) \ ziemia D [F_ {4} ] = D [p]} re$ $\ Displaystyle D [q] = [F_ {7 },S_{7},A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\ Displaystyle (S_ {6} \ implikuje (\ nazwa operatora {równa} [A_ {6}, x ]\land V[F_{6}]=A_{6}))\land D[F_{6}]=D[x]}$ ${\ Displaystyle (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, q] \ ziemia V [F_ {7} ]=A_{7}))\kraina D[F_{7}]=D[q]}$ Z dwóch definicji dla ${\ Displaystyle D [p]}$ ; ${\ Displaystyle F_ {4} = q}$ ${\ Displaystyle F_ {3} = x}$ Więc ${\ Displaystyle D [p] = [q, S_ {4}, A_ {4}] ::[x,S_{3},A_{3}]::K_{2}}$ ${\ Displaystyle (S_ {3} \ implikuje (\ nazwa operatora {równać} [A_ {3}, f] \ ziemia V [x] = A_ {3}}) \land re[x]=D[f]}$ ${\ Displaystyle (S_ {4} \ implikuje (\ nazwa operatora {równać} [A_ {4}, p] \ ziemia V [q] = A_ {4}}) \ ziemia D [q] = D [p]}$ re ${\ Displaystyle D [q] = D [p]$ i ${\ Displaystyle D [p] = [F_ {7}, S_ {7}, A_{7}]::[F_{6},S_{6},A_{6}]::K_{5}}$ ${\ Displaystyle (S_ {6} \ implikuje (\ nazwa operatora {równa} [A_ {6}, x] \ ziemia V [F_ {6}] =A_{6})}\land D[F_{6}]=D[x]}$ ${\ Displaystyle (S_ {7} \ implikuje (\ nazwa operatora {równać} [A_ {7}, q] \ ziemia V [F_ {7}] = A_ {7}}) \ ziemia D[F_{7}]=D[q]}$ porównując z powyższym, ${\ Displaystyle F_ {7} = q, F_ {6} = x, A_{3}=A_{6},A_{4}=A_{7},S_{3}=S_{6},S_{4}=S_{7}}$ Więc, ${\ Displaystyle V [x] = A_ {3}}$ ${\ Displaystyle V [q] = A_ {4}}$ W, ${\ Displaystyle S_ {3} \ implikuje A_ {3} = f}$ ${\ Displaystyle S_ {3} \ implikuje ( A_{3}=x\lub A_{3}=v[x])}$ zmniejsza się do, ${\ Displaystyle S_ {3} \ implikuje A_ {3} = f}$ Również, ${\ Displaystyle S_ {4} \ implikuje A_ {4} = p}$ ${\ Displaystyle S_ {4} \ implikuje ( A_{4}=q\lub A_{4}=v[q])}$ zmniejsza się do, ${\ Displaystyle S_ {4} \ implikuje A_ {4} = p}$ Tak więc lista parametrów dla p jest efektywnie; ${\ Displaystyle D [p] = [q, \ _, p]:: [x, \ _, f] ::\_}$

Upuść parametry

Użyj informacji uzyskanych za pomocą list parametrów kompilacji, aby usunąć rzeczywiste parametry, które nie są już potrzebne. drop-params ma parametry,

• Wyrażenie lambda, w którym parametry mają zostać usunięte.
• Mapowanie nazw zmiennych na listy parametrów (wbudowane w listy parametrów Build).
• Zestaw zmiennych dowolnych w wyrażeniu lambda.
• Zwrócona lista parametrów. Parametr używany wewnętrznie w algorytmie.

Abstrakcja

${\ Displaystyle \ nazwa operatora {drop-params} [(\ lambda NS) \ L, D, V, R] \ równoważnik (\lambda N.\operatorname {drop-params} [S,D,F,R])\\operatorname {drop-formal} [D[N],L,F]}$

Gdzie,

${\ Displaystyle F = FV [(\ lambda NS) \ L]}$

${\ Displaystyle \ operatorname {drop-params} [\ lambda NS, D, V, R] \ równoważnik (\ lambda N. \ operatorname {drop-params} [ S,D,P,R])}$

Gdzie,

${\ Displaystyle F = FV [\ lambda NS]}$

Zmienny

${\ Displaystyle \ nazwa operatora {drop-params} [N, D, V, D [N]] \ równoważnik N}$

W przypadku nazwy funkcji lub parametru zacznij zapełniać rzeczywistą listę parametrów, wyświetlając listę parametrów dla tej nazwy.

Aplikacja — aplikacja (wywołanie funkcji) jest przetwarzana w celu wyodrębnienia

$\ Displaystyle (\ nazwa operatora {def} [F] \ ziemia \ nazwa operatora {zapytaj} [S] \ ziemia FV [A] \subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R ]}$

${\ Displaystyle \ neg (\ nazwa operatora {def} [F] \ ziemia \ nazwa operatora {zapytaj} [S ]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F, S,A]::R]\ \operatorname {drop-params} [P,D,V,\_]}$

Let - Let wyrażenie.

${\ Displaystyle \ operatorname {drop-params} [\ operatorname {niech} V: E \ operatorname { in} L]\equiv \operatorname {let} V:\operatorname {drop-params} [E,D,FV[E],[]]\operatorname {in} \operatorname {drop-params} [L,D, FV[L],[]]}$

I - Do użytku w „niech”.

${\ Displaystyle \ operatorname {drop-params} [E \ ziemia F, D, V, \ _] \ równoważnik \ nazwa operatora {drop-params} [E, D ,V,\_]\land \operatorname {drop-params} [F,D,V,\_]}$

Upuść parametry z aplikacji

${\ Displaystyle \ lambda g. \ lambda nn \ (g \ m \ p \ n) \ (g \ q \ p \ n)}$ Stan Wyrażenie ${\ Displaystyle \ nazwa operatora {drop-param} [\ lambda g. \ lambda nn \ (g \ m \ p\ n)\ (g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\ Displaystyle \ lambda g. \ nazwa operatora {drop-param} [\ lambda nn \ (g \ m \ p\ n)\ (g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\ Displaystyle \ neg (\ nazwa operatora {def} [F_ {1}] \ ziemia ...)$ ${\ Displaystyle \ lambda g. \ lambda n. \ operatorname {drop-param} [n \ (g \ m\ p\ n),D,\{p,q,m\},[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-param} [ (g\ q\ p\ n),D,\{p,q,m\},\_]}$ ${\ Displaystyle \ neg (\ nazwa operatora {def} [F_ {2}] \ ziemia ...)$ ${\ Displaystyle \ lambda g. \ lambda n. \ operatorname {drop-param} [n \, re, \ {p, q, m \}, [F_ {2}, S_{2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-param} [(g\ m\ p\ n ),D,\{p,q,m\},\_]\\operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_ ]}$ ${\ Displaystyle D [n] = [F_ {2}, S_ {2}, A_{2}]::[F_{1},S_{1},A_{1}]::\_]}$ ${\ Displaystyle \ lambda g. \ lambda nn \ \ operatorname {drop-param} [(g \ m \ p \ n), re, \ {p ,q,m\},\_]\ \operatorname {drop-param} [(g\ q\ p\ n),D,\{p,q,m\},\_]}$ Z wyników zestawień parametrów budynku; ${\ Displaystyle D [n] = [[\ _, \ _, (g \ m\ p\ n)],[\_,\_,(g\ q\ p\ n)]]}$ Więc, ${\ Displaystyle F_ {1} = \_}$ ${\ Displaystyle F_ {2} = \ _}$ Więc, ${\ Displaystyle \ nazwa operatora {def} [F_ {1}] = \ nazwa operatora {fałsz}}$ ${\ Displaystyle \ nazwa operatora {def} [F_ {2} ]=\nazwa operatora {fałsz} }$ ${\ Displaystyle \ operatorname {drop-param} [(g \ m \ p \ n ),D,\{p,q,m\},\_]}$ Stan Rozszerzony Wyrażenie ${\ Displaystyle V = \ {p, q, m \}}$ ${\ Displaystyle \ operatorname {drop-param} [(g \ m \ p \ n), D, V, \_]}$ ${\ Displaystyle FV (A_ {1}) \ nie \ podzbiór \ {p, q, m \}}$ ${\ Displaystyle n \ nie \ podzbiór \ {p, q, m \}}$ ${\ Displaystyle \ nazwa operatora {drop-params} [g \ m \ p, D, V, [F_ {1}, S_ {1}, A_ {1}]:: \ _] \ \ nazwa operatora {drop- parametry} [n,D,V,\_]}$ ${\ Displaystyle \ nazwa operatora {def} [F_ {2}] \ ziemia \ nazwa operatora {zapytaj} [S_ {2}] \ teren FV[A_{2}]\podzbiór V}$ ${\ Displaystyle \ nazwa operatora {def} [y] \ ziemia \ nazwa operatora {zapytaj} [\ _] \ ziemia FV [p]\podzbiór \{p,q,m\}}$ ${\ Displaystyle \ nazwa operatora {upuść parametry} [g \ m, D, V, [F_ {2}, S_ {2}, A_ {2}]:: [ F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\ Displaystyle \ neg \ nazwa operatora {zapytaj} [S_ {3}]}$ ${\ Displaystyle \ neg \ nazwa operatora {zapytaj} [\ nazwa operatora {fałsz}]}$ ${\ Displaystyle \ nazwa operatora {drop-params} [g, D, V, [F_ {3}, S_ {3}, A_ {3}]:: [F_ {2}, S_ {2}, A_ {2} ]::[F_{1},S_{1},A_{1}]::\_]\ \operatorname {drop-params} [m,D,V,\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\ Displaystyle D [g] = [[x, \ operatorname {fałsz}, \_ ],[o,\_,p],[y,\_,n]]}$${\ Displaystyle = [F_ {3}, S_ {3}, A_ {3}]:: [F_ {2}, S_ {2},A_{2}]::[F_{1},S_{1},A_{1}]::\_]}$ ${\ Displaystyle F_ {3} = x, S_ {3} = \ operatorname {fałsz}, A_ {3} = \_}$${\ Displaystyle F_ {2} = o, S_ {2} = \ _, A_ {2} = p}$${\ Displaystyle F_ {1} = y, S_ {1} = \ _, A_ {1} = n}$ ${\ Displaystyle g \ m \ n}$ ${\ Displaystyle \ operatorname {drop-param} [(g \ q \ p \ n ),D,\{p,q,m\},\_]}$ Stan Rozszerzony Wyrażenie V = \{p, q, m\} ${\ Displaystyle \ operatorname {drop-param} [(g \ q \ p \ n), D, V, \_]}$ ${\ Displaystyle FV (A_ {4}) \ nie \ podzbiór V}$ ${\ Displaystyle n \ nie \ podzbiór \ {p, q, m \}}$ ${\ Displaystyle \ nazwa operatora {upuść parametry} [g \ q \ p, D, V, [F_ {4}, S_ {4}, A_ {4}]:: \ _] \ \ nazwa operatora {upuść- parametry} [n,D,V,\_]}$ ${\ Displaystyle \ nazwa operatora {def} [F_ {5}] \ ziemia \ nazwa operatora {zapytaj} [S_ {5}] \ teren FV[A_{5}]\podzbiór V}$ ${\ Displaystyle \ nazwa operatora {def} [o] \ ziemia \ nazwa operatora {zapytaj} [\_] \ ziemia p \ podzbiór \ {p,q,m\})}$ ${\ Displaystyle \ nazwa operatora {upuść parametry} [g \ q, D, V, [F_ {5}, S_ {5}, A_ {5}]:: [ F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\ Displaystyle \ neg \ nazwa operatora {zapytaj} [S-6]}$ ${\ Displaystyle \ neg \ nazwa operatora {zapytaj} [\ nazwa operatora {fałsz}]}$ ${\ Displaystyle \ nazwa operatora {drop-params} [g, D, V, [F_ {6}, S_ {6}, A_ {6}]:: [F_ {5}, S_ {5}, A_ {5} ]::[F_{4},S_{4},A_{4}]::\_]\ \operatorname {drop-params} [m,D,V,\_]\ \operatorname {drop-params} [n,D,V,\_]}$ ${\ Displaystyle D [g] = [[x, \ nazwa operatora {fałsz}, \_ ],[o,\_,p],[y,\_,n]]}$${\ Displaystyle = [F_ {6}, S_ {6}, A_ {6}]:: [F_ {5}, S_ {5},A_{5}]::[F_{4},S_{4},A_{4}]::\_]}$ ${\ Displaystyle F_ {6} = x, S_ {6} = \ operatorname {fałsz}, A_ {6} = \_}$${\ Displaystyle F_ {5} = o, S_ {5} = \ _, A_ {5} = p}$${\ Displaystyle F_ {4} = y, S_ {4} = \ _, A_ {4} = n}$ ${\ Displaystyle g \ q \ n}$

Porzuć parametry formalne

drop-formal usuwa parametry formalne na podstawie zawartości list rozwijanych. Jego parametry to m.in.

• Lista upuszczania,
• Definicja funkcji (abstrakcja lambda).
• Wolne zmienne z definicji funkcji.

formalny jest zdefiniowany jako,

1. ${\ Displaystyle (\ nazwa operatora {zapytaj} [S] \ ziemia FV [A] \ podzbiór V) \to \operatorname {drop-formal} [[F,S,A]::Z,\lambda FY,V]\equiv \operatorname {drop-formal} [[F,S,A]::Z,Y[ F:=A],L]}$
2. ${\ Displaystyle \ neg (\ nazwa operatora {zapytaj} [S] \ ziemia FV [A] \ podzbiór V) \to \operatorname {drop-formal} [[F,S,A]::Z,\lambda FY,V]\equiv \lambda F.\operatorname {drop-formal} [[F,S,A]:: Z,Y,V]}$
3. ${\ Displaystyle \ nazwa operatora {drop-formal} [Z, Y, V] \ równoważnik Y}$

Co można wytłumaczyć jako,

1. Jeśli wszystkie rzeczywiste parametry mają tę samą wartość, a wszystkie wolne zmienne tej wartości są dostępne do zdefiniowania funkcji, usuń parametr i zastąp stary parametr jego wartością.
2. w przeciwnym razie nie upuszczaj parametru.
3. w przeciwnym razie zwróć treść funkcji.

Stan	Wyrażenie
${\ Displaystyle \ nazwa operatora {fałsz}}$	${\ Displaystyle \ nazwa operatora {drop-formal} [D, \ lambda x. \ lambda o. \ lambda yo \ x \ y, F]}$
${\ Displaystyle \ nazwa operatora {prawda} \ ziemia \ {p \} \ podzbiór F}$	${\ Displaystyle \ lambda x. \ operatorname {drop-formal} [D, \ lambda o. \ lambda yo \ x \ y, F]}$
${\ Displaystyle \ neg (\ nazwa operatora {prawda} \ ziemia \ {n \} \ podzbiór F}$ )	${\ Displaystyle \ lambda x. \ operatorname {drop-formal} [D, ( \lambda yo\ x\ y)[o:=p],F]}$
	${\ Displaystyle \ lambda x. \ lambda y. \ operatorname {drop-formal} [D, p \ x \ y, F] }$
	${\ Displaystyle \ lambda x. \ lambda yp \ x \ y}$

Przykład

Zaczynając od definicji funkcji kombinatora Y,

${\ Displaystyle \ operatorname {niech} p \ f \ x = f \ (x \ x) \ ląd q\ p\ f=(p\ f)\ (p\ f)\nazwa_operatora {w} q\ p\ }$

Transformacja	Wyrażenie
	${\ Displaystyle \ operatorname {niech} p \ f \ x = f \ (x \ x) \ ląd q\ p\ f=(p\ f)\ (p\ f)\nazwa_operatora {w} q\ p}$
streszczenie * 4	${\ Displaystyle \ nazwa operatora {niech} p = \ lambda f. \ lambda xf \ (x \ x) \ ziemia q = \ lambda p. \ lambda f. (p \ f)\ (p\ f)\nazwa_operatora {w} q\ p}$
lambda-abstrakcyjny-tran	${\ Displaystyle (\ lambda q. ( \lambda pq\ p)\ (\lambda f.\lambda xf\ (x\ x)))\ (\lambda p.\lambda f.(p\ f)\ (p\ f))}$
zlew-trans	${\ Displaystyle (\ lambda p. \ lambda f. (p \ f) \ (p \ f))\ (\lambda f.\lambda xf\ (x\ x))}$
zlew-trans	${\ Displaystyle \ lambda f. (\ lambda p. (p \ f) \ (p \ f)) \ (\lambda f.\lambda xf\ (x\ x))}$
drop-param	${\ Displaystyle \ lambda f. (\ lambda pp \ p) \ (\ lambda xf \ (x \ x))}$
beta-redeks	${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) \ }$

Co zwraca kombinator Y ,

${\ Displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x)) }$

Zobacz też

• Niech wyrażenie
• Kombinator punktów stałych
• rachunek lambda
• Dedukcyjny rachunek lambda
• Superkombinator
• Paradoks Curry'ego

Linki zewnętrzne

• Wyjaśnienie dotyczące przepełnienia stosu z przykładem JavaScript
• Sloneger, Ken; Kurtz, Barry. „5. Omówienie wyrażeń let” (PDF) . Podstawy języka programowania . Uniwersytet Iowa.