7Several Features as a Functional Programming Language

This chapter introduces several Egison features that facilitate functional programming.

7.1Anonymous Parameter Functions

Anonymous parameter functions allow you to define functions without naming the arguments. Lambda expressions let you omit the naming of the function itself. Anonymous parameter functions, which also let you omit the naming of arguments, can be thought of as taking this idea one step further. For example, an anonymous parameter function that multiplies the first argument by 10 and adds the second argument can be defined as follows.

2#($1 * 10 + $2) 1 2
-- 12

The 2 before # indicates that this defines a 2-argument function. The $1 and $2 appearing in the function body represent the first and second arguments, respectively.

Anonymous parameter functions have two variants: one that takes a tuple as its argument and one that takes a list. These two variants are defined by enclosing the number before # in parentheses or brackets. Enclosing the number before # in () defines an anonymous parameter function that takes a tuple as its argument.

(2)#($1, $2) (10, 20)
-- (10, 20)

Enclosing the number before # in [] defines an anonymous parameter function that takes a list as its argument.

[2]#($2, $1) [10, 20]
-- (20, 10)

7.2Anonymous matchAll Functions and Anonymous match Functions

When defining functions, it is common to immediately pattern-match on a formal parameter. In such cases, the formal parameter name serves no purpose other than as the target of that pattern match. To address this issue, anonymous matchAll functions and anonymous match functions are provided.

First, let us introduce anonymous matchAll functions. An anonymous matchAll function is defined by writing matchAll immediately after \ without a space. In this case, the pattern-matching target is omitted. This is because the argument of the anonymous matchAll function becomes the target.

\matchAll as list something with
  | $hs ++ $ts -> (hs, ts)

An anonymous match function can be defined simply by replacing matchAll with match in an anonymous matchAll function.

\match as list something with
  | nil -> True
  | _ -> False

7.3Defining Infix Operators

Egison provides the ability for users to define new infix operators. To declare an infix operator, use infix, infixl, or infixr. infix, infixl, and infixr are used to define non-associative, left-associative, and right-associative operators, respectively. infix, infixl, and infixr all take three arguments. The first argument takes the keyword expression or pattern to specify whether the infix operator being defined is a function or a pattern constructor. The second argument takes an integer value specifying the precedence of the infix operator being defined. The third argument takes the name of the infix operator being defined.

As an example of defining a function used as an infix operator, the logical conjunction && is defined as follows. The type annotation indicates that it takes two boolean values as arguments and returns a boolean value.

infixr expression 5 &&

