Advanced Functional Programming

Third International School, AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures

By: S. Doaitse Swierstra (Editor), Pedro R. Henriques (Editor), Jose N. Oliveira (Editor)

Write A Review

Paperback | 7 July 1999

At a Glance

Paperback
312 Pages

Dimensions(cm)
27.94 x 21.59 x 1.65

Paperback

$84.99

or 4 interest-free payments of $21.25 with

Ships in 5 to 7 business days

Inthisvolumeyouwill?ndthelecturenotescorrespondingtothepres- rd tationsgivenatthe3 summerschoolonAdvancedFunctionalProgramming, heldinBraga,PortugalfromSeptember12-19,1998. ThisschoolwasprecededbyearlieronesinB?astad(1995,Sweden,LNCS925) andOlympia,WA(1996,USA,LNCS1129). Thegoalofthisseriesofschoolsis tobringrecentdevelopmentsintheareaoffunctionalprogrammingtoalarge groupofstudents. Thenotesarepublishedinordertoenableindividuals,small studygroups,andlecturerstobecomeacquaintedwithrecentworkinthefast developingareaoffunctionalprogramming. Whatmadethisschoolparticularlyinterestingwasthefactthatalllectures introducedusefulsoftware,thatwasusedbythestudentsintheclassestoget hands-onexperiencewiththesubjectstaught. Weurgereadersofthisvolumeto downloadthelatestversionofthissoftwarefromtheInternetandtrytodothe exercisesfromthetextthemselves;theproofoftheprogramisinthetyping. The?rstlecture,onSortingMorphisms,servesasagentleintroductiontothe thingstocome. Ifyouhavealwaysbeenafraidoftheword"morphism",andyou havebeenwonderingwhatcatamorphisms,anamorphisms,hylomorphims,and paramorphimswereabout,thisisthepapertoread?rst;youwilldiscoverthat theyaremerelynamesforrecursionpatternsthatoccuroverandoveragainwhen writingfunctionalprograms. Thealgorithmsinthepaperareallaboutsorting, andsinceyouarelikelytoknowthosealgorithmsbyheartalready,seeingthem structuredandanalyzedinanovelwayshouldserveasamotivationtoreadon tothesecondlecture. Thesecondlecture,onGenericProgramming,isalmostabookinabook. ThenotescanbeseenastheculminatingpointoftheSTOP-project,sponsored bytheDutchgovernmentattheendofthe80'sandthebeginningofthe90's. Its overallgoalwasthedevelopmentofacalculationalwayofderivingprograms. The projecthasprovideddeeperinsightintorealfunctionalprogrammingandinto thetheorybehindmanythingscommonlywrittenbyfunctionalprogrammers. Oneofthemainachievementsoftheprojecthasbeentomakepeopleaware ofthefactthatmanyalgorithmscanbedescribedinadata-independentway. ThePolyPsystemintroducedinthesenotesisoneofthetranslationstothe Haskell-worldofthistheoreticalunderpinning. Thethirdlecture,onGenericProgramTransformation,canalsobeseenas anapplicationofthetheoryintroducedinlecturetwo. Manye?ciency-improving programtransformationscanbeperformedinamechanicalway,andthesewould nothavebeenpossiblewithoutinsightintothecorrectnessofsuchtransfor- tionsgainedinthelectureonGenericProgramming. Thefourthlecture,onDesigningandImplementingCombinatorLanguages, introducesaneasytowriteformalismforwritingdownthecatamorphismsint- ducedinearlierchapters. Itisshownhowquitecomplicatedcatamorphisms,that at?rstsightseemratherforbiddingbymakingextensiveuseofhigher-orderdo- VI Preface mains,canactuallybedevelopedinastep-wisefashion,usinganattributegr- marview;itisfurthermoreshownhowtorelatethiswayofprogrammingwith conceptsfromtheobject-orientedworldthusmakingclearwhatthestrengths andweaknessesofeachworldare. The?fthlecture,titledUsingMetaML:AStagedProgrammingLanguage, introducestheconceptofpartialevaluation. Itservesasanotherinstanceof thequestfor"themostgenericofwritingprogramsatthelowestcost". The stagingtechniquesshowhowcoststhatwereintroducedbyaddingextralevels ofabstraction,maybemovedfromrun-timetocompile-time. Ithasbeencommonknowledgetousersofmodernfunctionallanguagesthat thetypesystemcanbeagreathelpinshorteningprogramsandreducingerrors. Intheextremeonemightseeatypeasapredicatecapturingtheproperties ofanyexpressionwiththattype. InthesixthlectureonCayenne-Spiceup yourProgrammingwithDependentTypesitisshowninwhatdirectionfunct

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Computer Programming & Software Development Object-Oriented Programming or OOP Software Engineering Programming & Scripting Languages

