Re: Verbose functional languages?

On Fri, 04 Jan 2008 19:46:21 +0100, Joachim Durchholz
<jo@xxxxxxxxxxxxx> wrote:

George Neuner schrieb:
- how to know when your type checking has failed. It's rather easy to
*** up an HM implementation so that it spins forever rather than
failing on pathological input and many people have tried to extend it
to cover their own notions of typing in ways that make the algorithm
unstable;

I may be underestimating the work involved here - but I always thought
that if you understand what HM does, it should be straightforward to
"see" whether a variation may terminate.

Unification is not conceptually difficult, but solving for the fixed
point of recursive unification can be tricky to implement. It's
fairly easy to accidently construct equations that will oscillate
rather than converge.


- how to relate typing problems back to the source;

Yes, that's indeed a problem.
Is there any knowledge how to do that reasonably well, for some value of
"reasonably well"?

Lots and lots of bookkeeping to record where the offending objects
were defined and where the incompatible references are in the source.

This is one particular task that explicit typing makes easier - you
only need to report at most the definition site and the site of the
current incompatible operation.

Type inference makes this much harder because, in general, you need to
look at all the operations on the object to decide the type. So are
incompatible operations/bindings/assignments an error or an indication
that the type is polymorphic? If you have two sets of operations
which are internally consistent but mutually inconsistent, what do you
report?

I'm personally not a great fan of type inferencing. As a compiler
writer (hobby), inference raises a lot of implementation issues. As a
programmer, I haven't really liked using any of the implementations
I've so far seen.

Of course, I grew up on simple static languages like C and Pascal and
then found Lisp. In practice Dylan's type system works closest to the
way my brain does - latent typing by default but explicit type
notations elide runtime checks wherever all the types in an expression
can be statically determined. But I dislike Dylan itself for other
reasons.

YMMV.


Their definition of "parallel" is different from mine. Their hooks
look ok for an interleaved (sequential) GC but not for one that truly
runs in parallel with the mutator(s). I would want to make use of
multiple cores as much as possible.

Speaking of multiple cores: when I look at what's Intel talking about,
it seems that CPUs with four, a dozen or hundreds of cores are less than
half a decade away.

Is there any known memory management scheme that would scale to such a
situation? Even memory allocation would create all kinds of mutual wait
conditions unless you use a separate memory pool per process, but then
you run into trouble when you want to transfer ownership of a block of
memory to another process.

I know of no shared scheme that can scale to large numbers of cores.
OTOH, there are a number of ideas that haven't been much explored
because of hardware limitations (large memories, processors/cores) on
the researchers.

I believe that any viable solution is going to involve private per
process/thread heaps. The problem is what to do with shared space if
there is to be any.

Just offhand, I think I would implement a large shared heap as
multiple treadmills with a separate large object space. Treadmills
are nice because they are non-moving and their use characteristics are
similar to Cheney collectors - constant time allocation, cheap write
barrier for parallel collection, marking and sweeping can be done
touching only the live objects in the heap, dead object recovery is a
constant time operation and with enough cores available each treadmill
could have its own GC thread. The only downside to treadmills is the
large block header (2 pointers), but memory is cheap and the impact
depends on the language - Lisp, for example, which uses conses like
crazy would be affected more than some other languages.

The large object space I am less certain about ... probably I would
use mark-sweep switching to mark-compact as the heap filled up.
Mark-compact is hard to do in parallel unless object access is
indirect, but the compiler could use heuristic locking to make that
acceptable.

I'm less convinced about general use of semi-space moving collectors
in a shared space with multiple mutators. Memory being cheap, I don't
care about taking some to support parallel collection, but I do care
about the impact on mutators of having to use indirect access all the
time. VMM solutions not involving indirection are, in general, not
portable and cause headaches and unpredictable access delays for
objects that span multiple pages. I am a fan of compiler directed
threading and I don't have a feel for how a VMM solution on multiple
cores would interact with that.

AFAIK, no one has come up with any really good solution involving
copying collectors. Mirroring collectors (Nettles, O'Toole, etc.)
have shown some promise, but IMO not enough research has been done on
them yet.

George
--
for email reply remove "/" from address
.