[Caml-list] More or bignums/ints

[Caml-list] More or bignums/ints

[John Hughes]

I've read the May interchange in CWN that started with the question

> I have made a web search to understand which kind of support for 
> bignums is available for OCaml...

and found it interesting. I'll be teaching a few weeks of ML as part 
of a first-year course at Brown University, and we've used SML in 
previous years. SML/NJ works OK, but we'd like a debugger, so I've 
looked at OCaml as a possible alternative. I was a little depressed 
to find (by trial and error) that "int" doesn't mean "integer" but 
rather "element of Z/nZ for some very large n, represented with 
integer notation, including negative signs." 

I think I can live with this if only there's some way to write 
something like this (pseudo-ML/Java):

fun fact(0) = 1
  | fact(n) = try {
                 n * fact(n-1)
              }
              catch (IntegerOverflow e) ...


What I don't think I can bear is to use the sorts of "bignum"-like 
libraries that make me write things like

 y = x bigadd big-unit

to mean 

 y = x + 1

because our students will actually be writing some code that has 
a good deal of arithmetic in it. 

---

So the questions are

1. Is there a way to catch overflow exceptions within an entire 
   computation?
2. Is there a way to tell OCaml that ints really are either 
   (a) bignums or
   (b) overflow-protected ints (as in SML/NJ, for instance)

Perhaps the implicit third question is

3. Is there a reasonable debugger for some dialect of ML that has 
what I might call "protected integers"? 

Thanks very much in advance. 

-John Hughes

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Jacques Garrigue]

From: "John Hughes" <jfh@cs.brown.edu>
> So the questions are
> 
> 1. Is there a way to catch overflow exceptions within an entire 
>    computation?

Not that I know of.

> 2. Is there a way to tell OCaml that ints really are either 
>    (a) bignums or
>    (b) overflow-protected ints (as in SML/NJ, for instance)

No. Old Caml had (a), but this is more than 10 years ago.
Note however that you may redefine operators if you want to:

exception Int_overflow

let (+) a b =
  let c = Pervasives.(+) a b in
  if a < 0 && b < 0 && c >= 0 || a > 0 && b > 0 && c <= 0
  then raise Int_overflow;
  c

This is going to be pretty slow, but if this is for beginners this
shouldn't matter too much.
And it won't change the behaviour of other operations in the library,
but you don't want to: they may depend on the rollover behaviour.

> Perhaps the implicit third question is
> 
> 3. Is there a reasonable debugger for some dialect of ML that has 
> what I might call "protected integers"? 

I don't know, but it should be possible to hack ocamlrun to check for
overflows. Combined with C primitives, you could also set whether an
exception should be raise or not.
A bit more painful than the above approach, but this should run
faster.

Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Brian Hurt]

On Fri, 11 Jun 2004, John Hughes wrote:

> I've read the May interchange in CWN that started with the question
> 
> > I have made a web search to understand which kind of support for 
> > bignums is available for OCaml...
> 
> and found it interesting. I'll be teaching a few weeks of ML as part 
> of a first-year course at Brown University, and we've used SML in 
> previous years. SML/NJ works OK, but we'd like a debugger, so I've 
> looked at OCaml as a possible alternative. I was a little depressed 
> to find (by trial and error) that "int" doesn't mean "integer" but 
> rather "element of Z/nZ for some very large n, represented with 
> integer notation, including negative signs." 

Yep.  Generally mod 2^n for some n.  This is because this is what the 
hardware supplies for fast integer arithemetic.  "Fixing" this, so that 
ints are real (mathematical) integers entails a *huge* performance cost, 
for very little gain.

> 
> I think I can live with this if only there's some way to write 
> something like this (pseudo-ML/Java):
> 
> fun fact(0) = 1
>   | fact(n) = try {
>                  n * fact(n-1)
>               }
>               catch (IntegerOverflow e) ...
> 

There are two problems with this: 1) most CPUs don't support throwing 
exceptions on integer overflows, because 2) the CPU throwing an exception 
is incredibly expensive (two complete pipeline drains (the same cost as a 
mispredicted branch), and two task switches (into and back out of the 
OS)).  

