F# for Scientists E-Book

Jon Harrop

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 502

Veröffentlichungsjahr: 2011

Beschreibung

"This work strikes a balance between the pure functional aspects of F# and the object-oriented and imperative features that make it so useful in practice, enable .NET integration, and make large-scale data processing possible." --Thore Graepel, PhD, Researcher, Microsoft Research Ltd. Over the next five years, F# is expected to become one of the world's most popular functional programming languages for scientists of all disciplines working on the Windows platform. F# is free and, unlike MATLAB® and other software with numerical/scientific origins, is a full-fledged programming language. Developed in consultation with Don Syme of Microsoft Research Ltd.--who wrote the language--F# for Scientists explains and demonstrates the powerful features of this important new programming language. The book assumes no prior experience and guides the reader from the basics of computer programming to the implementation of state-of-the-art algorithms. F# for Scientists begins with coverage of introductory material in the areas of functional programming, .NET, and scientific computing, and goes on to explore: * Program structure * Optimization * Data structures * Libraries * Numerical analysis * Databases * Input and output * Interoperability * Visualization Screenshots of development using Visual Studio are used to illustrate compilation, debugging, and interactive use, while complete examples of a few whole programs are included to give readers a complete view of F#'s capabilities. Written in a clear and concise style, F# for Scientists is well suited for researchers, scientists, and developers who want to program under the Windows platform. It also serves as an ideal supplemental text for advanced undergraduate and graduate students with a background in science or engineering.

Leseprobe

Contents

Foreword

Preface

Acknowledgments

List of Figures

List of Tables

Acronyms

CHAPTER 1: INTRODUCTION

1.1 PROGRAMMING GUIDELINES

1.2 A BRIEF HISTORY OF F#

1.3 BENEFITS OF F#

1.4 INTRODUCING F#

1.5 IMPERATIVE PROGRAMMING

1.6 FUNCTIONAL PROGRAMMING

CHAPTER 2: PROGRAM STRUCTURE

2.1 NESTING

2.2 FACTORING

2.3 MODULES

2.4 OBJECTS

2.5 FUNCTIONAL DESIGN PATTERNS

2.6 F# DEVELOPMENT

CHAPTER 3: DATA STRUCTURES

3.1 ALGORITHMIC COMPLEXITY

3.2 ARRAYS

3.3 LISTS

3.4 SETS

3.5 HASH TABLES

3.6 MAPS

3.7 CHOOSING A DATA STRUCTURE

3.8 SEQUENCES

3.9 HETEROGENEOUS CONTAINERS

3.10 TREES

CHAPTER 4: NUMERICAL ANALYSIS

4.1 NUMBER REPRESENTATION

4.2 ALGEBRA

4.3 INTERPOLATION

4.4 QUADRATIC SOLUTIONS

4.5 MEAN AND VARIANCE

4.6 OTHER FORMS OF ARITHMETIC

CHAPTER 5: INPUT AND OUTPUT

5.1 PRINTING

5.2 GENERIC PRINTING

5.3 READING FROM AND WRITING TO FILES

5.4 SERIALIZATION

5.5 LEXING AND PARSING

CHAPTER 6: SIMPLE EXAMPLES

6.1 FUNCTIONAL

6.2 NUMERICAL

6.3 STRING RELATED

6.4 LIST RELATED

6.5 ARRAY RELATED

6.6 HIGHER-ORDER FUNCTIONS

CHAPTER 7: VISUALIZATION

7.1 WINDOWS FORMS

7.2 MANAGED DIRECTX

7.3 TESSELATING OBJECTS INTO TRIANGLES

CHAPTER 8: OPTIMIZATION

8.1 TIMING

8.2 PROFILING

8.3 ALGORITHMIC OPTIMIZATIONS

8.4 LOWER-LEVEL OPTIMIZATIONS

CHAPTER 9: LIBRARIES

9.1 LOADING .NET LIBRARIES

9.2 CHARTING AND GRAPHING

9.3 THREADS

9.4 RANDOM NUMBERS

9.5 REGULAR EXPRESSIONS

9.6 VECTORS AND MATRICES

9.7 DOWNLOADING FROM THE WEB

9.8 COMPRESSION

9.9 HANDLING XML

9.10 CALLING NATIVE LIBRARIES

