Lisp implemented in Rust macros

293 points by quasigloam 9 months ago | 79 comments
  • duetosymmetry 9 months ago
    Greenspun's tenth rule strikes again! https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule
    • bigdict 9 months ago
      nah, this is about codebases that are not themselves primarily lisp implementations
      • kazinator 9 months ago
        This is correct. Greenspun's Tenth Rule is not meant to be interpreted as applying to projects that are consciously creating a Lisp implementation. It's about programs which are not meant to be language implementations at all reinventing ad hoc infrastructure that is designed in Lisps according to established patterns. For instance, badly reinventing something that functions as symbols.
        • Nevermark 9 months ago
          I conjecture the line is not so easy to draw.

          If you are creating Lisp because you want to create Lisp, like creating Lisp, want to show off creating Lisp, that obviously is not what the Law is about.

          Furthermore, if you create Lisp because you know the Law, know it is inevitable, and want to avoid the caveats and missed bars by doing so explicitly, well then that also is not what the Law is about.

          But if you are going about your business, focused on your independent goal, realize you need Lisp like lists, and then 250 lines of code later realize you have created a solid Lisp unintentionally? Well, congrats on falling into the trap but not getting hurt!

          Personally, I have created both Lisp and Forth multiple times for suitable projects where I wanted some flexible runtime scripting. I am not familiar with the standard version libraries of either and don’t need them.

          Minimal foundation implementations are extremely easy to create, and eliminate any dependencies or sources of mystery.

          Anyone know of any other well designed mininal languages?

        • PhilipRoman 9 months ago
          Pretty sure it applies to Common Lisp itself too.
          • arnsholt 9 months ago
            The corollary to Greenspun’s rule is that any sufficiently complicated Common Lisp program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Prolog.
            • vasvir 9 months ago
              yes but not recursively!
            • rfl890 9 months ago
              I think that's the joke
            • klrtaj 9 months ago
              A great example of the rule is that C++ rediscovers car/cdr at a glacial pace in the template language. In C++26 one can finally get the car of a typename parameter pack with Args...[0].

              I've no idea why they don't introduce car/cdr functions and nil for empty parameter packs and allow to store parameter packs instead of the current syntax insanity.

              • gpderetta 9 months ago
                C++ metaprogramming was done with cons cells already back in '98. The new syntax provides random access instead, which is completely different from linked lists.
                • otabdeveloper4 9 months ago
                  Store where?

                  C++ templates are a lambda calculus, there's no notion of memory cells or state.

                  • jasfas 9 months ago
                    In a struct! Pseudo code for extracting the types from subclasses and calling a multimethod on them:

                      template <typename Result, typename Head, typename ...Tail>
                      struct Foo : Visitor {
                        Result res;
                        UntypedList lst; // This does not exist!
                        Tail... tail;    // This is not possible!
                        Foo(UntypedList l; Head hd, Tail... tl) : lst(l), tail(tl) {
                          hd->accept(*this);
                        }
                        void visit(float *f) {
                          res = Foo<Result, Tail...>(append(lst, f), tail)::res; }
                        }
                      };
                     
                      // Base case that calls the multimethod omitted.
                    
                    There are two issues here: You can't store the parameter pack in Foo() which is later required by the continuation in visit(). And you would have to use tuples and tuple_cat() instead of UntypedList.

                    Why can the compiler not infer the types in such an UntypedList? Why is there no car/cdr for tuples?

                • ForOldHack 9 months ago
                  HA!

                  "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."

                  HA HA!

                  • dgfitz 9 months ago
                    What defines "sufficiently complicated" I wonder? Seems like a shit definition.
                    • kazinator 9 months ago
                      That's explicitly encoded right in the rule itself! When the program contains a bug-ridden, ad-hoc simulacrum of half (or more) of Common Lisp, then it has become sufficiently complicated. When it has less than half, it is not yet sufficiently complicated.
                      • StableAlkyne 9 months ago
                        It's just a funny observation he made, it's not meant to be a rigorous academic definition :)
                        • ithkuil 9 months ago
                          "for any sufficiently X the Y" just means that if you don't observe Y right now, just increase the magnitude of X and you'll inevitably reach the conditions for Y to happen.

                          Famous use of that pattern is Arthur's Clarke "Any sufficiently advanced technology is indistinguishable from magic.". As with OP's quote, this is also vague and imprecise but the point of the idea is that there is a gradient towards which advancements in technology bring us towards a situation where the average person no longer understands how it works and it may as well be magic (while not necessarily defining exactly when does that transition happen)

                          • munificent 9 months ago
                            I like that the "sufficiently complicated" part bothered you, but not the "ad hoc", "informally-specified", "bug-ridden", or "slow" parts.
                            • krick 9 months ago
                              No, I think it's pretty fair. One could argue about these, but except for "slow" these are more quality qualifiers, rather than quantity. So you either agree it's "bug-ridden" or not (i.e. the number and seriousness of bugs in it is negligible by whatever standards). And I think even "slow" can be discussed in the same manner, the actual speed is quantitative, of course, but in the end one either argues that this speed is "slow" or isn't. So, given some rhetoric skills of your opponent it's at least possible for that statement to be proven false, if he convinces you the implementation actually isn't slow nor bug-ridden, or at least if there's no Lisp-implementation indeed.

                              But what is "sufficiently" complicated? Now it's a silly statement that just doesn't pass Popper criterion: even if nobody dares to deny your program is complicated, one can always say it isn't sufficiently complicated, hence the fact it doesn't contain Lisp-interpreter disproves nothing. A man of culture wouldn't use such definitions.

                            • eyelidlessness 9 months ago
                              The rule defines it tautologically. Which is sufficiently unambiguous for its purpose!
                              • throw-the-towel 9 months ago
                                Greenspun's tenth rule, corollary: Any sufficiently precise definition of "complex system" contains an ad hoc, informal, bug-ridden, slow specification of half of Common Lisp.
                              • orwin 9 months ago
                                My experience is: once you have enough different FSM and reducers that you need to abstract them, the 'sufficiently complicated' criterion is made.
                            • celeritascelery 9 months ago
                              I tried doing something similar to this once. I ran into an issue where I couldn’t define symbols with a dash in them (DEFINE MY-FN…). This is because rust will split the tokens on a dash. It was a small thing, but it meant I couldn’t just copy and paste snippets from a real lisp, I had to transform everything to underscore. Is it the same in your implementation?
                              • quasigloam 9 months ago
                                Yes, at the moment I just assume that all atoms are rust idents because that makes it easier to implement (I can just match against $x:ident), so it doesn't support dashes in atoms. I guess you could match against `$x:ident $(- $y:ident)*` instead? That should work I think, I'd have to change some details in some of the arms but it seems like that would be possible.
                                • throwup238 9 months ago
                                  Wouldn’t that match “(foo - bar)” as well as “(foo-bar)”? I don’t think you can get around token whitespace in macro_rules
                                  • quasigloam 9 months ago
                                    Yes it would match both, this would require us to assume that "foo - bar" can only be an atom. It's not a great solution.
                                    • celeritascelery 9 months ago
                                      It would, but lisp has prefix operators, so you wouldn’t have to worry about it getting confused.
                                    • anothername12 9 months ago
                                      Does Rust have something like a reader macro where you can have arbitrary syntax for a bit?
                                      • throwup238 9 months ago
                                        It's almost but not quite arbitrary. It still has to be a valid Rust token stream with matching braces/parens. Since it's whitespace insensitive with respect to tokens and "-" is its own token, "(foo-bar)" and "(foo - bar)" result in the same token stream minus the span information.

                                        You can use proc_macro::Span.line()/column() [1] to track how much whitespace there is between tokens and merge them, but the macro will have to rename them to valid Rust identities ("foo-bar" to "foo_bar") and make sure there's no collisions.

                                        [1] https://doc.rust-lang.org/proc_macro/struct.Span.html#method...

                                    • zozbot234 9 months ago
                                      > I ran into an issue where I couldn’t define symbols with a dash in them

                                      I'm not seeing any issue? (DEFINE MYᜭFN...) works just fine.

                                    • gleenn 9 months ago
                                      I wish there was a well-supported Lisp in Rust, not just the macros. I wonder how much memory safety you would retain or lose being based in Rust. Is it even possible to leverage the borrow checker any any sane way?
                                      • dokyun 9 months ago
                                        Some Lisp compilers like SBCL are already capable of more extensive compile-time type-checking, but its information that the programmer is up to supply, and tends to be the part of the optimization stage rather than normal, incremental development. Lisp is usually defined by its dynamic nature, and run-time type checking is a big part of this. Making the programmer have to worry about how objects are managed before the fact would conflict with the freedom and expressibility one would expect from such a system. It also makes the compilers themselves simpler in comparison: Normal code without any extra declarations is safe by default, some systems might ignore such declarations for always being 'safe' (say if you're on a bytecode VM like CLISP or a Lisp machine that does hardware type-checking). SBCL compiles code quite quickly--so I've heard others tend to be even faster; the Rust compiler on the other hand is more likely to introduce a young programmer to the concept of thrashing. I really see them as two mutually incompatible worlds although they may not seem to be at first glance. One thing to remember is that Lisp is essentially the flagship "The Right Thing" language, while C is the "Worse is Better" language. Rust is neither, it is something entirely different which I think is overdue for a name, perhaps something that reflects the losing characteristics of both philosophies.

                                        (This isn't to discredit the OP article: it's still a cool hack!)

                                        • wild_egg 9 months ago
                                          > perhaps something that reflects the losing characteristics of both philosophies.

                                          Oof. With how much love Rust gets here, I didn't expect to see it being called out like that.

                                          How about "The Worse Thing"?

                                          • BoingBoomTschak 9 months ago
                                            > Some Lisp compilers like SBCL are already capable of more extensive compile-time type-checking, but its information that the programmer is up to supply

                                            Which is nice and all, but very much gimped by the glaring holes in CL's typing tooling: you can't create actual types, only derived types (deftype) and struct/class types. The two consequences of that is that you can't type cons-based lists/trees (arguably THE Lisp data structure) because deftype can't be recursive and you can't create parametric types, it's an internal thing only used for https://www.lispworks.com/documentation/HyperSpec/Body/t_arr... (and not even hash-tables, these are completely untyped!).

                                            • dokyun 9 months ago
                                              > you can't type cons-based lists/trees (arguably THE Lisp data structure) because deftype can't be recursive and you can't create parametric types

                                                (deftype list-of (type)
                                                  `(cons ,type (or null (list-of ,type))))
                                              
                                                (typep '(1 2 3 4) '(list-of integer))
                                                => T
                                              
                                              Most of the standard types from which derived types can be made are parametric types, which specialize on their arguments in different ways. They work the same way as macros. One upon a time I wrote a type specifier that allows you to specialize on a lambda expression, using the ordinary 'satisfies' type that only lets you provide named functions:

                                                (deftype satisfiesp (function)
                                                  (let (predicate)
                                                    (cond ((symbolp function)
                                                           (setq predicate function))
                                                          ((functionp function)
                                                           (setq predicate (gensym))
                                                           (setf (symbol-function predicate) function))
                                                          ((and (consp function) (eq (car function) 'lambda))
                                                           (setq predicate (gensym))
                                                           (compile predicate function))
                                                          (t (error "~S is neither a lambda expression, function or symbol." function)))
                                                    `(satisfies ,predicate)))
                                              
                                              Now you can even type-check on lambda expressions, and quasiquotation can sidestep the issue of capturing variables.

                                                (defvar foo 'bar)
                                                (typep 'bar `(satisfiesp (lambda (x) (eq x ',foo))))
                                                => T
                                              
                                              https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node44.html
                                          • alilleybrinker 9 months ago
                                            Steel seems alright: https://github.com/mattwparas/steel

                                            There are other Lisps too (https://github.com/alilleybrinker/langs-in-rust) though I think they’re less actively maintained.

                                            • robinsonrc 9 months ago
                                              Steel has worked well for me as far as I’ve used it. It’s easy to get going and the partnership with Helix will surely give it a popularity boost over the next year or so.
                                          • 9 months ago
                                            • p4bl0 9 months ago
                                              That was fun. Thanks for sharing!
                                              • quasigloam 9 months ago
                                                Thanks! It was fun to make. It was also instructive, as I learned that rust analyser doesn't handle macros generating millions of tokens :D
                                                • fallat 9 months ago
                                                  I would love for you to elaborate on lessons learned in the project readme!
                                                  • detourdog 9 months ago
                                                    Does this reinforce Greenspan’s 10th rule?
                                                • krick 9 months ago
                                                  Everyone is supposed to be cheering for how "fun" it is, but every time I see anything like that I cannot help but think, that I hate the fact it can be implemented in Rust. It never truly was a simple language, but I think it started as something way more manageable than what it has become.
                                                  • zxexz 9 months ago
                                                    Rust is definitely not a simple language, I agree there.

                                                    I am quite likely a bit naïve here, but I'm having trouble understanding why you hate that this is possible. Now, the macro system definitely can generate near infinitely-complex code, but I'm not getting how implementing a sandboxed lisp using macros is a particularly potent example of the language being less manageable than at its genesis.

                                                    On another note, the fact that the type system is turing-complete, like with C++ templates or the Haskell type system (variously dependent on which GHC languages extensions you're using...), makes me want to see a lisp implemented that way!

                                                    • quasigloam 9 months ago
                                                      Implementing a lisp in the type system would be fun, that's originally what this project was about until I got distracted with macros. Awesome projects like fortraith (https://github.com/Ashymad/fortraith) already exist, and even far more useful projects like dimensioned (compile time dimensional analysis using type level numbers) are inspiring. These examples, although cool, are probably a worse sign for krick for Rust compared with macro_rules being Turing complete.
                                                      • zxexz 9 months ago
                                                        Aha, that's pretty cool! Didn't even scroll more halfway down the page before my lizard brain saw some something resembling Peano numbers.

                                                        Thanks for sharing your project, by the way - between this and the other one you linked, I think I know what my leisure time this weekend is going to consist of...

                                                    • pkolaczk 9 months ago
                                                      > but I think it started as something way more manageable than what it has become.

                                                      Hard disagree here. Rust team is continuously making the language easier to work with by removing limitations and making features more orthogonal. A notable example is non lexical lifetimes, impl Trait in return position or async traits. Also they have removed some features eg before it went 1.0, it even had GCed references built in with special syntax.

                                                      • rapsey 9 months ago
                                                        The only real change since 1.0 was async. If you want to live without async that is completely up to you. It is an entirely optional part of the language.

                                                        If you want a language guided by the principle of simplicity Rust was never that and you have plenty of options elsewhere.

                                                        • xedrac 9 months ago
                                                          Except that many crates only provide an async interface. I actually use async for many things, but the whole colored functions thing is really annoying.
                                                          • chickdilla 9 months ago
                                                            One trick to get out of this is to wrap any function with an asynchronous interface with pollster::block_on which turns the call back into exactly how it would have run if it had been synchronous (which leads to no color leaking).
                                                        • IshKebab 9 months ago
                                                          Nah, it really takes very little for something like this to become possible. I bet you could do it with C macros, which are supposedly simple.

                                                          (I checked; I win this bet: https://github.com/kchanqvq/CSP )

                                                          • huijzer 9 months ago
                                                            Aren’t macro’s always very powerful but at the same time very tricky? I wouldn’t count the macro side into language complexity. It’s an add-on which you can but don’t have to use (I’m talking about creating macro’s here.)
                                                            • josmar 9 months ago
                                                              If it's Turing Complete, there will be a LISP for it
                                                            • brundolf 9 months ago
                                                              Wow and it uses macro_rules
                                                              • 9 months ago
                                                                • meindnoch 9 months ago
                                                                  But C++ is not a sane language because templates are Turing-complete, right?
                                                                  • danschuller 9 months ago
                                                                    C++ is not a sane language for anyone with a passing familiarity. At least Rusts macros aren't literal text substitutions, a move towards the light.
                                                                    • sham1 9 months ago
                                                                      To be fair, neither are C preprocessor macros. They're instead token substitutions. It's not that much better, but they're not literally text substitution. They're at least more clever than just that.

                                                                      They're also of course surprisingly powerful, at the expense of being very cludgy.

                                                                      • pjmlp 9 months ago
                                                                        C++ templates, coupled with compile time programming, and eventually static reflection, make it easier than the multiple macro languages from Rust, with the additional dependency on syn crate.
                                                                      • keybored 9 months ago
                                                                        There’s Turing Complete and Turing Tarpit.[1]

                                                                        [1] Which one is the Rust macro system? I have no idea.

                                                                        • ramon156 9 months ago
                                                                          C++ templates are a hell to develop with, at least macro_expand is a thing in Rust. It's the fact Rust's tooling is so well done.
                                                                          • pjmlp 9 months ago
                                                                            There are C++ template debugging tools in IDEs.
                                                                        • djha-skin 9 months ago
                                                                          Obligatory reference to Carp[1], the lisp that uses borrow checking; the "rust" of lisps.

                                                                          1: https://github.com/carp-lang/Carp

                                                                          • elif 9 months ago
                                                                            Hmmmmmmm.... Rustemacs?
                                                                            • Validark 9 months ago
                                                                              This is super awesome!
                                                                              • MrYHdP8nPLiG 9 months ago
                                                                                [dead]
                                                                                • MIzOjy4EhuJX 9 months ago
                                                                                  [dead]
                                                                                  • IPqLanQvqw7x 9 months ago
                                                                                    [flagged]