7
$\begingroup$

Is there a simple model of computation with homoiconicity?

It would also be nice if, like beta reduction in lambda calculus, every step in execution yields a new valid program.

Besides the lack of homoiconicity, another annoyance of lambda calculus is the necessity of checking for free variables when performing substitution.

$\endgroup$

migrated from stackoverflow.com Sep 16 '11 at 20:40

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ why do you say that lambda calculus lacks homoiconity? regarding free variables, you may use de Bruijn indices $\endgroup$ – max taldykin Sep 16 '11 at 18:06
  • 1
    $\begingroup$ In lambda calculus, you can't access the contents of a piece of code as data without executing it. (Sorry I'm not sure how to put that more technically.) $\endgroup$ – oozer Sep 16 '11 at 18:34
  • $\begingroup$ yep, you are right. I see now. $\endgroup$ – max taldykin Sep 16 '11 at 18:44
  • $\begingroup$ The semi-canonical way of eliminating free variables entirely is by using combinatory logic instead. That doesn't help with your main question, though. $\endgroup$ – C. A. McCann Sep 16 '11 at 19:16
  • $\begingroup$ I don't fully understand the original question, but it might be useful to look at languages like Template Haskell, Converge or MetaOCaml, which I'd say are homoiconic (in subtly different ways). They are all based around providing explicit support for quasi-quotes which is a convenient mechanism (API) for abstract syntax trees. $\endgroup$ – Martin Berger Sep 18 '11 at 11:27
9
$\begingroup$

The paper Typed Self-Representation by Tillmann Rendel, Klaus Ostermann and Christian Hofer seems to satisfy the requirements, and it's typed too. Perhaps it doesn't satisfy the criteria of being a simple model of computation.

$\endgroup$
6
$\begingroup$

Structural operational semantics is standard technology in theory of programming languages in which execution of a program is described as a series of transitions, each of which yields a valid program.

There are well-known mechanisms for dealing with or avoiding substitution in the execution of a program. Probably the most common one is that of keeping a run-time environment, which correspond to the subtitution we would have made so far, as well as to the run-time stack.

As far as homoiconicity is concerned, there are several options:

  • In Kleene's number realizability each piece of data is represented by a number. This holds for machines themselves, so we have homoiconicity, as every infinite object (function with infinite domain, a real number, an infinite sequence) is represented by a number, which can be understood as its Goedel code or "source code".

  • In theory of programming languages there are programming constructs that explicitely yield homoiconicity, for example the quote/unqoute mechanism in PCF+quote.

  • The general buzz word you may want to look up is meta programming, see e.g. this random paper.

$\endgroup$

Your Answer

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