<p>Traditionally, an algebra is a carrier set with operations that satisfy some equations (think "group"). There are many ways in which the notion can be generalized:</p>

<ul>
<li><p><em>multi-sorted</em> algebras have several carrier sets. An example would be a module $M$ over a ring $R$, where we want to consider the whole thing as a single algebra. Another, rather silly example, is a directed graph, which has two carrier sets, $E$ of edges and $V$ of vertices, and two operations, source $s : E \to V$ and target $E \to V$, satisfying no equations.</p></li>
<li><p><em>more general axioms</em> which are not just equations may be allowed. For example, the axioms for a field are all equations except for $x \neq 0 \implies x \cdot x^{-1} = 1$. Another example is something like an integral domain.</p></li>
<li><p><em>more general operations</em> may be allowed, in particular ones of infinite arity, or higher-order operations which take functions as arguments. An example of an infinitary operation is the $M$ in <a href="http://www.cs.bham.ac.uk/~mhe/.talks/map2011/martin_map.pdf">midpoint algebras</a> of Martin Escardo and Alex Simpson. If you go far in this direction you arrive at monads.</p></li>
</ul>

<p>In this sense the untyped $\lambda$-calculus is an algebra because it is specified in terms of a carrier set with some (higher-order) operations satisfying some equations ($\beta$ and $\eta$).</p>

CC BY-SA 3.0
2012-01-30T20:32:04.493Z
2012-01-30T20:32:04.493Z
Andrej Bauer
<p>There is a quite precise definition of what an algebra is in category theory: see <a href="http://en.wikipedia.org/wiki/F-algebra">this article</a> for instance. It took a few years to understand how a structure with bound variables could be understood in the same context as the <a href="http://en.wikipedia.org/wiki/Term_algebra">term algebra structure</a> commonly used in mathematics and computer science, and it turns out that the categorical concept of F-algebras is capable of unifying the two. I am not sure bout the historical aspects of the solution but one possible approach is the presheaf algebras introduced by Fiore, Plotkin and Turi (available <a href="http://www.dcs.ed.ac.uk/~dt/abstractsyn.ps">here</a>) settled the question and spurred different but similar approaches, see e.g. <a href="http://arxiv.org/abs/0704.2900">Hirshowitz et al.</a> and his phd student <a href="http://tel.archives-ouvertes.fr/tel-00535944/fr/">Julianna Zsido</a>. </p>

<p>Some exiting research remains to be done on how to use the categorical concepts to refactor and deepen our understanding of structures with bound variables, in the hopes of eliminating syntactic "cruft" which usually comprises the most boring chapters of theses on $\lambda$-calculi and related structures.</p>

CC BY-SA 3.0
2013-06-27T23:37:55.353Z
F-algebras usually are free algebras, i.e. don't allow equations; Pierce's category theory intro (from 1992) claims there is no development of equations for F-algebras.

I've only read of solutions in the abstract of Chung-Kil (Gil) Hur's PhD thesis, from 2010:
"Categorical equational systems: algebraic models and equational reasoning". Is that what I guess, and is it the first treatment o the topic?
Blaisorblade
CC BY-SA 3.0
2013-06-28T00:22:03.233Z
I don't think there's any reason the F-algebra approach does not apply to theories with equations. The idea is that you can form initial algebras with equations from the free ones (without equations) by "quotienting" by the appropriate theory. I don't know much about Gil's work or what Pierce meant by his remark.
cody
CC BY-SA 3.0
2013-06-28T00:25:31.527Z
Addendum: after a cursory glance, Gil's work with Marcello Fiore does seem to treat a general notion of equational theories for F-algebras.
cody
CC BY-SA 3.0
2012-01-30T20:25:16.103Z
2012-01-30T20:25:16.103Z
cody
<p>While it is true that the notion of "calculus" is less well-defined than the notion of an "algebra", broadly "calculus" generally implies a process of calculation, while algebras have patterns of construction with equational theories.<br>
You could say there is more of a feeling that algebras "already exist" as structures and we are merely uncovering truths about them, rather than using some method to produce new answers that didn't exist before.</p>

<p>If you think about what Scott was trying to accomplish with Scott domains, his statement makes sense:  he was trying to find predefined mathematical and algebraic structures that would serve as a fixed semantics for LC.  He wanted to do away the feeling that the meaning of a term was whatever happened to come out of a particular process.</p>

