Functional Programming Reading List

During the last months, I started to collect some readings (academic publications and books) that one should check out, as he learns functional programming. These are life changing readings (other pretty fundamendal, other very specific), and can be studied in a time frame of several months or more, so unless you are a doctoral researcher on the field of programming languages, take your time and enjoy.

[ 1] J. V. Eijck and C. Unger, Computational Semantics with Functional Programming, 1st ed. Cambridge University Press, 2010.
[ 2] R. Bird, Pearls of Functional Algorithm Design, 1st ed. Cambridge University Press, 2010.
[ 3] D. Vytiniotis and P. Jones, “Let should not be generalized,” in Proceedings of the 5th ACM SIGPLAN workshop on Types in language design and implementation, pp. 39–50, 2010.
[ 4] F. Kirchner and C. Munoz, “The proof monad,” Journal of Logic and Algebraic Programming, 2010.
[ 5] A. Filinski, “Monads in action,” in Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 483–494, 2010.
[ 6] J. Gibbons and B. C. Oliveira, “The essence of the Iterator pattern,” Journal of Functional Programming, vol. 19, no. 3, pp. 377–402, 2009.
[ 7] G. Hutton, Programming in Haskell. Cambridge University Press, 2007.
[ 8] C. McBride and R. Paterson, “Applicative programming with effects,” Journal of functional programming, vol. 18, no. 01, pp. 1–13, 2007.
[ 9] R. K. Dyvbig, S. P. Jones, and A. Sabry, “A monadic framework for delimited continuations,” Journal of Functional Programming, vol. 17, no. 06, pp. 687–730, 2007.
[10] P. Wadler and P. Thiemann, “The marriage of effects and monads,” ACM Transactions on Computational Logic (TOCL), vol. 4, no. 1, p. 32, 2003.
[11] B. C. Pierce, Types and Programming Languages, 1st ed. The MIT Press, 2002.
[12] B. Mcadams, “Y in practical programs,” 2001.
[13] G. Hutton, “A tutorial on the universality and expressiveness of fold,” Journal of Functional Programming, vol. 9, no. 4, pp. 355–372, 1999.
[14] S. Finne, D. Leijen, E. Meijer, and S. P. Jones, “Calling hell from heaven and heaven from hell,” in Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, pp. 114-125, 1999.
[15] J. Palsberg and C. B. Jay, “The essence of the visitor pattern,” COMPSAC-NEW YORK-, pp. 9–15, 1998.
[16] G. Hutton and E. Meijer, “Monadic parsing in Haskell,” Journal of functional programming, vol. 8, no. 04, pp. 437–444, 1998.
[17] G. Huet, “The zipper,” Journal of Functional Programming, vol. 7, no. 05, pp. 549–554, 1997.
[18] H. Abelson and G. J. Sussman, Structure and Interpretation of Computer Programs - 2nd Edition, 2nd ed. The MIT Press, 1996.
[19] G. Hutton and E. Meijer, “Monadic parser combinators,” Journal of Functional Programming, vol. 8, no. 4, pp. 437–444, 1996.
[20] P. Wadler, “Monads for functional programming,” Advanced Functional Programming, pp. 24–52, 1995.
[21] E. Meijer and G. Hutton, “Bananas in space: Extending fold and unfold to exponential types,” in Proceedings of the seventh international conference on Functional programming languages and computer architecture, p. 333, 1995.
[22] P. Wadler, “Monads and composable continuations,” Lisp and Symbolic Computation, vol. 7, no. 1, pp. 39–55, 1994.
[23] G. L. Steele Jr, “Building interpreters by composing monads,” in Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p. 492, 1994.
[24] J. M. Hill and K. Clarke, An introduction to category theory, category theory monads, and their relationship to functional programming. Citeseer, 1994.
[25] P. Jones, L. Simon, and P. Wadler, “Imperative functional programming,” in Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p. 84, 1993.
[26] P. Wadler, “The essence of functional programming,” in Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p. 14, 1992.
[27] D. J. King and P. Wadler, “Combining monads,” Functional Programming, Glasgow, pp. 134–143, 1992.
[28] A. W. Appel, Compiling with Continuations. Cambridge University Press, 1991.
[29] E. Moggi, “Notions of computation and monads,” Information and computation, vol. 93, no. 1, pp. 55–92, 1991.
[30] E. Meijer, M. Fokkinga, and R. Paterson, “Functional programming with bananas, lenses, envelopes and barbed wire,” in Functional Programming Languages and Computer Architecture, pp. 124–144, 1991.
[31] O. Danvy, J. Koslowski, and K. Malmkjær, “Compiling monads,” TechnicalReportCIS-92-3, Kansas State University, Manhattan, Kansas, 1991.
[32] P. Wadler, “Comprehending monads,” in Proceedings of the 1990 ACM conference on LISP and functional programming, pp. 61–78, 1990.
[33] E. Moggi, “An abstract view of programming languages,” 1989.
[34] J. Hughes, “Why functional programming matters,” The computer journal, vol. 32, no. 2, p. 98, 1989.
[35] P. Wadler and R. Bird, “Introduction to functional programming,” pp. 1--14, 1988.
[36] E. Moggi, “Computational lambda-calculus and monads,” 1988.
[37] G. L. Steele Jr and G. J. Sussman, “Lambda: The ultimate imperative,” AIM-353, 1976.
[38] G. L. Steele Jr, “Lambda: The ultimate declarative,” AIM-379, 1976.

