UT Dallas CS 4337 - #Sebesta pl10e ch15 functional prog (71 pages)

Previewing pages 1, 2, 3, 4, 5, 33, 34, 35, 36, 67, 68, 69, 70, 71 of 71 page document View the full content.
View Full Document

#Sebesta pl10e ch15 functional prog



Previewing pages 1, 2, 3, 4, 5, 33, 34, 35, 36, 67, 68, 69, 70, 71 of actual document.

View the full content.
View Full Document
View Full Document

#Sebesta pl10e ch15 functional prog

32 views


Pages:
71
School:
University of Texas at Dallas
Course:
Cs 4337 - Organization of Programming Languages
Unformatted text preview:

Chapter 15 Functional Programming Languages Chapter 15 Topics Introduction Mathematical Functions Fundamentals of Functional Programming Languages The First Functional Programming Language LISP Introduction to Scheme Common LISP ML Haskell F Support for Functional Programming in Primarily Imperative Languages Comparison of Functional and Imperative Languages Copyright 2012 Addison Wesley All rights reserved 1 2 Introduction The design of the imperative languages is based directly on the von Neumann architecture Efficiency is the primary concern rather than the suitability of the language for software development The design of the functional languages is based on mathematical functions A solid theoretical basis that is also closer to the user but relatively unconcerned with the architecture of the machines on which programs will run Copyright 2012 Addison Wesley All rights reserved 1 3 Mathematical Functions A mathematical function is a mapping of members of one set called the domain set to another set called the range set A lambda expression specifies the parameter s and the mapping of a function in the following form x x x x for the function cube x x x x Copyright 2012 Addison Wesley All rights reserved 1 4 Lambda Expressions Lambda expressions describe nameless functions Lambda expressions are applied to parameter s by placing the parameter s after the expression e g x x x x 2 which evaluates to 8 Copyright 2012 Addison Wesley All rights reserved 1 5 Functional Forms A higher order function or functional form is one that either takes functions as parameters or yields a function as its result or both Copyright 2012 Addison Wesley All rights reserved 1 6 Function Composition A functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second Form h f g which means h x f g x For f x x 2 and g x 3 x h f g yields 3 x 2 Copyright 2012 Addison Wesley All rights reserved 1 7 Apply to all A functional form that takes a single function as a parameter and yields a list of values obtained by applying the given function to each element of a list of parameters Form For h x x x h 2 3 4 yields 4 9 16 Copyright 2012 Addison Wesley All rights reserved 1 8 Fundamentals of Functional Programming Languages The objective of the design of a FPL is to mimic mathematical functions to the greatest extent possible The basic process of computation is fundamentally different in a FPL than in an imperative language In an imperative language operations are done and the results are stored in variables for later use Management of variables is a constant concern and source of complexity for imperative programming In an FPL variables are not necessary as is the case in mathematics Referential Transparency In an FPL the evaluation of a function always produces the same result given the same parameters Copyright 2012 Addison Wesley All rights reserved 1 9 LISP Data Types and Structures Data object types originally only atoms and lists List form parenthesized collections of sublists and or atoms e g A B C D E Originally LISP was a typeless language LISP lists are stored internally as singlelinked lists Copyright 2012 Addison Wesley All rights reserved 1 10 LISP Interpretation Lambda notation is used to specify functions and function definitions Function applications and data have the same form e g If the list A B C is interpreted as data it is a simple list of three atoms A B and C If it is interpreted as a function application it means that the function named A is applied to the two parameters B and C The first LISP interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation Copyright 2012 Addison Wesley All rights reserved 1 11 Origins of Scheme A mid 1970s dialect of LISP designed to be a cleaner more modern and simpler version than the contemporary dialects of LISP Uses only static scoping Functions are first class entities They can be the values of expressions and elements of lists They can be assigned to variables passed as parameters and returned from functions Copyright 2012 Addison Wesley All rights reserved 1 12 The Scheme Interpreter In interactive mode the Scheme interpreter is an infinite read evaluateprint loop REPL This form of interpreter is also used by Python and Ruby Expressions are interpreted by the function EVAL Literals evaluate to themselves Copyright 2012 Addison Wesley All rights reserved 1 13 Primitive Function Evaluation Parameters are evaluated in no particular order The values of the parameters are substituted into the function body The function body is evaluated The value of the last expression in the body is the value of the function Copyright 2012 Addison Wesley All rights reserved 1 14 Primitive Functions Expressions LAMBDA Primitive Arithmetic Functions ABS SQRT REMAINDER MIN MAX e g 5 2 yields 7 Lambda Expressions Form is based on notation e g LAMBDA x x x x is called a bound variable Lambda expressions can be applied to parameters e g LAMBDA x x x 7 LAMBDA expressions can have any number of parameters LAMBDA a b x a x x b x Copyright 2012 Addison Wesley All rights reserved 1 15 Special Form Function DEFINE DEFINE Two forms 1 To bind a symbol to an expression e g DEFINE pi 3 141593 Example use DEFINE two pi 2 pi These symbols are not variables they are like the names bound by Java s final declarations 2 To bind names to lambda expressions LAMBDA is implicit e g DEFINE square x x x Example use square 5 The evaluation process for DEFINE is different The first parameter is never evaluated The second parameter is evaluated and bound to the first parameter Copyright 2012 Addison Wesley All rights reserved 1 16 Output Functions Usually not needed because the interpreter always displays the result of a function evaluated at the top level not nested Scheme has PRINTF which is similar to the printf function of C Note explicit input and output are not part of the pure functional programming model because input operations change the state of the program and output operations are side effects Copyright 2012 Addison Wesley All rights reserved 1 17 Numeric Predicate Functions or t is true and F or f is false sometimes is used for false EVEN ODD ZERO NEGATIVE T The NOT function inverts the logic of a Boolean expression Copyright 2012 Addison Wesley All rights reserved 1 18 Control Flow Selection the special form IF IF predicate then exp


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view #Sebesta pl10e ch15 functional prog and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view #Sebesta pl10e ch15 functional prog and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?