Drzewa ekspresji dla manekinów? [Zamknięte]

83

Jestem manekinem w tym scenariuszu.

Próbowałem przeczytać w Google, co to jest, ale po prostu nie rozumiem. Czy ktoś może mi w prosty sposób wyjaśnić, czym są i dlaczego są przydatne?

edycja: mówię o funkcji LINQ w .Net.


źródło
1
Wiem, że ten post jest dość stary, ale ostatnio przyglądałem się drzewom wyrażeń. Zainteresowałem się, gdy zacząłem używać Fluent NHibernate. James Gregory szeroko wykorzystuje to, co jest znane jako odbicie statyczne, i ma intro: jagregory.com/writings/introduction-to-static-reflection Aby zobaczyć statyczne odbicie i drzewa ekspresji w akcji, sprawdź kod źródłowy Fluent NHibernate ( fluentnhibernate.org ). To jest bardzo czyste i bardzo fajna koncepcja.
Jim Schubert,

Odpowiedzi:

89

Najlepszym wyjaśnieniem drzew ekspresji, jakie kiedykolwiek czytałem, jest ten artykuł Charliego Calverta.

Podsumowując;

Drzewo wyrażeń reprezentuje to , co chcesz zrobić, a nie sposób , w jaki chcesz to zrobić.

Rozważmy następujące bardzo proste wyrażenie lambda:
Func<int, int, int> function = (a, b) => a + b;

To oświadczenie składa się z trzech części:

  • Oświadczenie: Func<int, int, int> function
  • Operator równości: =
  • Wyrażenie lambda: (a, b) => a + b;

Zmienna functionwskazuje na surowy kod wykonywalny, który wie, jak dodać dwie liczby .

To jest najważniejsza różnica między delegatami a wyrażeniami. Wołasz function(a Func<int, int, int>), nigdy nie wiedząc, co zrobi z dwiema podanymi liczbami całkowitymi. Zajmuje dwa i zwraca jeden, czyli najwięcej, co Twój kod może wiedzieć.

W poprzedniej sekcji dowiedziałeś się, jak zadeklarować zmienną wskazującą na surowy kod wykonywalny. Drzewa wyrażeń nie są kodem wykonywalnym , są formą struktury danych.

Teraz, w przeciwieństwie do delegatów, Twój kod może wiedzieć, do czego służy drzewo wyrażeń.

LINQ zapewnia prostą składnię do tłumaczenia kodu na strukturę danych nazywaną drzewem wyrażeń. Pierwszym krokiem jest dodanie instrukcji using w celu wprowadzenia Linq.Expressionsprzestrzeni nazw:

using System.Linq.Expressions;

Teraz możemy stworzyć drzewo wyrażeń:
Expression<Func<int, int, int>> expression = (a, b) => a + b;

Identyczne wyrażenie lambda pokazane w poprzednim przykładzie jest konwertowane na drzewo wyrażenia zadeklarowane jako typu Expression<T>. Identyfikator expression nie jest kodem wykonywalnym; jest to struktura danych zwana drzewem wyrażeń.

Oznacza to, że nie możesz po prostu wywołać drzewa wyrażeń, tak jak można wywołać delegata, ale możesz je przeanalizować. Co więc może zrozumieć Twój kod, analizując zmienną expression?

// `expression.NodeType` returns NodeType.Lambda.
// `expression.Type` returns Func<int, int, int>.
// `expression.ReturnType` returns Int32.

var body = expression.Body;
// `body.NodeType` returns ExpressionType.Add.
// `body.Type` returns System.Int32.

var parameters = expression.Parameters;
// `parameters.Count` returns 2.

var firstParam = parameters[0];
// `firstParam.Name` returns "a".
// `firstParam.Type` returns System.Int32.

var secondParam = parameters[1].
// `secondParam.Name` returns "b".
// `secondParam.Type` returns System.Int32.

Tutaj widzimy, że jest wiele informacji, które możemy uzyskać z wyrażenia.

Ale po co nam to?