My live Q&A with Eric Lippert, Luke Hoban and Mads Torgersen at Tech·Ed 2010, North America

Yesterday I watched the live 3:30 PM: Languages Panel session, with Eric Lippert, Luke Hoban and Mads Torgersen and the niner Charles Torre, through (http://www.msteched.com/), provided by Channel9 live (http://channel9.msdn.com/). This wasn’t just a live panel, but an interactive QnA too, so as me and a friend / colleague of mine (Nikos), watched it, we asked a question through twitter of Channel9 (http://twitter.com/ch9live). The question (both actually) have been presented through the monitor, to the panel and was answered briefly (check screenshots). The following, are food for thought to everyone and anyone who would like to participate in a conversation about Types in C#, F#, Scala, Java, etc, provide clarifications or error corrections in the way I perceived the answers or else :):)

Mads Torgersen seemed pretty sure and his initial reaction was original when answering the question! A bright “No”, from the member of the C# Language, designer group (he was speaking of his main domain of work, C#).

Take LINQ for example, he said. LINQ is hardwired in the compiler, providing of this query pattern of composed Select, Where, From, … etc clauses, that provide a single type of computation, over our data. How can one, express through type system, such compositions? The answer is Higher Kind Types. Mads said, that providing such functionality to the C# programmer, would be pretty confusing. There would be rare cases, that one would like to define higher kind types[1], thus this capability (a concept coming from languages like Haskell btw), is not included in future plans currently.

LINQ construct is in general following the monadic [2] programming model. In contrast, F#, being a functional programming language and giving features like computational expressions for asynchronous programming, would be able to provide such level of abstraction if needed in the future. As I understood from what Luke Hoban said, this is more “easy” in F#, as during the design process, such monadic constructs are already implemented in a general way by the F# language design group, hence, this could be exposed in the future.

The live panel, continued the conversation with very interesting topics, such as Rx, but when the “pure” word came up, I couldn’t resist posting another (and much more impulsive) question, that was answered live very quickly, from the panel.

Luke immediately took action and said that, many people are very active with Haskell inside the MS group, but currently isn’t any movement for incorporating .NET with a pure functional language, due to the incompatible paradigm of current .NET with FP. .NET is a chaos of libraries, doing so many things, providing ways of side effect-“ing” so much, that a pure functional language couldn’t fit in. However ideas from this whole class of functional languages, could migrate in the future, towards F#.

Mads noted something pretty accurate. Purity is also a programming style. This very same concept is very useful as a C# style too. Minimizing side effects, approaches this way of thinking, and we can simulate this in our own way (in a local manner). Mads, also said that this could be the way of .NET library transformation over the years, but not instantly.

I would like to thank the panel, for providing such elaborate answers! Keep up the very good work, providing us such expressive languages!!

[1] Kind is to a type what a type is to a value (I don’t think this is accurate, but it will do the job for now). So, conceptually, we have objects in the bottom. Objects are distinguished by types and types are classified by kinds. Starting again from bottom, objects are known at run time, types must be known at compile time and the kinds are specified by the language itself. Java 5 and C# 2.0 introduced first order parametric polymorphism, thus abstracting over types. The resulting type constructor cannot be further abstracted, however. In a generic way, you can say I want a list of T, where T is int... . So in List<T>, how would it be to abstract over that and specify through a parameter the List too via a Container[T] parameter for example? Thus we could parameterize more (abstract) List<T>, instantiating an M<T, Container> with int and List and getting List<int> or ArrayList<Customer>. So I have the M which takes a type and returns a type. Monads are generalized via this way in Haskell (check Simon Peyton Jones’ words here).

[2] Monad in simple words is a way (strategy), of combining computations to build other computations.

Παρουσίαση .NET και C# στο ΠΜΣ Πληροφοριακά Συστήματα ΟΠΑ – Τεχνολογία Λογισμικού

Παραθέτω το υλικό της σημερινής παρουσίασης για .NET, C# που είδαμε στο μάθημα Τεχνολογίας Λογισμικού (ευχαριστούμε τον καθηγητή Εμ. Γιακουμάκη που την πραγματοποιήσαμε επιτυχώς). Η παρουσίαση που διαδέχτηκε τη δική μου, από τον Μιχάλη Ζερβό, βρίσκεται εδώ. Και οι δύο, βρίσκονται στο e-class του μαθήματος.

Στην παρουσίασή μου, προσπάθησα να δώσω όσες περισσότερες ιδέες μπορούσα (στο σύντομο χρονικό διάστημα της μίας ώρας) αναδεικνύοντας την εκφραστικότητά της και τις δυνατότητες που έχει. Καλύφθηκαν αρκετά θέματα, ξεκινώντας από τις βασικές δομές και εξηγώντας στη συνέχεια μία πληθώρα από άλλες όπως, delegates, anonymous functions, anonymous types, iterators, lambdas, extension methods, LINQ καθώς επίσης τα βασικά από τη λειτουργία του ίδιου του περιβάλλοντος εκτέλεσης και της εσωτερικής οργάνωσης του .NET. H παρουσίαση, είχε στόχο να δώσει πολλές ιδέες και ερεθίσματα, καθώς δύσκολα μία έννοια μπορεί να διατυπωθεί μέσα από μερικά slides σε περιορισμένο χρόνο.

Τα Demos (WPF, F#) που παρουσίασα για τις ανάγκες περιήγησης στο Visual Studio βρίσκονται εδώ, καθώς και η παρουσίαση. Για να κατεβάσετε την Beta 2 του VS Studio 2010 Beta 2 θα ακολουθήσετε τον εν λόγω σύνδεσμο. Τέλος, για την σύντομη αναφορά στην F#, μπορείτε να δείτε μία επεξήγηση (στο ίδιο πρόγραμμα για τους πύργους του Ανόι) στο εξής blogpost.

Enjoy coding!!

Πύργοι του Ανόι σε F#

Θυμάστε πώς είχαμε υλοποιήσει τους πύργους του Ανόι σε C στη σχολή όταν πρωτοπήγαμε; Ορίστε πόσο απλή είναι η έκδοση του σε συναρτησιακό προγραμματισμό (με χρήση της F#).

Κατ’αρχάς μερικές νύξεις στο VS Studio 2010 που έχει ενσωματωμένα templates και debugging tools για αυτή τη νέα γλώσσα. Ανοίγουμε το VS Studio 2010 Beta 2 που μπορούμε να το κατεβάσουμε δωρεάν όσο διαρκεί η φάση Beta και διαλέγουμε να δημιουργήσουμε ένα Console Application σε F#.

Στην συνέχεια κάνουμε paste τον παρακάτω κώδικα (προσέξτε το indentation στον κώδικα καθώς έχει σημασία να είναι σωστά στοιχειοθετημένες οι εντολές. Δεν γίνεται compile αν δεν ακολουθηθούν οι αντίστοιχοι απλοί κανόνες) που ορίζει δύο συναρτήσεις, την move (μετακίνησε από στύλο σε στύλο, στην ουσία απλά κάνει print την κίνηση για να βλέπουμε την αλλαγή της κατάστασης) και την hanoi η οποία υλοποιεί την αναδρομική συνάρτηση. Όποτε δοκιμάζω να μάθω την F#, μου αρέσει να στέλνω ότι γράφω στο interactive environment της. Ότι γράφεται σε αυτό το παράθυρο μοιάζει να περνάει από interpreter, αλλά στην ουσία γίνεται δυναμικά compile on-the-fly βλέποντας την αποτίμηση κάποιας έκφρασης, εκείνη τη στιγμή στο παράθυρο.

let move = printfn "Μετακίνησε δίσκο από %c στο %c" let rec hanoi f x t = function   | 1 -> move f t   | n -> hanoi f t x (n - 1)          move f t          hanoi x f t (n - 1)

Το παραπάνω κομμάτι κώδικα ορίζει μία απλή συνάρτηση και μία αναδρομική.

Μόλις γίνει η μεταφορά του κώδικα στο interactive παράθυρο, μας παρουσιάζονται δύο γραμμές:

val move : (char -> char -> unit)

//Η δήλωση της move που παίρνει δύο παραμέτρους τύπου char 

//Η παραπάνω δήλωση ερμηνεύεται ως εξής λόγω του currying: το move είναι μία συνάρτηση που παίρνει ένα argument και επιστρέφει μία συνάρτηση με τύπο (char->unit).

val hanoi : char -> char -> char -> int –> unit

//Η δήλωση της hanoi που παίρνει τρεις χαρακτήρες και ένας ακέραιο.

//Ομοιοτρόπως και σε αυτή τη δήλωση. To int σε αυτή τη περίπτωση είναι μία επίδραση του keyword function, το οποίο λόγω της ιδιότητάς του δημιουργεί μία έμμεση μεταβλητή.

Η δήλωση unit σημαίνει ότι δεν επιστρέφεται τίποτα από αυτή τη συνάρτηση. Το unit αποτελεί έναν primitive type που δεν περιέχει καμία απολύτως πληροφορία και η μόνη του τιμή είναι το ().

Πάμε στην αναδρομική συνάρτηση. Ξεκινάμε με το keyword let, με το οποίο δηλώνουμε πως ότι θα γράψουμε, θα δεθεί με το όνομα hanoi, γίνεται δηλαδή binding του ονόματος με την έκφραση της συνάρτησης. Στη συνέχεια, με το keyword rec αναφέρουμε πως το binding αυτό μπορεί να αναφερθεί στον εαυτό του ή πιο απλά, ότι έχουμε μία αναδρομική συνάρτηση. Ορίζονται το όνομα και οι μεταβλητές μας (χωρίς να ορίζουμε τύπο-γίνεται infer από την F#). Με την λέξη κλειδί function ανακοινώνουμε ότι έχουμε μία συνάρτηση η οποία μπορεί να αναγνωρίσει πρότυπα πάνω στα ορίσματά της (pattern matching), έτσι η F# καταλαβαίνει ότι στα ορίσματα υπεισέρχεται ακόμα ένας τύπος ακεραίου (o ακέραιος εκείνος που μας έδειξε το interactive window παραπάνω). Τι είναι pattern matching εν συντομία; Pattern matching είναι η δυνατότητα που προσφέρει η δομή function… και η δομή match…with… να εκτιμά το αποτέλεσμα μίας έκφρασης και να συγκρίνει αυτό το αποτέλεσμα με μία σειρά από κανόνες. Στην περίπτωσή μας, οι κανόνες πηγάζουν από την αναδρομική λύση του προβλήματος. Αν παρατηρήσουμε τη μαθηματική λύση και το παραπάνω κώδικα, θα δούμε ότι οι παραπάνω εκφράσεις είναι η μετάφραση της μαθηματικής λύσης αυτούσια από το συλλογισμό μας, στην F#. Παρατηρήστε την αναδρομική λύση του προβλήματος. Έχει τρία βήματα που λένε:

• - Μετέφερε n-1 δίσκους από τον πρώτο στύλο στο δεύτερο (οπότε απομένει ο δίσκος με τον αριθμό n – ο μεγαλύτερος στον πρώτο στύλο)
  - Μετέφερε τον δίσκο n από τον πρώτο στύλο στον τρίτο
  - Μετέφερε n-1 δίσκους από τον δεύτερο στύλο στον τρίτο.
• - Τι γίνεται όταν έχουμε τον δίσκο υπ’ αριθμόν 1 (τον μικρότερο δηλαδή); Μετέφερέ τον στον τρίτο στύλο!

Ακριβώς δηλαδή ότι είναι γραμμένο στο παραπάνω κομμάτι κώδικα!

Εκτελώντας τον κώδικα για διαφoρετικούς ακεραίους, μία για 2 δίσκους και μία για 4 δίσκους, βλέπουμε τη λύση στο interactive window.

Cheers!