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, not how to implement it. See implementation of SFL for a discussion of the implementation.
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 that 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? How do you do anything without commands? 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.
Some of the ideas of functional programming are not as foreign as you might imagine. In Java, integers and strings both have the characteristic that you cannot change them. For example, you can build a string, but there is no operation to modify a string. You can only compute new strings. But Java programmers seem to get by just fine without operations that change integers or strings.
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 simple, pure language, though.
This document describes a bar-bones functional programming language. We will call it SFL, for Small Functional Language.
SFL is a free-form language. That means that, in most contexts, a newline or tab is like a space, and several spaces in a row are equivalant to a single space.
SFL is case-sensitive. So R and r are considered different letters.
A comment begins with // and ends at the end of the line.
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.
Characters
Characters constants have the form 'a'. There are two special character constants, '\n' and '\\', standing for the newline character and the backslash character.
[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. SFL is a typeless language, so you can create list [true, 3].
Functions
Functions are values. Each function takes exactly one parameter, and produces exactly one result.
Actions
An action is a command. It runs and produces a result. I said above that there are no commands. To be precise, there are no commands that you can run from within the program. You can build up commands, but only an external agent can perform them. Actions include forms print(x), produce(x), readChar and readInt, where print(x) prints x, readChar reads one character, readInt reads one integer and produce(x) does nothing but yields value x. There is more on actions below.
SFL is a typeless language. That means that all type checking, where needed, is done at run time.
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, print, produce, readChar, readInt, 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.
true
false
These reserved words stand for boolean values.
1234
Integer constants are written in standard decimal notation. There is no sign.
'a'
'\n'
These are character constants.
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.
A > B
Expression A > B is equivalent to expression B < A. (Note that there are no <= or >= operators.)
A + B
A + B produces the sum of the values of A and B. It is required that expressions A and B produce integers.
A - B
A - B produces the difference of the values of A and B. It is required that expressions A and B produce integers.
A * B
A * B produces the product of the values of A and B. It is required that expressions A and B produce integers.
A / B
A / B produces the integer quotient of the values of A and B. For example, expresssion 5/3 has value 1. It is required that expressions A and B produce integers.
( 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 zero or more 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):[ ]).
readChar
readInt
produce A
print A
Each of these expressions produces an action. (A is another expression.) Note that they do not perform an action. Rather, they have an action as their value. There is more detail about these below.
A ~> B
This is used with actions. Expression A should produce an action, and B should produce a function that produces an action as its result. An action can produce an answer (as do readChar and readInt). This expression builds a new action that: (1) performs action A, getting result r; (2) computes new action b = B(r); (3) performs action b. The result of action b is used as the result of expression A ~> B.
A ; B
This is equivalent to A ~> (x -> B), where x is a new name, not used anywhere else. It just does action A then does action B, ignoring the result of A, and producing the same answer as B.
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.
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.
isChar A
Expression isChar A produces true if A is a character value, and false otherwise.
isFunction A
Expression isFunction A produces true if A is a function, and false otherwise.
isAction A
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.
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, isChar, isFunction, isAction, isInt, isList, isNull, print | n/a |
| juxtaposition | left |
| *, / | left |
| +, - | left |
| : | right |
| ==, <, > | none (x == y == z is not allowed) |
| and | left |
| or | left |
| -> | right |
| ;, ~> | 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, and to show the tree that caused the error. There is no support for recovering from sending bad arguments 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
def max x y =
case
x > y => x
| else => y
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
Function showSquare ignores its parameter. It yields an actions that, when run, will read an integer and print the square of that integer.
def showSquare a =
readInt ~> (x -> print [x*x])
end
Identifier main names an action that, when run, prints Hello.
def main =
print ['H','e','l','l','o','\n']
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 or performs the result.
Use the following rules for showing results.
If the result is a number, show it in its usual (decimal) form. Note that it might be negative. (There are no negative integer constants, but the program can compute negative numbers.)
Show true as true and false as false.
Show a character as it would appear as a character constant in a program. For example, show character 'x' as 'x'.
Show the empty list as [ ]. Show list x:y by showing x, then writing a colon, then showing y.
Show a function simply as (a function).
If the answer is an action, perform the action. You will need a function, performAction, that takes a tree and returns a tree.
readChar
Read a character from the standard input and return that character (as a tree)
readInt
Read an integer from the standard input and return that integer (as a tree)
produce v
Do nothing and return v.
print v
Value v should be a list, or it is an error. Print the members of list v. Print a character without quotes, just as that character. Print all other members the same way you would if they were the result of main, except that, if one of the members of the list is an action, just show it as (an action). Return 0.
A ~> B
Perform action A, getting result r. B must be a function. Run that function on r, getting result b, which must be an action. Run that action. The result of action b is the result of A ~> B.
A ; B
Perform action A. Ignore its result. Perform action B. The answer produced by B is used as the result of A ; B.
Program
def a = [2,4,6] end
def b = [8,10] end
def main =
cat a b
end
def cat x y =
case
isNull x => y
| else => head x : cat (tail x) y
end
end
prints
2:4:6:8:10:[]
Program
def main =
print ['H','o','w',' ','m','a','n','y',' ','s','e','c','o','n','d','s','?'];
readInt ~> (n ->
let m = n/60 in
let h = n/3600 in
let secs = n - 60*m in
let mins = m - 60*h in
print [h, ':', mins, ':', secs]
end
end
end
end)
end
reads a number than prints it as hours, minutes, seconds. For example, if it reads 1000
then it prints
0:16:40