Friday, February 20, 2015

Turing tarpits in Rust's macro system

Bitwise Cyclic Tag is an extremely simple automaton slash programming language. BCT uses a program string and a data string, each made of bits. The program string is interpreted as if it were infinite, by looping back around to the first bit.

The program consists of commands executed in order. There is a single one-bit command:

0: Delete the left-most data bit.

and a single two-bit command:

1 x: If the left-most data bit is 1, copy bit x to the right of the data string.

We halt if ever the data string is empty.

Remarkably, this is enough to do universal computation. Implementing it in Rust's macro system gives a proof (probably not the first one) that Rust's macro system is Turing-complete, aside from the recursion limit imposed by the compiler.

#![feature(trace_macros)]

macro_rules! bct {
    // cmd 0:  d ... => ...
    (0, $($ps:tt),* ; $_d:tt)
        => (bct!($($ps),*, 0 ; ));
    (0, $($ps:tt),* ; $_d:tt, $($ds:tt),*)
        => (bct!($($ps),*, 0 ; $($ds),*));

    // cmd 1p:  1 ... => 1 ... p
    (1, $p:tt, $($ps:tt),* ; 1)
        => (bct!($($ps),*, 1, $p ; 1, $p));
    (1, $p:tt, $($ps:tt),* ; 1, $($ds:tt),*)
        => (bct!($($ps),*, 1, $p ; 1, $($ds),*, $p));

    // cmd 1p:  0 ... => 0 ...
    (1, $p:tt, $($ps:tt),* ; $($ds:tt),*)
        => (bct!($($ps),*, 1, $p ; $($ds),*));

    // halt on empty data string
    ( $($ps:tt),* ; )
        => (());
}

fn main() {
    trace_macros!(true);
    bct!(0, 0, 1, 1, 1 ; 1, 0, 1);
}

This produces the following compiler output:

