Re: RAD vs. performance

During development, you do it all the time.

You wouldn't use the full program compiler when you're developing.

Then what would you use?
The incremental compiler.

let map f a =
let l = length a in
if l = 0 then [||] else begin
let r = create l (f(unsafe_get a 0)) in
for i = 1 to l - 1 do
unsafe_set r i (f(unsafe_get a i))
done;
r
end

and here is List.map:

let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l

where is all of this commonality and code duplication?!

This is even worse than I thought. A map function only requires an
iterable object--whether or not the object is an array or list is
irrelevant. Specifically, in my language map looks like this (types
present for clarity):
[code]
def map(xs:iterable, f):
ret = []
for x in xs:
ret.append_ip(f(x))
return ret
[/code]

What is the type of this "map" function? In particular, how are the argument
and return types related?
They're not. I've already given this example before, but with all the
types shown it looks like this:

def map(xs:iterable('a), f:function('a)->any):
ret = []
for x in xs:
ret.append_ip(f(x))
return ret

As such, the type of 'map' is function(iterable('a),
function('a)->any)->[any]

(an iterable is any object with an 'iter' function, which returns an
iterator over the object; 'for' automatically handles all this)

That is completely wrong for OCaml. Appending to either arrays or lists is
O(n) in OCaml, so your map function would be O(n^2).
Regardless of performance, it shows that the same function can be used
for any sort of iterable container in my language. Either way, I'm not
sure how your judging the performance of my program (written in my
language, no less) based on the speed of OCaml's appending routine.
Actually, if you really wanted it to be fast you could do something
like this:

import array

def map(xs, f):
len = xs.len()
ret = array.create(len)
for i in [0..len]:
ret[i] = f(xs[i])
return ret

Assuming array.create allocates an array with the given size. This
function would work efficiently over _any_ iterable container. I think
this is probably closer to the first OCaml version for arrays, now that
I look at it.

It may not be immediately obvious, but the reason the two versions
above are different is solely because Array and lists don't expose the
same interface--namely, being able to deconstruct via the '::' operator
in pattern matching.

No. Arrays and lists are fundamentally different in OCaml and, consequently,
there is no commonality between most of their code. I say again, no code
duplication. The stdlib Array.map uses "make" and then "set", and List.map
uses decapitation and prepend.
Fundamentally different...except for the fact that they're both
sequential containers which can be iterated over?

note: this is assuming the array version isn't in-place. It doesn't
look like it, although it's not particularly easy to understand. If it
is in place, then you're comparing apples to oranges.

The array version is not in-place.
Ok, that's what I thought :)

Or, a real world example:
http://www.gamedev.net/community/forums/topic.asp?topic_id=401651

Before I start ranting, here is a solution:

module Make(Elt : sig
type t
val zero : t
val one : t
val ( ~: ) : t -> t
val ( +: ) : t -> t -> t
val ( -: ) : t -> t -> t
val ( *: ) : t -> t -> t
val sqrt : t -> t
end) = struct
type t = Elt.t list

open Elt
open List

let ( ~| ) = map ( ~: )
let ( +| ) = map2 ( +: )
let ( -| ) = map2 ( -: )
let ( *| ) s = map (( *: ) s)
let ( *.| ) = fold_left2 (fun t a b -> t +: a *: b) zero
let length2 r = r *.| r
let length r = sqrt(length2 r)
end;;
Ah, but I thought you said generic types weaken type checking?

Now, there are many problems with this:

1. It is not a "real world problem" but a specific solution. A real world
problem might be "write a working ray tracer".
It's a real world code reuse situation. You know, you write it once and
use it after that. I suppose that concept is kind of unfamiliar to
someone who uses OCaml, though ;)

2. Generalising over dimensionality weakens the static type checking. It
might be preferable to have different types for different dimensionalities.
Heh, not if you have dependant types. This is a great example where
having a poweful type system improves type checking:

data Vector:
elements:[number] where (x => x.len() == length)
length:number

def create_vector(elements):
return Vector(elements, elements.len())

Dependant types like that are generally relatively easy to check at
compile time.

Reading a profile is time consuming, even if we assume that your
profile will contain all of the type information that is required.

True. This wouldn't be necessary in the two serious solutions I
proposed.

It would if the types could not be inferred specifically enough.
Among other things, that's a very rare case. In fact, it'd be pretty
obvious when that's would increase speed, too.

This is a question of specificity. In ML, the factorial function has
the type int -> int and the type checker will unify this type with any
uses of this factorial function in order to type check the rest of the
program. A type-specific version in your language will have the same
type checking done. A type-generic (e.g. int | float) version in your
language can only have the same type checking guaranteed if whole
program analysis is used to examine every call site (monomorphisation).
Alternatively, you can type check the union type int|float but this is
weaker type checking (the type is not as specific) so it will not catch
as many bugs.

Do you have any examples of how it "weakens type checking"?

http://caml.inria.fr/pub/ml-archives/caml-list/2000/02/5851221420b7f01204e5ad638750e728.en.html
http://groups.google.com/group/comp.lang.functional/browse_thread/thread/f89de6bc7456c7d7/8fc976d8b306cc4c?lnk=raot

Hmm, so you're talking about the case when only one of the possible
value types is handled?

Specifically,
it would only happen when either 1) there's no way to optimise it,
period or 2) when the function is in a library and its usage isn't
known at compile time. The latter can be offset through the use of the
other method I posted.

