GNU Guile Scheme Gets a Register VM and CPS-Based IL

← Back to Stories (view on slashdot.org)

GNU Guile Scheme Gets a Register VM and CPS-Based IL

Posted by Unknown on Wednesday January 15, 2014 @08:02AM from the lisp-hacker-does-weird-thing-for-fun dept.

In late November, Andy Wingo pushed a new register VM to Guile's (the GNU implementation of the Scheme language) master branch. It brought a number of performance improvements, but led to a bit of a conceptual mismatch between the compiler's direct-style intermediate language and the virtual machine. Earlier this week Andy Wingo announced a new continuation-passing style intermediate language for Guile. From the article: "To recap, we switched from a stack machine to a register machine because, among other reasons, register machines can consume and produce named intermediate results in fewer instructions than stack machines, and that makes things faster. To take full advantage of this new capability, it is appropriate to switch at the same time from the direct-style intermediate language (IL) that we had to an IL that names all intermediate values. ... In Guile I chose a continuation-passing style language. ... Guile's CPS language is composed of terms, expressions, and continuations. It was heavily inspired by Andrew Kennedy's 'Compiling with Continuations, Continued' paper. ... The optimizations I have currently implemented for CPS are fairly basic. Contification was tricky. One thing I did recently was to make all non-tail $call nodes require $kreceive continuations; if, as in the common case, extra values were unused, that was reflected in an unused rest argument. This required a number of optimizations to clean up and remove the extra rest arguments for other kinds of source expressions: dead-code elimination, the typical beta/eta reduction, and some code generation changes." The article describes the CPS language provided by Guile and explains the reasons behind choosing CPS over SSA or A-Normal Form. The Guile manual contains draft documentation. The new VM and Intermediate Language will be released with Guile 2.2, which should be out later this year.

42 comments

Min score:

Reason:

Sort:

frost pist with a wager by inode_buddha · 2014-01-15 08:05 · Score: 0, Troll

I'll wager this article garners less than 100 comments. Also, WTF is all this "guile" about?

--
C|N>K
1. Re:frost pist with a wager by Chris+Mattern · 2014-01-15 08:09 · Score: 1, Troll
  
  Also, WTF is all this "guile" about?
  Sonic BOOM!
2. Re:frost pist with a wager by iluvcapra · 2014-01-15 08:16 · Score: 5, Insightful
  
  Remember when a nerd was someone who cared about tail call optimizations and SSA, and not which corporation made their cellphone?
  Off my lawn.
  
  --
  Don't blame me, I voted for Baltar.
3. Re: frost pist with a wager by Anonymous Coward · 2014-01-15 08:19 · Score: 0
  
  Guile's Scheme goes with âeverythingâ
  Baa ba da badaaa
  Baa ba da badaaa
4. Re:frost pist with a wager by freefal67 · 2014-01-15 08:20 · Score: 2
  
  This. "I'm kind of a nerd. I'm really into technology. I've got a ton of high-end Apple products"
5. Re:frost pist with a wager by Em+Adespoton · 2014-01-15 08:42 · Score: 1
  
  So? I fit that, and still consider this "stuff that matters". I was wondering why they thought their register VM was applicable to a scheme variant, and I had started to cross Guile off my list of relevant Scheme implementations. I'll be waiting until I see what actually gets documented before I weigh in further though.
  Then again, I've been interested in Apple products since the 70's, so get off my lawn :D
6. Re:frost pist with a wager by Guy+Harris · 2014-01-15 09:11 · Score: 1
  
  I was wondering why they thought their register VM was applicable to a scheme variant
  Why would it not be relevant?
7. Re:frost pist with a wager by Darinbob · 2014-01-15 10:36 · Score: 1
  
  This is awesome. Where else other than slashdot can we discuss continuation passing as a compilation method with peers who understand what we're talking about?
