Lecture Notes in Computer Science

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)
23.5 x 15.88 x 1.91

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

Orders over $89.00 qualify for free shipping.

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.

Lecture Notes in Computer Science

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 Software Engineering

Multimodal Artificial Intelligence in Precision Agriculture

Practices, Challenges, and Applications

Ethics and Governance of Artificial Intelligence

Frameworks, Risks, and Society

Cloud-Native Modernization Unleashed

Revolutionizing Legacy Systems with Spring, Ai, Cloud, and Microservices

The Essence of Software Engineering

Fundamentals of Software Architecture

A Modern Engineering Approach

Design Patterns

Elements of Reusable Object-Oriented Software

Building Microservices

Designing Fine-Grained Systems 2nd Edition

The Manager`s Path

A Guide for Tech Leaders Navigating Growth and Change

Git : Pocket Guide

A Working Introduction

Site Reliability Engineering

How Google Runs Production Systems

The Pragmatic Programmer 2nd edition

your journey to mastery, 20th Anniversary Edition

C# 12 in a Nutshell

The Definitive Reference

Architecture Patterns with Python

Enabling Test-Driven Development, Domain-Driven Design, and Event-Driven Microservices

Arduino for Dummies

Blackwell Philosophy Anthologies

Developing Graphics Frameworks with Java and OpenGL

Coding All-in-One For Dummies

2nd Edition

Code

2nd Edition - The Hidden Language of Computer Hardware and Software

Swim Training Patterns

1st Edition - Plan your Training Sessions with the Power of Mathematics

Hacking For Dummies

For Dummies (Computer/Tech)

Robert C. Martin

A Craftsman's Guide to Software Structure and Design

Robert C. Martin

A Handbook of Agile Software Craftsmanship

User Story Mapping

Discover the Whote Story, Build the Right Product

Web Application Security

2nd Eidtion - Exploitation and Countermeasures for Modern Web Applications

The Engineering Leader

Strategies for Scaling Teams and Yourself

This product is categorised by