MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Eijiro Sumii]

Hi,

I have implemented a simple but efficient compiler from a tiny ML
subset to the SPARC assembly language.

  http://min-caml.sourceforge.net/min-caml.tar.gz

The primary purpose is advanced education: the compiler is well
documented (only in Japanese for now, unfortunately)

  http://min-caml.sourceforge.net/

and has been used in a class at Tokyo for years.

The compiler consists of only 2000 lines of OCaml.  Yet, it produces
as efficient SPARC code as OCaml and GCC does (for the tiny ML subset
and equivalent C programs).

  A typical functional program (Ackermann):

    GCC 6.8s
    OCaml 0.9s
    MinCaml 0.9s

  A typical imperative program (raytracing):

    GCC 14.7s
    OCaml 36.7s (could perhaps be improved by using BigArray)
    MinCaml 17.0s

So, please take a look if you are interested.  Even if you don't
understand Japanese, you may be able to understand OCaml!:-)

Best,

--
Eijiro Sumii (http://www.cis.upenn.edu/~sumii/)
Department of Computer and Information Science, University of Pennsylvania

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Jon Harrop]

On Thursday 03 March 2005 22:26, Eijiro Sumii wrote:
> I have implemented a simple but efficient compiler from a tiny ML
> subset to the SPARC assembly language.
>
>   http://min-caml.sourceforge.net/min-caml.tar.gz
>
> The primary purpose is advanced education:

I think this is an absolutely fantastic project!

A tiny ML compiler would have helped me to learn how to write ML compilers and 
interpreters when I decided to study this. I had a go at writing my own but 
it will take a lot more practise before I am good enough. I think this 
project could help a lot of people.

> Yet, it produces as efficient SPARC code as OCaml and GCC does

Did you choose SPARC because of availability or for technical reasons?

> for the tiny ML subset and equivalent C programs).

What features of ML are implemented?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Eijiro Sumii]

From: "Jon Harrop" <jon@jdh30.plus.com>
> > Yet, it produces as efficient SPARC code as OCaml and GCC does
> 
> Did you choose SPARC because of availability or for technical reasons?

Both - Sun is still strong in universities around me and IA-32 is a
mess (for me, at least) compared to RISC...

> > for the tiny ML subset and equivalent C programs).
> 
> What features of ML are implemented?

Only a _very_ tiny subset: for now, it does not have polymorphism,
data types, modules, nor garbage collection (so I shouldn't even call
it ML, except that the syntax is a subset of OCaml).  However, it
_does_ have type inference, higher-order functions, floating-point
numbers, tuples, and arrays with destructive update - which are
sufficient for minimal examples (such as gcd, ack, matrix, etc.)  and
one application (raytracing).  Also, it does implement optimizations
such as known-function calls, tail calls, inlining, constant folding,
etc.  It can call external functions if you provide the stubs in
assembly.

The subset is so tiny because MinCaml was developed for an
undergraduate course, where I put most energy to the ease of
understanding and couldn't include many features.  However, adding
them would be a nice project for more advanced students.

By the way, for the majority of people who do not speak Japanese:-), I
am preparing an Enlish documentation.

--
Eijiro Sumii (http://www.cis.upenn.edu/~sumii/)
Department of Computer and Information Science, University of Pennsylvania

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Eijiro Sumii]

From: Eijiro Sumii <eijiro_sumii@anet.ne.jp>
> By the way, for the majority of people who do not speak Japanese:-), I
> am preparing an Enlish documentation.

P.S.  For the moment, I found Babelfish

  http://babelfish.altavista.com/

does a modest job of translting the project page

  http://min-caml.sourceforge.net/

to some extent.

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Jon Harrop]

On Saturday 05 March 2005 14:37, Eijiro Sumii wrote:
> From: "Jon Harrop" <jon@jdh30.plus.com>
> > Did you choose SPARC because of availability or for technical reasons?
>
> Both - Sun is still strong in universities around me and IA-32 is a
> mess (for me, at least) compared to RISC...

Yes indeed! :-)

Are you interested in commercialising this project? I think that many 
companies would be interested in a mini compiler which they could customise 
themselves, e.g. to create JIT compilers, or to have a decent embedded 
language.

Obviously this would require more work but I do not believe it would take 
someone (suitably talented, such as yourself) very long.