8. Re:frost pist with a wager by Darinbob · 2014-01-15 11:00 · Score: 1
  
  Because they already had a stack machine variant. And stack machines tend to have a lot of activity on the top of the stack, and in some lisp implementations that can result in a lot of garbage collection. Even without garbage being created it's a lot of extra churning, with more stack manipulation instructions being generated by the compiler. Note that a lot of Forth machines and implementations implement a top-of-stack register for efficiency.
9. Re:frost pist with a wager by Anonymous Coward · 2014-01-15 11:46 · Score: 2, Informative
  
  Usenet?
  lambda-the-ultimate.org?
  Slashdot has been overrun by tech consumers.
10. Re:frost pist with a wager by ChunderDownunder · 2014-01-15 12:29 · Score: 1
  
  one of the most widely deployed vms on the planet is register based - dalvik. consequently, such an architecture may be back in vogue.
11. Re:frost pist with a wager by Anonymous Coward · 2014-01-15 13:41 · Score: 3, Interesting
  
  Register VMs began to come back into vogue at least since the Dis VM in Plan 9. The Bell Labs developers wrote a paper about Dis which effectively stated that, "yo, yo, register VMs are faster out-of-the-box, easier to optimize, and easier to translate to native code".
  By the time Dalvik came along (10 years after the Dis paper) it was already conventional wisdom that register-based VMs were the obvious choice for performance. But most projects still use stack-based VMs because they're easier to implement and easier to generate code for.
  Lua 5.0 (of almost 10 years ago) was register-based and the developers wrote a paper about it: http://www.lua.org/doc/jucs05.pdf
  Note that Lua (not just LuaJIT) blows the pants off of Python and Ruby in terms of performance, and it's largely because of their efficient VM. Lua has full lexical closures, coroutines, GC, tail calls, extensible metatypes, etc, yet it's ridiculously fast for a purely interpreted language.
  Here's the Plan 9 Dis paper: http://doc.cat-v.org/inferno/4th_edition/dis_VM_design
12. Re:frost pist with a wager by Anonymous Coward · 2014-01-15 13:45 · Score: 0
  
  lambda-the-ultimate?
Parroting parrot? by Anonymous Coward · 2014-01-15 08:15 · Score: 0

Is GNU parroting the parrot VM?
1. Re:Parroting parrot? by hummassa · 2014-01-15 08:34 · Score: 1
  
  AFAICR parrot is SSA, no?
  
  --
  It's better to be the foot on the boot than the face on the pavement. ~~ tkx Kadin2048
2. Re:Parroting parrot? by DuckDodgers · 2014-01-15 15:38 · Score: 1
  
  Parrot is register-based, you can get that from the main website or the wikipedia article. Does that automatically mean it's also CPS, or can register-based still be SSA?
  
  I don't understand CPS or SSA and register-based vs. stack-based well enough to know the answer.
3. Re:Parroting parrot? by cheesybagel · 2014-01-16 05:12 · Score: 1
  
  SSA can use registers. In fact it usually does use registers.
4. Re:Parroting parrot? by DuckDodgers · 2014-01-17 04:16 · Score: 1
  
  Thanks. Again, I didn't know.
Scheme-Great way to learn function programming by freefal67 · 2014-01-15 08:17 · Score: 2

Never done anything substantial in Scheme, but was probably my favorite language to learn in college, in the context of a function programming course. I did not know there as a GNU interpreter. Will have to check it out. Speaking of functional languages, someone told me that the XKCD website is programmed entirely in Haskell. True?
1. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 08:27 · Score: 0
  
  'Many parts' are done in Haskell, apparently: http://forums.xkcd.com/viewtopic.php?f=7&t=107544&sid=75038535f4c8cbb47e602acbe40ef3e7#p3519138
2. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 08:34 · Score: 0
  
  I think it's the worst way. Source code looks like oatmeal with nail clippings mixed in, and probably tastes the part.
  A good way of learning functional programming is with an ML language like SML, or OCaml, or a hybrid like Scala. Anything that has parentheses-matching as a requirement is simply self-flagellation.
3. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 08:34 · Score: 0
  
  it will remain your favorite language as long as you don't try to do anything substantial with it
4. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 08:39 · Score: 2, Informative
  
  www.lilypond.org
  Thanks
5. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 08:39 · Score: 0
  
  Guile's real strength is that you can shove it into pretty much any other language. I use it in a project primarily written in C, and it easily lets users add real customization without having to recompile anything.
6. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 09:39 · Score: 0
  
  thanks for your session id
7. Re:Scheme-Great way to learn function programming by bzipitidoo · 2014-01-15 09:41 · Score: 1
  
  Anything that has parentheses-matching as a requirement is simply self-flagellation.
  That's what the backronym says: Lots of Idiotic Single Parentheses.
  Hierarchic thinking has infested Computer Science for decades. The entire Object Oriented Programming paradigm was founded on hierarchy, with Inheritance defined as from one parent only, and many not too sure if multiple inheritance is a good idea or needed. That the notion of inheritance even has to be qualified with that word "multiple", because it implicitly means single otherwise, is a barrier to thought. Trees are useful data structures, but they aren't the ultimate, universal data structure that can succinctly describe all other organizations of data.
  
  --
  Intellectual Property is a monopolistic, selfish, and defective concept. It is "tyranny over the mind of man"
8. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 09:53 · Score: 0
  
  Don't most people use Lua for that nowadays?
9. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 10:26 · Score: 0
  
  Not to mention Python or TCL.
10. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 10:38 · Score: 0
  
  Perhaps. I guess it was mostly my personal bias in choosing Guile, since I knew Scheme and didn't know Lua.
11. Re:Scheme-Great way to learn function programming by Darinbob · 2014-01-15 10:43 · Score: 1
  
  True, you can do DAGs in trees, which encompasses most of the hard stuff in theory. But with Lisp you can have the cycles too, so it really does implement a universal data structure.
12. Re:Scheme-Great way to learn function programming by dkf · 2014-01-15 11:06 · Score: 4, Insightful
  
  Hierarchic thinking has infested Computer Science for decades. The entire Object Oriented Programming paradigm was founded on hierarchy, with Inheritance defined as from one parent only, and many not too sure if multiple inheritance is a good idea or needed. That the notion of inheritance even has to be qualified with that word "multiple", because it implicitly means single otherwise, is a barrier to thought. Trees are useful data structures, but they aren't the ultimate, universal data structure that can succinctly describe all other organizations of data.
  There's a lot of foolish programmers who think that because they've got inheritance available to them, they've got to use it. It's the If All You Have Is A Hammer principle. Delegation/composition is much more useful in practice (and can express arbitrary graphs just fine).
  
  --
  "Little does he know, but there is no 'I' in 'Idiot'!"
13. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-15 12:31 · Score: 0
  
  Python doesn't work well as an embedded scripting language. It can be done, of course, but Lua is infinitely nicer in that context.
  Python's API is skewed toward C modules, not C embedding. It's a big difference from an application perspective.
  Tcl is decent either way, but Lua's API is just beautiful for mixing with C code, either for embedded or module work. I mean, that's what Lua was designed for, from the bottom up--as an extension language for C. Everything from the VM to the API is focused on this niche.
14. Re:Scheme-Great way to learn function programming by Anonymous Coward · 2014-01-16 03:02 · Score: 0
  
  Not really, your IDE/editor should match it for you. You should be using whitespace to communicate structure to other programers and yourself the second time you read it.
This stuff is starting to matter. by elfsternberg8092 · 2014-01-15 08:32 · Score: 3, Interesting

The frightening thing is, a year ago, I wouldn't have understood this post. Now I'm reading the paper on Contifications and nodding my head, going "Yeah, yeah... huh... uh... yeah, okay..." It's been that kind of year. This is the kind of stuff that's starting to show up on webdevs' radars. With the release of ECMA-6 and the precompiler suites, the essential core scheme-ness of even Javascript is starting to infect us all.
Parentheses matching not required by dwheeler · 2014-01-15 12:03 · Score: 3, Informative

