Lambda the Ultimate

Computational thinking is a fundamental skill for everyone, not just for computer scientists. To reading, writing, and arithmetic, we should add computational thinking to every child’s analytical ability. Just as the printing press facilitated the spread of the three Rs, what is appropriately incestuous about this vision is that computing and computers facilitate the spread of computational thinking.

Computational thinking involves solving problems, designing systems, and understanding human behavior, by drawing on the concepts fundamental to computer science. Computational thinking includes a range of mental tools that reflect the breadth of the field of computer science.

from Jeannette M. Wing's Computational Thinking Manifesto

The Center for Computation Thinking at CMU has more information about the subject.

We talked briefly about Computational Thinking back in 2006. Recently I listened to Jon Udell's interview with Jeannette Wing and realized that it's time to bring this subject up again for discussion.

Hello All

(I hope this forum is the appropriate place to ask)

I'm working within GCC on a Lisp translator (from some Lisp dialect, called MELT, to C) to be used for GCC middle end analysis; the motivation is to be able to code GCC middle end analyzers & passes in my Lisp dialect.

The code is updated several times a day on the GCC SVN. See MELT for details (or ask me).

The lisp dialect is not really documented yet. The major difference is that MELT has both boxed and unboxed values. Also, most primitives are not called as in Lisp (but most control operators are the same, let is somehow a let*, ...). Primitives are described by giving their expansion to C. MELT files have a *.bysl extension (because MELT was called Basilys at first).

The MELT dialect is a lisp like dialect (a Lisp1 in C.Queinnec terminology), with dynamic types and lexical scoping (a la Scheme).

Here is the familiar 2nd order function to map a function into a list.

(defun list_map (lis f)
  (if (is_list lis)
      (if (is_closure f)
	  (let ( (reslis (make_list discr_list)) 
		 (curpair (list_first lis)) )
	    (forever lisloop
		     (if (not (is_pair curpair)) 
			 (return reslis))
		     (let ( (curelem (pair_head curpair)) )
		       (list_append reslis (f curelem)))
		     (setq curpair (pair_tail curpair)))
	    ))))

In the code above, defun if let forever return setq are "keywords" ie have a special significance to the compiler. is_list is_closure make_list list_first not is_pair pair_head list_append pair_tail are primitives (expanded to some C code). lis f lisploop reslis curpair curelem are locally bound names and the function list_map is globally defined by the defun

Here is the not (boolean not, on unboxed longs) and is_list (on values) primitive:

(defprimitive not (:long i) :long "(!(" i "))")

(defprimitive is_list (li) :long
  "(basilys_magic_discr((" li ")) == OBMAG_LIST)")

The first :long occurrence in not before i tells that formal i is an unboxed long, and the second :long occurrence tells that the result of not primitive is an unboxed long.

The is_list primitive definition tells that the result of is_list is an unboxed long, and how to expand it into C. The quoted strings are actually C code fragments appearing in the generated code.

Lists in MELT are not just pairs. A List is actually a structure keeping the first & the last pair of a linked list of pairs.

First, some fact about my implementation (available on GCC SubVersion repository in the MELT branch).

I'm working within GCC, closely following the trunk (future 4.4)

I have a runtime, which means a garbage collector & various primitives coded in C. See files gcc/basilys.c & gcc/basilys.h - it is debugged well enough to be able to run many minutes. (BTW debugging a garbage collector is a nightmare). MELT garbage collector is built above the existing GGC collector in GCC.

I have a cold translator, coded in Common Lisp (CLISP actually). File contrib/cold-basilys.lisp. It is able to translate some MELT code *.bysl into *.c ; I do know it is buggy, but I want to maintain it as little as possible. Conceptually the only purpose of this cold translator is to be able to handle warm-basilys.bysl below

The real stuff is the warm translator, in file gcc/melt/warm-basilys.bysl it is translated by CLISP running cold-basilys.lisp to coldbuilt-warm-basilys.c & coldbuilt-warm-basilys.so (a plugin dynamically loaded by my cc1 - the C compiler proper of gcc).

my cc1 with the above generated coldbuilt-warm-basilys.so is able to translate (except bugs) any *.bysl file into *.c (so it does the same work as cold-basilys.lisp, but in principle better, and coded in MELT). in particular it is able to translate itself, ie warm-basilys.bysl into warm-basilys-1.c etc..

my cc1 with warm-basilys-1.so is able to generate warm-basilys-2.c from the same warm-basilys.bysl. Sadly, warm-basilys-2.c is not the same as warm-basilys-1.c (it should)

my cc1 with warm-basilys-2.so produces warm-basilys-3.c from warm-basilys.bysl. warm-basilys-2.c & warm-basilys-3.c are identical (but buggy).

The buggy bootstrap (with warm-basilys-2 & warm-basilys-3 identical but buggy) actually happenned in svn rev135845

I am chasing a meta-bug, in the following sense.. The function pairlist_to_multiple in warm-basilys.bysl near line 2183 is incorrectly translated by warm-basilys.bysl (actually by coldbuilt-warm-basilys.so) - founding that one of the badly translated function is this one is non trivial. It behaves differently in coldbuilt-warm-basilys.so (works ok there) and in warm-basilys-1.so (incorrectly returns nil).

I am experimenting that chasing metabug is challenging, and quite difficult.

Do you have horror stories, hints, insights, theoretical papers, personal experiences, about these?

How do you find such metabugs? (it is meta in the sense that the generated code behave wrongly).

Regards.