5 ms·

Why is this quoting the top-level lambda expression arguments? Unless I'm mistaken that's not how JMC did it. For example, to define a binding the cited resourc

Why is this quoting the top-level lambda expression arguments? Unless I'm mistaken that's not how JMC did it. For example, to define a binding the cited resource http://www.paulgraham.com/rootsoflisp.html http://www.paulgraham.com/rootsoflisp.html uses (defun null (x) (eq x '())) Replacing the defun with an env binding, I believe the value translates to: (lambda (x) (eq x '())) I don't think this should be quoted? Even though lambda isn't typically assumed in the "seven primitives," it _is_ required by the runtime. Are your function calls implicitly dropping quotes when evaluating arguments?

jart 5y ago
Author here. The quotes are indeed needed. Emacs does the same thing. For example: ((lambda (x) (message "%S" x)) (1)) ;; fails: no such function `1' ((lambda (x) (message "%S" x)) (quote (1))) ;; prints (1) The original evaluator is defined so that if the first item of a list, is a list whose first item is LAMBDA, then what it does is it calls Evlis() and Pairlis() which is sort of like a glorified version of Python's zip() function, to attach all the subsequent list items to the parameter name list. ((LAMBDA (ARG1 ARG2 ARG3) <YOUR PROGRAM GOES HERE>) (QUOTE VAL1) (QUOTE VAL2) (QUOTE VAL3)) This is the "venus fly trap" that the blog post mentions. The process of evaluation causes the expression the clamp in on itself where the args get digested into an association list which can be referenced and then the payload is evaluated. This was all non-obvious to me, even after using LISP casually for years, since we normally don't write code that way. Now it's possible to add extra code to the evaluator so that if a naked lambda is encountered, i.e. it sees (LAMBDA ...) rather than ((LAMBDA ...) ...), it just lets it pass through, so you don't need the quotes. We did that originally, but deemed it non-essential and was removed, since that would have made it much harder to hit the 512-byte goal.
- akkartik 5y ago
  By Emacs do you mean Elisp? Your session there is not surprising to me. I don't have emacs handy but what does this do? ((lambda (f) (f)) (lambda() 42)) You might need to throw a 'funcall in there or something, but my hypothesis is that this will work (return 42) without needing the top-level argument to be quoted. 'lambda is a deep special case, basically. I understand that functions always zip through their arguments, evaluating each one. But when you quote the args in the call, I tend to expect the arguments to not be evaluated within 'evlis. I'm surprised that quoting args makes the interpreter smaller! That's pretty interesting. But I think this interpreter will have some behavior that is surprising to anyone used to all extant lisps for examples like this: ((lambda (sym) (cons sym 3)) (quote a)) Here there's no binding for 'a. I expect this to return (a . 3) in JMC's original Lisp.
  - anderskaseorg 5y ago
    The lambdas are quoted because they’re lambdas, not because they’re arguments. In a more fully-featured Lisp, the code (LAMBDA () 42) would evaluate to a special function data type with no direct representation in terms of cons cells. That’s a luxury this implementation can’t afford, so its data representation of a function is the same as its code representation: a cons cell whose car is the atom LAMBDA. With this design, the code (LAMBDA () 42) would be self-evaluating: it would evaluate to the same thing as the code (QUOTE (LAMBDA () 42)). But since the latter syntax works, there’s no need to waste bytes supporting the former syntax. In the absence of that special support, the default meaning of the code (LAMBDA () 42) is to call a function named LAMBDA, just like the code (FOO () 42) calls a function named FOO.
    - akkartik 5y ago
      I see. Kinda. The 'lambda in the first line isn't quoted. And the eval itself seems identical to JMC. So this is just the substrate level and only when evaluating args? Does that seem right?
      - jart 5y ago
        The first item in the list is evaluated, just like the other items in the list. For example: ((LAMBDA (ARG1 ARG2 ARG3) <YOUR PROGRAM GOES HERE>) (QUOTE VAL1) (QUOTE VAL2) (QUOTE VAL3)) Is the same syntax as a normal function call: (PROGRAM (QUOTE VAL1) (QUOTE VAL2) (QUOTE VAL3)) The only difference is that, since it's the root-level program, the binding of the name PROGRAM can't have happened yet. So it's simply inlined into the expression. The Apply() part of the evaluator has a special case for recognizing this, which causes evaluation of the first argument to terminate: int Apply(int fn, int x, int a) { int t1, si, ax; if (ISATOM(fn)) { switch (fn) { case ATOM_CAR: return Car(Car(x)); case ATOM_CDR: return Cdr(Car(x)); case ATOM_ATOM: return ISATOM(Car(x)) ? ATOM_T : NIL; case ATOM_CONS: return Cons(Car(x), Car(Cdr(x))); case ATOM_EQ: return Car(x) == Car(Cdr(x)) ? ATOM_T : NIL; default: // recurse to turn (FUNC ARG1 ARG2) into ((LAMBDA ...) ARG1 ARG2) return Apply(Eval(fn, a), x, a); } } // evaluate ((LAMBDA ...) ARG1 ARG2) if (Car(fn) == ATOM_LAMBDA) { t1 = Cdr(fn); si = Pairlis(Car(t1), x, a); ax = Car(Cdr(t1)); return Eval(ax, si); } return UNDEFINED; } The Eval() function which calls Apply() has already evaluated all the list items except for the first one, which is left to Apply() to figure out. The reason why things are this way is because, in order to save space, the REPL loop doesn't maintain a persistent set of global variables. Due to the NIL here, each expression is its own hermetic job: void Repl(void) { for (;;) { Print(Eval(Read(), NIL)); } } If you changed that NIL to be an alist that's populated by things like defun / setq / etc. in the global scope, then the usability of the language improves dramatically. We didn't do it due to the singular focus on size. But at the same time that simply means we left fun opportunities for improvement to anyone wishing to hack on the codebase and make it their own.
bsder 5y ago
> Why is this quoting the top-level lambda expression arguments? I suspect mostly because the implementation stumbled into the dynamic binding/lexical binding/FEXPR traps that hit all the early Lisps. > Here it becomes clear that, in its most bare essential form, beneath the macros and abstractions, LISP actually has an unpleasant nature where name bindings (or assignments) look like a venus fly trap. Ayup. A lot of these problems were addressed by the late John Shutt in his thesis about vau calculus in the Kernel programming language: FEXPRS: https://en.wikipedia.org/wiki/Fexpr https://en.wikipedia.org/wiki/Fexpr John Shutt's vau calculus thesis: http://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf http://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unre... John Shutt's Kernel Language--"Revised-1 Report on the Kernel Programming Language" https://core.ac.uk/download/pdf/47187352.pdf https://core.ac.uk/download/pdf/47187352.pdf The "magic" is that the "$vau" operative closes over the environment when it is defined so that it can execute later in that environment--this is the "static/lexical environment". However, when you actually execute the "$vau" operative, you also pass in the "execution/dynamic" environment so that the code that the "$vau" operative runs can choose to do what it wants with the arguments--do nothing, evaluate them in the lexical environment, or evaluate them in the dynamic environment. It's a powerful concept, but difficult to compile so got kind of relegated from the Lisp/Scheme languages. For something which seems to implement it properly, see the "Oh" UNIX shell: https://github.com/michaelmacinnis/oh https://github.com/michaelmacinnis/oh https://www.youtube.com/watch?v=v1m-WEZz46U https://www.youtube.com/watch?v=v1m-WEZz46U I would mumble that the fact that "list" is defined as "cons pairs with a final nil()" is also a pain in the ass. I understand why it was originally done this way, but it makes the idea of a "sequence" abstraction so very much more painful. It's one of the reasons why Clojure dropped it.
- akkartik 5y ago
  I love chatting about Kernel :D Here's my most recent post: https://lobste.rs/s/d0hogq/problem_with_macros#c_nozcrm https://lobste.rs/s/d0hogq/problem_with_macros#c_nozcrm Thanks for showing me Oh! It really has f-exprs?! I didn't immediately see it in https://github.com/michaelmacinnis/oh/blob/main/doc/manual.md https://github.com/michaelmacinnis/oh/blob/main/doc/manual.m...

jart 5y ago

Author here. The quotes are indeed needed. Emacs does the same thing. For example: ((lambda (x) (message "%S" x)) (1)) ;; fails: no such function `1' ((lambda (x) (message "%S" x)) (quote (1))) ;; prints (1) The original evaluator is defined so that if the first item of a list, is a list whose first item is LAMBDA, then what it does is it calls Evlis() and Pairlis() which is sort of like a glorified version of Python's zip() function, to attach all the subsequent list items to the parameter name list. ((LAMBDA (ARG1 ARG2 ARG3) <YOUR PROGRAM GOES HERE>) (QUOTE VAL1) (QUOTE VAL2) (QUOTE VAL3)) This is the "venus fly trap" that the blog post mentions. The process of evaluation causes the expression the clamp in on itself where the args get digested into an association list which can be referenced and then the payload is evaluated. This was all non-obvious to me, even after using LISP casually for years, since we normally don't write code that way. Now it's possible to add extra code to the evaluator so that if a naked lambda is encountered, i.e. it sees (LAMBDA ...) rather than ((LAMBDA ...) ...), it just lets it pass through, so you don't need the quotes. We did that originally, but deemed it non-essential and was removed, since that would have made it much harder to hit the 512-byte goal.

