Functional MiniJava, Calling variationsWhen to do assignmentsWhy have a “functional” languageDo we need functions returning functions?Contrast Translate to AddthreeChanges to MJ to make it “functional” section 15.1Lexical changes to MJ to make it “functional”Grammar changes to MJ to make it “functional”What’s this change to CallExp?Type Check changes to MJ to make it “functional”Interpreter Changes to MJ to make it “functional”Slide 12Example… of upward functional arg (return)What is “pure functional” ?What is “pure functional” output like?What is “pure functional” input like?What if we wanted to add this to MJ?Remind me again why we would do this?Slide 19Other issues of Chapter 15Call by name (Important on CS GRE)One implementation [equivalent, easier for humans to reason about]: copy over the body..Lazy vs StrictLazy evaluationA thought: should cons evaluate its args? (Should it be by-need? Or lazy?)Call by value, copy-in/out, etcCall by reference in FORTRANMJ function callsProf. Fateman CS 164 Lecture 18 1Functional MiniJava, Calling variationsLecture 18Prof. Fateman CS 164 Lecture 18 2When to do assignmentsDID YOU START ON ASSIGNMENT 6 YET?Prof. Fateman CS 164 Lecture 18 3Why have a “functional” language•Silly examples from Scheme–(define (addn n)(lambda(x)(+ x n))) ;returns funct.–(define addthree (addn 3))•Less silly examples: encapsulate state, e.g. bank account balance in CS61a examples•Ways to accomplish similar results via Java “privacy” of variables or methods•Motivation for first-class functions-–Eliminate need for other mechanisms–Unifies concepts of functions and dataProf. Fateman CS 164 Lecture 18 4Do we need functions returning functions?•Less silly examples: a translator that returns an answer as a function:•(translate "x+sin(x)" ) which might return (lambda(x)(+ x (sin x)); •(defdiff f(x) )(+ x (sin x))•; could return (f x) and derivative e.g. 1+cos(x).•; or could return a (lambda (…) …) which could be compiled and called later (lambda (g0) ;; function generated automatically (let ((t4 0) (f3 0) (t2 1) (f1 g0)) (setf f3 (sin g0)) (setf t4 (cos g0)) (setf t2 (+ t4 t2)) (setf f1 (+ f3 f1)) (values f1 t2)))Prof. Fateman CS 164 Lecture 18 5Contrast Translate to Addthree•Translate takes expressions, perhaps strings, and return expressions. Since expressions are also programs potentially everything is happy•Functions are, however, more than expressions in that they also have environments… as in the addthree, where n is bound to 3 in the environment.Prof. Fateman CS 164 Lecture 18 6 Changes to MJ to make it “functional” section 15.1How will this work? Here’s an example type foo= (int,String) -> int[] //assume class String exists type bar=(int->String, int) -> int->intThese say that a variable F of type foo may be assigned a value which is a function which takes args that are int, String and returns an array (how long??) of ints.And that a variable B of of type bar may be assigned a function which takes two args, one of which is a function int->String, and the other an int. and returns another function of type int -> int.Prof. Fateman CS 164 Lecture 18 7 Lexical changes to MJ to make it “functional”Lexical changes are simple. Add one keyword and one operatortokens for MJ -> typeProf. Fateman CS 164 Lecture 18 8Grammar changes to MJ to make it “functional”New grammar rules for type declaration ClassDecl type id = ty;ty ! ty -> ty ty ! (ty {,ty}) -> ty ty ! () -> tyAnd for CallExpNew grammar rules for CallExp exp ! exp (exp {,exp}) ;actually unlikely to be LALR(1)Prof. Fateman CS 164 Lecture 18 9What’s this change to CallExp? Must allow the use of an expression like F(x) in the place we previously expected only a name of a function/method. That is, the expression F(x) may evaluate to a function g, in which case one must call g. We now allow a call like Add(3)(4) Where Add(3) perhaps returns a function that adds three to its argument.Prof. Fateman CS 164 Lecture 18 10Type Check changes to MJ to make it “functional”New typechecking for AST FunTy Compare the signatures for 2 functions carefully. Deciding about structure vs name equivalence again.(personally, I think this would be a delicate business: to match type bar=(int->string,int) -> int->int)Prof. Fateman CS 164 Lecture 18 11Interpreter Changes to MJ to make it “functional”In a traditional Scheme environment, no change!The environments persist until the Lisp GC removes them. Lists of bindings can look likethis.env1env2Prof. Fateman CS 164 Lecture 18 12Interpreter Changes to MJ to make it “functional”A stack interpreter cannot build such a tree. Its lexical environments persist only while within lexical scope. We need to preserve until function, returned upward, is called. Here env2 clobbers env1.env1env2Prof. Fateman CS 164 Lecture 18 13Example… of upward functional arg (return)New function here..Prof. Fateman CS 164 Lecture 18 14What is “pure functional” ?Equational reasoning about programs requires that (say) f(3) always is the same. Prohibits “side effects” forbidding f from doing assignment, output, or input.How to do this? Assignment is easy: don’t allow it. Just allow initial values to be set. Functions can bind new parameters on call. Just not reset anything.Prof. Fateman CS 164 Lecture 18 15What is “pure functional” output like?How to get around the output restriction. It is easily to write it down in Lisp: Conceptually change this: ;main_prog …. (print xyz); do_more_stuff; maybe print other stuff…. return_from_main; ;;by converting print to (cons xyz (rest of program…)) ;; any prints in “do_more_stuff” will also be changed to conses… (print (cons xyz (cons (do_more_stuff) …. (return_from_main )…)…so all the output is stacked up until the program finishesProf. Fateman CS 164 Lecture 18 16What is “pure functional” input like?Oh, MJ has no input.. But if it DID have input.. Change : ;main_prog …. (let ((x (read *std-io*)) ;; remember, no assignment, only bindings (f x) ; use x..to (let ((x 12345)) ; whatever it would have read! (f x) or just(f 12345)Any function like read must, under the restrictions of pure functional programming, always produce the same thing. That’s what happens here.Prof. Fateman CS 164 Lecture 18 17What if we wanted to add this to
View Full Document
Unlocking...