November 25, 2008

The Presentation that sets New Standards

Posted in Computers, Lisp, Programming tagged , , , , , , at 12:54 am by pmatos

In October 1958, John McCarthy published one in a series of reports about his then ongoing effort for designing a new programming language that would be especially suited for achieving artificial intelligence. That report was the first one to use the name LISP for this new programming language. 50 years later, Lisp is still in use. This year we are celebrating Lisp’s 50th birthday.

Lisp was fifty last month. Happy Birthday!

Most importantly, Guy Steele and Richard Gabriel did a presentation that sets a new standard on presentations. Funny, provocative, original, concise and bright!!! A must see… a must re-see…

Presentation!

If one day I manage to do something similar, I will feel accomplished! Congratulations to the speakers!

Advertisements

October 12, 2007

(Common) Lisp on (Tube) Rails

Posted in Lisp at 2:13 pm by pmatos

No, not to talk about some implementation of RoR for Common Lisp.

In fact, it’s just to note that only today (with a 2 years delay) I noticed that the  London Underground is powered by Portuguese software running Common Lisp (Allegro Common Lisp most probably).

Isn’t that nice?

February 3, 2007

Religious Cults are Never Enough…

Posted in Computers, Lisp, Programming, Scheme at 1:21 am by pmatos

Ah, the good side of religion…

Scheme Church Sign

Brothers and sisters, by following Paolo Amoroso’s cult… I found the truth! Come with me through the path of thy lord…

Behold our patch to the book of genesis:

— genesis.txt 2007-02-03 00:13:29.000000000 +0000
+++ genesis-scheme.txt 2007-02-03 00:19:04.000000000 +0000
@@ -5,9 +5,11 @@
of them.

002:002 And on the seventh day God ended his work which he had made;
– and he rested on the seventh day from all his work which he
+ but something was missing so he implemented define, lambda and some other mystic functions;
+ and said unto the skies, here lies the foundation for a great language;
+ now, multiply through diverse implementations and grow…
+ and in the remaining minutes of the day he rested from all his work which he
had made.

002:003 And God blessed the seventh day, and sanctified it: because
– that in it he had rested from all his work which God created
– and made.
+ that in it he had created his masterpiece that would enlighten all he had already made.

May 8, 2006

Porquê LISP?

Posted in Lisp, Portuguese, Programming, Scheme at 9:28 am by pmatos

Parece que existe uma questão recorrente para aqueles que ouvem falar de LISP pela primeira vez seja este sobre a forma de qualquer um dos seus dialectos: “Porquê LISP?”
A pergunta acentua-se quando percebem que de facto, aqueles que se encontram entusiasmados com LISP, encontram-se mesmo viciados. Ora, isto surge em aulas, apresentações e um pouco por todos aqueles que tentam dissiminar a semente do LISP. Paul Graham dá uma resposta interessante à questão na sua página. Visto que existem 2 traduções, uma para Japonês e outra para Romeno, cá fica a portuguesa.

Maio 2003

Se o Lisp é tão bom porque é que não existem mais pessoas a utilizá-lo? Um estudante colocou-me esta questão durante uma apresentação que fiz recentemente. Não foi, no entanto, a primeira vez.

Em linguagens de programação, tal como em muitas outras coisas, não existe grande correlação entre popularidade e qualidade. Porque é que John Grisham (King of Torts ranking de vendas, 44) vende mais que Jane Austen (Pride and Prejudice ranking de vendas, 6191)? Será que o próprio Grisham afirmaria que é por ele próprio ser melhor escritor?

Aqui está a primeira frase de Pride and Prejudice:

“Será uma verdade universalmente aceite que um homem solteiro com uma grande fortuna tenha de estar à procura de esposa?”

“Será uma verdade universalmente aceite?” Palavras fortes para a primeira frase de uma história de amor.

Tal como Jane Austen, o Lisp parece difícil. A sua sintaxe, or falta dela, faz com que esta parece completamente diferente das linguagens que a maior parte de nós está habituado. Antes de conhecer o Lisp, eu também tive medo. Recentemente encontrei um caderno datado de 1983 onde eu escrevi:
“Acho de devo aprender Lisp, mas parece tão diferente.”

Felizmente, na altura, tinha 19 anos e não tinha muita inércia em aprender coisas novas. Era tão ignorante que aprender fosse o que fosse significava aprender coisas novas.