akkartik 5y ago
By Emacs do you mean Elisp? Your session there is not surprising to me. I don't have emacs handy but what does this do? ((lambda (f) (f)) (lambda() 42)) You might need to throw a 'funcall in there or something, but my hypothesis is that this will work (return 42) without needing the top-level argument to be quoted. 'lambda is a deep special case, basically. I understand that functions always zip through their arguments, evaluating each one. But when you quote the args in the call, I tend to expect the arguments to not be evaluated within 'evlis. I'm surprised that quoting args makes the interpreter smaller! That's pretty interesting. But I think this interpreter will have some behavior that is surprising to anyone used to all extant lisps for examples like this: ((lambda (sym) (cons sym 3)) (quote a)) Here there's no binding for 'a. I expect this to return (a . 3) in JMC's original Lisp.
- anderskaseorg 5y ago
  The lambdas are quoted because they’re lambdas, not because they’re arguments. In a more fully-featured Lisp, the code (LAMBDA () 42) would evaluate to a special function data type with no direct representation in terms of cons cells. That’s a luxury this implementation can’t afford, so its data representation of a function is the same as its code representation: a cons cell whose car is the atom LAMBDA. With this design, the code (LAMBDA () 42) would be self-evaluating: it would evaluate to the same thing as the code (QUOTE (LAMBDA () 42)). But since the latter syntax works, there’s no need to waste bytes supporting the former syntax. In the absence of that special support, the default meaning of the code (LAMBDA () 42) is to call a function named LAMBDA, just like the code (FOO () 42) calls a function named FOO.
  - akkartik 5y ago
    I see. Kinda. The 'lambda in the first line isn't quoted. And the eval itself seems identical to JMC. So this is just the substrate level and only when evaluating args? Does that seem right?
    - jart 5y ago
      The first item in the list is evaluated, just like the other items in the list. For example: ((LAMBDA (ARG1 ARG2 ARG3) <YOUR PROGRAM GOES HERE>) (QUOTE VAL1) (QUOTE VAL2) (QUOTE VAL3)) Is the same syntax as a normal function call: (PROGRAM (QUOTE VAL1) (QUOTE VAL2) (QUOTE VAL3)) The only difference is that, since it's the root-level program, the binding of the name PROGRAM can't have happened yet. So it's simply inlined into the expression. The Apply() part of the evaluator has a special case for recognizing this, which causes evaluation of the first argument to terminate: int Apply(int fn, int x, int a) { int t1, si, ax; if (ISATOM(fn)) { switch (fn) { case ATOM_CAR: return Car(Car(x)); case ATOM_CDR: return Cdr(Car(x)); case ATOM_ATOM: return ISATOM(Car(x)) ? ATOM_T : NIL; case ATOM_CONS: return Cons(Car(x), Car(Cdr(x))); case ATOM_EQ: return Car(x) == Car(Cdr(x)) ? ATOM_T : NIL; default: // recurse to turn (FUNC ARG1 ARG2) into ((LAMBDA ...) ARG1 ARG2) return Apply(Eval(fn, a), x, a); } } // evaluate ((LAMBDA ...) ARG1 ARG2) if (Car(fn) == ATOM_LAMBDA) { t1 = Cdr(fn); si = Pairlis(Car(t1), x, a); ax = Car(Cdr(t1)); return Eval(ax, si); } return UNDEFINED; } The Eval() function which calls Apply() has already evaluated all the list items except for the first one, which is left to Apply() to figure out. The reason why things are this way is because, in order to save space, the REPL loop doesn't maintain a persistent set of global variables. Due to the NIL here, each expression is its own hermetic job: void Repl(void) { for (;;) { Print(Eval(Read(), NIL)); } } If you changed that NIL to be an alist that's populated by things like defun / setq / etc. in the global scope, then the usability of the language improves dramatically. We didn't do it due to the singular focus on size. But at the same time that simply means we left fun opportunities for improvement to anyone wishing to hack on the codebase and make it their own.

