wingolog

maxwell's equations of software

11 December 2009 2:23 PM (scheme | guile | meta-circular | evaluator | compiler)

There was some interesting feedback on my last article, and I ended up wanting to say too much in reply that here I am again, typing at the ether.

Stephen reflects the common confusion that somehow this is just a little file that might or might not work. No man, this is Guile! That's the implementation of Guile's eval. So unit tests, yes, we have more than 12000 of them. Only some of them specifically test the evaluator, but all of them go through the evaluator.

But to be honest, I think unit tests help, but when I'm hacking the compiler the most useful test is to simply rebuild the compiler. If it successfully bootstraps, usually we're doing pretty well.

Zed raises a more direct criticism:

This is why I hate lisp: [link to my article] Long and dense, no comments, not semantic. That's "awesome code"?

I don't think I used the word "awesome", but yes, I believe so, in the sense of "inspiring awe" -- at least for me.

I'm going to call on my homie Alan Kay for some support here. There was an oft-cited interview with Alan Kay a few years back, when he described eval as "Maxwell's equations of software". I quote:

[Interviewer:] If nothing else, Lisp was carefully defined in terms of Lisp.

[Alan Kay:] Yes, that was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!” This is the whole world of programming in a few lines that I can put my hand over.

I realized that anytime I want to know what I’m doing, I can just write down the kernel of this thing in a half page and it’s not going to lose any power. In fact, it’s going to gain power by being able to reenter itself much more readily than most systems done the other way can possibly do.

Just for context, here is that half-a-page -- Maxwell's equations of software:

evalquote is defined by using two main functions, called eval and apply. apply handles a function and its arguments, while eval handles forms. Each of these functions also has another argument that is used as an association list for storing the values of bound variables and function names.

 evalquote[fn;x] = apply[fn;x;NIL]

where

 apply[fn;x;a] =
       [atom[fn] → [eq[fn;CAR] → caar[x];
                    eq[fn;CDR] → cdar[x];
                    eq[fn;CONS] → cons[car[x];cadr[x]];
                    eq[fn;ATOM] → atom[car[x]];
                    eq[fn;EQ] → eq[car[x];cadr[x]];
                    T → apply[eval[fn;a];x;a]];
        eq[car[fn];LAMBDA] → eval[caddr[fn];pairlis[cadr[fn];x;a]];
        eq[car[fn];LABEL] → apply[caddr[fn];x;cons[cons[cadr[fn];
                                                   caddr[fn]];a]]]

 eval[e;a] =
       [atom[e] → cdr[assoc[e;a]];
        atom[car[e]] → [eq[car[e];QUOTE] → cadr[e];
                        eq[car[e];COND] → evcon[cdr[e];a];
                        T → apply[car[e];evlis[cdr[e];a];a]];
        T → apply[car[e];evlis[cdr[e];a];a]]

pairlis and assoc have been previously defined.

 evcon[c;a] = [eval[caar[c];a] → eval[cadar[c];a];
               T → evcon[cdr[c];a]]

and

 evlis[m;a] = [null[m] →  NIL;
               T → cons[eval[car[m];a];evlis[cdr[m];a]]]

From the LISP 1.5 Programmer's Manual

What a mess! Where are the unit tests? Where are the comments? A little bit of whitespace, please! They use "cdar", "caar", and "cadr". They should be using named accessors! What if you eval an atom that's not found in the association list? Did they really name a function "evlis"? Et cetera.