def (&&) (a: Bool) (b: Bool) : Bool := match (a, b) as (eq, eq) with
  | (#True, #True) -> True
  | _              -> False

As an example of defining a pattern constructor used as an infix operator, the join pattern ++ is defined as follows. The type annotation indicates that it takes a type parameter {a} and a matcher argument (m: Matcher a), and returns a matcher for the list type [a].

infixl pattern 7 ++

def list {a} (m: Matcher a) : Matcher [a] := matcher
  | $ ++ $ as (list m, list m) with
    ...
OperatorDescriptionPrecedence
^Exponentiation8
*Multiplication7
/Division7
%Remainder7
.Tensor product7
+Addition6
-Subtraction6
::Cons5
++Append5
=, <= >=, <, >Comparison4
&&Logical conjunction3
||Logical disjunction2
$Function application0
List of infix operators (functions)

OperatorDescriptionPrecedence
^Exponentiation8
*Multiplication7
/Division7
+Addition6
::Cons5
++Append5
&And-pattern3
|Or-pattern2
List of infix operators (patterns)

7.4Type Classes

Egison supports type classes. Type classes are a mechanism for abstracting common behavior across multiple types. Egison's type classes have syntax and semantics similar to Haskell's type classes.

7.4.1Defining Type Classes

Type classes are defined using the class keyword. A type class definition includes a type variable and the signatures of functions required for that type variable. For example, the Eq type class representing types that can be compared for equality is defined as follows.

class Eq a where
  (==) (x: a) (y: a) : Bool
  (/=) (x: a) (y: a) : Bool

This definition means that “for a type a to be an instance of Eq, it must provide operations == and /= that take two values of type a and return a Bool.”

Egison also supports superclass declarations using the extends keyword. A type class can declare one or more superclasses, meaning that any type that is an instance of the subclass must also be an instance of the superclass(es).

Using these features, Egison defines the following algebraic type class hierarchy for numeric types. First, the additive hierarchy is defined as follows.

class AddSemigroup a where
  (+) (x: a) (y: a) : a

class AddMonoid a extends AddSemigroup a where
  zero : a

class AddGroup a extends AddMonoid a where
  neg (x: a) : a

AddSemigroup provides addition, AddMonoid extends it with a zero element, and AddGroup further extends it with negation.

Similarly, the multiplicative hierarchy is defined as follows.

class MulSemigroup a where
  (*) (x: a) (y: a) : a

class MulMonoid a extends MulSemigroup a where
  one : a

class MulGroup a extends MulMonoid a where
  inv (x: a) : a

These hierarchies are combined into composite algebraic structures. A type class can extend multiple superclasses, separated by commas. A type class with no methods of its own serves as a marker class that simply combines its superclasses.

class Ring a extends AddGroup a, MulMonoid a
class Field a extends Ring a, MulGroup a

Ring requires both additive group and multiplicative monoid structure, while Field additionally requires multiplicative inverses.

Further extensions for computer algebra are also defined.

class GCDDomain a extends Ring a where
  gcd (x: a) (y: a) : a

class EuclideanDomain a extends GCDDomain a where
  divMod (x: a) (y: a) : (a, a)

7.4.2Type Class Instances

To make a concrete type an instance of a type class, use the instance keyword. For example, to make the Integer type an instance of Eq, write the following.

instance Eq Integer where
  (==) x y := x = y
  (/=) x y := not (x == y)

An example of making the MathValue type an instance of the algebraic type class hierarchy is as follows. Each level of the hierarchy requires its own instance definition.

instance AddSemigroup MathValue where
  (+) x y := plusForMathValue x y

instance AddMonoid MathValue where
  zero := 0

instance AddGroup MathValue where
  neg x := minusForMathValue 0 x

instance MulSemigroup MathValue where
  (*) x y := multForMathValue x y

instance MulMonoid MathValue where
  one := 1

instance MulGroup MathValue where
  inv x := divForMathValue 1 x

Marker class instances (classes with no methods) can be declared without a where clause.

instance Ring MathValue
instance Field MathValue

Type class instance definitions can also include type class constraints. For example, when making the Tensor a type an instance of Eq, if the element type a also needs to be an instance of Eq, write the following.

instance {Eq a} Eq (Tensor a) where
  (==) t1 t2 := t1 = t2
  (/=) t1 t2 := not (t1 == t2)

7.4.3Using Type Class Constraints

By using type classes, you can impose constraints on polymorphic functions. Type class constraints are written in curly braces {} in the function's type signature. For example, a function that compares two values for equality can be defined as follows.

def eqAs {Eq a} (m: Matcher a) (x: a) (y: a) : Bool := ...

This type signature means “when type a is an instance of Eq, eqAs takes a Matcher a, an a, and an a, and returns a Bool.”

Multiple type class constraints can also be imposed. For example, a function that requires both ordering and equality can be written as follows.

def compare {Eq a, Ord a} (x: a) (y: a) : Ordering := ...

Using the algebraic type class hierarchy, subtraction and division can be defined as derived operations using the minimum necessary type class constraints.

def (-) {AddGroup a} (x: a) (y: a) : a := x + neg y
def (/) {Field a} (x: a) (y: a) : a := x * inv y

Similarly, sum and product are defined with precise constraints.

def sum {AddMonoid a} (xs: [a]) : a := foldl (+) zero xs
def product {MulMonoid a} (xs: [a]) : a := foldl (*) one xs

Type class constraints can be used not only in function definitions but also in matcher definitions. For example, the sortedList matcher requires that the element type be orderable (an instance of Ord).

def sortedList {Ord a} (m: Matcher a) : Matcher [a] := matcher
  ...

7.4.4Type Class Implementation: Dictionary-Passing Style

Egison's type classes are implemented using dictionary-passing style. This means that a function with type class constraints is transformed into a function that actually takes a dictionary containing the type class methods as an argument.

For example, the following function with a type class constraint

def double {AddSemigroup a} (x: a) : a := x + x

is internally transformed into a function that takes a dictionary parameter.

def double (dict_AddSemigroup_a) (x: a) : a :=
  (dict_AddSemigroup_a_"plus") x x

Here, dict_AddSemigroup_a is a hash (dictionary) containing the methods of the AddSemigroup a instance (in this case, +).

When calling a function on a concrete type, the appropriate instance dictionary is automatically passed. For example, double 1 is transformed into the following.

double addSemigroupInteger 1

Here, addSemigroupInteger is the dictionary for the AddSemigroup Integer instance.

This dictionary-passing style achieves dynamic dispatch of type classes (selection of methods based on the type at runtime). It also correctly handles calls between functions with type class constraints. For example, in the following functions

def myPlus {AddSemigroup a} (x: a) (y: a) : a := x + y
def myPlus2 {AddSemigroup a} (x: a) (y: a) : a := myPlus x y

the dictionary received by myPlus2 is correctly passed to myPlus.

7.5IO Input/Output

Egison, whose default evaluation strategy is lazy evaluation, has special syntax for writing programs with side effects. Egison is a language with a static type system, and it uses the same approach as Haskell for writing programs with side effects.

7.5.1The main Function

For example, a program that outputs the string “Hello world!” can be written as follows. The type annotation indicates that it takes a list of strings as command-line arguments and performs IO processing.

def main (args: [String]) : IO () := write "Hello world!\n"

When the command-line option -t is not specified, Egison executes the main function. The above program can be executed as follows.

$ cat hello.egi
def main (args: [String]) : IO () := write "Hello world!\n"
$ egison hello.egi
Hello world!

write is a built-in IO function in Egison. write takes a string as its first argument and prints that string to standard output. There are several other IO functions besides write. Figure 7.5.1 summarizes the complete list.

Function nameDescription
return \(x\)Returns \(x\) as the result of an IO function.
openInputFile \(path\)Opens the file at path \(path\) in read mode and returns an input port to that file.
openOutputFile \(path\)Opens the file at path \(path\) in write mode and returns an output port to that file.
closeInputPort \(port\)Closes the input port \(port\).
closeOutputPort \(port\)Closes the output port \(port\).
readCharReads one character from standard input and returns that character.
readLineReads one line from standard input and returns that string.
writeChar \(c\)Writes the character \(c\) to standard output.
write \(s\)Writes the string \(s\) to standard output.
readCharFromPort \(port\)Reads one character from the input port \(port\) and returns that character.
readLineFromPort \(port\)Reads one line from the input port \(port\) and returns that string.
writeCharToPort \(c\) \(port\)Writes the character \(c\) to the output port \(port\).
writeToPort \(s\) \(port\)Writes the string \(s\) to the output port \(port\).
isEofChecks whether standard input has reached EOF (end of file), returning True if so and False otherwise.
isEofPort \(port\)Checks whether the input port \(port\) has reached EOF, returning True if so and False otherwise.
flushImmediately outputs the contents buffered in standard output.
flushPort \(port\)Immediately outputs the contents buffered in the output port \(port\).
readFile \(path\)Reads the entire contents of the file at path \(path\) and returns it as a string.
rand \(n_1\) \(n_2\)Returns a random integer in the range from \(n_1\) to \(n_2\) (inclusive).
f.rand \(f_1\) \(f_2\)Returns a random floating-point number in the range from \(f_1\) to \(f_2\).
newIORefCreates a mutable variable (reference) and returns that reference. The initial value is undefined.
writeIORef \(ref\) \(x\)Updates the value of the mutable variable referenced by \(ref\) to \(x\).
readIORef \(ref\)Returns the current value of the mutable variable referenced by \(ref\).
readProcess \(cmd\) \(args\) \(input\)Executes the command \(cmd\) with argument list \(args\), provides the string \(input\) as standard input, and returns the standard output as a string.
io \(ioAction\)Executes the IO function \(ioAction\) within a pure function and returns its result (equivalent to unsafePerformIO).
List of IO functions

The first argument of main contains the command-line arguments. Command-line arguments are passed as strings to the first argument of main.

$ cat args.egi
def main (args: [String]) : IO () := write (show args)
$ egison args.egi hello world 1
["hello", "world", "1"]

If you want to make a script created in Egison into a command, you can use a shebang.

$ cat args
#!/usr/local/egison

def main (args: [String]) : IO () := write (show args)
$ args hello world 1
["hello", "world", "1"]

7.5.2The do Expression

The do expression allows you to combine multiple IO functions and execute them in sequence. The do expression corresponds to Haskell's do notation. For example, the following program reads one line of user input and outputs it.

def main (arg: [String]) : IO () := do
  let line := readLine ()
  write line

The do expression can be combined with recursive functions. The following is a program that implements a REPL (Read-Eval-Print Loop) without the Eval part.

def main (arg: [String]) : IO () := repl

def repl : IO () := do
  write "> "
  flush ()
  let line := readLine ()
  write line
  flush ()
  repl

As in Haskell, a syntax for do notation without the offside rule is also supported.

do { print "foo" ; print "bar" ; print "baz" }

Note that Egison's do expression can only be used with the IO monad and cannot be used with the list monad or other monads as in Haskell.

7.5.3The io Function

The io function is a built-in function corresponding to Haskell's unsafePerformIO function. Using the io function, you can call IO functions from within ordinary functions that are not IO functions. This is convenient for tasks such as printf debugging.

The following program rolls two dice and returns the sum of their values.

def dice : Integer := io (rand 1 6)

dice + dice

7.6Built-in Functions

Egison provides a large number of built-in functions (primitive functions). These functions are built into the language implementation and can be used directly by the user. This section introduces the major built-in functions organized by category.

7.6.1Arithmetic Functions

Built-in functions for integer and floating-point arithmetic are provided. Table 7.6.1 shows the major arithmetic functions.

Function nameDescription
i.+ \(x\) \(y\)Returns the sum of integers \(x\) and \(y\).
i.- \(x\) \(y\)Returns the difference of integers \(x\) and \(y\).
i.* \(x\) \(y\)Returns the product of integers \(x\) and \(y\).
i./ \(x\) \(y\)Returns the quotient of integer \(x\) divided by \(y\) as a rational number.
i.modulo \(x\) \(y\)Returns the remainder of integer \(x\) divided by \(y\) (mod).
i.quotient \(x\) \(y\)Returns the quotient of integer \(x\) divided by \(y\) (quot).
i.% \(x\) \(y\)Returns the remainder of integer \(x\) divided by \(y\) (rem).
i.power \(x\) \(y\)Returns integer \(x\) raised to the power of \(y\).
i.abs \(x\)Returns the absolute value of integer \(x\).
i.neg \(x\)Returns integer \(x\) with its sign negated.
i.< \(x\) \(y\)Returns True if integer \(x\) is less than \(y\), False otherwise.
i.<= \(x\) \(y\)Returns True if integer \(x\) is less than or equal to \(y\), False otherwise.
i.> \(x\) \(y\)Returns True if integer \(x\) is greater than \(y\), False otherwise.
i.>= \(x\) \(y\)Returns True if integer \(x\) is greater than or equal to \(y\), False otherwise.
f.+ \(x\) \(y\)Returns the sum of floating-point numbers \(x\) and \(y\).
f.- \(x\) \(y\)Returns the difference of floating-point numbers \(x\) and \(y\).
f.* \(x\) \(y\)Returns the product of floating-point numbers \(x\) and \(y\).
f./ \(x\) \(y\)Returns the quotient of floating-point number \(x\) divided by \(y\).
f.abs \(x\)Returns the absolute value of floating-point number \(x\).
f.neg \(x\)Returns floating-point number \(x\) with its sign negated.
f.< \(x\) \(y\)Returns True if floating-point number \(x\) is less than \(y\), False otherwise.
f.<= \(x\) \(y\)Returns True if floating-point number \(x\) is less than or equal to \(y\), False otherwise.
f.> \(x\) \(y\)Returns True if floating-point number \(x\) is greater than \(y\), False otherwise.
f.>= \(x\) \(y\)Returns True if floating-point number \(x\) is greater than or equal to \(y\), False otherwise.
round \(x\)Rounds floating-point number \(x\) to the nearest integer.
floor \(x\)Returns the largest integer less than or equal to floating-point number \(x\) (floor function).
ceiling \(x\)Returns the smallest integer greater than or equal to floating-point number \(x\) (ceiling function).
truncate \(x\)Returns the integer obtained by truncating the fractional part of floating-point number \(x\).
List of arithmetic functions

Mathematical functions for floating-point numbers are also provided (Table 7.6.1).

Function nameDescription
f.sqrt \(x\)Returns the square root of floating-point number \(x\).
f.exp \(x\)Returns \(e\) (the base of natural logarithms) raised to the power of \(x\).
f.log \(x\)Returns the natural logarithm of floating-point number \(x\).
f.sin \(x\)Returns the sine of \(x\).
f.cos \(x\)Returns the cosine of \(x\).
f.tan \(x\)Returns the tangent of \(x\).
f.asin \(x\)Returns the arcsine of \(x\).
f.acos \(x\)Returns the arccosine of \(x\).
f.atan \(x\)Returns the arctangent of \(x\).
f.sinh \(x\)Returns the hyperbolic sine of \(x\).
f.cosh \(x\)Returns the hyperbolic cosine of \(x\).
f.tanh \(x\)Returns the hyperbolic tangent of \(x\).
f.asinh \(x\)Returns the inverse hyperbolic sine of \(x\).
f.acosh \(x\)Returns the inverse hyperbolic cosine of \(x\).
f.atanh \(x\)Returns the inverse hyperbolic tangent of \(x\).
List of mathematical functions

The mathematical constants pi f.pi (\(\pi \approx 3.14159\)) and Euler's number f.e (\(e \approx 2.71828\)) are defined.

7.6.2String Manipulation Functions

Built-in functions for manipulating strings are provided (Table 7.6.2).

Function nameDescription
pack \(cs\)Converts a list of characters \(cs\) to a string.
unpack \(s\)Converts a string \(s\) to a list of characters.
unconsString \(s\)Returns a tuple of the first character and the remaining string of string \(s\).
lengthString \(s\)Returns the length (number of characters) of string \(s\).
appendString \(s_1\) \(s_2\)Returns the string obtained by concatenating strings \(s_1\) and \(s_2\).
splitString \(pat\) \(s\)Splits string \(s\) by the pattern \(pat\) and returns a list of substrings.
regex \(pat\) \(s\)Matches string \(s\) against the regular expression \(pat\) and returns a triple of the pre-match, match, and post-match parts.
regexCg \(pat\) \(s\)Matches string \(s\) against the regular expression \(pat\) and returns the result including capture groups.
read \(s\)Parses string \(s\) as an Egison expression, evaluates it, and returns the result.
readTsv \(s\)Parses tab-separated string \(s\), evaluates it, and returns the result.
show \(x\)Converts value \(x\) to its string representation.
showTsv \(x\)Converts value \(x\) to a tab-separated format string.
List of string manipulation functions

7.6.3Type Conversion and Type Checking Functions

Built-in functions for type conversion and type checking are provided (Table 7.6.3).

Function nameDescription
itof \(n\)Converts integer \(n\) to a floating-point number.
rtof \(r\)Converts rational number \(r\) to a floating-point number.
ctoi \(c\)Converts character \(c\) to its Unicode code point (integer).
itoc \(n\)Converts integer \(n\) to the corresponding Unicode character.
isInteger \(x\)Returns True if value \(x\) is an integer, False otherwise.
isRational \(x\)Returns True if value \(x\) is a rational number, False otherwise.
List of type conversion and type checking functions

Note: In Egison, MathValue, Integer, and Rational are identified with each other, so isInteger and isRational are used to determine properties of numerical values in the computer algebra system.

7.6.4Tensor-Related Functions

Built-in functions for obtaining tensor information are provided (Table 7.6.4).

Function nameDescription
tensorShape \(t\)Returns the shape (size of each dimension) of tensor \(t\) as a list.
tensorToList \(t\)Converts the elements of tensor \(t\) to a list.
dfOrder \(t\)Returns the order of the differential form \(t\).
addSubscript \(sym\) \(sub\)Adds the subscript \(sub\) to the symbol \(sym\).
addSuperscript \(sym\) \(sup\)Adds the superscript \(sup\) to the symbol \(sym\).
List of tensor-related functions

7.6.5Debugging and Testing Functions

Built-in functions for program debugging and testing are provided (Table 7.6.5).

Function nameDescription
assert \(label\) \(test\)Raises an assertion error containing the label \(label\) if the test \(test\) is not True.
assertEqual \(label\) \(actual\) \(expected\)Raises an assertion error containing the label \(label\) if values \(actual\) and \(expected\) are not equal.
List of debugging and testing functions

7.7The seq Expression

The seq expression is used when you want to partially evaluate a program strictly rather than lazily. While lazy evaluation is convenient, it can sometimes waste memory and be inefficient. Partially evaluating a program strictly can improve efficiency. The seq expression strictly evaluates its first argument and then evaluates its second argument. For example, it is known that foldl can be made more efficient by using the seq expression as follows. The type annotation indicates that it takes a folding function, an initial value, and a list, and returns the accumulated result.

def foldl {a, b} (fn: b -> a -> b) (init: b) (ls: [a]) : b :=
  match ls as list something with
    | [] -> init
    | $x :: $xs ->
      let z := fn init x
        in seq z (foldl fn z xs)
This book in another language: English, 日本語