Rust मैक्रो से लागू किया गया Lisp

 (github.com/RyanWelly)
1 पॉइंट द्वारा GN⁺ 2024-09-15 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • lisp-in-rs-macros Rust के declarative macros भर से चलने वाला एक सरल lexical-scope Lisp interpreter है, और lisp! macro compile time पर code को evaluate करके stringified Lisp value बनाता है
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) rustc की macro expansion प्रक्रिया के दौरान calculate होकर string "A" में expand होता है, और पूरा implementation 250 लाइनों से कम है
  • उदाहरणों में CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY का इस्तेमाल है, और quine example दिखाता है कि Lisp code अपने-आप में evaluate होता है
  • explicit recursion अभी supported नहीं है, लेकिन self application से list append जैसी recursive behavior लिखी जा सकती है; हालांकि DEFINE खुद recursive definitions handle नहीं करता
  • metacircular interpreter example चलता हुआ लगता है, लेकिन ((lambda (X) X) (quote a)) evaluation में 30 सेकंड से ज्यादा लगते हैं और दस लाख से अधिक tokens बनते हैं, इतना inefficient कि cargo sigkill हो जाता है

Rust macros के अंदर चलने वाला Lisp

  • lisp-in-rs-macros Rust के declarative macros भर से लिखा गया lexical-scope Lisp interpreter है
  • lisp! macro दिए गए Lisp code को evaluate करने के बाद calculated Lisp value को stringified करता है
  • उदाहरण के लिए lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) string "A" में expand होता है
  • यह calculation runtime पर नहीं, बल्कि rustc द्वारा macro expand किए जाने वाले compile time पर होती है
  • implementation 250 लाइनों से कम है

Basic usage example

  • CAR, LIST, QUOTE को मिलाकर list का पहला element लिया जा सकता है
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • कई expressions evaluate करने के लिए PROGN का इस्तेमाल होता है
    • PROGN सभी expressions evaluate करता है और आखिरी expression की value return करता है
  • DISPLAY पहले argument को evaluate करता है, फिर println!("{}", stringify!(evaled_argument)) के रूप में expand करके tokens को stringified कर output करता है
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • ऊपर का example "hello there" और "TRUE" print करता है

अपने-आप में evaluate होने वाला quine

  • quine example दिखाता है कि Lisp code अपने-आप में evaluate होता है
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • यह code नीचे जैसे stringify! call में expand होता है
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Recursion और self application

  • यह Lisp फिलहाल explicit recursion support नहीं करता
  • explicit recursion के बिना भी सिर्फ lambda से recursive behavior बनाई जा सकती है
  • example में append function अपने body में append नाम का सीधे उल्लेख नहीं करता, बल्कि self argument के जरिए self-application से recursive call करता है
lisp!(PROGN
(DEFINE append
    (LAMBDA (self X Y)
        (COND
            ((EQ X NIL) Y)
            (TRUE (CONS (CAR X) (self self (CDR X) Y)))
        )))
(append append (QUOTE (A B)) (QUOTE (C D)))

)
  • यह code result के रूप में "(A B C D)" बनाता है

इस्तेमाल की सीमाएं

  • lisp! macro सिर्फ एक expression evaluate करता है
    • कई expressions को (PROGN expr1 expr2 expr3) में wrap करना होगा
  • empty list self-evaluating नहीं है
    • empty list value NIL या (QUOTE ()) से मिल सकती है
    • empty list ही इकलौता falsy object है
  • dotted list support नहीं है
    • CONS मानता है कि आखिरी argument एक list है
  • DEFINE कहीं भी इस्तेमाल किया जा सकता है और empty list में evaluate होता है, लेकिन recursion support नहीं करता
  • non-function atoms में TRUE ही इकलौता self-evaluating है

Supported forms

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE असली Lisp-style recursive definition से ज्यादा Scheme की internal definition जैसा form है

Lisp में लिखा Lisp interpreter

  • repository में इसी Lisp पर लिखा गया metacircular interpreter example शामिल है
  • example दो arguments के लिए Y2 combinator, CADR, CAAR, ASSOC, eval आदि define करता है
  • interpreter चलता हुआ दिखता है, लेकिन ((lambda (X) X) (quote a)) evaluate करने की कोशिश में 30 सेकंड से ज्यादा लगते हैं
  • यह evaluation दस लाख से ज्यादा tokens generate करता है और आखिर में इतना बड़ा हो जाता है कि cargo sigkill हो जाता है
  • explicit Y combinator इस्तेमाल करने वाली recursion यहां खास तौर पर inefficient है
  • इसे ठीक करने के लिए explicit recursion primitive जोड़ना होगा, ऐसा लिखा है
  • metacircular evaluator लिखने की walkthrough के लिए Paul Graham की "Roots of Lisp" recommend की गई है

