Feed aggregator
Jose Antonio Ortega: At the workshop
I just came back from the Scheme and Functional Programming Workshop at Montréal, hosted by Marc Feeley and an excellent organisation team. It’s been a fun couple of days putting faces to emails and IRC nicks and attending a handful of pretty interesting talks. Here’s a quick report.
My favourites were the two invited papers. The first day, Olin Shivers presented a pretty cool hack in a delicious talk consisting in actually writing the code he was explaining. Under the title Eager parsing and user interaction with call/cc, he showed us how call/cc is not just an academic toy, but can be put to good use in writing a self-correcting reader for s-expressions on top of the host scheme read (or any other parser, for that matter). He started from the very basics, explaining how input handling and buffering is usually delegated to the terminal driver, which offers a rather dumb, line-oriented service. Wouldn’t it be nice if, as soon as you typed an invalid character (say, a misplaced close paren) the reader complained, before waiting for the whole line to be submitted to read? Well, all we need to do is to implement the input driver in scheme, and he proceeded to show us how. As you know, reading s-expressions is a recursive task, meaning that when you detect invalid input in the middle of a partial s-expression, or want to delete a character, you might find yourself somewhere deep inside a stack of recursive calls and you’ll need to backtrack to a previous checkpoint. That’s an almost canonical use case for call/cc, provided you use it intelligently. Let me tell you that Olin is quite capable of using call/cc as it’s meant to be used, as he immediately demonstrated. I’m skipping the details in the hope that a paper will be available any time soon. As i mentioned, his talk was a beautiful example of live coding: he showed us the skeleton of the implementation and filled it up as he explained how it should work. Olin does know how to write good code, and it was a pleasure (and a lesson) seeing him doing just that. It was all so schemish: a terminal and emacs in the venerable twm: that’s all you need to create beauty.
The second invited talk was by Robby Findler, who gave us a tour of Racket’s contract system, how to use it and the subtleties of implementing it properly. The basic idea dates back to Meyer’s design by contract methodology of the early nineties, and was subsequently explored further by several authors, including Robby. Simple as they sound at first sight, good contracts are not trivial to implement. For instance, it’s vital to assign blame where’s blame is due, and Robby gave examples of how tricky that can get (and how Racket’s contracts do the right thing). Another subtlety arises when you try to write contracts assessing a property of an input data structure (say, you want to ensure that an argument is actually a binary search tree). The problem here is that checking the contract can alter the asymptotic complexity of the wrapped function (e.g., you can go from O(log n) to O(n) in a lookup, an exponential degradation). Racket provides an ingenious fix for that problem, by means of lazy contracts that are checked as the input is traversed by the “real” function.
There was also real-time scheme in Robby’s talk, although in a much more sophisticated way, thanks to Slideshow’s magic, which lets you embed code files and snippets in a presentation, evaluate them and show the results in the same or a new slide. Very elegant. He also used DrRacket a bit during the introductory part of his talk, and i’m starting to understand why some people are so happy with Racket’s IDE: it definitely felt, in his hands, professional and productive. And also kind of fun.
There were also lightning talks. I’m of course biased, but the one i enjoyed most was Andy Wingo’s Guile is OK!, where he showed us how Guile has overcome the problems, perceptual and real, of its first dozen years. For instance, he reminded us how Guile was traditionally a “defmacro scheme”, and he himself a “defmacro guy”… until he studied in earnest Dyvbig’s work and ported his syntax-case implementation to Guile, to become a “syntax-case man” as Guile gained full syntax-case support (i hope i’ll reach that nirvana some day; i still find syntax-case too complex and plagued by unintuitive corner cases (one of them was showed by Aaron Hsu in another lightning talk, where apparently none of us was able to correctly interpret 10 lines of scheme) that make me uneasy; but that’s surely just ignorance on my part). There are many other things that make Guile a respectable citizen of the Scheme Underground, which were also listed in Andy’s talk: i’ll ask him for a PDF, but in the meantime you can just try Guile and see :).
Although this time we didn’t have a talk by Will Clinger, to me it’s always a pleasure to listen to what he has to say, even if only as comments to other people’s talks. For instance, i enjoyed his introduction to Alex Shinn’s R7RS progress report. Will showed us three one dollar coins, of the same size and shape, but different, as he described, in almost everything else. And yet, all three were useful and recognised as (invalid) dollars by the Canadian vending machines at the entrance. He thinks that says something about standards, but he left to us to decide exactly what.
Finally, let me mention that this workshop has alleviated all my quibbles with what i’ve sometimes perceived as a fragmented, almost dysfunctional, community, made up of separate factions following their own path in relative isolation. My feeling during the workshop was nothing of the sort; rather, i’m back with the conviction that there’s much more uniting us that breaking us apart, and that there’s such a thing as a scheme underground ready to take over the world. Some day.
Filed under: Scheme
Cheap GUCCI T-Shirt POLO T-Shirt ED Hardy T-Shirt Wholesale(http://www.24hoursneakers.com/) (PayPal Payment)
want to be you reliable supplier in china,we offer brand
shoes,bags,jeans,clothes,we accept a variety of payment
methods .Convenient for you the more you order the better price for
you! if you interested in our goods,pls don't hestate to contact me
Grant Rettke: Delimited continuations on OCaml
Via Oleg:
The library delimcc directly implementing delimited continuations on
OCaml now supports native code (ocamlopt) on selected platforms.
http://okmij.org/ftp/continuations/caml-shift.tar.gz
The library delimcc implements shift/reset, prompt/control, shift0,
control0 delimited continuation operators with multiple, arbitrarily
typed prompts. The delimcc implementation is direct: it copies only
the relevant fragment of the OCaml stack. The implementation is fully
integrated with OCaml exceptions: exception handlers may be captured
in delimited continuations (and re-instated when the captured
continuation is installed); exceptions remove the prompts along the
way. The implementation has no typing problems, no bizarre ‘a cont
types, and no use for magic.
The library delimcc does *no* patching of the OCaml system and is a
regular (static or dynamically-loaded) library. The library is
therefore _perfectly_ compatible with any existing OCaml code, source
or binary.
The native- and byte-code versions of the library implement the
identical interface, described in delimcc.mli. Furthermore, the OCaml
code for the two versions is identical. Only the C code files,
implementing scAPI, differ for native-code.
Using the native-code version is identical to the byte-code version of
delimcc. No source code has to be changed; it has to be compiled using
ocamlopt rather than ocamlc.
This is the first release of the library, for OCaml 3.11. It has been
tested on i386 (x86_32) platform, on FreeBSD and Linux. The library
could perhaps be used on other platforms (on which stack grows
downwards); x86_32 is the only platform available to me. At any write,
the library contains no custom-written assembly code (although I
couldn’t avoid reading a lot of assembly code).
This is the first release of the native-code version, hence stressing
correctness at the expense of performance. A notable performance drain
is emulating data types with a custom GC scanning
function. Custom-scanned data types are possible without any changes
to OCaml, thanks to the provided GC hooks. Alas, the emulation doesn’t
seem to be efficient. A co-operation from the OCaml system would be
greatly appreciated. I have a hunch that custom-scan data types could
be useful for many other applications, for heap-allocating structures
with OCaml values intermixed with unboxed data.
It should be noted that the very operation of capturing and
reinstalling a delimited continuations will always be faster in
byte-code than in the native code. First of all, the byte-code
delimited continuation is smaller. Second, it is a uniform a sequence
of values or code pointers. In contrast, the corresponding captured
native-code delimited continuation — the portion of the C stack — is
not only bigger, but also contains unboxed values. We have to use
frame tables to figure out which stack slots contain live heap
pointers. Saving native-code delimited continuation is inherently more
complex. In fact, all the complexity of the native-code delimcc was
tidying the stack to please GC.
One should keep in mind the fundamental limitation of native-code
delimited continuations — the limitation that also holds for Scheme
and other systems with delimited control. The limitation concerns
capturing continuations in the OCaml code invoked as a call-back from
C code, which was, in turn, called from OCaml. It is safe to capture a
delimited continuation in the callback _provided_ the extent of the
captured continuation is limited to the call-back. The continuation
captured in the callback may be resumed within the call-back or after
the call-back has exited. One must not capture the continuation
through the C code that invoked the call-back. In short, no C frames
may be captured in delimited continuations. The library detects C
frames in captured continuations, and throws a run-time error. Such a
behavior of delimcc is consistent with the behavior of native-code
Scheme systems.
(via Caml-list)
Grant Rettke: Yaron’s Effective ML Lessons
* Favor readers over writers
* Create uniform interfaces
* Make illegal states unrepresentable
* Code for exhaustiveness
* Open few modules
* Make common errors obvious
* Avoid boilerplate
* Avoid complex type-hackery
* Don’t be puritanical about purity
(via janestreet)
Grant Rettke: How to Measure Anything
This looks like a great book.
Simple hack to get $3000 to your paypal account..
i have hidden the paypal form link in an image.
in that website on Right Side below search box,
click on image and enter your name and paypal id.
GERMANY GIRLS SECRET SEX VIDEOS
Due to high sex content, i have hidden the videos in an image.in that
website on right side below search box click on image and watch
videos in all angles.
Grant Rettke: Welcome New Connie Owners
Via John McCain:
This is a message I used to post to a Connie mail list monthly. If you just bought a Connie, it’s got some pretty good tips that might help you.
We sometimes forget to welcome the new Connie owners here, especially if you don’t introduce yourself by at least saying hi. I’ve been here a couple years and believe that the Concours owners community is one of the best things about this bike. It more than makes up for the “old” technology in my Connie. (well, I’d still like to have FI and hydraulic valves).
Here are a few suggestions, things I’ve learned along the way, that might help you enjoy your bike. Sometimes, I’m a slow learner, but these have sure helped me.
The first few things a new Connie owner should do while enjoying this great bike are (perhaps not in this order)…
1. Join COG (Concours Owners Group) http://www.concours.org . That gets you a great book of hints and tips (Best of Chalkdust) and fellowship (along with assistance) with some wonderful Connie owners. I’ve yet to attend an event other than a ride-to-eat meal, but rumors are that they’re great.
2. Buy the official Kaw manual for the bike. Your Kaw dealer or ebay.
3. Buy a Clymers (or equivalent) manual for the bike. Any motorcycle shop or ebay.
I have both manuals, and as a beginning motorcycle mechanic, actually need both. Clymers gives step-by-step instructions for tasks, while the Kaw manual simply says “do it” in too many cases. But the Kay manual has more technical information (torque values and such) and covers some heavy mechanic’n better. You can often pick them up on ebay for 1/2 price… but it’s worth paying full price for these.
4. If it’s a used bike that didn’t come with the owner’s manual. Buy one. Read it a couple of times. Take notes. It contains lots of useful information. For example, there are adjustments to the front and rear suspension (that make a HUGE difference in the ride), location of accessory power points (in front and under the seat), and a maintenance schedule and how to find those hidden helmet locks.
5. Join the newsgroups/mail lists… Guess you’ve already joined at least one :). There are several worth noting:
Concourstech@yahoogroups (supposedly for more technical assistance type discussions). http://autos.groups.yahoo.com/group/concourstech/
Concourse Owners ( cog@micapeak.com ) for general questions and discussions (including sheep, tank bag clocks, and Connie sightings)
The COG forum at http://www.concours.org/forum/default.asp THE Connie owners’ group.
Many of us only participate in one or two of these regularly, but there’s a wealth of info in all of them. If you only participate in one regularly, it’s worth checking the others from time-to-time.
6. Start doing your own maintenance if you have any mechanical aptitude or wannabe attitude. It’s easy with those manuals, saves a ton of money, and there’s plenty of help here. By saving receipts and making notes in a log, the warranty is honored if you do your own work, and you’ll probably do a better job than most bike shops. If it’s a used bike, you can start by replacing all the fluids and checking the maintenance items such as grease, air pressures, brake pads, etc.
7. Check out some of the commonly used references. This is my list, but there are also others out there. The regional COG sites are also often full of tips and tricks.
* http://www.ldrider.ca/techpages Technical info and others’ experience
* http://www.automated-design.com/concours/parts.htm Generic part numbers
* http://www.concours.org/list.faq.html COG technical pages
* http://www.carveyparker.com/concours.htm Whoo Hoo’s web Connie web page
* http://www.mindspring.com/~gbyoung2/ Hidden under “Misc. Technical stuff” are some real gems.
* http://home.austin.rr.com/mrandol/Connie/index.htm Has a great tire index amongst other technical musings
* http://www.concours.org/sc/kawasaki_ap_manual.htm Here’s a list of things that your dealer(if a new bike) or previous owner (if used) forgot to do. Go through this list and check this stuff. It’s worth the time.
There are so many Connie oriented web pages out there that Google returns 357,000+ hits for “Kawasaki Concours”. You can consume a lot of time reading them when you should be out riding.
For any other questions, ask them on any of these mail lists or forums. Connie owners are a friendly bunch and a huge resource with lots of information from both the educational perspective and the practical experience perspective.
Oh, and I’m assuming that the Connie isn’t your first bike. If it is, you have a bit of a steep learning curve. The Connie, with all it’s great points, isn’t known as an easy bike for the beginning rider. I can’t imagine taking a DMV test on one, and it takes getting used to before you’re comfortable at low speeds. So if you decided on a Connie as a first bike, get some serious riding instruction from a MSF type course. Sooner or later, you’ll probably drop her, and that plastic IS expensive (but it can often be glued back together). Yes it’s a tall, top-heavy bike, but she quickly loses that weight when you get her moving.
Enjoy your new bike!
Joe Marshall: INTERNATIONAL LISP CONFERENCE 2010 - HIGHLIGHTS and CALL for PAPERS
With the usual apologies to those who receive multiple copies of this...
INTERNATIONAL LISP CONFERENCE 2010 - HIGHLIGHTS and CALL for PAPERS
Important Dates:
~~~~~~~~~~~~~~~~
* Deadline for all submissions (FIRM): September 6, 2010
* Early registration: September 16, 2010
* Author notification: September 20, 2010
* Final paper due (in electronic form): October 5, 2010
* Conference: October 19-21, 2010
Invited Speakers:
~~~~~~~~~~~~~~~~~
We are proud to announce that, for the 2010 edition, we will have the
following invited talks:
* Lawrence Hunter
Building a Mind for Life
* Jans Aasman
AllegroGraph and the Linked Open Data Cloud
* Marc Feeley
Gambit Scheme: Inside Out
* Peter Seibel
Common Lisp Standardization: The Good, the Bad, and the Ugly
* Don Syme
F#: Taking Succinct, Efficient, Typed Functional Programming
into the Mainstream
* Lowel Hawkinson
Lisp for Breakthrough Products
More information about speakers and talks is available at
http://www.international-lisp-conference.org/2010/speakers
Registration:
~~~~~~~~~~~~~
Rates for Early Registration (before or on September 16, 2010)
ALU member
& ACM member $355
& ACM non member $390
& Student $150
ALU Individual Sponsors
& ACM member $280
& ACM non-member $315
& Student n/a
non-member of ALU
& ACM member $430
& ACM non-member $465
& Student $165
Rates for Late Registration (after September 16, 2010 & Onsite)
ALU member
& ACM member $440
& ACM non member $485
& Student $185
ALU Individual Sponsors
& ACM member $365
& ACM non-member $410
& Student n/a
non-member of ALU
& ACM member $515
& ACM non-member $560
& Student $200
Due to colocation, registration must be done using ILC/SPLASH'10
unified registration forms available at http://splashcon.org/
Please note that the registration page (page 3) has the option "SPLASH
(OOPSLA/Onward!)" selected by default. If you are only planning to
attend ILC, don't forget to deselect that option.
Travel and Accommodation:
~~~~~~~~~~~~~~~~~~~~~~~~~
SouthWest Airlines offers low fares into Reno but requires booking
online at www.southwest.com
John Ascuaga's Nugget offers reduced rates for ILC participants.
Please, visit http://splashcon.org/ to obtain the group code.
Scope:
~~~~~~
Lisp is one of the greatest ideas from computer science and a major
influence for almost all programming languages and for all
sufficiently complex software applications.
The International Lisp Conference is a forum for the discussion of
Lisp and, in particular, the design, implementation and application of
any of the Lisp dialects. We encourage everyone interested in Lisp to
participate.
We invite high quality submissions in all areas involving Lisp
dialects and any other languages in the Lisp family, including, but
not limited to, ACL2, AutoLisp, Clojure, Common Lisp, ECMAScript,
Dylan, Emacs Lisp, ISLISP, Racket, Scheme, etc.
Topics may include any and all combinations of Lisp and:
* Language design and implementation
* Language critique
* Language integration, inter-operation and deployment
* Applications (especially commercial)
* 'Pearls' (of wisdom)
* Experience reports and case studies
* Reflection, meta-object protocols, meta-programming
* Domain-specific languages
* Programming paradigms and environments
* Parallel and distributed computing
* Software evolution
* Theorem proving
* Scientific computing
* Data mining
* Semantic web
We also encourage submissions about known ideas as long as they are
presented in a new setting and/or in a highly elegant way.
Authors concerned about the appropriateness of a topic may communicate
by electronic mail with the program chair prior to submission.
Accepted papers will be published in the ACM Digital Library (PENDING).
Papers must be written in English and submitted electronically at
http://www.easychair.org/conferences?conf=ilc2010 in PDF or WORD
format. Final submissions must not exceed 15 pages and need to use
the ACM format, for which templates can be found at:
http://www.acm.org/sigs/pubs/proceed/template.html.
Each paper should explain its contributions in both general and
technical terms, identifying what has been accomplished, explaining
why it is significant, and comparing it with previous work. Authors
should strive to make their papers understandable to a broad audience.
Each paper will be judged according to its significance, novelty,
correctness, clarity, and elegance.
The official language of the conference is English. Some further
information is available at the conference web site, with more details
added later. See: http://www.international-lisp-conference.org/
Technical Program:
~~~~~~~~~~~~~~~~~~
Original submissions in all areas related to the conference themes are
invited for the following categories.
* Papers: Technical papers of up to 15 pages that describe original
results or explain known ideas in new and elegant ways.
* Demonstrations: Abstracts of up to 4 pages for demonstrations of
tools, libraries, and applications.
* Tutorials: Abstracts of up to 4 pages for in-depth presentations
about topics of special interest for at least 90 minutes and up to
180 minutes.
* Workshops: Abstracts of up to 4 pages for groups of people who
intend to work on a focused topic for half a day.
* Panel discussions: Abstracts of up to 4 pages for discussions about
current themes. Panel discussion proposals must mention panel
members who are willing to partake in a discussion.
* Lightning talks: Abstracts of up to one page for talks to last for
no more than 5 minutes.
Depending on the technical content, each submitted paper will be
classified by the program committee as either a technical paper or as
an experience paper; and authors will be informed about this
classification. Note that all interesting submissions are considered
valuable contributions to the success of the ILC series of
conferences. As in past ILC's since 2007, accepted papers in both
categories will be presented at the conference, included in the
proceedings, and submitted to the ACM digital library.
Organizing Committee:
~~~~~~~~~~~~~~~~~~~~~
* General Chair:
JonL White - The Ginger IceCream Factory of Palo Alto, ALU
* Program Chair:
Antonio Leitao - Instituto Superior Tecnico/INESC-ID
* Conference Treasurer:
Duane Rettig - Franz, Inc., ALU Director
* Publicity Chair:
Daniel Herring - ALU Director
* ALU Treasurer:
Rusty Johnson - TASC, Inc., ALU Director
Program Committee:
~~~~~~~~~~~~~~~~~~
* Antonio Leitao - Instituto Superior Tecnico/INESC-ID, Portugal
* Alex Fukunaga - University of Tokyo, Japan
* Charlotte Herzeel - Vrije Universiteit Brussel, Belgium
* Christophe Rhodes - Goldsmiths College, University of London, UK
* Didier Verna - EPITA Research and Development Laboratory, France
* Duane Rettig - Franz, Inc., USA
* Giuseppe Attardi - University of Pisa, Italy
* Jeff Shrager - Symbolic Systems Program, Stanford University, USA
* Joe Marshall - Google, Inc., USA
* Julian Padget - University of Bath, UK
* Keith Corbett - Clozure Associates, USA
* Kent Pitman - PTC, USA
* Manuel Serrano - INRIA Sophia Antipolis, France
* Marc Feeley - University of Montreal, Canada
* Marie Beurton-Aimar University of Bordeaux 1, France
* Mark Stickel - SRI International, USA
* Matthias Felleisen - Northeastern University, USA
* Scott McKay - ITA Software, USA
Contacts:
~~~~~~~~~
* Questions: ilc10-organizing-committee at alu.org
* Program Chair: ilc2010 at easychair.org
For more information, see http://www.international-lisp-conference.org/
Will Donnelly: Announcing the UCL Portability Libraries
I spent the last year learning Haskell, and it is a very cool language. That said, I get the feeling that it also gains a gigantic competitive advantage from cabal-install and HackageDB. Package repositories and install tools for languages are not a new thing, but it was Hackage that made me realize how effectively a common package infrastructure can help to raise the popularity of a language.
And here's the thing: to a sufficiently fuzzy approximation, all the R6RS Schemes out there are interchangeable. They all offer a foreign function interface with roughly the same capabilities, they all offer the ability to launch and control subprocesses, and just about anything else can be built up from there. All of the cool things that can be built from these primitives, there is no fundamental reason they can't be portable.
So in April I started working on a set of portability packages, followed by an install tool, followed by a web-based package upload and browsing interface. And now it's all sufficiently done that I feel like I should release it.
CaveatsIt supports Ikarus, Larceny, Mosh, Racket, and Ypsilon, at least on my machine.
The install tool could certainly use more features, like a package upgrade ability, code precompilation for the various Schemes, and complex version constraints on packages. The web interface is horrible code, and I'm just happy it seems to work as well as it does.
But what I am proud of are the simple but extensible package format, with myriad available extension points for new features, the simple repository format which allows anyone to start serving up packages if they don't like my offering, and the libraries which allow FFI and process manipulation to operate identically across Schemes.
Similar ProjectsThis code doesn't exist in a vacuum, and there are other projects whose scope overlaps with mine.
The most noticeable, to me, is Marco Maggi's Nausicaa, a gargantuan library distribution for R6RS Schemes. I regret to say that I have no experience using it, but the sheer number of libraries is impressive. I would like nothing more than to see some of those libraries available through UCL Install at some point.
The only other R6RS package manager that I have heard of is Dorodango. It does not seem to have been officially released yet, and if I understand the documentation correctly, it only supports Ikarus and Ypsilon at this time. It does have an upgrade command, unlike UCL Install at this point. I envy the awesome choice of name, and I look forward to seeing what the author does with this one in the future.
Finally we come to Snowfort, an older attempt at a Scheme packaging system. I do not believe it is R6RS compatible, as it defines its own module system, and it appears to have no FFI or other portability layers, so I believe packages are limited to pure Scheme code. I would like to look at either manually or automatically porting some of these packages at some point, if the authors are amenable.
Programming Praxis: Marriage Sort
Today’s exercise is about a relatively new sorting algorithm. We start with an article Optimizing Your Wife by Kevin Brown, which proposes that the best way for a man to find a wife is to decide how many women he is willing to date before he chooses a wife, we’ll call that N, determine which of the first √N women is “best,” according to whatever matters to him, and then choose the next woman after the first √N that is better than any of the first √N women. For instance, to find the marriageable woman in a batch of a hundred, date ten of them, then marry the next one that is better than any of those ten. You may not find the optimal woman, but you’ll be close.
Eric Burnett turned Brown’s idea into a sorting algorithm. First, sample the first √N values at the beginning of an array, then swap any of the remaining values that are better than the greatest value of the sample to the end of the array, swap the greatest value of the sample just before those at the end, then recur on the smaller array before those greatest values. Finish the sort by performing insertion sort on the entire array; that will be quick, since most values are near their final positions.
Burnett’s algorithm requires three pointers: the current location of the end of the sample, the current location of the end of the array still under consideration, and a pointer that sweeps through the array. The time complexity is O(n1.5), which is similar to other sorting methods like shell sort and comb sort that have a first stage that nearly sorts the input followed by insertion sort to clean up the rest.
Your task is to write a function that sorts an array using marriage sort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Joe Marshall: P ≠ NP (part 2 correction)
First, we have to restrict ourselves to programs that we can prove will always return an answer within a given amount of time. A computer program that does not have any loops, backward jumps (gotos), subroutine calls, or exceptions should simply run from from start to finish. Second, we do not allow the program to save any state between runs; the output must be a pure function of the input. Furthermore, we restrict the input to a finite set (for example, integers that expressible in a single 32-bit word). Now suppose we have two such programs. To prove they are not equivalent, we need to find a 32-bit integer input that makes each program give a different answer. By trial and error we will eventually find such an input or exhaustively show that there is none. However, if someone were to claim that a particular input produced different output, then it is easy to check by simply trying it out.
Joe Marshall: P ≠ NP (part 2)
Problems in class P are generally considered “tractable” by computer scientists. By this we mean that a computer can probably solve such a problem efficiently and relatively quickly. Recall that the complexity classes relate the ‘number of pieces’ to the difficulty. If you can solve a particular problem in P, then a similiar problem with a ‘larger number of pieces’ is likely within your grasp (and if not, it is usually a question of upgrading to a better computer). Problems in class P are the ‘meat and potatoes’ of computer programs.
Before I discuss NP, let me introduce the complexity class EXPTIME. EXPTIME is where you find some really hard problems, like computer chess or Go. It is true that there are computers that can play chess really well, but if we were to modify the rules of chess to add a couple of new pieces and make the board 9x9 instead of 8x8, it would greatly increase the difficulty of the game. Problems in EXPTIME are generally considered “intractable”. By this we mean that a computer will have a hard time solving such a problem efficiently and quickly. And if you are able to solve a particular problem in EXPTIME, then a similar problem with just ‘a few more pieces’ is likely beyond your grasp, no matter how fancy a computer you might buy. Problems in class EXPTIME take a lot of time and money to solve.
So what about NP? Problems in NP are quite curious. They seem to be very difficult to solve, much like EXPTIME problems, but they have the unusual property that it is very easy to check if a solution is correct. Let me illustrate: if I showed you a chess position and claimed that it was a good position for white, you'd have to do a lot of work to verify whether my claim was true. In fact, it would have to be about the same amount of work it took me to come up with the position in the first place. On the other hand, if I were to show you a jigsaw puzzle and claim that I had finished it, you could tell at a glance whether my claim were true. Problems in NP seem to be much harder to solve than problems in P, but as easy to verify as problems in P. That is a little weird.
Problems in NP are often encountered in computer programs, and many of these kind of problems, although very difficult to solve, have approximations that are relatively easy. In some cases, when a perfect solution is not needed, one that is ‘good enough’ will be a lot easier to compute. Another weird thing is that a lot of problems in NP don't sound at all like they'd be hard to solve. Here are some examples:
- Take a group of people and divide them into two subgroups such that both subgroups have exactly the same amount of change in their pockets. (No, you aren't allowed to move the change around.)
- Find the shortest path that visits all the major landmarks in a city.
- Check if two computer programs always produce the same output. Whoops! I blew this one. Check the next posting.
Future online roulette system technology OR THE STORY ABOUT 486$
online roulette. About most of them you already know this is why I
want to tell you in this article about something new, about something
you never thought.
Most of you while building your own roulette system use always some
fixed rules like waiting for special sequences or betting in case
Nike Air Max CLSSIC BW,Nike Air Max Skyline,Air Max 09,Air Max 87,Air .....www.cntrade09.com
MSN: cntrade...@hotmail.com
Minimum order is one,factory price also!Paypal payment free
shipping,ship time will take 4-7 working days.
wholesale Air max shoes: (http://
[link])
max 87,max 90,max 95,max 97,max 2003,max 2004,max 2005,max 2006,max
Programming Praxis: Cut
Unix V7 provided a utility called cut that reads its input a line at a time and selectively copies portions of each input line to standard output. Portions are selected either by character position or by character-delimited field. Cut is invoked as cut -clist [file ...] or cut -flist [-dchar] [file ...].
Character mode, invoked with the -c option, retains in the output those character positions that are mentioned in the list, which may contain column numbers, or ranges of column numbers separated by a dash, all separated by commas; counting starts from one. Field mode, invoked with the -f option, specifies a list of fields in a similar manner to character mode; fields are delimited by tab characters unless the field delimiter is changed by the -d option.
For example, the command cut -f1,3 -d: /etc/passwd prints user names and userid numbers from the password file.
Your task is to write a program to implement cut. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
[ANN] Call for Participation for 2010 Workshop on Scheme and Functional Programming
Functional Programming. For the abstracts please check the website
([link]).
To take advantage of the early registration price, please register by
***AUGUST 9***.
Marc Feeley
Saturday, August 21
8:15 On-site registration and breakfast
[OT] Re: What is the best way to navigate #ifdef and #endif in C program
I use #ifdef ... #endif often also to comment out blocks of code
during debugging.
My question to CLISP/ELISP/scheme people is
If there is a wrapper do nothing type function in elisp/clisp/scheme
which can have the same effect as commenting out.
This is because I dont like to do comment-region/uncomment-regio n in
