[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Hello from a new user interested in shipping applications
Thanks again for all the comments (public and private).
Well, just to take DrScheme out for a spin, I coded up something that
can translate the simple numerical Scheme->C example I presented. I
think the hardest part was actually writing "for-each-between", which I
am used to from iterating over Smalltalk collections.
This is my first major Scheme program beyond a few GUI tests, and some
turtle drawing, so be kind! :-) I haven't used Lisp like languages for
about a dozen years. Suggestions for improvements or pointers to
libraries or other code in MzScheme to make this easier appreciated.
Since this was just for fun and to learn a bit, I haven't tried to
figure out how mzc works yet or even looked at the code, for example --
assuming it is in Scheme? Presumably it would be more efficient to
modify mzc instead.
Notice the beginner approach of bypassing I/O -- just like TeachScheme!
advocates. Just copy and paste your C program from the DrScheme
evaluation window after executing. You need to insert your program to be
converted at the top in place of what's there. [Under NT 4.0 Edit|Copy
seems to not work until I do it first by the menu selections -- I'm
using 102 with the patch.]
First, here is the output program which compiles under Visual C++ 5.0. I
threw in a "(sin 1.0)" in the source program just for an added test.
Mzc choked with an internal error for me on trying to link in the
mzdyn.obj file when I tested it or I'd try automating this more. Maybe
mzdyn.obj was compiled under 6.0 and I need to set a flag?
==== Sample output (some blank lines removed) =========
//code converted from Scheme to C by ConverterToCCode.scm
#include <math.h>
#include <stdio.h>
//Scheme: (define (foo a b) (* a b))
float foo(float a, float b) {
return a*b;
}
//Scheme: (define (bar a b) (/ a b))
float bar(float a, float b) {
return a/b;
}
//Scheme: (define (baz a b) (+ (foo a b) (bar a b) (sin 1.0)))
float baz(float a, float b) {
return foo(a, b)+bar(a, b)+sin(1.0);
}
//Scheme: (define (main) (print (baz 10 20)))
void main() {
printf("%f\n", baz(10, 20));
}
//main
==== the MzScheme code -- feel free to use it under an X/MIT License
======
;example of converting MzScheme to numerical C
;Paul Fernhout pdfernhout@kurtz-fernhout.co
;2000 07 31
;Proof of concept -- no doubt function names should be better,
;and probably mzc could provide more useful code!
;define the program here
;restricted to simple function evaluations which each return one value
(define code-to-convert '(
(define (foo a b) (* a b))
(define (bar a b) (/ a b))
(define (baz a b) (+ (foo a b) (bar a b) (sin 1.0)))
;(define (baz a b) (+ (foo a b) (bar a b)))
(define (main) (print (baz 10 20)))
(main)
))
;define various code generation functions
(define (for-each-between func-each func-between args)
(if (null? args)
'()
(begin
(func-each (car args))
(if (not (null? (cdr args)))
(begin
(func-between args)
(for-each-between func-each func-between (cdr args)))))))
(define (print-type-and-name name)
(if (eq? name 'main)
(printf "void main")
(printf "float ~s" name)))
(define (print-arg arg)
(printf "float ~s" arg))
(define (print-comma args)
(printf ", "))
(define (print-args args)
(printf "(")
(for-each-between print-arg print-comma args)
(printf ")"))
(define (infix? operator)
(not (char-alphabetic? (car (string->list (symbol->string
operator)))))
)
(define (print-infix-call-arg arg)
(if (list? arg)
(print-call arg)
(print arg)))
(define (print-infix-call call)
(for-each-between print-infix-call-arg
(lambda (x) (print (car call)))
(cdr call))
)
(define (print-functional-call-arg arg)
(if (list? arg)
(print-call arg)
(printf "~s" arg)))
(define (print-function-name name)
(if (eq? name 'print)
(printf "printf(\"%f\\n\", ")
(printf "~s(" name)))
(define (print-functional-call call)
(print-function-name (car call))
(for-each-between print-functional-call-arg print-comma (cdr call))
(printf ")")
)
(define (print-call call)
(if (infix? (car call))
(print-infix-call call)
(print-functional-call call)))
(define (print-calls calls has-return)
(printf " {")
(newline)
(if has-return
(printf "return "))
(for-each print-call calls)
(printf ";")
(newline)
(printf "}")
(newline)
)
(define (define-c-function definition)
(let ((name (caadr definition))
(args (cdadr definition))
(calls (cddr definition)))
(printf "//Scheme: ")
(print definition)
(newline)
(print-type-and-name name)
(print-args args)
(print-calls calls (not (eq? name 'main)))
(newline))
)
;(print input)
(define (convert-to-c-code definition)
; toss the main invocation
(if (eq? (car definition) 'main)
(print '//main)
(define-c-function definition))
(newline))
(define (generate-c-code-for-program program)
(printf "//code converted from Scheme to C by ConverterToCCode.scm")
(newline)
(printf "#include <math.h>")
(newline)
(printf "#include <stdio.h>")
(newline)
(newline)
(for-each convert-to-c-code program)
)
(generate-c-code-for-program code-to-convert)
============== end code ======================
Definitely seems easier than type inferencing to me (if less robust).
Problem is, I don't do loops or if-then yet, so maybe this approach will
run out of steam as it gets more elaborate.
Squeak Smalltalk has some tools to do Smalltalk->C, but they consist of
about twenty classes and many methods. This code is definitely much more
concise, of course largely because Scheme is easier to parse.
-Paul Fernhout
Kurtz-Fernhout Software
=========================================================
Developers of custom software and educational simulations
Creators of the Garden with Insight(TM) garden simulator
http://www.kurtz-fernhout.com
Paul Fernhout wrote:
>
> Noel-
>
> Thanks for the great pointers and suggestions.
>
> Certainly improving MzScheme numerical performance automatically by
> analyzing the program would be fantastic. I'm not sure I'm personally up
> to spending time doing this though (given limited time).
>
> However, Squeak does translation of Smalltalk to C and I think the type
> hinting it uses is not that bad. What follows is inspired in part by
> that.
>
> One of the things that appeals to me in Scheme (over say Python or
> Smalltalk) is that it is somewhat more straightforward to process Scheme
> programs with hints or assumptions.
>
> For example, if I write this in MzScheme and save it in the file:
>
> (define (foo a b) (* a b))
> (define (bar a b) (/ a b))
> (define (baz a b) (+ (foo a b) (bar a b)))
> (define (main) (print (baz 10 20)))
> (main)
>
> there is little to then stop me from easily parsing the input file as a
> list and then running my own operations on it to generate C code with an
> assumption that all arguments are floats unlest specifed otherwise, to
> get:
>
> float foo(float a, float b) {return a * b;}
> float bar(float a, float b) {return a / b;}
> float baz(float a, float b) {return foo(a, b) + bar(a, b);}
> void main(void) {printf("%f", baz(10, 20));}
>
> Then I can almost trivially have a list of variable names to treat
> otherwise.
> Ex. '((int p q r) (string s t u) (float-array l m n))
> Obviously, you need to work in a subset of MzScheme to do this (no "car"
> or "cdr" use for example) but in practice the core numerical parts of
> something like a simulation are often mainly loops, tests, array
> references, and numerical operations. [Note: I did this conversion by
> hand.]
>
> This is very different from compiling these functions to code that would
> work generically with MzScheme, where a and b might be strings or lists
> or objects.
> To optimize that sort of code, you definitely would need a system for
> inferring types.
>
> Obvious limitations of this approach are that it won't neccesarily give
> the same exact results under MzScheme -- for example, MzScheme prints
> "401/2" as the answer to the above, whereas the C program prints
> "200.500000". They are equivalent mathematically in this case, but might
> not be in others.
>
> The important point to make here is that because the algorithm is
> encoded in MzScheme, there are all sorts of interesting things that are
> easy to do with it (analyze interdependencies, variable useages, browse
> it, generate assembler code directly, etc.). C is a much more difficult
> informational container to extract algorithm related information from,
> because you need to have a C parser, etc.
>
> -Paul Fernhout
> Kurtz-Fernhout Software
> =========================================================
> Developers of custom software and educational simulations
> Creators of the Garden with Insight(TM) garden simulator
> http://www.kurtz-fernhout.com
>
> Noel Welsh wrote:
> >
> > Paul Fernhout writes:
> > > On Numerical performance. This does appear to be an issue for further
> > > consideration. It looks like I would then need to improve this area
> > > myself
> > > (similar to the library for Gambit or NumPy for Python) if I was to use
> > > MzScheme for numerical work. Or alternatively, I could generate C code
> > > to do number crunching from Scheme with type hints. Either of these
> > > might be doable with a reasonable effort (perhaps leveraging off the
> > > approach done for say Python's NumPy) -- assuming the other parts of
> > > the system work well enough for my purposes.
> >
> > I've just looked at NumPy, and it appears that they've written some C
> > code to do the basic matrix operations in reasonable time, and then
> > interfaced to the Netlib (http://www.netlib.org/) libraries for all
> > the hard algorithms. You could certainly follow this approach in
> > MzScheme, and get respectable performance.
> >
> > More interesting is the second approach you mention - generating C
> > code with(out) type hints. I think almost all the basic research has
> > been done to get great numerical performance in Scheme. The following
> > pointers may help:
> >
> > - Andrew Wright's soft scheme system for infering types (no need for
> > type hints. See
> > http://www.intertrust.com/star/wright/personal-index.html) This would
> > be doubly useful if a distinction is made between fixnums and bignums
> >
> > - Unboxing of floats (e.g: http://www-fp.dcs.st-and.ac.uk/~kh/papers/pseudoknot/subsubsection3_5_6_4.html)
> >
> > - It should be possible to avoid most index out-of-bounds checks by
> > inducing the range of index variables. I don't know if anyone has done
> > this. I suppose it would require adding invariant properties to the
> > type system, so that the compiler could deduce any variable in the
> > range [0 (vector-length)) doesn't require an out-of-bounds check.
> >
> > Finally, I read somewhere that researchers in Aspect-Orientated
> > Programming (http://www.parc.xerox.com/csl/projects/aop/
> > http://www.acl.lanl.gov/iscope97/papers/lamping.html
> > http://www.diku.dk/research-groups/topps/activities/PartialEvaluation.html)
> > developed a system that collapsed operations on arrays into a single
> > loops. Eg, if one is doing something like Ax + b, the multiplication
> > and addition are collapsed into one loop without the programmer having
> > to write special purpose code. The good thing is, this work was
> > originally done in Scheme. "All are academic projects, with promising
> > results so far. The Scheme systems are the most mature."
> >
> > cya,
> > Noel
> > --
> > Noel Welsh
> > http://www.dai.ed.ac.uk/~noelw/ noelw@dai.ed.ac.uk