Yes. So your abstraction has cost you fast and incremental compilation or
performance.
Neither of which are needed at the same time. Compile time doesn't
matter for the user and performance doesn't matter when you're not in
the optimisation phase.

As I've said, we don't do this to optimise our code, we do it to
statically check our code to remove more bugs. Over-abstracting is
every bit as bad as premature optimisation. People just haven't
realised it yet...

Only in the sense that over-abstraction is needless abstraction.
Over-abstraction doesn't apply to libraries, since it's impossible to
know what people will or will not need.

Of course it applies to libraries! It is not in our best interests to write
libraries that are abstracted in every possible way. Each abstraction you
add takes time, costs code (and probably money) making things slower to
compile and run, harder to learn and harder to use.
It doesn't take time or code if it's done automatically, and it doesn't
make things slower when it matters. It most certainly doesn't make it
harder to learn or use--probably the exact opposite.

If you try advocating abstractions that aren't going to be used
How do you know they're not going to be used?

but cost you
static checking then any ML advocate will tell you to stick your
abstraction up your whole program optimising compiler.
Heh. I guess it's a good thing I'm not trying to attract ML advocates
with my language ;)

Do you agree that the following polymorphic variants are ordered with the
most specific types appearing first:

[`Int]
[<`Int|`Float]
[`Int|`Float]
[>`Int|`Float]
No, although I don't know what the > and < syntax is for. It depends on
the situation.

.

Relevant Pages

  • Re: parameter speed
    ... With array constructors you can make something pretty close ... compile time as such... ... to get better at processing constant expressions, ...
    (comp.lang.fortran)
  • Re: .class and Class.forName
    ... Class, which attempts to find, and if necessary load, the named class at ... checked at compile time, but when invoked the method forces the class to ... array objects do not actually have a field named length. ...
    (comp.lang.java.programmer)
  • Re: Copying an array slice (Was: Re: Difficulties with passing multi-dimensional arrays)
    ... > the pointer to array of unknown size. ... but it still compiles without a cast. ... unknown at compile time so nothing can be checked. ...
    (comp.lang.c)
  • Re: Use of getchar
    ... "Cam" wrote in message ... I do this by calling a KeyboardInput() function ... > key2 array as if the user had entered them. ... compileable code, i.e., compile it yourself and then copy and paste it ...
    (comp.lang.cpp)
  • Re: Polymorphism in C (very basic)
    ... GPS data comes in once per second. ... There are about 60 measurements in total. ... >> allocated at compile time. ... The index to the array provides a very fast ...
    (comp.lang.c)