As pessoas amedrontadas pelo Lisp inventm outras desculpas para não o usar. A desculpa usual, na altura em que C era a linguagem mais comumente utilizada, era que o Lisp era demasiado lento. Agora que os dialectos do Lisp encontram-se entre as linguagens mais rápidas ao nosso dispôr, essa desculpa desvaneceu.
Agora a desculpa usual é circular: que outras linguagens são mais populares.

(Cuidado com este raciocínio: leva-nos ao Windows)

A popularidade tem sempre o poder de se renovar indefinidamente, especialmente quando estamos a falar de linguagens de programação. Mais bibliotecas são escritas para as linguagens mais populares, o que as torna ainda mais populares. Os programas necessitam recorrentemente de cooperar com programas já existentes, e isto torna-se mais fácil se estiverem escritos na mesma linguagem, logo as linguagens espalham-se de programa para programa que nem um vírus. E os ‘chefes’ preferem linguagens populares, porque dá-lhes mais flexibilidade sobre os programadores, que são mais facilmente substituidos.

Na verdade, se as linguagens de programação fossem mais ou menos equivalentes, não existiria grande justificação para não usar a mais popular. Mas não são equivalentes, nem de perto, nem de longe. E é por isso que as linguagens menos populares, tal como os romances da Jane Austen, continuam a sobreviver. E enquanto todos os outros estão a ler o último romance de John Grisham, existe sempre alguém, mesmo que poucos, a ler Jane Austen.

February 23, 2006

ANN: New Beta of SchemeUnit

Posted in Lisp, Programming, Scheme at 11:18 am by pmatos

SchemeUnit, the scheme unit test package developed by Noel Welsh arrives to a new beta.

Thanks Noel.

Another beta. Same place:

http://schematics.sf.net/schemeunit.plt

Install using

planet -f schemeunit.plt schematics 2 0

Remove previous betas using

planet -r schematics schemeunit.plt 2 0

What’s new? A conversion script from 1.x to 2.0 (in
plt/convert.ss) Nothing else you’re likely to notice unless
you hack on SchemeUnit.

There are three items left on my TODO list. I’d appreciate
feedback from interested parties.

1. Make define-assertion also define the shortcut test-X
form. A good idea, but at the moment I lack the energy to
fight with syntax-case. (Note that the shortcut name is
irregular in, for example assert-equal? => test-equal? but
assert => test-assert)

2. Change the pompous name assert to the more friendly
check. Requires lots of code changes.

3. Use the contract language to define checks on values.
This is a very good idea. However 1) it requires lots of
reworking of SchemeUnit, 2) it requires deep understanding
of how the contract system works, and 3) possibly makes
portability difficult.

N.

December 9, 2005

Teaching Mathematica as First Programming Language…

Posted in Computers, Education, Lisp, Mathematics, Programming, Scheme, Uncategorized at 1:57 pm by pmatos

is worse than shooting yourself in the foot… worse than shooting yourself in the head… is like shooting a whole bunch of students in the head, his friends, parents and colleagues. I would better call it a genocide.
From the wikipedia definition of genocide:

Genocide is (…) Killing members of the group; Causing serious bodily or mental harm to members of the group; Deliberately inflicting on the group conditions of life calculated to bring about its physical destruction in whole or in part; Imposing measures intended to prevent births within the group; and forcibly transferring children of the group to another group (…)

Students learning Mathematica as a first programming language are most probably mentally mutilated beyond hope of regeneration. In what follows I will explain why this is so.

During my degree in Software and Computer Engineering I had the possibility to learn programming in various languages like C, C++, JAVA, and some more eccentric languages like Scheme, Common Lisp and Mathematica. During the last years teaching Programming Fundamentals in Scheme as a first Programming Language in Software and Computer Engineering and following students from the Mathematics Department which learn Mathematica as a first Programming Language I’ve noticed the following differences:

  • Mathematica does not ease teaching students Programming Techniques, while Scheme does.
  • Mathematica makes it hard to teach good programming styles while the PLT Scheme approach makes it much easier.
  • Mathematica makes the learning of abstract datatypes (ADTs) extremelly difficult, while Scheme mostly enforces it.
  • Mathematica makes it even more awkard the teaching of orders of growth while Scheme does not.
  • Usual Programming Concepts like Interpreter, Compiler, REPL are not easily taught to students using Mathematics. PLT Scheme makes them explicit.

Now, I’ll try to detail each of the previous items in more detail.

Programming Styles

