book

Expert F# 2.0

Name: Expert F# 2.0
ISBN: 9781430224310

by Don Syme, Adam Granicz, Antonio Cisternino

June 2010

Intermediate to advanced

623 pages

15h 49m

English

Apress

Read now

Unlock full access

Copyright
Foreword
About the Authors
About the Technical Reviewer
Acknowledgments
1. Introduction
1.1. The Genesis of F#1.2. About This Book1.3. Who This Book Is For
2. Getting Started with F# and .NET
2.1. Creating Your First F# Program2.1.1. Documenting Code Using XMLDocs2.1.2. Using let2.1.3. Understanding Types2.1.4. Calling Functions2.1.5. Lightweight Syntax2.1.6. Understanding Scope2.1.7. Using Data Structures2.1.8. Using Properties and the Dot-Notation2.1.9. Using Tuples2.1.10. Using Imperative Code2.2. Using .NET Libraries from F#2.2.1. Using open to Access Namespaces and Modules2.2.2. Using new and Setting Properties2.2.3. Fetching a Web Page2.3. Summary
3. Creating Your First F# Program—Introducing Functional Programming
3.1. Getting Started with F# Arithmetic3.1.1. Basic Literals3.1.2. Arithmetic Operators3.1.3. Bitwise Operations3.1.4. Arithmetic Conversions3.1.5. Arithmetic Comparisons3.1.6. Overloaded Math Functions3.2. Introducing Simple Strings3.2.1. Working with String Literals and Primitives3.2.2. Building Strings3.3. Working with Lists and Options3.3.1. Using F# Lists3.3.2. Using F# Option Values3.3.3. Using Option Values for Control3.3.4. Working with Conditionals: && and ||3.4. Defining Recursive Functions3.5. Introducing Function Values3.5.1. Using Anonymous Function Values3.5.2. Computing with Aggregate Operators3.5.3. Composing Functions with >>3.5.4. Building Functions with Partial Application3.5.5. Using Local Functions3.5.6. Using Functions as Abstract Values3.5.7. Iterating with Aggregate Operators3.5.8. Abstracting Control with Functions3.5.9. Using .NET Methods as First-Class Functions3.6. Getting Started with Pattern Matching3.6.1. Matching on Structured Values3.6.2. Guarding Rules and Combining Patterns3.7. Getting Started with Sequences3.7.1. Using Range Expressions3.7.2. Iterating a Sequence3.7.3. Transforming Sequences with Aggregate Operators3.7.4. Which Types Can Be Used as Sequences?3.7.5. Using Lazy Sequences from External Sources3.8. Using Sequence Expressions3.8.1. Creating Sequence Expressions Using for3.8.2. Enriching Sequence Expressions with Additional Logic3.8.3. Generating Lists and Arrays Using Sequence Expressions3.9. Exploring Some Simple Type Definitions3.9.1. Defining Type Abbreviations3.9.2. Defining Records3.9.3. Handling Non-Unique Record Field Names3.9.4. Cloning Records3.9.5. Defining Discriminated Unions3.9.6. Using Discriminated Unions as Records3.9.7. Defining Multiple Types Simultaneously3.10. Summary
4. Introducing Imperative Programming
4.1. Imperative Looping and Iterating4.1.1. Simple for Loops4.1.2. Simple while Loops4.1.3. More Iteration Loops over Sequences4.2. Using Mutable Records4.2.1. Mutable Reference Cells4.2.2. Avoiding Aliasing4.2.3. Hiding Mutable Data4.3. Using Mutable Locals4.4. Working with Arrays4.4.1. Generating and Slicing Arrays4.4.2. Two-Dimensional Arrays4.5. Introducing the Imperative .NET Collections4.5.1. Using Resizeable Arrays4.5.2. Using Dictionaries4.5.3. Using Dictionary's TryGetValue4.5.4. Using Dictionaries with Compound Keys4.5.5. Some Other Mutable Data Structures4.6. Exceptions and Controlling Them4.6.1. Catching Exceptions4.6.2. Using try . . . finally4.6.3. Defining New Exception Types4.7. Having an Effect: Basic I/O4.7.1. Very Simple I/O: Reading and Writing Files4.7.2. .NET I/O via Streams4.7.3. Some Other I/O-Related Types4.7.4. Using System.Console4.7.5. Using printf and Friends4.7.6. Generic Structural Formatting4.7.7. Cleaning Up with IDisposable, use, and using4.8. Working with null Values4.9. Some Advice: Functional Programming with Side Effects4.9.1. Consider Replacing Mutable Locals and Loops with Recursion4.9.2. Separate Pure Computation from Side-Effecting Computations4.9.3. Separate Mutable Data Structures4.9.4. Not All Side Effects Are Equal4.9.5. Avoid Combining Imperative Programming and Laziness4.10. Summary
5. Mastering Types and Generics
5.1. Understanding Generic Type Variables5.2. Writing Generic Functions5.3. Understanding Some Important Generic Functions5.3.1. Generic Comparison5.3.2. Generic Hashing5.3.3. Generic Pretty-Printing5.3.4. Generic Boxing and Unboxing5.3.5. Generic Binary Serialization via the .NET Libraries5.4. Making Things Generic5.4.1. Generic Algorithms through Explicit Arguments5.4.2. Generic Algorithms through Abstract Object Types5.4.3. Arithmetic Operators and Generic Algorithms through Inlining5.5. Understanding .NET Types5.5.1. Reference Types and Value Types5.5.2. Other Flavors of .NET Types5.6. Understanding Subtyping5.6.1. Casting Up Statically5.6.2. Casting Down Dynamically5.6.3. Performing Type Tests via Pattern Matching5.6.4. Knowing When Upcasts Are Applied Automatically5.6.5. Flexible Types5.7. Units of Measure5.8. Troubleshooting Type-Inference Problems5.8.1. Using a Visual Editing Environment5.8.2. Using Type Annotations5.8.3. Understanding the Value Restriction5.8.4. Working Around the Value Restriction5.8.4.1. Technique 1: Constrain Values to Be Nongeneric5.8.4.2. Technique 2: Ensure Generic Functions Have Explicit Arguments5.8.4.3. Technique 3: Add Dummy Arguments to Generic Functions When Necessary5.8.4.4. Technique 4: Add Explicit Type Arguments When Necessary5.8.5. Understanding Generic Overloaded Operators5.9. Summary

