DOC PREVIEW
UT Arlington CSE 3302 - Functional Programming

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE3302 Programming Languages (n-n-n-notes)Functional ProgrammingLISPListsLISP ExecutionData StructuresConstructorAccessing Parts of a ListBuilding a listInfo RepresentationSlide 11Recursive list constructionAtomsList representationList PrimitivesConditional expressionIterationFunctional argumentsRecursive InterpretersInterpretersEnvironment of evaluationStatic scopingIncompatible scope rulesStorage reclamationReference countsSlide 26Garbage CollectionSlide 28Slide 29CSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 1 jcmtCSE3302CSE3302Programming LanguagesProgramming Languages(n-n-n-notes)(n-n-n-notes)Summer 2003Dr. Carter TiernanCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 2 jcmtFunctional ProgrammingFunctional Programming•List Processing - LISP•Complex interrelationships among data•Recursion in conjunction with conditional expressions•Primitive list-handling subroutines•Applicative languageCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 3 jcmtLISPLISP•John McCarthy•Function applications–Prefix (Polish) notation : flexibility–Fully parenthesized : no precedence rules•Symbolic data–Lists of symbols called atoms–List is ONLY data structure in LISPCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 4 jcmtListsLists•S-expressions–Function applications are evaluated–Quoted lists are treated as data•Programs and data represented the same way–Convenient for one program to generate and call for execution of another–Simple to write program manipulatorsCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 5 jcmtLISP ExecutionLISP Execution•Usually interpreted and often interactive•Functions–Pure : compute a value only•eq, plus, difference, etc.–Pseudo : have side effects on computer state•set, defun, etc.CSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 6 jcmtData StructuresData Structures•Constructor : list•Primitives : atoms–Numeric (integer and floating point)•Many ops provided: arithmetic, increment, decrement, max, min, relational, predicates–Nonnumeric character strings•Limited ops: comparisons for equality•nil (false, empty set) •null is the test opCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 7 jcmtConstructorConstructor•List–Surrounded by parentheses–Separated by blanks–Zero, one or more elements–Can contain lists–() equivalent to nil; called empty or null listCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 8 jcmtAccessing Parts of a ListAccessing Parts of a List•Car–Selects the first element of a list•Cdr–Returns all of a list except its first element•Car and Cdr are selectors•Car and Cdr can be combined to access interior parts of a list: ex. caadrCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 9 jcmtBuilding a listBuilding a list•Cons–Creates a list from a first element and a list–Is the inverse of car and cdr–Example:•(car ‘(to be or not)) = to•(cdr ‘(to be or not)) = (be or not)•(cons ‘to ‘(be or not)) = (to be or not)CSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 10 jcmtInfo RepresentationInfo Representation•Property lists–(p1 v1 p2 v2 … pn vn) where pn is the nth property and vn is the value of that property–P-lists give flexibility–Easy to define a function to get propertiesCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 11 jcmtInfo RepresentationInfo Representation•Association lists–((a1 v1) (a2 v2) … (an vn))–Handles properties which are flags or properties with multiple valuesCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 12 jcmtRecursive list constructionRecursive list construction•Append two lists together–Identify simplest cases•(append ‘() L) = L•(append L ‘()) = L–Reduce other cases to the simplest cases•(append L M) = (cons (car L) (append (cdr L) M)–(defun append (L M) (if (null L))M(cons (car L) (append (cdr L) M) ))CSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 13 jcmtAtomsAtoms•Created by mentioning them•Have properties and relations (p-list)–Print name / pname–putprop adds a property to an atom–apval denotes the binding of an atom to a value –set binds an atom–symbol-plist shows property list of an atomCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 14 jcmtList representationList representation•Linked list•Cells in the list have a right and a left–Right part points to next cell in list–Left part points to value of the cell•Data and programs both represented the same way–Program linked list called an expression treeCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 15 jcmtList PrimitivesList Primitives•Efficient–Car returns a left part–Cdr returns a right part–Cons requires storage allocation for new cell–Car, Cdr, and Cons do not change values•Sublists can be shared•Pseudo-functions alter lists–rplaca, rplacd –Have same drawbacks as aliasingCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 16 jcmtConditional expressionConditional expression•Cond–Mimics mathematical notation–Logical ops are defined in terms of the conditional•And & Or –Operands are evaluated sequentially–Conditional interpretation vs. strictCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 17 jcmtIterationIteration•Performed by recursion•Reduction–Perform some op on every element of a list–Uses a binary function to reduce a list to a single value•Mapping–Apply a function to every element of a list–Returns a list of the results•Filtering–Forms a sublist containing all elements that satisfy some propertyCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 18 jcmtFunctional argumentsFunctional arguments•Abstracting out pattern•Mapcar•Filter•Reduce•Suppress details •Simplify combinationCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 19 jcmtRecursive InterpretersRecursive Interpreters•Arranged by cases–Atoms•Numeric•Nonnumeric–Quote–Conditional–FunctionsCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 20 jcmtInterpretersInterpreters•Primitive ops performed explicitly•User-defined functions–Evaluate parameters–Bind formals to actuals–Add bindings to environment–Evaluate function in environmentCSE 3302 CSE@UTA Programming LanguagesCh. 9 - 11Ch. 9 - 11 21 jcmtEnvironment of evaluationEnvironment of evaluation•Arguments going to (apply f x


View Full Document

UT Arlington CSE 3302 - Functional Programming

Documents in this Course
Smalltalk

Smalltalk

11 pages

Syntax

Syntax

5 pages

Syntax

Syntax

5 pages

JAVA

JAVA

57 pages

Semantics

Semantics

41 pages

Control

Control

74 pages

Load more
Download Functional Programming
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Functional Programming 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 Functional Programming 2 2 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?