> > What features of ML are implemented?
>
> Only a _very_ tiny subset: for now, it does not have polymorphism,
> data types, modules, nor garbage collection (so I shouldn't even call
> it ML, except that the syntax is a subset of OCaml).  However, it
> _does_ have type inference,

I'd prioritise data types next, and pattern matching (of course) if that is 
not implemented already.

> higher-order functions, floating-point 
> numbers, tuples, and arrays with destructive update - which are
> sufficient for minimal examples (such as gcd, ack, matrix, etc.)  and
> one application (raytracing).

Amazing!

> The subset is so tiny because MinCaml was developed for an
> undergraduate course, where I put most energy to the ease of
> understanding and couldn't include many features.  However, adding
> them would be a nice project for more advanced students.

Might I suggest an OCaml byte-code back end? Then you could "borrow" the OCaml 
GC.

> By the way, for the majority of people who do not speak Japanese:-), I
> am preparing an Enlish documentation.

Marvellous, thank you. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

MinCaml English Documentation

[Eijiro Sumii]

Hi All,

I've uploaded a (rather quick) translation of my MinCaml compiler
tutorial:

  http://min-caml.sourceforge.net/index-e.html

It should be readable enough, though I'm not a very good English
writer (and some comments in the source code are still in Japanese).

Comments are welcome.  I don't have so much experience even in
compiler development (unlike Xavier and other real experts here).

From: "Jon Harrop" <jon@jdh30.plus.com>
> Are you interested in commercialising this project? I think that many 
> companies would be interested in a mini compiler which they could customise 
> themselves, e.g. to create JIT compilers, or to have a decent embedded 
> language.

I'm not sure if MinCaml by itself can make any money:-) but I've
always been wondering if it is possible to sell the "programming
language processing technology" (which is the killer application of
ML).  I heard Galois Connection has been doing something like that by
using Haskell, focusing on security in particular.

> I'd prioritise data types next, and pattern matching (of course) if that is 
> not implemented already.

I agree.  In fact, I'm looking for a good (as simple and efficient as
possible) algorithm of pattern matching.  Any suggestions, anyone?

> Might I suggest an OCaml byte-code back end? Then you could "borrow" the OCaml 
> GC.

Actually, I feel a little reluctant to use byte code in the back end,
because (for the original educational purpose) it hides some important
details - such as garbage collection!  On the other hand, if
supporting (not teaching) GC is important, I believe Boem's GC does a
good job even though it is conservative.

--
Eijiro Sumii (http://www.cis.upenn.edu/~sumii/)
Department of Computer and Information Science, University of Pennsylvania

Re: MinCaml English Documentation

[Jon Harrop]

On Tuesday 08 March 2005 03:01, Eijiro Sumii wrote:
> I've uploaded a (rather quick) translation of my MinCaml compiler
> tutorial:
>
>   http://min-caml.sourceforge.net/index-e.html

Fantastic, thank you!

> From: "Jon Harrop" <jon@jdh30.plus.com>
> I'm not sure if MinCaml by itself can make any money:-) but I've
> always been wondering if it is possible to sell the "programming
> language processing technology" (which is the killer application of
> ML).  I heard Galois Connection has been doing something like that by
> using Haskell, focusing on security in particular.

I think companies would be willing to spend a bit of money (~1000UKP) to buy a 
working shell of a compiler so that they could develop it however they 
wanted. If our company could afford a copy (and it was more complete) then we 
would use it to develop a custom language for graphics programming. An 
interpreter might also be commercially viable.

> Actually, I feel a little reluctant to use byte code in the back end,
> because (for the original educational purpose) it hides some important
> details - such as garbage collection!

Yes, ideally you want an elegant demo GC. But isn't having a hidden GC 
preferable to having no GC? Using an existing byte-code is probably also the 
most preferable way to make your compiler cross-platform, short of writing 
multiple assembler back-ends. Another option is C-- or maybe Java bytecode. 
From what I hear, C-- is stable enough now.

You could always write a demo OCaml-compatible GC in OCaml for educational 
purposes. Then people could use whichever GC they wanted.

> On the other hand, if 
> supporting (not teaching) GC is important, I believe Boem's GC does a
> good job even though it is conservative.

IMHO, Boem's GC would put people off. As OCaml's GC is already available, 
efficient and non-conservative, I'd go for that.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] MinCaml English Documentation

[Ken Friis Larsen]

Eijiro Sumii wrote:
> I agree.  In fact, I'm looking for a good (as simple and efficient as
> possible) algorithm of pattern matching.  Any suggestions, anyone?