Sorting Morphisms	p. 1
Introduction	p. 1
Morphisms on Lists	p. 2
The List Catamorphism	p. 2
The List Anamorphism	p. 4
The List Hylomorphism	p. 5
Insertion Sort	p. 6
Selection Sorts	p. 7
Leaf Trees	p. 9
The Leaf-Tree Catamorphism	p. 9
The Leaf-Tree Anamorphism	p. 10
The Leaf-Tree Hylomorphism	p. 11
Merge Sort	p. 12
Binary Trees	p. 13
The Tree Catamorphism	p. 13
The Tree Anamorphism	p. 14
The Tree Hylomorphism	p. 14
Quicksort	p. 15
Heap Sort	p. 16
Paramorphisms	p. 18
The List Paramorphism	p. 18
Insert As Paramorphism	p. 18
Remove As Paramorphism	p. 19
Generalizing Data Structures	p. 20
Generalizing Quicksort	p. 20
Generalizing Heap Sort	p. 21
Conclusions	p. 23
Generic Programming - An Introduction	p. 28
Introduction	p. 28
The Abstraction-Specialisation Cycle	p. 28
Genericity in Programming Languages	p. 29
Path Problems	p. 30
The Plan	p. 33
Why Generic Programming?	p. 35
Algebras, Functors and Datatypes	p. 36
Algebras and Homomorphisms	p. 36
Functors	p. 43
Polynomial Functors	p. 46
Datatypes Generically	p. 54
A Simple Polytypic Program	p. 67
PolyP	p. 68
Regular Functors in PolyP	p. 69
An Example: psum	p. 70
Basic Polytypic Functions	p. 72
Type Checking Polytypic Functions	p. 73
More Examples of Polytypic Functions	p. 75
PolyLib: A Library of Polytypic Functions	p. 76
Generic Unification	p. 83
Monads and Terms	p. 85
Generic Unification	p. 89
From Functions to Relations	p. 94
Why Relations?	p. 94
Parametric Polymorphism	p. 95
Relators	p. 99
Occurs-In	p. 101
Solutions to Exercises	p. 104
Generic Program Transformation	p. 116
Introduction	p. 116
Abstraction versus Efficiency	p. 117
Minimum Depth of a Tree	p. 117
Decorating a Tree	p. 118
Partitioning a List	p. 119
Automating the Transition: Fusion and Higher Order Rewriting	p. 120
The MAG System	p. 125
Getting Acquainted	p. 125
Accumulation Parameters	p. 128
Tupling	p. 131
Carrying On	p. 133
Matching Typed ¿-Expressions	p. 134
Types	p. 134
Expressions	p. 135
Substitutions	p. 138
Matching	p. 138
Concluding Remarks	p. 140
Answers to Exercises	p. 143
Designing and Implementing Combinator Languages	p. 150
Introduction	p. 150
Defining Languages	p. 150
Extending Languages	p. 151
Embedding Languages	p. 151
Overview	p. 152
Compositional Programs	p. 153
The Rep_Min Problem	p. 153
Table_Formatting	p. 159
Defining Catamorphisms	p. 170
Discussion	p. 175
Attribute Grammars	p. 177
The Rep_Min Problem	p. 177
The Table_Formatting Problem	p. 181
Comparison with Monadic Approach	p. 184
Pretty Printing	p. 185
The General Approach	p. 187
Improving Filtering	p. 188
Loss of Sharing in Computations	p. 193
Discussion	p. 196
Strictification	p. 201
Introduction	p. 201
Pretty Printing Combinators Strictified	p. 201
Conclusions	p. 203
Using MetaML: A Staged Programming Language	p. 207
Why Staging?	p. 207
Relationship to Other Paradigms	p. 210
Introducing MetaML	p. 211
The Bracket Operator: Building Pieces of Code	p. 212
The Escape Operator: Composing Pieces of Code	p. 213
The run Operator: Executing User-Constructed Code	p. 214
The lift Operator: Another Way to Build Code	p. 215
Lexical Capture of Free Variables: Constant Pieces of Code	p. 216
Pattern Matching Against Code	p. 217
A Staged Term Rewriting System	p. 218
Safe Reductions under Brackets	p. 222
Safe-Beta	p. 222
Safe-Eta	p. 222
Safe-Let-Hoisting	p. 223
Non-standard Extensions	p. 223
Higher Order Type Constructors	p. 223
Local Polymorphism	p. 224
Monads	p. 225
Monads in MetaML	p. 226
An Example Monad	p. 226
Safe Monad-Law-Normalization Inside Brackets	p. 227
From Interpetors to Compilers Using Staging	p. 228
The While-Language	p. 228
The Structure of the Solution	p. 229
Step1: Monadic Interpreter	p. 231
Step2: Staged Interpreter	p. 233
Typing Staged Programs	p. 236
Type Questions Still to be Addressed	p. 236
Conclusion	p. 238
Exercises	p. 238
Cayenne - A Language with Dependent Types	p. 240
Introduction	p. 240
The Type of printf	p. 241
The Set "Package"	p. 242
The Eq Class	p. 243
Core Cayenne	p. 246
Functions	p. 246
Data Types	p. 247
Records	p. 248
The Type of Types	p. 248
Full Cayenne	p. 249
Hidden Arguments	p. 249
Syntactic Sugar	p. 250
Modules	p. 251
The Cayenne Type System	p. 252
Translucent Sums	p. 252
Typing and Evaluation Rules	p. 253
Type Checking	p. 254
Undecidability in Practice	p. 257
Cayenne as a Proof System	p. 258
Implementation	p. 258
Erasing Types	p. 258
Keeping Types	p. 260
The Current Implementation	p. 260
Related Work	p. 260
Future Work	p. 261
Acknowledgments	p. 261
The Eq Class	p. 264
The TautologyFunction	p. 266
Haskell as an Automation Controller	p. 268
Introduction	p. 268
Minuscule Introduction to Haskell	p. 269
Using COM Components	p. 270
MS Agents in Haskell	p. 271
Exercises	p. 273
Essential COM	p. 273
Interface Types	p. 274
Inheritance	p. 274
IDL	p. 275
Automation	p. 276
Using Automation	p. 276
Methods	p. 277
Properties	p. 277
HaskellDirect	p. 278
Exercises	p. 278
Advanced Automation	p. 278
Variants	p. 279
Optional Arguments	p. 279
Advanced Example	p. 280
Webster	p. 281
Exercises	p. 282
Interacting with other Languages	p. 282
The Script Server Interfaces	p. 283
Exporting Values from Haskell	p. 284
Visual Basic and Haskell	p. 285
Importing Values into Haskell	p. 286
Handling Events	p. 286
Exercises	p. 288
Conclusions	p. 288
Table of Contents provided by Publisher. All Rights Reserved.

