Czy zamknięcia są uważane za nieczyste funkcjonalne?

33

Czy w programowaniu funkcjonalnym zamknięcia są uważane za nieczyste?

Wydaje się, że ogólnie można uniknąć zamknięć, przekazując wartości bezpośrednio do funkcji. Dlatego należy w miarę możliwości unikać zamykania?

Jeśli są one nieczyste i słusznie stwierdzam, że można ich uniknąć, dlaczego tak wiele funkcjonalnych języków programowania obsługuje zamykanie?

Jednym z kryteriów czystej funkcji jest to, że „Funkcja zawsze ocenia tę samą wartość wyniku, biorąc pod uwagę te same wartości argumentu ”.

Przypuszczać

f: x -> x + y

f(3)nie zawsze da taki sam rezultat. f(3)zależy od wartości, yktórej nie jest argumentem f. Zatem fnie jest to czysta funkcja.

Ponieważ wszystkie zamknięcia opierają się na wartościach, które nie są argumentami, jak to możliwe, aby każde zamknięcie było czyste? Tak, teoretycznie wartość zamknięta może być stała, ale nie ma możliwości, aby się tego dowiedzieć, po prostu patrząc na kod źródłowy samej funkcji.

To prowadzi mnie do tego, że ta sama funkcja może być czysta w jednej sytuacji, ale nieczysta w innej. Nie zawsze można ustalić, czy funkcja jest czysta, czy nie, studiując jej kod źródłowy. Być może trzeba będzie rozważyć to w kontekście otoczenia w momencie, w którym jest wywoływane, zanim będzie można dokonać takiego rozróżnienia.

Czy myślę o tym poprawnie?

użytkownik2179977
źródło
6
W Haskell cały czas używam zamknięć, a Haskell jest tak czysty, jak to tylko możliwe.
Thomas Eding,
5
W czysto funkcjonalnym języku ynie można go zmienić, więc wynik f(3)zawsze będzie taki sam.
Lily Chung,
4
yjest częścią definicji, fmimo że nie jest wyraźnie oznaczony jako dane wejściowe f- nadal jest to przypadek fzdefiniowany w kategoriach y(moglibyśmy oznaczyć funkcję f_y, aby uzależnić ją od yjawnej), a zatem zmiana ydaje inną funkcję . Określona funkcja f_yokreślona dla określonego yjest bardzo czysta. (Na przykład dwie funkcje f: x -> x + 3i f: x -> x + 5różnymi funkcjami, i obie są czyste, mimo że zdarzyło nam się użyć tej samej litery, aby je oznaczyć.)
ShreevatsaR

Odpowiedzi:

26

Czystość można zmierzyć za pomocą dwóch rzeczy:

  1. Czy funkcja zawsze zwraca to samo wyjście, biorąc pod uwagę to samo wejście; tzn. czy jest względnie przejrzysty?
  2. Czy funkcja modyfikuje coś poza sobą, tj. Czy ma skutki uboczne?

Jeśli odpowiedź na 1 brzmi „tak”, a odpowiedź na „2” nie, to funkcja jest czysta. Zamknięcia powodują, że funkcja staje się nieczysta tylko wtedy, gdy zmodyfikujesz zmienną zamkniętą.

Robert Harvey
źródło
Czy to nie determinizm pierwszego przedmiotu? Czy to też jest część czystości? Nie jestem zbyt zaznajomiony z pojęciem „czystości” w kontekście programowania.
4
@JimmyHoffa: Niekoniecznie. Możesz umieścić wyjście timera sprzętowego w funkcji i nic poza funkcją nie jest modyfikowane.
Robert Harvey
1
@RobertHarvey Czy chodzi o to, jak definiujemy dane wejściowe do funkcji? Mój cytat z wikipedii koncentruje się na argumentach funkcji, podczas gdy dodatkowo rozważasz zmienne zamknięte jako dane wejściowe.
user2179977,
8
@ user2179977: o ile nie są one zmienne, należy nie uwzględniać zmienne zamknięte nad jako dodatkowe wejścia do funkcji. Raczej powinieneś uważać samo zamknięcie za funkcję i za inną funkcję, gdy zamyka się na inną wartość y. Na przykład definiujemy funkcję gtaką, która g(y)sama jest funkcją x -> x + y. Następnie gjest funkcją liczb całkowitych, która zwraca funkcje, g(3)jest funkcją liczb całkowitych, która zwraca liczby całkowite, i g(2)jest inną funkcją liczb całkowitych, która zwraca liczby całkowite. Wszystkie trzy funkcje są czyste.
Steve Jessop,
1
@Darkhogg: Tak. Zobacz moją aktualizację.
Robert Harvey
10