Dowiedziałeś się, że drzewo wyrażeń jest strukturą danych, która reprezentuje wykonywalny kod. Ale jak dotąd nie odpowiedzieliśmy na główne pytanie, dlaczego ktoś miałby chcieć dokonać takiej konwersji. To jest pytanie, które zadaliśmy na początku tego postu i teraz czas na nie odpowiedzieć.

Zapytanie LINQ to SQL nie jest wykonywane w programie C #. Zamiast tego jest tłumaczony na język SQL, przesyłany przez sieć i wykonywany na serwerze bazy danych. Innymi słowy, następujący kod nigdy nie jest wykonywany w twoim programie:
var query = from c in db.Customers where c.City == "Nantes" select new { c.City, c.CompanyName };

Najpierw jest tłumaczony na następującą instrukcję SQL, a następnie wykonywany na serwerze:
SELECT [t0].[City], [t0].[CompanyName] FROM [dbo].[Customers] AS [t0] WHERE [t0].[City] = @p0

Kod znaleziony w wyrażeniu zapytania musi zostać przetłumaczony na zapytanie SQL, które można wysłać do innego procesu jako ciąg. W tym przypadku procesem jest baza danych serwera SQL. Oczywiście znacznie łatwiej będzie przetłumaczyć strukturę danych, taką jak drzewo wyrażeń na SQL, niż przetłumaczyć surowy IL lub kod wykonywalny na SQL. Aby nieco wyolbrzymić trudność problemu, wyobraź sobie, że próbujesz przetłumaczyć serię zer i jedynek na język SQL!

Kiedy nadchodzi czas na przetłumaczenie wyrażenia zapytania na język SQL, drzewo wyrażeń reprezentujące zapytanie jest rozbierane i analizowane, tak jak w poprzedniej sekcji rozebraliśmy nasze proste drzewo wyrażeń lambda. To prawda, algorytm analizowania drzewa wyrażeń LINQ to SQL jest znacznie bardziej wyrafinowany niż ten, którego użyliśmy, ale zasada jest taka sama. Po przeanalizowaniu części drzewa wyrażenia LINQ analizuje je i decyduje o najlepszym sposobie napisania instrukcji SQL, która zwróci żądane dane.

Drzewa wyrażeń zostały utworzone w celu wykonania zadania konwersji kodu, takiego jak wyrażenie zapytania, na ciąg znaków, który można przekazać do innego procesu i tam wykonać. To takie proste. Nie ma tu żadnej wielkiej tajemnicy, żadnej magicznej różdżki, którą trzeba machać. Po prostu bierze się kod, konwertuje go na dane, a następnie analizuje dane w celu znalezienia części składowych, które zostaną przetłumaczone na ciąg, który można przekazać do innego procesu.

Ponieważ zapytanie dociera do kompilatora w takiej abstrakcyjnej strukturze danych, kompilator może je zinterpretować w niemal dowolny sposób. Nie jest zmuszony do wykonania zapytania w określonej kolejności ani w określony sposób. Zamiast tego może przeanalizować drzewo wyrażeń, odkryć, co chcesz zrobić, a następnie zdecydować, jak to zrobić. Przynajmniej w teorii ma swobodę uwzględniania dowolnej liczby czynników, takich jak bieżący ruch w sieci, obciążenie bazy danych, aktualne dostępne zestawy wyników itp. W praktyce LINQ to SQL nie bierze pod uwagę wszystkich tych czynników. , ale teoretycznie może robić prawie wszystko, czego chce. Co więcej, można przekazać to drzewo wyrażeń do jakiegoś niestandardowego kodu, który piszesz ręcznie, który mógłby je przeanalizować i przetłumaczyć na coś bardzo różniącego się od tego, co jest produkowane przez LINQ to SQL.

Po raz kolejny widzimy, że drzewa wyrażeń pozwalają nam przedstawić (wyrazić?) To , co chcemy zrobić. Korzystamy z usług tłumaczy, którzy decydują o tym, jak używane są nasze wyrażenia.

