This language is intended as a programming project for CSCI 5220, Program Translation. The project is to write a compiler and interpreter for this language.
Functional programming languages have been around since the early days of Lisp. Based on Church's lambda-calculus, they have a few common characteristics.
All computation is performed by using pure functions. A function takes a parameter and produces a result. There is no notion of a side effect. There are no variables, or anything that can change while a program is computing. Data structures cannot be modified.
Programs are declarative. They consist of a collection of facts.
Functions are considered values, just like other values. You can pass a function to another function, receive a function as the result of a function, etc.
Implementation issues such as memory management the pollute the pure notion of functions are handled by the language implementation, not by the programmer.
To somebody who has only used imperative programming languages, functional languages initially seem very strange, to the point of being impossible to use. How can you compute if you cannot change anything? How can you manage without variables? And yet, functional languages are popular among programmers who bother to learn how to use them. The reason is that they tend to yield short, simple programs for some problems that would be quite difficult to solve in other styles. Programmers often find that their programs work the first time they are tried, or with only a tiny amount of fixing, far more often than even the programmers feel they have a right to expect.
Examples of functional programming languages are Lisp, Standard ML and Haskell. There are many others. Not all functional languages offer only functional programming. Standard ML, for example, also offers imperative features. We are only interested here in a pure language, though.
This document describes a bar-bones functional programming language. We will call it SFL, for Small Functional Language.
The values of SFL have the following forms. Each value has exactly one type.
Values true and false are simple values used as the results of tests.
Integers (..., -2, -1, 0, 1, 2, ...) are values. Integers are restricted to the range from -231 to 231-1. Attempting to compute an integer outside of that range yields an error.
Characters 'a', 'b', etc. are values. The alphabet is the ASCII alphabet.
A list of zero or more values is a value. We will write lists in square brackets, with commas separating the list members. For example, [1,2,3] is a list of three things. [3] is a list with just one integer in it. ['a','b'] is a list of two characters. [] is the empty list.
Different types of things can be mixed in a list. For example, you can create list [true, 'a', 15].
Functions are values. Each function takes exactly one parameter, and produces exactly one result.
A name, or an identifier, is a sequence of letters containing at least one letter. The reserved words and, case, def, else, end, false, in, let, not, or and true are not allowed to be used as identifiers.
Identifiers are used to name values. They are not variables. They just refer to things.
An expression is evaluated to produce a value. The expressions have the following forms.
An identifier is an expression, assuming it occurs in a context where that identifier is defined. It stands for the value that the identifier names. So x is the thing named by x.
'a' is the character constant (lower case a). Character constants allow letters, digits, special characters (other than the newline character) and the special sequence '\n' (a newline character).
Integer constants are written in standard decimal notation.
Expresson A == B has value true if A and B have the same value, and false if A and B have different values.
Expression A < B has value true if the value of A is strictly less than the value of B, and false otherwise.
A or B is equivalent to case A => true | else => B end.
A and B is equivalent to case A => B | else => false end.
not A is equivalent to case A => false | else => true end.
A + B produces the sum of the values of A and B.
A - B produces the difference of the values of A and B.
A * B produces the product of the values of A and B.
A / B produces the integer quotient of the values of A and B. For example, expresssion 5/3 has value 1.
A : B produces a list L such that head(L) is the value of expression A, and tail(L) is the value of expression B.
If A and B are expressions, then A B is an expression. The value of A must be a function. If the value of A is function f, and the value of B is value v, then evaluating A B produces the value f (v), the result of applying function f to value v.
Expression case C1 => E1 | C2 => E2 | ... | Cn=> En | else => En+1 end is evaluated by testing conditions C1, ..., Cn in the order written. If expression C1 evaluates to true, then the value of this case expression is the value of expression E1. If C1 evaluates to false, but C2 evaluates to true, then the value of expression E2 is the value of the case expression. In general the value is the value of Ei where Ci is the first of the conditions whose value is true. If none of the conditions is true, then the value is En+1.
The else phrase is required. There must be at least one condition. So n > 0.
If x is an identifier and A and B are expressions then expression let x = A in B end has the value of expression B, but while B is evaluated, identifier x names the value of expression A. Expression let x = A in B end has the same value as ((\ x -> B) A).
The value of expression \ x -> A is a function f defined by f (x) = A. What occurs after the \ is an identifier, and that identifier can be used in expression A.
Expression (A) has the same meaning as expression A.
Any sequence of expression separated by commas and surrounded by [...] is an expression whose value is a list of the values of the expressions listed. There can be any number of expressions in the list, including none. For example, expression [2+3, 8+4] has value [5,12]. Expression [A,B,C] is has the same meaning as ((A):(B):(C):nil).
Ambiguity is resolved by the following precedence and associativity rules. The table lists operators from high precedence to low precedence, with an associativity for each.
| Operator | Associativity |
|---|---|
| (juxtaposition) | left |
| *, / | left |
| +, - | left |
| : | right |
| ==, < | none (x == y == z is not allowed) |
| and | left |
| or | left |
| \ ... -> | n/a |
The following definitions are available to all programs.
| Name | Type | Meaning |
|---|---|---|
| nil | list x | nil is the empty list. |
| head | list x -> x | Produce the head (the first member) of a list. |
| tail | list x -> list x | Produce the tail (all but the first member) of a list. |
| nilq | list x -> bool | nilq(v) is true just when v is an empty list. |
Sometimes a function cannot produce a value. For example, you cannot divide by 0, and you cannot take the head of an empty list. The value of a condition in a case might not be true or false. All such errors will cause a program to stop immediately. There is no support for recovering from sending bad data to one of the standard functions or operators.
This definition indicates that x names the value of expression E.
This is equivalent to def A = \B -> E end
A program is a sequence of definitions, one after another.
Definition
def twenty = 20 end
defines identifier twenty to name number 20.
The following is a definition of the list concatenation function, cat. For example, expression (cat [2,4] [6,8]) yields result [2,4,6,8].
def cat x y =
case
nilq x => y
| else => head x : cat (tail x) y
end
end
Notice that, since juxtaposition is left-associative, an equivalent definition is
def (cat x) y =
case
nilq x => y
| else => head x : cat (tail x) y
end
end
Now, according to the rule for a definition where the expression being defined is a juxaposition of two other expressions, this is the same as
def cat x =
\y ->
case
nilq x => y
| else => head x : cat (tail x) y
end
end
The expression being defined is still a juxtaposition. Using the same rule again yields
def cat =
\x ->
\y ->
case
nilq x => y
| else => head x : cat (tail x) y
end
end
Here is a function composition function. (compose f g) is a function which, when applied to x, produces f(g(x)).
def compose f g x = f(g x) end