bct! { 0 , 0 , 1 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
...
bct.rs:19:13: 19:45 error: recursion limit reached while expanding the macro `bct`
bct.rs:19         => (bct!($($ps),*, 1, $p ; $($ds),*));
                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

You can try it online, as well.

Notes about the macro

I would much rather drop the commas and write

// cmd 0:  d ... => ...
(0 $($ps:tt)* ; $_d:tt $($ds:tt)*)
    => (bct!($($ps)* 0 ; $($ds)*));

// cmd 1p:  1 ... => 1 ... p
(1 $p:tt $($ps:tt)* ; 1 $($ds:tt)*)
    => (bct!($($ps)* 1 $p ; 1 $($ds)* $p));

// cmd 1p:  0 ... => 0 ...
(1 $p:tt $($ps:tt)* ; $($ds:tt)*)
    => (bct!($($ps)* 1 $p ; $($ds)*));

but this runs into the macro future-proofing rules.

If we're required to have commas, then it's at least nice to handle them uniformly, e.g.

// cmd 0:  d ... => ...
(0 $(, $ps:tt)* ; $_d:tt $(, $ds:tt)*)
    => (bct!($($ps),*, 0 ; $($ds),*));

// cmd 1p:  1 ... => 1 ... p
(1, $p:tt $(, $ps:tt)* ; $($ds:tt),*)
    => (bct!($($ps),*, 1, $p ; 1 $(, $ds)*, $p));

// cmd 1p:  0 ... => 0 ...
(1, $p:tt $(, $ps:tt)* ; $($ds:tt),*)
    => (bct!($($ps),*, 1, $p ; $($ds),*));

But this too is disallowed. An $x:tt variable cannot be followed by a repetition $(...)*, even though it's (I believe) harmless. There is an open RFC about this issue. For now I have to handle the "one" and "more than one" cases separately, which is annoying.

In general, I don't think macro_rules! is a good language for arbitrary computation. This experiment shows the hassle involved in implementing one of the simplest known "arbitrary computations". Rather, macro_rules! is good at expressing patterns of code reuse that don't require elaborate compile-time processing. It does so in a way that's declarative, hygienic, and high-level.

However, there is a big middle ground of non-elaborate, but non-trivial computations. macro_rules! is hardly ideal for that, but procedural macros have problems of their own. Indeed, the bct! macro is an extreme case of a pattern I've found useful in the real world. The idea is that every recursive invocation of a macro gives you another opportunity to pattern-match the arguments. Some of html5ever's macros do this, for example.

60 comments:

  1. Thanks. I always appreciate learning your material – they are always humorous and amazing. I am a china tour lover,You can learn more: China tours | China travels | China Trip

    ReplyDelete

  2. بسم الله الرحمن الرحيم عميلنا العزيز نحن نقدم افضل خدمات تنظيف المجالس والشقق بافضل انواع

    التنظيفات المشهود لها عالميا
    شركة تنظيف مجالس بالطائف
    شركة تنظيف مجالس بجازان
    شركة تنظيف مجالس بحائل
    ونحن فى خماتكم 24 ساعة على مدار الشهر

    ReplyDelete
  3. Hello would you mind stating which blog platform you're using?
    I'm looking to start my own blog in the near future but I'm having a tough time choosing between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design seems different then most blogs
    and I'm looking for something unique.
    P.S Sorry for getting off-topic but I had to ask!

    ReplyDelete
  4. My brother suggested I would possibly like this web site.
    He was entirely right. This post actually made my day.
    You cann't consider simply how a lot time I had spent for this information! Thanks!

    ReplyDelete


  5. افضل شركة تنظيف بالاحساء شركة تنظيف بالاحساء
    شركة مكافحة حشرات بالخبر شركة مكافحة حشرات بالخبر
    شركة مكافحة حشرات بالجبيل شركة مكافحة حشرات بالجبيل
    شركة رش مبيدات بالدمام شركة رش مبيدات بالدمام
    شركة مكافحة الحشرات بالاحساء

    ReplyDelete
  6. GBWhatsapp plus APK 7.0 which is an alteration of WhatsApp application. Many individuals use alteration in various kinds of applications and there are additionally various sorts of WhatsApp mods yet the best among all is GBWhatsApp Plus.

    ReplyDelete
  7. Live Net TV is an extraordinary choice to stream satellite TV without paying a penny. There are a lot of channels to look over.
    live net tv apk
    live nettv 4.7
    live nettv app
    https://apkmist.com/live-nettv-apk/

    ReplyDelete
  8. Online astrological consulting services and use it to improve their lives. for more visit astrology services

    ReplyDelete
  9. Clicks Bazaar, an application development company in Chennai, dominated other companies in the mobile application development industry because we know the impact that mobile applications can have to reach and interact with customers. For more app development company in chennai

    ReplyDelete
  10. If you have any questions regarding canon wireless printer setup
    problem or if you are still experiencing some annoying printer problems then just call us +1 800-684-5649

    ReplyDelete
  11. CTR Global is a full-service web design agency in London that has a holistic view of its brand. We believe in the power of positive emotions. We rely on the concept of the brand redesign. We believe that design plays a central role in defining the ideology of the brand. We understand that technology plays a fundamental role in spreading the cause. We integrate each element into our strategy to make an incredibly distinctive proposal. for more web design agency london

    ReplyDelete
  12. Clicks Bazaar is the best SEO company in Delhi NCR with extensive experience in the field and strives to ensure that the websites it develops are ranked and prioritized by search engines. With more than a decade’s experience in providing pioneer internet marketing solutions and satisfying its customers for more seo company in delhi ncr

    ReplyDelete
  13. Wow i can say that this is another great article as expected of this blog.Bookmarked this site..
    pop slots free chips

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. AE Clicks is one of the top Web design company Dubai. With a team of highly skilled web developers and web designers, we have successfully completed over 300+ projects across various industries.

    ReplyDelete
  16. اشكال بلاط الحوش تراكوتا من الانواع المميزة
    شركة نقل اثاث بابها
    شركة تنظيف بحفر الباطن

    كم يكلف تبليط الحوش ؟ الحمامات من الاماكن التي يجب ان تكون نظيفة دائماً و احيانا نظافة الحمامات تعتمد علي عدم توازن البلاط و بالتالي تقف المياه ولا تسير في اتجاه الصرف و تلك الاخطاء تكن بسبب الالتوائات الموجودة في البلاط و السبب الاساسي هي الصناعة، يجب ايها الاخ القارئ ان تنفق ما في جيبك من اجل اختيار افضل انواع البلاط من حيث جودة البلاطة الاساسية في الصنع و من حيث الالوان.شركة تسليك مجارى بالمدينة المنورة
    شركة تنظيف بحفر الباطن

    المواصفات التي يمتلكها البلاط و السيراميك الذي يتواجد لدينا

    ReplyDelete
  17. We support all types of HP printer troubleshooting and service. Just enter the model number of your printer in 123.hp.com to identify the software and drivers your printer requires. Download and install it in your mac and 'Run' the file. The process is easy however if you have any doubts or queries regarding HP printers contact us.

    ReplyDelete




  18. Fastsocial provides some of the best social media services which will help you in your social growth and connecting more people and aware about your work or proffesion all kinds of social media services at best prices , some of the services are best place to buy LinkedIn connections.

    ReplyDelete
  19. Thanks for sharing this stuff.. pinoybay replays provide you all the replays which you will be watch online in hd.
    pinoy tambayan shows
    kadingon ginto full hd

    ReplyDelete
  20. I have recently started a blog, the information you offer on this website has helped me greatly. Thanks for all of your time & work.
    Packers And Movers Hyderabad

    ReplyDelete
  21. That's really interesting and helpful. We are providing quality items Outdor furniture nz which you will be get online in Auckland in a single click.

    ReplyDelete
  22. Watch Pinoy TV, Pinoy Lambingan, Pinoy Tambayan, Pinoy Ako, Pinoy1TV, Pinoy Channel, Pinoy Teleserye, Pinoy TV Shows Replay, Pinoy Network episode. you are Amazing and doing a great job. Watch all Fipino replays online in hd,.pinoy channel replays.

    ReplyDelete
  23. Get Shifting/Relocation Quotation from ###Packers and Movers Delhi. Packers and Movers Delhi 100% Affordable and Reliable ***Household Shifting Services. Compare Transportation Charges and Save Time, Verified and Trusted Packers and Movers in Delhi, Cheap and Safe Local, Domestic House Shifting @
    Packers And Movers Delhi

    ReplyDelete
  24. Get Packers and Movers Kolkata List of Top Reliable, 100% Affordable, Verified and Secured Service Provider. Get Free ###Packers and Movers Kolkata Price Quotation instantly and Save Cost and Time. ???Packers and Movers Kolkata Reviews and Compare Charges for household Shifting, Home/Office Relocation, ***Car Transportation, Pet Relocation, Bike SHifting @ Packers and Movers Kolkata

    ReplyDelete
  25. Superb post, we enjoyed each and everything as per written in your post. Thank you for this informative article because it’s really helpful, I really like site.
    Please visit our website: Local Packers And Movers Bangalore

    ReplyDelete
  26. I rarely share my story with people, not only because it put me at the lowest point ever but because it made me a person of ridicule among family and friends. I put all I had into Binary Options ($690,000) after hearing great testimonies about this new investment

     strategy. I was made to believe my investment would triple, it started good and I got returns (not up to what I had invested). Gathered more and involved a couple family members, but I didn't know I was setting myself up for the kill, in less than no time all we had put ($820,000) was gone. It almost seem I had set them up, they came at me strong and hard. After searching and looking for how to make those scums pay back, I got introduced to maryshea03@gmail.com to WhatsApp her +15623847738.who helped recover about 80% of my lost funds within a month.

    ReplyDelete
  27. Permainan Sabung Ayam tentunya sudah pada tahu ya, yang dimana ayam melawan ayam pertandingan yang sangat seru ini bisa kalian nonton secara live lohh, banyak yang bermain di situs kami dan merasa sangat nyaman, bagi kalian yang ingin bermain bisa kunjungi situs kami, dijamin kalian akan merasa sangat senang.

    Download S128 Apk

    aplikasi sabung ayam

    aplikasi sabung ayam s128

    aplikasi s128 apk

    aplikasi s128

    s128 apk sabung ayam

    s128 apk


    Daftar s128

    daftar sabung ayam s128

    daftar s128 sabung ayam

    daftar s128 apk


    Sabung ayam deposit pulsa

    s128 deposit pulsa


    Login s128


    Link alternatif s128

    situs alternatif s128

    link alternatif sabung ayam

    link alternatif L128

    link alternatif s12888

    link alternatif s1288

    ReplyDelete
  28. Permainan tembak ikan adalah permainan yang paling rame orang mainkan, apalagi jika pelayanannya yang sangat memuaskan bagi anda tentunya kalian pasti akan merasa sangat puas juga kan ?, bagi kalian yang sangat menyukai permainan tembak ikan bisa datang ke situs kami :)

    https://www.aplikasijoker123.org/

    https://www.aplikasijoker123.org/daftar-akun-slot-joker123/

    https://www.aplikasijoker123.org/login-joker388-slot/

    https://www.aplikasijoker123.org/joker123-deposit-pulsa/

    https://www.aplikasijoker123.org/download-joker388-apk/

    https://www.aplikasijoker123.org/link-alternatif-joker123/

    ReplyDelete
  29. ما در شرکت الو اپلیکیشن با استفاده از این پشتوانه به ios طراحی اپلیکیشن و اندروید بصورت Native، تحت وب و Hybrid می پردازیم؛ اپلیکیشن هایی که در طول زمان کارایی خود را حفظ کرده و می توان امکانات آنها را توسعه و ارتقا داد.

    ReplyDelete
  30. Get your favourite Filipino tv shows online and all Teleserye Pinoy Tv shows Get videos and download all ofw pinoy tv

    ReplyDelete
  31. Despite the fact that this product has a few easy to use highlights, there are a few defects that happen now and again. Going over specialized glitches is certainly not another thing. On the off chance that during whenever you do go over any such issue you can don't hesitate to contact the QuickBooks Support Phone Number +1-888-403-0506, where you can achieve proficient direction towards taking care of your concern. More Detail Visit here: https://nethopeted.com/services/quickbooks-support-number/

    Our Video For Guide: https://www.youtube.com/watch?v=W3SR4RqRuYMM

    https://www.youtube.com/watch?v=hQxpX1-6j48 -

    https://www.youtube.com/watch?v=dd9k6CCg1aY -

    https://www.youtube.com/watch?v=9cjAVNdBPCU -

    https://www.youtube.com/watch?v=RBv3Gz2z0p8 -

    https://www.youtube.com/watch?v=dlnNyDYjdtI -

    https://www.youtube.com/watch?v=vEVANvqicSQ

    ReplyDelete
  32. ما همیشه سعی بر این داریم که استاندارد های بین المللی و جدید ترین تکنولوژی ها را در ساخت اپ اندروید و iOS بکار گیریم.

    ReplyDelete
  33. The Canon Pixma G3200 is an across the board inkjet printer having incredible print, sweep and duplicate capacities. It is a good gadget for the two Windows and macOS. However, you may interface your printer straightforwardly to a PC or PC utilizing a USB link, or to your system switch remotely utilizing WiFi. At the point when you are prepared to, Read more how to connect canon pixma g3200 printer to wifi

    ReplyDelete
  34. I like the way of your article posting. It is very informative and have importance in future. Hey! If you guys having the issues regarding the printer call our toll free number or visit our website 123 com setup at any time 24 x 7.

    ReplyDelete
  35. Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 스포츠중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 무료스포츠중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL KBO중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL K리그중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 한국프로야구중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 대만농구중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 러시아하키중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 중국롤LPL중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 동남아롤PCS중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 코로나중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL LCK중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 해외스포츠중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 해외축구중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 스포츠티비

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 스포츠분석

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 스포츠분석사이트

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 해외스포츠분석

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL nba중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 느바중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL mlb중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 믈브중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 해외농구중계

    Free Sports Live Streaming Tv Soccer Basketball Football Baseball Volleyball Pingpong Tennis LOL 무료농구중계

    ReplyDelete
  36. Do you search for a house of fun free spins? This is your best occasion for getting a stunning version of it! Our Powerful Domain Has a lot of coins for all gamers out there! Check house of fun free coins

    ReplyDelete
  37. This is the right webpage for anybody who wishes to understand this topic. You realize a whole lot its almost hard to argue with you (not that I actually would want to…HaHa). You definitely put a fresh spin on a topic that's been discussed for ages. Excellent stuff, just great! gogoanime

    ReplyDelete
  38. I blog often and I really appreciate your information. This article has really peaked my interest. I'm going to bookmark your website and keep checking for new information about once a week. I opted in for your RSS feed as well.movieswood

    ReplyDelete
  39. CROWNQQ I AGEN BANDARQ I BANDARQ ONLINE I ADUQ ONLINE I DOMINOQQ TERBAIK
    Yuk Buruan ikutan bermain di website CrownQQ

    Sekarang CROWNQQ Memiliki Game terbaru Dan Ternama loh...

    9 permainan :
    => Poker
    => Bandar Poker
    => Domino99
    => BandarQ
    => AduQ
    => Sakong
    => Capsa Susun
    => Bandar 66
    => Perang Baccarat (NEW GAME)

    => Bonus Refferal 20%
    => Bonus Turn Over 0,5%
    => Minimal Depo 20.000
    => Minimal WD 20.000
    => 100% Member Asli
    => Pelayanan DP & WD 24 jam
    => Livechat Kami 24 Jam Online
    => Bisa Dimainkan Di Hp Android0619679319
    => Di Layani Dengan 5 Bank Terbaik
    => 1 User ID 9 Permainan Menarik

    Ayo gabung sekarang juga hanya dengan
    mengklick CrownQQ

    Link Resmi CrownQQ:
    ratuajaib.com
    ratuajaib.net

    BACA JUGA BLOGSPORT KAMI:
    Agen BandarQ Terbaik
    Win CrownQQ
    Daftar CrownQQ
    Agen Poker Online

    Info Lebih lanjut Kunjungi :
    WHATSAPP : +855882357563
    Line : CS CROWNQQ
    Facebook : CrownQQ Official

    ReplyDelete
  40. Nice Blog!
    Know More About How to install diagnostic tool? Get live support 24*7 from QuickBooks expert on tool-free Number.
    Click here to know How to install diagnostic tool
    Dial for any tech support: 1-844-908-0801

    ReplyDelete
  41. Nice Blog !
    If dealing with QuickBooks Desktop Error 6189 816, fix it by calling our QuickBooks experts at 1-855-6OO-4O6O. QuickBooks error 6189 816 occurs when a user attempts to open or access a Company file from a network device.

    ReplyDelete
  42. All the articles here are informative. It is beneficial to the newcomers. Thanks for posting such a nice post.
    Make White Background
    Clipping Path
    Image Masking Service

    ReplyDelete
  43. If you want to watch free TV shows and movies using streaming websites then there is no alternative as compared to putlocker. Also, we made a list of alternatives like Putlocker sites that you can use to stream movies and TV shows.

    Here is the official Putlocker website with a lot of trending and popular movies to watch.

    Hosting companies and law enforcement are always taking down free streaming sites, including long-time favorite Putlockers. So what are you supposed to do when your usual top pick for free streaming isn’t working anymore?

    Don’t put away that popcorn just yet! I tested 47 leading streaming sites for safety, usability, and speed. After careful review and ranking based on streaming catalog size, content, and quality, I’ve found offical proxy site of Putlockers.

    ReplyDelete
  44. For those who like to do new things but get money right here. บาคาร่า

    ReplyDelete
  45. Your article is great. Come in, read my stuff, click. >> ไก่ชน

    ReplyDelete