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. This page only describes the 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.
true, false
Values true and false are simple values used as the results of tests.
Integers
Integers (..., -2, -1, 0, 1, 2, ...) are values. Integers are 32 bit 2's complement integers, restricted to the range from -231 to 231-1. Adding 1 to 231 - 1 yields -231.
[x,y,z]
A value can be a list of zero or more things. 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. [true, false] is a list of two boolean values. [] is the empty list. Normally, you do not mix different types of things in a list, but we will have more to say about that later.
functions
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. Identifiers are only used to name values. They are not variables. The reserved words and, case, def, else, end, false, head, in, isBool, isFunction, isInt, isList, isNull, let, not, or, tail and true are not allowed to be used as identifiers.
An expression is evaluated to produce a value. The expressions have the following forms.
x
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.
1234
Integer constants are written in standard decimal notation.
A == B
Expression A == B has value true if A and B have the same value, and false if A and B have different values.
A < B
Expression A < B has value true if the value of A is strictly less than the value of B, and false otherwise. (There are no other relational operators, just == and <.
A + B
A + B produces the sum of the values of A and B.
A - B
A - B produces the difference of the values of A and B.
A * B
A * B produces the product of the values of A and B.
A / B
A / B produces the integer quotient of the values of A and B. For example, expresssion 5/3 has value 1.
( A )
Expression (A) has the same meaning as expression A.
A : B
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. For example, expression [2]:[4,6] has value [2,4,6].
[A, B, C]
Any sequence of expressions 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):[ ]).
head A
Expression head A produces the head of list A.
tail A
Expression tail A produces the tail of list A.
isNull A
Expression isNull A produces true if A is [], and false otherwise.
isNull A
Expression isNull A produces true if A is [], and false otherwise.
isList A
Expression isList A produces true if A is a list (either [] or something created using the : operator), and false otherwise.
isInt A
Expression isInt A produces true if A is an integer, and false otherwise.
isBool A
Expression isBool A produces true if A is a boolean value (true or false), and false otherwise.
isFunction A
Expression isFunction A produces true if A is a function, and false otherwise.
case C1 => E1 | C2 => E2 | ... | else => En+1 end
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.
A or B
A or B is equivalent to case A => true | else => B end.
A and B
A and B is equivalent to case A => B | else => false end.
not A
not A is equivalent to case A => false | else => true end.
A B
If A and B are expressions, then A B is an expression. Since you just write two expressions next to one another, this is called juxtaposition. 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.
x -> A
The value of expression x -> A is a function f defined by f (x) = A. The left-hand side of -> is required to be an identifier, and that identifier can be used in expression A.
let x = A in B end
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).
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 |
|---|---|
| head, tail, isBool, isFunction, isInt, isList, isNull | n/a |
| juxtaposition | left |
| *, / | left |
| +, - | left |
| : | right |
| ==, < | none (x == y == z is not allowed) |
| and | left |
| or | left |
| -> | right |
Sometimes an expression cannot produce a value. For example, you cannot divide by 0, you cannot take the head of an empty list, and you cannot do an and unless both of the operands are boolean values. The value of a condition in a case might not be true or false. You might be asked to add a boolean value to a function. 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.
Definitions have the following forms.
def x = E end
This definition indicates that x names the value of expression E.
def A B = E end
This is equivalent to def A = B -> E end. This only makes sense if B is an identifier, but it does not require A to be an identifier. You can use this rule more than once. For example, you can perform conversions
| def x y z = a end |
| => def x y = z -> a end |
| => def x = y -> z -> a end |
Definition
def twenty = 20 end
defines identifier twenty to name number 20.
Function sqr returns the square of its parameter. You can define it by
def sqr = x -> x*x endor by
def sqr x = x*x end
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
isNull x => y
| else => head x : cat (tail x) y
end
end
After doing replacements, the definition of cat is
equivalent to the following.
def cat =
x ->
y ->
case
isNull 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
A program is a sequence of one or more definitions, one after another. When a program is run, the language implementation evaluates the definition of main and prints the result.
This part is only intended to be done by graduate students. Add type checking, so that a definition that does not work according to type rules will receive a warning that it is poorly typed. The details are discussed in the implementation page.