What papers and strategies underly Gambit's design, in particular the compiler & VM?
Hi,
In the purpose of making it clear and easy-enough for the unintroduced to understand the inner workings of Gambit in its current version, it'd be great to know what strategies/philosophies, papers and other reference documents underly Gambit - its compiler, environment and so on, beyond the Scheme (R5RS etc.) and SRFI specs.
I'd be happy to make a Wiki page, Theory and papers, or alike, of this.
My best understanding is that compilation to C/asm of Scheme with callcc support generally is perceived as a process that's intricate and of an abstract nature, asking this quite a lot therefore. :-)
The papers I'm aware of are basically those on Marc's homepage and those listed by Alex below. And, beyond knowing which they are, it'd be great to have a clue of how central the respective paper is in Gambit's particular design / how strictly it was adhered to, on the scale from directly/being implemented as it is to indirectly/used rather for inspiration.
Things whose answers can be found in the papers would include: * How the internal value, object, procedure and closure representations look and fit together Closures effectively special-purpose vectors of boxes? All values and object references are internally native-size integers with a number of reserved bytes describing the value type, what about them? * Value and object allocations, made how and what optimizations for fast dead object detection and subsequent reclaim are there * The layout of the asm/C-level stack and trampolines and how the GC resolves the locations of all object reference, anatomy of a procedure call and return * How the CPS transformation works * What optimizations are made, in terms of register use optimizations, compile-time pre-evaluation or deductions of datatype At some point I got that generally |cdr| is translated to +1 in asm/c, for instance * What does the internal form of interpreted code actually look/work like * Interrupt checks, made provenly at what granularity * Code debuggability, made in compiled code on what basis * Motivations for the GVM code's design * Hashtable algorithm * Number handling
I suppose there's key areas beyond these also. And, I suppose quite possibly, some key things are not described in any paper.
Find below an attempt to figure out which of Marc's papers are in use for these respects of Gambit today.
If you know such papers/docs or you see areas beyond those listed above that ought to be considered as in the scope too, please tell.
Kind regards, Mikael
* Marc Feeley. *Speculative inlining of predefined procedures in an R5RS Scheme to C compiler. *In Olaf Chitil, Zoltán Horváth, and Viktória Zsók, editors, *Implementation and Application of Functional Languages (IFL'07)*, volume 5083 of *Lecture Notes in Computer Science*, pages 237-253, 2008. [PDF] http://www.iro.umontreal.ca/~feeley/papers/FeeleyIFL07.pdf * Fernanda Kri and Marc Feeley. *Genetic instruction scheduling and register allocation. *In *International Conference on the Quantitative Evaluation of Systems (QEST'04)*, pages 76-83, 2004. [PDF]http://www.iro.umontreal.ca/~feeley/papers/KriFeeleyQEST04.pdf * Marc Feeley. *A better API for first-class continuations. *In *Scheme and Functional Programming Workshop (SFPW'01)*, pages 1-3, September 2001. [PDF] http://www.iro.umontreal.ca/~feeley/papers/FeeleySW01.pdf * Danny Dubé and Marc Feeley. *Demand-driven type analysis: an introduction. *In *Scheme and Functional Programming Workshop (SFPW'01)*, pages 21-32, September 2001. [PDF]http://www.iro.umontreal.ca/~feeley/papers/DubeFeeleySW01.pdf * Marc Feeley. *A portable implementation of first-class continuations for unrestricted interoperability with C in a multithreaded Scheme. *In *Scheme and Functional Programming Workshop (SFPW'00)*, pages 65-66, September 2000. [PDF] http://www.iro.umontreal.ca/~feeley/papers/FeeleySW00.pdf * Mauricio Solar and Marc Feeley. *Scheduling algorithm considering latency time on a shared-memory machine. *In *XVI World Computer Congress, International Conference on Software: Theory and Practice*, August 2000. * Marc Feeley, James S. Miller, Guillermo J. Rozas, and Jason A. Wilson. *Compiling higher-order languages into fully tail-recursive portable C. *Technical Report 1078, département d'informatique et r.o., Université de Montréal, August 1997. [PDF]http://www.iro.umontreal.ca/~feeley/papers/FeeleyMillerRozasWilsonDIRO1078.pdf * Dominique Boucher and Marc Feeley. *Abstract compilation: a new implementation paradigm for static analysis. *In *International Conference on Compiler Construction (CC'96)*, pages 192-207, April 1996.[PDF]http://www.iro.umontreal.ca/~feeley/papers/BoucherFeeleyCC96.pdf * Manuel Serrano and Marc Feeley. *Storage use analysis and its applications. *In *ACM SIGPLAN International Conference on Functional Programming (ICFP'96)*, pages 50-61, May 1996. [PDF]http://www.iro.umontreal.ca/~feeley/papers/SerranoFeeleyICFP96.pdf * Marc Feeley. *Polling efficiently on stock hardware. *In *ACM Conference on Functional Programming Languages and Computer Architecture (FPCA'93)*, pages 179-187, 1993. [PDF]http://www.iro.umontreal.ca/~feeley/papers/FeeleyFPCA93.pdf * Marc Feeley and Guy Lapalme. *Closure generation based on viewing LAMBDA as EPSILON plus COMPILE. **Computer Languages*, 17(4):251-267, 1992. [PDF]http://www.iro.umontreal.ca/~feeley/papers/FeeleyLapalmeCL92.pdf Marc Feeley and Guy Lapalme. *Using closures for code generation. **Computer Languages*, 12(1):47-66, 1987. [PDF]http://www.iro.umontreal.ca/~feeley/papers/FeeleyLapalmeCL87.pdf * Marc Feeley. *Deux approches à l'implantation du language Scheme. *Master's thesis, Université de Montréal, May 1986. [PDF]http://www.iro.umontreal.ca/~feeley/papers/FeeleyMSc.pdf
2011/6/9 Alex Queiroz
Hallo,
On Wed, Jun 8, 2011 at 11:14 PM, Jason E. Aten j.e.aten@gmail.com wrote:
If others on the list have pointers to papers as well, I'd enjoy reading about the best thoughts on how to implement continuations.
"Representing Control in the Presence of First-Class Continuations" http://www.cs.indiana.edu/~dyb/papers/stack.ps
"A portable implementation of first-class continuations for unrestricted interoperability with C in a multithreaded Scheme" http://repository.readscheme.org/ftp/papers/sw2000/feeley.pdf
"Implementation strategies for first-class continuations" http://www.springerlink.com/content/h5808n962434j275/fulltext.pdf
More in: http://library.readscheme.org/page6.html
Cheers,
-alex
Afficher les réponses par date
Mikael. Sorry for the long silence... I've been rather busy lately.
As you might expect documenting all of the inner workings of Gambit is a major endeavor. You will find in my publications some of the most important design strategies that were used while building Gambit. I know that it doesn't cover all aspects, and some important things are yet to be published.
Currently I don't have time for an open-ended documentation effort. However, I am willing to invest a few hours a week to explain the design strategies that users care to know about.
So how about this... someone should create a wiki page with an ordered wish list of specific things to document. Every week I will pick the next thing off of the list and reply to the ML.
By the way, in the list of publications you forgot to put my PhD which documents the implementation of futures (http://www.iro.umontreal.ca/~feeley/papers/FeeleyPhD.pdf).
Marc
On 2012-05-27, at 10:13 AM, Mikael wrote:
Hi,
In the purpose of making it clear and easy-enough for the unintroduced to understand the inner workings of Gambit in its current version, it'd be great to know what strategies/philosophies, papers and other reference documents underly Gambit - its compiler, environment and so on, beyond the Scheme (R5RS etc.) and SRFI specs.
I'd be happy to make a Wiki page, Theory and papers, or alike, of this.
My best understanding is that compilation to C/asm of Scheme with callcc support generally is perceived as a process that's intricate and of an abstract nature, asking this quite a lot therefore. :-)
The papers I'm aware of are basically those on Marc's homepage and those listed by Alex below. And, beyond knowing which they are, it'd be great to have a clue of how central the respective paper is in Gambit's particular design / how strictly it was adhered to, on the scale from directly/being implemented as it is to indirectly/used rather for inspiration.
Things whose answers can be found in the papers would include:
- How the internal value, object, procedure and closure representations look and fit together Closures effectively special-purpose vectors of boxes? All values and object references are internally native-size integers with a number of reserved bytes describing the value type, what about them?
- Value and object allocations, made how and what optimizations for fast dead object detection and subsequent reclaim are there
- The layout of the asm/C-level stack and trampolines and how the GC resolves the locations of all object reference, anatomy of a procedure call and return
- How the CPS transformation works
- What optimizations are made, in terms of register use optimizations, compile-time pre-evaluation or deductions of datatype At some point I got that generally |cdr| is translated to +1 in asm/c, for instance
- What does the internal form of interpreted code actually look/work like
- Interrupt checks, made provenly at what granularity
- Code debuggability, made in compiled code on what basis
- Motivations for the GVM code's design
- Hashtable algorithm
- Number handling
I suppose there's key areas beyond these also. And, I suppose quite possibly, some key things are not described in any paper.
Find below an attempt to figure out which of Marc's papers are in use for these respects of Gambit today.
If you know such papers/docs or you see areas beyond those listed above that ought to be considered as in the scope too, please tell.
Kind regards, Mikael
- Marc Feeley. Speculative inlining of predefined procedures in an R5RS Scheme to C compiler. In Olaf Chitil, Zoltán Horváth, and Viktória Zsók, editors, Implementation and Application of Functional Languages (IFL'07), volume 5083 of Lecture Notes in Computer Science, pages 237-253, 2008. [PDF]
- Fernanda Kri and Marc Feeley. Genetic instruction scheduling and register allocation. In International Conference on the Quantitative Evaluation of Systems (QEST'04), pages 76-83, 2004. [PDF]
- Marc Feeley. A better API for first-class continuations. In Scheme and Functional Programming Workshop (SFPW'01), pages 1-3, September 2001. [PDF]
- Danny Dubé and Marc Feeley. Demand-driven type analysis: an introduction. In Scheme and Functional Programming Workshop (SFPW'01), pages 21-32, September 2001. [PDF]
- Marc Feeley. A portable implementation of first-class continuations for unrestricted interoperability with C in a multithreaded Scheme. In Scheme and Functional Programming Workshop (SFPW'00), pages 65-66, September 2000. [PDF]
- Mauricio Solar and Marc Feeley. Scheduling algorithm considering latency time on a shared-memory machine. In XVI World Computer Congress, International Conference on Software: Theory and Practice, August 2000.
- Marc Feeley, James S. Miller, Guillermo J. Rozas, and Jason A. Wilson. Compiling higher-order languages into fully tail-recursive portable C. Technical Report 1078, département d'informatique et r.o., Université de Montréal, August 1997. [PDF]
- Dominique Boucher and Marc Feeley. Abstract compilation: a new implementation paradigm for static analysis. In International Conference on Compiler Construction (CC'96), pages 192-207, April 1996.[PDF]
- Manuel Serrano and Marc Feeley. Storage use analysis and its applications. In ACM SIGPLAN International Conference on Functional Programming (ICFP'96), pages 50-61, May 1996. [PDF]
- Marc Feeley. Polling efficiently on stock hardware. In ACM Conference on Functional Programming Languages and Computer Architecture (FPCA'93), pages 179-187, 1993. [PDF]
- Marc Feeley and Guy Lapalme. Closure generation based on viewing LAMBDA as EPSILON plus COMPILE. Computer Languages, 17(4):251-267, 1992. [PDF]
Marc Feeley and Guy Lapalme. Using closures for code generation. Computer Languages, 12(1):47-66, 1987. [PDF]
- Marc Feeley. Deux approches à l'implantation du language Scheme. Master's thesis, Université de Montréal, May 1986. [PDF]
2011/6/9 Alex Queiroz Hallo,
On Wed, Jun 8, 2011 at 11:14 PM, Jason E. Aten j.e.aten@gmail.com wrote:
If others on the list have pointers to papers as well, I'd enjoy reading about the best thoughts on how to implement continuations.
"Representing Control in the Presence of First-Class Continuations" http://www.cs.indiana.edu/~dyb/papers/stack.ps
"A portable implementation of first-class continuations for unrestricted interoperability with C in a multithreaded Scheme" http://repository.readscheme.org/ftp/papers/sw2000/feeley.pdf
"Implementation strategies for first-class continuations" http://www.springerlink.com/content/h5808n962434j275/fulltext.pdf
More in: http://library.readscheme.org/page6.html
Cheers,
-alex
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
(dear ml, please see the question to you highlighted in green below)
2012/6/8 Marc Feeley feeley@iro.umontreal.ca
Mikael. Sorry for the long silence... I've been rather busy lately.
As you might expect documenting all of the inner workings of Gambit is a major endeavor. You will find in my publications some of the most important design strategies that were used while building Gambit. I know that it doesn't cover all aspects, and some important things are yet to be published.
Currently I don't have time for an open-ended documentation effort. However, I am willing to invest a few hours a week to explain the design strategies that users care to know about.
So how about this... someone should create a wiki page with an ordered wish list of specific things to document. Every week I will pick the next thing off of the list and reply to the ML.
Cool, great!
The way you propose sounds like it makes a lot of sense.
I intend to put something like this together soon. If others would make sth like this I suppose just kind of merging the two would be fine.
Anyone please feel free to suggest questions or angles on subjects that should be addressed in this document, so that these will be covered too.
So basically, what about Gambit have you always wanted to get a good understanding of (and which is not quite obvious from looking at Gambit's sourcecode), and what are the questions that would take you to getting this understanding?
By the way, in the list of publications you forgot to put my PhD which
documents the implementation of futures ( http://www.iro.umontreal.ca/~feeley/papers/FeeleyPhD.pdf).
Ah right, current Gambit has a the |future| form so it's clearly in the current version indeed.
Marc
Brgds, Mikael
On 2012-05-27, at 10:13 AM, Mikael wrote:
Hi,
In the purpose of making it clear and easy-enough for the unintroduced
to understand the inner workings of Gambit in its current version, it'd be great to know what strategies/philosophies, papers and other reference documents underly Gambit - its compiler, environment and so on, beyond the Scheme (R5RS etc.) and SRFI specs.
I'd be happy to make a Wiki page, Theory and papers, or alike, of this.
My best understanding is that compilation to C/asm of Scheme with callcc
support generally is perceived as a process that's intricate and of an abstract nature, asking this quite a lot therefore. :-)
The papers I'm aware of are basically those on Marc's homepage and those
listed by Alex below. And, beyond knowing which they are, it'd be great to have a clue of how central the respective paper is in Gambit's particular design / how strictly it was adhered to, on the scale from directly/being implemented as it is to indirectly/used rather for inspiration.
Things whose answers can be found in the papers would include:
- How the internal value, object, procedure and closure representations
look and fit together
Closures effectively special-purpose vectors of boxes? All values and object references are internally native-size integers
with a number of reserved bytes describing the value type, what about them?
- Value and object allocations, made how and what optimizations for
fast dead object detection and subsequent reclaim are there
- The layout of the asm/C-level stack and trampolines and how the GC
resolves the locations of all object reference, anatomy of a procedure call and return
- How the CPS transformation works
- What optimizations are made, in terms of register use optimizations,
compile-time pre-evaluation or deductions of datatype
At some point I got that generally |cdr| is translated to +1 in
asm/c, for instance
- What does the internal form of interpreted code actually look/work
like
- Interrupt checks, made provenly at what granularity
- Code debuggability, made in compiled code on what basis
- Motivations for the GVM code's design
- Hashtable algorithm
- Number handling
I suppose there's key areas beyond these also. And, I suppose quite
possibly, some key things are not described in any paper.
Find below an attempt to figure out which of Marc's papers are in use
for these respects of Gambit today.
If you know such papers/docs or you see areas beyond those listed above
that ought to be considered as in the scope too, please tell.
Kind regards, Mikael
- Marc Feeley. Speculative inlining of predefined procedures in an R5RS
Scheme to C compiler. In Olaf Chitil, Zoltán Horváth, and Viktória Zsók, editors, Implementation and Application of Functional Languages (IFL'07), volume 5083 of Lecture Notes in Computer Science, pages 237-253, 2008. [PDF]
- Fernanda Kri and Marc Feeley. Genetic instruction scheduling and
register allocation. In International Conference on the Quantitative Evaluation of Systems (QEST'04), pages 76-83, 2004. [PDF]
- Marc Feeley. A better API for first-class continuations. In Scheme
and Functional Programming Workshop (SFPW'01), pages 1-3, September 2001. [PDF]
- Danny Dubé and Marc Feeley. Demand-driven type analysis: an
introduction. In Scheme and Functional Programming Workshop (SFPW'01), pages 21-32, September 2001. [PDF]
- Marc Feeley. A portable implementation of first-class continuations
for unrestricted interoperability with C in a multithreaded Scheme. In Scheme and Functional Programming Workshop (SFPW'00), pages 65-66, September 2000. [PDF]
- Mauricio Solar and Marc Feeley. Scheduling algorithm considering
latency time on a shared-memory machine. In XVI World Computer Congress, International Conference on Software: Theory and Practice, August 2000.
- Marc Feeley, James S. Miller, Guillermo J. Rozas, and Jason A.
Wilson. Compiling higher-order languages into fully tail-recursive portable C. Technical Report 1078, département d'informatique et r.o., Université de Montréal, August 1997. [PDF]
- Dominique Boucher and Marc Feeley. Abstract compilation: a new
implementation paradigm for static analysis. In International Conference on Compiler Construction (CC'96), pages 192-207, April 1996.[PDF]
- Manuel Serrano and Marc Feeley. Storage use analysis and its
applications. In ACM SIGPLAN International Conference on Functional Programming (ICFP'96), pages 50-61, May 1996. [PDF]
- Marc Feeley. Polling efficiently on stock hardware. In ACM Conference
on Functional Programming Languages and Computer Architecture (FPCA'93), pages 179-187, 1993. [PDF]
- Marc Feeley and Guy Lapalme. Closure generation based on viewing
LAMBDA as EPSILON plus COMPILE. Computer Languages, 17(4):251-267, 1992. [PDF]
Marc Feeley and Guy Lapalme. Using closures for code generation.
Computer Languages, 12(1):47-66, 1987. [PDF]
- Marc Feeley. Deux approches à l'implantation du language Scheme.
Master's thesis, Université de Montréal, May 1986. [PDF]
2011/6/9 Alex Queiroz Hallo,
On Wed, Jun 8, 2011 at 11:14 PM, Jason E. Aten j.e.aten@gmail.com
wrote:
If others on the list have pointers to papers as well, I'd enjoy
reading
about the best thoughts on how to implement continuations.
"Representing Control in the Presence of First-Class Continuations" http://www.cs.indiana.edu/~dyb/papers/stack.ps
"A portable implementation of first-class continuations for unrestricted interoperability with C in a multithreaded Scheme" http://repository.readscheme.org/ftp/papers/sw2000/feeley.pdf
"Implementation strategies for first-class continuations" http://www.springerlink.com/content/h5808n962434j275/fulltext.pdf
More in: http://library.readscheme.org/page6.html
Cheers,
-alex
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Hallo,
On Fri, Jun 8, 2012 at 11:44 PM, Mikael mikael.rcv@gmail.com wrote:
Anyone please feel free to suggest questions or angles on subjects that should be addressed in this document, so that these will be covered too.
- How the partial evaluator works
- How the partial evaluator works
Seconded! I would love to hear about this also. -Patrick
On Wed, Jun 13, 2012 at 2:00 PM, Alex Queiroz asandroq@gmail.com wrote:
Hallo,
On Fri, Jun 8, 2012 at 11:44 PM, Mikael mikael.rcv@gmail.com wrote:
Anyone please feel free to suggest questions or angles on subjects that should be addressed in this document, so that these will be covered too.
- How the partial evaluator works
-- -alex http://www.artisancoder.com/ _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Am putting together a tree of questions for this currently.
As for how the partial evaluator works, it would be great if you could please think of and tell here, how you would formulate one or more questions (in the same format as you would typically express them in a personal conversation), that together would communicate this understanding to you [of how the partial evaluator works].
Brgds
2012/6/14 Patrick Li patrickli.2001@gmail.com
- How the partial evaluator works
Seconded! I would love to hear about this also. -Patrick
On Wed, Jun 13, 2012 at 2:00 PM, Alex Queiroz asandroq@gmail.com wrote:
Hallo,
On Fri, Jun 8, 2012 at 11:44 PM, Mikael mikael.rcv@gmail.com wrote:
Anyone please feel free to suggest questions or angles on subjects that should be addressed in this document, so that these will be covered too.
- How the partial evaluator works
-- -alex http://www.artisancoder.com/ _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
I have read through some articles on partial evaluation before, and found that most of them are either too trivial (e.g. the popular printf partial evaluator) or that the article immediately delves into the theory and too quickly jumps into notation. An explanation of Gambit's partial evaluator applied to a simple example, and a description of the various bookkeeping datastructures used would be extremely helpful to me. The description of the datastructures would be extremely helpful in particular. I am also interested in whether the partial evaluator is built as a separate system, or whether it is closely coupled with Gambit's interpreter.
Thanks very much! -Patrick
On Wed, Jun 13, 2012 at 2:20 PM, Mikael mikael.rcv@gmail.com wrote:
Am putting together a tree of questions for this currently.
As for how the partial evaluator works, it would be great if you could please think of and tell here, how you would formulate one or more questions (in the same format as you would typically express them in a personal conversation), that together would communicate this understanding to you [of how the partial evaluator works].
Brgds
2012/6/14 Patrick Li patrickli.2001@gmail.com
- How the partial evaluator works
Seconded! I would love to hear about this also. -Patrick
On Wed, Jun 13, 2012 at 2:00 PM, Alex Queiroz asandroq@gmail.com wrote:
Hallo,
On Fri, Jun 8, 2012 at 11:44 PM, Mikael mikael.rcv@gmail.com wrote:
Anyone please feel free to suggest questions or angles on subjects that should be addressed in this document, so that these will be covered
too.
- How the partial evaluator works
-- -alex http://www.artisancoder.com/ _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
-
Alex Queiroz -
Marc Feeley -
Mikael -
Patrick Li