When learning functional programming, a difficult concept to grasp is how any "actual work" gets done. That is, if all functions are referentially transparent, then how does the program perform IO (input/output), which is not typically referentially transparent? Are our functional programs locked out of IO, consigned to calculations without doing useful things like reading from the keyboard, printing to the screen, saving to disk or communicating over a network?

The answer, of course, is no. We create programs so that our entire program is a single IO action that, when run, can perform IO. Ideally, the program we write never actually runs any IO action, we rely on the runtime environment to run the single IO action representing our program. Most languages don’t have this environment; we compromise by making our main method run the single IO action representing the program.

This is stated eloquently at Haskell/Simple input and output,

The question immediately arises: "how do you run an action?". This is something that is left up to the compiler. You cannot actually run an action yourself; instead, a program is, itself, a single action that is run when the compiled program is executed. Thus, the compiler requires that the main function have type IO (), which means that it is an IO action that returns nothing. The compiled code then executes this action.

There are lots of good resources for further information on this topic, including [1] and [2]. Let’s investigate how this works in practice with an example in a typically impure language like Groovy.

Simple Input/Output Program

I am going to implement a simple REPL (Read, Eval, Print, Loop) that reads an integer from standard input and prints the square of that integer. If the line of input is q the program will quit, if the input is not an integer or q then an error is printed and we accept further input. This example was inspired from [2], which has a similar program in Scala (Chapter 13, External Effects and I/O).

A simple, typical, imperative solution might be:

package com.github.mperry.fg

import groovy.transform.TypeChecked

@TypeChecked
class SimpleIODemoImperative {

	String quit = "q"
	String help = "Squaring REPL\nEnter $quit to quit"
	String prompt = ">"

    static void main(def args) {
        def d = new SimpleIODemoImperative()
        d.repl()
    }

    void repl() {
        println(help)
        System.in.withReader { Reader r ->
            def doLoop = true
            while (doLoop) {
                println(prompt)
                def s = r.readLine()
                process(s)
                doLoop = continueLoop(s)
            }
        }
    }

    String squareMessage(Integer n) {
		"square $n = ${n * n}"
	}

	String invalidMessage(String s) {
		"Not an integer: $s"
	}

	Boolean continueLoop(String s) {
		s != quit
	}

	Boolean isQuit(String s) {
		!continueLoop(s)
	}

	Boolean validInput(String s) {
		s.isInteger() || isQuit(s)
	}

	void process(String s) {
		if (!validInput(s)) {
			println(invalidMessage(s))
		}
		if (s.isInteger()) {
			println(squareMessage(s.toInteger()))
		}
	}

}

A program run (interactive session) might proceed as:

Squaring REPL
Enter q to quit
>
5
square 5 = 25
>
3
square 3 = 9
>
abc
Not an integer: abc
>
q

The main method in this program instantiates the SimpleIODemoImperative class and calls the repl method. The repl method prints a help message and then enters a loop where the loop:

  • prints a prompt

  • reads a line of input

  • processes the input, printing the result or an error (or nothing if quitting)

  • checks whether the loop should continue

Let’s transform this program to do referentially transparent IO.

A Simple IO Type

Instead of reading from or writing to standard input directly, we introduce a type that, when run, will perform this IO effect. When we write output we discard the value we output; for input we represent the type of the input value directly in the SimpleIO type to make the value accessible to other parts of the program.

import groovy.transform.TypeChecked

@TypeChecked
abstract class SimpleIO<A> {
    abstract A run()
}

When run, the BasicIO type will perform the effect and return a value of type A. For output, we can make this output type be Java’s Void or Functional Java’s Unit type [3]. Despite being conceptually similar, I find the Unit type much easier to work with.

Some values that read from and write to standard input and output are as below. Remind yourself that no IO is done until the run method is called.

import fj.Unit
import fj.data.Option
import groovy.transform.TypeChecked;

@TypeChecked
class IOConstants {

	static SimpleIO<String> stdinReadLine() {
		new SimpleIO<String>() {
			String run() {
				System.in.newReader().readLine()
			}
		}
	}

	static SimpleIO<Unit> stdoutWriteLine(final String msg) {
		new SimpleIO<Unit>() {
			Unit run() {
				println(msg)
				Unit.unit()
			}
		}
	}

    static SimpleIO<Unit> empty() {
        new SimpleIO<Unit>() {
            Unit run() {
                Unit.unit()
            }
        }
    }

}

An essential method for SimpleIO is to combine two SimpleIO instances that, when run, will perform each sequentially. Unfortunately the obvious implementation in Groovy does not compile. When I try to add this to the Groovy SimpleIO class as per below the Groovy compiler gives the error "Groovyc unable to resolve class B".

  def <B> SimpleIO<B> append(final SimpleIO<B> io) {
        new SimpleIO<B>() {
            @Override
            B run() {
                SimpleIO.this.run()
                return io.run()
            }
        }
    }

I was not happy with the suggested solution to workaround this problem with the Groovy compiler, so switched this class from Groovy to Java. The append method then becomes:

    public <B> SimpleIO<B> append(final SimpleIO<B> io) {
        return new SimpleIO<B>() {
            @Override
            public B run() {
                SimpleIO.this.run();
                return io.run();
            }
        };
    }

Constructing the Referentially Transparent Program

We now have the knowledge to write our program. We create a SimpleIO action to output the initial help message and a stream of actions representing each loop iteration of our program. These are then combined to form a single SimpleIO action. The main method creates this single SimpleIO action and runs it.

The sample interactive session shown above (with a slightly enhanced help message) is duplicated below for reference:

