CS 421 Lecture 19: Functional Programming in Object-Oriented Languages Announcements Lecture outline Multi-paradigm programming languages Functional programming in OOP Function objects Examples Java C++ Based on slides developed by Dongyun Jin7/16/20091Announcements MP7 has been posted Midterm grades will be up soon Questions about your grade7/16/20092Objectives Multi-Paradigm Programming Language Other paradigms in a Programming Language Functional Programming in OOP Function Object Examples Function Objects in Java Function Objects in C++ Parser Combinators in Java7/16/20093Multi-paradigm PL Programming Languages that support more than one programming paradigm Java Imperative, Generic, Reflective, Object-Oriented C++ Imperative, Generic, Object-Oriented Ocaml Functional, Imperative, Generic, Object-Oriented Why? No one paradigm solves all problems in the easiest or most efficient way.7/16/20094Other paradigms in a PL In a programming language Some paradigms are supported fundamentally Other paradigms can be simulated by using language features If a programming language is Turing-complete, any paradigm can be simulated in the languageparadigm can be simulated in the language Problem Conciseness Efficiency Difficulty7/16/20095Functional programming in OOP Functional Programming No Side Effects Dynamic Memory Allocation Recursion Higher-Order FunctionsLazy EvaluationLazy Evaluation In Object-Oriented Language, Naturally Accomplishable Useful7/16/20096Function object Function Object Also called Functor or Functionoid A programming construct allowing an object to be invoked or called as if it were an ordinary functionIn OcamlIn OO language7/16/20097map (fun x -> x+1) [1;2;3;4]inside of map:(fun x -> x+1) (1)(fun x -> x+1) (2)...List map(IntFun f, List l);inside of map:j = f(i);But f is an object.Class IntFun{….}f.apply(i)Purpose of function objects More Expressiveness Sometimes simpler and more convenient than other approaches High-Order Functions Resilient to Design ChangesWe don’t need to change the interfaceWe don’t need to change the interface Create New Functionality without writing new functions7/16/20098Function objects in Java Function object interface and definitioninterface IntFun {int apply(int x);}class Incr implements IntFun {... // blah blahIn Ocamllet f x = x + 1;;map f A;; Inner class7/16/20099... // blah blah}map(new IntFun {int apply(int x){return x+1;}}, A); In Ocamlmap (fun x -> x+1) A;;Function objects in Java Function interface example 1interface IntFun {int apply(int x);}... //some classes and blahclass Incr implements IntFun {int apply(int x) {return x + 1;}}7/16/200910int[] map(IntFun f, int A[]) {int B[] = new int[A.length];for(int i = 0, i < A.length; i++)B[i] = f.apply(A[i]);return B;}… //some classes and blahint A[] = new int[30];...int C[] = map(new Incr(), A);Function objects in Java Function interface example 2interface IntBinaryPred {boolean apply(int x, int y);}class GT implements IntBinaryPred {booleanapply(intx, inty) {Interface BoolBinaryPred {boolean apply(boolean x, boolean y);}class And implements BoolBinaryPred {booleanapply(booleanx, booleany)7/16/200911booleanapply(intx, inty) {retun x > y;}}booleanapply(booleanx, booleany){return x && y;}}Function objects in Java Inner classinterface IntBinaryPred {boolean apply(int x, int y);}class GT implements IntBinaryPred {booleanapply(intx, inty) {Interface IntBinaryPred {boolean apply(int x, int y);}...CompareArray(7/16/200912booleanapply(intx, inty) {retun x > y;}}...CompareArray(new GT(), A, B);CompareArray(new IntBinaryPred {boolean apply(int x, int y){return x > y;}}, A, B);Function objects in Java Real example – ComparatorList<String> list = Arrays.asList(new String[] {"10", "1", "20", "11", "21", "12"});Collections.sort(list,new Comparator<String>() {7/16/200913new Comparator<String>() {public int compare(String o1, String o2) {return Integer.valueOf(o1).compareTo(Integer.valueOf(o2));}});Function objects in Java Higher-order function objectsinterface IntFun {int apply(int x);}IntFun combine-add(IntFun f, IntFun g) {return new IntFun{7/16/200914return new IntFun{int apply(int x) {return f.apply(x) + g.apply(x);}};}In Ocaml:let combine-add f g = fun x -> (f x) + (g x);;Function objects in Java Higher-order function objectsinterface IntFun {int apply(int x);}interface IntFun2 {int apply(int x, int y);}In Ocaml:let compose2 f g h = fun x -> f(g x, h x)7/16/200915}IntFun compose2 (IntFun2 f, IntFun g, IntFun h) {return new IntFun {int apply(int x) {return f.apply(g.apply(x), h.apply(x));}};}Function objects in C++ Operator overloadingIncr incr = new Incr();a = incr(3);class Incr{public:7/16/200916public:int operator() (int x) {return x + 1;}}Function objects in C++ Operator overloading example 1class IntFun {public:int operator() (int x){// return blah ...}}7/16/200917}template<class IntFun>int* map(IntFun f, int *A, int n) {int *C = new int[n];for(int i = 0; i < n; i++)C[i] = f ( A[i] );return C;}Function objects in C++ Operator overloading example 2class GT {public:bool operator() (int x, int y) {return x > y;}}7/16/200918}class AND {public:bool operator() (bool x, bool y) {return x && y;}}Function objects in C++ Higher-order functors – example 1template<class IntFun>class Combine_Add {public:IntFun f, g;Combine_Add(IntFun f, IntFun g) {this.f= f;7/16/200919this.f= f;this.g = g;}int operator() (int x) {return f(x) + g(x);}}In Ocaml:let combine-add f g = fun x -> (f x) + (g x);;Function objects in C++ Higher-order functors – example 2template<class IntFun>class Funmod {public:IntFun f; int x, y;Funmod(IntFun f, int x, int y) {this.f= f; this.x= x; this.y= y;7/16/200920this.f= f; this.x= x; this.y= y;}int operator() (int z) {if(x == z)return y;elsereturn f(z);}}In Ocaml:let funmod f x y =fun z -> if x = z then y else f z;Parser combinators in Javainterface Parser {ArrayList apply(ArrayList cl);}Parser token(String s) {return new Parser {ArrayList apply(ArrayList cl) {ArrayList cl2;In Ocaml:let token s = fun cl ->if cl = [] then Noneelse if s = hd clthen Some(tl cl)else None;;7/16/200921if (cl == null || cl.size() == 0)return null;if (s.compareTo((String)cl.get(0)) ==0) {cl2 = cl.clone();cl2.remove(0);return cl2;}return null;}}}Parse parserx = token(“x”);let parsex = token
View Full Document