Homoiconicity

In computer programming, homoiconicity (from the Greek words homo meaning the same and icon meaning representation) is a property of some programming languages in which the program structure is similar to its syntax, and therefore the program's internal representation can be inferred by reading the text's layout.[1] If a language is homoiconic, it means that the language text has the same structure as its abstract syntax tree (i.e. the AST and the syntax are isomorphic). This allows all code in the language to be accessed and transformed as data, using the same representation.

In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself. This makes metaprogramming easier than in a language without this property, since code can be treated as data: reflection in the language (examining the program's entities at runtime) depends on a single, homogeneous structure, and it does not have to handle several different structures that would appear in a complex syntax. To put that another way, homoiconicity is where a program's source code is written as a basic data structure that the programming language knows how to access.

A typical, commonly cited example is the programming language Lisp, which was created to be easy for lists manipulation and where the structure is given by S-expressions that take the form of nested lists. Lisp programs are written in the form of lists; the result is that the program can access its own functions and procedures while running, and programmatically reprogram itself on the fly. Homoiconic languages typically include full support of syntactic macros allowing the programmer to express program transformations in a concise way. Examples are the programming languages Clojure (a contemporary dialect of Lisp), Rebol and Refal.

History

The original source is the paper Macro Instruction Extensions of Compiler Languages,[2] according to the early and influential paper TRAC, A Text-Handling Language:[3]

One of the main design goals was that the input script of TRAC (what is typed in by the user) should be identical to the text which guides the internal action of the TRAC processor. In other words, TRAC procedures should be stored in memory as a string of characters exactly as the user typed them at the keyboard. If the TRAC procedures themselves evolve new procedures, these new procedures should also be stated in the same script. The TRAC processor in its action interprets this script as its program. In other words, the TRAC translator program (the processor) effectively converts the computer into a new computer with a new program language -- the TRAC language. At any time, it should be possible to display program or procedural information in the same form as the TRAC processor will act upon it during its execution. It is desirable that the internal character code representation be identical to, or very similar to, the external code representation. In the present TRAC implementation, the internal character representation is based upon ASCII. Because TRAC procedures and text have the same representation inside and outside the processor, the term homoiconic is applicable, from homo meaning the same, and icon meaning representation.

[...]

Following suggestion of McCullough, W. S., based upon terminology due to Peirce, C. S. s McIlroy. M. D., "Macro Instruction Extensions of Compiler Languages," Comm. ACM, p. 214-220; April, 1960.

Alan Kay used and possibly popularized the term "homoiconic" through his use of the term in his 1969 PhD thesis:[4]

A notable group of exceptions to all the previous systems are Interactive LISP [...] and TRAC. Both are functionally oriented (one list, the other string), both talk to the user with one language, and both are "homoiconic" in that their internal and external representations are essentially the same. They both have the ability to dynamically create new functions which may then be elaborated at the users's pleasure.

Their only great drawback is that programs written in them look like King Burniburiach's letter to the Sumerians done in Babylonian cuniform! [...]

Uses, advantages, and disadvantages

One advantage of homoiconicity is that extending the language with new concepts typically becomes simpler, as data representing code can be passed between the meta and base layer of the program. The abstract syntax tree of a function may be composed and manipulated as a data structure in the meta layer, and then evaluated. It can be much easier to understand how to manipulate the code since it can be more easily understood as simple data (since the format of the language itself is as a data format).

The simplicity that allows this also presents a disadvantage: one blogger argues that, at least in the case of LISP-like list-oriented languages, it can do away with many of the visual cues that help humans visually parse the constructs of the language, and that this can lead to a steep learning curve for the language.[5] See also essay "The Lisp Curse"[6] for disadvantages.

A typical demonstration of homoiconicity is the meta-circular evaluator.

Examples

Languages which are considered to be homoiconic include

In Von Neumann architecture systems (including the vast majority of general purpose computers today), raw machine code also has this property, the data type being bytes in memory.

Homoiconicity in Lisp

Lisp uses S-expressions as an external representation for data and code. S-expressions can be read with the primitive Lisp function READ. READ returns Lisp data: lists, symbols, numbers, strings. The primitive Lisp function EVAL uses Lisp code represented as Lisp data, computes side-effects and returns a result. The result will be printed by the primitive function PRINT, which creates an external S-expression from Lisp data.

Lisp data, a list using different data types: (sub)lists, symbols, strings and integer numbers.

((:name "john" :age 20) (:name "mary" :age 18) (:name "alice" :age 22))

Lisp code. The example uses lists, symbols and numbers.

(* (sin 1.1) (cos 2.03))      ; in infix: sin(1.1)*cos(2.03)

Create above expression with the primitive Lisp function LIST and set the variable EXPRESSION to the result

(setf expression  (list '* (list 'sin 1.1) (list 'cos 2.03)) )  
-> (* (SIN 1.1) (COS 2.03))    ; Lisp returns and prints the result

(third expression)    ; the third element of the expression
-> (COS 2.03)

Change the COS term to SIN

(setf (first (third expression)) 'SIN)
; The expression is now (* (SIN 1.1) (SIN 2.03)).

Evaluate the expression

(eval expression)
-> 0.7988834

Print the expression to a string

(print-to-string expression)
->  "(* (SIN 1.1) (SIN 2.03))"

Read the expression from a string

(read-from-string "(* (SIN 1.1) (SIN 2.03))")
->  (* (SIN 1.1) (SIN 2.03))     ; returns a list of lists, numbers and symbols

Homoiconicity in Prolog 

1 ?- X is 2*5.
X = 10.

2 ?- L = (X is 2*5), write_canonical(L).
is(_, *(2, 5))
L = (X is 2*5).

3 ?- L = (ten(X):-(X is 2*5)), write_canonical(L).
:-(ten(A), is(A, *(2, 5)))
L = (ten(X):-X is 2*5).

4 ?- L = (ten(X):-(X is 2*5)), assert(L).
L = (ten(X):-X is 2*5).

5 ?- ten(X).
X = 10.

6 ?-

On line 4 we create a new clause. The operator :- separates the head and the body of a clause. With assert/1* we add it to the existing clauses (add it to the "database"), so we can call it later. In other languages we would call it "creating a function during runtime". We can also remove clauses from the database with abolish/1, or retract/1.

* The number after the clause's name is the number of arguments it can take. It is also called arity.

We can also query the database to get the body of a clause:

7 ?- clause(ten(X),Y).
Y = (X is 2*5).

8 ?- clause(ten(X),Y), Y = (X is Z).
Y = (X is 2*5),
Z = 2*5.

9 ?- clause(ten(X),Y), call(Y).
X = 10,
Y = (10 is 2*5).

call is analogous to Lisp's eval function.

Homoiconicity in Rebol

The concept of treating code as data and the manipulation and evaluation thereof can be demonstrated very neatly in Rebol. (Rebol, unlike Lisp, does not require parentheses to separate expressions).

The following is an example of code in Rebol (Note that >> represents the interpreter prompt; spaces between some elements have been added for readability):

>> repeat i 3 [ print [ i "hello" ] ]

1 hello
2 hello
3 hello

(repeat is in fact a built-in function in Rebol and is not a language construct or keyword).

By enclosing the code in square brackets, the interpreter does not evaluate it, but merely treats it as a block containing words:

[ repeat i 3 [ print [ i "hello" ] ] ]

This block has the type block! and can furthermore be assigned as the value of a word by using what appears to be a syntax for assignment, but is actually understood by the interpreter as a special type (set-word!) and takes the form of a word followed by a colon:

>> block1: [ repeat i 3 [ print [ i "hello" ] ] ] ;; Assign the value of the block to the word `block1`
== [repeat i 3 [print [i "hello"]]]
>> type? block1 ;; Evaluate the type of the word `block1`
== block!

The block can still be interpreted by using the do function provided in Rebol (similar to eval in Lisp).

It is possible to interrogate the elements of the block and change their values, thus altering the behavior of the code if it were to be evaluated:

>> block1/3 ;; The third element of the block
== 3
>> block1/3: 5 ;; Set the value of the 3rd element to 5
== 5
>> probe block1 ;; Show the changed block
[repeat i 5 [print [i "hello"]]]
== [repeat i 5 [print [i "hello"]]]
>> do block1 ;; Evaluate the block
1 hello
2 hello
3 hello
4 hello
5 hello

See also

References

  1. ↑ David A. Wheeler. "Readable Lisp S-expressions".
  2. ↑ Douglas McIlroy (1960) Macro Instruction Extensions of Compiler Languages
  3. ↑ Calvin Mooers and L. Peter Deutsch (1965) TRAC, A Text-Handling Language
  4. ↑ Alan Kay (1969) The Reactive Engine, PhD thesis (Accessed 20061229)
  5. 1 2 3 Homoiconic languages, in true Blue blog at Oracle
  6. ↑ The Lisp Curse, at Winestock Webdesign
  7. 1 2 3 4 5 6 7 8 9 Homoiconic Languages
  8. ↑ Shapiro, Ehud Y.; Sterling, Leon (1994). The art of Prolog: advanced programming techniques. Cambridge, Mass: MIT Press. ISBN 0-262-19338-8.
  9. ↑ S. Ramsay and B. Pytlik-Zillig, Code-Generation Techniques for XML Collections Interoperability, Digital Humanities 2012 conference proceedings.
  10. ↑ Wolfram Language Notes for Programming Language Experts

External links

This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.