This package implements genereric syntax for working with monads in R6RS scheme.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
examples
lib
test
.gitignore
LICENSE
README.md
package.scm

README.md

R6RS monads

This package implements genereric syntax for working with monads in R6RS scheme.

Main syntax

Given a monad m with chain operator m->>= and return operator m-return, we can define syntax:

(define-monad m m->>= m-return)

This defines two new pieces of syntax: with-m and seq-m. The first bundles the monadic operators in a context:

(with-m
  (>>= value (lambda (x) (return (* x 42)))))

The seq-m operator provides a syntax very similar to Haskell's do.

(seq-m
  (x <- (div 1 a))
  (y <- (+ x 1))
  (return y))

Example: making a parser

In this example we show how to build a very simple parser using the parser (state) monad in this libary. I learned how to build a monadic parser from Graham Hutton's book "Programming in Haskell". This is also explained in Function pearls - Monadic parsing in Haskell by Graham Hutton and Eric Meijer.

The parser monad is defined in (monads parser).

(import (rnrs (6))
        (monads)
        (monads parser))

A value in the parser monad (or just 'parser') is a function that takes a state and returns values with a result and a new state.

In this case, our state variable is a list. We will take elements from this list one by one. Our first parser is the function element. It takes an element from a list and returns it along with the rest of the list. If the list was empty, we return *failure*.

(define (element c)
  (if (null? c)
    (values *failure* c)
    (values (car c) (cdr c))))

We can build a slightly more advanced parser, that filters the output of element.

(define (satisfies pred?)
  (seq-parser
    (x <- element)
    (if (pred? x)
      (return x)
      parser-failure)))

Note that, since the values in the parser monad are functions, seq-parser returns a function similar to element: one that takes a state and returns a value and a new state.

Using satisfies we can build a parser that accepts only values that are eq? to a given value.

(define (equals x)
  (satisfies (lambda (y) (eq? x y))))

Using these basic building blocks we can build a very simple parser that reads a recursive list structure.

(define number
  (satisfies number?))

(define list-of-items
  (seq-parser
    (x <- (equals '<))
    (y <- (many item))
    (z <- (equals '>))
    (return y)))

(define item
  (choice number list-of-items))

Running this on a small test:

#| Test the code on a sample |#
(let ((input '(< 1 2 < 3 4 > < < 5 > 6 > 7 >)))
  (display (parse list-of-items input))
  (newline))

gives the output

(1 2 (3 4) ((5) 6) 7)

Running this example

This example can be found in the examples folder, and run with Guile

guile -L lib examples/parser.scm

or with Chez Scheme

scheme --libdirs lib --script examples/parser.scm