bsder 5y ago

> Why is this quoting the top-level lambda expression arguments? I suspect mostly because the implementation stumbled into the dynamic binding/lexical binding/FEXPR traps that hit all the early Lisps. > Here it becomes clear that, in its most bare essential form, beneath the macros and abstractions, LISP actually has an unpleasant nature where name bindings (or assignments) look like a venus fly trap. Ayup. A lot of these problems were addressed by the late John Shutt in his thesis about vau calculus in the Kernel programming language: FEXPRS: https://en.wikipedia.org/wiki/Fexpr https://en.wikipedia.org/wiki/Fexpr John Shutt's vau calculus thesis: http://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf http://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unre... John Shutt's Kernel Language--"Revised-1 Report on the Kernel Programming Language" https://core.ac.uk/download/pdf/47187352.pdf https://core.ac.uk/download/pdf/47187352.pdf The "magic" is that the "$vau" operative closes over the environment when it is defined so that it can execute later in that environment--this is the "static/lexical environment". However, when you actually execute the "$vau" operative, you also pass in the "execution/dynamic" environment so that the code that the "$vau" operative runs can choose to do what it wants with the arguments--do nothing, evaluate them in the lexical environment, or evaluate them in the dynamic environment. It's a powerful concept, but difficult to compile so got kind of relegated from the Lisp/Scheme languages. For something which seems to implement it properly, see the "Oh" UNIX shell: https://github.com/michaelmacinnis/oh https://github.com/michaelmacinnis/oh https://www.youtube.com/watch?v=v1m-WEZz46U https://www.youtube.com/watch?v=v1m-WEZz46U I would mumble that the fact that "list" is defined as "cons pairs with a final nil()" is also a pain in the ass. I understand why it was originally done this way, but it makes the idea of a "sequence" abstraction so very much more painful. It's one of the reasons why Clojure dropped it.

akkartik 5y ago
I love chatting about Kernel :D Here's my most recent post: https://lobste.rs/s/d0hogq/problem_with_macros#c_nozcrm https://lobste.rs/s/d0hogq/problem_with_macros#c_nozcrm Thanks for showing me Oh! It really has f-exprs?! I didn't immediately see it in https://github.com/michaelmacinnis/oh/blob/main/doc/manual.md https://github.com/michaelmacinnis/oh/blob/main/doc/manual.m...