Now, I do think the LISP 1.5 (it wasn't yet spelled "Lisp" then) evaluator is awesome, as it was in McCarthy's first papers on the subject. If you disagree with that, that's cool, I see why one would "hate" my poor imitation.

But given the Lisp history of meta-circular evaluators, one doesn't need to comment every one as if it were the first. In the same way that one recognizes an if statement without the need for a design pattern behind it, I would want anyone who's hacking on Guile's evaluator to have read or perhaps even written several evaluators; and once you've written one, you know the pattern.

More substantively, Charles speculates on source-to-source transformations to ease interpretation. I admit almost total ignorance regarding PreScheme; I've been meaning to learn about it for years now. But the point of this evaluator was to have it use the same representation as VM-compiled procedures; ideally it should run fast, but the first priority is for it to run on the VM itself instead of on a separate stack. There's certainly many more clever things that can be done there, and thankfully since eval is implemented in Scheme and compiled like anything else, it will also reap advantages of an improving compiler.

Regarding Emacs, I hope to say more on that point within a week or so, when the video for my talk at the recent GNU Hackers Meeting gets put up.

Finally, Bubo asks if this work is in a released tarball. Not yet is the answer, but it will be in Tuesday's 1.9.6 release.

Happy hacking!

29 responses

  1. bubo says:

    thanks for the reply! it wasn't in the tarball but already in git. i need quite a bit of libraries on Debian testing to install the stuff in the git repo, so i'll give it a shot on the weekend. otherwise: tuesday == eval/apply-day :)! if this realy works it should give guile quite a boost in performance. if not at least debugging will be more fun in the future. by the way: IMHO scheme48 is one of the best scheme's out there in terms of design, power, features. but it's quite slow. so i don't think that the underlying prescheme (which is AFAIK r4rs) has helped it a lot in terms of program execution speed. however, thanks a lot for making guile *better*! bye

  2. wingo says:

    Thanks for stopping by. Regarding speed of eval however, I am afraid you will be disappointed; consider that the C evaluator that we have, for bootstrapping purposes uses the same algorithm as the Scheme evaluator. So you have the same algorithm implemented in two languages. The faster implementation is the one whose compiler produces the fastest code. Guile's compiler is not as fast as GCC, and probably will never be, though who knows.

    Where we win is by having a uniform semantics, and a uniform debugging interface (once eval.scm is compiled).

    That said, whether the evaluator is in Scheme or C doesn't affect the speed of compiled code, which is the vast majority of code executed by Guile. Even the REPL is really a read-compile-run-print loop, not a read-eval-print loop. But since the semantics are the same, and the compiler is zippy enough for REPL purposes, no one notices.

  3. rotty says:

    @bubo: Regarding PreScheme: IIRC, PreScheme is a Scheme-like language with quite heavy restrictions (e.g. no garbage collection) that can be compiled to C and is used to implement the Scheme48 virtual machine. So it's not really R4RS, or any Scheme (could a language without GC still be called Scheme?).

  4. Thomas says:

    Hi,

    thanks a lot for your great improvements on Guile. I am once again awed by your work ^^
    I just listened to your talk/skimmed through the slides and I must say I'm really excited about the idea of a Guile-based GNU Emacs.

    Keep up the good work!

    Thomas

  5. bubo says:

    @wingo: to be honest - i haven't thought this through entirely. i try to get proficient to hack in guile and c not on guile and c. i'm not god enough for that. i read the guile-devel mail but never post - i'd just hold you back...;)

    @rotty: hmmm. i remember olin shivers saying something like this in the talk, he gave on dan friedman's 60th birthday. i have a paper on prescheme anywhere in an archive, which means i can't find it. without gc it can't be r4rs, that's for sure... however: when is serveez coming back to squeeze, man? i'm really missing my favorite server! :)

  6. John Cowan says:

    If you're not familiar with how the Chicken Scheme bootstrap works, you may be interested. Chicken is primarily meant for creating libraries and stand-alone applications, not as an extension language, so it's not directly comparable to Guile.

    Chicken's compiler generates C code which is then compiled with gcc. There is also some run-time code written in C, and a single assembler routine that obviates the need for libffi in simple cases. The interpreter is a library function written in Chicken and compiled with the Chicken compiler and gcc; there is an application wrapper around it that provides a stand-alone REPL for Chicken.

    So then, how does Chicken compile its compiler? In normal operation, with a pre-existing Chicken compiler, provided it is not too old. If it is too old, or if you have no existing Chicken compiler on the system, you download the C sources of the latest stable Chicken compiler and compile them with gcc.

    The resulting bootstrap compiler is then used to compile the new Chicken compiler, which then compiles itself in order to take advantage of any recent improvements in the compiler. Given that, all the Chicken libraries and utilities can be compiled, and there you are. You can then throw away both binary and source of the bootstrap compiler, as normal updating will employ the compiler you just created.

  7. assignment writing uk says:

    I've been perusing this article about month lastly completed it today. On account of you, I've at least acknowledged, what mathematicians imply by "excellence", when they discuss math.

  8. buy dissertation uk says:

    This is an excellent article...mention on Maxwell's equations of software...this type of work has been happening for years and is offered fromacxcurate knowledge algorithm implemented in two languages. ...we follow the these...it is such a privilege.

  9. download wifikill says:

    awesome Tick mark on the "unidentified sources" in setups of the smart device or tablet. certainly permit you to download the software to your pc great.

  10. cheap Puma shoes says:

    It is great to see this blog. Thank you for sharing this.

  11. cheap christian louboutin says:

    I am really pleased to read this I would like to give special thanks to share

    this article with us

  12. YO YO says:
  13. vShare for iOS says:

    good The highlight is that.It does not permit your apple iphone to be jailbreak or have cydia mounted. You can obtain vshare ios ios 9 totally free and also without any inconvenience nice.

  14. dsadsa says:
  15. iTube Android says:

    good it in history and could carry on numerous functions on the smartphone with no issue.It works really well with the earphone, you can easily miss any song with the click of earphone button nice.

  16. ADIL says:

    River map of United statesRiver map of United statesRiver map of United statesRiver map of United statesPrintable calendar 2017Printable calendar 2017Printable calendar 2017Printable calendar 2017Printable calendar 2017Printable calendar 2017Free Printable calendar 2017

    Free Printable calendar 2017Free Printable calendar 2017Free Printable calendar 2017Free Printable calendar 2017Free Printable calendar 2017Free calendar TemplatesFree calendar Templates

    Free calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree 2017 calendar Templates

    Free 2017 calendar TemplatesFree 2017 calendar TemplatesFree 2017 calendar TemplatesFree 2017 calendar TemplatesFree 2017 calendar Templates

    printable calendars printable calendars printable calendars printable calendar printable black calendars printable black calendars printable black calendars printable indian calendars printable us calendars printable us calendars printable calendars us printable calendars indian printable calendars print us calendars

  17. Bari Bryla says:

    di berbagai ajang perlombaan di tingkat provinsi, nasional, dan internasional. “Prestasi ini tidak hanya menunjukkan kualitas ironsteelcenter.com ironsteelcenter.comHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga besi cnp Harga besi cnpHarga besi unp Harga besi unpHarga wiremesh Harga wiremeshHarga besi wf Harga besi wfHarga besi h beam Harga besi h beamHarga Plat besi Harga Plat besiHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga besi siku Harga besi sikuHarga Plat kapal besi baja bki krakatau steel Harga Plat kapal besi baja bki krakatau steelHarga bondek Harga bondekHarga baja ringan Harga baja ringanHarga Atap spandek Harga atap spandekHarga stainless steel Harga stainless steeljasa konstruksi jasa konstruksi besi baja jasa konstruksi gudang jasa konstruksi gedung jasa konstruksi undangan pernikahan undangan pernikahan simpleundangan pernikahan online udangan pernikahan pinkundangan pernikahan unik undangan pernikahan onlineundangan pernikahan murah undangan pernikahan islamiundangan pernikahan islami undangan pernikahan murahundangan pernikahan elegan undangan pernikahan artisundangan pernikahan unik dan murah contoh undangan pernikahan
    www.gudangbesibaja.com www.gudangbesibaja.comHarga besi cnp Harga besi cnpHarga besi h beam baja Harga besi h beam bajaHarga Plat besi plat kapal Harga Plat besi plat kapalHarga besi siku Harga besi sikuHarga besi unp Harga besi unpHarga besi wf baja Harga besi wf bajaHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga wiremesh Harga wiremeshHarga bondek Harga bondekHarga besi Wf Baja Harga besi Wf Bajajasa konstruksi baja wf jasa konstruksi jembatan jasa konstruksi bangunan jasa konstruksi undangan pernikahan elegan dan murah undangan pernikahan eleganundangan pernikahan simple undangan pernikahan elegan dan murahundangan pernikahan artis undangan pernikahan putihudangan pernikahan pink undangan pernikahan unik dan murahundangan pernikahan putih undangan pernikahan unikContoh undangan pernikahan undangan pernikahan

    harga besi beton sni toko besi baja harga besi bahan bangunanharga pipa stainless steel pipa galvanis medium a besi bjkujual baja wf tabel baja krakatau steel harga besi ulir 16 mmharga stainless steel harga baja profil per kg harga besi 12 sniharga besi ulir harga besi wire mesh harga besi 8 mmdaftar harga pipa galvanis harga besi hollow stainless harga besi beton 10harga besi wf 200 harga baja hollow harga besi 13 ulirbesi kanal c galvanis steel rangka besi betondaftar harga besi beton harga pipa hollow harga besi kgjual wiremesh besi beam sni besi betonsupplier besi profil baja iwf harga besi behel 8mmbesi baja pipa galvanized harga besi beton 10mm snikonstruksi baja wf jual expanded metal harga besi ulir 10daftar harga besi hollow besi wire mesh harga sikuharga wiremesh profil baja h beam harga besi siku 4x4Supplier besi harga beam 200 besi siku hargaharga besi baja harga besi cnp 100 harga pipa besi hitamharga pipa baja jual besi cnp pipa seamlessbesi beton murah harga besi unp 100 daftar harga pipa stainless steelharga kanal c besi kanal c harga harga pipaharga besi stainless harga besi cnp 125 pipa stainlessharga besi per kg besi u galvanisharga plat stainless steel besi c pipa besi galvanisbesi unp harga besi cnp 150 harga besi hollow untuk pagarjual besi wf kanal c pipa besi hitamharga baja h beam daftar harga besi kanal c harga besi hollow 40x40

  18. mobdro app says:

    good the most recent movies using one single application. You can see any type of tv show, anytime as well as can eliminate time with easer. Passing time was never ever so easy as well as nice.

  19. tutuapp apk says:

    good We Ended up the presettings.I understand you are egerly waiting to mount the application on your smartphone.so lets go straight to the setup of Tutu application for android nice.

  20. james clark says:

    Valentine's Day, also called Saint Valentine's Day or the Feast of Saint Valentine, valentines day is an annual holiday celebrated on February 14. valentines day messages It originated as a Western Christian liturgical feast day honoring one or more early saints named Valentinus, and is recognized as a significant cultural and commercial celebration in many regions around the world, happy valentines day quotes although it is not a public holiday in any country. Valentine's Day is celebrated on February 14 Valentine's Day is also a very popular date for weddings..It is a festival of romantic love and many people give cards, letters, flowers or presents to their spouse or partner. They may also arrange a romantic meal in a restaurant or night in a hotel. Common symbols of Valentine's Day are hearts, red roses and Cupid.The most common happy valentines day images Valentine's Day symbols are the heart, particularly in reds and pinks, and pictures or models of Cupid. Cupid is usually portrayed as a small winged figure with a bow and arrow.Many people celebrate their love for their partner by sending cards or letters, giving gifts or flowers and arranging meals in restaurants or romantic nights in hotels. People who would like to have a romantic relationship with somebody may use the occasion to make this known, often anonymously. Valentine's cards are often decorated with images of hearts, red roses or Cupid. Common Valentine's Day gifts are flowers chocolates, candy, lingerie and champagne or sparkling wine

  21. nikky says:

    check your mah hsc results 2017 at official website.

  22. nikky says:

    Maharashtra board will publish the ssc result 2017 soon.

  23. nikky says:

    Students are eagerly waiting for their mah results 2017.

  24. cbse 10th results 2017 says:

    great education stuff students can check cbse 10th result 2017 here

  25. roja says:
  26. john says:
  27. happy valentines day says:
  28. nikky says:

    Click here to get karnataka sslc result 2017.

  29. nikky says:

    Students can check TN HSC Result at official website.

Leave a Reply