6
$\begingroup$

According to the wikipedia page on homoiconicity:

In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself.

I was wondering if the lambda calculus was homoiconic (I assume not, because applications are not data (which, for the calculus, would mean variable or abstraction?)), and if not, what it would take to make it homoiconic (wrap all applications in an abstraction with a useless variable, a la \a.b c?).

But the more important question is this: If the only primitive data type in the language is the function, is it possible to achieve homoiconicity? (Does homoiconicity even make sense if all you have are functions?) If not, then is there some formal definition of what data-properties must be present in order to achieve homoiconicity?

$\endgroup$
10
$\begingroup$

The definition implies not only that programs are represented by a "primitive" datatype, but presumably also that it is possible to inspect the elements of this type, i.e., one can actually get at the code (otherwise I can just declare a primitive abstract type code and never let you look at it).

In general, the construct you are looking for is known as quote. It takes a piece of code (in $\lambda$-calculus or anywhere else) and returns its representation, either as an abstract syntax tree, a string, or just an integer (because integers can encode syntax trees). Of course, in the case of $\lambda$-calculus such trees, strings or numbers would be encoded in the usual way that we encode datastructures in $\lambda$-calculus.

It is known that having quote in general increases the expressive power of the language. For example, in $\lambda$-calculus we cannot implement the statement "all functions are continuous" but we can if we also have quote at our disposal (this is the essence of Kreisel-Lacombe-Shoenfield-Tseitin theorem).

The opposite of quote is eval, which many languages have. However, eval does not add to the expressive power of a language because it can be implemented within the language, assuming the language is general enough (eval is essentially an interpreter for the language).

It is worth mentioning that quote is an abstract way of making a programming language be a lot more like the Turing machine model (TM) of computation. In the TM model a piece of code is a Turing machine, and it is represented on the tape as a sequence of symbols, which is the only datatype that Turing machines know about.

Note: it is common knowledge that "all models of computation are equivalent". What this means is that they compute the same class of functions from numbers to numbers $\mathtt{nat} \to \mathtt{nat}$, but they are not equivalent when it comes to higher-order functions such as $(\mathtt{nat} \to \mathtt{nat}) \to \mathtt{nat}$.

$\endgroup$
  • $\begingroup$ Say LC had a quote method... What would it return? We can construct sequences and use K and I to access its members... If I ran quote (\a.a b) would it return the sequence \a.a, b? What if I ran quote \a.a? Would it return the sequence a, a? How can a functional language "inspect" functions? (I'm an idiot, thank you for humoring me.) $\endgroup$ – sdleihssirhc Oct 17 '15 at 8:36
  • $\begingroup$ And regarding the last paragraph, I thought LC and TM were computationally equivalent... How can TM be capable of doing something LC can't? $\endgroup$ – sdleihssirhc Oct 17 '15 at 8:38
  • $\begingroup$ I amended my answer, please read again. $\endgroup$ – Andrej Bauer Oct 17 '15 at 10:04
  • $\begingroup$ Marking as accepted, because it explains what I was looking for, but I'm afraid I still don't quite understand. LC doesn't have quote... but it can create data structures that can represent programs, and it can implement its own eval and pass those data structures to it, so what expressive power does quote add? I can see finding myself in a situation where I wish I could quote an expression, but can't I fix that by rewriting my code so that I'm dealing with those syntax trees and passing them to eval instead writing the code directly? It sounds like quote is just convenience. $\endgroup$ – sdleihssirhc Oct 20 '15 at 0:58
  • $\begingroup$ Nope, it is not just convenience. There is no $\lambda$-term $q$ such that, for every $\lambda$-term $t$ we would have that $q \, t$ is the representation of the syntax of $t$. Rewriting code does not count because you are not a $\lambda$-term. $\endgroup$ – Andrej Bauer Oct 20 '15 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.