Peter Sestoft has a nice paper about pattern matching:
	 "ML pattern match compilation and partial evaluation"
           In Danvy, Glück, and Thiemann (editors): Partial Evaluation.
           Dagstuhl Castle, Germany, February 1996.
           Lecture Notes in Computer Science, vol. 1110, pages 446-464.
           Springer-Verlag 1996
	  http://www.dina.kvl.dk/~sestoft/papers/match.ps.gz

Easy to follow and it has a nice trade-off between simplicity and efficiency.


Cheers,

--Ken Friis Larsen

Re: [Caml-list] MinCaml English Documentation

[David MENTRE]

Hello,

First of all, a big thank to you for releasing your mini-caml compiler
under a free license. I always wanted to dive into Caml compiler
intricacies but was feared by its size. The size of MinCaml makes
possible to study it.

Eijiro Sumii <eijiro_sumii@anet.ne.jp> writes:

> I've uploaded a (rather quick) translation of my MinCaml compiler
> tutorial:
>
>   http://min-caml.sourceforge.net/index-e.html

I noticed that the different english comment are available as different
pages (1->N).

  http://min-caml.sourceforge.net/tutorial-mincaml-1.eng.htm

Do you have all of them in the same file ? (otherwise I'll just play
with wget :)

>> I'd prioritise data types next, and pattern matching (of course) if that is 
>> not implemented already.

I would also like to have a GC in addition of data types and pattern
matching. 

Depending on wether you want to teach GC or just use it, either we could
write one or use OCaml's one.

Yours,
d.
-- 
pub  1024D/A3AD7A2A 2004-10-03 David MENTRE <dmentre@linux-france.org>
 5996 CC46 4612 9CA4 3562  D7AC 6C67 9E96 A3AD 7A2A

Re: [Caml-list] MinCaml English Documentation

[Eijiro Sumii]

From: David MENTRE <dmentre@linux-france.org>
> I noticed that the different english comment are available as different
> pages (1->N).
> 
>   http://min-caml.sourceforge.net/tutorial-mincaml-1.eng.htm
> 
> Do you have all of them in the same file ? (otherwise I'll just play
> with wget :)

Please use recursive wget for the moment.  Something like

  wget --timestamping --quota=100m --no-parent --recursive --convert-links --level 0 http://min-caml.sourceforge.net/

will mirror the whole site (which is less than 2MB in total).

I've created these pages by "sanitizing" Word-generated HTML with
DreamWeaver, and it's too much pain to manage many versions of the
same document.  Sorry...!

> I would also like to have a GC in addition of data types and pattern
> matching. 
> 
> Depending on wether you want to teach GC or just use it, either we could
> write one or use OCaml's one.

OK, I'll try to include data types, pattern matching, and some GC in
the next major release.  (It may take a little time, though, since I'm
getting rather overloaded this month...:-)

	Eijiro

Re: [Caml-list] MinCaml English Documentation

[Xavier Leroy]

> In fact, I'm looking for a good (as simple and efficient as
> possible) algorithm of pattern matching.  Any suggestions, anyone?

There are hard trade-offs between simplicity, execution speed and
size of generated code.  However, the compilation scheme I used in
Caml Light is a reasonable starting point.  It was inspired by
Phil Wadler's chapter in Simon Peyton Jones's book "The implementation of
functional programming languages" (out of print, but a scanned version
is available from SPJ's Web page), and described in details in the
"ZINC report", http://pauillac.inria.fr/~xleroy/publi/ZINC.ps.gz

Luc Maranget has some papers describing much more sophisticated
approaches used in the OCaml compiler, if you find so inclined.

- Xavier Leroy

Re: [Caml-list] MinCaml English Documentation

[Eijiro Sumii]

From: "Xavier Leroy" <Xavier.Leroy@inria.fr>
> There are hard trade-offs between simplicity, execution speed and
> size of generated code.  However, the compilation scheme I used in
> Caml Light is a reasonable starting point.  It was inspired by
> Phil Wadler's chapter in Simon Peyton Jones's book "The implementation of
> functional programming languages" (out of print, but a scanned version
> is available from SPJ's Web page), and described in details in the
> "ZINC report", http://pauillac.inria.fr/~xleroy/publi/ZINC.ps.gz
> 
> Luc Maranget has some papers describing much more sophisticated
> approaches used in the OCaml compiler, if you find so inclined.