Zamknięcia pojawiają się Lambda Calculus, który jest najczystszą możliwą formą programowania funkcjonalnego, więc nie nazwałbym ich „nieczystymi” ...

Zamknięcia nie są „nieczyste”, ponieważ funkcje w językach funkcjonalnych są pierwszorzędnymi obywatelami - oznacza to, że można je traktować jako wartości.

Wyobraź to sobie (pseudokod):

foo(x) {
    let y = x + 1
    ...
}

yjest wartością. Jego wartość zależy od x, ale xjest niezmienna, więc ywartość jest również niezmienna. Możemy wywoływać foowiele razy z różnymi argumentami, które wytworzą różne ys, ale ywszystkie one żyją w różnych zakresach i zależą od różnych xs, więc czystość pozostaje nienaruszona.

Teraz zmieńmy to:

bar(x) {
    let y(z) = x + z
    ....
}

Tutaj używamy zamknięcia (zamykamy x), ale jest to to samo co w foo- różne wywołania barz różnymi argumentami tworzą różne wartości y(pamiętaj - funkcje są wartościami), które są niezmienne, więc czystość pozostaje nienaruszona.

Należy również pamiętać, że zamknięcia mają bardzo podobny efekt do curry:

adder(a)(b) {
    return a + b
}
baz(x) {
    let y = adder(x)
    ...
}

baztak naprawdę nie różni się od bar- w obu tworzymy funkcję o nazwie, yktóra zwraca jej argument plus x. W rzeczywistości w Lambda Calculus używasz zamknięć do tworzenia funkcji z wieloma argumentami - i nadal nie jest to nieczyste.

Idan Arye
źródło
9

Inni ładnie opisali ogólne pytanie w swoich odpowiedziach, więc przyjrzę się tylko usunięciu zamieszania, które zasygnalizowałeś w swojej edycji.

Zamknięcie nie staje się wejściem funkcji, a raczej „wchodzi” do treści funkcji. Mówiąc ściślej, funkcja odnosi się do wartości w zewnętrznym zakresie w jej ciele.

Masz wrażenie, że funkcja ta jest nieczysta. Zasadniczo tak nie jest. W programowaniu funkcjonalnym wartości są niezmienne przez większość czasu . Dotyczy to również wartości zamkniętej.

Powiedzmy, że masz taki kod:

let make y =
    fun x -> x + y

Wywoływanie make 3i make 4daje dwie funkcje z zamknięciami ponad make„s yargument. Jeden wróci x + 3, drugi x + 4. Są to jednak dwie odrębne funkcje i obie są czyste. Zostały one utworzone przy użyciu tej samej makefunkcji, ale to wszystko.

Zauważ najczęściej kilka akapitów wstecz.

  1. W Haskell, który jest czysty, można zamknąć tylko niezmienne wartości. Nie ma stanu zmiennego do zamknięcia. Z pewnością uzyskasz w ten sposób czystą funkcję.
  2. W nieczystych językach funkcjonalnych, takich jak F #, możesz zamykać komórki referencyjne i typy odwołań, i uzyskać efekt nieczystości. Masz rację, że musisz śledzić zakres, w którym funkcja jest zdefiniowana, aby wiedzieć, czy jest czysta, czy nie. Możesz łatwo stwierdzić, czy wartość jest zmienna w tych językach, więc nie stanowi to większego problemu.
  3. W językach OOP obsługujących zamknięcia, takich jak C # i JavaScript, sytuacja jest podobna do nieczystych języków funkcjonalnych, ale śledzenie zakresu zewnętrznego staje się trudniejsze, ponieważ zmienne są domyślnie zmienne.

Pamiętaj, że dla 2 i 3 języki te nie dają żadnych gwarancji czystości. Zanieczyszczenia nie są właściwością zamknięcia, ale samym językiem. Zamknięcia same w sobie nie zmieniają obrazu.