9.11 FOURIER TRANSFORM

9.12 METAPROGRAMMING

CHAPTER 10: DATABASES

10.1 PROTEIN DATA BANK

10.2 WEB SERVICES

10.3 RELATIONAL DATABASES

CHAPTER 11: INTEROPERABILITY

11.1 EXCEL

11.2 MATLAB

11.3 MATHEMATICA

CHAPTER 12: COMPLETE EXAMPLES

12.1 FAST FOURIER TRANSFORM

12.2 SEMI-CIRCLE LAW

12.3 FINDING NTH-NEAREST NEIGHBORS

12.4 LOGISTIC MAP

12.5 REAL-TIME PARTICLE DYNAMICS

Appendix A: Troubleshooting

A.1 VALUE RESTRICTION

A.2 MUTABLE ARRAY CONTENTS

A.3 NEGATIVE LITERALS

A.4 ACCIDENTAL CAPTURE

A.5 LOCAL AND NON-LOCAL VARIABLE DEFINITIONS

A.6 MERGING LINES

A.7 APPLICATIONS THAT DO NOT DIE

A.8 BEWARE OF “IT”

Glossary

Bibliography

INDEX

Copyright © 2008 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., Ill River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic format. For information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Harrop, Jon D.

F# for scientists / Jon Harrop.

p. cm.

Includes index.

ISBN 978-0-470-24211-7 (cloth)

1. F# (Computer program language) 2. Functional programming (Computer science) 3. Science—Data processing. I. Title.

QA76.73.F163H37 2008

005.1'14—dc22

2008009567

To my family

Foreword

Computational science is one of the wonders of the modern world. In almost all areas of science the use of computational techniques is rocketing, and software has moved from being a supporting tool to being a key site where research activities are performed. This has meant a huge increase in the importance of controlling and orchestrating computers as part of the daily routine of a scientific laboratory, from large teams making and running the computers performing global climate simulations to the individual scientist/programmer working alone. Across this spectrum, the productivity of teams and the happiness of scientists depends dramatically on their overall competency as programmers, as well as on their skills as researchers within their field. So, in the last 30 years we have seen the continued rise of that new profession: the scientific programmer. A good scientific programmer will carry both epithets with pride, knowing that programming is a key foundation for a successful publication record.

However, programming cultures differ widely, and, over time, gaping divides can emerge that can be to the detriment of all. In this book, Dr. Harrop has taken great steps forward to bridging three very different cultures: managed code programming, scientific programming and functional programming. At a technical level, each has its unique characteristics. Managed code programming, epitomized by .NET and Java, focuses on the productivity of the (primarily commercial) programmer. Scientific programmers focus on high performance computations, data manipulation, numerical computing and visualization. Functional programming focuses on crisp, declarative solutions to problems using compositional techniques. The challenge, then, is to bring these disparate worlds together in a productive way.

The language F#, which Dr. Harrop uses in this book, itself bridges two of these cultures by being a functional language for the .NET platform. F# is an incredibly powerful language: the .NET libraries give a rich and solid foundation of software functionality for many tasks, from routine programming to accessing web services and high performance graphics engines. F# brings an approach to programming that routinely makes even short programs powerful, simple, elegant and correct. However Dr. Harrop has gone a step further, showing how managed code functional programming can revolutionize the art of scientific programming itself by being a powerful workhorse tool that unifies and simplifies many of the tasks scientific programmers face.

But what of the future? The next 20 years will see great changes in scientific programming. It is customary to mention the ever-increasing challenges of parallel, concurrent, distributed and reactive programming. It is widely expected that future micro-processors will use ever-increasing transistor counts to host multiple processing cores, rather than more sophisticated microprocessor designs. If computations can be parallelized and distributed on commodity hardware then the computing resources that can be brought can be massively increased. It is well known that successful concurrent and distributed computing requires a combination of intelligent algorithm design, competent programming, and core components that abstract some details of concurrent execution, e.g. databases and task execution libraries. This needs a language that can interoperate with key technologies such as databases, and parallelism engines. Furthermore, the ability to declaratively and crisply describe solutions to concurrent programming problems is essential, and F# is admirably suited to this task.

