program-data identity

[va1]

We all know the powerful implications of the program-data identity
in LISP. Most of the power comes from one side of the identity,
that is, that programs are data.

What about the other side of the identity, that lists are treated
as programs (by the interpreter)? I'm wondering what advantages
there are to being able to treat any list as a program (i.e. procedure
call).

For example, say we choose a new representation for 'procedure call'
expressions. Suppose we required that they look like (applic op x y),
i.e. a list that must be headed by the 'applic' symbol (which is not
bound to anything, it's just syntactic). In other words, procedure
calls
are special forms, too.
Now, only a finite number of lists actually correspond to programs
(i.e. all our special forms). Lists no longer default to
procedure-call
semantics.
What disadvantages, other than the inconvenience of always having to
cons 'applic' and the list desired to be 'executed' together, are
implied by such a representation?
Concrete examples?

[Pascal Costanza]

va1 wrote:
> We all know the powerful implications of the program-data identity
> in LISP. Most of the power comes from one side of the identity,
> that is, that programs are data.
>
> What about the other side of the identity, that lists are treated
> as programs (by the interpreter)? I'm wondering what advantages
> there are to being able to treat any list as a program (i.e. procedure
> call).

A list can only be successfully treated as a function call only if the
environment in which it is interpreted (or compiled, no difference here)
contains a definition for the name with which you refer to a function.

Your requirement to always use 'applic' doesn't change this in a
fundamental way: It is already the case that not all "correct" lists are
also "correct" programs.

Pascal

[va1]

Yes, I was assuming the environment had bindings for the cars of
the lists in question.

What I mean is, to the interpreter an unquoted list is treated
as a function call if it's not first found to be a special form.
(then, of course if there's no binding for it's car field, we get
an error).

I'm wondering what happens if we take away that default meaning
of an unquoted list: how inconvenienced we'd be (apart from verbosity).

I don't have enough experience with Scheme to know how handy
the default meaning of an unquoted list really is.

For starters, we wouldn't have a recursive definition for the 'applic'
special form. That is, internally an applic structure wouldn't be
represented as nested 'applic's. Meaning function application
expressions always have to be preconceived. That bugs me.
Should it?

[Pascal Bourguignon]

"va1" <hue...@csd.uwo.ca> writes:

Some data is program, not all data is program. And this data is
program, ONLY given an interpreter.

You should not concentrate too much on lists. You may have an
interpreter that runs byte arrays instead of lists.

Have a look at the following toy compiler/interpreter. The output of
ASSEMBLE is a vector of bytes, taken as input by the EXECUTE
interpreter. These data vectors of bytes are program, only for this
EXECUTE interpreter. They'd be nothing to CL:EVAL (but a literal
vector). An interpreter can accept any kind of data, not only
lists. (Most accept only source strings).

Now, if you have a PROLOG interpreter, it won't execute lists such as:

(let ((a 0))
(if (< a 1) (print "too small")))

but it could gladly execute lists such as:

(((too_small _a) --> (_a < 1))
((too_small _a) --> (_a >= 1) (print "too small"))
(too_small 0))

On the other hand, CL:EVAL will execute the former, but give an error
for the later.

;;----------------------------------------

(defun make-label () (gensym))

(defstruct (asm (:constructor nil) (:type list)) label op arg)
(defun make-asm (op &optional arg label) (list label op arg))

(defstruct (proc (:constructor nil) (:type list)) head tail)
(defun make-proc () (list nil nil))
(defun proc-length (proc) (length (proc-head proc)))

(defun gen-asm (proc asm)
(if (null (proc-head proc))
(setf (proc-head proc) (list asm)
(proc-tail proc) (proc-head proc))
(setf (cdr (proc-tail proc)) (list asm)
(proc-tail proc) (cdr (proc-tail proc))))
proc);;gen-asm

(defun append-asm (&optional proc1 proc2)
(if (null proc1)
(make-proc)
(progn
(if (null (proc-head proc1))
(setf (proc-head proc1) (proc-head proc2)
(proc-tail proc1) (proc-tail proc2))
(setf (cdr (proc-tail proc1)) (proc-head proc2)
(proc-tail proc1) (proc-tail proc2)))
proc1)));;append-asm