Thanks a lot for the references - and yes, that reminds me what I
forgot to mention:

If anybody is interested in a compiler of the complexity "between"
OCaml and MinCaml (and generating byte code or C), it may be good to
take a look at Caml Light, Camlot, or Bigloo.

  http://caml.inria.fr/distrib-caml-light-eng.html

--
Eijiro Sumii (http://www.cis.upenn.edu/~sumii/)
Department of Computer and Information Science, University of Pennsylvania

Looking for an efficient implementation of simply typed lambda calculus

[Sébastien Hinderer]

Dear all,

Has some library been developed to handle simply typed lambda terms ?
The library should be able to build and reduce terms, in a
computationally efficient way.

If you are aware of such a work, many thanks for letting me know.

Cheers,
Sébastien.

Re: [Caml-list] Looking for an efficient implementation of simply typed lambda calculus

[Manos Renieris]

I don't know about the efficiency, but Benjamin Pierce's book
comes with implementations, which include the simply typed lambda
calculus.

http://www.cis.upenn.edu/~bcpierce/tapl/index.html

On Mon, Mar 14, 2005 at 06:31:27PM +0100, S?bastien Hinderer wrote:
> Dear all,
> 
> Has some library been developed to handle simply typed lambda terms ?
> The library should be able to build and reduce terms, in a
> computationally efficient way.
> 
> If you are aware of such a work, many thanks for letting me know.
> 
> Cheers,
> S?bastien.
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Corey O'Connor]

On Thu, 03 Mar 2005 17:26:52 -0500 (EST), Eijiro Sumii
<eijiro_sumii@anet.ne.jp> wrote:
> Hi,
> 
> I have implemented a simple but efficient compiler from a tiny ML
> subset to the SPARC assembly language.
> 
>   http://min-caml.sourceforge.net/min-caml.tar.gz
> 
> The primary purpose is advanced education: the compiler is well
> documented (only in Japanese for now, unfortunately)
> 
>   http://min-caml.sourceforge.net/
> 
> and has been used in a class at Tokyo for years.

Neat! I've started studying compilers for functional languages and
japanese. I'm sure this will be very useful for both my studies. :-)
Thanks!

-Corey O'Connor

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Oliver Bandel]

On Thu, Mar 03, 2005 at 05:26:52PM -0500, Eijiro Sumii wrote:
> Hi,
> 
> I have implemented a simple but efficient compiler from a tiny ML
> subset to the SPARC assembly language.
> 
>   http://min-caml.sourceforge.net/min-caml.tar.gz

Wow, thanks.

> 
> The primary purpose is advanced education: the compiler is well
> documented (only in Japanese for now, unfortunately)

OK, that's good for getting some impression on using ocamlyac too.


[...]
> So, please take a look if you are interested.  Even if you don't
> understand Japanese, you may be able to understand OCaml!:-)

Well, just some weeks ago I started learning japanese.
So, I can read hiragana (not fluently, but with some work...)
but that only is a small part.
But so your project is good for learning japanese language too,
not only in exploring ocaml-programming/ocamlyacc-usage.



Regards,
    Oliver


P.S.: I'm looking for free fonts (postscript-fonts, if possible) for
      hiragana/katkana/kanji.  Can you give me a hint, where to find
      it?! Thanks...

Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Eijiro Sumii]

From: "Oliver Bandel" <oliver@first.in-berlin.de>
> P.S.: I'm looking for free fonts (postscript-fonts, if possible) for
>       hiragana/katkana/kanji.  Can you give me a hint, where to find
>       it?! Thanks...

I'm not an expert here (and it's a little off-topic for caml-list) but
many distributions of UNIX-like OS (as well as recent versions of
Windows and Mac OS) have standard packages of Japanese fonts.  Perhaps
you can look at the package manager of your OS distrubition, or google
"free Japanese fonts" _together with_ the name of your OS
distribution.

	Eijiro

OT: Re: [Caml-list] MinCaml: an educational compiler for tiny ML subset (documented in Japanese)

[Richard Jones]

On Thu, Mar 03, 2005 at 05:26:52PM -0500, Eijiro Sumii wrote:
> So, please take a look if you are interested.  Even if you don't
> understand Japanese, you may be able to understand OCaml!:-)

This is a very good site which adds hints to Japanese web pages:

http://www.popjisyo.com/WebHint/Portal_e.aspx

For example, the min-caml site rendered using this tool:

http://tinyurl.com/55zxf

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com