scrwtp
źródło
1
Możesz całkowicie zamknąć zmienne wartości w Haskell, ale coś takiego byłoby opatrzone adnotacją w monadzie IO.
Daniel Gratzer
1
@ jozefg nie, zamykasz niezmienną IO Awartość, a twój typ zamknięcia jest IO (B -> C)lub taki. Czystość została utrzymana
Caleth,
5

Zwykle prosiłbym cię o wyjaśnienie definicji „nieczystej”, ale w tym przypadku tak naprawdę nie ma to znaczenia. Zakładając, że kontrastujesz go z terminem czysto funkcjonalnym , odpowiedź brzmi „nie”, ponieważ nie ma nic o zamknięciach, które z natury są destrukcyjne. Jeśli twój język byłby czysto funkcjonalny bez zamknięć, nadal byłby czysto funkcjonalny z zamknięciami. Jeśli zamiast tego masz na myśli „niefunkcjonalny”, odpowiedź brzmi „nie”; zamknięcia ułatwiają tworzenie funkcji.

Wydaje się, że ogólnie można uniknąć zamknięcia, przekazując dane bezpośrednio do funkcji.

Tak, ale wtedy twoja funkcja miałaby jeszcze jeden parametr, a to zmieniłoby jej typ. Zamknięcia umożliwiają tworzenie funkcji opartych na zmiennych bez dodawania parametrów. Jest to przydatne, gdy masz, powiedzmy, funkcję, która przyjmuje 2 argumenty i chcesz utworzyć jej wersję, która przyjmuje tylko 1 argument.

EDYCJA: W odniesieniu do twojej edycji / przykładu ...

Przypuszczać

f: x -> x + y

f (3) nie zawsze daje taki sam wynik. f (3) zależy od wartości y, która nie jest argumentem f. Zatem f nie jest funkcją czystą.

Zależy to od złego wyboru słowa tutaj. Cytując ten sam artykuł w Wikipedii, który napisałeś:

W programowaniu komputerowym funkcję można opisać jako funkcję czystą, jeśli obie instrukcje dotyczące funkcji są wstrzymane:

  1. Funkcja zawsze ocenia tę samą wartość wyniku, biorąc pod uwagę te same wartości argumentu. Wartość wyniku funkcji nie może zależeć od żadnych ukrytych informacji lub stanów, które mogą się zmieniać w trakcie wykonywania programu lub między różnymi wykonaniami programu, ani też nie może zależeć od jakichkolwiek zewnętrznych danych wejściowych z urządzeń I / O.
  2. Ocena wyniku nie powoduje żadnych semantycznie obserwowalnych skutków ubocznych lub wyników, takich jak mutacja obiektów podlegających mutacji lub wyjście do urządzeń I / O.

Zakładając, że yjest niezmienny (co zwykle ma miejsce w językach funkcjonalnych), warunek 1 jest spełniony: dla wszystkich wartości xwartość f(x)nie zmienia się. Powinno to wynikać z faktu, że yniczym nie różni się od stałej i x + 3jest czyste. Jest również jasne, że nie ma mutacji ani operacji we / wy.

Doval
źródło
3

Bardzo szybko: podstawienie jest „referencyjnie przezroczyste”, jeśli „podstawienie podobnego prowadzi do podobnego”, a funkcja jest „czysta”, jeśli wszystkie jej efekty są zawarte w jej wartości zwracanej. Oba można sprecyzować, ale należy pamiętać, że nie są one identyczne, ani nawet nie implikuje drugiego.

Porozmawiajmy teraz o zamknięciach.

Nudne (głównie czyste) „zamknięcia”

Zamknięcia występują, ponieważ podczas oceny terminu lambda interpretujemy (powiązane) zmienne jako wyszukiwania środowiska. Zatem, gdy zwrócimy termin lambda w wyniku oceny, zmienne w nim zawarte „zamkną” wartości, które przyjęli, gdy zostały zdefiniowane.

W prostym rachunku lambda jest to trochę banalne i całe pojęcie po prostu znika. Aby to wykazać, oto stosunkowo lekki interpreter rachunku lambda:

-- untyped lambda calculus values are functions
data Value = FunVal (Value -> Value)

-- we write expressions where variables take string-based names, but we'll
-- also just assume that nobody ever shadows names to avoid having to do
-- capture-avoiding substitutions