Şafak Gür
źródło
2
Jedna z lepszych odpowiedzi.
johnny
4
doskonała odpowiedź. Jednym małym aspektem do dodania do tego genialnego wyjaśnienia jest - innym zastosowaniem drzew wyrażeń jest to, że możesz modyfikować drzewo wyrażeń w locie w czasie wykonywania, jak uważasz za stosowne, zanim zaczniesz je wykonywać, co czasami jest niezwykle przydatne.
Yan D,
41

Drzewo wyrażeń to mechanizm służący do tłumaczenia kodu wykonywalnego na dane. Korzystając z drzewa wyrażeń, możesz utworzyć strukturę danych, która reprezentuje Twój program.

W języku C # można pracować z drzewem wyrażeń utworzonym przez wyrażenia lambda przy użyciu Expression<T>klasy.


W tradycyjnym programie piszesz taki kod:

double hypotenuse = Math.Sqrt(a*a + b*b);

Ten kod powoduje, że kompilator generuje przypisanie i to wszystko. W większości przypadków to wszystko, na czym Ci zależy.

W przypadku tradycyjnego kodu aplikacja nie może cofnąć się wstecz i sprawdzić hypotenuse, czy została utworzona przez wykonanie Math.Sqrt()wywołania; ta informacja po prostu nie jest częścią tego, co jest zawarte.

Rozważmy teraz wyrażenie lambda, takie jak następujące:

Func<int, int, double> hypotenuse = (a, b) => Math.Sqrt(a*a + b*b);

To jest trochę inne niż wcześniej. Teraz hypotenusejest właściwie odniesieniem do bloku kodu wykonywalnego . Jeśli zadzwonisz

hypotenuse(3, 4);

otrzymasz 5zwróconą wartość .

Możemy użyć drzew wyrażeń do zbadania bloku kodu wykonywalnego, który został utworzony. Spróbuj tego zamiast tego:

Expression<Func<int, int, int>> addTwoNumbersExpression = (x, y) => x + y;
BinaryExpression body = (BinaryExpression) addTwoNumbersExpression.Body;
Console.WriteLine(body);

To daje:

(x + y)

Bardziej zaawansowane techniki i manipulacje są możliwe dzięki drzewom ekspresji.

AnarchistGeek
źródło
7
OK, byłem z tobą do samego końca, ale nadal nie rozumiem, dlaczego to taka wielka sprawa. Trudno mi myśleć o aplikacjach.
1
Posługiwał się uproszczonym przykładem; prawdziwa siła tkwi w tym, że kod, który eksploruje drzewo wyrażeń, może być również odpowiedzialny za jego interpretację i nadanie znaczenia semantycznemu wyrażeniu.
Pierreten
2
Tak, ta odpowiedź byłaby lepsza, gdyby wyjaśnił, dlaczego (x + y) było dla nas przydatne. Dlaczego mielibyśmy chcieć badać (x + y) i jak to robimy?
Paul Matthews
Nie musisz tego eksplorować, robisz to tylko po to, aby zobaczyć, jakie jest twoje zapytanie i co zostanie w takim przypadku przetłumaczone na inny język na SQL
stanimirsp
15

Drzewa wyrażeń są reprezentacją wyrażenia w pamięci, np. Wyrażeniem arytmetycznym lub logicznym. Weźmy na przykład pod uwagę wyrażenie arytmetyczne

a + b*2

Ponieważ * ma wyższy priorytet operatorów niż +, drzewo wyrażeń jest zbudowane w następujący sposób:

    [+]
  /    \
 a     [*]
      /   \
     b     2

Mając to drzewo, można je ocenić dla dowolnych wartości a i b. Dodatkowo możesz przekształcić go w inne drzewa wyrażeń, na przykład w celu uzyskania wyrażenia.

Kiedy implementujesz drzewo wyrażeń, sugerowałbym utworzenie Expression klasy bazowej . Na tej podstawie klasa BinaryExpression byłaby używana dla wszystkich wyrażeń binarnych, takich jak + i *. Następnie można wprowadzić VariableReferenceExpression do zmiennych referencyjnych (takich jak a i b) oraz inną klasę ConstantExpression (dla 2 z przykładu).