GNU guile's built-in reader includes support for SRFI-105, so you can use infix expressions directly. In particular, you can use {...} instead of (...) and put the operator in the EVEN position, e.g., {n https://www.gnu.org/software/guile/manual/html_node/SRFI_002d105.html
If you want to eliminate more of the parens, you can use guile with SRFI-110, which provides support for indentation-sensitive semantics. An implementation is available with an MIT license. See more here: http://readable.sourceforge.net/

--
- David A. Wheeler (see my Secure Programming HOWTO)
1. Re:Parentheses matching not required by Anonymous Coward · 2014-01-16 02:36 · Score: 0
  
  I like it, but it's a couple decades too late...
Slashdot in Greek by macraig · 2014-01-15 12:42 · Score: 1, Funny

I don't think I have ever encountered a title at Slashdot more meaningless to me than this one. There might be a lesson in that, and I don't think the lesson is for me.
1. Re:Slashdot in Greek by ari_j · 2014-01-15 13:40 · Score: 3, Insightful
  
  To those interested in the implementation of programming languages, it is immediately apparent that this is a fundamental change in the compiler behind the GNU Guile system which implements the Scheme programming language, inasmuch as it now has a virtual machine based on the register model instead of the implied stack model, along with an intermediate language in its compilation path that is based on continuation-passing style.
  I think that the lesson here is for everyone: There are many segments of nerd culture, and it is very unlikely that any randomly-selected Slashdot reader understands and appreciates all of those segments. For example, the earlier headline today "Why Transivity Violations Can Be Rational" has no meaning to many readers, even after the title was corrected to spell transitivity correctly. After reading a little about that topic, I see that it is an area of of obvious interest to many nerds.
  That being said, there are plenty of topics Slashdot poorly reports on which are not of interest to any segment of nerd culture, at least not beyond the overlap between nerd culture and the mainstream news where we already read the same information three days earlier except through the words of a literate, competent reporter with real editing before it hit the press.
2. Re:Slashdot in Greek by complete+loony · 2014-01-15 13:56 · Score: 1
  
  It's about defining an intermediate syntax for the compiler to use, so that optimisations can be performed efficiently. As TFA suggests, if you need an overview on the differences & similarities of SSA and CPS, you could read his earlier article.
  I've experimented a little with LLVM's SSA form for compiling and optimising high level procedural languages. And I think he makes a few quite valid criticisms of the way SSA form is defined and used.
  
  --
  09F91102 no, 455FE104 nope, F190A1E8 uh-uh, 7A5F8A09 that's not it, C87294CE no. Ah! 452F6E403CDF10714E41DFAA257D313F.
3. Re:Slashdot in Greek by Anonymous Coward · 2014-01-15 14:17 · Score: 0
  
  "News for nerds..."
Great language that no one uses.. by guacamole · 2014-01-15 18:54 · Score: 2

The Guile team is doing amazing work. Starting with version 2, Scheme is no longer something that always runs slow. My simple test code run several times faster in Guile 2 compared to similar code in python 3. The problem is that no one seems to be interested. It's quite sad. Guile is simply a fantastic, fairly complete programming environment with a very fast VM. In the early days of Gnome, GNU elevated Scheme to the number 1 status among the Gnome languages, but it was dropped since then. I don't know whether this is from the perception of LISP as the old-school language or the rejection of the code aesthetics due to meticulous use of parenthesis.
Lesson by Anonymous Coward · 2014-01-15 19:13 · Score: 0

> I don't think the lesson is for me
You gotta decide whether the lesson is for you or not.
The outcome of one of the choices will be that you've learnt something, the outcome of the other, that you won't.
Guess which is which.
BTW: Kudos, Andy! I bow in awe.