Slashdot Mirror

Or you structure your state so that creating "copies" is cheap (some sort of tree or graph -- you only need to copy the path to the modified portions). Something like this.

If they had assigned a random value to each element and sorted by that value the result would have been truly random as the value associated with each element would have been consistent.

As another poster above pointed out, that only works if your "random values" are unique.

  -AC

It's not an issue of how to get a truly random number, or of seeding a random number generator, but rather how to you use a source of random numbers to randomly order a list.

Some "reasonable sounding" methods don't actually work - e.g. attach random numbers to each list item and sort the list by these numbers (1). Microsoft used a similar method of sorting using a random comparator.

Some simple methods that DO work are picking a random permutation or executing a bunch of random swap operations on the list.

(1) http://okmij.org/ftp/Haskell/perfect-shuffle.txt

It's even cleaner in Scheme. (Just saying.) And, your code doesn't handle attributes or empty tags properly. But it's true that the Python equivalent would need to make some compromises to avoid getting completely hairy -- starting by either putting the HTML pseudocode into a string or throwing parentheses all over the place.

DSLs aren't Python's strong point. Some options are:
- Some string transformations, then eval()
- A recursive operation on a dictionary, since HTML in particular kind of fits that model
- Just use a library like xml.etree for whatever you were actually trying to do (I know, that's just what a Java programmer would say)
- Full-blown parser and interpreter, with some help from the standard library

But the specific case isn't that interesting. Almost all of the capabilities (not necessarily basic features) are the same between the latest incarnations of Ruby, Python, Perl, and JavaScript -- where one's missing a feature, there tends to be at least a workaround.

The main difference between Ruby and Python is that Guido doesn't like functional programming, but really likes structured C, Unix, and teaching languages. Matz seems to really like Common Lisp and Smalltalk, but recognizes the need to git 'er done, Perl-style, too. Guido's background is in big organizations; Matz's is in compilers. They're both brilliant.

So Python code looks almost exactly like C pseudocode, and the real-world code often looks just as clean as the tutorial examples (in contrast to, say, C++). If you write something that runs correctly and efficiently in Python, it will generally look reasonable to any other programmer, too.

Ruby instead takes every standard programming style and makes it easy to express an idea that way. If you already understand FP, OOP, etc., it's incredibly expressive. I think an experienced, well-rounded hacker tends towards Ruby... but a company like Google is sane for mandating that their gargantuan codebase, written by thousands of adventurous coders with differing styles and tastes, should be mostly Python.

More fundamentally, a universal turing machine has the quality of turing completeness. That is, it can compute anything that can be computed at all.

Given that, a convieniant short proof of the turing completeness of any programming language or computing device is to write a universal turing machine emulator for it. Note that just being Turing complete doesn't mean that th machine or language has decent performance or that it's any good to write a program for/in, just that it's not totally worthless.

Perhaps frighteningly, this has been accomplished for Sendmail's configuration language.

Irrelevant to the real world? Hmmm... I suppose one's definition of "real" depends on the limitations of one's experience, but a clearer understanding of what is and is not possible in principle should surely be recognized as relevant by anyone interested. Maybe you really just aren't. Studies of intractability in computability do not only show where the boundaries lie, but can be helpful and save time in practical ways. In the context of security, I've personally seen halting concerns arise in turing-complete grammar extensions to regular expression engines, for example. Ever heard of a DoS attack? You wouldn't want a devious user to trigger one of those on your modded PCRE engine, so what's the best prefilter/dectector? Doh! There isn't one! Good thing that expensive CS education helped to steer us clear of that pitfall. Why aren't there any good sendmail configuration security checkers? Answer. Honestly, there are an infinitude of real, practical examples. You need to check out Garey&Johnson's Classic, at least the introduction. :-)

uh... splint? Now you're just being silly on purpose.

Make it out of cheese? Talk about an irrelevancy.

Poor Russell and Gödel and Turing and Post and Church and Rice and .... All those mental masturbators! What wasted lives!

Sendmail “configuration” is a Turing-complete language. In that sense, it is unlike what most people think of in terms of configuration, which typically amounts to key-value pairs. And as another poster pointed out, you should not be editing it directly unless you have very specific needs.

OK, I'll indulge you. Why sendmail sucks, in a nutshell:

It was designed before Internet e-mail standards were established. As a result, it contains a general purpose rewriting engine that's Turing complete--the idea was it would be able to be configured to translate addresses between BITNET, UUCP, JANET, ARPAnet, CompuServe, FidoNet, and so on, without recompiling the sendmail binary. This was important because back in the 80s, those networks all had different address formats.

Nowadays the ability to arbitrarily rewrite addresses is completely unnecessary, but Sendmail keeps the old design. This leads to a number of major misfeatures.

1. Sendmail is a pig to configure. The "new improved" sendmail.mc is slightly better than the old sendmail.cf, but still awful compared to the alternatives because it's layered on top of M4, an ancient macro processor. Compare an example postfix config and an example sendmail config. And remember, that's the new .mc file that's compiled into the actual sendmail.cf; if you ever need to do something complex that requires editing the sendmail.cf itself, you'll be faced with something much nastier.

2. Sendmail has a continuing history of poor security. 16 vulnerabilities between 2000 and mid-2006, according to nvd.nist.gov. By comparison, Exim has had 9, Postfix has had 4, Qmail 3.

3. Sendmail has lousy performance. Postfix is 2-4x faster. Take a look at some benchmarks.

4. Sendmail was designed to parse and reconstruct the header of every e-mail going through it. This makes it brittle--give it something it isn't expecting, and the results are unpredictable. This has resulted in Bcc:ed recipients being revealed to each other, unknown header fields being destroyed, and so on. It also makes e-mail forensics difficult--just because the message looked like it had the right addresses when it arrived, didn't mean it had the right addresses when it was sent, if it has passed through sendmail. MTAs should not rewrite e-mail going through them; only e-mail being passed to them directly by a client.

5. It has broken behavior when sending to multiple recipients. For example, if the To: field is missing a comma between two addresses, sendmail will send copies of the e-mail to all the addresses that it can parse, then barf on the broken ones. This is unhelpful, because if the user then re-sends the mail, most people end up getting 2 copies.

So in short: it's broken, it's slow, it's insecure, and it's awkward to configure. There are other open source mailers that have a few of those defects, but sendmail is the only one that has them all. Do a search for "sendmail sucks" and you'll find plenty of people with the same opinion as me.

sendmail is a computer programming language?

Well, for one, the poster of this submission states that optional garbage collection IS one of the proposed additions in C++0x, so I don't know where this complaint is coming from. On top of that, if you really did want the equivalent of garbage collection, just use Boost smart pointers for any heap allocations.

the lack of import declarations

Why should this require language changes? Just get (or develop) an IDE that generates the headers for you. Problem solved. This seems like more laziness. There's perfectly sensible reasons to separate the headers from the code.

no properties

Just make class variables protected or public and access them directly. Accessors really are not that important. Frankly, I don't believe in encapsulation for the sake of encapsulation. Most of the time, it simply obfuscates things. Hell, most of the reason I can't stand java to this day is because I tired of dealing with constructs like this:

system.subsystem.lang.util.math.random.Plus(myclas s.GetInteger().intValue(),myclass2.GetInteger().in tValue()) // exaggeration intended.

It's bad enough that Java is too stupid to auto-cast Integers and "int" when it has hundreds of functions that deal exclusively with each. At least if the Integer class had the "int" variable not within a damn accessor, each line of my code might actually be shorter than 80 chars *smirk*

No closures

It is possible to carry over functional programming style into C++, including closures, lambda-expressions, and currying. It's just not pretty. And honestly, I see no reason for it being there. C++ is not, nor was it ever intended to be, a functional programming language. Why not just code in Scheme or Ocaml if that's what you want? Most C programmers can't stand the sight of those constructs.

For example, a button with an optional bitmap would be constructed in one line of code, like this: new Button(parent = mainWindow, text = "hello world", bitmap = bitmap1, click = {mainWindow.close()});.

How is that any different than "new Button(mainWindow, "hello world", bitmap1, &mainWindow.close)", with a single constructor on the backend? And if you really wanted to allow for a dynamic situation, what's wrong with instantiating an object and then manually assigning the values? You could even put them all on one line if you wanted: myButton = newButton(); myButton.text = "hellow world", etc etc...

C++ could have been the dominant language, if it was not for the stubborness of the C++ committee to accept that programming languages are developed based on what the world needs, and not on what a few good men know.

Many of your complaints seem to stem from the fact that alot of functional dogma has not carried over into C++ (such as continuations and closures). Last I recall, functional programming represented a very small subset of the programming populace ("what a few good men know"). Most programmers simply don't think that way. Anyways, most problems that call for a functional solution are better done in other languages anyways.

Alot of the other things you mention would be nice though.

Sorry for rather long and muddled post, and also for my poor English... Also, if you have allergic reaction to Lisp advocacy, don't read any further.

Some years ago when I had some spare time I was struggling a lot trying to make C++ a better language. I was trying to reinvent reflection, easy serialization, extend metaprogramming facilities and so on. My hopes were mostly in http://www.boost.org/">Boost C++ libraries.

At some point I've decided to try to write some extended metaobject generator, like Qt's moc, but friendlier to "modern C++", using GCCXML. In addition to generating reflection info, I was thinking of generating proxy classes and other stuff like this.

Among other things I've tried to do some of XML translation work using XSL (i.e. XML AST from GCCXML -> some more AST convenient XML representation -> (transformation) -> resulting metaobject AST. I've discovered some interesting things about XSL, e.g. that it's possible to "emulate" iteration (which is somewhat lacking in XSL) with recursion. Nevertheless after a few days of fighting with XSL I've decided to try some language which is more suited for processing various trees. Of course, when C++0x is ready, I thought, it will be the best language in all respects, including tree stuff, but as of now, STL+boost::lambda+whatever is still somewhat quirky (for instance, look at those 10 pages long error messages when you make a typo). So, although I was heavily influenced by standard myth-based mindset concerning Lisps (slow, interpreted, purely academic, "lost in a sea of parenthesis" and so on) I've decided to give Scheme a try, as I've heard that it can be used as a better XSL.

After playing with Scheme for a while, I've found out (to my surprise) that the language can be used for many other purposes besides list (tree) processing and simple scripting (as in Gimp). As an example, there are wonderful things like Scsh. It's possible to write Web applications, many Schemes can do OO. My deep respect to C++ (The Most Powerful Language Ever) began to fade, albeit slowly.

So I've begun to try to do some real things in Scheme. Disillusionment has come rather quickly due to the fact that a lot of critical stuff in Scheme (e.g. OO and packages) is not standardized and thus is 100% non-portable between implementations. Moreover, every implementation has its bugs and limitations, and when you come to the point when you need to change your implementation you discover that most of your code needs to be rewritten from scratch.

I was nearly ready to continue developing my "metaobject generator", pushing Scheme's role back to "better XSL". But something made me try Common Lisp before doing so.

What quickly became apparent to me from my CL experience is that most of problems Boost guys are fighting against are just plain nonexistent for Lispers. Look at this, for example: variant.hpp. A good workaround for C++ typing model. What do we have in Common Lisp?

(let ((x 5))
....
(setf x "abc") ;; no problems with types!
....)

(sorry for mangled indentation)

Now look at this beauty: boost::lambda. Don't forget error messages it produces when you mistype something or stumble across a bug. CL example?

(mapcar #'(lambda (x)
;; any code you want
...)
my-list)

Not to mention Lisp's GC versus boost::shared_ptr.

OK, these are areas where dynamic languages like Perl, Python and Ruby, and even statically typed like C# or Java are catching up to some degree. Now let's look at some CL's more-or-less unique features.

Except that this article is about people developing in Haskell - a language that's every bit as fun to use as Python (it even has optional syntactic whitespace), but compiles to native code (so it's faster) and infers types at compile-time (so it's robuster).

Think Pugs is cool? Look at this. These guys have implemented a complete transactional file system - looks like a Unix FS, but provides snapshots, unlimited undo, true copy-on-write handling of links (including link cycles), and perfect concurrency without requiring any OS-level threading. In just 540 lines of Haskell.

Give it a try. The learning curve's steep at first - it's got some concepts you simply won't have encountered anywhere else. But if you're smart enough to have dropped C++ in favour of Python, you're smart enough to handle Haskell.

...this.

It may have something to do with this. (Though to be honest, it wouldn't take much stretching beyond the ideas in that web page to argue that BASIC is a functional programming language that uses monads.)

I appologize about macros. I have had only brief exposure to Haskell, and knew that it had macros, so (it being a functional language and all) I just assumed that that meant macros ala LISP. Clearly I was wrong.

As for Scheme, here's a reference that discussses schemem macros

Overall, I wasn't trying to start a language war. I have a great deal of respect for Common LISP. It is, however, huge and quirky, so I generally don't tend to direct people at it who just want to learn functional programming. That's a bit like giving someone an F-18 to learn how to fly.

http://okmij.org/ftp/papers/Scheme-Metcast-paper.p s.gz

http://okmij.org/ftp/papers/Scheme-Metcast-talk.ps .gz

Getting weather data using Scheme.

http://okmij.org/ftp/papers/Scheme-Metcast-paper.p s.gz

http://okmij.org/ftp/papers/Scheme-Metcast-talk.ps .gz

Getting weather data using Scheme.

Actually, it's demonstrably superior to Java's way, as Java doesn't maintain the Liskov Substitution Principle. With no subclassing, Limbo doesn't have this problem.

I wouldn't say that Limbo's way was superior in the same way to all languages with subclassing, as that's a matter of taste. I'll just say that IMHO, the main obstacle to writing sound, maintainable programs is the problem of complexity.

A big contributor to the complexity of a system is the amount of interdependency between its components, which is often encapsulated by class/module interfaces. In a system with subclassing, I cannot understand a subclass unless I have understood all its interface superclasses; likewise I cannot understand a class implementation unless I have understood all its implementation superclasses.

Instead of encapsulating complexity behind an interface as narrow as possible, subclassing promotes unnecessary interdependency between software components, and therefore makes for a more complex and less maintainable system.

This page has more references on this kind of thing.

You'd end up keeping the receive patterns and that one in sync, which would be pain

That's what type checking's about, dude! As far as I can see, with Erlang message passing, if you accidentally send a message of the wrong type, it'll just hang around, lost in transit. The type checking on Limbo channels is just the same as that on function calls, and that's great. For looser, untyped, interconnections, you've got files (which in Inferno can represent any external resource).

That's not to say I don't think that Erlang isn't cool - I do, and I like functional programming languages. I'm just saying that Inferno has a great deal to offer too, and perhaps more in some areas.

Monads are also a branch of category theory that are adopted by languages like Haskell (the prime developer of which works for Microsoft Research).

I doubt this is a coincidence. I'd love it if this meant that MS is working functional concepts into its mainstream software. It might even be a reference to the clever article Unix Pipes as IO Monads. Unfortunately, the short review doesn't offer any hint of this, but frankly the reviewer seemed wowed by pretty uninspired features, so maybe he missed the cool parts. Or, the name might just be a throw-away in-joke.

SXML & SXLT. It's Scheme with XML. True, it's not procedural, but it's a programming language. Oleg Kiselov wrote it. http://okmij.org/ftp/Scheme/SXML.html

Uh, unfortunately I'm obliged to retract my endorsement - it's not XML at all!

In fact, Water is pretty eccentric all over.

I'm afraid it's back to Scheme and SXML for me...

that the same applications of XML that drive the keening about bloat and hype seen in these comments are precisely those which are driving the specs to the wrong side of the 80/20 for XML/XSL's original goals: bringing the semantic power of SGML and DSSSL to the Web. Goals for which its purist cousins RelaxNG, REST, et. al. remain admirably suited.

The back-end curmudgeons are right, XML stinks for a universal wire format. But for loosely-coupled, message-based, semantically-rich systems it is hard to beat. And document-oriented systems which don't use XML barely deserve notice any longer.

I gently refer s-expression trolls to paul and oleg

What you want to look at for processing XML in a "lisp-like language" (Scheme) is SXML and its related packages (SXPath, etc.)

These are packages for manipulating and representing XML content in Scheme programs.

XML can be seen as a syntax tree, right? XSL and its friends are tree manipulation tools.

The same can be said for Lisp and Lisp-like languages, whose "program as data" philosophy (and 35 years of history) focuses on program evaluation as tree transformation and manipulation (through nested lists.)

SXML is a translation of XML from its heavy angle-bracket syntax to a Scheme sexpr (Scheme/Lisp's bracket expression syntax) syntax (and back to XML again.) It's extremely powerful.

It's worth looking at if you spend large amounts of time manipulating XML data.

It's alllll about the ratio.

If you have lots of real text, and tags scattered lightly around your document, then XML is easy for humans to read. Think about how readable HTML1 documents were.

If you have little bits and pieces of data embedded into a massive element hierarchy, then deciphering it becomes a chore. Ant's config file falls in that category. So do most web pages nowadays, it seems.

Remember that XML (and SGML) was designed so humans could write documents with it. Config files are really outside of its original domain, and it's no wonder it's showing some problems. That's why I prefer to use SXML syntax when I'm dealing with XML-as-dataformat. I find it's better tuned for that application.

I've become fairly interested lately in using Scheme (probably mzscheme) and the SXML package as a way to do arbitrary XML translations in my free time (if I had any).

From the looks of it, the ability to create a reflexive mapping between an arbitrary XML document and an interpretable programming language is too powerful to be ignored.

Do you think that in the future one of the primary roles of Scheme/Lisp is going to be in manipulation of XML documents, or is this going to be relegated as an academic curiostiy while the world struggles through parsing XML in Java?