[HN Gopher] Lisp implemented in Rust macros
___________________________________________________________________
Lisp implemented in Rust macros
Author : quasigloam
Score : 281 points
Date : 2024-09-13 21:31 UTC (1 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| gleenn wrote:
| 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?
| alilleybrinker wrote:
| 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 wrote:
| 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.
| dokyun wrote:
| 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 wrote:
| > 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 wrote:
| > 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.lispw
| orks.com/documentation/HyperSpec/Body/t_arr... (and not even
| hash-tables, these are completely untyped!).
| dokyun wrote:
| > 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
| duetosymmetry wrote:
| Greenspun's tenth rule strikes again!
| https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule
| dgfitz wrote:
| What defines "sufficiently complicated" I wonder? Seems like a
| shit definition.
| StableAlkyne wrote:
| It's just a funny observation he made, it's not meant to be a
| rigorous academic definition :)
| eyelidlessness wrote:
| The rule defines it tautologically. Which is sufficiently
| unambiguous for its purpose!
| throw-the-towel wrote:
| 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.
| munificent wrote:
| I like that the "sufficiently complicated" part bothered you,
| but not the "ad hoc", "informally-specified", "bug-ridden",
| or "slow" parts.
| krick wrote:
| 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.
| devjab wrote:
| Isn't that sort of the point? It makes the argument
| impossible to dispute. If it's not slow or big-ridden,
| then it's just not sufficiently complicated. Which you're
| correct to call out.
|
| I think what makes it work is that Common Lisp very
| quickly becomes a faster way to do things because of how
| insanely efficient it is.
| samatman wrote:
| A man of culture would never refer to an epigram as a
| definition.
| kazinator wrote:
| 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.
| ithkuil wrote:
| "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)
| orwin wrote:
| My experience is: once you have enough different FSM and
| reducers that you need to abstract them, the 'sufficiently
| complicated' criterion is made.
| ForOldHack wrote:
| 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!
| bigdict wrote:
| nah, this is about codebases that are not themselves primarily
| lisp implementations
| kazinator wrote:
| 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 wrote:
| 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?
| pjmlp wrote:
| Except it is been like 60 years that any proper Lisp
| implementation has more than plain cons lists.
| PhilipRoman wrote:
| Pretty sure it applies to Common Lisp itself too.
| vasvir wrote:
| yes but not recursively!
| arnsholt wrote:
| 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.
| hun3 wrote:
| It would be fun if it was "half Prolog, half Common Lisp"
| Guthur wrote:
| I've now used both professionally. I look forward to
| hopefully using both in the same project. Though not
| holding my breath.
| rfl890 wrote:
| I think that's the joke
| klrtaj wrote:
| 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 wrote:
| 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 wrote:
| Store where?
|
| C++ templates are a lambda calculus, there's no notion of
| memory cells or state.
| jasfas wrote:
| 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?
| p4bl0 wrote:
| That was fun. Thanks for sharing!
| quasigloam wrote:
| 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
| detourdog wrote:
| Does this reinforce Greenspan's 10th rule?
| fallat wrote:
| I would love for you to elaborate on lessons learned in the
| project readme!
| elif wrote:
| Hmmmmmmm.... Rustemacs?
| celeritascelery wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| It would, but lisp has prefix operators, so you wouldn't
| have to worry about it getting confused.
| quasigloam wrote:
| Although in a Lisp such as Scheme, you could pass around
| the negation operator in something like (map - '(1 2 3)),
| so it would be a valid concern that it might clash.
| tmtvl wrote:
| The problem with that is that there are spaces between
| map, -, and '(1 2 3). The only way to get spaces into a
| name is by using vertical bars: (defvar
| |do i 10| 1.100)
| anothername12 wrote:
| Does Rust have something like a reader macro where you can
| have arbitrary syntax for a bit?
| throwup238 wrote:
| 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 wrote:
| > 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.
| brundolf wrote:
| Wow and it uses macro_rules
| krick wrote:
| 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 wrote:
| Rust is definitely not a _simple_ language, I agree there.
|
| I am quite likely a bit naive 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 wrote:
| 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 wrote:
| 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...
| quasigloam wrote:
| No problem! I had fun making it, for such a silly little
| project it's given me a surprising amount of joy. If you
| want to look at another cool project that's tangentially
| related, have a look at Sectorlisp.
| zxexz wrote:
| Oh, I'm very well acquainted with Sectorlisp - I even
| have a scrappy local package on nixos to build, boot and
| launch a qemu repl for it locally! Somewhere around here
| there's an HDD in an X200 that probably still has it in
| the boot sector on its HDD.
|
| I think I objectively suck at lisp, but that doesn't
| preclude me from being a "Greenspan enjoyer" :) I think
| all of my projects that used Selenium ended up with a
| haphazardly-pieced-together lisp interpreter as their
| scripting tool after I realized whatever I was writing
| was effectively becoming a DSL in a .ini/.yaml/.toml
| file. These days, I mostly use nix, but my dream is a
| lispy NixOS (yes, I know of and have used Guix, but I
| really just want a lisp<>Nix 'native' compiler, and to be
| able to use it with nixpkgs without hassle).
| pkolaczk wrote:
| > 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.
| huijzer wrote:
| 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.)
| rapsey wrote:
| 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 wrote:
| 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 wrote:
| 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).
| xedrac wrote:
| Yes, easy enough but annoying. Going the other direction
| (async -> sync) is a bit more problematic though. Now
| you've got to wrap things in spawn_blocking(), which
| isn't nearly as benign.
| IshKebab wrote:
| 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 )
| josmar wrote:
| If it's Turing Complete, there will be a LISP for it
| Validark wrote:
| This is super awesome!
| meindnoch wrote:
| But C++ is not a sane language because templates are Turing-
| complete, right?
| danschuller wrote:
| 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 wrote:
| 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 wrote:
| 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.
| ramon156 wrote:
| 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 wrote:
| There are C++ template debugging tools in IDEs.
| keybored wrote:
| There's Turing Complete and Turing Tarpit.[1]
|
| [1] Which one is the Rust macro system? I have no idea.
| djha-skin wrote:
| Obligatory reference to Carp[1], the lisp that uses borrow
| checking; the "rust" of lisps.
|
| 1: https://github.com/carp-lang/Carp
___________________________________________________________________
(page generated 2024-09-14 23:00 UTC)