(defun compile-statement-list (tree)
(reduce (function append-asm) (mapcar (function compile-statement) tree)))

(defun compile-expression (tree)
(let ((proc (make-proc)))
(cond ((atom tree)(error "Invalid syntax tree ~S." tree))
(t (case (first tree)
((integer) (gen-asm proc (make-asm 'push-imm (second tree))))
((< = >)
;; 1- generate the first expression
(append-asm proc (compile-expression (second tree)))
;; 2- generate the second expression
(append-asm proc (compile-expression (third tree)))
;; 3- generate the comparaison
(gen-asm proc (make-asm (first tree))))
(:otherwise
(error "Invalid expression tree ~S." tree)))))
proc));;compile-expression

(defun compile-statement (tree)
(let ((proc (make-proc)))
(cond ((null tree))
((atom tree)
(error "Invalid syntax tree ~S." tree))
(t (case (first tree)
((if)
(let ((lab-else (make-label))
(lab-end (make-label)))
;; 1- generate the expression
(append-asm proc (compile-expression (second tree)))
;; 2- generate the jump if false
(gen-asm proc (make-asm 'jump-if-false lab-else))
;; 3- generate the then
(append-asm proc (compile-statement-list (third tree)))
;; 4- generate the jump to end
(gen-asm proc (make-asm 'jump nil lab-end))
;; 5- generate the else
(gen-asm proc (make-asm nil nil lab-else))
(append-asm proc (compile-statement-list (fourth tree)))
;; 6- generate the end
(gen-asm proc (make-asm nil nil lab-end))))
((print)
(append-asm proc (compile-expression (second tree)))
(gen-asm proc (make-asm 'print)))
(:otherwise
(error "Invalid token in tree ~S." tree)))))
proc));;compile-statement

(defun compile-program (tree)
(let ((proc (compile-statement-list tree)))
(gen-asm proc (make-asm 'ret))
proc))

(compile-program '((print (integer 0))
(if (< (integer 42) (integer 0))
((if (= (integer 2) (integer 0))
((print (integer 1)))
((print (integer 2)))))
((print (integer 3))))
(print (integer 4))))

(defparameter +asm-code+ #(push-imm < = > jump-if-false jump print ret))

(deftype bytecode nil '(unsigned-byte 8))

(defun build-label-table (proc)
(let ((address 0)
(table (make-hash-table)))
(map nil (lambda (asm)
(unless (null (asm-label asm))
(setf (gethash (asm-label asm) table) address))
(setf (asm-label asm) address)
(unless (null (asm-op asm))
(incf address (if (null (asm-arg asm)) 1 2))))
(proc-head proc))
(values table address)));;build-label-table

(defun assemble (proc)
(multiple-value-bind (label-table code-size) (build-label-table proc)
(let ((code (make-array (list code-size) :element-type 'bytecode)))
(map nil
(lambda (asm)
(unless (null (asm-op asm))
(setf (aref code (asm-label asm))
(let ((bcode (position (asm-op asm) +asm-code+)))
(unless bcode
(error "Invalid asm operator ~S." (asm-op asm)))
bcode))
(unless (null (asm-arg asm))
(setf (aref code (1+ (asm-label asm)))
(cond
((symbolp (asm-arg asm))
(let ((address (gethash (asm-arg asm) label-table)))
(or address
(error "Invalid label ~S." (asm-arg asm)))))
((integerp (asm-arg asm)) (asm-arg asm))
(t (error "Invalid argument ~S." asm)))))))
(proc-head proc))
code)));;assemble

(defun execute (bytecode &key verbose)
(let ((stack (make-array '(100) :element-type 'integer
:fill-pointer 0 :adjustable t))
(pc 0))
(macrolet ((pop () `(vector-pop stack))
(push (arg) `(vector-push-extend ,arg stack))
(trace (&rest args) `(when verbose (print (list ,@args))))
(top (&optional (offset 0))
`(aref stack (- (fill-pointer stack) 1 ,offset))))
(loop
(case (aref bytecode pc)
((0) ;; push-imm
(trace pc 'push-imm (aref bytecode (1+ pc)))
(push (aref bytecode (incf pc))) (incf pc))
((1) ;; <
(trace pc '< (top 0) (top 1) '--> (if (< (top 0) (top 1)) 0 1))
(push (if (< (pop) (pop)) 0 1)) (incf pc))
((2) ;; =
(trace pc '= (top 0) (top 1) '--> (if (= (top 0) (top 1)) 0 1))
(push (if (= (pop) (pop)) 0 1)) (incf pc))
((3) ;; >
(trace pc '> (top 0) (top 1) '--> (if (> (top 0) (top 1)) 0 1))
(push (if (> (pop) (pop)) 0 1)) (incf pc))
((4) ;; jump-if-false
(trace pc 'jump-if-false (top 0) '--> 'pc '= (aref bytecode (1+ pc)))
(if (= 0 (pop))
;; jump
(setf pc (aref bytecode (incf pc)))
(incf pc)))
((5) ;; jump
(trace pc 'jump '--> 'pc '= (aref bytecode (1+ pc)))
(setf pc (aref bytecode (incf pc))))
((6) ;; print
(trace pc 'print (top))
(print (pop)) (incf pc))
((7) ;; ret
(trace pc 'ret)
(return-from execute))
(:otherwise (error "Invalid bytecode pc=~S byte=~S stack=~S~"
pc (aref bytecode pc) stack)))
(when verbose (finish-output))))));;execute

(defstruct env
(stack (make-array '(100) :element-type 'integer
:fill-pointer 0 :adjustable t)))

(defun interpret-expression (expr env)
(cond
((atom expr) (error "Invalid syntax expr ~S." expr))
(t (case (first expr)
((integer) (vector-push-extend (second expr) (env-stack env)))
((< = >)
(interpret-expression (second expr) env)
(interpret-expression (third expr) env)
(vector-push-extend (if (funcall (first expr)
(vector-pop (env-stack env))
(vector-pop (env-stack env)))
0 1) (env-stack env)))
(:otherwise
(error "Invalid expression expr ~S." expr))))));;interpret-expression

(defun interpret-statement (stat env)
(cond ((atom stat) (error "Invalid statement ~S." stat))
(t (case (first stat)
((print)
(interpret-expression (second stat) env)
(print (vector-pop (env-stack env))))
((if)
(interpret-expression (second stat) env)
(interpret-statements (if (zerop (vector-pop (env-stack env)))
(fourth stat)
(third stat)) env))
(:otherwise
(error "Invalid statement ~S." stat))))));;interpret-statement

(defun interpret-statements (statements env)
(map nil (lambda (statement) (interpret-statement statement env)) statements))

(defun interpret-program (sexp)
(interpret-statements sexp (make-env)))

#||

CL-USER> (compile-program '((print (integer 0))
(if (< (integer 42) (integer 0))
((if (= (integer 2) (integer 0))
((print (integer 1)))
((print (integer 2)))))
((print (integer 3))))
(print (integer 4))))

(((NIL PUSH-IMM 0) (NIL PRINT NIL) (NIL PUSH-IMM 42) (NIL PUSH-IMM 0)
(NIL < NIL) (NIL JUMP-IF-FALSE #:G2037) (NIL PUSH-IMM 2) (NIL PUSH-IMM 0)
(NIL = NIL) (NIL JUMP-IF-FALSE #:G2039) (NIL PUSH-IMM 1) (NIL PRINT NIL)
(#:G2040 JUMP NIL) (#:G2039 NIL NIL) (NIL PUSH-IMM 2) (NIL PRINT NIL)
(#:G2040 NIL NIL) (#:G2038 JUMP NIL) (#:G2037 NIL NIL) (NIL PUSH-IMM 3)
(NIL PRINT NIL) (#:G2038 NIL NIL) (NIL PUSH-IMM 4) (NIL PRINT NIL)
(NIL RET NIL))
((NIL RET NIL)))
CL-USER> (assemble (compile-program '((print (integer 0))
(if (< (integer 42) (integer 0))
((if (= (integer 2) (integer 0))
((print (integer 1)))
((print (integer 2)))))
((print (integer 3))))
(print (integer 4)))))

#(0 0 6 0 42 0 0 1 4 25 0 2 0 0 2 4 21 0 1 6 5 0 2 6 5 0 3 6 0 4 6 7)
CL-USER> (execute (assemble (compile-program
'((print (integer 0))
(if (< (integer 42) (integer 0))
((if (= (integer 2) (integer 0))
((print (integer 1)))
((print (integer 2)))))
((print (integer 3))))
(print (integer 4))))))

0
3
4
NIL
CL-USER>
||#

--
__Pascal Bourguignon__ http://www.informatimago.com/

Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.

[GP lisper]

On 3 Mar 2005 04:51:41 -0800, <hue...@csd.uwo.ca> wrote:
> We all know the powerful implications of the program-data identity
> in LISP. Most of the power comes from one side of the identity,
> that is, that programs are data.
>
> What about the other side of the identity, that lists are treated
> as programs (by the interpreter)? I'm wondering what advantages
> there are to being able to treat any list as a program (i.e. procedure
> call).

This is the whole point of such programs as lilgp.lisp. Great for
solving tough relational problems.

--
Everyman has three hearts;
one to show the world, one to show friends, and one only he knows.

[Ulrich Hobelmann]

va1 wrote:
> For example, say we choose a new representation for 'procedure call'
> expressions. Suppose we required that they look like (applic op x y),
> i.e. a list that must be headed by the 'applic' symbol (which is not
> bound to anything, it's just syntactic). In other words, procedure
> calls
> are special forms, too.
> Now, only a finite number of lists actually correspond to programs
> (i.e. all our special forms). Lists no longer default to
> procedure-call
> semantics.
> What disadvantages, other than the inconvenience of always having to
> cons 'applic' and the list desired to be 'executed' together, are
> implied by such a representation?
> Concrete examples?
>

As you said, it's mostly inconvenient, I guess. Unlike XML, Lisp is
actually human-read/writeable. While explicitly tagging any Lisp form
with its type (like fun-application) works, it's simply more convenient
to assume that everything that's not tagged with a known special form
has to be a macro or function call.

Otherwise, obviously, current Scheme and Scheme with your suggested
change are isomorphic.

[Pascal Costanza]

va1 wrote:
> Yes, I was assuming the environment had bindings for the cars of
> the lists in question.
>
> What I mean is, to the interpreter an unquoted list is treated
> as a function call if it's not first found to be a special form.
> (then, of course if there's no binding for it's car field, we get
> an error).
>
> I'm wondering what happens if we take away that default meaning
> of an unquoted list: how inconvenienced we'd be (apart from verbosity).

Not much, apart from the increased number of keystroke. We already have
to use unquoted lists in order to make our intentions clear.

> I don't have enough experience with Scheme to know how handy
> the default meaning of an unquoted list really is.
>
> For starters, we wouldn't have a recursive definition for the 'applic'
> special form. That is, internally an applic structure wouldn't be
> represented as nested 'applic's. Meaning function application
> expressions always have to be preconceived. That bugs me.
> Should it?

Does it bug you that your CD player doesn't play DVDs?

Pascal

[A. Huerter]

>
> Does it bug you that your CD player doesn't play DVDs?
>

Of course not; there's no way of making it do so. But I
can turn any symbol-headed list into a function call just
by defining an appropriate binding.

[Pascal Costanza]

You can change a CD player into a DVD player by opening it up and
replacing its drive. ;)

Can we agree on not stretching analogies too far? ;-)

Pascal

[Pascal Bourguignon]

Pascal Costanza <p...@p-cos.net> writes:

It's not stretched too far. Hofstadter used it a lot. You can also
open up the source of your program and replace the interpreter for
data of form X by an interpreter for data of form Y.

--
__Pascal Bourguignon__ http://www.informatimago.com/

The mighty hunter
Returns with gifts of plump birds,
Your foot just squashed one.