If you want to make money online : Register now

[Solved]: Can a functional language be homoiconic?

, , No Comments
Problem Detail: 

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?

Asked By : sdleihssirhc

Answered By : Andrej Bauer

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}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48343

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback