If you're interested, the Anarki lib/arcformat.arc is actually a start at parsing Arc syntax; we just have to change the filters so that instead of emitting html, we emit Arc objects wrapped in singleton lists. It uses treeparse.
treeparse is pretty good, and I'm sure a full Arc parser can be built on treeparse.
Looks like I need to speed up writing my treeparse tutorial ^^
As for parsing special syntax, an Arc version of ssyntax would work: we just need a symbol->string conversion (meaning full 'coerce support) and seek ~!.: in the substring.
edit: how did you handle continuations and tail call opts?
Ah, I'll have a closer look at arcformat then. Might be good to have a reader :)
Continuations & tail-calls are treated the way Steele proposed it in the lambda papers.
The following code :
(set f (fn (n)
(if (< n 2)
n
(+ (f (- n 1)) (f (- n 2))))))
(prn (f 30))
is first translated so as to have unique names for variables and so that primitive operations are prefixed with a % (we won't treat them the same way as other operations in the next steps) :
Then we perform continuation-passing-style transformation : each function call is given, as an extra parameter, the portion of code (the continuation) it will send its result to : functions do not return, they call another function with the value they calculated :
(Sorry for the indentation, I don't feel like indenting this by hand, but you get the idea I guess ?)
Generating C code from there is then easy. It is almost only Marc feeley's code, based on Steele's ideas a few years ago. I only changed the code so that it understands Arc code and primitives instead of Scheme's...
I assume that for code blocks 3 and 4, 'let is the Lisp 'let, not the Arc one? (let ((var val)) ...) not (let var val ...)?
Also on code block 1 you show (prn (f 30)) but in code block 2 you seem to pass (f <continuation> 20)? I assume this is just a mistake?
I managed to understand the transformation up to code block 3, but not code block 4; what does '%closure do? Allocate heap memory for the closure? Also, what's the syntax for "goto"?
Finally: how about the equivalent C code?
LOL, maybe I should just wait for you to push it on the git and experiment with it myself.
Aruu, okay okay I finally actually looked at the presentation docs, which I probably should have looked at first. One of the things that threw me off was 'self - I was thinking of Arc's sense of 'self as in 'afn!
The output C code looks suspiciously like assembly language to me. Perhaps we can also target a temporary assembly syntax so that we can do minimal peephole opts, such as convert stuff like PUSH(x); y = TOS(); to MOVE(x,y);. Can't wait to actually see this code on the git ^^.
P.S. Given that the transformations are (gasp!) syntactic, it might actually be possible to implement the entire compiler as (gasp gasp!) a treeparse parser (or at the very least a piped chain of treeparse parsers) ^^.
Maybe treeparse would be the right thing to use... The code is getting uglier everytime I try to add a new primitive / special form... I dunno...
As for the generated code, yes, it's a lot like a portable assembly code. There are certainly easy optimizations to perform on it, but as for now, it's working and that's a lot :)
And yes, let is the traditional one -- with tons of parens everywhere.
I'll go through the code later to see what can be done. Certainly the AST looks representable as plain lists to me, although I haven't fully analyzed it yet.
As an aside compile-file could be restructured like the following:
(def compile-file (filename)
(compile-ast (parse-file filename) (+ (strip-ext filename) ".c")))
; to allow programmatic access
(def compile-ast (ast dest)
; chain of conversions
(let chain
(list
(list cps-convert "CPS-CONVERSION")
(list closure-convert "CLOSURE-CONVERSION"))
; do reduction
(let final-ast
(reduce
(fn (ast (f desc))
(let new-ast (f ast)
(prn "----------------- AST after " desc)
(prn (source new-ast))
new-ast))
chain ast)
(prn "-------------------- C Code:")
(w/outfile f dest
(w/stdout f
(prn:liststr:code-generate final-code))))))
This should allow easy insertion of any steps (e.g. optimization steps) along the way.
In fact the chain list should probably be better use `(,), so that we can support flags or suchlike for optimizations:
For that matter my concern is with the expansion of PUSH and POP:
PUSH(x); y = POP();
=>
*sp++ = x; y = *--sp;
Can gcc peephole the above, completely eliminating the assignment to the stack (which is unnecessary in our case after all)?
y = x; //desired target
Without somehow informing gcc to the contrary, gcc will assume that writing to * sp is significant, even though in our "higher-level" view the assignment to * sp is secondary to transferring the data between two locations.
Well, with full optimizations on gcc (-O3), it doesn't change anything (at least in execution time, I didn't compare generated machine codes). Wow, gcc seems really clever. Now that I know how hard it is to implement a compiler, I can only applaud :)
"Google does not have specific eligibility requirements for mentors, as we know our mentoring organizations will be best able to determine the selection criteria for their mentors."
I don't know if LispNYC has any specific requirements.
As a mentor, I think you have to be in email contact with your student, give them advice as necessary, and evaluate their work. I believe I read somewhere that they estimate mentoring will take about 5 hours a week depending on the number and difficulty of projects.
If there's no need to be physically there, I'm willing to mentor you, in case sacado is somehow disqualified or is otherwise unable to mentor you (I'll probably ask sacado to unofficially mentor my mentoring you, though, sort of a meta-mentor). Anyway I've just applied, although I'll gladly defer to sacado (it'll be mostly his code anyway) if he is able to mentor you.
Note that due to various circumstances, I won't be able to leave my country until about a year or so, so if my physical presence is needed, sorry!
Ok, I submitted my proposal to GSoC. If you'd like to mentor, I would appreciate it. (Otherwise I can't get funded.) And please note that if you want to mentor, you need to apply today, or tomorrow (March 31) before 5:00 PM PDT.
mzscheme has a rather good C API. I was thinking about using it to generate C code for Arco that would less rely on mzscheme after each release, before both are totally independant.
I am currently working on the one at the first address. I translated it to Arc. In other words, I have a scheme compiler written in Arc that can hardly do anything but compile the fib function to C.
Pretty soon, I'll have something compiling a poor subset of Arc (only fixnums and symbols, no list, no bignum, no GC, no special syntax, but with closures and call/cc fully operational).
"Yes, the assembly part of it looks difficult to me. When I look at Arc or Lisp code I don't see any way to translate that to native code. Obviously has been done, I'm just not educated on such matters."
I found a good link / tutorial about how to compile a subset of Scheme to C language. The compiler is about 800 lines of Gambit Scheme (blank lines included) and even deals with tail-recursion and continuations ! (well, that's based on the lambda papers...)
No GC, but you can use Boehm and have one for free.
I tried that. Not very easy as Ikarus' hash-tables don't work like mzscheme's (there is no "equal" hash-tables). You would have to rewrite the reader too. And I'm not sure we would get all the stuff with sockets and networking. It doesn't have an FFI yet, either.
Well, actually, I'm not sure if implementing a still-designed language in the beta-release of a compiler is a long-term solution... :) Maybe in a few months / years this could be done ? But as for now, I think porting it to CL would be easier.
If you look in the long term run the best (and most difficult) solution would be to write an Arc compiler that translates Arc code directly in machine code.
I also suggest that. In fact, looking at Chicken's implementation - stack == heap - is rather inspiring, because it shows exactly how a garbage-collected memory manager should be done: just decrement a pointer, in this case the stack pointer. Brilliant IMO. Wish I'd thought of that.
The funny thing is that, even in some of my webapps, I always needed some more speed, at one moment or another. The last example I have in mind : I wanted to generate a chart showing the use of a big system. As the chart's look depends on a few criteria given by the user, it has to be generated on demand. Well I had to dig into a DB containing millions of items, then mix these items together (that couldn't be done in SQL) and finally generate the chart.
Glad I had Psyco there. If I hadn't had it, or at least Pyrex, I would have probably dropped Python because writing C extensions for it is quite painful. And that's also the reason why I never really used Ruby, despite its cool features.
And I don't want to write prototypes and say : "Hmm... My code is working now, let's write it in a serious language for the production version".
Look at Scheme anyway. We really can't say it's a language focused on speed or designed to crunch numbers. Well, look at Ikarus. Oh, yes, for number crunching, you might prefer Stalin. Even C looks slow when compared to Stalin.
Of course, this shouldn't be the main focus of the community, and I don't even think the language should be designed with speed in mind (well, a little of course, or else we would have dead slow numbers implementd with lists of symbols) but that it should be seriously taken into consideration.
Yes, exactly. I think a major cause of all this railing against optimizations is all the newbies who have just learned to write programs running around shouting about efficiency. I was one of those just a couple of years ago. The problem with these newbies is that they're naive. They decide that something is fast or slow based on how efficient its most naive implementation sounds. It seems that they grasp the vague idea that optimized code tends to be longer than code that is not optimized, but rather than responding to that by not trying to optimize until they know what parts of the code are slow, they respond by assuming that approaches that take more lines of code are more efficient and therefore better.
A misplaced focus on speed is bad, and you should get it working before you make it fast, but that doesn't mean speed is a non-issue. If a program is slow enough to cause annoyance, that is a problem, and it should be fixed. Languages have to pay extra attention to speed issues. If programs written in a language are slow because of the language, and not because the programs themselves are badly written, there's something wrong with the language.
Another thing that newbies don't get is that well-built languages are usually optimized so that the more obvious and more commonly-used approaches are actually faster than that tangled mass of "optimized" code you just wrote. Profiling profiling profiling. Don't just guess.
So, the points are: performance should be a secondary concern, but secondary is still pretty high up on the list, and optimization should be based on information gathered with a profiler, not what sounds efficient or inefficient. Sorry for rambling, I hope this post contributes something to something. I just have a tendency to spew everything I have to say about a topic all in one place every now and then, even if only some of it is relevant. I guess you could boil this post down to a "me too", but only if you boiled it a lot.
Anyway, maybe the right way to do so is by destructuring a Scheme implementation ? Starting from a given implementation, you write your compiler from scratch, but use the facilities of the chosen implementation for the reader and the GC. Then, once it's working, you gradually remove the scaffolding by implementing these things by hand...
Well, if you're going to end up implementing something like my unrolled-lists ideas, then everything can very well be a cons cell underneath. Including bignums and strings.
It's because 'quote doesn't necessarily create a new list every time (at least not in function definitions). If you do
(def foo ()
'(a b c))
(foo) will return the same list every time, so if you modify the list in or before your next call, you'll get the modified instead of the original value.
