About me

About me

Feeds

RSS feed

Lisp problems site

5th October 2016

I've recently been playing with the idea of a website that presents a series of Lisp problems, to help people learning Lisp. It will present a description of the problem, and allow the user to post their answer. The program then tells them if they've got it correct.

The interesting question is: how do you check whether the user has got a problem correct?

Lisp interpreter

One approach is to provide a Lisp interpreter on the server, and execute the user's answer to check that it produces the correct result. This wouldn't be a problem for me, since the web server I'm using, CL-HTTP, is itself written in Lisp. However, how do you ensure, for example, that the user doesn't answer the question:

Find the largest four-digit Fibonacci number

with:

(defun fib4 () 6765)

There are also security implications with allowing the user to run arbitrary Lisp code on the server, so for these reasons I decided against this approach.

Provide all possible alternative solutions

The second approach is to try to provide a list of all conceivable solutions to the problem, and check the user's answer against each of them. However, after a bit of thought it's soon clear that this won't work. For example, in the answer to:

Find the nth Fibonacci number

the user can write:

(defun fib (n)
  (if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))

or can replace n with any symbol they like. Furthermore, even with this simple problem there is a wide range of variations that are essentially identical; for example:

(defun fib (n)
  (if (= n 0) 1
    (if (= n 1) 1 
      (+ (fib (- n 1)) (fib (- n 2))))))

or:

(defun fib (n)
  (cond
   ((zerop n) 1)
   ((= n 1) 1)
   (t (+ (fib (- n 1)) (fib (- n 2))))))

The number of variations soon mushrooms into a very large number.

Unify solutions

The solution I've finally decided on is to unify the user's answer, and then compare this with the unified solution, or if necessary, multiple alternative solutions.

The unify stage performs several substitutions to convert the solution into a standard form. Here's a list of some examples:

  • Parameters to defun, let, and let* are converted to a standard set of symbols ?1, ?2, ?3 etc.
  • The constructs if, when, and unless are converted to the equivalent cond construct.
  • Functions with synonyms, such as first, second, and rest are converted to car, cadr, and cdr etc.
  • Forms such as (+ var 1) or (+ 1 var) are converted to (1+ var), and likewise for (- var 1).
  • Arguments to commutative functions, such as + and *, are arranged into a consistent order.

Ultimately for this to work better I would need a Lisp code walker, but for simple problems what I have now is working satisfactorily. If I fail to find a match I give the user the benefit of the doubt and reply:

You've come up with an original answer and we'll need to check it.

A site moderator could then check the answer, and if appropriate, use it to improve the unify procedure, or add it as an alternative answer.

Update

9th February 2017: The Lisp problems site is now live:

http://www.lispq.com/

I'd welcome any feedback, or suggestions for new problems.


blog comments powered by Disqus