The future, will, however, bring other challenges as well. Truly massive amounts of data are now being generated by scientific experiments. Web-based programming will become more and more routine for scientific teams: a good web application can revolutionize a scientific field. Shared databases will soon be used in almost every scientific field, and programmatic access to these will be essential. F# lends itself to these challenges: for example, it is relatively easy to perform sophisticated and high-performance analysis of these data sources by bringing them under the static type discipline of functional programming, as shown by some of the samples in this book.

You will learn much about both programming and science through this book. Dr. Harrop has chosen the style of F# programming most suited to the individual scientist: crisp, succinct and efficient, with a discursive presentation style reminiscent of Mathematica. It has been a pleasure to read, and we trust it will launch you on a long and productive career as a managed code, functional scientific programmer.

Preface

The face of scientific computing has changed. Computational scientists are no longer writing their programs in Fortran and competing for time on supercomputers. Scientists are now streamlining their research by choosing more expressive programming languages, parallel processing on desktop machines and exploiting the wealth of scientific information distributed across the internet.

The landscape of programming languages saw a punctuation in its evolution at the end of the 20th century, marked by the advent of a new breed of languages. These new languages incorporate a multitude of features that are all designed to serve a single purpose: to make life easier. Modern programming languages offer so much more expressive power than traditional languages that they even open up new avenues of scientific research that were simply intractable before.

The next few years will usher in a new era of computing, where parallelism becomes ubiquitous. Few approaches to programming will survive this transition, and functional programming is one of them.

Seamlessly interoperating with computers across the world is of pivotal importance not only because of the breadth of information now available on-line but also because this is the only practicable way to interrogate the enormous amount of data available. The amount of genomic and proteinomic data published every year continues to grow exponentially, as each generation of technology fuels the next.

Only one mainstream programming language combines awesome expressive power, interoperability and performance: F#. This book introduces all of the aspects of the F# programming language needed by a working scientist, emphasizing aspects not covered by existing literature. Consequently, this book is the ideal complement to a detailed overview of the language itself, such as the F# manual or the book Expert F#[25].

Chapters 1–5 cover the most important aspects of F# programming needed to start developing useful F# programs. Chapter 6 ossifies this knowledge with a variety of enlightening and yet simple examples. Chapters 7–11 cover advanced topics including real-time visualization, interoperability and parallel computing. Chapter 12 concludes the book with a suite of complete working programs relevant to scientific computing.

The source code from this book is available from the following website: http://www.ffconsultancy.com/products/fsharp_for_scientists/

J. D. HARROP

Cambridge, UK

June, 2008

Acknowledgments

I would like the thank Don Syme, the creator of F#, for pioneering research into programming languages and for thrusting the incredibly powerful ML family of languages into the limelight of mainstream software development.

Xavier Leroy, everyone at projet Cristal and the Debian package maintainers for making OCaml so practically useful.

Stephen Elliott and Sergei Taraskin and their group at the University of Cambridge for teaching me how to be a research scientist and letting me pursue crazy ideas when I should have been working.

Ioannis Baltopoulos and Enrique Nell for proofreading this book and giving essential feedback.

J. D. H.

List of Tables

3.1 Complexity of the ipow_2 function measured as the number of multiply operations performed.3.2 Functions implementing common operations over data structures.3.3 Asymptotic algorithmic complexities of operations over different data structures containing n elements where i ∈ {0 … n – 1} is a parameter of some of the operations, e.g. insert at index i.7.1 DirectX primitive drawing functions.

Acronyms

ADOActive Data ObjectsASPActive Server PagesASTAbstract-syntax treeBNFBackus-Naur formCAMLCategorical Abstract Machine LanguageFFTFast Fourier TransformFFTWFastest Fourier Transform in the WestGOEGaussian Orthogonal EnsembleHOFHigher-Order FunctionIDEIntegrated Development EnvironmentINRIAInstitut National de Recherche en Informatique et en AutomatiqueIOInput and OutputLCFLogic of Computable FunctionsMLMeta-LanguageOCamlObjective CAMLOOObject-OrientedOOPObject-Oriented ProgrammingOpenGLOpen Graphics LibraryRPCRemote Procedure CallSOAPSimple Object Access ProtocolUDDIUniversal Description, Discovery and IntegrationVMVirtual MachineVSVisual StudioWSDLWeb Service Definition LanguageXMLeXtensible Markup LanguageXSLTeXtensible Stylesheet Language Transformations