A beginning programmer needs, more than usual, that tools work on his side. No need for highly extensible, general-purpose, do-all tool (that’s why in general everyone works in windows, and why no beginner starts programming in emacs). If they are learning a programming language they already have a steep curve to go through, no need for another one to learn about an editor or how pretty-print stuff, indent or anything else.

Mathematica interface goes against these principles. Its interface is highly problematic, counter-intuitive and ugly. No help source colouring is provided and paren-matching functions are as simple as they can be. Check the snapshot!

  • It’s hard to keep track of what each parentheses close;
  • No colouring at all;
  • No support for indentation – the code is indented automatticly but if you for some reason miss the indentation and destroy the automatic indentation (remember, they are only beginners) it’s hard to get it back in place;
  • Copy-pasting the code can get a harsh job due to newline problems, etc… (I was never able to understand these issues)

Now, for your delight, check for example a PLT Scheme snapshot.

ADTs

One thing which is particularly annoying in Mathematica is its uses of lists. Students learning Mathematica know surely all of the following functions for lists: PreppendTo, Preppend, Append, AppendTo, Length, First, Rest and [[_]].

Lists are a very good datatype but one that should be used with care not to shoot yourself in the foot. The major problem is Lists in Mathematica are not Lists. Lists in Mathematica are vectors, uni-dimensional tensors, and what makes things more irritating is that they are called lists. Check the following copy-pasted from Mathematica 5.1 help on List:

- {e1, e2, ...} is a list of elements.
(...)
- {a, b, c} represents a vector.
- {{a, b}, {c, d}} represents a matrix.
- Nested lists can be used to represent tensors.

Geeez, check the first line, oh it’s a list of elements… some lines below… it’s a vector… 2 lines below, oh no, nested lists…

This will not make sense of any student and imagine what a beginning student will learn from this? Lists and vectors are probably the same. Which is utterly incorrect!

From the Dictionary of Algorithms and Data Structures on list:

Definition: A collection of items accessible one after another beginning at the head and ending at the tail.

And on vector (also known as 1D-array):

Definition: A set of items which are randomly accessible by numeric index.

So, definitely this is a vector. How we really know the Mathematica list is a vector and not a list? Check next section on orders of growth.

This seems like a stupid non-sense that any student may go through without any problem but it is not true. Mathematica students learn talk about lists and which is ultimately worse, “think” about lists when they really mean vectors. And these are basic ADTs, every other ADT knowledge will come distorted because of this.

One can think:

Oh, no big deal, I can explain my students that lists and vectors are one. There are list functions and vector functions that work exactly on the same datatype (which is true).

You can explain this fact and probably 40% (at best) of them will understand but this will not help. When they get to learn other programming languages like C++ (which have separate STL List and Vector), Common Lisp, Scheme, etc, etc, etc… they won’t understand.
Using Mathematica and getting used to the fact that lists and vectors are the same will make them bad programmers for the rest of their days and will mutilate them and everyone who this person might teach.

Orders of Growth

Although we do not teach our students much about orders of growth in a first programming languages course, we do mention about the computational cost of some function and the computational cost of each ADT we use. However, we do know most students in their first project are eager to make them as computationally efficient as possible so that it’ll run faster than of most of their colleagues, not knowing that:

Premature Optimization is the Root of all Evil!
— Donald E. Knuth