<p>You might be interested in a previous answer about a related question:  <a href="https://cstheory.stackexchange.com/questions/3577/what-constitutes-denotational-semantics/3583#3583">What constitutes denotational semantics?</a></p>

CC BY-SA 3.0
2012-01-30T17:15:06.283Z
2012-01-30T17:15:06.283Z
2017-04-13T12:32:28.743Z
Marc Hamann
<p>I would be very reluctant to call lambda-calculus an "algebra" for a very simple reason.  It is a formal system defined purely using syntax, without any reference to meaning.  The equivalences $\beta$ and $\eta$ are at a meta-level, using variables like $M$ and $N$ that range over terms.  That is not what algebraists would call an "algebra".  On the other hand, logicians have long used the term "calculus" to mean formal systems where rules are expressed at the meta-level.</p>

<p>If Scott ever did call lambda calculus an "algebra" (which I rather doubt), then he would have been making a rather subtle point, <i>viz.,</i> that you <i>can</i> think of lambda calculus as having an <i>a priori</i> meaning.</p>

<p>Still he would have a hard time convincing any algebraists of his claim, because he doesn't have equations in lambda calculus, he has equivalences (i.e., at the meta-level).  "Combinatory algebra", on the other hand, is perfectly normal.</p>

CC BY-SA 3.0
2012-02-23T23:08:44.290Z
2012-02-23T23:17:53.093Z
2012-02-23T23:17:53.093Z
Uday Reddy
<p>There is no such thing as <em>a calculus</em>, but there is a well-defined mathematical object called <em>algebra</em>, though the word <a href="http://mathworld.wolfram.com/Algebra.html" rel="nofollow">has many uses</a>. However, my guess is that the name was given in the sense of</p>

<blockquote>
  <p>(...) the abstract study of number systems and operations within them.</p>
</blockquote>

<p>since, in $\lambda$-calculus, you define objects (<em>terms</em>, which you may call <em>numbers</em>) and operations within those objects.</p>

CC BY-SA 3.0
2012-01-30T19:24:48.240Z
Look at Neel's answer.
Dave Clarke
CC BY-SA 3.0
2012-01-30T19:41:45.047Z
Yep. That certainly looks like a definition, but it is not a standard one. I agree with Neel that it can be whatever you want depending on your interpretation of the rules, but that also depends on your definition of "a calculus" and "an algebra", neither of which is standard (apart from the formal object coming from a vector space, which is not the case with $\lambda$-calculus).
Janoma
CC BY-SA 3.0
2012-01-30T15:49:30.960Z
2012-01-30T15:49:30.960Z
Janoma
<p>A calculus is a system of computation based on the manipulation of symbolic expressions. An algebra is a system of symbolic expressions and relations between them[*]. That is, a calculus is a system for figuring out answers, and an algebra is a way of expressing the relations between terms. </p>

<p>The $\lambda$-calculus is either a calculus or an algebra, depending on whether you want to think of the $\beta$ and $\eta$ rules as oriented reduction rules or unoriented equations. If you think of the rules as being oriented, then you have fixed an evaluation order, and the rules tell you how to take a term and produce a normal form. If you think of the rules as being unoriented, then they give you the equality relation on $\lambda$-terms.</p>

<p>[*] There is also a categorical definition of algebra, which is a formal definition somewhat more restrictive than the informal idea. Loosely speaking, the difference is that the formal definition of algebra encompasses just those systems without variable binding. So SKI combinators form an algebra, but the $\lambda$-calculus doesn't. </p>

