[Lecture Notes]Functional Programming

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

CSci 555: Functional Programming
Spring Semester 2016
Lecture Notes

---

Sections

• Schedule, Lecture Notes, and Examples
• Reference Materials and Other Resources
  

---

Schedule, Lecture Notes, and Examples

• (26 Jan) Examine syllabus and discuss class organization.
  
  
• Discuss programming paradigms
  
  
  
  • (26 Jan) A programming paradigm is "a way of conceptualizing what it means to perform computation, of structuring and organizing how tasks are to be carried out on a computer."
    -- from: Timothy A. Budd. Multiparadigm Programming in Leda, Addison-Wesley, 1995, page 3
    
    
  • (26 Jan) Programming Language Paradigms, section 1.3, pages 5-6, from the instructor's Notes on Functional Programming with Haskell
    
    Note: I use the phrase "programming language paradigms" in this document. More correctly, I should only say "programming paradigms" and differentiate among different styles of programming but not among languages. A language typically supports more than one style although some styles may be more directly supported than others.
    
    Concepts: programming language paradigm, imperative language, declarative language, functional language, relational or logic language; program state, implicit versus explicit state; sequencing versus recursion, execution of commands versus evaluation of expressions, "how" versus "what" to compute.
    
    
  • Peter Van Roy's Programming Paradigms Poster website
    
    • (28 Jan) local pdf of poster pdf
    • (for reference) Programming Paradigms for Dummies: What Every Programmer Should Know
      
    
    
  
  
• Motivate the study of functional programming
  
  
  
  • (28 Jan) Excerpt from Backus' 1977 Turing Award Address, section 1.2, pages 2-4, from the instructor's Notes on Functional Programming with Haskell
    From the 1977 Turing Award Address, John Backus. Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, Communications of the ACM 21.8 (1978): 613-641.
    
    Concepts: von Neumann computer, bottleneck; von Neumann language, world of expressions versus world of statements. Functional programming.
    
    
  • (28 Jan) Reasons for Studying Functional Programming, section 1.4, pages 6-10, from the instructor's Notes on Functional Programming with Haskell
    
    Concepts: referential transparency, abstraction, higher-order function, first-class function, eager versus lazy evaluation, separation of data from control
    
    
  • (2 Feb) Objections Raised to Functional Languages, section 1.5, pages 11-12, from the instructor's Notes on Functional Programming with Haskell
    
  
  
• Introduce Scala to Java programmers
  
  
  
  • (2-9 Feb) Notes on Scala for Java Programmers [HTML] [PDF]
    Michel Schniz and Philipp Haller, A Scala Tutorial for Java Programmers
    
    Concepts: basic syntax and semantics of Scala from the perspective of a Java programmer; includes singleton objects, val and var identifiers, type inference, infix method calls, higher-order and first-class functions, anonymous functions, argumentless methods, classes, overriding, case classes, pattern matching, traits, generics, etc.
    
    
  • (4 Feb, for Assignment #1) Arithmetic expression tree program skeletons
    
    
    
    Functional versions
    • Scala Recursive Functions with Case Classes (ExprCase.scala)
    • (for reference) Lua Recursive Functions with Record Representation (exprRecFuncRecord.lua)
    • (for reference) Lua Recursive Functions with List Representation (exprRecFuncList2.lua)
    • (for reference) Lua Evaluation Function Table with List Representation (exprEvalTable2.lua)]
      
      Object-oriented versions
    • Scala Traditional Object-Oriented (ExprObj.scala)
    • (for reference) Lua Prototype Object-Based (exprObjBased.lua)
    • (for reference) Lua Object-Oriented with Inheritance (exprObjInherit.lua)
      
    
    
  • (9 Feb) Scala Class Hierarchy
    
    Concepts: Unification of Java/Scala primitive value types under type AnyVal, Java/Scala reference types under AnyRef, and both under Any.
    
    
  • (for reference) A Tour of Scala
    
    
  • (for reference) Martin Odersky. Scala by Example, June 11, 2014.
    Original at http://www.scala-lang.org (Documentation, Older Documentation, Scala By Example).
    
    
  
  
• Explore recursion in Scala
  
  
  
  • (11 Feb) Recursion Concepts and Terminology: Scala Version [HTML] [PDF] [Elixir] [Lua]
    
    Concepts: recursion, linear and nonlinear recursion, tree recursion, backward and forward recursion, tail recursion, tail recursion optimization (also know as tail call elimination or proper tail calls), auxiliary functions, accumulating parameter (i.e. accumulator), nested functions, time and space complexity of recursive functions, termination arguments for recursive functions, preconditions and postconditions, Scala function definitions.
    
    
  • (for reference) Tail call (on Wikipedia)
    
    
  
  