type Name = String

data Expr
  = Var Name
  | App Expr Expr
  | Abs Name Expr

-- We model the environment as function from strings to values, 
-- notably ignoring any kind of smooth lookup failures
type Env = Name -> Value

-- The empty environment
env0 :: Env
env0 _ = error "Nope!"

-- Augmenting the environment with a value, "closing over" it!
addEnv :: Name -> Value -> Env -> Env
addEnv nm v e nm' | nm' == nm = v
                  | otherwise = e nm

-- And finally the interpreter itself
interp :: Env -> Expr -> Value
interp e (Var name) = e name          -- variable lookup in the env
interp e (App ef ex) =
  let FunVal f = interp e ef
      x        = interp e ex
  in f x                              -- application to lambda terms
interp e (Abs name expr) =
  -- augmentation of a local (lexical) environment
  FunVal (\value -> interp (addEnv name value e) expr)

Ważną kwestią, na którą należy zwrócić uwagę, jest fakt, addEnvże rozszerzamy środowisko o nową nazwę. Ta funkcja jest nazywana tylko „wewnątrz” interpretowanego Absterminu trakcji (lambda). Środowisko jest „sprawdzane” za każdym razem, gdy oceniamy dany Vartermin, a zatem Varrozwiązują one wszystko, Nameo czym mowa w tym, Envco zostało przechwycone przez Absprzyczepę zawierającą Var.

Teraz znowu, w kategoriach LC, jest to nudne. Oznacza to, że zmienne powiązane są tylko stałymi, o ile kogokolwiek to obchodzi. Są one oceniane bezpośrednio i natychmiast, jako wartości, które oznaczają w środowisku, jak do tego momentu, w zakresie leksykalnym.

Jest to również (prawie) czyste. Jedyne znaczenie dowolnego terminu w naszym rachunku lambda zależy od jego wartości zwracanej. Jedynym wyjątkiem jest efekt uboczny braku rozwiązania, który jest ujęty w nazwie Omega:

-- in simple LC syntax:
--
-- (\x -> (x x)) (\x -> (x x))
omega :: Expr
omega = App (Abs "x" (App (Var "x") 
                          (Var "x")))
            (Abs "x" (App (Var "x") 
                          (Var "x")))

Interesujące (nieczyste) zamknięcia

Teraz, dla niektórych środowisk, zamknięcia opisane w zwykłym LC powyżej są nudne, ponieważ nie ma pojęcia, że ​​będziemy w stanie oddziaływać na zmienne, które zamknęliśmy. W szczególności słowo „zamknięcie” ma tendencję do wywoływania kodu, takiego jak poniższy Javascript

> function mk_counter() {
  var n = 0;
  return function incr() {
    return n += 1;
  }
}
undefined

> var c = mk_counter()
undefined
> c()
1
> c()
2
> c()
3

To pokazuje, że zamknęliśmy nzmienną w funkcji wewnętrznej incri wywoływanie w sposób incrznaczący współdziała z tą zmienną. mk_counterjest czysty, ale incrzdecydowanie nieczysty (i nie jest również względnie przejrzysty).

Co różni się między tymi dwoma instancjami?

Pojęcia „zmiennej”

Jeśli spojrzymy na znaczenie substytucji i abstrakcji w prostym sensie LC, zauważymy, że są one zdecydowanie jasne. Zmienne są dosłownie niczym więcej niż bezpośrednimi przeglądami środowiska. Abstrakcja Lambda jest dosłownie niczym więcej niż stworzeniem rozszerzonego środowiska do oceny wewnętrznego wyrażenia. W tym modelu nie ma miejsca na zachowanie, które widzieliśmy z mk_counter/, incrponieważ nie jest dozwolona żadna odmiana.

Dla wielu jest to sedno tego, co oznacza „zmienna” - zmienność. Jednak semantycy lubią rozróżniać rodzaj zmiennej używanej w LC od rodzaju „zmiennej” używanej w Javascript. Aby to zrobić, nazywają to „komórką zmienną” lub „gniazdem”.

Ta nomenklatura nawiązuje do długiego historycznego użycia „zmiennej” w matematyce, gdzie oznaczała coś bardziej jak „nieznany”: (matematyczne) wyrażenie „x + x” nie pozwala xzmieniać się w czasie, zamiast tego ma znaczenie niezależnie wartości (pojedynczej, stałej) xtrwa.

