=Paper=
{{Paper
|id=Vol-2203/18
|storemode=property
|title=Approaching Side-effects in Pure Functional Programming by Interpreting Data Structures as Recipes
|pdfUrl=https://ceur-ws.org/Vol-2203/18.pdf
|volume=Vol-2203
|authors=Michal Strba,Richard Ostertag
|dblpUrl=https://dblp.org/rec/conf/itat/StrbaO18
}}
==Approaching Side-effects in Pure Functional Programming by Interpreting Data Structures as Recipes==
https://ceur-ws.org/Vol-2203/18.pdf
S. Krajči (ed.): ITAT 2018 Proceedings, pp. 18–27
CEUR Workshop Proceedings Vol. 2203, ISSN 1613-0073, c 2018 Michal Štrba and Richard Ostertág
Approaching side-effects in pure functional programming by interpreting data
structures as recipes
Michal Štrba, Richard Ostertág
Faculty of Mathematics, Physics and Informatics, Comenius University, Mlynská dolina, Bratislava, Slovakia
faiface@ksp.sk, ostertag@dcs.fmph.uniba.sk
Abstract: We present a new approach to side-effects in stand. The description is very dense, full comprehension
pure functional programming. The approach is not novel is not required.
in every aspect but rather in combining of multiple already
known concepts into a coherent method.
1.1 Names and tokens
The key concept in this approach is to view some data
structures as describing a recipe of what should be done. Tokens in Funky are generally separated by whitespace,
A program expressed in form of this data structure is then except for these special characters which are always
passed to another program called ’interpreter’. An inter- parsed as separate tokens, whether separated by whites-
preter takes the recipe, examines it, and actually executes pace or not:
all the desired side-effects.
Keeping simplicity, clarity, and avoiding introduction of ( ) [ ] { } , ; \ #
any unnecessary theory, the recipe data structures tend to
Aside from these, all tokens are separated by whites-
roughly conform to the CPS (continuation passing style)
pace. Consequentially, identifiers may contain all kinds
model and tend to contain function values inside of them.
of symbols. For example, these are all valid identifiers:
This means, that expressing them in code involves a lot of
fold>, fold<, empty?, skip-whitespace. Dashes (-)
anonymous functions and large “continuations” as argu-
are used to separate words in function names instead of un-
ments to other functions. Attempting to write such code in
derscores or camel-case. However, type names start with
any of the traditional functional languages, most notably
upper-case letters and use camel-case.
Haskell, results in a very messy, unpleasant, and hard to
Tokens starting with a digit or a +/- sign followed by a
read code. We also think that it’s the main reason why
digit are numbers (valid or invalid). Any series of charac-
techniques described in this paper weren’t developed ear-
ters enclosed in single quotes is a character literal (valid or
lier in these languages.
invalid) and similarly, double quotes enclose a string literal
Therefore, we created a new language that makes such
(again, valid or invalid). Escaping in characters/strings
code beautiful and pleasant to read. The subtle features of
works as expected.
the language that make this new approach to side-effects
viable have far reaching implications, mostly by making it
possible to write purely functional code that reads top to 1.2 Functions
bottom.
A function definition is signified by the func keyword,
In this paper, we describe the Funky programming lan-
which is followed by a function name, a colon, the type of
guage, how it facilitates writing vertical code, how we can
the function, equals sign and finally the function body –
write interpreters for recipe data structures, and how we
an expression. Function definitions cannot be nested and
can use the language to transform and combine the recipes
expressions are only allowed as function bodies, no ex-
in purely functional code and thereby attain great expres-
pressions outside functions are meaningful. For example:
sivity in writing side-effecting programs.
func sqrt : Float -> Float = \x x ^ 0.5
1 Short introduction to Funky
func max : Int -> Int -> Int =
\x \y if (x >= y) x y
Funky is a simple language with a small set of orthogo-
nal features that combine very well. The language was func flip : (a -> b -> c) -> b -> a -> c =
designed and implemented by us and was the topic of our \f \x \y
bachelor’s thesis. This paper is a shortened version of that f y x
thesis. The parts left out in this paper are mainly the thor-
ough description of the language. This shouldn’t cause As we can see, function argument names are not spec-
any trouble to people generally familiar with functional ified before the equals sign, instead, all arguments are in-
programming, for whom this paper is intended anyway. troduced by abstractions. Funky is very consistent with
Now we’ll briefly describe the important aspects of the this – literally all variables in expressions are introduced
language so that the following sections are easy to under- by abstractions, there isn’t a single case otherwise.
Approaching side-effects in pure functional programming by interpreting data structures as recipes 19
Abstractions are very concise – they consist only of a In the case of need or a desire for clarification, any ex-
backslash followed by the name of the bound variable fol- pression can be type-annotated with a colon:
lowed by the body of the abstraction (function). Multi-
ple arguments are introduced simply by nesting abstrac- ((x : Int) + (y : Int) : Int)
tions. The body of an abstraction always spans until the
end of the scope (for example, inside parentheses it spans 1.3 Records
until the closing parenthesis), which prevents unnecessary
parentheses in many cases. Records are one of the three means of creating own types
Function names consisting solely of special characters in Funky (the other two are unions and aliases). Records
(no letters or numbers) are infix functions. All infix func- are similar to structs from C or records from Pascal. They
tions have the same precedence, which is lower than the are compound types, a single value containing multiple
precedence of regular prefix function application and are fields.
all right-associative. This is to free the programmer from A record definition is signified by the record keyword,
the burden of manually specifying the precedence and as- which is followed by the record name, a list of type vari-
sociativity of infix functions. Right-associativity was cho- ables required by the record (if any), and an equals sign
sen because it’s more often useful than left-associativity. followed by a comma-separated list of fields. All fields
The type system is very similar to the one in Haskell. must be type annotated.
The main difference is that Funky has no type-classes and
record Pair a b = first : a, second : b
disallows higher-kinded types (type variables with argu-
ments), which shall not be confused with higher-order record Person =
types that are supported in Funky. name : String,
Quite unusually and very importantly, Funky supports age : Int, # trailing comma is allowed
function overloading – defining multiple functions with
the same name, but different types. For example: record Vec4D =
x : Float,
# map applies a function to all elements of y : Float,
# a list z : Float,
func map : (a -> b) -> List a -> List b = w : Float,
\f
fold< ((::) . f) [] # :: is cons Funky generates a few functions per record: the con-
structor and a getter and an updater for each field. For
# map applies a function to the potential example, in case of the Person record, these functions get
# content of a maybe generated:
func map : (a -> b) -> Maybe a -> Maybe b =
\f \maybe func Person : String -> Int -> Person
switch maybe
case nothing nothing func name : Person -> String
case just \x just (f x) func name : (String -> String) -> Person ->
Person
# useless converts a list of maybe floats to
# a list of maybe ints func age : Person -> Int
# ^ that's a useless comment func age : (Int -> Int) -> Person -> Person
func useless : List (Maybe Float) ->
List (Maybe Int) = The constructor takes the values of the record fields in
map (map int) order and returns an instance of the record. A getter sim-
ply takes a record value and returns the given field. An
This comes very handy in many situations – program- updater is more peculiar. It takes a function mapping the
mer doesn’t have to think about names too much and sim- record field to a new value and a record value. Then it re-
ilar behavior on different types may be assigned the same turns a copy of the original record where the given field is
function name. Also, as we’ll see, records are thereby al- replaced by the result of applying the function to its orig-
lowed to share field names, which is something that causes inal value. This approach to updaters was chosen for two
a lot of trouble in Haskell. reasons: first is that this is usually what we want to do:
Function overloading is not arbitrary – overloaded func- to update a field according to its previous value; the sec-
tions with colliding types are disallowed. Colliding types ond reason is that updaters compose very well in this form
are such types that can be specialized (their type variables (they were inspired by Lenses from Haskell).
can be substituted) into the same type. This is because it For example, let’s work with these two records:
would be impossible to determine, or even easily express,
which of the colliding functions should be used in many record Point = x : Int, y : Int
situations.
20 Michal Štrba and Richard Ostertág
record Segment = func length : List a -> Int =
start : Point, \list
end : Point, switch list
case empty
Say we have a variable seg which is a segment. We can 0
compose getters to access the X coordinate of the starting case (::) \x \xs
point: 1 + length xs
(x . start) seg Each case is followed by the name of the alternative,
which is followed by a function that accepts the argu-
But we can also compose updaters to change the value ments of the alternative and returns the final result of the
of that coordinate and get an updated segment: switch/case structure. The arguments in the case body
don’t have to be mentioned explicitly – the above function
(start . x) (+ 4) seg could’ve been written like this:
To replace the value of a field with a value independent func length : List a -> Int =
of the previous value of the field, we use the const func- \list
tion (const x takes one argument and always returns x): switch list
case empty 0
(start . x) (const 0) seg case (::) const ((1 +) . length)
Let’s define one more record:
1.5 Aliases
record Plan = segments : List Segment
The simplest way of making type names is by aliasing.
Alias simply defines another name for an existing type,
The map function can also be used as an updater on a
albeit a possibly more complex one. For example, the
list, and so we can write this to update all Y coordinates of
String type from the standard library is defined like this:
all the end points of the segments in a plan:
alias String = List Char
(segments . map . end . y) (* 2) plan
The alias is perfectly identical to the type on right side
The whole main motivation for the creation of the huge
of the equals side. They may be used interchangeably.
and abstract Lens library in Haskell is avoided in Funky
Aliases may also have type variables.
simply by providing clever updater functions.
1.4 Unions 2 Vertical code
Unions are just like data types in Haskell. Their definition No feature is useful unless the benefits of its employment
is signified by the union keyword followed by the name of outweigh the costs – the feature must be viable. The new
the union and a list of type variables, then an equals sign approach to side-effects described in this paper is viable in
followed by a | separated list of alternative forms. For Funky, but not in Haskell, or any other traditional purely
example (:: is cons, the list prepend function): functional language. What makes the difference? Surpris-
ingly, only two subtle syntactic differences, nothing major
union Bool = true | false at the first sight. Yet, these two syntactic differences make
code that is otherwise ugly and messy in Haskell beauti-
union Maybe a = nothing | just a
ful and readable in Funky. Of course, some code that is
beautiful and readable in Haskell is in its original form not
union List a = empty | a :: List a
possible in Funky at all. But, we’re not talking about just
Funky generates a single constructor function for each any code here: we’re talking about the kind of code that
alternative, which takes all the arguments in the order and makes the new approach to side-effects viable and that is
returns an instance of the union. For example, these func- – vertical code.
tions get generated for the List union: Writing code that reads top to bottom and composes ver-
tically has always been the domain of imperative program-
func empty : List a ming. “Do this, then do that, then repeat this until some
func (::) : a -> List a -> List a other thing happens” is a very natural way of expressing
programs. Programmer reads the code top to bottom, re-
To get values out of a union value, Funky introduces a membering the invariants as they occur, until they form a
special switch/case structure that looks like this: complete picture of the program in their mind.
Approaching side-effects in pure functional programming by interpreting data structures as recipes 21
Functional programs tend to compose differently. In- func n! : Int -> Int =
stead of a series of statements, functional programs are \n
mere expressions constructed mostly from function appli- if (n <= 0) 1 (n * n! (n - 1))
cation and abstraction. An expression has no natural “or-
der of execution”, it’s usually a function application whose This particular code isn’t too bad, but it’s easy to con-
arguments are yet other expressions. The arguments can ceive situations where using the if as a simple, one-line
be understood in any order. However, if the arguments are conditional expression would be outright unacceptable.
large expressions containing more function applications Funky introduces a special syntactic concept: the semi-
with still more large expressions as their arguments, the colon. All it does is it puts everything that’s after it (in the
whole thing becomes very inconvenient to read and un- scope) inside parentheses. It works just like the $ function
derstand. The reason is that humans operate with only a in Haskell. So we can rewrite this:
finite (and fairly small) amount of working memory. Un-
if (n <= 0) 1 (n * n! (n - 1))
derstanding an expression that is syntactically a wide and
deep tree requires a lot of working cognitive memory, so
into this:
it’s hard.
Of course, designers of functional languages are well if (n <= 1) 1; n * n! (n - 1)
aware of this. Many syntactic features present in those lan-
guages are specially designed to tackle this issue. These and then split it into multiple lines:
features include: pattern matching, guards, let bindings,
where bindings, or Haskell’s do notation. However, none if (n <= 1)
of these features solves the problem fully, because they 1;
don’t nest very well. n * n! (n - 1)
The motivation for designing Funky arose from the har-
mony experienced while playing with the pure λ -calculus A more involved example is the infamous FizzBuzz
and from the frustration with existing functional lan- problem. Here’s a function that returns the correct output
guages. Experimenting with the pure λ -calculus gave us for each number:
the opportunity to step back – see the bigger picture. We
saw that instead of adding new syntactic features like the func fizzbuzz : Int -> String =
\number
ones described above, all that was needed was to improve
if ((number % 15) == 0)
the core – make writing ordinary expressions more concise "fizzbuzz";
and make it possible to naturally split them into multiple if ((number % 3) == 0)
lines. It turned out that this was enough. Funky has no "fizz";
pattern matching, guards, let binding syntax, nor anything if ((number % 5) == 0)
analogous to the Haskell’s do notation. "buzz";
The two subtle syntactic features that make it possible string number
are: concise trailing lambdas and the semicolon. We’ll
demonstrate them on concrete examples: the if and the Here, if is used to express a series of cases terminated
let function in Funky. by a catch-all case. The built-in if structure in Haskell is
not suitable for such purposes – one would have to use
guards instead. But as we’ve already said, guards don’t
2.1 if and let nest so well.
In Funky, if is a simple function from the standard library In contrary, Funky’s if function nests perfectly. Both
(body omitted): “then” and “else” expressions may be arbitrarily large,
nested, vertical expressions.
func if : Bool -> a -> a -> a
if condition (
It takes a condition and two arguments of the same type: then
then and else, and returns back the correct one. It can be ...
used as a simple conditional expression, just like the if );
structure in Haskell, or the ternary operator in C: else
...
func min : Int -> Int -> Int =
\x \y Similarly to if, let bindings (variable assignments) are
if (x < y) x y not a built-in language construct in Funky. Instead, let is
a function from the standard library. Here’s its full defini-
But if the expressions are more complex, this becomes tion (including the body):
hard to read. Let’s take the factorial function as an exam-
ple (we’ll call it n! because Funky allows this): func let : a -> (a -> b) -> b = \x \f f x
22 Michal Štrba and Richard Ostertág
The function let takes a value and then takes a function The last argument to a semicolon kind vertical function
to which it passes the value as an argument. Thanks to can be usually understood as a continuation, analogous to
the Funky’s concise function construction (lambda/back- CPS (continuation passing style).
slash), this function is a perfectly viable replacement for a The if function is an example of a semicolon kind ver-
let binding construct built directly into the language. tical function.
In some cases, the above form is violated and the return
let "me stay by your" type doesn’t match the last argument, while the function
(\side reverse side ++ " " ++ side) is still used vertically. However, the signature usually fol-
lows the mentioned form.
Here we call the let function with two arguments: the
The second kind we call trailing lambda kind vertical
first one is the string "me stay by your" and the second
functions. Their signatures have this general form:
one is a function. Calling let passes the string as the ar-
gument to the function and the whole expression evaluates
... -> (... -> V ) -> V
to "ruoy yb yats em me stay by your".
Thanks to the Funky’s trailing lambda syntax (function The vertical function passes some arguments to the con-
body spans until the end of scope), we can remove the tinuation, which then takes on the same role as with the
parentheses around the function: semicolon kind vertical functions. Again, some vertical
let "me stay by your" functions may violate this form, but those cases are rare.
\side reverse side ++ " " ++ side The let function is an example of a trailing lambda
kind vertical function.
Furthermore, we can split the expression into two lines,
yielding a very readable piece of code:
2.3 Viability
let "me stay by your" \side
reverse side ++ " " ++ side The main reason why vertical functions along with their
usage haven’t seen the light of the day in traditional func-
Now, instead of thinking in terms of function applica- tional languages, such as Haskell is that they’re hardly vi-
tions and abstractions, we understand the code as an as- able there. The reasons are very subtle. After all, Haskell
signment to a variable (immutable, of course) followed by supports anonymous functions and has the $ function anal-
the resulting expression. ogous to the Funky’s semicolon.
To assign multiple variables, we can just stack let as- To demonstrate this, let’s take a function for generating
signments: all permutations of a list (the code contains some functions
we haven’t discussed, and won’t discuss, in this paper, but
let (filter prime? (count 2)) \primes the understanding of what the function does is irrelevant
let (take-while (< 100) primes) \small-primes now):
let (length small-primes) \count
string count ++ " small primes (< 100)" func permutations : List a -> List (List a) =
\list
This expression evaluates to: "25 small primes (< if (empty? list)
100)". (yield []; empty);
pick (permutations (rest list)) \tail
pick (insert (first list) tail) \perm
2.2 Vertical functions yield perm;
empty
Some function are suitable for composing code vertically,
either with the help of the semicolon or trailing lambdas.
In Haskell, the above code could be rewritten roughly
We’ve seen both in the previous section on the if and the
like this:
let function. Other functions aren’t suitable for that. Now
we’ll describe a small theory about these functions that al- permutations list =
low vertical composition. We call them vertical functions. if null list
There are two main kinds of vertical functions: those then yield [] $ empty
that utilize the semicolon and those that involve trailing else
lambdas. Both are characterized by their signature (type). pick (permutations (rest list)) (\tail ->
The first kind we call semicolon kind vertical functions. pick (insert (first list) tail) (\perm ->
Their signatures have this general form (where V is an ar- yield perm $
bitrary type and ... is an arbitrary sequence of -> appli- empty))
cations):
In case if was a function in Haskell, instead of a built-in
... -> V -> V construct, we can improve the code a bit:
Approaching side-effects in pure functional programming by interpreting data structures as recipes 23
permutations list = given task. In this paper, we’ll examine the interpreter for
if (null list) command-line applications.
(yield [] $ empty) $
pick (permutations (rest list)) (\tail ->
pick (insert (first list) tail) (\perm -> 3.1 Interpreters
yield perm $ Funky’s runtime is currently written in Go. As interpreters
empty))
need to interact with the runtime, they too must be writ-
We could improve the code a little bit more by removing ten in Go. This may be expanded to more languages in
the parentheses around anonymous functions and inserting the future, for example, it would be useful to write Funky
a few more dollars: interpreters in Java or C++.
To write an interpreter we need to import the
permutations list = "github.com/faiface/funky" package and call the
if (null list) funky.Run function. This function does all the job re-
(yield [] $ empty) $ garding command-line flags, reading, parsing, and compil-
pick (permutations (rest list)) $ \tail -> ing source files, and returns a runtime value representing
pick (insert (first list) tail) $ \perm -> the data structure, the recipe, back to the programmer.
yield perm $
empty package main
The result is still fairly bad, though. The dollar signs all import "github.com/faiface/funky"
over the place stick out too much and the arrow at the end
of the argument list of an anonymous function is similarly func main() {
detrimental to the overall aesthetics. It’s no wonder that program := funky.Run("main")
vertical functions weren’t in fact invented in Haskell. Of }
course, one would use pattern matching or the do notation The funky.Run function takes one argument: the
to write a similar function in Haskell. However, neither name of the function containing the recipe value.
of those features nests very well. The approach taken by The return type of the funky.Run function is
Funky is more general. *runtime.Value. The runtime package is located
at "github.com/faiface/funky/runtime". The
3 Side-effects and interpreters *runtime.Value type provides several methods we can
use to interact with the value:
Funky’s approach to side-effects is unique among func- func (*runtime.Value) Char() rune
tional languages, but after exploring it, this fact comes func (*runtime.Value) Int() *big.Int
rather surprising. The approach is so obvious that it’s quite func (*runtime.Value) Float() float64
curious no other language (to our knowledge) has adopted func (*runtime.Value) Field(i int)
it before. *runtime.Value
The idea is this: a program in Funky is just a value, a func (*runtime.Value) Alternative() int
data structure. Then there is a special program called in- func (*runtime.Value) Apply(
terpreter. This program interacts with the Funky’s runtime arg *runtime.Value) *runtime.Value
(evaluator) to examine this data structure, which serves the
role of a recipe. A recipe then tells the interpreter what to // these three are implemented using the
// above six
do. Contrary to ordinary recipes, these recipes are gen-
func (*runtime.Value) Bool() bool
erated, combined, recursive, and so on, all the goods of func (*runtime.Value) List() []*runtime.Value
functional programming. func (*runtime.Value) String() string
The Funky programming language itself has no intrinsic
concept of side-effects. In fact, the interpreters themselves The Char, Int, and Float methods are used to retrieve
add no real concept of side-effects either. Everything still values of Funky’s built-in types. The Field function re-
remains just a value. The recipe is a value that can be trans- turns the i-th field of a record, or the i-th argument to a
formed and manipulated just like any other value. This is union constructor. The Alternative method returns the
where a lot of expressive power comes in as we’ll see. index of the union constructor of the value. And lastly, the
There isn’t just one interpreter. In fact, any Funky pro- Apply function takes another runtime value and applies it
grammer can make their own interpreters for their own to the function in the receiving runtime value and returns
special purposes. Each interpreter works with a different the result of this application.
data structure describing the desired side-effects. One in- All the above functions crash if they’re used on values
terpreter is intended for command-line applications. An- of wrong types. For example, calling Alternative on
other one is for web servers. And yet another is for 2D a record value crashes, and calling Char on a float value
games. Each interprets a data structure specialized for the likewise.
24 Michal Štrba and Richard Ostertág
The last three functions are just for convenience because For example, here’s a “cat” program, a program that
booleans, lists, and strings are very widely used types. simply copies the input to the output:
The interpreter sometimes needs to fabricate new run-
func main : IO =
time values not originating in the Funky program. For
getc \c
example, when a command-line interpreter loads a char- putc c;
acter from the input, it needs to make a character value main
and pass it to the program. These functions are provided
in the "github.com/faiface/funky/runtime" pack- This program has no done node, it’s an infinite data
age for this purpose: structure. Before we run it, though, we need an interpreter.
Here it is (badly formatted, because the lack of horizontal
func MkChar(c rune) *runtime.Value space):
func MkInt(i *big.Int) *runtime.Value
func MkFloat(f float64) *runtime.Value package main
func MkRecord(fields ...*runtime.Value)
*runtime.Value import (
func MkUnion(alt int, fields ...*runtime.Value) "bufio"
*runtime.Value "io"
"os"
// these three are, again, implemented using "github.com/faiface/funky"
// the above five "github.com/faiface/funky/runtime"
func MkBool(b bool) *runtime.Value )
func MkList(elems ...*runtime.Value)
*runtime.Value func main() {
func MkString(s string) *runtime.Value program := funky.Run("main")
in := bufio.NewReader(os.Stdin)
Their meaning is clear, so we’ll avoid explaining that. out := bufio.NewWriter(os.Stdout)
defer out.Flush()
3.2 Interactive command-line programs loop:
for {
The data structure serving the role of a recipe we chose for switch program.Alternative() {
simple interactive command-line programs is strikingly case 0: // done
simple: break loop
case 1: // putc
union IO = out.WriteRune(program.Field(0).Char())
done | program = program.Field(1)
putc Char IO | case 2: // getc
getc (Char -> IO) | out.Flush()
r, _, err := in.ReadRune()
It is a kind of a linked list, with three types of nodes. if err == io.EOF {
One signals the end of the program: done. The next one break loop
– putc – says that a character should be printed and the }
program should continue in some way. The first argument program = program.Field(0).
to putc is the character to be printed. The other argument Apply(runtime.MkChar(r))
is the rest of the program – a continuation. The last node }
– getc – is requesting a character from the input. It has }
one argument: a function. The interpreter should read the }
character and pass it as an argument to this function. The The interpreter enters a loop where it checks the pro-
function then returns the rest of the program. gram node type and acts accordingly, always proceeding
Funky always generates constructor functions for a to the continuation until reaching the done node.
union and these are the ones generated for IO (bodies omit- Now we can run the “cat” program (user input is em-
ted, internal to the compiler/runtime): phasized, funkycmd is the name of the interpreter):
func done : IO $ funkycmd cat.fn stdlib/*.fn stdlib/
func putc : Char -> IO -> IO funkycmd/*.fn
func getc : (Char -> IO) -> IO hello, cat!
hello, cat!
The imporant thing to notice is that putc is a semicolon do you cat?
kind vertical function and getc is a trailing lambda kind do you cat?
vertical function. This makes it easy to compose interac- you do cat!
tive command-line programs in a natural, imperative-like you do cat!
style. ^D
Approaching side-effects in pure functional programming by interpreting data structures as recipes 25
At the end, the user pressed the Ctrl+D combination to This is a common pattern in Funky. It’s used to avoid cre-
signal the end of file which caused the program to finish. ating unnecessary helper functions in places where the re-
We can’t do much with just done, putc, and getc, not cursion needs to remember more arguments than the orig-
at least conveniently. That’s why we’ll now show how to inal function has. The recursion in our case has to remem-
define more complex functions on top of the basic ones to ber the accumulated string starting from an empty string.
get a more powerful – and sometimes surprisingly power- The |> function (x |> f = f x) passes the empty string
ful – behavior. as the initial value to the recursion.
With the help of print, println, and scanln, we can
make more involved programs. Here’s a number guessing
3.3 print, println, scanln game:
The first function with a more complex behavior that we’re
func main : IO =
going to tackle is print. The print function prints a
println "Think a number from 1 and 100.";
whole string instead of a single character as putc does 100 |> 1 |> fix \loop \min \max
(it doesn’t do it, but it instructs the interpreter to do it, and let ((min + max) / 2) \mid
similarly, print instructs the interpreter to print a string). print (string mid ++ "? ");
scanln \response
func print : String -> IO -> IO = if (response == "less")
\s \next (loop min (mid - 1));
if (empty? s) if (response == "more")
next; (loop (mid + 1) max);
putc (first s); if (response == "yes")
print (rest s); (println "Yay!"; done);
next println "Say one of less/more/yes.";
loop min max
The print function takes a string and a continuation
– the rest of the program. Then it recursively describes And here’s an example running of the program:
how to print the string – print the first character and then
continue printing the rest until we printed the whole string. Think a number from 1 and 100.
Alternatively, print can be defined with a right fold: 50? no
Say one of less/more/yes.
func print : String -> IO -> IO = 50? nope
\s \next fold< putc next s Say one of less/more/yes.
50? less
Now we can use print to create a convenience 25? more
println function, which additionally prints a newline at 37? more
the end of the string: 43? less
40? more
func println : String -> IO -> IO = 41? more
print . (++ "\n") 42? yes
Yay!
The next function we’re going to define is scanln,
which scans a whole line from the input (excluding the 3.4 ungetc, skip-whitespace, scan
newline character) and passes its content. While print
and println prepended some putc nodes to the contin- The print, println, and scanln functions only
uation, scanln prepends some getc nodes, accumulates “prepend” operations to the continuation. But since IO is
the line and passes it to the continuation, which accepts a fully transparent data structure, we can define transfor-
one argument: the line string. It’s a trailing lambda kind mations that penetrate it, twist it around, or transform it in
vertical function. any other way.
The first and a very useful example of such a function
func scanln : (String -> IO) -> IO =
is ungetc. It is used to “push a character back on the in-
\f
put”, so that the next getc call will get it. The plain IO
"" |> fix \loop \s
getc \c data structure has no such functionality and we can’t get
if (c == '\n') any similar behavior just by sequencing done, putc, and
(f (reverse s)); getc. What we need is we need to write a function that
loop (c :: s) takes a character and a continuation, then searches through
the continuation until it finds the first getc node, and fi-
The body makes use of the fix function (fix-point op- nally passes the character to that node. Since IO is just a
erator, fix f = f (fix f)) to insert inline recursion. transparent data structure, this is quite easy:
26 Michal Štrba and Richard Ostertág
func ungetc : Char -> IO -> IO = It uses the skip-whitespace at the beginning, then it
\c \io enters a loop where it accumulates the word until it reaches
switch io a whitespace again. This whitespace wasn’t supposed to
case done be read by scan, so it’s put back on the input by ungetc.
done Here’s a simple calculator program demonstrating the
case putc \d \jo
scan function:
putc d;
ungetc c; func main : IO =
jo print "> ";
case getc \f scan \x-str
f c scan \op
scan \y-str
The ungetc function examines the top node of the con- # float x-str returns Maybe Float
tinuation and recursively propagates itself down the data # hence the call to extract
structure until it finds a getc node. When it does, it passes let (extract (float x-str)) \x
the character to the function of the getc node and turns it let (extract (float y-str)) \y
into its result. println (
The ungetc function is particularly useful for imple- if (op == "*") (string (x * y));
menting the scan function. We’ve already implemented if (op == "/") (string (x / y));
"invalid operation: " ++ op
scanln, which scans whole lines. The scan function, on
);
the other hand, scans the next full word (a continuous se- main
quence of characters not containing any whitespace) on the
input. To do that it first needs to skip all the whitespace And here’s its running:
preceding the word, then scan the word, but avoid scan-
ning the first whitespace character after the word. We’ll > 10 / 3
see how ungetc comes to help with this. 3.3333333333333335
First, we’ll make a general function for skipping whites- > ^D
pace on the input:
3.5 reverse-lines
func whitespace? : Char -> Bool =
\c The last example in our exploring of the possibilities of the
any (c ==) [' ', '\t', '\n', '\r'] IO data structure is a rather peculiar one: not practically
useful, but quite showing of the potential present here.
func skip-whitespace : IO -> IO = The function is called reverse-lines and its job is
\next to reverse all the lines on the output. Lines come to the
getc \c output in two ways: either a sequence of putc nodes ter-
if (whitespace? c) (
minated by a putc of a newline, or a sequence of putc
skip-whitespace;
next nodes terminated by a getc node – all the pending output
); must be shown to the user before requesting input and the
ungetc c; user input will be entered by a newline.
next
func reverse-lines : IO -> IO =
\io
The skip-whitespace function continuously reads
io |> "" |> fix \loop \s \(io : IO)
characters from the input until it reaches a non-whitespace switch io
character. It wasn’t supposed to read this character, but it case done
needed to in order to determine whether to stop skipping done
or not. So it uses ungetc to put it back on the input. case putc \c \jo
With the help of skip-whitespace, here’s scan: if (c == '\n') (
println s;
func scan : (String -> IO) -> IO = loop "";
\f jo
skip-whitespace; );
"" |> fix \loop \s loop (c :: s);
getc \c jo
if (whitespace? c) ( case getc \f
ungetc c; print s;
f (reverse s) getc \c
); loop "";
loop (c :: s) f c
Approaching side-effects in pure functional programming by interpreting data structures as recipes 27
The reverse-lines function starts a loop using inline
recursion with fix to accumulate the line to be reversed.
It removes the original putc nodes from the data structure
and keeps accumulating until reaching one of the above-
mentioned conditions for terminating a line. When one
of the conditions occurs, it transforms the accumulated re-
versed line into a proper series of putc calls using print
or println.
Here’s the small program augmented by
reverse-lines:
func main : IO =
reverse-lines;
print " What's your name? ";
scan \name
println ("Hello, " ++ name ++ "!");
done
And here’s its running:
?eman ruoy s'tahW
!lahciM ,olleH
Unimportant to this paper, this reverse-lines func-
tion isn’t perfect. For example, it fails to reverse the lines
of the “cat” program, because that one has a getc before
each putc and so no full line ever gets accumulated. The
solution to this problem is left as an exercise to the reader.
4 Conclusion
Combining the concept of vertical code with the new ap-
proach to side-effects in a language that makes it viable
resulted in a whole new approach to structuring purely
functional code. We saw that purely functional programs
can be expressed in a way that is familiar to an imperative
programmer. In Funky, this doesn’t come from artificially
implanted syntactic features, but instead stems naturally
from the core, general concepts in the language itself.
At the moment, Funky is virtually unknown. We will
make all the efforts to get the word out there, because we
believe we’ve got something worthy in our hands.