Archaic Code Contest in Common Lisp

[Tom]

This idea has been bouncing around in my head for a while. I'd like to propose an annual contest called

Archaic Code Contest in Common Lisp

I propose that it be held every October. The task for the contest will be released on the first of October and the deadline for entries is the last day of October. The goal of the contest is fun which is achieved by limiting the programming constructs to "Archaic" functions like CAR and CDR and perhaps only lists as data structures.

The first step is to define the allowable Common Lisp data structures, conditionals, iterative functions and access functions. Generally, I think data structures should be limited to lists. Macros should *not* be allowed because then people would just Greenspun "Modern" Common Lisp functions. Simple conditionals like IF are allowed, but I'm not sure COND is "Archaic" enough. What about iteration, should DOLIST be allowed or only recursion? Basically, I want to limit the allowable forms to the bare minimum "Archaic" forms while still enabling interesting problems to be solved. I'm going to do a little more research into what qualifies as an "Archaic" form.

Once we've hashed out what are the allowable forms, we can start discussing the types of problems to pose for the contest. Looking forward to everyone's thoughts. I'll try to collect my thoughts more, incorporating any ideas from responses, and follow this post up in a few days with better defined rules for the contest.

Cheers,

Tom

[Harleqin]

COND is even more archaic than IF. If I recall correctly, John McCarthy put COND as the basic branching construct into the first Lisp.

[gugamilare]

I once saw a CL tutorial (but it was in Brazilian Portuguese) in which there was some interesting exercises similar in idea to this contest. It allowed you to use only defun, if, zerop, 1+, 1-, cons, car and cdr, and told you to define all common operations with integers and rationals (+, -, *, /). The functions cons, car and cdr was only used when defining rationals. The result, off course, isn't fast, but it works.
They were interesting exercises, it is nice to do abstractions, but doing big things this way might be just painful.

[findinglisp]

If you really want to do this right, you should limit yourself to the fundamental forms defined in "Recursive Functions of Symbolic Expressions and Their Computation by Machine." This was THE original paper that defined Lisp, written by John McCarthy in 1960. Of course, using those fundamental forms you can define all of modern Lisp (which was sort of the point of the whole paper ).

[jrigler]

So is it trivial to create an environment where you don't have the possibility of cheating? From what I understand you could add what you wanted to make available to a package and just tell people not to use anything outside of it. Seems like it should be ok to create macros. If you have someone with a cpan / asdf approach to everything, even defining their own fundamental macros could be a liberating experience. I am pretty sure I couldn't create 'loop' from scratch anytime soon.

[gugamilare]

If you really want to do this right, you should limit yourself to the fundamental forms defined in "Recursive Functions of Symbolic Expressions and Their Computation by Machine." This was THE original paper that defined Lisp, written by John McCarthy in 1960. Of course, using those fundamental forms you can define all of modern Lisp (which was sort of the point of the whole paper ).

! I've never seen this. I'm almost crying .

[Paul Donnelly]

Surely use of PROG has to be encouraged.

[tayssir]

Maybe you can get unofficial style points for using the old formatting style. I kid you not, old books often contain something like:

Code: Select all

(DEFUN has_thing (elem)
  (
   SUBSEQ elem r_top (PLUS
                  my_bottom
                  your_top)
   )
  )

It makes me appreciate how standardized modern Lisp education is. It's rare to see anything like that nowadays; and only from the occasional newbie or experienced AI type.

And they didn't restrict themselves only to CAR and CDR. I knew someone -- in the 21st century no less! -- who passed variables everywhere like so:

Code: Select all

(defun a ()
  (declare (special a g_STZ filename))
  (setf filename "c:\\Documents and Settings\\bob\\Desktop\\gnrd.txt")
  (b))

 (defun b ()
   (declare (special a g_STZ filename))
   ...)

The funny thing is, people get flamed on usenet and IRC for much less. (Actually, independent thinking gets you flamed, but that's another story.)

[Tom]

If you really want to do this right, you should limit yourself to the fundamental forms defined in "Recursive Functions of Symbolic Expressions and Their Computation by Machine." This was THE original paper that defined Lisp, written by John McCarthy in 1960. Of course, using those fundamental forms you can define all of modern Lisp (which was sort of the point of the whole paper ).

Thanks for the reference. This is what I was thinking of. I'm going to go through it and compare what's defined with what is in CL.

So is it trivial to create an environment where you don't have the possibility of cheating? From what I understand you could add what you wanted to make available to a package and just tell people not to use anything outside of it. Seems like it should be ok to create macros. If you have someone with a cpan / asdf approach to everything, even defining their own fundamental macros could be a liberating experience. I am pretty sure I couldn't create 'loop' from scratch anytime soon.

It is not trivial. I think this would be a secondary benefit of the contest, trying to create an environment that would not allow cheating. It could be the basis for deploying a "secured" REPL. Based on the discussions I've seen related to creating a limited environment in CL, the consensus seems to be you cannot rely on packages, you have to intercept and validate all commands. I've not looked into this in detail, but did recognize it as an issue.

The "secured" REPL concept has spawned a second contest idea, to break the "secured" REPL. That might be much more interesting. The contest could be in 2 parts. In the first part, a team defines a "secured" REPL with a specified set of operations. In the second part, the adversary team tries to break out of the "secured" REPL. Initially, stick with one implementation, then down the road try the contest on multiple implementations.

They were interesting exercises, it is nice to do abstractions, but doing big things this way might be just painful.

The idea is that the challenge would be just big enough to be interesting/entertaining/thought provoking, but not so big as to be painful.

Maybe you can get unofficial style points for using the old formatting style.

Definitely style points for archaic formatting.

~ Tom

[gugamilare]

If you really want to do this right, you should limit yourself to the fundamental forms defined in "Recursive Functions of Symbolic Expressions and Their Computation by Machine." This was THE original paper that defined Lisp, written by John McCarthy in 1960. Of course, using those fundamental forms you can define all of modern Lisp (which was sort of the point of the whole paper ).

Thanks for the reference. This is what I was thinking of. I'm going to go through it and compare what's defined with what is in CL.

So is it trivial to create an environment where you don't have the possibility of cheating? From what I understand you could add what you wanted to make available to a package and just tell people not to use anything outside of it. Seems like it should be ok to create macros. If you have someone with a cpan / asdf approach to everything, even defining their own fundamental macros could be a liberating experience. I am pretty sure I couldn't create 'loop' from scratch anytime soon.

It is not trivial. I think this would be a secondary benefit of the contest, trying to create an environment that would not allow cheating. It could be the basis for deploying a "secured" REPL. Based on the discussions I've seen related to creating a limited environment in CL, the consensus seems to be you cannot rely on packages, you have to intercept and validate all commands. I've not looked into this in detail, but did recognize it as an issue.

Why isn't telling everyone to use only the symbols of a particular package safe? I can't think of a single example, unless, of course, this package provides functions like intern, *package*, read, eval, ... So, if the symbols of a package are carefully defined, I don't see why it wouldn't be safe.