Defunktionalisering i programmering är en teknik för att transformera ett program vid kompilering , ersätta funktioner av högre ordning med ett anrop till en enda funktion för att applicera en funktion på ett argument.
Det beskrevs först av John Reynolds 1972 [ 1 ] . Eftersom vilket program som helst innehåller ett ändligt antal funktionella abstraktioner, kan var och en av dem ersättas med en unik identifierare, och varje tillämpning av en abstrakt funktion i ett sådant program kan ersättas av ett funktionsanrop för tillämpningsfunktionen med identifieraren för abstraktet fungerar som den första parametern. I det här fallet väljer applikationsfunktionen operationer med identifieraren för den abstrakta funktionen och utför dem på de återstående argumenten (de ursprungliga argumenten för den abstrakta funktionen).
En svårighet för denna teknik är att den funktionella abstraktionen kan referera till fria variabler . I en sådan situation måste λ-lifting — omvandlingen av fria variabler till stängningar — utföras innan defunktionalisering utförs , så att alla fria variabler som används av den funktionella abstraktionen skulle skickas som ett argument till applikationsfunktionen. Dessutom, om tömning stöds som ett förstaklassvärde måste nya datastrukturer skapas för att representera de infångade värdena.
Istället för att använda en enda applikationsfunktion för att hantera alla fall, kan olika tekniker för kontrollflödesanalys (inklusive den enkla distinktionen mellan olika sorters ariteter (antal argument) eller typsignaturer ) användas för att separera applikationen i flera specialiserade funktioner. Dessutom kan programmeringsspråket stödja funktionspekare , vilket kan vara mer effektivt än avsändningsmetoden.
Förutom att användas i kompilatorer för funktionella programmeringsspråk som använder högre ordningsfunktioner, har defunktionalisering också utforskats som en metod för att mekanistiskt omvandla en tolk till en abstrakt maskin . Defunktionalisering är också relaterad till tekniken att representera funktioner med funktionsobjekt i objektorienterad programmering (som ett alternativ till att använda stängningar).
För träddatatypen [ 2] :
dataträd a = Blad a | _ Nod ( Träd a ) ( Träd a )följande program är defunktionaliserat:
nackdelar :: a -> [ a ] -> [ a ] nackdelar x xs = x : xs o :: ( b -> c ) -> ( a -> b ) -> a -> c o f g x = f ( g x ) platta :: Träd t -> [ t ] platta t = gå t [] promenad :: Träd t -> [ t ] -> [ t ] promenad ( Löv x ) = nackdelar x promenad ( Nod t1 t2 ) = o ( promenad t1 ) ( promenad t2 )För att göra detta ersätts alla funktioner av högre ordning ( cons, o, och ) med ett värde av typen , och istället för ett direkt funktionsanrop används en funktion som bearbetar värden av denna typ: walkLamapply
data Lam a = LamCons a | LamO ( Lam a ) ( Lam a ) tillämpa :: Lam a -> [ a ] -> [ a ] applicera ( LamCons x ) xs = x : xs tillämpas ( LamO f1 f2 ) xs = tillämpa f1 ( tillämpa f2 xs ) cons_def :: a -> Lam a cons_def x = LamCons x o_def :: Lam a -> Lam a -> Lam a o_def f1 f2 = LamO f1 f2 flatten_def :: Träd t -> [ t ] flatten_def t = tillämpa ( walk_def t ) [] walk_def :: Träd t -> Lam t walk_def ( Blad x ) = cons_def x walk_def ( Nod t1 t2 ) = o_def ( walk_def t1 ) ( walk_def t2 )