2009-01-29

Why Lisp Do Not Have A Generic Copy-List Function

perm url: http://xahlee.org/UnixResource_dir/writ/lisp_equal_copy_list.html

Xah Lee, 2009-01-29

Dear lispers,

LOL.

There's is a paper by Kent Pitman, about something about why lisp doesn't have copy or the complexities of meaning of equality. This essay is often cited by lispers in comp.lang.lisp, about every few months in the past 9 years.

The current url is here: http://www.nhplace.com/kent/PS/EQUAL.html

I became aware of this essay maybe in early 2000s. I actually never red it. I just knew that it's something lisper quote frequently like a gospel. In the back of my mind, i tend to think it is something particular to lisp, and thus is stupid, because many oft-debated lisp issues, never happens in Mathematica, nor any dynamic langs i have become a expert of since 2000. (e.g. perl, python, php, javascript.).

Today, out of boredom, i went and took a look (it has been just cited again, by a old-time lisper Rob Warnock). I thought: let's see what would happen, and perhaps it would cause me to write some damning refutation about it.

This is when i LOL'd.

The paper, basically indicates a fundamental problem of lisp i have tried to tell lispers for long. Namely: The cons prevents lisp from developing into a coherent, consistent, libraries of functions that deal with tree data. Secondly, the problem is caused by Lisp's “internal” representation of things so-called “object”.

It is not a wonder, why these problems doesn't occur in other dynamic languages, in particular PHP, Mathematica. (it does occur to some degree in Perl, since it somewhat heavily relies on some “internal” gook about references, type globs, file handles, distinction of its own peculiar notion of list and array, etc.)

These 2 issues i have discussed in depth in the past. See:

Here's a short quote from the first essay:

Lisp at core is based on functional programing on lists. This is comparatively a powerful paradigm. However, for historical reasons, lisp's list is based on the hardware concept of “cons” cell. From a mathematical point of view, what this means is that lisp's lists is limited to a max of 2 elements. If you want a longer list, you must nest it and interpret it in a special way. (i.e. effectively creating a mini-protocol of nesting lists, known as proper lists.) The cons fundamentally crippled the development of list processing.

Many lispers do not understand it, in fact actively accuse me of no understanding. (this is in the context of comp.lang.lisp.) Most of this reaction is rather just being defensive. (i presume lispers in real life would receive it better.)

Kent's essay, may be viewed with 2 reactions. One of them, typically taken by lispers, is this:

1. Typical programers are ignorant of lisp. They should learn lisp before “attacking” (and see the light!).

However, it can be viewed in another way:

2. Lisp is a old lang, one of the first lang, with first running version in the 1960s. Many later development in computing theory, isn't caught up in lisp for many social reasons that is naturally understandable, in particular after 1990s when lisp ceased to be used in the industry. Many lisp's ways, thus is quaint, incompatible with today's language views and practices, and sometimes, if not often, not the best.

This essay is originally a post to newsgroup “comp.lang.lisp”.

2009-01-28

function application is not currying

perm url: http://xahlee.org/UnixResource_dir/writ/apply_func_examples.html

In Jon Harrop's book Ocaml for Scientist at http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html

It says:

Currying

A curried function is a function which returns a function as its result.

LOL. That is incorrect.

Here are some examples of a function that returns a function as result, but is not currying.

Mathematica example:

f[n_]:=Function[n^#];
f[7][2]
(* returns 49 *)

Emacs lisp example:

(defmacro f (n) (list 'lambda (list 'x) (list 'expt n 'x) ) )
(funcall (f 7) 2)

Perl example:

sub f {$n=$_[0]; sub { $n ** $_[0]} };
print &{ f(7) } (2);

Javascript example:

function f(n) {return function (x) {return Math.pow(x,n);}; }
alert (f(7) (2));

In the above, a function returns a function, and the result function is applied to a value. They demonstrate 2 things:

  • The ability of the lang to have a function that returns a function.
  • The ability to apply a value (of type function) to a value.

These, are 2 of the features that is part of often sloppily termed as “function as first class citizens”.

However, the above are not languages that support currying, which is a feature that Haskell & Ocaml has.

So what is Currying?

Wikipedia article Currying said it best:

In computer science, currying, invented by Moses Schönfinkel and Gottlob Frege, and independently by Haskell Curry,[1] is the technique of transforming a function that takes multiple arguments (or more accurately an n-tuple as argument) in such a way that it can be called as a chain of functions each with a single argument.

Note how it says “is the technique of ...”.

To be more concrete, in the context of a given computer language, to say that it support curring, is to mean that the compiler understand the concept to certain degree. More to the point, the language is inherently able to take a function of more than one arg and deconstruct it to several functions of single arg.

To say that function returning function is Currying, is a confusion of fundamental concepts.

Mathematically, currying is the concept of deconstructing a function of multiple parameters to a composition of several functions all of arity 1.

I like Jon, because i consider majority of his argument and perspective are more correct or sensible in his trollish spats in newsgroup fighting with tech geekers. But he is really a asshole, and take every chance to peddle his book. Every mother fucking opponitunity, he injects random opinion into discussions about how static typing or greatness of Microsoft, which paves a way for him to post a link to his book on Ocaml/F# or “study” or “speed comparison” of his site. He does this repeatedly and intentionally, about every week for the past 2 or so years, and write in a way to provoke irate responses. In the past 2 or 3 years, i have for 2 or so times without his or anyone's solicitation, publically supported him in ugly newsgroup fights (such as some serious sounding post that accuse him of spamming or or some real life threats about network abuse). However, in the past year as i have had some debates on language issues with jon, i find Jon to be a complete asshole as far as his newsgroup demeanor goes.

PS see also: A Mathematica Optimization Problem ( story of a thread where Jon started a fight with me )


Related essays: