OT: Tackling NPhard problems - good languages?
Martin Young — 2006-04-26 09:51:43
Sorry for the OTness but I know there are some very clever folk on
this list who may also be involved in NP stuff and tackling them with
domain specific languages (or at least better suited languages than C++).
Anyway, I'm about to embark on a project that involves several
difficult problems, at least one of which is known NPcomplete and I
suspect the others are NPhard. I think that the exact problem doesn't
matter, I'll mention it anyway. The tasks involve optimised
placement, route finding (and optimisation) and a time sharing task
which is interwoven into the other two. The scale of the inputs mean
that finding the best solution is intracable so I'll be chasing a good
enough one using known heuristics and trying to develop some novel
ones of my own.
One might normally dig out a C++ compiler and start coding from the
ground up. However, I'm certain there must be a better language for
this kind of thing.
What I'm looking for is suggestions of languages to look at and
suggestions of where to go to read about and discuss them. I intend
to look at the usual functional suspects but my experience of the
functional programming world is that it's polarised between language
researchers and students with homework to do. Is there a good
itermediate level formum somebody could recommend?
I'm not above implementing a new language/runtime if necessary.
Thanks for any suggests. I'm more than happy to take this off-list to
avoid clogging up concat.
-Martin.
Joe Bowbeer — 2006-04-26 10:06:40
If you asked this 20 years ago I would have no reservations
recommending Scheme. It has always been a good language for creating
domain-specific languages.
But maybe there's a better option now..
On 4/26/06, Martin Young <martin@...> wrote:
> Sorry for the OTness but I know there are some very clever folk on
> this list who may also be involved in NP stuff and tackling them with
> domain specific languages (or at least better suited languages than C++).
>
> Anyway, I'm about to embark on a project that involves several
> difficult problems, at least one of which is known NPcomplete and I
> suspect the others are NPhard. I think that the exact problem doesn't
> matter, I'll mention it anyway. The tasks involve optimised
> placement, route finding (and optimisation) and a time sharing task
> which is interwoven into the other two. The scale of the inputs mean
> that finding the best solution is intracable so I'll be chasing a good
> enough one using known heuristics and trying to develop some novel
> ones of my own.
>
> One might normally dig out a C++ compiler and start coding from the
> ground up. However, I'm certain there must be a better language for
> this kind of thing.
>
> What I'm looking for is suggestions of languages to look at and
> suggestions of where to go to read about and discuss them. I intend
> to look at the usual functional suspects but my experience of the
> functional programming world is that it's polarised between language
> researchers and students with homework to do. Is there a good
> itermediate level formum somebody could recommend?
>
> I'm not above implementing a new language/runtime if necessary.
>
> Thanks for any suggests. I'm more than happy to take this off-list to
> avoid clogging up concat.
>
> -Martin.
>
sa@dfa.com — 2006-04-26 14:48:13
hi martin - welcome back.
i'm a little puzzled. why should NPness matter in the choice
of language? i can understand why one might care (or not)
about performance, terseness, library-availability, or other
features which a given application might require, but the
goals you list don't seem to pick out language-properties
in the same way.
you might want to look at jon harrop's OCAML for scientists
page here:
http://www.ffconsultancy.com
if you mention to him that i sent you his way he'll only
charge you double for his ocaml book. :)
and if you don't already know of J, you might want to check
that out:
http://www.jsoftware.com/
concatenative@yahoogroups.com wrote on 04/26/2006 05:51:43 AM:
> Sorry for the OTness but I know there are some very clever folk on
> this list who may also be involved in NP stuff and tackling them with
> domain specific languages (or at least better suited languages than C++).
>
> Anyway, I'm about to embark on a project that involves several
> difficult problems, at least one of which is known NPcomplete and I
> suspect the others are NPhard. I think that the exact problem doesn't
> matter, I'll mention it anyway. The tasks involve optimised
> placement, route finding (and optimisation) and a time sharing task
> which is interwoven into the other two. The scale of the inputs mean
> that finding the best solution is intracable so I'll be chasing a good
> enough one using known heuristics and trying to develop some novel
> ones of my own.
>
> One might normally dig out a C++ compiler and start coding from the
> ground up. However, I'm certain there must be a better language for
> this kind of thing.
>
> What I'm looking for is suggestions of languages to look at and
> suggestions of where to go to read about and discuss them. I intend
> to look at the usual functional suspects but my experience of the
> functional programming world is that it's polarised between language
> researchers and students with homework to do. Is there a good
> itermediate level formum somebody could recommend?
>
> I'm not above implementing a new language/runtime if necessary.
>
> Thanks for any suggests. I'm more than happy to take this off-list to
> avoid clogging up concat.
>
> -Martin.
>
>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
William Tanksley, Jr — 2006-04-28 01:20:42
Martin Young <
martin@...> wrote:
> Anyway, I'm about to embark on a project that involves several
> difficult problems, at least one of which is known NPcomplete and I
> suspect the others are NPhard. I think that the exact problem doesn't
> matter, I'll mention it anyway. The tasks involve optimised
> placement, route finding (and optimisation) and a time sharing task
> which is interwoven into the other two. The scale of the inputs mean
> that finding the best solution is intracable so I'll be chasing a good
> enough one using known heuristics and trying to develop some novel
> ones of my own.
Sounds like you need a language that you know well enough that it
doesn't get in your way. C++ is never that language (and I know it
pretty well). Python would be my choice for myself, because I know it
and it's dynamic enough to experiment with.
I don't think I'd bother learning a new language under those
circumstances. At most I'd learn a new API.
Just my always humble opinion.
> -Martin.
-Billy
stevan apter — 2006-04-28 01:55:57
or pick a language which has a subcommunity actively
involved in the application domain. so: lisp, scheme,
or one of the functional languages.
----- Original Message -----
From: William Tanksley, Jr
To: concatenative@yahoogroups.com
Sent: Thursday, April 27, 2006 9:20 PM
Subject: Re: [stack] OT: Tackling NPhard problems - good languages?
Martin Young <martin@...> wrote:
> Anyway, I'm about to embark on a project that involves several
> difficult problems, at least one of which is known NPcomplete and I
> suspect the others are NPhard. I think that the exact problem doesn't
> matter, I'll mention it anyway. The tasks involve optimised
> placement, route finding (and optimisation) and a time sharing task
> which is interwoven into the other two. The scale of the inputs mean
> that finding the best solution is intracable so I'll be chasing a good
> enough one using known heuristics and trying to develop some novel
> ones of my own.
Sounds like you need a language that you know well enough that it
doesn't get in your way. C++ is never that language (and I know it
pretty well). Python would be my choice for myself, because I know it
and it's dynamic enough to experiment with.
I don't think I'd bother learning a new language under those
circumstances. At most I'd learn a new API.
Just my always humble opinion.
> -Martin.
-Billy
Yahoo! Groups Links
[Non-text portions of this message have been removed]