Functional Programming in Lisp
• LanguagedesignedbyJohnMcCarthybetween1956- 1959 at MIT for applications related to artificial intelligence
– one of the oldest languages still in use
• LISP=LIStProcessor
Copyright By PowCoder代写 加微信 powcoder
• Derivedfrom𝝀𝝀-calculus.
– 𝝀𝝀-calculus allows functions to be the values of an expression
• Manydialects
– Lisp 1.5 (1960), Scheme (1975), Common Lisp (1985)
,PLT Scheme (Racket) (1995) …
• Richlanguage:functional,symbolic.
• Syntaxandsemanticsaresimpleanduniform
Creation of Lisp
• 1960:McCarthypublishedhispaperonLisp
• Lisp/Schemehasafewsimpleoperatorsandarich notation for functions.
– This is combined with simple data structures
• Asaresultwehaveafullandexpressiveprogramming language
Nine Key Concepts
1. Conditions(if-then-else) 2. Functionsasdatatypes 3. Recursions
4. Variablesaspointers
5. Automaticgarbagecollection
6. Aprogramisanexpression(notaseriesofstatements) 7. Symbolsoratoms
8. Listsandtrees
9. Completelanguageavailableatalltimes(read-eval-print)
Pure Functional Programming
• Aprogramcorrespondstoafunctioncall • Afunctionisacompositionoffunctions • Functionsarenon-causal
– Depend only on the parameters passed • Novariables,noassignments
• Noloops,nocontrolstatement
– Beyond the if-then-else function
Functional Programming in Practise
• Someadditionstopurefunctionalprogramming – Local definition of certain values
– Assignments (lexically scoped variables)
– Use an execution sequence (in order to break up the program).
Functional Programming in Scheme
• SchemeisLISPdialectdesignedatMITin1975,mainly for education
• Initiallysmall
– But it is now a complete language.
• StandardizedbyANSI/IEEE
– Language continues to evolve
• Commonlyusedasinterpretedlanguage
– But may also be compiled to be executed efficiently.
Functional programming and Racket
• DevelopedbyM.Felleisenin1995
– Originally called PLT
– Goal: create a pedagogical-oriented programming environment
– e.g. integration of simple graphic elements • 2010PLTbecomesRacket
– and his programming tool becomes Dr Racket • It’samulti-paradigmlanguage
– But belonging to the Lisp family
Application Area of Functional Programming
• Applicationsofsymboliccomputation,i.e.,non-numerical applications
– Artificial intelligence (expert systems, natural language interfaces, …)
– Automated reasoning (theorem proving, proofs of programs … )
– Symbolic Computation
• Today,functionalprogrammingiseverywhere
– Python lambda, map, filter, reduce, list comprehension etc.
– Javascript function expressions, binding, currying, partials
– Also C++ and Go have lambdas, higher order functions etc.
– Many other languages …
Basic Concepts
• List is the fundamental data structure
• Atom: a number, a character string or a symbol.
• All data types are equal
• Expression: an atom or a list
• List: a series of expressions in parentheses
(+ (sqrt 3) 6)
• Including the empty list, () Nile, both list and atom
• A function is a first-class data object that can be created, assigned to variables, passed as a parameter or returned as a value.
̀re – uOttawa
Evaluation rules
• Constants are evaluated for what they are.
• Identifiers are evaluated at the value commonly assigned
• Lists are evaluated by first evaluating the first expression that composes them;
• the value of this expression must be a function
• The arguments of this function are the values obtained by the evaluation
of the expressions contained in the rest of the list
(+ (sqrt 3) 6)
̀re – uOttawa
Evaluations of Expressions
• Constantsareevaluatedtowhattheyare. – numbers
> “Hello” => “Hello”
• Identifiersevaluatetothevaluethatisattributedtothem. > * => #
– first evaluating the head, i.e., the first expression; the value of this expression must be a function
– The arguments of this function are the values obtained by evaluating the expressions contained in the rest of the list
A First Scheme Session
• Initssimplestform,aSchemeinterpretersessionuses the interactive READ-EVAL-PRINT programming model (REPL)
• Example:
7> (+ 3 4)
• Intheexample,wehavealist.
– The first entry is the function +
– The rest of the list are constant expressions 3 and 4.
• Thelistisreadas(+34),evaluatedandthenthe
result 7 printed.
A First Scheme Session
• Inthesimplestform,shemeusesthemodelof programming interactive READ-EVAL-PRINT
> (+ 3 4) 7
Scheme Interpreter
• ClassicalMITSchemeinterpreter
– http://www.gnu.org/software/mit-scheme/
– While available, not well supported under windows
– Another LISP dialect
• DrRacket
– http://racket-lang.org/
– Convenient and full-fledged programming environment to run LISP dialects
The DrRacket environment
• designed for education, powerful enough for “real” use • sequence of language levels keyed to textbook
• includes good development tools
• two windows: Interactions and Definitions
• Interactions window: a read-evaluate-print loop (REPL)
Few Remarks on the IDE
You must select a language in top of window.
Program editor
Bottom window is for running programs
This is the classic REPL Buffer
Evaluation of Expressions
• Theprefixnotationisusedinexpressions – Instead of inline operators as in 3+4*5 – Oneneedstowrite (+3(*45))
• Toevaluateanexpression,allsub-expressionsmustbe evaluated first.
– The evaluation follows normal order evaluation
– Brackets determine the order and are not optional
(+ 3 (* 4 5)) (+ 3 20)
Converting an expression into Racket
As before, we put parentheses around the function and arguments. 3 − 2 becomes (− 3 2)
3 − 2 + 4/5 becomes (+ (− 3 2) (/ 4 5))
(6 −4)(3 + 2) becomes (∗(−6 4) (+ 3 2))
In Racket, parentheses are used to associate arguments with functions, and are no longer needed for precedence.
Extra parentheses are harmless in mathematical expressions, but they are harmful in Racket. Only use parentheses when necessary.
Racket expressions causing errors
What is wrong with each of the following?
• (* (5) 3) • (+ (* 2 4) •(5 * 14)
• (* + 3 5 2) •(/ 25 0)
Representation of numbers
• Real numbers may be represented accurately or inaccurately
• The exact representation uses a representation by rational numbers, thus:
> (/ 50 6)
8 1/3 ; ie 8 and 1/3
• Most math operations return exact numbers
> Except those likely to return irrational numbers • eg sqrt
̀re – uOttawa
Representation of numbers
A number written with a period is an incorrect number • The IEEE754 representation is then adopted
> (/ 50.0 6)
8.333333333333334
The conversion from inaccurate to exact is written: > (inexact> exact (/ 50.0 6))
8 187649984473771/562949953421312
Function truncate will return the integer that precedes
> (truncate (/ 10 3)) 3
> (truncate 3.7) 3.0
̀re – uOttawa
Function applications in Racket
In a Racket function application, parentheses are put around the function name and the arguments.
To translate from mathematics to Racket
• move ‘(’ to before the name of the function, and
• replace each comma with a space. g(3,1) becomes (g 3 1)
g(f (2),g(3,1)) becomes (g (f 2) (g 3 1))
There is one set of parentheses for each function application.
Built-in functions
Racket has many built-in functions, such as familiar functions from mathematics, other functions that consume numbers, and also functions that consume other types of data.
You can find the quotient of two integers using quotient and the remainder using remainder.
(quotient 75 7) (remainder 75 7)
Defining functions in Racket
Ourdefinitionsf(x) = x2 andg(x,y) = x−ybecome (define (f x) (∗ x x))
(define (g x y) (− x y))
define is a special form; it looks like a Racket function, but not all of
its arguments are evaluated.
It binds a name to an expression (which uses the parameters that follow the name).
A function definition consists of
• a name for the function,
• a list of parameters, and
• a single “body” expression.
The body expression typically uses the parameters together with other built-in and user-defined functions.
To give names to the function and parameters, we use identifiers.
Syntax rule: an identifier starts with a letter, and can include letters, numbers, hyphens, underscores, and a few other punctuation marks.
It cannot contain spaces or any of ( ) , { } [ ] ‘ ’ “ ”. Syntax rule: function definition is of the form
(define (id1 . . . idk) exp), where exp is an expression and each id is an identifier.
We can fix the syntax rule for a function application to say that a function name is a built-in name or an identifier.
The rule doesn’t distinguish id1 (the function name) from the rest; that is semantics.
Constants in Racket
The definitions k = 3 and p = k2 become (define k 3)
(define p (∗ k k))
The first definition binds the identifier k to the value 3.
In the second definition, the expression (∗ k k) is first evaluated to give 9, and then p is bound to that value.
Syntax rule: a constant definition is of the form (define id exp).
definition in Racket
definition = |
(define (name variable variable …) expr)
(define name expr)
(define name (lambda (variable variable …) expr))
(define-struct name (name …)) (name expr expr …)
https://docs.racket-lang.org/htdp-langs/beginner.html
Special Syntactic Forms
• Someexpressionsdonotobeythenormalorder evaluation, these expressions are said to have a special syntactic form.
• Theevaluationoftheirargumentsisdeferreduntilthe required values are known.
• Themainspecialsyntacticformsare: – if statement
• conditional branching – creation of local scope
– quotation
Special Syntactic Forms:
The Alternative (if statement)
(if (= x 0) “Infinity” (/ 1 x))
• Theexpressionfollowingtheifisevaluatedfirst. • Ifitsvalueistrue(#t)then
– the second argument is evaluated
– its value is returned without evaluating the third argument
• ifitsvalueisfalse(#f)then
– the third argument is evaluated and returned
types of comparisons
A comparison is a function that consumes two numbers and produces a Boolean value.
(> x y) (<= x y) (>= x y)
We can also compare strings using string=?, string= (string-length str) 3)
(string=? “cat” (substring str 0 3)))
(or (= x 0) (> (/ 100 x) 5))
Special Syntactic Forms: 2. Conditional Branching
• Conditionalexpressionsaresimilartoifbutmorethan two branches can be specified
(cond ((< x xmin) xmin)
((> x xmax) xmax)
• Thecondexpressionisfollowedbyaseriesoflists
composed of two expressions.
– If the first of the two expressions in one of these lists evaluates to #t then the value of the second expression is returned
– If the first expression evaluates to false, then evaluation proceeds to the next list.
– If no lists evaluates to #t then nil is returned.
Predicates
A predicate is a function that produces a Boolean result: true if data is of a particular form, and false otherwise.
Built-in predicates: e.g. even?, negative?, zero?, string? User-defined:
(define (between? low high nbr) (and (< low nbr) (< nbr high)))
(define (can-drink? age) (>= age 19))
Conditional expressions
Sometimes expressions should take different values under different conditions.
• These use the special form cond.
• Each argument of cond is a question/answer pair.
• The question is a Boolean expression.
• The answer is a possible value of the conditional expression.
Example: taking the absolute value of x.
−x whenx<0 x when x ≥ 0
In Racket, we can compute |x|with the expression
(cond [(< x 0)
(− x)] [(>= x 0) x])
• square brackets used by convention, for readability
• square brackets and parentheses are equivalent (must be
nested properly)
• abs is a built-in Racket function
• cond is a special form because it doesn’t fully evaluate its arguments.
The general form of a conditional
expression is
[question1 answer1]
[question2 answer2] …
[questionk answerk])
where questionk could be else.
The questions are evaluated in order; as soon as one evaluates to
true, the corresponding answer is evaluated and becomes the value of the whole expression.
• The questions are evaluated in top-to-bottom order.
• As soon as one question is found that evaluates to true, no
further questions are evaluated.
• Only one answer is ever evaluated, that is
– the one associated with the first question that evaluates to
– the one associated with the else if that is present and reached (all other questions evaluate to false).
(define n 5)
(cond [(even? n) “even”] [(odd? n) “odd”])
Example: Conditional and Top-level Define
Definition of the function showIt taking an argument pts and evaluating a conditional
(define (showIt pts)
(cond ((or (<= pts 3) (>= pts 65)) 0)
((<= 4 pts 6) 0.5) ((<= 7 pts 12) 1.0) ((<= 13 pts 15) 1.5) ((<= 16 pts 18) 1.8) (else 2.0)))
(showIt 25)
Special Syntactic Forms: 3. Creating Local Scope
• LetExpressions
(let ((a 3) (b 4)) (* a b))
– The first argument of a let expression is a list of links created between an identifier and a value
– These links are only valid for the evaluation of the following expression(s)
• There can be several to allow the execution of a sequence.
(let ((a 3) (b 4)) (* a b) (+ a b)) => 12 7
Special Syntactic Forms: 4. Quotations
• Thequotefunctionensuresthatanargumentlistisnot evaluated.
(quote (1 2 3)) => (1 2 3)
– But the list is rather returned as is.
– Quotation is necessary here, otherwise the first
expression of a list needs to evaluate to a function. ‘(+34) => (+34)
(+ 3 4)=>7
– The quote function can simply written with a ‘ :
=> (1 2 3)
Quotation Example
(let ((a ‘(1 2 3)) (b ‘(3 4 5))) (cons a b))
equates to
(cons ‘(1 2 3) ‘(3 4 5)) ⇒ ((1 2 3) 3 4 5)
– Thefunctionconsisthedotoperatorforlists,i.e.,it puts the first expression as the head of the second list expression
– Thelist(123)becomesthefirstelementinthe combined list ((1 2 3) 3 4 5)
– (Much)moreonlistprocessingsoon.
Example: Building a List with the Function list
(list `a `b `c) ⇒ (a b c)
(list `(a b c)) ⇒ ((a b c))
• Lambdaexpressionsare“localfunctions”
The expression (lambda(var1, var2, …) exp1 exp2 …) returns a function and applies it to the variables
that are the parameters to the function expressions, e.g.,
((lambda (x) (* x x)) 3) ⇒9
Multiple variables and multiple expression (result of last expression is the answer
((lambda (f x y) (f x x) (f x y) (f y y)) + 23)
Function Definitions
A definition associates a function expression to a name:
(define square (lambda (x) (* x x)))
or equivalently (and shorter):
(define (square x) (* x x))
Use of define, here procedure square:
(square 2) ⇒4
Example: Factorial
Top-level Function Definition
(define (fact n) ( if (> n 0)
( * n (fact (- n 1)))
=> 10333147966386144929666651337523200000000
Another Example Function
Conversion from degrees Fahrenheit to Celsius
(define (F-a-C temperature)
(/ (- temperature 32) 1.8))
(F-a-C 95)
(define freezing 32) => freezing
(F-a-C freezing)
Function Definitions with Lambdas
• WehaveseenLambdascanbecombinedwithtop-level defines
(define fct (lambda (f x) (f x x))) (fct + 13)
• Combine with let binding: x is a let-bound variable in the enclosing scope
(let ((x ‘a))
(let ((f (lambda (y) (list x y))))
(f ‘b))) => (a b)
Lambda Expression and Let-Bound Variables
(let ((x 2) (y 3)) (+ x y))
is equivalent to
((lambda (x y) (+ x y)) 2 3)
In general:
((let (var val) …) expr…) ≡ ((lambda (var …) expr…) val…)
Example: Greatest Common Divisor (GCD)
• topleveldefineforgcdfunction
(define gcd (lambda (a b)
(if (= a b)
a(if (> a b)
(gcd (- a b) b)
(gcd a (- b a))))))
(gcd 12 15) => 3
• IntroductiontoFunctionalProgramming • BasicScheme
• SpecialSyntacticForms
– Alternative (if then else) – Conditional
– Local Scope
– Quotation
• Let-boundvariables
• Top-level(function)definitions • Lambdaexpressions
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com