6. Working with Objects and Modules
6.1. Getting Started with Objects and Members6.2. Using Classes6.3. Adding Further Object Notation to Your Types6.3.1. Working with Indexer Properties6.3.2. Adding Overloaded Operators6.3.3. Using Named and Optional Arguments6.3.4. Using Optional Property Settings6.3.5. Adding Method Overloading6.4. Defining Object Types with Mutable State6.5. Getting Started with Object Interface Types6.5.1. Defining New Object Interface Types6.5.2. Implementing Object Interface Types Using Object Expressions6.5.3. Implementing Object Interface Types Using Concrete Types6.5.4. Using Common Object Interface Types from the .NET Libraries6.5.5. Understanding Hierarchies of Object Interface Types6.6. More Techniques to Implement Objects6.6.1. Combining Object Expressions and Function Parameters6.6.2. Defining Partially Implemented Class Types6.6.3. Using Partially Implemented Types via Delegation6.6.4. Using Partially Implemented Types via Implementation Inheritance6.7. Using Modules and Static Members6.8. Extending Existing Types and Modules6.9. Working with F# Objects and .NET Types6.9.1. Structs6.9.2. Delegates6.9.3. Enums6.10. Summary
7. Encapsulating and Packaging Your Code
7.1. Hiding Things Away7.1.1. Hiding Things with Local Definitions7.1.2. Hiding Things with Accessibility Annotations7.2. Using Namespaces and Modules7.2.1. Putting Your Code in a Namespace7.2.2. Using Files as Modules7.3. Creating Assemblies, DLLs, and EXEs7.3.1. Compiling EXEs7.3.2. Compiling DLLs7.3.3. Mixing Scripting and Compiled Code7.3.4. Choosing Optimization Settings7.3.5. Generating Documentation7.3.6. Building Shared Libraries and Using the Global Assembly Cache7.3.7. Using Static Linking7.4. Using Signature Types and Files7.4.1. Using Explicit Signature Types and Signature Files7.4.2. When Are Signature Types Checked?7.5. Packaging Applications7.5.1. Packaging Different Kinds of Code7.5.2. Using Data and Configuration Settings7.6. Summary
8. Mastering F#: Common Techniques
8.1. Equality, Hashing, and Comparison8.1.1. Asserting Equality, Hashing, and Comparison Using Attributes8.1.2. Fully Customizing Equality, Hashing, and Comparison on a Type8.1.3. Suppressing Equality, Hashing, and Comparison on a Type8.1.4. Customizing Generic Collection Types8.2. Efficient Precomputation and Caching8.2.1. Precomputation and Partial Application8.2.2. Precomputation and Objects8.2.3. Memoizing Computations8.2.4. Lazy Values8.2.5. Other Variations on Caching and Memoization8.3. Cleaning Up Resources8.3.1. Cleaning Up with use8.3.2. Managing Resources with More Complex Lifetimes8.3.3. Cleaning Up Internal Objects8.3.4. Cleaning Up Unmanaged Objects8.3.5. Cleaning Up in Sequence Expressions8.3.6. Using using8.4. Stack as a Resource: Tail Calls and Recursion8.4.1. Tail Recursion and List Processing8.4.2. Tail Recursion and Object-Oriented Programming8.4.3. Tail Recursion and Processing Unbalanced Trees8.4.4. Using Continuations to Avoid Stack Overflows8.4.5. Another Example: Processing Syntax Trees8.5. Events8.5.1. Events as First-Class Values8.5.2. Creating and Publishing Events8.6. Summary
9. Introducing Language-Oriented Programming
9.1. Using XML as a Concrete Language Format9.1.1. Using the System.Xml Namespace9.1.2. From Concrete XML to Abstract Syntax9.2. Working with Abstract Syntax Representations9.2.1. Abstract Syntax Representations: Less Is More9.2.2. Processing Abstract Syntax Representations9.2.3. Transformational Traversals of Abstract Syntax Representations9.2.4. Using On-Demand Computation with Abstract Syntax Trees9.2.5. Caching Properties in Abstract Syntax Trees9.2.6. Memoizing Construction of Syntax Tree Nodes9.3. Introducing Active Patterns9.3.1. Converting the Same Data to Many Views9.3.2. Matching on .NET Object Types9.3.3. Defining Partial and Parameterized Active Patterns9.3.4. Hiding Abstract Syntax Implementations with Active Patterns9.4. Embedded Computational Languages with Workflows9.4.1. An Example: Success/Failure Workflows9.4.2. Defining a Workflow Builder9.4.3. Workflows and Untamed Side Effects9.4.4. Example: Probabilistic Workflows9.4.5. Combining Workflows and Resources9.4.6. Recursive Workflow Expressions9.5. Using F# Reflection9.5.1. Reflecting on Types9.5.2. Schema Compilation by Reflecting on Types9.5.3. Using the F# Dynamic Reflection Operators9.6. Using F# Quotations9.6.1. Example: Using F# Quotations for Error Estimation9.6.2. Resolving Top Definitions9.7. Summary
10. Using the F# and .NET Libraries
10.1. A High-Level Overview10.1.1. Namespaces from the .NET Framework10.1.2. Namespaces from the F# Libraries10.2. Using the System Types10.3. Using Regular Expressions and Formatting10.3.1. Matching with System.Text.RegularExpressions10.3.2. Formatting Strings Using .NET Formatting10.3.3. Encoding and Decoding Unicode Strings10.3.4. Encoding and Decoding Binary Data10.4. Using Further F# and .NET Data Structures10.4.1. System.Collections.Generic and Other .NET Collections10.5. Introducing Microsoft.FSharp.Math10.5.1. Using Matrices and Vectors10.5.2. Using Operator Overloads on Matrices and Vectors10.6. Supervising and Isolating Execution10.7. Further Libraries for Reflective Techniques10.7.1. Using General Types10.7.2. Using Microsoft.FSharp.Reflection10.8. Some Other .NET Types You May Encounter10.9. Some Other .NET Libraries10.10. Summary
11. Building Graphical User Interfaces
11.1. Writing "Hello, World!" in a Click11.2. Understanding the Anatomy of a Graphical Application11.3. Composing User Interfaces11.4. Drawing Applications11.5. Writing Your Own Controls11.5.1. Developing a Custom Control11.5.2. Anatomy of a Control11.6. Displaying Samples from Sensors11.6.1. Building the GraphControl: The Model11.6.2. Building the GraphControl: Style Properties and Controller11.6.3. Building the GraphControl: The View11.6.4. Putting It Together11.7. Creating a Mandelbrot Viewer11.7.1. Computing Mandelbrot11.7.2. Setting Colors11.7.3. Creating the Visualization Application11.7.4. Creating the Application Plumbing11.8. Windows Presentation Foundation11.8.1. When GUIs Meet the Web11.8.2. Drawing11.8.3. Controls11.8.4. Bitmaps and Images11.8.5. Final Considerations11.9. Summary
12. Working with Symbolic Representations
12.1. Symbolic Differentiation and Expression Rendering12.1.1. Modeling Simple Algebraic Expressions12.1.2. Implementing Local Simplifications12.1.3. A Richer Language of Algebraic Expressions12.1.4. Parsing Algebraic Expressions12.1.5. Simplifying Algebraic Expressions12.1.6. Symbolic Differentiation of Algebraic Expressions12.1.7. Rendering Expressions12.1.7.1. Converting to VisualExpr12.1.7.2. Rendering12.1.8. Building the User Interface12.2. Verifying Circuits with Propositional Logic12.2.1. Representing Propositional Logic12.2.2. Evaluating Propositional Logic Naively12.2.3. From Circuits to Propositional Logic12.2.4. Checking Simple Properties of Circuits12.2.5. Representing Propositional Formulae Efficiently Using BDDs12.2.6. Circuit Verification with BDDs12.3. Summary
13. Reactive, Asynchronous, and Parallel Programming
13.1. Introducing Some Terminology13.2. Using and Designing Background Workers13.2.1. Building a Simpler Iterative Worker13.2.2. Raising Additional Events from Background Workers13.2.3. Connecting a Background Worker to a GUI13.3. Introducing Asynchronous and Parallel Computations13.3.1. Fetching Multiple Web Pages in Parallel, Asynchronously13.3.2. Understanding Thread Hopping13.3.3. Under the Hood: What Are Asynchronous Computations?13.3.4. Parallel File Processing Using Asynchronous Workflows13.3.5. Running Asynchronous Computations13.3.6. Common I/O Operations in Asynchronous Workflows13.3.7. Under the Hood: Implementing Async.Parallel13.3.8. Using async for CPU Parallelism with Fixed Tasks13.3.9. Understanding Exceptions and Cancellation13.4. Passing and Processing Messages13.4.1. Introducing Message Processing13.4.2. Creating Objects That React to Messages13.4.3. Scanning Mailboxes for Relevant Messages13.4.4. Example: Asynchronous Web Crawling13.5. Using Shared-Memory Concurrency13.5.1. Creating Threads Explicitly13.5.2. Shared Memory, Race Conditions, and the .NET Memory Model13.5.3. Using Locks to Avoid Race Conditions13.5.4. Using ReaderWriterLock13.5.5. Some Other Concurrency Primitives13.6. Summary
14. Building Smart Web Applications
14.1. Serving Static Web Content14.2. Serving Dynamic Web Content with ASP.NET14.2.1. Understanding the Languages Used in ASP.NET14.2.2. A Simple ASP.NET Web Application14.2.3. Deploying and Running the Application14.2.4. Using Code-Behind Files14.3. Using ASP.NET Input Controls14.4. Displaying Data from Databases14.5. Going Further with ASP.NET14.5.1. ASP.NET Directives14.5.2. Server Controls14.5.3. Debugging, Profiling, and Tracing14.5.4. Understanding the ASP.NET Event Model14.5.5. Maintaining the View State14.5.6. Understanding the Provider Model14.5.6.1. Configuring the Provider Database14.5.7. Creating Custom ASP.NET Server Controls14.6. Building Ajax Rich Client Applications14.6.1. More on the WebSharper Platform14.6.1.1. Getting Started with WebSharper14.6.1.2. WebSharper Pagelets14.6.1.3. Calling Server Code from the Client14.7. WebSharper Formlets14.7.1.14.7.1.1. .NET Proxies and JavaScript Stubs14.7.1.2. Automated Resource Tracking and Handling14.7.1.3. Dependent Formlets and Flowlets14.8. Using WSDL Web Services14.8.1. Consuming Web Services14.8.2. Calling Web Services Asynchronously14.9. Summary
15. Working with Data
15.1. Querying In-Memory Data Structures15.1.1. Select/Where/From Queries Using Aggregate Operators15.1.2. Using Aggregate Operators in Queries15.1.3. Accumulating Using Folding Operators15.1.4. Expressing Some Queries Using Sequence Expressions15.2. Using Databases to Manage Data15.2.1. Choosing Your Database Engine15.2.2. Understanding ADO.NET15.2.3. Establishing Connections to a Database Engine15.2.4. Creating a Database15.2.5. Creating Tables and Inserting and Fetching Records15.2.6. Using Untyped Datasets15.2.7. Generating Typed Datasets Using xsd.exe15.2.8. Using Stored Procedures15.2.9. Using Data Grids15.3. Working with Databases in Visual Studio15.3.1. Creating a Database15.3.2. Visual Data Modeling: Adding Relationships15.4. Accessing Relational Data with Linq Queries15.4.1. Generating the Object/Relational Mapping15.4.2. Building the DataContext Instance15.4.3. Using LINQ from F#15.5. Working with XML as a Generic Data Format15.5.1. Constructing XML via LINQ15.5.2. Storing, Loading, and Traversing LinqToXml Documents15.5.3. Querying XML15.6. Summary
16. Lexing and Parsing
16.1. Processing Line-Based Input16.1.1. On-Demand Reading of Files16.1.2. Using Regular Expressions16.2. Tokenizing with FsLex16.2.1. The FsLex Input in More Detail16.2.2. Generating a Simple Token Stream16.2.3. Tracking Position Information Correctly16.2.4. Handling Comments and Strings16.3. Recursive-Descent Parsing16.3.1. Limitations of Recursive-Descent Parsers16.4. Parsing with FsYacc16.4.1. The Lexer for Kitty16.4.2. The Parser for Kitty16.4.3. Parsing Lists16.4.4. Resolving Conflicts, Operator Precedence, and Associativity16.4.5. Putting It Together16.5. Binary Parsing and Pickling Using Combinators16.6. Summary
17. Interoperating with C and COM
17.1. Common Language Runtime17.2. Memory Management at Runtime17.3. COM Interoperability17.4. Platform Invoke17.4.1. Getting Started with PInvoke17.4.2. Data Structures17.4.3. Marshalling Strings17.4.4. Function Pointers17.4.5. PInvoke Memory Mapping17.4.6. Wrapper Generation and Limits of PInvoke17.5. Summary
18. Debugging and Testing F# Programs
18.1. Debugging F# Programs18.1.1. Using Advanced Features of the Visual Studio Debugger18.1.2. Instrumenting Your Program with the System.Diagnostics Namespace18.1.3. Debugging Concurrent and Graphical Applications18.2. Debugging and Testing with F# Interactive18.2.1. Controlling F# Interactive18.2.2. Some Common F# Interactive Directives18.2.3. Understanding How F# Interactive Compiles Code18.2.4. F# Interactive and Visual Studio18.3. Unit Testing18.4. Summary
19. Designing F# Libraries
19.1. Designing Vanilla .NET Libraries19.2. Understanding Functional Design Methodology19.2.1.19.2.1.1.19.2.1.1.1. Understanding Where Functional Programming Comes From19.2.1.1.2. Understanding Functional Design Methodology19.3. Applying the .NET Library Design Guidelines to F#19.3.1.19.3.1.1.19.3.1.1.1. Recommendation: Use the .NET Naming and Capitalization Conventions Where Possible19.3.1.1.2. Recommendation: Avoid Using Underscores in Names19.3.1.1.3. Recommendation: Follow the .NET Guidelines for Exceptions19.3.1.1.4. Recommendation: Consider Using Option Values for Return Types Instead of Raising Exceptions19.3.1.1.5. Recommendation: Follow the .NET Guidelines for Value Types19.3.1.1.6. Recommendation: Consider Using Explicit Signature Files for Your Framework19.3.1.1.7. Recommendation: Consider Avoiding the Use of Implementation Inheritance for Extensibility19.3.1.1.8. Recommendation: Use Properties and Methods for Attributes and Operations Essential to a Type19.3.1.1.9. Recommendation: Avoid Revealing Concrete Data Representations Such as Records19.3.1.1.10. Recommendation: Use Active Patterns to Hide the Implementations of Discriminated Unions19.3.1.1.11. Recommendation: Use Object Interface Types Instead of Tuples or Records of Functions19.3.1.1.12. Recommendation: Understand When Currying Is Useful in Functional Programming APIs19.3.1.1.13. Recommendation: Use Tuples for Return Values, Arguments, and Intermediate Values19.4. Some Recommended Coding Idioms19.4.1.19.4.1.1.19.4.1.1.1. Recommendation: Use the Standard Operators19.4.1.1.2. Recommendation: Place the Pipeline Operator |> at the Start of a Line19.4.1.1.3. Recommendation: Format Object Expressions Using the member Syntax19.5. Summary
A. F# Brief Language Guide
A.1. Comments and AttributesA.2. Basic Types and LiteralsA.3. TypesA.4. Patterns and MatchingA.5. Functions, Composition, and PipeliningA.6. Binding and Control FlowA.7. ExceptionsA.8. Tuples, Arrays, Lists, and CollectionsA.9. OperatorsA.10. Type Definitions and ObjectsA.11. Namespaces and ModulesA.12. Sequence Expressions and Workflows

Content preview from Expert F# 2.0

Chapter 16. Lexing and Parsing

In this chapter, you take a closer look at lexing and parsing, topics introduced briefly in Chapter 9 and 11. In particular, the chapter introduces the lexer and parser generators, fslex and fsyacc, that come with the F# distribution. A typical scenario when these techniques and tools can come in handy is the following:

You want to read user-readable input that has a well-defined syntax.
You have a type (often an abstract syntax tree [AST] type) to represent this input.

The typical task is to parse the user input into your internal representation by breaking down the input string into a sequence of tokens (a process called lexical analysis) and then constructing an instance of your internal representation based on a ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781430224310Purchase book

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Expert F# 2.0

by Don Syme, Adam Granicz, Antonio Cisternino

Chapter 16. Lexing and Parsing

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.