Imagine that a student A is asked to define a function in Scheme that given an ordered list of numbers and a number (which is known to be in the list) should return the position (1-based) of the element in the list. A smart student will try to make is run as fast as hell so it uses a neat trick:

  ;; Returns the position of a given element in an ordered list.
  ;; (give-element '(2 3 6 8 15) 8) => 4
  (define (give-element-fast l n)
    (define (aux l i)
      (let* ((len (length l))
             (mid-pos (inexact->exact (ceiling (/ len 2))))
             (n-element (nth l mid-pos)))
        (cond (( n-element n)
               (aux (take l mid-pos) i))
              (else 
               i))))
    (aux l 1))

(defined nth and take for Scheme, almost as defined in Mathematica to resemble [[_]] and Take, which for Schemers is Take is take when receives a positive argument and drop when receives a negative argument. Code is in the end of this blog post.)

This is a usual recursive function with no-side effects that will as fast as possible try to compute the position given the fact that the list is ordered. A simple-minded student B will do in Scheme:

  ;; Returns the position of a given element in an ordered list.
  ;; (give-element '(2 3 6 8 15) 8) => 4
(define (give-element-slow l n)
    (let loop ((l l) (i 1))
      (if (= (first l) n)
          i
          (loop (rest l) (+ i 1)))))

Let’s make the same students define these in Mathematica. So student A:

GiveElementFast = Function[{l, n},
      Module[{lst, i, len, midpos, nelement},
        lst = l;
        i = 0;
        len = Length[lst];
        midpos = 1;
        nelement = Infinity;
        While[nelement != n,
          len = Length[lst];
          midpos = Ceiling[len/2];
          nelement = lst[[midpos]];
          If[nelement 
Let's take a bunch of benchmarks now.</del>(In fact I did take some benchmarks but unfortunately, posting them along the post would take more time than it should and the results are intuitive.)
What happens is that the time to search a list in Scheme with the Fast Procedure is much larger than the Slow one, and in Mathematica happens exactly the opposite. This is exactly due to the fact that Mathematica Lists are vectors and the Fast Procedure is only really fast if the datatype is a vector since getting an element from a list is O(n) and getting an element from a vector is O(1) (which means that getting an element from a list is done in linear time with the size of the list, and constant in the size of the vector). So, in fact, the approach student B took when developing the functions was the correct one since he probably new the orders of growth in list access, what he didn't knew and that's why his approach fails in Mathematica is that Mathematica cheats you when talking about lists. Student A approach although wise with vectors is naive with lists and or he knows he is working with vectors in Mathematica (which is rarely the case if we are talking Mathematica as a first programming language) or he gets is fast just by luck. Either case, something is wrong and potencially confuses the student. Mathematica is great for symbolic manipulation, data plotting and programming of rather simple software prototypes but extremelly bad to teach programming concepts. Seems simple and straightforward to those programming in Mathematica for a long time but cannot see the damage they are inflicting to their students.

<strong>License</strong>

And of course, there are the license issues. Mathematica is cross-platform but also is PLT-Scheme and many others. However, if you find a bug in Mathematica 5.1 (for example, the extremelly annoying bug of numlock not working ok on Linux Systems) you have to wait for the next release (probably a couple of months), if you find a bug in an open source free system you contact the developers and probably in less than a day they put online a binary version of the software working as you wanted to.

<strong>Last Comments</strong>

Surely Mathematica is not useless. Mathematica is a powerful symbolic manipulator with a nice embedded Programming Language, still using it for a course on Programming as a first Programming Language should be considered a criminal offense, and those enforcing its use should revise the course or accept the death penalty.

<strong>Other Code</strong>
Nth:

(define (nth l n)
    (if (= n 1)
        (first l)
        (nth (rest l) (- n 1))))

Take:

(define (take l n)
    (define (take-aux l n)
      (if (= n 0)
          ()
          (cons (first l)
                (take-aux (rest l) (- n 1)))))
    (define (drop l n)
      (if (= n 0)
          l
          (drop (rest l) (- n 1))))
    (if (> n 0)
        (take-aux l n)
        (drop l (- n))))

September 28, 2005

Um Portal de Scheme

Posted in Computers, Education, Lisp, Portuguese, Scheme, Uncategorized at 2:33 pm by pmatos

Tenho desde o início do meu blog publicado anúncios e ideias sobre Scheme aqui. Agora terminou… não os anúncios mas sim os anúncios aqui. O Portal de Scheme está oficialmente inaugurado e em constante construção.
O endereço é: http://sat.inesc-id.pt/~pocm/scheme_portal

Divirtam-se!

September 7, 2005

Learning Lisp…

Posted in Lisp, Uncategorized at 11:37 pm by pmatos

It seems that some people are interest in learning Lisp… Good News, huh?

April 20, 2005

Structured Lispy Syntax on SAT Competition

Posted in Lisp, SAT, Uncategorized at 11:16 pm by pmatos

I am just amazed to see the benchmarks posted on the SMT-COMP’05 homepage! And you know why?
Well, take a look at a benchmark, don’t you just recognize the syntax? :D Of course… it’s Lisp. Parsing it with Lisp would be a walk in the park. However, mostly due to the fact everyone thinks Lisp is not the fastest ‘language’… (and you can be sure we need the fastest in SMT-COMP) mostly all software is programmed in C or C++. Would this format provide an excuse for a team to use Lisp? I am curious about it.

Now, a question also comes to my mind. Even for those using C or C++, using Guile to parse the format and then passing it to C would be really nice I think. Oh well, let me just study this for the next few days and I’ll post more about this later…

Note: Note the ‘…’ surrounding “language” above. When I say most people think Lisp is not the fastest language, I mean most people think that current Lisp (Common Lisp, Scheme…) compilers do not generate the fastest executables.