• Examine functions adapted from SICP
  
  
  
  • Background reading: Chapter 1 of the classic textbook SICP -- Harold Abelson and Gerald J. Sussman with Julie Sussman. Structure and Interpretation of Computer Programs, Second Edition, MIT Press, 1996:
    [book site at MIT Press] [HTML book] [SICP ebook site] [local copy of source code]
    
    
  • (9-11 Feb) First-order functions in Scala
    
    • (9 Feb) Square root (Newton's Method) version 1 with all public functions
      [Scala source] [listing]
    • (9 Feb) Square root (Newton's Method) version 2 with nested function definitions
      [Scala source] [listing]
    • (11 Feb) Factorial -- discussed in Recursion Concepts notes above
      [Scala source] [listing]
    • (11 Feb) Fibonacci -- discussed in Recursion Concepts notes above
      [Scala source] [listing]
    • (11 Feb) Exponentiation -- discussed in Recursion Concepts notes above
      [Scala source] [listing]
    • (11 Feb) Greatest common divisor
      [Scala source] [listing]
      
    
    Concepts: Reinforces the concepts noted above for the "Notes on Scala for Java Programmers" and the notes on "Recursion Concepts and Terminology." Scala object as module, appropriate use of type inference and explicit typing of public features.
  • (11 Feb) Higher-order functions in Scala
    
    • Summation (takes function arguments)
      [Scala source] [listing]
    • Derivative (returns function result)
      [Scala source] [listing]
      
    
    Definition: A higher-order function is a function that takes other functions as input and/or returns a function as its output value.
    
    Related definition: A first-class function is a function that is a first-class value in the language. It can be stored in a variable or some other data structure, passed to a function, or returned by a function.
    
    Concepts: Higher order functions allow us to capture the common aspects of a computational pattern in the fixed part of a function and pass in the variable aspects as functional arguments.
    
    
  • (for reference) Other versions
    
    • Elixir versions from Spring 2015
      [Square root] [Factorial] [Fibonacci] [Exponentiation] [Greatest common divisor] [Summation] [Derivative]
    • Lua versions from Fall 2013
      [Square root] [Factorial] [Fibonacci] [Exponentiation] [Greatest common divisor] [Summation] [Derivative]
      
  
  
• Study functional data structures
  
  
  
  
  • Background reading: "Functional Data Structures," Chapter 3, Paul Chiusano and Runar Bjarnason, Functional Programming in Scala
    
    
  • (16-18 Feb, 25 Feb, 1-3 Mar) Functional data structures lecture notes to accompany Chapter 3 (primarily on the List data type)
    [source]
    
    Concepts: referential transparency, side effect, immutable; algebraic data type, composite type, sum type (tagged, disjoint union, variant), product type (tuple, record), enumerated type, algebraic data type versus abstract data type, syntax, semantics; list, head, tail, constructor, sealed, case class, case object, distinction between case and regular objects, singleton object; polymorphism, ad hoc polymorphism, overloading, subtyping (subtype or inclusion polymorphism), parametric polymorphism (generics), type class, early versus late binding; variance, covariant, contravariant, invariant (nonvariant), variance annotation; companion object; form of the data guides the form of the algorithm, following types to implementations, pattern matching; associativity, identity element, monoid, zero element; variadic functions, apply method in companion object; data sharing, persistent data structure; when to throw exceptions, when not; backward recursion, tail recursion, accumulating parameter, auxiliary function; higher-order function, anonymous function (function literal), underscore notation in anonymous functions; fold functions, map function, filter function, flatMap function; local mutation; type inference, currying, partial application, upper and lower type bounds, view bounds; insertion sort, merge sort, total order pattern of computation, generalizing function definition; stack overflow error; method chaining, train wreck.
    
    
  • (23 Feb) No class because of instructor illness
    

本帖隐藏的内容

http://www.cs.olemiss.edu/~hcc/csci555/notes/555lectureNotes.html

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Programming Functional function Program Lecture

1. /* Square Root by Newton's Method -- Version 1
   
2.    Functional Programming Example
   
3.    H. Conrad Cunningham, Professor, Computer and Information Science
   
4.    University of Mississippi
   
5. 
   
6.    Developed for CSci 555, Functional Programming, Spring 2016
   
7. 
   
8. 1234567890123456789012345678901234567890123456789012345678901234567890
   
9. 
   
10. 2016-02-10: Developed from 2015 Elixir version
    
11. 
    
12. Function sqrt computes the square root of its argument x using
    
13. Newton's method.  
    
14. 
    
15. I adapted this square root module from an Elixir version, which was,
    
16. in turn, adapted from a Lua version, which was, in turn, adapted from
    
17. the Scheme code in section 1.1.7 of Abelson and Sussman's Structure
    
18. and Interpretation of Computer Programs (SICP) textbook. I changed the
    
19. function names to better match the Scala naming convention.
    
20. 
    
21. I have only tested this code minimally.
    
22. 
    
23. Scala and functional programming highlights:
    
24. - Uses object to define a module
    
25. - Uses type inference as much as possible (But I suggest it is
    
26.   better to give return types for public functions.)
    
27. - Requires return type for sqrtIter because it is recursive
    
28. - Makes all functions visible.  Should hide all but sqrt.
    
29. - Uses tail recursion
    
30. - Calls Math.abs.
    
31. 
    
32. */
    
33. 
    
34. object Sqrt {
    
35. 
    
36.   def sqrt(x: Double) = sqrtIter(1.0, x)
    
37. 
    
38.   // Tail recursive auxiliary function
    
39.   def sqrtIter(guess: Double, x: Double) : Double =
    
40.     if (isGoodEnough(guess,x))
    
41.       guess
    
42.     else
    
43.       sqrtIter(improve(guess,x),x)
    
44. 
    
45.   def isGoodEnough(guess: Double, x: Double) =
    
46.     Math.abs(square(guess)- x)< 0.001
    
47. 
    
48.   def square(x: Double) = x * x
    
49. 
    
50.   def improve(guess: Double, x: Double) = average(guess,x/guess)
    
51. 
    
52.   def average(x: Double, y: Double) = (x + y) / 2
    
53. 
    
54.   // Should implement extensive tesing externally
    
55.   def main(args: Array[String]) {
    
56.     println("square root of 9 is " + sqrt(9.0))
    
57.   }
    
58. 
    
59. }

复制代码

1. /* Square Root by Newton's Method -- Version 2
   
2.    Functional Programming Example
   
3.    H. Conrad Cunningham, Professor Computer and Information Science
   
4.    University of Mississippi
   
5. 
   
6.    Developed for CSci 555, Functional Programming, Spring 2016
   
7. 
   
8. 1234567890123456789012345678901234567890123456789012345678901234567890
   
9. 
   
10. 2016-02-10: Developed from 2015 Elixir version
    
11. 
    
12. Function sqrt computes the square root of its argument x using
    
13. Newton's method.  
    
14. 
    
15. I adapted this square root module from an Elixir version, which was,
    
16. in turn, adapted from a Lua version, which was, in turn, adapted from
    
17. the Scheme code in section 1.1.7 of Abelson and Sussman's Structure
    
18. and Interpretation of Computer Programs (SICP) textbook. I changed the
    
19. function names to better match the Scala naming convention.
    
20. 
    
21. I have only tested this code minimally.
    
22. 
    
23. Scala and functional programming highlights, version 2 relative to 1:
    
24. - Nests all other functions inside sqrt, hiding all but sqrt
    
25. - Returns last expression's value from sqrt
    
26. - Gives explicit return type for public function sqrt
    
27. - Uses type inference where possible for other return values
    
28. 
    
29. */
    
30. 
    
31. object Sqrt {
    
32. 
    
33.   def sqrt(x: Double): Double = {
    
34. 
    
35.     // Tail recursive auxiliary function
    
36.     def sqrtIter(guess: Double, x: Double) : Double =
    
37.       if (isGoodEnough(guess,x))
    
38.         guess
    
39.       else
    
40.         sqrtIter(improve(guess,x),x)
    
41. 
    
42.     def isGoodEnough(guess: Double, x: Double) =
    
43.       Math.abs(square(guess)- x) < 0.001
    
44. 
    
45.     def square(x: Double) = x * x
    
46. 
    
47.     def average(x: Double, y: Double) = (x + y) / 2
    
48. 
    
49.     def improve(guess: Double, x: Double) = average(guess,x/guess)
    
50. 
    
51.     sqrtIter(1.0, x)
    
52.   }
    
53. 
    
54.   // Should implement extensive tesing externally
    
55.   def main(args: Array[String]) {
    
56.     println("square root of 9 is " + sqrt(9.0))
    
57.   }
    
58. 
    
59. }

复制代码