Write Yourself a Scheme in 48 Hours - Wikimedia Commons

[Pages:138]Write Yourself a Scheme in 48 Hours

An Introduction to Haskell through Example

by Wikibooks contributors originally by Jonathan Tang

Created on Wikibooks, the open content textbooks collection.

Copyright c 2007 Jonathan Tang & Wikibooks contributors.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License".

Contents

Overview

v

1 First Steps

1

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Parsing

5

Writing a Simple Parser . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Whitespace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Recursive Parsers: Adding lists, dotted lists, and quoted datums . . . 13

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Evaluation, Part 1

17

Beginning the Evaluator . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Beginnings of an Evaluator: Primitives . . . . . . . . . . . . . . . . . . 20

Adding Basic Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4 Error Checking and Exceptions

29

5 Evaluation, Part 2

37

Additional Primitives: Partial Application . . . . . . . . . . . . . . . . 37

Conditionals: Pattern Matching 2 . . . . . . . . . . . . . . . . . . . . . 42

List Primitives: car, cdr, and cons . . . . . . . . . . . . . . . . . . . 42

Equal? and Weak Typing: Heterogenous Lists . . . . . . . . . . . . . 48

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6 Building a REPL

57

7 Adding Variables and Assignment

65

8 Defining Scheme Functions

77

9 Creating IO Primitives

87

i

10 Towards a Standard Library

91

Conclusion

101

A Complete Parser

103

B Answers to Exercises

113

Section 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Exercise 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Part 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Part 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Exercise 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Exercise 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Exercise 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Exercise 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

C Document Information

117

History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

PDF Information & History . . . . . . . . . . . . . . . . . . . . . . . . 117

Document Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Orignal Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Wikibooks Changes . . . . . . . . . . . . . . . . . . . . . . . . . 118

D GNU Free Documentation License

119

1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . 119

2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . 121

3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . 121

4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . 124

6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . 124

7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . 125

8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . 125

ADDENDUM: How to use this License for your documents . . . . . . 126

Index

127

ii

Listings

1.1 hello.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.1 simpleparser1.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 simpleparser2.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 datatypeparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 recursiveparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1 evaluator1.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 evaluator2.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 evaluator3.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1 errorcheck.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.1 operatorparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 listparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.3 equalparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.1 replparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.1 variableparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 8.1 functionparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 10.1 stdlib.scm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 A.1 completeparser.hs . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

iii

Overview

Most Haskell tutorials on the web seem to take a language-reference-manual approach to teaching. They show you the syntax of the language, a few language constructs, and then have you construct a few simple functions at the interactive prompt. The "hard stuff" of how to write a functioning, useful program is left to the end, or sometimes omitted entirely.

This tutorial takes a different tack. You'll start off with command-line arguments and parsing, and progress to writing a fully-functional Scheme interpreter that implements a good-sized subset of R5RS Scheme. Along the way, you'll learn Haskell's I/O, mutable state, dynamic typing, error handling, and parsing features. By the time you finish, you should be fairly fluent in both Haskell and Scheme.

There're two main audiences targetted by this tutorial:

1. People who already know Lisp or Scheme and want to learn Haskell

2. People who don't know any programming language, but have a strong quantitative background and are familiar with computers

The second group will likely find this challenging, as I gloss over several Scheme and general programming concepts to stay focused on the Haskell. A good textbook like Structure and Interpretation of Computer Programs or The Little Schemer may help a lot here.

Users of a procedural or object-oriented language like C, Java, or Python should beware, however: You'll have to forget most of what you already know about programming. Haskell is completely different from those languages, and requires a different way of thinking about programming. It's best to go into this tutorial with a blank slate and try not to compare Haskell to imperative languages, because many concepts in them (classes, functions, 'return') have a significantly different meaning in Haskell.

Since each lesson builds on the code written for the previous one, it's probably best to go through the lessons in order.

This tutorial assumes that you'll be using GHC as your Haskell compiler. It may work with eg. Hugs, but it hasn't been tested at all, and you may need to download additional libraries.

? live version ? discussion ? edit ? comment ? report an error

v

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download