A Schemer's Notebook


Scheme programs and libraries written by Phil Bewig

SchemeWeb  A literate programming system for Scheme.  The LSS files on this pages can be processed by SchemeWeb.  Say (weave "filename") to create an HTML document and (tangle "filename") to extract source code.  In a running Scheme top-level, say (lload "filename") to load the code contained in a literate Scheme source file.  [LSS]  [SS]  [HTML]

A Statisticle Speling Korrecter  A reimplementation of Peter Norvig’s Python-based spelling corrector in Scheme.  Original version using treaps; the code works, but the text was never finished.  [LSS]  [SS]  [HTML]  Revised version using hash tables.  [LSS]  [SS]  [HTML]

Sudoku  A simple sudoku solver based on depth-first search.  [LSS]  [SS]  [HTML] 

Streams  SRFI-41 describes libraries of primitive and derived functions for programming with streams.  Local copies are available here: [HTML]  [PDF]  [DOC].  Code is available here: [PRIMITIVE]  [DERIVED]  [STREAMS].  Sample code from the article is available here: [SAMPLES].  Test suite is available here: [TEST].  Code and tests for R5RS Scheme are available here: [CODE]  [TEST].  See also my earlier work at SRFI-40, which is now deprecated.

Word Hy-phen-a-tion By Com-pu-ter  An implementation of Frank Liang's hyphenation algorithm for TeX.  [PDF]  [SS]

Map-Reduce  An implementation in Scheme of a programming idiom developed by Jeffrey Dean and Sanjay Ghemawat of Google that pre-processes, combines and sorts data sets.  Unlike the Google version, this map-reduce doesn’t parallelize the processing, but it does provide a useful framework for many data processing tasks.  [PDF]

Text-File Databases  Convenient processing of fielded text files is provided by a library that reads records and maps ports.  Readers and writers are provided for fixed-length, character-delimited, comma-separated, and name-value formats.  Processors are provided for the for-each, map, fold, and map-reduce operators.  Includes related utility functions, several sample applications, and a complete test suite.  [PDF]  Also see these three little procedures for reading files.  [SS]

List Comprehensions   A simple macro that provides Haskell-style list comprehensions for Scheme.  A list comprehension is given by the syntax (list-of expr clauses ...).  The five clause types are (var for first past), (var for first second past), (var in list), (var is expr), and (pred? var); note that past never appears in the output list (it is the first value past the end of the list).  [LSS]  [SS]  [HTML]

Shuffle and Sort   Permute a list, using any of several algorithms.  [LSS]  [SS]  [HTML]  Sort a list, using Richard O'Keefe's smooth applicative merge sort; also provides a simple function to stably merge two lists.  [LSS]  [SS]  [HTML]

Prime Numbers  Various functions on prime numbers.  [LSS]  [SS]  [HTML]

Trex   Rob Pike's tiny regular expression matcher from The Practice of Programming and Beautiful Code[LSS]  [SS]  [HTML]

Cluster  Collects elements of an input list with a common signature into groups.  [LSS]  [SS]  [HTML]

Date arithmetic  Two functions that convert between julian day number and gregorian dates.  [LSS]  [SS]  [HTML]  A function to calculate the date of Easter, and various other dates related to Easter.  [LSS]  [SS]  [HTML]

Homework  Sometimes my daughters ask for help with their math homework.  Sometimes it even leads to an interesting programming project.  Green Eyes is a problem in enumerating sets.  [HTML]  Golden Ratio is a problem in continued fractions.  [PDF]

Mr S and Mr P  A reimplementation of Oleg Kiselyov’s Haskell-based reimplementation of John McCarthy’s mathematical solution to the classic Mr S and Mr P puzzle.  [PDF] 

Task 206 Bitmap  A task from the Sphere Online Judge[LSS]  [SS]  [HTML]

Other Stuff  Code for treaps and ternary search tries is incomplete.