Orbit: An Optimizing Compiler for Scheme (1986) [pdf](cpsc.yale.edu)
cpsc.yale.edu
Orbit: An Optimizing Compiler for Scheme (1986) [pdf]
http://cpsc.yale.edu/sites/default/files/files/tr445.pdf
27 comments
Interestingly, one of the pages you link (http://mumble.net/~jar/tproject/) links a paper (grep "1986: Kelsey dissertation on rewrite-based compilation
") that shows the implementation of a compiler with multiple frontends (BASIC, Scheme, Pascal) using only source-to-source) transformation.
I find this interesting because in a certain way, this reminds me of how the go assembler works (https://www.youtube.com/watch?v=KINIAgRpkDA).
For those who haven't seen the talk: basically the go compiler works on the assumption that pretty much all computer, in a way, move memory from one address to another, generate and handle interrupts, have call/return instructions and so on. Thus, the go compiler emits (IIRC) some sort of "intermediate assembler" (somehow similar to llvm's intermediate representation, but simpler) and then proceeds to "translate" such assembler to various platform native assembler. I clearly remember Rob Pike (in the talk) saying "so the task of supporting a new platform becomes a task in text processing" (okay, maybe it was worded a bit better).
This might be a bit tangential, but it is interesting how some "new" ideas aren't that new after all. But I guess this is due to Rob Pike's deep experience and history with computers.
I find this interesting because in a certain way, this reminds me of how the go assembler works (https://www.youtube.com/watch?v=KINIAgRpkDA).
For those who haven't seen the talk: basically the go compiler works on the assumption that pretty much all computer, in a way, move memory from one address to another, generate and handle interrupts, have call/return instructions and so on. Thus, the go compiler emits (IIRC) some sort of "intermediate assembler" (somehow similar to llvm's intermediate representation, but simpler) and then proceeds to "translate" such assembler to various platform native assembler. I clearly remember Rob Pike (in the talk) saying "so the task of supporting a new platform becomes a task in text processing" (okay, maybe it was worded a bit better).
This might be a bit tangential, but it is interesting how some "new" ideas aren't that new after all. But I guess this is due to Rob Pike's deep experience and history with computers.
There are some more bits of T-ness here: http://mumble.net/~campbell/t/ related to the T Revival Project, which itself is in need of reviving.
It says on the revival project page [1] that the plan was to make T R5RS compatible. That is probably why they abandoned T to make Scheme 48 [2]
I am also interested in the revival of this language, but I don't see what the point of that would be. Does anyone here feel the same way?
[1] http://web.archive.org/web/20070103020434/http://mumble.net/...
[2] http://s48.org/
I am also interested in the revival of this language, but I don't see what the point of that would be. Does anyone here feel the same way?
[1] http://web.archive.org/web/20070103020434/http://mumble.net/...
[2] http://s48.org/
It was verified as part of VLISP project. So, I've been keeping papers on PreScheme, Scheme48, and VLISP in case anyone wants to redo them with modern techniques. Another commenter, hga, helped me find a few I didn't have before with the specific algorithms. The basic ones are on the bottom here:
https://en.wikipedia.org/wiki/PreScheme
PreScheme itself is possibly worth reviving esp with ref counting or Rust's type of no-GC safety. I know another LISP, Carp, is trying to do something like the latter.
https://en.wikipedia.org/wiki/PreScheme
PreScheme itself is possibly worth reviving esp with ref counting or Rust's type of no-GC safety. I know another LISP, Carp, is trying to do something like the latter.
Thanks for the reminder, I loved rereading this article.
Even though I read this years ago, I'm still having vertigo when reading the last part. So many people, so many ideas .. so much inspiration.
Even though I read this years ago, I'm still having vertigo when reading the last part. So many people, so many ideas .. so much inspiration.
Interesting historical note: this is the compiler we used to program the research rovers at JPL before the Sojourner mission. It compiled an object-oriented dialect of Scheme called T which IMHO is one of the most elegant programming languages ever designed. It is not almost totally forgotten, and the world is poorer for it. :-(
(OakLisp is another beautiful riff on Scheme. Like T, it too has been all but completely forgotten AFAICT.)
(OakLisp is another beautiful riff on Scheme. Like T, it too has been all but completely forgotten AFAICT.)
For the historical record:
> It is not almost totally forgotten
That should, of course, have been "now", not "not".
> It is not almost totally forgotten
That should, of course, have been "now", not "not".
> It compiled an object-oriented dialect of Scheme called T
do you have a link for this? It's difficult to search for.
update: ignore me, found a link in the comments: http://mumble.net/~jar/tproject/
first line: "It occurred to me recently that The T Project had no coherent presence on the web." :)
do you have a link for this? It's difficult to search for.
update: ignore me, found a link in the comments: http://mumble.net/~jar/tproject/
first line: "It occurred to me recently that The T Project had no coherent presence on the web." :)
source repo for oaklisp https://github.com/barak/oaklisp
There is also Kelsey's 1989 popl paper, which explains the idea of compilation as program transformation very clearly.
Kelsey and Hudak "Realistic Compilation by Program Transformation" POPL 1989
Kelsey and Hudak "Realistic Compilation by Program Transformation" POPL 1989
A similar Scheme-to-C project I wrote last century for the SCM scheme, should be still usable: http://people.csail.mit.edu/jaffer/hobbit.pdf
One goal of the project was to produce human-readable C.
One goal of the project was to produce human-readable C.
- Stalin WPO compiler: https://en.wikipedia.org/wiki/Stalin_(Scheme_implementation)
- Larceny: https://en.wikipedia.org/wiki/Larceny_(Scheme_implementation...
(Personally, I haven't explored any of these yet. I plan to get into scheme-to-C compilation some day. I think it's the future of programming, but I might be wrong.)
- Larceny: https://en.wikipedia.org/wiki/Larceny_(Scheme_implementation...
(Personally, I haven't explored any of these yet. I plan to get into scheme-to-C compilation some day. I think it's the future of programming, but I might be wrong.)
Why do you think scheme-to-C compilation is the future of programming?
Scheme allows practically infinite possibility of language extension due to its syntax (this is same with lisp and scheme, but I prefer scheme due to its lexical scoping, a minimal standard like R7RS etc). (Note that I'm a big advocate of Python-C hybrid programming too, and so for me it's either python-and-C or scheme-and-C)
Moving towards Scheme-to-C is moving towards solving all performance/concurrency/what-not problems of a high-level-language like Scheme, without having to drop down to a low-level-language like C (or assembly). (I guess I should say that there might be a need for generating code for GPU, e.g., OpenCL. Just a heads up that I'm not trying to ignore that).
What I say has to be qualified with two very important assumptions:
- I believe 'large-scale programming' is 'research'. E.g., if the system you're building is under 20k-50k lines of code, give or take, it largely doesn't matter what paradigm you're using, or what language you're using. But for larger systems, the best way forward is to treat such a complex system as a research topic, and try to work at a higher level of abstraction, watch out for opportunities of creating new DSLs, and so on. (I believe this is part of the reason large projects do better in open source, firefox, linux, chromium, etc, etc. No manager is watching over your shoulders with a stick and a deadline on their notepad.).
- You have to think in terms of meta-programming. It comes in many flavors but take code-generation. Think of the whole purpose of your scheme code is to let you generate human-readable C code. For me, meta-programming means never having to write your program (here the program is the C code), but using tools and machines that write the program for you (here the tool and the machine is Scheme).
E.g., take a very large system like the linux kernel. It's 90% C with some assembly. A big motivation for my ideas comes from asking the question 'Can we develop and work at a high layer of abstraction in Scheme and create a code of ~100K to ~200K lines, that, using the ideas of meta-programming, compiles down to ~20M lines of C code which is functionally equivalent, as well as equally readable, to the current ~20M lines of the linux kernel?' (Note the scheme code size being 1% of the C code size!)
When you think along those lines, and realize that 21st-century large-scale programming is just getting started and something like a linux kernel is just the tip of the iceberg, you probably would reach many of the conclusions and beliefs that I gravitate towards.
Note that my ideas are in stark contrast to people who think the problem is that we need a new programming language. In that regard, I'm anti C++, D, Go, Rust, Swift, Kotlin, etc, etc. We don't need a new programming language. We need to treat the activity of programming as a research activity. (again, I'm talking about large-scale).
Moving towards Scheme-to-C is moving towards solving all performance/concurrency/what-not problems of a high-level-language like Scheme, without having to drop down to a low-level-language like C (or assembly). (I guess I should say that there might be a need for generating code for GPU, e.g., OpenCL. Just a heads up that I'm not trying to ignore that).
What I say has to be qualified with two very important assumptions:
- I believe 'large-scale programming' is 'research'. E.g., if the system you're building is under 20k-50k lines of code, give or take, it largely doesn't matter what paradigm you're using, or what language you're using. But for larger systems, the best way forward is to treat such a complex system as a research topic, and try to work at a higher level of abstraction, watch out for opportunities of creating new DSLs, and so on. (I believe this is part of the reason large projects do better in open source, firefox, linux, chromium, etc, etc. No manager is watching over your shoulders with a stick and a deadline on their notepad.).
- You have to think in terms of meta-programming. It comes in many flavors but take code-generation. Think of the whole purpose of your scheme code is to let you generate human-readable C code. For me, meta-programming means never having to write your program (here the program is the C code), but using tools and machines that write the program for you (here the tool and the machine is Scheme).
E.g., take a very large system like the linux kernel. It's 90% C with some assembly. A big motivation for my ideas comes from asking the question 'Can we develop and work at a high layer of abstraction in Scheme and create a code of ~100K to ~200K lines, that, using the ideas of meta-programming, compiles down to ~20M lines of C code which is functionally equivalent, as well as equally readable, to the current ~20M lines of the linux kernel?' (Note the scheme code size being 1% of the C code size!)
When you think along those lines, and realize that 21st-century large-scale programming is just getting started and something like a linux kernel is just the tip of the iceberg, you probably would reach many of the conclusions and beliefs that I gravitate towards.
Note that my ideas are in stark contrast to people who think the problem is that we need a new programming language. In that regard, I'm anti C++, D, Go, Rust, Swift, Kotlin, etc, etc. We don't need a new programming language. We need to treat the activity of programming as a research activity. (again, I'm talking about large-scale).
> We need to treat the activity of programming as a research activity.
You know about Racket, right?
https://racket-lang.org/
They're not kidding when they call it an ecosystem for developing new languages (indeed, racket itself is on some bleeding edges of language research, notably in the area of sound gradual typing with the ongoing typed racket project). Many Racketeers are researchers who take metaprogramming very seriously.
Racket currently uses the GNU lightning VM[1] via a JIT compiler, but is migrating onto the recently much-less-encumbered Chez (thanks, Cisco!).
https://groups.google.com/forum/#!msg/racket-dev/2BV3ElyfF8Y...
Recent update!
https://groups.google.com/forum/#!topic/racket-dev/rkXuHNAmQ...
Lightning and Chez both provide AOT features that Racket can use, although neither can really do source-to-source translation of Racket to C.
If you really want a modern scheme->C, then Chicken Scheme https://www.call-cc.org/ is your best bet. It gains some advantages by using (highly idiomatic) C as an intermediate language, but unfortunately then has to contend with C language idioms and constraints, especially C's runtime, which strongly constrains Chicken's approaches to concurrency.
I find it difficult to imagine that anyone will sit down and write a scheme->C compiler that produces human-readable C. You can see for yourself what Chicken emits, and that's still much more readable than the long-dead DEC Scheme->C's output.
Lastly, doing serious systems programming in Scheme is both feasible and has even been done. Sadly one extremely interesting example of this is decaying at http://www.scsh.net/ (the links to Shivers's papers are broken, and frankly they were the most entertaining parts of SCSH) although some ideas originating in SCSH have been ported to other Scheme implementations.
[1] kinda. http://lists.racket-lang.org/dev/archive//2014-September/014...
You know about Racket, right?
https://racket-lang.org/
They're not kidding when they call it an ecosystem for developing new languages (indeed, racket itself is on some bleeding edges of language research, notably in the area of sound gradual typing with the ongoing typed racket project). Many Racketeers are researchers who take metaprogramming very seriously.
Racket currently uses the GNU lightning VM[1] via a JIT compiler, but is migrating onto the recently much-less-encumbered Chez (thanks, Cisco!).
https://groups.google.com/forum/#!msg/racket-dev/2BV3ElyfF8Y...
Recent update!
https://groups.google.com/forum/#!topic/racket-dev/rkXuHNAmQ...
Lightning and Chez both provide AOT features that Racket can use, although neither can really do source-to-source translation of Racket to C.
If you really want a modern scheme->C, then Chicken Scheme https://www.call-cc.org/ is your best bet. It gains some advantages by using (highly idiomatic) C as an intermediate language, but unfortunately then has to contend with C language idioms and constraints, especially C's runtime, which strongly constrains Chicken's approaches to concurrency.
I find it difficult to imagine that anyone will sit down and write a scheme->C compiler that produces human-readable C. You can see for yourself what Chicken emits, and that's still much more readable than the long-dead DEC Scheme->C's output.
Lastly, doing serious systems programming in Scheme is both feasible and has even been done. Sadly one extremely interesting example of this is decaying at http://www.scsh.net/ (the links to Shivers's papers are broken, and frankly they were the most entertaining parts of SCSH) although some ideas originating in SCSH have been ported to other Scheme implementations.
[1] kinda. http://lists.racket-lang.org/dev/archive//2014-September/014...
What does C get you, in the long run? Why not just compile Scheme to machine code directly?
Note that Chez takes this approach, and is faster than Chicken, which compiles to C.
Note that Chez takes this approach, and is faster than Chicken, which compiles to C.
Some apparently regularly updated benchmarks comparing implementations of scheme: https://ecraven.github.io/r7rs-benchmarks/benchmark.html
Chez isn't always the fastest, but it's the fastest so often that I wouldn't look much beyond it if performance were of major importance to me. It's been written about here on HN before, but the next major version of Racket will be based on Chez. Chez will get package management, libraries, and modern tooling of Racket, and Racket will (presumably) be able to capitalize on the performance of Chez.
Of course if you come from, say Python, performance shouldn't really matter much to you, as pretty much all the schemes are already playing in a different league: http://benchmarksgame.alioth.debian.org/u64q/compare.php?lan...
Chez isn't always the fastest, but it's the fastest so often that I wouldn't look much beyond it if performance were of major importance to me. It's been written about here on HN before, but the next major version of Racket will be based on Chez. Chez will get package management, libraries, and modern tooling of Racket, and Racket will (presumably) be able to capitalize on the performance of Chez.
Of course if you come from, say Python, performance shouldn't really matter much to you, as pretty much all the schemes are already playing in a different league: http://benchmarksgame.alioth.debian.org/u64q/compare.php?lan...
I've received this criticism of my approach before.
Note I'm talking about not just C code-gen, but human-readable C code-gen. If it's not human-readable, then I agree with you, we might as well generate machine code and become full-time scheme programmers.
But if it's human readable C, as if the code was created by a C programmer with clean coding practices, then it makes a big difference.
You might ask, "but why human readable?"
I think the answer is that as a result, you can work on that C project, try out ideas, pick the one that works best, then go back to scheme to see how you can generate what you just tried out. It's a long-winded way of doing things, but you're doing research, you're not simply taking a hand-written change-set in C and creating the simplest scheme code to generate it (e.g., dumping a sequence of string literals to stdout). You are exploring the higher abstractions of the scheme code, and finding out how the new code that generates new change-set fits in with the rest of the scheme code.
Take 'logging' for example. Logging is orthogonal to a functioning C code. A well written fully functioning 10k lines of C program could easily become 30k-50k lines simply by adding comprehensive logging and not adding a single other feature.
If scheme code-generator has a logging module, it would not generate logging code directly, but it would take the non-logging functionality of the program as input, analyze it, and output logging code as a result. Further more, you could disable logging code-gen, and generate the original 10k lines of code, and then study the C code, and it would help a lot with readability (you're not coming across 10 lines of logging code every 2 or 3 lines of actual code).
Similarly, debuggability. A scheme code could help insert debugging code at relevant points. Heck, we're using scheme as a tool, a machine to help our coding, why not use scheme as an automation agent, i.e., use it to iterate through a debugging process by giving some directions in the beginning and letting it triangulate the exact line in C code which, e.g., causes a segmentation fault.
C code is full of error checks. Every function call is followed by "if (error1) { do_this(); } else if (error2) { do_that(); }". Wish to read the code without error checks? Just re-generate the code with error-checking disabled! Done.
Even more, you use scheme to generate various kinds of data that can be used for analysis. E.g., you wish to visualize the call-graph of the C code? you could generate the graph data file then run it through graphviz. (I know gcc does that already but then what is gcc? an automation tool for your C program! All I'm saying is that all these things can be done in a much better way in scheme)
(again, think of Scheme as a tool and an automation agent, and C code being the actual program!).
Note I'm talking about not just C code-gen, but human-readable C code-gen. If it's not human-readable, then I agree with you, we might as well generate machine code and become full-time scheme programmers.
But if it's human readable C, as if the code was created by a C programmer with clean coding practices, then it makes a big difference.
You might ask, "but why human readable?"
I think the answer is that as a result, you can work on that C project, try out ideas, pick the one that works best, then go back to scheme to see how you can generate what you just tried out. It's a long-winded way of doing things, but you're doing research, you're not simply taking a hand-written change-set in C and creating the simplest scheme code to generate it (e.g., dumping a sequence of string literals to stdout). You are exploring the higher abstractions of the scheme code, and finding out how the new code that generates new change-set fits in with the rest of the scheme code.
Take 'logging' for example. Logging is orthogonal to a functioning C code. A well written fully functioning 10k lines of C program could easily become 30k-50k lines simply by adding comprehensive logging and not adding a single other feature.
If scheme code-generator has a logging module, it would not generate logging code directly, but it would take the non-logging functionality of the program as input, analyze it, and output logging code as a result. Further more, you could disable logging code-gen, and generate the original 10k lines of code, and then study the C code, and it would help a lot with readability (you're not coming across 10 lines of logging code every 2 or 3 lines of actual code).
Similarly, debuggability. A scheme code could help insert debugging code at relevant points. Heck, we're using scheme as a tool, a machine to help our coding, why not use scheme as an automation agent, i.e., use it to iterate through a debugging process by giving some directions in the beginning and letting it triangulate the exact line in C code which, e.g., causes a segmentation fault.
C code is full of error checks. Every function call is followed by "if (error1) { do_this(); } else if (error2) { do_that(); }". Wish to read the code without error checks? Just re-generate the code with error-checking disabled! Done.
Even more, you use scheme to generate various kinds of data that can be used for analysis. E.g., you wish to visualize the call-graph of the C code? you could generate the graph data file then run it through graphviz. (I know gcc does that already but then what is gcc? an automation tool for your C program! All I'm saying is that all these things can be done in a much better way in scheme)
(again, think of Scheme as a tool and an automation agent, and C code being the actual program!).
I feel a "Use Nim" but sorely need to restrain myself.
I know Nim but moved away after trying it out briefly.
I may not have emphasized in my comment but human-readable code-gen is very important.
Think of scheme as just a tool to generate C code, and C code is your actual code that you wish to deal with (debugging, benchmarking, trying out variations, etc). If the code is not human readable, then you might as well forget about C and become a full-time scheme programmer.
I may not have emphasized in my comment but human-readable code-gen is very important.
Think of scheme as just a tool to generate C code, and C code is your actual code that you wish to deal with (debugging, benchmarking, trying out variations, etc). If the code is not human readable, then you might as well forget about C and become a full-time scheme programmer.
Can anyone recommend an ocr program that can convert these old pdf scans to modern type?
ABBYY Finereader
Rees maintains a related archive [most recently updated 2010] on his page at http://mumble.net/~jar/tproject/
That in turn links to Shivers's overview of T and the development of its compilers (including Orbit) at http://www.paulgraham.com/thist.html