Implementation method और references

  • technical explanation EXPLANATION.md में है
  • macros मूल रूप से SECD machine simulate करते हैं
    • SECD machine lambda calculus term evaluate करने वाली एक सरल stack-based abstract machine है

References

  • Functional Programming: Application and Implementation by Peter Henderson
  • Ager, Mads Sig, et al. "A functional correspondence between evaluators and abstract machines."
  • The Implementation of Functional Programming Languages by Simon Peyton Jones
  • Matt Might के Lisp-related blog posts: https://matt.might.net

TODO

  • letrec जोड़ना
  • recursive define जोड़ना

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-09-15
Hacker News की राय

  • Greenspun का दसवां नियम फिर आ गया: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • यह ऐसे codebase के बारे में है जिसका मुख्य उद्देश्य Lisp implementation नहीं है, इसलिए यहाँ यह बिल्कुल फिट नहीं लगता
    • इस नियम का अच्छा उदाहरण यह है कि C++ template language के अंदर car/cdr को हिमनद जैसी धीमी रफ्तार से फिर से खोज रहा है
      C++26 में जाकर ही Args...[0] से type-name parameter pack का car मिल पाएगा
      समझ नहीं आता कि खाली parameter pack के लिए nil और car/cdr functions क्यों नहीं लाए जाते, और अभी जैसी syntax की अफरा-तफरी के बजाय parameter packs को store करने की सुविधा क्यों नहीं दी जाती
    • “हर पर्याप्त रूप से जटिल C या Fortran program में Common Lisp के आधे हिस्से का एक ad-hoc, अनौपचारिक specification वाला, bug-भरा और धीमा implementation शामिल होता है” — यह वाक्य तुरंत याद आता है
    • “पर्याप्त रूप से जटिल” का क्या मतलब है, समझ नहीं आता; definition खास अच्छी नहीं है

  • पहले मैंने भी कुछ ऐसा ही किया था, लेकिन dash वाले symbols define नहीं कर पाने की समस्या थी
    DEFINE MY-FN... जैसा कुछ काम नहीं करता था, क्योंकि Rust dash पर token को तोड़ देता था
    छोटा सा फर्क है, लेकिन असली Lisp code snippet को जस का तस paste नहीं कर सकते और सबको underscore में बदलना पड़ता था। जिज्ञासा है कि इस implementation में भी ऐसा ही है या नहीं

    • अभी यह मानकर चल रहा है कि सभी atoms Rust identifiers हैं। इससे implementation आसान हो जाता है क्योंकि $x:ident से match कर सकते हैं, इसलिए atom के अंदर dash support नहीं है
      इसके बजाय $x:ident $(- $y:ident)* जैसे तरीके से match किया जा सकता है। कुछ macro branch details बदलनी पड़ेंगी, लेकिन संभव लगता है
    • समस्या नहीं दिखती? DEFINE MYᜭFN... ठीक से काम करता है

  • सिर्फ macros नहीं, Rust-based अच्छी तरह supported कोई Lisp implementation हो तो अच्छा होगा
    Rust के ऊपर बनाने पर memory safety कितनी बनी रहेगी या खो जाएगी, यह जानने की उत्सुकता है। क्या borrow checker का sane तरीके से उपयोग करना संभव भी होगा?

    • SBCL जैसे कुछ Lisp compilers ज्यादा व्यापक compile-time type checking भी कर सकते हैं, लेकिन वह जानकारी programmer को देनी होती है और आमतौर पर रोजमर्रा के incremental development से ज्यादा optimization phase का हिस्सा होती है
      Lisp को आम तौर पर उसके dynamic स्वभाव से परिभाषित किया जाता है, और runtime type checking उसका बड़ा हिस्सा है। अगर programmer को object management के तरीके पहले से सोचने के लिए मजबूर किया जाए, तो यह ऐसे system से अपेक्षित freedom और expressiveness से टकराता है
      इसके बजाय compiler खुद अपेक्षाकृत सरल हो सकता है। अतिरिक्त declarations के बिना सामान्य code default रूप से safe होता है, और CLISP जैसी bytecode virtual machine या hardware type checking वाली Lisp machine में ऐसी declarations को ignore कर देने पर भी हमेशा safe रह सकता है
      SBCL code को काफी तेजी से compile करता है, और सुना है कि कुछ दूसरे implementations उससे भी तेज हैं। दूसरी ओर Rust compiler युवा programmers को thrashing की अवधारणा से परिचित कराने की ज्यादा संभावना रखता है
      मेरी नजर में, पहली नजर के उलट, ये दोनों एक-दूसरे के साथ मुश्किल से compatible worlds हैं। Lisp मूलतः “The Right Thing” philosophy की प्रतिनिधि language है, और C “Worse is Better” language है। Rust दोनों में से कोई नहीं है; यह कुछ इतना अलग लगता है कि दोनों philosophies की खराब विशेषताओं को दर्शाने वाला कोई नया नाम चाहिए
      यह सब original post को नीचा दिखाने के लिए नहीं है; यह अब भी एक शानदार hack है
    • Steel ठीक लगता है: https://github.com/mattwparas/steel
      दूसरे Lisps भी हैं (https://github.com/alilleybrinker/langs-in-rust). हालांकि वे कम actively maintained लगते हैं

  • इसे बनाते हुए मजा आया, और यह भी सीखा कि rust-analyser लाखों tokens generate करने वाले macro को handle नहीं कर पाता

  • माहौल ऐसा है कि सबको “मजेदार है” कहकर उत्साहित होना चाहिए, लेकिन जब भी ऐसी चीजें देखता हूँ, मुझे यह बात पसंद नहीं आती कि Rust में यह implement किया जा सकता है
    Rust पहले भी कोई simple language नहीं था, लेकिन लगता है कि शुरुआत की तुलना में अब यह कहीं ज्यादा संभालना मुश्किल हो गया है

    • मैं सहमत हूँ कि Rust simple language नहीं है
      हालांकि यह संभव है, इस बात को आप क्यों नापसंद करते हैं, यह मुझे ठीक से समझ नहीं आता। macro system लगभग अनंत रूप से complex code generate कर सकता है, लेकिन macros से sandboxed Lisp implement करना क्या इस बात का मजबूत उदाहरण है कि Rust शुरुआती दौर से ज्यादा manage करना मुश्किल हो गया है — यह स्पष्ट नहीं है
      वहीं, क्योंकि Rust का type system C++ templates या Haskell type system की तरह Turing complete है, उस तरीके से implement किया गया Lisp भी देखना चाहूँगा
    • इस बात से मैं strongly disagree करता हूँ। Rust team constraints हटाकर और features को अधिक orthogonal बनाकर लगातार language को इस्तेमाल में आसान बना रही है
      प्रमुख उदाहरण हैं non-lexical lifetimes, return position में impl Trait, और async traits। 1.0 से पहले special syntax वाले GC references भी built-in थे, और ऐसे features हटाए भी गए
    • 1.0 के बाद की असल बड़ी change सिर्फ async है। अगर आप async के बिना रहना चाहते हैं तो यह पूरी तरह optional है, और language का पूरी तरह optional हिस्सा है
      अगर आपको simplicity को principle मानने वाली language चाहिए, तो Rust कभी वैसी language था ही नहीं, और विकल्प बहुत हैं
    • ऐसी चीज संभव होने के लिए असल में बहुत कम चीजों की जरूरत होती है। simple माने जाने वाले C macros से भी शायद यह किया जा सकता है
      मैंने check किया, और यह बाजी मैंने जीत ली: https://github.com/kchanqvq/CSP
    • क्या macros हमेशा बहुत powerful और साथ ही tricky नहीं होते? मैं macro side को language complexity में शामिल नहीं करूँगा
      खास तौर पर macros “लिखने” की बात कर रहा हूँ; यह ऐसी अतिरिक्त capability जैसी है जिसे इस्तेमाल भी कर सकते हैं और नहीं भी

  • वाह, यह macro_rules इस्तेमाल करता है

  • लेकिन क्या C++ के बारे में यह नहीं कहा जाता था कि templates Turing complete हैं, इसलिए वह sane language नहीं है?

    • C++ थोड़ा भी जान लें तो पता चल जाता है कि वह sane language नहीं है। कम से कम Rust macros literal text substitution नहीं हैं, इसलिए यह रोशनी की ओर एक कदम है
    • Turing complete और Turing tarpit अलग चीजें हैं
      Rust macro system इनमें से कौन सा है, यह मुझे नहीं पता
    • C++ templates के साथ development करना नरक है। Rust में कम से कम macro_expand है, और Rust tools अच्छी तरह बनाए गए हैं — यह बड़ी बात है

  • Carp को भी छोड़ा नहीं जा सकता। यह borrow checking इस्तेमाल करने वाला Lisp है, और Lisp दुनिया का “Rust” जैसा है
    1: https://github.com/carp-lang/Carp