CC BY-SA 3.0
2012-01-31T10:19:36.387Z
As mentioned in my comment, the categorical definition of algebras can be shown to encompass structures with binding operations. The main idea is that whereas structures without binders can be represented as algebras on sets, structures with binders can be represented by algebras on -presheafs-.
cody
CC BY-SA 3.0
2013-06-27T23:32:46.757Z
AFAIK, it's the definition of algebra in universal algebras doesn't allow operations with higher-order signatures (according to John Mitchell's Foundations of Programming Languages).
Blaisorblade
CC BY-SA 3.0
2012-01-30T18:33:48.713Z
2012-01-30T18:33:48.713Z
Neel Krishnaswami
<p>What is the difference of calling $\lambda$-calculus an algebra instead of a calculus? I raise this question because I read somewhere the line "$\lambda$-calculus is not a calculus but an algebra" (iirc, attributed to Dana Scott). What is the point? Thanks.</p>

CC BY-SA 3.0
2012-02-27T17:29:23.110Z
Coming from an apprentice of the subject with likely no insight whatsoever: isn't determining whether two lambda-calculus expressions are equivalent undecidable? Does that have any influence on why it wouldn't be considered a "calculus"? Because that's a fundamental question that can't be algorithmically calculated...
Jeremy Kun
<soft-question><lambda-calculus>
What is the point of calling $\lambda$-calculus an algebra?
day
# What is the point of calling $\lambda$-calculus an algebra?

(Asked by: username_0 on 2012-01-30)

What is the difference of calling $\lambda$-calculus an algebra instead of a calculus? I raise this question because I read somewhere the line "$\lambda$-calculus is not a calculus but an algebra" (iirc, attributed to Dana Scott). What is the point? Thanks.

**Tags:** soft-question, lambda-calculus

> **Comments:**
> **username_1**: Coming from an apprentice of the subject with likely no insight whatsoever: isn't determining whether two lambda-calculus expressions are equivalent undecidable? Does that have any influence on why it wouldn't be considered a "calculus"? Because that's a fundamental question that can't be algorithmically calculated...  

---

## 6 answers

### Answer by username_9 on 2012-01-30. Score: 18 | Accepted answer

A calculus is a system of computation based on the manipulation of symbolic expressions. An algebra is a system of symbolic expressions and relations between them[\*]. That is, a calculus is a system for figuring out answers, and an algebra is a way of expressing the relations between terms.

The $\lambda$-calculus is either a calculus or an algebra, depending on whether you want to think of the $\beta$ and $\eta$ rules as oriented reduction rules or unoriented equations. If you think of the rules as being oriented, then you have fixed an evaluation order, and the rules tell you how to take a term and produce a normal form. If you think of the rules as being unoriented, then they give you the equality relation on $\lambda$-terms.

[\*] There is also a categorical definition of algebra, which is a formal definition somewhat more restrictive than the informal idea. Loosely speaking, the difference is that the formal definition of algebra encompasses just those systems without variable binding. So SKI combinators form an algebra, but the $\lambda$-calculus doesn't.

> **Comments:**
> **username_3**: As mentioned in my comment, the categorical definition of algebras can be shown to encompass structures with binding operations. The main idea is that whereas structures without binders can be represented as algebras on sets, structures with binders can be represented by algebras on -presheafs-.  
> **username_4**: AFAIK, it's the definition of algebra in universal algebras doesn't allow operations with higher-order signatures (according to John Mitchell's Foundations of Programming Languages).  

---

### Answer by username_2 on 2012-01-30. Score: 12

Traditionally, an algebra is a carrier set with operations that satisfy some equations (think "group"). There are many ways in which the notion can be generalized:

* *multi-sorted* algebras have several carrier sets. An example would be a module $M$ over a ring $R$, where we want to consider the whole thing as a single algebra. Another, rather silly example, is a directed graph, which has two carrier sets, $E$ of edges and $V$ of vertices, and two operations, source $s : E \to V$ and target $E \to V$, satisfying no equations.
* *more general axioms* which are not just equations may be allowed. For example, the axioms for a field are all equations except for $x \neq 0 \implies x \cdot x^{-1} = 1$. Another example is something like an integral domain.
* *more general operations* may be allowed, in particular ones of infinite arity, or higher-order operations which take functions as arguments. An example of an infinitary operation is the $M$ in [midpoint algebras](http://www.cs.bham.ac.uk/~mhe/.talks/map2011/martin_map.pdf) of Martin Escardo and Alex Simpson. If you go far in this direction you arrive at monads.

In this sense the untyped $\lambda$-calculus is an algebra because it is specified in terms of a carrier set with some (higher-order) operations satisfying some equations ($\beta$ and $\eta$).


---

### Answer by username_3 on 2012-01-30. Score: 6

There is a quite precise definition of what an algebra is in category theory: see [this article](http://en.wikipedia.org/wiki/F-algebra) for instance. It took a few years to understand how a structure with bound variables could be understood in the same context as the [term algebra structure](http://en.wikipedia.org/wiki/Term_algebra) commonly used in mathematics and computer science, and it turns out that the categorical concept of F-algebras is capable of unifying the two. I am not sure bout the historical aspects of the solution but one possible approach is the presheaf algebras introduced by Fiore, Plotkin and Turi (available [here](http://www.dcs.ed.ac.uk/~dt/abstractsyn.ps)) settled the question and spurred different but similar approaches, see e.g. [Hirshowitz et al.](http://arxiv.org/abs/0704.2900) and his phd student [Julianna Zsido](http://tel.archives-ouvertes.fr/tel-00535944/fr/).

Some exiting research remains to be done on how to use the categorical concepts to refactor and deepen our understanding of structures with bound variables, in the hopes of eliminating syntactic "cruft" which usually comprises the most boring chapters of theses on $\lambda$-calculi and related structures.

> **Comments:**
> **username_4**: F-algebras usually are free algebras, i.e. don't allow equations; Pierce's category theory intro (from 1992) claims there is no development of equations for F-algebras.  I've only read of solutions in the abstract of Chung-Kil (Gil) Hur's PhD thesis, from 2010: "Categorical equational systems: algebraic models and equational reasoning". Is that what I guess, and is it the first treatment o the topic?  
> **username_3**: I don't think there's any reason the F-algebra approach does not apply to theories with equations. The idea is that you can form initial algebras with equations from the free ones (without equations) by "quotienting" by the appropriate theory. I don't know much about Gil's work or what Pierce meant by his remark.  
> **username_3**: Addendum: after a cursory glance, Gil's work with Marcello Fiore does seem to treat a general notion of equational theories for F-algebras.  

---

### Answer by username_5 on 2012-01-30. Score: 5

While it is true that the notion of "calculus" is less well-defined than the notion of an "algebra", broadly "calculus" generally implies a process of calculation, while algebras have patterns of construction with equational theories.  
You could say there is more of a feeling that algebras "already exist" as structures and we are merely uncovering truths about them, rather than using some method to produce new answers that didn't exist before.

If you think about what Scott was trying to accomplish with Scott domains, his statement makes sense: he was trying to find predefined mathematical and algebraic structures that would serve as a fixed semantics for LC. He wanted to do away the feeling that the meaning of a term was whatever happened to come out of a particular process.

You might be interested in a previous answer about a related question: [What constitutes denotational semantics?](https://cstheory.stackexchange.com/questions/3577/what-constitutes-denotational-semantics/3583#3583)


---

### Answer by username_6 on 2012-02-23. Score: 4

I would be very reluctant to call lambda-calculus an "algebra" for a very simple reason. It is a formal system defined purely using syntax, without any reference to meaning. The equivalences $\beta$ and $\eta$ are at a meta-level, using variables like $M$ and $N$ that range over terms. That is not what algebraists would call an "algebra". On the other hand, logicians have long used the term "calculus" to mean formal systems where rules are expressed at the meta-level.

If Scott ever did call lambda calculus an "algebra" (which I rather doubt), then he would have been making a rather subtle point, *viz.,* that you *can* think of lambda calculus as having an *a priori* meaning.

Still he would have a hard time convincing any algebraists of his claim, because he doesn't have equations in lambda calculus, he has equivalences (i.e., at the meta-level). "Combinatory algebra", on the other hand, is perfectly normal.


---

### Answer by username_7 on 2012-01-30. Score: 3

There is no such thing as *a calculus*, but there is a well-defined mathematical object called *algebra*, though the word [has many uses](http://mathworld.wolfram.com/Algebra.html). However, my guess is that the name was given in the sense of

> (...) the abstract study of number systems and operations within them.

since, in $\lambda$-calculus, you define objects (*terms*, which you may call *numbers*) and operations within those objects.

> **Comments:**
> **username_8**: Look at Neel's answer.  
> **username_7**: Yep. That certainly looks like a definition, but it is not a standard one. I agree with Neel that it can be whatever you want depending on your interpretation of the rules, but that also depends on your definition of "a calculus" and "an algebra", neither of which is standard (apart from the formal object coming from a vector space, which is not the case with $\lambda$-calculus).  

---