Dlatego mówimy „szczelina”, aby podkreślić możliwość umieszczania wartości w szczelinie i wyjmowania ich.

Aby dodać zamieszanie, w Javascript, te „sloty” wyglądają tak samo jak zmienne: piszemy

var x;

stworzyć taki, a potem, kiedy piszemy

x;

wskazuje, że szukamy wartości aktualnie przechowywanej w tym gnieździe. Aby to wyjaśnić, czyste języki mają tendencję do myślenia o gniazdach jako nazwach (rachunku matematycznym, rachunku lambda). W takim przypadku musimy wyraźnie oznaczyć, kiedy otrzymujemy lub wkładamy z automatu. Taka notacja zwykle wygląda

-- create a fresh, empty slot and name it `x` in the context of the 
-- expression E
let x = newSlot in E

-- look up the value stored in the named slot named `x`, return that value
get x

-- store a new value, `v`, in the slot named `x`, return the slot
put x v

Zaletą tego zapisu jest to, że mamy teraz wyraźne rozróżnienie między zmiennymi matematycznymi a zmiennymi szczelinami. Zmienne mogą przyjmować boksy jako ich wartości, ale konkretny boks nazwany przez zmienną jest stały w całym jego zakresie.

Za pomocą tej notacji możemy przepisać mk_counterprzykład (tym razem w składni podobnej do Haskella, choć zdecydowanie nie podobnej do semantyki podobnej do Haskella):

mkCounter = 
  let x = newSlot 
  in (\() -> let old = get x 
             in get (put x (old + 1)))

W tym przypadku używamy procedur, które manipulują tym zmiennym gniazdem. Aby go zaimplementować, musielibyśmy zamknąć nie tylko stałe środowisko nazw, xale także zmienne środowisko zawierające wszystkie potrzebne gniazda. Jest to bliższe powszechnemu pojęciu „zamknięcia”, które ludzie tak bardzo kochają.

Znowu mkCounterjest bardzo nieczyste. Jest także bardzo referencyjnie nieprzejrzysty. Zauważ jednak, że skutki uboczne nie wynikają z przechwytywania lub zamykania nazwy, ale z przechwytywania modyfikowalnej komórki i działań niepożądanych na niej, takich jak geti put.

Ostatecznie myślę, że jest to ostateczna odpowiedź na twoje pytanie: na czystość nie wpływa (matematyczne) przechwytywanie zmiennych, ale zamiast tego działania niepożądane wykonywane na zmiennych gniazdach nazwanych przez przechwycone zmienne.

Tyle tylko, że w językach, które nie próbują być blisko LC ani nie próbują zachować czystości, te dwa pojęcia są tak często splecione, co prowadzi do zamieszania.

J. Abrahamson
źródło
1

Nie, zamknięcia nie powodują nieczystości funkcji, o ile wartość zamknięcia jest stała (nie zmieniana przez zamknięcie ani inny kod), co jest typowym przypadkiem w programowaniu funkcjonalnym.

Zauważ, że chociaż zawsze możesz zamiast tego podać wartość jako argument, zwykle nie możesz tego zrobić bez znacznych trudności. Na przykład (coffeescript):

closedValue = 42
return (arg) -> console.log "#{closedValue} #{arg}"

Według Twojej sugestii możesz po prostu wrócić:

return (arg, closedValue) -> console.log "#{closedValue} #{arg}"

Ta funkcja nie jest w tym momencie wywoływana , tylko zdefiniowana , więc musisz znaleźć sposób na przekazanie pożądanej wartości closedValuedo punktu, w którym funkcja jest faktycznie wywoływana. W najlepszym wypadku tworzy to wiele sprzężeń. W najgorszym przypadku nie kontrolujesz kodu w punkcie wywoływania, więc jest to praktycznie niemożliwe.

Biblioteki zdarzeń w językach, które nie obsługują zamknięć, zwykle zapewniają inny sposób przekazywania dowolnych danych z powrotem do wywołania zwrotnego, ale nie są ładne i powodują wiele trudności zarówno dla osoby zarządzającej biblioteką, jak i dla użytkowników biblioteki.

Karl Bielefeldt
źródło