program stamping & homoiconicity & lisp

in java, if you want to generate a set of classes, you have to write a class that can output strings that will ultimately represent a valid java program. at runtime, you may have a method called generateObject that accepts some arguments and outputs the blueprint of a class. the output will be strings or even files but they are not being generated and compiled at the same time. compilation will need to happen after runtime generation. this separation of code generation and compilation in meta-programming is common in most statically typed languages.

dynamically typed languages and interpreted languages such as ruby and python support code generation / program generation and execution at runtime. for example, ruby supports defining methods dynamically at runtime that becomes available to the rest of the system via define_method and it can even evaluate arbitrary ruby code using functions like class_eval. however, any sufficiently complex program can only be represented as strings and thus the only way to manipulate them is as plain strings.

in both situations, whether dynamic or static, languages have

1. a representation of a program in a particular language that conforms to a special grammar, usually EBNF
2. a set of primitive data structures that can be manipulated at program runtime

and the actual program representation does not conform to the same structures as its data structures. in other words, the language does not allow the program itself to be treated as a data structure – because the literal representation of the program itself (that a programmer sees) is not a data structure but rather just text strings.

take ruby as an example

class Animal
  def initialize(name, sound)
    @name = name
    @sound = sound
  end

  def make_sound
    puts "#{@name} says #{@sound}!"
  end
end

# Creating an instance of the Animal class
cat = Animal.new("Cat", "Meow")

# Calling the make_sound method
cat.make_sound
Code language: Ruby (ruby)

that’s a representation of a ruby program – in no way does that resemble any of the data structures in ruby such as arrays or dictionaries.

program source representations as part of a interpretation or compilation process do eventually undergo transformations that turn plain source text into data structures that can be manipulated. for example, the lexing and parsing phases of compilers product syntax tree data structures that can in fact be expressed with the same primitive structures supported by the language itself.

the keyword here is “eventually”. in other words, not during runtime. the program as it is represented before any compilation occurs is not a data structure and cannot be manipulated as such.

lisp

the one exception to this is lisp. the fancy word used to describe this unique position held by lisp regarding the discrepancy between the languages external representation and its data structures is homoiconicity.

lisp is homoiconic because lisp programs manipulate s-expressions and are written in s-expressions.

here’s a simple demonstration using a dialect of lisp (racket scheme) where we define an original program (as a list) and then we transform the program literally before eval’ing it.

#lang racket/base

(define original-program '(+ 1 2 3))
(define reshaped-program (list (car original-program) 4 5 6))
(define ns (make-base-namespace))
(eval reshaped-program ns)Code language: Lisp (lisp)

since our original-program is just a list, it can be manipulated like any other list using functions like car. notice here how there’s no distinction between a manipulated program and the surrounding program representation. it’s all just lists. that is code as data.

this power extends not just to arbitrary program eval and manipulation – lisp also lets you extend its syntax in new ways to support custom language features that are not built into the language. these are known as macros. again, since the language is made up of s-expressions, any new formulation or semantic of the language can likewise be expressed in s-expressions and can be expanded and eval’d at runtime.

i’ve long wondered what the yinyang symbol of lisp represented and it’s actually from structures and interpretations. the yin yang represents eval and apply in the metacircular evaluator from the textbook. the metacircular evaluator is basically a lisp interpreter written in lisp – it is lisp evaluating itself. in other words, evaluating a lisp program at runtime (through the use of both eval and apply).