Advanced Functional Programming

Third International School, AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Object-Oriented Programming or OOP

Learning Python 6th Edition

Powerful Object-Oriented Programming

Refactoring 2ed

Improving the Design of Existing Code

Design Patterns

Elements of Reusable Object-Oriented Software

PHP, MySQL, & JavaScript All-In-One For Dummies

For Dummies

Head First Python

3rd Edition - A Learner's Guide to the Fundamentals of Python Programming, a Brain-Friendly Guide

Effective Modern C++

42 Specific Ways to Improve Your Use of C++11 And C++14

Head First Design Patterns

Building Extensible and Maintainable Object-Oriented Software 2nd Edition

Programming Rust

Fast, Safe Systems Development 2nd Edition

Head First Object-Oriented Analysis and Design

A Brain Friendly Guide to OOA &D

Statistical Analysis with R For Dummies

For Dummies (Computer/Tech)

C++ Primer

Objects First with Java 6ed

A Practical Introduction Using BlueJ, Global Edition

Concurrency in C# Cookbook

2nd Edition - Asynchronous, Parallel, and Multithreaded Programming

Deep Learning with R, Third Edition

Software Design in Python

Principles and Patterns

The Well-Grounded Rubyist, Fourth Edition

C++ Software Design

Design Principles and Patterns for High-Quality Software

The Art of Code

The surprising power of beauty in software development

Python Pocket Reference

Python in Your Pocket : 5th Edition

Reactive Programming with RxJava

Java 9 Modularity

Patterns and Practices for Developing Maintainable Applications

Scala Cookbook

Recipes for Object-Oriented and Functional Programming 2nd Edition

Programming IOS 14

Dive Deep Into Views, View Controllers, and Frameworks

PowerShell Cookbook

The Complete Guide to Scripting Microsoft's Command Shell 4th Edition

This product is categorised by