7
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\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}$.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Oct 17, 2015 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
    Commented Oct 17, 2015 at 8:38
  • 1
    $\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
    Commented Oct 20, 2015 at 0:58
  • 1
    $\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
    Commented Oct 20, 2015 at 21:25
  • 1
    $\begingroup$ Short explanation: a number written in binary is a sequence of 0's and 1's, and computers store everything as sequences of 0's and 1's in memory. Long explanation: Gödel numbering. $\endgroup$
    – Andrej Bauer
    Commented Sep 19, 2016 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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