# 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]