Levels of Homoiconicity [closed]

Question

This is a follow up to my previous question. I’m not convinced that Lisp code is as Homoiconic as machine code on a Von Neumann architecture. It seems obvious to me that in both cases code is represented as data, but it also seems apparent that you can exploit this property much more freely in machine code than you can in Lisp.

When mucking around with machine code, self modifying code is so easy it happens all the time, often by accident and with (in my experience) hilarious results. While writing a simple “print the numbers 0-15” program I might have an “off by one” error with one of my pointers. I’ll end up accidentally dumping whatever is in Register 1 into the address in memory that contains the next instruction, and a random instruction gets executed instead. (Always great when it’s some sort of “goto”. God knows where it’s going to end up and what it’s going to do after that happens)

There really is no separation between code and data. Everything is simultaneously an instruction (even if it’s just a NOP), a pointer, and a plain old number. And it’s possible for the code to change before your eyes.

Please help me with a Lisp scenario I’ve been scratching my head over. Say I’ve got the following program:

(defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (- n 1)))))
; -- Demonstrate the output of factorial --
; -- The part that does the Self modifying goes here –
; -- Demonstrate the changed output of factorial

Now what I want to happen is to append to this program some Lisp code which will change the * to a +, change the <= to a >=, stick a (+ 1 2 3) somewhere in there, and generally bugger the function up. And then I want the program to execute the absolute mess that results.

Key point: Unless I’ve made some fatal error in the sample code you’re only allowed to alter the -– More code goes here –- part. What you see above is the code. I don’t want you quoting the entire list and storing it in a variable so that it can be manipulated and spat out as a separate function with the same name; I don’t want a standard redefinition of factorial as something completely different. I want that code, right there that I can see on my screen to change itself before my eyes, just like machine code.

If this is an impossible/unreasonable request then it only solidifies further in my mind the idea that Homoiconicity is not a discrete property that a language either has or doesn’t have, it is a spectrum and Lisp isn't at the bleeding edge. (Alternatively Lisp is as Homoiconic as they come and I'm looking for some other term to describe machine-code-esque self-modification)

Cutcherry

also, inb4 comment that the code on my screen is unlikely to change before my eyes because it's just some text on a webpage. If you honestly don't understand what I mean and aren't trolling I'll try to clarify some more :) – Cutcherry

Typical machine code is not "homoiconic", and assembly language less so. Although machine code is an array of bits, machine languages do not have the tools to specifically manipulate arrays of bits that represent machine language programs. For instance, given an array of bits, you don't even know where, say, the 17th instruction starts, unless they are all exactly the same length. If you insert code into a template, branch offsets which cross the insertion point have to be recalculated and patched. You need a big library of routines to do anything, and it's not included in machine language. – Hausmann

Machine languages do indeed have the tools to specifically manipulate arrays of bits that represent machine language programs. Every time you use a "store" instruction that's exactly what's going on. – Cutcherry

sounds like a question for programmers stackexchange... – Quahog

Answer 1

That's easy. You only need to change the list representation. All you need is a Lisp interpreter.

The Common Lisp implementation LispWorks provides us with a Lisp interpreter:

CL-USER 137 > (defun factorial (n)
                (if (<= n 1)
                    1
                  (* n (factorial (- n 1)))))
FACTORIAL

CL-USER 138 > (fifth (function-lambda-expression #'factorial))
(IF (<= N 1) 1 (* N (FACTORIAL (- N 1))))

CL-USER 139 > (fourth (fifth (function-lambda-expression #'factorial)))
(* N (FACTORIAL (- N 1)))

CL-USER 140 > (setf (first (fourth (fifth (function-lambda-expression
                                             #'factorial))))
                    '+)
+

CL-USER 141 > (fourth (fifth (function-lambda-expression #'factorial)))
(+ N (FACTORIAL (- N 1)))

CL-USER 142 > (factorial 10)
55

CL-USER 143 > (setf (first (fourth (fifth (function-lambda-expression
                                             #'factorial))))
                    '*)
*

CL-USER 144 > (factorial 10)
3628800

Here is an example where a function modifies itself. To make it slightly easier, I use a feature of Common Lisp: it allows me to write code which is not just some nested list, but a graph. In this case the function can access its own code:

CL-USER 180 > (defun factorial (n)
                (if (<= n 1)
                    1
                  (progn 
                    (setf (first '#1=(* n (factorial (- n 1))))
                          (case (first '#1#)
                            (+ '*)
                            (* '+)))
                    #1#)))
FACTORIAL

Above function alternatively uses + or * by modifying its code.

#1= is a label in the expression, #1# then references that label.

CL-USER 181 > (factorial 10)
4555

In earlier times (70s/80s) in some Lisp groups the developers were not using a text editor to write Lisp code, but a structure editor. The editor commands were directly changing the structure of the Lisp code.

Mechanist

haha wow. That's awesome. I've been looking for something like that for yonks. And I guess there's nothing to stop you from doing this sort of thing outside of a REPL too (So you could potentially have a recursive function that modifies itself over and over again?) – Cutcherry

Please note this is not portable Common Lisp, as FUNCTION-LAMBDA-EXPRESSION is allowed to return NIL. – Ostiole

@ThomasBartscher: true. I also assume that it's an interpreter - also something which is not portable. Common Lisp not only is about the portable language, but also where individual implementations have a degree of freedom (Interpreter vs. Compiler, development vs. delivery, optimizations, garbage collection, ...). Just pick a Common Lisp implementation which has the right feature set. – Mechanist