Drzewo wyrażeń jest w wielu przypadkach budowane w wyniku analizy danych wejściowych (bezpośrednio od użytkownika lub z pliku). Do oceny drzewa wyrażeń sugerowałbym użycie wzorca Visitor .

EFrank
źródło
15

Krótka odpowiedź: Fajnie jest móc napisać tego samego rodzaju zapytania LINQ i skierować je do dowolnego źródła danych. Bez niego nie byłoby zapytania „Language Integrated”.

Długa odpowiedź: Jak zapewne wiesz, kompilując kod źródłowy, przekształcasz go z jednego języka na inny. Zwykle od języka wysokiego poziomu (C #) do niższej dźwigni (IL).

Zasadniczo można to zrobić na dwa sposoby:

  1. Możesz przetłumaczyć kod za pomocą funkcji znajdź i zamień
  2. Analizujesz kod i otrzymujesz drzewo parsowania.

To ostatnie jest tym, co robią wszystkie programy, które znamy jako „kompilatory”.

Gdy masz już drzewo parsowania, możesz je łatwo przetłumaczyć na dowolny inny język i na to pozwalają drzewa wyrażeń. Ponieważ kod jest przechowywany jako dane, możesz z nim zrobić wszystko, co chcesz, ale prawdopodobnie będziesz chciał po prostu przetłumaczyć go na inny język.

Teraz w LINQ to SQL drzewa wyrażeń są zamieniane w polecenie SQL, a następnie przesyłane za pośrednictwem połączenia kablowego do serwera bazy danych. O ile wiem, tłumacząc kod nie robią nic wymyślnego, ale mogli . Na przykład dostawca zapytań może utworzyć inny kod SQL w zależności od warunków sieciowych.

Rodrick Chapman
źródło
6

IIUC, drzewo wyrażeń jest podobne do abstrakcyjnego drzewa składni, ale wyrażenie zwykle wyświetla pojedynczą wartość, podczas gdy AST może reprezentować cały program (z klasami, pakietami, funkcją, instrukcjami itp.)

W każdym razie dla wyrażenia (2 + 3) * 5 drzewo to:

    *
   / \ 
  +   5
 / \
2   3

Oceń każdy węzeł rekurencyjnie (od dołu do góry), aby uzyskać wartość w węźle głównym, tj. Wartość wyrażenia.

Możesz oczywiście mieć operatory jednoargumentowe (negacja) lub trójargumentowe (jeśli-to-jeszcze) oraz funkcje (n-ary, tj. Dowolna liczba operacji), jeśli pozwala na to język wyrażeń.

Ocena typów i kontrola typów odbywa się na podobnych drzewach.

Macke
źródło
5


Drzewa wyrażeń DLR są dodatkiem do języka C # w celu obsługi środowiska uruchomieniowego języka dynamicznego (DLR). DLR jest również tym, co jest odpowiedzialne za udostępnianie nam metody deklarowania zmiennych „var”. (var objA = new Tree(); )

Więcej o DLR .

Zasadniczo Microsoft chciał otworzyć środowisko CLR dla języków dynamicznych, takich jak LISP, SmallTalk, Javascript itp. Aby to zrobić, musieli mieć możliwość analizowania i oceniania wyrażeń w locie. Nie było to możliwe przed pojawieniem się DLR.

Wracając do mojego pierwszego zdania, drzewa wyrażeń są dodatkiem do C #, który otwiera możliwość korzystania z DLR. Wcześniej C # był językiem znacznie bardziej statycznym - wszystkie typy zmiennych musiały być zadeklarowane jako określony typ, a cały kod musiał być napisany w czasie kompilacji.

Używanie go z
drzewami wyrażeń danych otwiera bramy powodziowe dla kodu dynamicznego.

Załóżmy na przykład, że tworzysz witrynę z nieruchomościami. Na etapie projektowania znasz wszystkie filtry, które możesz zastosować. Aby zaimplementować ten kod, masz dwie możliwości: możesz napisać pętlę porównującą każdy punkt danych z serią testów Jeśli-To; lub możesz spróbować zbudować zapytanie w języku dynamicznym (SQL) i przekazać je do programu, który może przeprowadzić wyszukiwanie za Ciebie (baza danych).

Dzięki drzewom wyrażeń możesz teraz zmieniać kod w swoim programie - w locie - i przeprowadzać wyszukiwanie. W szczególności możesz to zrobić za pośrednictwem LINQ.

(Zobacz więcej: MSDN : instrukcje: używanie drzew wyrażeń do tworzenia zapytań dynamicznych ).

Więcej niż dane
Podstawowe zastosowania drzew wyrażeń to zarządzanie danymi. Można ich jednak używać również w przypadku kodu generowanego dynamicznie. Tak więc, jeśli potrzebujesz funkcji, która jest definiowana dynamicznie (ala Javascript), możesz utworzyć drzewo wyrażeń, skompilować je i ocenić wyniki.

Poszedłbym nieco bardziej dogłębnie, ale ta strona radzi sobie znacznie lepiej:

Drzewa wyrażeń jako kompilator

Wymienione przykłady obejmują tworzenie operatorów ogólnych dla typów zmiennych, ręcznie przewijane wyrażenia lambda, wydajne płytkie klonowanie i dynamiczne kopiowanie właściwości odczytu / zapisu z jednego obiektu do drugiego.


Drzewa wyrażeń podsumowania to reprezentacje kodu, który jest kompilowany i oceniany w czasie wykonywania. Pozwalają na typy dynamiczne, co jest przydatne przy manipulowaniu danymi i programowaniu dynamicznym.

Richard
źródło
Tak, wiem, że spóźniłem się na mecz, ale chciałem napisać tę odpowiedź, aby samemu ją zrozumieć. (To pytanie pojawiło się wysoko podczas mojego wyszukiwania w Internecie.)
Richard
Dobra robota. To dobra odpowiedź.
Rich Bryant
5
Słowo kluczowe „var” nie ma nic wspólnego z DLR. Mylisz to z „dynamiką”.
Yarik
To jest dobra, mała odpowiedź na temat var, która pokazuje, że Yarik ma rację. Wdzięczny jednak za resztę odpowiedzi. quora.com/…
johnny
1
To wszystko jest złe. varjest cukrem składniowym czasu kompilacji - nie ma nic wspólnego z drzewami wyrażeń, DLR czy środowiskiem wykonawczym. var i = 0jest kompilowany tak, jakbyś pisał int i = 0, więc nie możesz użyć go vardo reprezentowania typu, który nie jest znany w czasie kompilacji. Drzewa wyrażeń nie są „dodatkiem do obsługi DLR”, zostały wprowadzone w .NET 3.5, aby umożliwić LINQ. Z drugiej strony DLR został wprowadzony w .NET 4.0, aby umożliwić języki dynamiczne (takie jak IronRuby) i dynamicsłowo kluczowe. Drzewa wyrażeń są w rzeczywistości używane przez DLR do zapewniania współdziałania, a nie na odwrót.
Şafak Gür,
-3

Czy drzewo wyrażeń, do którego się odwołujesz, jest drzewem oceny wyrażeń?

Jeśli tak, to jest to drzewo zbudowane przez parser. Parser użył Lexera / Tokenizera do identyfikacji tokenów z programu. Parser konstruuje drzewo binarne z tokenów.

Oto szczegółowe wyjaśnienie

Vinay
źródło
Cóż, chociaż prawdą jest, że drzewo wyrażeń, do którego odwołuje się OP, działa podobnie i ma taką samą koncepcję jak drzewo parsowania, jest wykonywane dynamicznie w czasie wykonywania z kodem, jednak należy zauważyć, że wraz z wprowadzeniem kompilatora Roslyn wiersz podział między nimi stał się naprawdę rozmyty, jeśli nie został całkowicie usunięty.
yoel halb