The Spectacular Squaring REPL!
Enter an integer to square or enter q to quit
>
5
square 5 = 25
>
3
square 3 = 9
>
abc
Not an integer: abc
>
q

We create the initial help message using "IOConstants.stdoutWriteLine(help)" where help is a user help message. An action representing a single interaction loop is:

    SimpleIO<String> interaction() {
        stdoutWriteLine(prompt).append(stdinReadLine()).flatMap1({ String s ->
            invalidMessageIO(s).append(squareIO(s))
        } as F)
    }

The interaction function creates an object that will write the prompt(">") to standard output and appends the standard input read line action; the resulting expression has the type SimpleIO<String>. The function to flatMap1 takes the input line as a String and creates a SimpleIO for a (possibly empty) invalid message and appends an action for the squaring message (which could also be empty). The function flatMap1 is defined as:

    public <B> SimpleIO<A> flatMap1(final F<A, SimpleIO<B>> f) {
        return new SimpleIO<A>() {
            public A run() {
                A a = SimpleIO.this.run();
                f.f(a).run();
                return a;
            }
        };
    }

The flatMap1 function creates a SimpleIO action that, when run, runs the first SimpleIO<A>, then uses the function argument f to create a SimpleIO<B> and runs this action, then returns the result of the first action of type A. By using flatMap1 in the interaction function in this way we create a SimpleIO<String> where the String is the value read from standard input.

We now have a single IO action for a single loop of interaction, however we need to create a single SimpleIO to represent a sequence of interaction loops. The following codes does exactly this:

    SimpleIO<Stream<String>> interactionStream() {
        SimpleIO.sequenceWhile(Stream.repeat(interaction()), { String s -> isLoop(s) } as F)
    }

Before explaining this, we need to understand what sequenceWhile does. The type signature of sequenceWhile is interesting:

    static <A> SimpleIO<Stream<A>> sequenceWhile(final Stream<SimpleIO<A>> stream, final F<A, Boolean> f)

The function sequenceWhile transforms a stream of IO actions into a single IO action containing the stream of input values whilst the function argument f returns true. We pass in a lazy infinite stream into sequenceWhile and use the function argument f to return an single SimpleIO action with a finite stream of input strings. The definition of sequenceWhile is beyond the scope of this post. For more information on a proposal of adding this to the Haskell Control.Monad library see [4].

Now that we have the interactiveStream function returning a single SimpleIO to do the main interactive loop, the repl and main methods are defined as:

    SimpleIO<Stream<String>> repl() {
        stdoutWriteLine(help).append(interactionStream())
    }

	static void main(def args) {
		def d = new SimpleIODemoFunctional()
		d.repl().run()
	}

Conclusion

Our REPL consists of a single, referentially transparent SimpleIO action representing IO that does nothing until the main method calls run. Our entire program is referentially transparent. One might suspect that the main method is not referentially transparent, but because it is called just once at "the end of the world", it can be replaced with it’s definition without affecting program semantics. That is, no one can observe the effect. This could be enforced if we had an environment that enforced that main returned a single SimpleIO where the runtime environment called run on our behalf (Haskell!).

Appendix: The Full Program

The text of the full referentially transparent program is on Github [5], the entire SimpleIODemoFunctional class is:

package com.github.mperry.fg

import fj.F
import fj.Unit
import fj.data.Option
import fj.data.Stream
import groovy.transform.TypeChecked

import static com.github.mperry.fg.IOConstants.stdinReadLine
import static com.github.mperry.fg.IOConstants.stdoutWriteLine
import static fj.data.Option.none
import static fj.data.Option.some

@TypeChecked
class SimpleIODemoFunctional {

	final String quit = "q"
	final String help = "The Spectacular Squaring REPL!\nEnter an integer to square or enter $quit to quit"
	final String prompt = ">"

	Option<Integer> toInt(String s) {
		s.isInteger() ? some(s.toInteger()) : none()
	}

	String squareMessage(Integer n) {
		"square $n = ${n * n}"
	}

	Option<SimpleIO<Unit>> squareOptionIO(String s) {
		toInt(s).map { Integer n ->
			stdoutWriteLine(squareMessage(n))
		}
	}

    SimpleIO<Unit> squareIO(String s) {
        squareOptionIO(s).orSome(IOConstants.empty())
    }

    Boolean isLoop(String s) {
        !isQuit(s)
	}

	Boolean isQuit(String s) {
        s == quit
	}

	Boolean validMessage(String s) {
		(s.isInteger() || isQuit(s))
	}

	Option<String> invalidMessage(String s) {
		validMessage(s) ? none() : Option.<String>some("Not an integer: $s")
	}

	Option<SimpleIO<Unit>> invalidMessageOptionIO(String s) {
		invalidMessage(s).map { String it -> stdoutWriteLine(it)}
	}

    SimpleIO<Unit> invalidMessageIO(String s) {
        invalidMessageOptionIO(s).orSome(IOConstants.empty())
    }

    SimpleIO<String> interaction() {
        stdoutWriteLine(prompt).append(stdinReadLine()).flatMap1({ String s ->
            invalidMessageIO(s).append(squareIO(s))
        } as F)
    }

    SimpleIO<Stream<String>> interactionStream() {
        SimpleIO.sequenceWhile(Stream.repeat(interaction()), { String s -> isLoop(s) } as F)
    }

    SimpleIO<Stream<String>> repl() {
        stdoutWriteLine(help).append(interactionStream())
    }

	static void main(def args) {
		def d = new SimpleIODemoFunctional()
		d.repl().run()
	}

}

Bibliography


comments powered by Disqus