Στο απόλυτο βιβλίο για compilers (καθιερωμένο ως Dragon Book εξαιτίας του concept art εξωφύλλου του στην πρώτη έκδοση) ως abtract syntax trees ή απλά syntax trees, ορίζονται οι ιεραρχικές συντακτικές δομές του πηγαίου κώδικα ενός προγράμματος. Όταν γράφουμε κώδικα, υπάρχει μία πάρα πολύ συγκεκριμένη διαδικασία η οποία μετατρέπει τις λέξεις και τα σύμβολα που γράφουμε, σε δομές που έχουν συγκεκριμένη σημασιολογία. Το πρώτο κομμάτι ενός μεταγλωττιστή ασχολείται με το “διάβασμα” του κώδικα που γράφουμε. Αυτή η διαδικασία αποτελείται από τρία στάδια. Στο πρώτο στάδιο υπάρχει ένας λεκτικός αναλυτής ο οποίος παίρνει ως είσοδο το αρχείο κειμένου που γράψαμε, και το σπάει σε τεμάχια ή αλλιώς tokens. Για παράδειγμα εμείς γράφουμε items + 1 και ο αναλυτής αναγνωρίζει ως token την λέξη item. Στην συνέχεια λαμβάνει χώρα η ανάλυση (parsing), που παίρνει τα tokens και σύμφωνα με τους κανόνες της γλώσσας, δημιουργεί συντακτικά δένδρα εκφράσεων. Στο τελευταίο βήμα λαμβάνονται οι εν λόγω δενδρικές δομές και παράγεται αυτό που λέμε ενδιάμεσος κώδικας. Υπάρχουν δύο ήδη συντακτικών δένδρων, τα αφηρημένα και τα μη (abstract και concrete). Σε ένα abstract syntax tree λοιπόν απεικονίζεται μία έκφραση, του οποίου ο εσωτερικός κόμβος είναι ένας operator και τα παιδιά είναι τα operands (τα οποία μπορούν με τη σειρά τους να είναι εκφράσεις). Η διαφορά με τα concrete syntax trees είναι ότι τα concrete έρχονται κατευθείαν από τον parser (αντικατοπτρίζοντας αποκλειστικά το συντακτικό της γλώσσας) ενώ τα abstract προσδίδουν με τη σειρά τους πρόσθετη πληροφορία (σχετικά με σημασιολογία π.χ.).
Πολύ όμορφα λοιπόν, γράφουμε λέξεις περιγράφοντας διαδικασίες οι οποίες μεταφράζονται σε εντολές. Στην γλώσσα C# τα expression trees αποτελούν έναν τύπο δεδομένων που αποθηκεύει κώδικα σε μορφή δεδομένων. Τα δεδομένα αποθηκεύονται υπό τη μορφή δένδρων, όπως ακριβώς τα δένδρα που περιέγραψα παραπάνω. Με το συγκεκριμένο τύπο δεδομένων μπορούμε να κάνουμε κάτι πάρα πολύ όμορφο και θεάρεστο :P: να αλλάξουμε ή να μετασχηματίσουμε κώδικα κατά το runtime execution, πριν τον εκτελέσουμε. Για παράδειγμα υπάρχει η δυνατότητα να μετατραπεί κώδικας C# (όπως κάνει η LINQ μέσω των query expressions) σε κώδικα που εκτελείται σε άλλο process, όπως είναι μία βάση δεδομένων.
Έστω ότι έχουμε την παρακάτω έκφραση lambda λοιπόν, η οποία μας περιγράφει μία συνάρτηση που παίρνει δύο ακεραίους ως παραμέτρους και επιστρέφει έναν άλλον ακέραιο.
Func<int, int, int> function = (a,b) => a + b;
Το παραπάνω μας βοηθάει να δηλώσουμε μία μεταβλητή συνάρτησης στην οποία αποθηκεύεται ένα lambda που υπολογίζει το άθροισμα δύο αριθμών (βλ. delegates και generic functions). Ακόμα και για κάποιον που δεν έχει κατανοήσει πολύ καλά τις δύο παραπάνω έννοιες, φαίνεται πολύ καθαρά από την παραπάνω γραμμή ότι κατά κάποιον τρόπο έχουμε αποθηκεύσει στη μεταβλητή function μία αναφορά προς εκτελέσιμο κώδικα. Τα expression trees δεν είναι εκτελέσιμος κώδικας, οπότε πώς μεταφράζουμε το παραπάνω expression σε expression tree;
Expression<Func<int, int, int>> expression = (a,b) => a + b;
Με την παραπάνω γραμμή κάναμε αυτό που θέλαμε! Δηλώσαμε μία μεταβλητή expression η οποία περιέχει σε μορφή δεδομένων το συντακτικό δένδρο που θέλαμε. Τι μπορούμε να κάνουμε με αυτό λοιπόν; Μπορούμε καταρχάς να πάρουμε το σώμα της συνάρτησης με το Property Body, τις παραμέτρους με το Property Parameter, τον τύπο του κόμβου που θέλουμε με το Property NodeType (η λίστα με τους τύπους expressions), ή απλά τον CLR τύπο με το Property Type. Για την καλύτερη κατανόηση της διαφοράς μεταξύ Node Type και Type παραθέτω το παράδειγμα από το msdn:
// NodeType is Constant; Type is System.Int32.
ConstantExpression constExpr1 = Expression.Constant(5);
// NodeType is Add; Type is System.Int32
BinaryExpression binExpr = Expression.Add(constExpr1, constExpr1)
Έστω ότι έχουμε το expression που περιγράψαμε παραπάνω: Τα “δεδομένα” μπορούν να ανακτηθούν ως εξής:
BinaryExpression body = (BinaryExpression)expression.Body;
ParameterExpression left = (ParameterExpression)body.Left;
ParameterExpression right = (ParameterExpression)body.Right;
Τι κάνουμε όμως αν έχουμε μία έκφραση σε μορφή δεδομένων και θέλουμε να την εκτελέσουμε; Ότι κάνουμε πάντα! Compile!
expression.Compile()(3, 5);
Μπορεί με πρώτη ματιά να φαίνεται ότι απλά προσθέσαμε overhead στην λειτουργικότητα των lambdas. Σκεφτείτε όμως μία χρήση που ήδη βλέπετε τριγύρω σας. Πόσα διαφορετικά είδη LINQ εκτός από LINQ to objects υπάρχουν; Πώς τα queries που γράφουμε, μπορούν να εκτελεστούν σε διαφορετικά processes που τρέχουν κάποια εφαρμογή; Μέχρι τώρα λοιπόν, αυτή είναι η αλήθεια για την κύρια χρήση των expression trees. Χρησιμοποιούνται σε LINQ providers καθώς επίσης και σε μετατροπές expression trees και compilation. Στο Visual Studio 2010 τα Expression Trees έχουν επεκταθεί και κάποιος προγραμματιστής μπορεί τώρα πια με τη χρήση τους, να παράγει και δυναμικές μεθόδους (χωρίς MSIL). Αυτή η νέα δυνατότητα δεν μπορεί να πραγματοποιηθεί με lambda expressions αλλά μόνο με το νεό Expression Trees APΙ (διαθέσιμο στο Visual Studio 2010 έχοντας διατηρήσει και το υπάρχον functionality) που το επιτρέπει αυτό. Ας ξεκινήσουμε με την Expression.Block που συμβάλει στις νέες δυνατότητες των Expression Trees και επιτρέπει σειριακή εκτέλεση expressions. Το παράδειγμα πηγάζει από εδώ:
// Δημιουργώ ένα expression που θα κρατήσει την παράμετρο int arg
ParameterExpression param = Expression.Parameter(typeof(int), "arg");
// Δημιουργώ ένα expression που τυπώνει ένα string
MethodCallExpression firstMethodCall = Expression.Call(
typeof(Console).GetMethod("WriteLine", new Type[] { typeof(String) }),
Expression.Constant("Print arg:"));
// Δημιουργώ ένα expression που τυπώνει την τιμή της παραμέτρου param (int arg)
MethodCallExpression secondMethodCall = Expression.Call(
typeof(Console).GetMethod("WriteLine", new Type[] { typeof(int) }),
param);
// Βάζω σε σειρά εκτέλεσης τα δύο expressions
BlockExpression block = Expression.Block(firstMethodCall, secondMethodCall);
// Compiling ένα lambda κλείνοντας τον τύπο μεθόδου
// ως μία μέθοδο που παίρνει μία παράμετρο το οποίο lambda
// γίνεται construct με το προηγούμενο block ένα πίνακα
// με τις παραμέτρους και την αποτίμηση τους στην παράμετρο του lambda
Expression.Lambda<Action<int>>(block,new ParameterExpression[] { param }).Compile()(10);
Console.ReadKey();
Το αποτέλεσμα έχει ως εξής:
Στο ίδιο blog post μπορούμε να βρούμε ένα πιο δύσκολο παράδειγμα, παρουσιάζοντας πώς μπορούμε δυναμικά να φτιάξουμε μία μέθοδο που να παίρνει ως όρισμα έναν αριθμό (Expression.Parameter), να δηλώσουμε μία μεταβλητή (Expression.Assign) και ένα επαναληπτικό block (Expression.Loop), φτιάχνοντας την Factorial.
