3 ms·

I know that lisp compilers compile compute heavy trivial functions directly to machine code. But how is the output of a program containing a lisp macro for exam

I know that lisp compilers compile compute heavy trivial functions directly to machine code. But how is the output of a program containing a lisp macro for example. Let's say define a lisp macro don't call it and generate its assembly. What is the machine code output? This is the part I'm speechless about. "The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written. We need to generate an example of something we can't do in C, something which requires evaluation at runtime.

Jtsummers 4y ago
> But how is the output of a program containing a lisp macro for example. I think you have a fundamental confusion about when and where macros are applied. In a compiled CL implementation, macros are expanded prior to compilation. The code will be exactly the same as if there was no macro involved. If you want to see what that might look like take the function body of this simple function: (defun bar (filename) (with-open-file (in filename :element-type '(unsigned-byte 16)) (let ((contents (make-array (file-length in) :element-type '(unsigned-byte 16)))) (read-sequence contents in) contents))) And run it through `macroexpand` (`with-open-file` is the macro I'm particularly interested in here): CL-USER> (macroexpand '(with-open-file (in filename :element-type '(unsigned-byte 16)) (let ((contents (make-array (file-length in) :element-type '(unsigned-byte 16)))) (read-sequence contents in) contents))) (LET ((IN (OPEN FILENAME :ELEMENT-TYPE '(UNSIGNED-BYTE 16))) (#:G659 T)) (UNWIND-PROTECT (MULTIPLE-VALUE-PROG1 (PROGN (LET ((CONTENTS (MAKE-ARRAY (FILE-LENGTH IN) :ELEMENT-TYPE '(UNSIGNED-BYTE 16)))) (READ-SEQUENCE CONTENTS IN) CONTENTS)) (SETQ #:G659 NIL)) (WHEN IN (CLOSE IN :ABORT #:G659)))) Now take that output and put it in a new function, call it `baz`. Then disassemble both `bar` and `baz` (I've done this and included the output of just one because they have the same instructions): EDIT: Snipped the excessively long code, here's a link: https://topaz.github.io/paste/#XQAAAQCODwAAAAAAAAAQYOhAaDnr7QIy+t3L74P+gfSyurN4xBqqRWDKGrfTibEvWKLiZQV6OUDskNamSTE6rKL6Tc41DobwEH/u5gDW2L0lA3v35/1zJ1y6GYXeZrrRB2PfLaksX/d61C9WtCwQuB5kdoZtgD9tkQ1wcJKGC9apdT06udkLusjg3ZfQW+q3+gMlY2UIRcia9P9Jpe0Do089yFEpmZzwcbQjWDhbnTXUG/Jg6leXLrMbqZ0XYJHSgDHy4s8MoIiXPsBHl7K8UG7qQu1LBVFgVApFwzld1lLUqk1/c8+Wh4oVR6nwPc52ddWb/25+p1N5x4RQtrn/iG2U+BgJcjma/XfNVgJVbhZ82rceK9Dlg4zGkDcnDpqfapy7YocJ4f5YXkLrdGYjK2LoWxkZwjGYIGvlFfJCB1MqZbmJLxrHAgCOe+F7VjQE39Mh72bEZjv2rTQKW0/P5Vsg4JcLM2j5/vJRnszz3gTm7+3oxxg/vJ+58JB/1dIwZiXixlGTDm2Sax7u6ykOy9kTtOdqzTptzlcq74XOIjTut4DhWc5GEB6HVjpU8sVMAtmmdu1GdAT3yfiuPcHIoAaKv2FD1nTtDzYx36if8AXQfUr1XeoxYupiA5BfM7nsmVN7cJhutV1rRNEgybudHoG9RDwoCFkIKDsH2Ba2aIzNLpkwS6H6JNNMUrvQ+gZY3FLLPLkhg5/YCAgRjKfv23lg72f8APMQMMW36C5KlcmIpvl9K0JenkXg6AEx1Fqou6vIPXNMskYhCh7eaPGIH6Pj9hrGEF35d+OPKD4U3tn6zKdMElcltcOfodsKUeGOiS+fGmd8VVtQpgymz+0BX6vNB4wIElQukdRd/Ksv/7WOVThauhUMis8hJYeOrfNV838h1x0zcdiVBuMsdTLDo5HwvOfO0BkbgwAzkVT93xWd+HGYKSMv5Z+anFVpYMnw+icd8d5bSvEGOLDkHh96FIvVrH9GB49PQIOOkeJJ+MOgDyqz8SuuRlHOTbep+a3VibYKf80zgcFOcUu03eORCKp56Fxrs3fVgx5xn/TYgzhDw60XpsaPBSL9nobVpJH1e0W2Rx6HedSHhg1ZgGsr20BJB8xPw1/qtjCErimpZzCkWdcF9R2XkSU2qXaEWDGz9u6Wrhr9Jc1tu8W1721kgMSRBlcuvS32V7n5CsNmv1aRyC6KENw71+mLekuJGXbbWqtzIOd05gFUu7PJhDOcAPbUTcAQeaQY3vu0C9LcGM/byfbexPmj957XRo1Bk5OfW73TJsj45w3LNjFeGKN2HuX28UaleHnilNz5OaI5JSs3JYE7LFw//2tYYQA= https://topaz.github.io/paste/#XQAAAQCODwAAAAAAAAAQYOhAaDnr7... (still long, but at least HN will truncate it) It doesn't really make sense to talk about disassembling a macro as a macro is not, itself, what gets compiled when it's applied, but rather its output gets compiled (in a compiled Lisp). > "The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Then every compiled program that uses a tagged union is really an interpreted program (which is a statement you could make a strong argument for, perhaps). The code above is still machine code, though, it's not being interpreted. This is part of the distinction between an interpreter and a runtime. Dynamic dispatch can be applied to statically typed languages as well as dynamically typed languages. > We need to generate an example of something we can't do in C, something which requires evaluation at runtime. Strictly speaking, there is no such thing as something that can be done in Lisp that cannot be done in C. It'll just take a lot more effort in C to do some things like compiling a function on the fly, returning it, and then applying it later. You'd at least need to link in a compiler and feed it some structure which it can then compile into a function which gets returned, probably, as a function pointer.
- terminalcommand 4y ago
  From my conversation with lispm, I discovered that each binary sbcl produces includes the lisp compiler. That means for evaluating expressions that cannot be determined at runtime, SBCL does some kind of JIT compilation. I think this is called incremental compilation: https://en.wikipedia.org/wiki/Incremental_compiler https://en.wikipedia.org/wiki/Incremental_compiler Now it makes sense, SBCL requires a complete compiler embedded in the runtime. Runtime is small enough that you don't care for it. Okay I agree that lisp can be compiled. You just need a clever runtime being able to dynamically compile parts at runtime. If there are lisp implementations that do not require embedding either a compiler or an interpreter in the runtime, I'd doubt their expressiveness.
deleted 4y ago
[deleted]
dreamcompiler 4y ago
> Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written. Not sure what you mean by this but perhaps you're referring to how Lisp allows redefining functions on the fly without relinking? That's done by indirect function calls. Every function call in Lisp jumps indirectly through the function's symbol name (if it has one). This incurs a runtime penalty of one extra memory access per function call, but it enables functions to be redefined on the fly without changing any of their callers. Optimization switches exist to get rid of this extra overhead if you need maximum speed in deployed code.
lispm 4y ago
> But how is the output of a program containing a lisp macro for example. The use of the macro gets expanded at compile time and the expanded code then gets compiled. Lisp macros are designed in such a way that they are be expanded before runtime. > evaluation at runtime Evaluation at runtime does not mean the code gets not compiled. The SBCL implementation of Common Lisp: * (let ((fn-code (quote (lambda (a) (* a 42))))) ;source of function as a list -> FN-CODE (let ((fn (eval fn-code))) ; evaluation of that list FN-CODE ->eval-> FN (prog1 (funcall fn 11) (disassemble fn)))) ; disassembly for (LAMBDA (A)) ; Size: 36 bytes. Origin: #x700568E8E4 ; (LAMBDA (A)) ; 8E4: AA0A40F9 LDR R0, [THREAD, #16] ; binding-stack-pointer ; 8E8: 4A0B00F9 STR R0, [CFP, #16] ; 8EC: EA030CAA MOV R0, R2 ; 8F0: 8B0A80D2 MOVZ R1, #84 ; 8F4: 3C9880D2 MOVZ TMP, #1217 ; 8F8: BE6B7CF8 LDR LR, [NULL, TMP] ; SB-KERNEL:TWO-ARG-* ; 8FC: DE130091 ADD LR, LR, #4 ; 900: C0031FD6 BR LR ; 904: E00120D4 BRK #15 ; Invalid argument count trap 462 You'll see that EVAL at runtime compiles the code on-the-fly and in-memory to ARM64 machine code.
- terminalcommand 4y ago
  You are dissasembling inside the interpreter. Interpreter already reads, evaluates before generating the assembly code. How does EVAL work if the entire program is compiled AoT?
  - lispm 4y ago
    > You are dissasembling inside the interpreter. What you see is no interpreter. It's an interactive interface, reading code, compiling it, executing it, printing the result. There is by default no interpreter. Everything is compiled in SBCL. A Lisp system typically includes an on-board compiler and/or interpreter.
    - terminalcommand 4y ago
      REPL is the interpreter isn't it? When you type the code into sbcl you are using the REPL which is the interpreter. Try running sbcl without the REPL and produce an executable binary file. Maybe the binary representation changes into something with dynamic dispatch?

Jtsummers 4y ago

> But how is the output of a program containing a lisp macro for example. I think you have a fundamental confusion about when and where macros are applied. In a compiled CL implementation, macros are expanded prior to compilation. The code will be exactly the same as if there was no macro involved. If you want to see what that might look like take the function body of this simple function: (defun bar (filename) (with-open-file (in filename :element-type '(unsigned-byte 16)) (let ((contents (make-array (file-length in) :element-type '(unsigned-byte 16)))) (read-sequence contents in) contents))) And run it through `macroexpand` (`with-open-file` is the macro I'm particularly interested in here): CL-USER> (macroexpand '(with-open-file (in filename :element-type '(unsigned-byte 16)) (let ((contents (make-array (file-length in) :element-type '(unsigned-byte 16)))) (read-sequence contents in) contents))) (LET ((IN (OPEN FILENAME :ELEMENT-TYPE '(UNSIGNED-BYTE 16))) (#:G659 T)) (UNWIND-PROTECT (MULTIPLE-VALUE-PROG1 (PROGN (LET ((CONTENTS (MAKE-ARRAY (FILE-LENGTH IN) :ELEMENT-TYPE '(UNSIGNED-BYTE 16)))) (READ-SEQUENCE CONTENTS IN) CONTENTS)) (SETQ #:G659 NIL)) (WHEN IN (CLOSE IN :ABORT #:G659)))) Now take that output and put it in a new function, call it `baz`. Then disassemble both `bar` and `baz` (I've done this and included the output of just one because they have the same instructions): EDIT: Snipped the excessively long code, here's a link: https://topaz.github.io/paste/#XQAAAQCODwAAAAAAAAAQYOhAaDnr7QIy+t3L74P+gfSyurN4xBqqRWDKGrfTibEvWKLiZQV6OUDskNamSTE6rKL6Tc41DobwEH/u5gDW2L0lA3v35/1zJ1y6GYXeZrrRB2PfLaksX/d61C9WtCwQuB5kdoZtgD9tkQ1wcJKGC9apdT06udkLusjg3ZfQW+q3+gMlY2UIRcia9P9Jpe0Do089yFEpmZzwcbQjWDhbnTXUG/Jg6leXLrMbqZ0XYJHSgDHy4s8MoIiXPsBHl7K8UG7qQu1LBVFgVApFwzld1lLUqk1/c8+Wh4oVR6nwPc52ddWb/25+p1N5x4RQtrn/iG2U+BgJcjma/XfNVgJVbhZ82rceK9Dlg4zGkDcnDpqfapy7YocJ4f5YXkLrdGYjK2LoWxkZwjGYIGvlFfJCB1MqZbmJLxrHAgCOe+F7VjQE39Mh72bEZjv2rTQKW0/P5Vsg4JcLM2j5/vJRnszz3gTm7+3oxxg/vJ+58JB/1dIwZiXixlGTDm2Sax7u6ykOy9kTtOdqzTptzlcq74XOIjTut4DhWc5GEB6HVjpU8sVMAtmmdu1GdAT3yfiuPcHIoAaKv2FD1nTtDzYx36if8AXQfUr1XeoxYupiA5BfM7nsmVN7cJhutV1rRNEgybudHoG9RDwoCFkIKDsH2Ba2aIzNLpkwS6H6JNNMUrvQ+gZY3FLLPLkhg5/YCAgRjKfv23lg72f8APMQMMW36C5KlcmIpvl9K0JenkXg6AEx1Fqou6vIPXNMskYhCh7eaPGIH6Pj9hrGEF35d+OPKD4U3tn6zKdMElcltcOfodsKUeGOiS+fGmd8VVtQpgymz+0BX6vNB4wIElQukdRd/Ksv/7WOVThauhUMis8hJYeOrfNV838h1x0zcdiVBuMsdTLDo5HwvOfO0BkbgwAzkVT93xWd+HGYKSMv5Z+anFVpYMnw+icd8d5bSvEGOLDkHh96FIvVrH9GB49PQIOOkeJJ+MOgDyqz8SuuRlHOTbep+a3VibYKf80zgcFOcUu03eORCKp56Fxrs3fVgx5xn/TYgzhDw60XpsaPBSL9nobVpJH1e0W2Rx6HedSHhg1ZgGsr20BJB8xPw1/qtjCErimpZzCkWdcF9R2XkSU2qXaEWDGz9u6Wrhr9Jc1tu8W1721kgMSRBlcuvS32V7n5CsNmv1aRyC6KENw71+mLekuJGXbbWqtzIOd05gFUu7PJhDOcAPbUTcAQeaQY3vu0C9LcGM/byfbexPmj957XRo1Bk5OfW73TJsj45w3LNjFeGKN2HuX28UaleHnilNz5OaI5JSs3JYE7LFw//2tYYQA= https://topaz.github.io/paste/#XQAAAQCODwAAAAAAAAAQYOhAaDnr7... (still long, but at least HN will truncate it) It doesn't really make sense to talk about disassembling a macro as a macro is not, itself, what gets compiled when it's applied, but rather its output gets compiled (in a compiled Lisp). > "The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Then every compiled program that uses a tagged union is really an interpreted program (which is a statement you could make a strong argument for, perhaps). The code above is still machine code, though, it's not being interpreted. This is part of the distinction between an interpreter and a runtime. Dynamic dispatch can be applied to statically typed languages as well as dynamically typed languages. > We need to generate an example of something we can't do in C, something which requires evaluation at runtime. Strictly speaking, there is no such thing as something that can be done in Lisp that cannot be done in C. It'll just take a lot more effort in C to do some things like compiling a function on the fly, returning it, and then applying it later. You'd at least need to link in a compiler and feed it some structure which it can then compile into a function which gets returned, probably, as a function pointer.

terminalcommand 4y ago
From my conversation with lispm, I discovered that each binary sbcl produces includes the lisp compiler. That means for evaluating expressions that cannot be determined at runtime, SBCL does some kind of JIT compilation. I think this is called incremental compilation: https://en.wikipedia.org/wiki/Incremental_compiler https://en.wikipedia.org/wiki/Incremental_compiler Now it makes sense, SBCL requires a complete compiler embedded in the runtime. Runtime is small enough that you don't care for it. Okay I agree that lisp can be compiled. You just need a clever runtime being able to dynamically compile parts at runtime. If there are lisp implementations that do not require embedding either a compiler or an interpreter in the runtime, I'd doubt their expressiveness.

deleted 4y ago

[deleted]

dreamcompiler 4y ago

> Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written. Not sure what you mean by this but perhaps you're referring to how Lisp allows redefining functions on the fly without relinking? That's done by indirect function calls. Every function call in Lisp jumps indirectly through the function's symbol name (if it has one). This incurs a runtime penalty of one extra memory access per function call, but it enables functions to be redefined on the fly without changing any of their callers. Optimization switches exist to get rid of this extra overhead if you need maximum speed in deployed code.

lispm 4y ago

> But how is the output of a program containing a lisp macro for example. The use of the macro gets expanded at compile time and the expanded code then gets compiled. Lisp macros are designed in such a way that they are be expanded before runtime. > evaluation at runtime Evaluation at runtime does not mean the code gets not compiled. The SBCL implementation of Common Lisp: * (let ((fn-code (quote (lambda (a) (* a 42))))) ;source of function as a list -> FN-CODE (let ((fn (eval fn-code))) ; evaluation of that list FN-CODE ->eval-> FN (prog1 (funcall fn 11) (disassemble fn)))) ; disassembly for (LAMBDA (A)) ; Size: 36 bytes. Origin: #x700568E8E4 ; (LAMBDA (A)) ; 8E4: AA0A40F9 LDR R0, [THREAD, #16] ; binding-stack-pointer ; 8E8: 4A0B00F9 STR R0, [CFP, #16] ; 8EC: EA030CAA MOV R0, R2 ; 8F0: 8B0A80D2 MOVZ R1, #84 ; 8F4: 3C9880D2 MOVZ TMP, #1217 ; 8F8: BE6B7CF8 LDR LR, [NULL, TMP] ; SB-KERNEL:TWO-ARG-* ; 8FC: DE130091 ADD LR, LR, #4 ; 900: C0031FD6 BR LR ; 904: E00120D4 BRK #15 ; Invalid argument count trap 462 You'll see that EVAL at runtime compiles the code on-the-fly and in-memory to ARM64 machine code.

terminalcommand 4y ago
You are dissasembling inside the interpreter. Interpreter already reads, evaluates before generating the assembly code. How does EVAL work if the entire program is compiled AoT?
- lispm 4y ago
  > You are dissasembling inside the interpreter. What you see is no interpreter. It's an interactive interface, reading code, compiling it, executing it, printing the result. There is by default no interpreter. Everything is compiled in SBCL. A Lisp system typically includes an on-board compiler and/or interpreter.
  - terminalcommand 4y ago
    REPL is the interpreter isn't it? When you type the code into sbcl you are using the REPL which is the interpreter. Try running sbcl without the REPL and produce an executable binary file. Maybe the binary representation changes into something with dynamic dispatch?