undefined | Better HN

0 pointsanderskaseorg3y ago0 comments

The situation with Lisp is exactly the same. To run a Lisp self-interpreter, we don’t pass it a Lisp function:

    (interpret (lambda (x) x))

but rather an encoded version of that Lisp function’s code:

    (interpret (cons 'lambda (cons (cons 'x nil) (cons 'x nil)))

Of course, Lisp gives us a more convenient syntax for the latter, in the form of the quote macro:

    (interpret (quote (lambda (x) x)))

    (interpret '(lambda (x) x))

But the quote macro is not a function; it’s just syntax. If it were a function, you’d expect this to be equivalent:

    (interpret
      (let ((f (lambda (x) x)))
        (quote f)))

which of course it is not.

Although the quote macro is an important part of what makes Lisp Lisp, it’s not a fundamental part of what makes Lisp a programming language. We could write any Lisp program without it (assuming we were still given a way to build a primitive 'symbol).

0 comments

4 comments · 1 top-level

kazinator3y ago· 3 in thread

> The situation with Lisp is exactly the same.

No it isn't, because the Lisp code is already understood to have an encoding. So we don't have to play any Gödel-numbering-like games to get the code to be able to talk about code. That battery is included.

> gives us a more convenient syntax for the latter, in the form of the quote macro

The ' in (cons 'lambda ...) is an instance of quote!

You must write (cons (intern "lambda") ...) to remove quote. Oops, now you're using a different kind of quote: a string literal quote. If you remove that, you will have character literals to otherwise build the symbol name.

I agree that quote is not essential: take out quote and you can still do useful symbolic processing. Just doing interactive testing and writing unit tests will be inconvenient, mainly.

The requirement for quote has a different effect. If we have quote, we can make the additional step in the documentation that all code has the representation produced by quote, even when quote is not being used. When lambda is seen in code, that is actually the same thing that (quote lambda) produces or that (intern "lambda") produces.

The above is almost inescapable if user-defined macros are supported. When code is read, it is not determined at read time what is a macro and what isn't. Therefore it is not known what parts of the form may need to be passed to a user-defined expander function without having been evaluated (and thus in the quote representation). The whole thing is in the quoted encoding, so that quote doesn't have to do anything other than pass through its interior.

anderskaseorgOP3y ago

Yes, I was clear above that I know ' means quote. My experiment is to compare Lisp to a restriction of Lisp where quote only works on symbols. This restriction doesn’t make it any harder to write a self-interpreter.

> If we have quote, we can make the additional step in the documentation that all code has the representation produced by quote, even when quote is not being used. When lambda is seen in code, that is actually the same thing that (quote lambda) produces or that (intern "lambda") produces.

I’m not sure what you’re suggesting here. Certainly the number (+ 2 2) must be distinguishable from the list '(+ 2 2). Even lambda expressions must be distinguishable from their quoted encodings, because otherwise lexical scoping breaks. If you make (lambda () x) equivalent to '(lambda () x), then this breaks:

    (let ((x 1)) (funcall (let ((x 2)) (lambda () x))))

and if you make (lambda () x) equivalent to `(lambda () ',x), then this breaks:

    (let ((x 1)) (funcall (lambda () (let ((x 2)) x))))

Macros expand at compile time, not runtime. Macros are also cool, but not fundamental, and don’t contribute to the ease of writing a self-interpreter.

kazinator3y ago

We can analyze lexical scoping through quote. Here is TXR Lisp doing it:

  1> (defmacro free-vars (expr :env e)
       (if-match (quote @qexp) expr  ;; unwrap quote if it occurs
         (set expr qexp))
       (tree-bind (expansion free-vars free-funs . rest) (expand-with-free-refs expr e)
         ^(quote ,free-vars)))
  free-vars
  2> (let ((a 42)) (free-vars '(lambda () (+ a b))))
  (b)

Roughly speaking, this is the basis for doing things like back-referencing against an existing lexical variable in pattern matching:

  3> (let ((x 1))
       (match (@x @y) '(1 2) y))
  2
  4> (let ((x 1))
       (match (@x @y) '(2 2) y))
  ** match: (@x @y) failed to match object (2 2)

match is nothing but a macro; application code could supply an equivalent, depending only on what is publicly documented.

Syntactically, the variable terms in (@x @y) are in the same category. Yet x is interpreted by the pattern matcher as a bound variable, whose value matches the corresponding object; whereas y is interpreted as a free variable to be lexically bound to the corresponding object.

You just need a macro system with environment parameters, and a defined API into them.

With help from the macro system, we could write an interpreter such that (let ((a 1) (b 2)) (interpret '(list a b))) will yield (1 2). interpret can't be a function; it has to be a macro which analyzes the argument for variables and creates a bridge between those variables and the surrounding lexicals at the point where interpret finds itself. The interpret macro transforms the code somehow and then hands it to an interpreter function.

kazinator3y ago

If we don't have quote for expressions but only for symbols, we can still write the interpreter function, and give it a test case by writing an expression which calculates the code that we want to interpret. Even without quote the language has given us a representation of the syntax that we can rely on.

We have it as a given that (list 'lambda (list 'x) 'x) produces (lambda (x) x).

We do not have such a thing in lambda calculus. We could create an extended lambda calculus which has it.

1 more reply

j / k navigate · click thread line to collapse

0 comments

4 comments · 1 top-level

kazinator3y ago· 3 in thread

> The situation with Lisp is exactly the same.

> gives us a more convenient syntax for the latter, in the form of the quote macro

The ' in (cons 'lambda ...) is an instance of quote!

I agree that quote is not essential: take out quote and you can still do useful symbolic processing. Just doing interactive testing and writing unit tests will be inconvenient, mainly.

anderskaseorgOP3y ago

    (let ((x 1)) (funcall (let ((x 2)) (lambda () x))))

and if you make (lambda () x) equivalent to `(lambda () ',x), then this breaks:

    (let ((x 1)) (funcall (lambda () (let ((x 2)) x))))

Macros expand at compile time, not runtime. Macros are also cool, but not fundamental, and don’t contribute to the ease of writing a self-interpreter.

kazinator3y ago

We can analyze lexical scoping through quote. Here is TXR Lisp doing it:

  1> (defmacro free-vars (expr :env e)
       (if-match (quote @qexp) expr  ;; unwrap quote if it occurs
         (set expr qexp))
       (tree-bind (expansion free-vars free-funs . rest) (expand-with-free-refs expr e)
         ^(quote ,free-vars)))
  free-vars
  2> (let ((a 42)) (free-vars '(lambda () (+ a b))))
  (b)

Roughly speaking, this is the basis for doing things like back-referencing against an existing lexical variable in pattern matching:

  3> (let ((x 1))
       (match (@x @y) '(1 2) y))
  2
  4> (let ((x 1))
       (match (@x @y) '(2 2) y))
  ** match: (@x @y) failed to match object (2 2)

match is nothing but a macro; application code could supply an equivalent, depending only on what is publicly documented.

You just need a macro system with environment parameters, and a defined API into them.

kazinator3y ago

We have it as a given that (list 'lambda (list 'x) 'x) produces (lambda (x) x).

We do not have such a thing in lambda calculus. We could create an extended lambda calculus which has it.

1 more reply

j / k navigate · click thread line to collapse