Single Assignment Language

A language in which a variable can only be assigned once. A single assignment language is a functional language, for an expression like x := sin(pi / 6) can be thought of as defining a nilary function x which returns the value of the above expression.

See also Single-Assignment C (http://www.sac-home.org/), and SISAL (http://www.llnl.gov/sisal/).

Are there any examples of functional languages that are not single-assignment? APL? I think AplLanguage allows reassignment...

What about LispLanguage? Lisp is not a functional language, and it has assignment operators (setf/setq)

AFAIK, functional languages and single-assignment languages are the same thing. However, many languages that are considered functional contain impure constructs, such as (non-initialising) assignment. Things like set! in Scheme [SchemeLanguage], or <- in ML [MlLanguage]. But using them is considered non-functional programming. You can use Haskell [HaskellLanguage] or ML just as a better C [CeeLanguage].

-- StephanHouben

I'd be a bit loath to say that all single assignment languages are functional. For example, modern optimizing compilers routinely transform programs into StaticSingleAssignmentForm (SSA), which as the name suggests, is a SingleAssignmentLanguage.

A perhaps better definition of a single assignment language is one which encourages programming through name binding rather than through assignment. [I'm assuming here that name binding the same symbol twice is not allowed.] It would then follow that most functional languages (FLs) are single assignment languages, on the grounds that FLs discourage programming through side effects, and variable assignment is a type of side effect.

My reason for using no verb stronger than "discourage" is that many (so called "impure") FLs do have "ref" or "box" variable types which admit multiple assignments. For example, in ML one can write

val a = ref 1; (* "=" binds names in ML; the variable a has type ref int *)

a := 2; (* ":=" assigns to refs *)

a := !a + 3;(* "!a" accesses the value of a ref *)

In addition, in ML, elements of arrays and strings are mutable, as well as fields of records and objects if they were specifically declared as "mutable". This is done using the "<-" assignment operator.

Nonetheless, I would still call ML a functional programming language, as it allows and encourages you to perform the majority of your programming in a side effect free manner. (Variables (ironically named), for example, are immutable in ML.) Similarly, I wouldn't call SSA form C a functional language, if only because the inserted phi functions mimic state through their nondeterminism.

Finally, I wouldn't call APL a functional programming language. You can do a lot through composing functions in APL, and it was clearly a historical inspiration for the early developers of FLs, but at the end of the day, you still assign to variables and use state based control flow.

-- ThomasColthurst

See also SingleAssignment and StaticSingleAssignmentForm.

CategoryFunctionalProgramming