You might be able to modify the ocaml compiler to add overflow checking 
code.  Most CPUs have a "jump on overflow" instruction.  But currently, an 
integer add takes at most 2 instructions (the second instruction to deal 
with the tag bit), and often only one.  This change would cause an add 
instruction to take at least two, maybe three, instructons- for a 
signifigant performance hit (this is assuming that the throwing the 
exception code is factored out).

How big of a performance hit, I don't know.  I note that on the Great 
Language Shootout page, SML/NJ has a much lower performance score than 
Ocaml or MLton.

Note that the numeric people have exactly the same problem, and are more 
likely to hit it than your average code.

> 
> What I don't think I can bear is to use the sorts of "bignum"-like 
> libraries that make me write things like
> 
>  y = x bigadd big-unit
> 
> to mean 
> 
>  y = x + 1
> 
> because our students will actually be writing some code that has 
> a good deal of arithmetic in it. 

Define new operators.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Xavier Leroy]

Dear John,

> 1. Is there a way to catch overflow exceptions within an entire 
>    computation?
> 2. Is there a way to tell OCaml that ints really are either 
>    (a) bignums or
>    (b) overflow-protected ints (as in SML/NJ, for instance)

Solution (a) is problematic because of literals.  It's easy to
redefine the infix `+' operator to mean "bignum addition", and
similarly for other arithmetic operators, but OCaml has no syntax for
bignum literals, e.g. to get the bignum 123 one needs to type
Int 123 or num_of_string "123".  A Camlp4 syntax extension could
possibly do the job, however.

Solution (b) is much easier, provided you don't care much for
performance (probably true for an intro course).  Stick the following
definitions in, say, CS101.ml

  exception Overflow

  let ( + ) a b =
    let c = a + b in
    if (a lxor b) lor (a lxor (lnot c)) < 0 then c else raise Overflow

  let ( - ) a b =
    let c = a - b in
    if (a lxor (lnot b)) lor (b lxor c) < 0 then c else raise Overflow

  let ( * ) a b =
    let c = a * b in
    if Int64.of_int c = Int64.mul (Int64.of_int a) (Int64.of_int b)
    then c else raise Overflow

  let ( / ) a b =
    if a = min_int && b = -1 then raise Overflow else a / b

[Note that the definition of ( * ) above assumes a 32-bit processor.
 Something even less efficient is required to work both on 32- and 64-bit
 architectures.]

Compile this source to CS101.cmo and make sure that the module CS101 is
linked and opened in the students' code.  For instance, with the
interactive toplevel loop, make them stick

   #load "/path/to/CS101.cmo";;
   #directory "/path/to";;
   open CS101;;

in $HOME/.ocamlinit, and voila, every time they start ocaml, they get
overflow-protected integers.

Don't even think of modifying the OCaml bytecode interpreter so that
the arithmetic operations of the abstract machine perform overflow
detection: some code in the standard library and the compilers rely on
modulo arithmetic.

Hope this helps,

- Xavier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Andreas Rossberg]

Brian Hurt wrote:
> 
>>I was a little depressed 
>>to find (by trial and error) that "int" doesn't mean "integer" but 
>>rather "element of Z/nZ for some very large n, represented with 
>>integer notation, including negative signs." 
> 
> Yep.  Generally mod 2^n for some n.  This is because this is what the 
> hardware supplies for fast integer arithemetic.  "Fixing" this, so that 
> ints are real (mathematical) integers entails a *huge* performance cost, 
> for very little gain.

I believe it is not too significant for most applications. And it could 
easily be subject to the no-bound-checks compiler switch, to satisfy 
performance junkies and number crunchers.

> How big of a performance hit, I don't know.  I note that on the Great 
> Language Shootout page, SML/NJ has a much lower performance score than 
> Ocaml or MLton.

Note that MLton also implements overflow checks, because they are 
required by the SML language/library specification.

Cheers,

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

Let's get rid of those possible thingies!  -- TB

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Brian Hurt]

On Fri, 11 Jun 2004, John Hughes wrote:

> I've read the May interchange in CWN that started with the question
> 
> > I have made a web search to understand which kind of support for 
> > bignums is available for OCaml...
> 
> and found it interesting. I'll be teaching a few weeks of ML as part 
> of a first-year course at Brown University, and we've used SML in 
> previous years. 

By the way, how well does this work?  Just out of curiosity.

I've never taught beginning anything to anyone, so I know diddly squat 
about about what works and what doesn't work.  That said, I think I'd 
rather teach Ocaml as a first language than either C++ or Java, but I 
think Scheme might be an even better language than Ocaml as a first 
language.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Brian Hurt]

On Tue, 15 Jun 2004, Brian Hurt wrote:

Something that shouldn't have gone to the main list.  Sorry 'bout that.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] More or bignums/ints

[Manos Renieris]

I think you also need 

    let ( ~- ) x = if x <> min_int then -x else raise Overflow

(~- is unary minus, commonly typed in as "-")

You still get
    -1073741824=1073741824
being true if you type in the exact literals. I think fixing this
requires tweaking the parser.

-- Manos

On Mon, Jun 14, 2004 at 05:55:52PM +0200, Xavier Leroy wrote:
> Dear John,
> 
> > 2. Is there a way to tell OCaml that ints really are either 
> >    (a) bignums or
> >    (b) overflow-protected ints (as in SML/NJ, for instance)
> 
> Solution (b) is much easier, provided you don't care much for
> performance (probably true for an intro course).  Stick the following
> definitions in, say, CS101.ml
> 
>   exception Overflow
> 
>   let ( + ) a b =
>     let c = a + b in
>     if (a lxor b) lor (a lxor (lnot c)) < 0 then c else raise Overflow
> ...

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] More or bignums/ints

[John Hughes]

Brian Hurt asked "How well does teaching ML in a first course work?"

To tell the truth, we teach Scheme for about 7 weeks, then 4.5 weeks
of 
ML, and then, in Spring, teach Java. Both Scheme and ML are taught 
purely-functionally: there's no "set!" in our world. The idea is to
teach them
  
* to think algorithmically
* to be able to analyze the big-O performance of their programs
* to know some basic structures like lists and trees, and even BSTs

For that, pure-functional is just fine. ML's structures and functors
give them a nice transition point towards OO programming: they start
to 
gather data and operations together, and they learn some data hiding
with
opaque signatures. By the time they reach Java, they're sophisticated
enough to complain appropriately: "You mean I can't just pass a
function
as an argument to another function? Why do I have to write a stupid
wrapper
around the Java container classes to get a safe CarList or a
TruckList? Why
isn't there appropriate polymorphism?" [OK, maybe they don't remember
that
it's called polymorphism, but they know that they want it...]

How well does it work? Well, the next year they end up in the same
courses 
as their friends who took a "program in Java" course first, and a
"data
structures and algorithms" course second. The average scores for the
two groups in the big software-engineering course are pretty much 
indistinguishable. Not surprisingly, the ones in OUR course do better
in the programming languages course in general. And lots of our
success
stories are with students who have never touched a computer before,
except
for email and Microsoft Word, so I think we're doing OK. 

Thanks again, to everyone here, for the suggestions on getting "safe"
integers into OCaml. I'm more or less committed to doing what was
suggested and redefining all the standard operations in some CS17.ml
"library" that's preloaded for them (after I show them the dark
underbelly of OCaml in which integer operations are silently 
incorrect <as operations on integers, I mean>). 

--John Hughes

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] More or bignums/ints

[skaller]

On Wed, 2004-06-23 at 20:50, John Hughes wrote:

>  The average scores for the
> two groups in the big software-engineering course are pretty much 
> indistinguishable. 

Do you have any comment as to why this might be?

Wouldn't you expect stronger concepts of abstraction
developed by starting with FP to be useful in 
a programming-in-the-large situation?

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners