Computer Aided Exercising in Prolog and SML

Dávid Hanák - Tamás Benkő - Péter Hanák - Péter Szeredi

Budapest University of Technology and Economics, Hungary

{dhanak,benko,hanak,szeredi}@inf.bme.hu

Abstract:

This paper introduces a fully computerized, web based interactive system which enables students of Computer Science at the Budapest University of Technology and Economics to do simple exercises in two declarative programming languages, namely Prolog and SML. This system works as a part of a comprehensive teaching support environment that supports both the students and the teachers of the Declarative Programming course.

1 Introduction

In the Declarative Programming course we teach Standard ML and Prolog for $4^\mathrm{th}$ semester students of Computer Science at the Budapest University of Technology and Economics (BUTE).

In the first three semesters students learn several imperative programming languages including Pascal, C and C++, they also get some basic training in x86 assembly, and later on they become familiar with Java and SQL. On the other hand, this single semester course is the only opportunity for them to learn about declarative thinking in the context of programming.

It is a commonplace that programming requires practice, but how can students be forced to exercise their skills? One way is to give laboratory exercises but unfortunately we run short both on human and technical resources. The number of students attending the course has increased from about 100 to more than 400 per semester in the last eight years, while the staff consists ``only'' of two lecturers and two PhD students. To tackle the problem we developed several tools to facilitate the work of lecturers, and an interactive web-based program incorporating an extensive exercise database which allows students to practice 24 hours a day. These pieces of software have recently been integrated into a comprehensive teaching support system called ETS, an Environment for Teachers and Students.

The rest of this paper presents a sketchy design of ETS and reports its current state, describing the exercise system in detail.


2 An Environment for Teachers and Students

Because of the high number of students, it is vitally important to have as many auxiliary tasks automated as possible, such as the evaluation of assignments and exercises. Supporting the lecturers by lifting the burden of administrative tasks is also a relevant question.

This recognition lead us first to the implementation of several independent programs handling these tasks, and finally to the integration of these pieces of software into a comprehensive teaching support system called ETS (a Hungarian acronym). The best English equivalent of this acronym is Environment for Teachers and Students. The design of ETS has been laid down in [1] and the system is currently under development.

The ETS consists of loosely connected components linked to a common database. Some components are already in use, others are unfinished yet, and still there are some which only exist in the plans.

One component provides an interface to the database for users with various privileges. Another component is responsible for managing assignments: this includes reception of the programs, running the tests, evaluating the results and notifying the students. A third component is an interactive exercise system designed especially for the needs of programming courses. The initial version of this component was reported in [2].

The latter two components will be introduced in the rest of this section.


1 Managing Assignments

Assignments consist of several simple programming tasks and a single complex problem issued in each semester. Points received for the solutions add up to the examination scores.

Along with each task we provide a testbed, a submission script and a set of test cases. The testbed contains procedures/functions for parsing test cases and pretty-printing solutions, so that the students do not have to bother with this and can fully concentrate on the algorithm. A very similar testbed is used for testing the solutions on the server-side, too. The submission script--running on Unix-like systems--must be used to hand in the programs via e-mail. This way we ensure that the students are properly identified (the script requests that the sender name be selected from a list), and also that all submissions use the same attachment format. The server automatically evaluates the submitted program, stores the results in the database, and sends a verbose log to the student.

An HTML form is also available for students who--being unfamiliar with Unix systems--may have problems using the submission script.


2 The Exercise System

The exercise system offers several types of exercise problems to the students, receives and checks their solutions. In case of an erroneous solution it reports the errors and offers re-editing. The system also follows and registers the progress of students by making statistics.

At the design of the exercise system, we had the following objectives in mind:

In order to avoid overwhelming the students with exercises they cannot solve, the problems are gradually made available by the system, following the course curriculum. The first exercises the students encounter are very simple and require only the most basic skills in both languages. Then--as the semester goes on--they assume deeper and deeper knowledge.

In the rest of the section, we describe those topics of the course material which are supported by the exercise system, and then we discuss some aspects of implementation of the system.

1 Exercise Topics in Prolog

1 Standard prefix notation.

First the students must get to know how Prolog parses expressions, what are the atoms, compounds and operators. This is best practised by letting the students themselves do the work of the Prolog parser: the task is to specify the canonical form of an expression.
[1]#0QA: 1QA:
a(2+3*5,b(1-2,4))
[1]#1QA: 2QA:
a(+(2,*(3,5)),b(-(1,2),4))

2 Lists

are fundamental in all declarative languages because of their recursive structure that suits recursive algorithms well. Therefore it is a must to understand how they are built. The canonical form expresses the recursiveness well, but using syntactic sugars may hide it. In this exercise the students must find the canonical form of list expressions.
[1]#2QA: 3QA:
[2+3,[1]|T]
[1]#3QA: 4QA:
.(+(2,3),.(.(1,[]),T))

3 Unification.

When the notion of canonical form is clear, attention must be paid to the unification of expressions containing variables. The students, given two expressions, must tell whether unification succeeds or fails, and in case of success what values the variables will assume.
[1]#4QA: 5QA:
[3+Y|Z] = [X+4*5,X].
[1]#5QA: 6QA:
success, X = 3, Y = 4*5, Z = [3]

4 Equational operations.

The four types of equations: unification (=), identity (==), arithmetic evaluation (is) and arithmetic equality (=:=) can be quite confusing for someone just learning Prolog. These exercises help understand the main differences between these predicates. The task is again to tell whether the call succeeds, fails or signals an error, and in case of success what values the variables will assume.
[1]#6QA: 7QA:
X is +(1,2), X =:= 10//3.
[1]#7QA: 8QA:
success, X = 3
[1]#8QA: 9QA:
X is 5//4, X == 5//4.
[1]#9QA: 10QA:
failure

5 Control.

The next step is to introduce control structures like the cut (!), the conditional (-> ;), and the negation (\+). The question is the same as above.
[1]#10QA: 11QA:
U is 21/6, (U < 3 -> X is 3-U ; X is U-3).
[1]#11QA: 12QA:
success, U = 3.5, X = 0.5
[1]#12QA: 13QA:
X = 2, \+ \+ X = 1.
[1]#13QA: 14QA:
failure

6 Backtracking

is of course the most powerful feature of Prolog. Students have to understand how a nondeterministic program is executed, how clauses are tried, what happens at cuts and in conditionals. In this type of exercise a small set of predicates is given, and the students have to tell what solutions are enumerated in the variable(s) of a specified call.
[1]#14QA: 15QA: 
p(1, 1).  p(3, 1).  p(_, 2).

q([H|T], A) :- p(H, A).
q([H|T], A) :- p(T, A).

| ?- q([1,2,3,4], X).
[1]#15QA: 16QA:
X = 1; X = 2; X = 2

7 Programming.

When the students can handle all of the above ``basic ingredients'', they are asked to write simple predicates. The problem is specified by giving the head comment of the predicate, and some examples.
[1]#16QA: 17QA: 
% adj(+L, ?Sum, ?A, ?B): A and B are adjacent elements
%   in the L list of numbers, and their sum is Sum.

| ?- adj([2,3,1,4], 5, A, B).
A = 2, B = 3 ? ;
A = 1, B = 4 ? ;
no

8 Built-in predicates.

As soon as they can write simple predicates from the scratch, it is time to start using built-in and library predicates. This is again the usual success/failure/error type exercise.
[1]#17QA: 18QA:
append(X, _, [1,2]), X = [_|_], !.
[1]#18QA: 19QA:
success, X = [1]

9 Meta-logic

predicates perform operations that require reasoning about the current instantiation of terms (such as atom/1 and ground/1) or decomposing terms into their constituents (functor/3, arg/3 and =../2). The question is the same as above.
[1]#19QA: 20QA:
functor(X, +, 2), X =.. [_,1,2|_].
[1]#20QA: 21QA:
success, X = 1+2
[1]#21QA: 22QA:
X =.. [_,1,2|_], functor(X, +, 2).
[1]#22QA: 23QA:
instantiation error

2 Exercise Topics in SML

1 Basic types and values.

The first thing students learn about SML is that it has a strong type system. They find out about primitive data types (like int and bool), the corresponding value sets, simple operators and functions manipulating these data, and how these values can be coupled into tuples. In the first exercises they are given a tuple containing basic expressions and have to specify its type and value the SML interpreter would give.
[1]#23QA: 24QA:
SPMamp("pi"^"e", 4 mod 2, 1<>0)&
[1]#24QA: 25QA:
SPMamp("pie", 2, true) : string * int * bool&

2 Lists

are naturally also important in SML, but the syntax is somewhat different from that of Prolog. Students learn how lists can be constructed with the cons (::) operator, how to use syntactic sugar, and also hear about the append (@) operator. Exercises at this stage ask the same kind of question as above, only for lists.
[1]#25QA: 26QA:
SPMamp[2.1, 4.2] @ real 3 :: [abs( 1.7)]&
[1]#26QA: 27QA:
SPMamp[2.1, 4.2, 3.0, 1.7] : real list&

3 Understanding simple functions.

The next step after learning about the basic data types is to come to know the most important SML construct, namely the notion of the function, and to learn about pattern matching and conditional constructs. Students also have to recognise (as yet monomorphic) function types. In these exercises we ask the type of a function or the return value of a function call.
[1]#27QA: 28QA:
SPMampfun f (c,s) = explode (s ^ str c)&
[1]#28QA: 29QA:
SPMampf : char * string -> char list&
[1]#29QA: 30QA:
f as above, SPMampf (#"e", "pi")& = ?
[1]#30QA: 31QA:
SPMamp[#"p", #"i", #"e"] : char list&

4 Writing simple functions

on your own stimulates constructive thinking already at this early stage. Students are given the specification and type of a function, and have to implement it.
P: 
(* sum xs = the sum of integers in `xs'
   sum : int list -> int
 *)
sum [4,6,3] = 13

5 Lambda notation

comes up as the canonical form of function definitions. These examples ask either the type or the value of an expression containing a lambda function.
[1]#31QA: 32QA:
SPMampval f = fn (s,c) = str c ^ s&
[1]#32QA: 33QA:
SPMampf : string * char -> string&
[1]#33QA: 34QA:
SPMamp(fn x => x*x) 2&
[1]#34QA: 35QA:
SPMamp4 : int&

6 Polymorphism.

Since students already know about lists and tuples, it is reasonable to teach them how they can handle such constructs in general, without knowing the type of their constituents in particular. Here we ask
[1]#  $\bullet$   $\bullet$
the type of a function with specified body;
[1]#  $\bullet$   $\bullet$
a possible body with given type and head;
[1]#  $\bullet$   $\bullet$
a function definition given its specification.
[1]#38QA: 39QA:
SPMampfun f x ls = length ls > x&
[1]#39QA: 40QA:
SPMampf : int -> 'a list -> bool&
[1]#40QA: 41QA:
SPMampf : 'a list -> 'a list * 'a&
SPMampfun f (x::xs) =& ?
[1]#41QA: 42QA:
SPMampfun f (x::xs) = (xs, x)&
P: 
(* lgr (l,ls) = `ls' is longer than `l'
   lgr : int * 'a list -> bool
 *)

7 Datatype declarations.

The ability of constructing user defined data types (like binary trees) is a very strong feature of SML. The task here usually is to write a function operating on a predefined data type.
P: 
datatype ('a, 'b) union = A of 'a
                        | B of 'b
(* split xs = (as,bs) where `as' is the list of all A values,
              `bs' is the list of all B values from `xs'
   split : ('a, 'b) union list -> 'a list * 'b list
 *)

8 Lazy and eager evaluation.

Students learn quite early that the evaluation strategy of SML is eager, but there are a few exceptions when lazy evaluation is used. These are the logical operators (andalso, orelse, if-then-else) and the function definition, where the body is evaluated only on calling the function. The goal here is to call their attention to this feature. An expression is given with calls to print and printVal, and the output of the evaluation must be specified as an answer.
[1]#42QA: 43QA:
SPMampprintVal 1 > 0 orelse printVal(null [1])&
[1]#43QA: 44QA:
SPMamp1&
[1]#44QA: 45QA:
SPMamp(fn (x,y) => print x) ("app", printVal "le")&
[1]#45QA: 46QA:
SPMamp"le"app&

9 Partially applicable functions.

If we know there is lazy evaluation in SML, we might be interested in delaying some calculations and bringing others forward. This can be solved with curried functions, which come handy in a lot of other situations as well. These exercises ask the type of partially applied functions.
[1]#46QA: 47QA: 
fun f x y = Math.sqrt(x*x + real(y*y))
val g = f 4.0
[1]#47QA: 48QA: 
f : real -> int -> real
g : int -> real

10 Higher order functions.

Eventually students learn about functions that take a function as an argument, like map and foldl. The exercises of this topic ask the type and/or value of expressions containing these functions.
[1]#48QA: 49QA:
SPMampfoldl op o chr&
[1]#49QA: 50QA:
SPMamp(char -> char) list -> int -> char&
[1]#50QA: 51QA:
SPMampmap (fn i => i div 2) [3,4,6,9]&
[1]#51QA: 52QA:
SPMamp[1,2,3,4] : int list&

3 About the Implementation.

In the implementation of the exercise system, we defined the following concepts: Categories can be formed by refining and further partitioning the topics discussed so far. The topics themselves can serve as category groups.

Let us now list the most important schemes:

Prolog schemes
Standard prefix notation:
give the canonical form of an expression
Success/failure/error:
give the result of a call, in case of success also determine the value of a specific variable
All solutions:
enumerate (in proper order) all solutions of a goal, as returned in a specified variable
Programming:
write a predicate satisfying a given specification

SML schemes
Type:
determine the type of a declaration (value or function)
Value:
determine the simplest form of the value of an expression
Function body:
determine the body of a function if the head and the type is given
Type declaration:
define a data type satisfying a specification
Programming:
write a function conforming to a given specification
Checking the exercises is not always simple and calls for tricks to handle every possible error intelligently. First of all the solution must pass a syntactical test and only then can we move on to the semantical test, which in turn may consist of more rounds. Often the solution has to be tested against minimal requirements and then checked whether it is not over-specific.

For example, to check that the type of an SML declaration is really what the student told and not more generic, we wrap the declaration and the type into a structure.

structure expr :
  sig val y : correct type end =
struct
  declaration of x
  val y : type guess = x
end
This way the message of the SML interpreter is different if the type is altogether wrong or if it is just over-specific.

To check Prolog standard prefix notations, an appropriate DCG parser has been included in the system.


3 Conclusions

We described that the increasing number of students presents a problem we faced by introducing automated tools in exercising, evaluation and administrative tasks. These tools have been integrated into a comprehensive teaching support system called ETS. We briefly presented the main components of ETS, and discussed the exercise system in greater length.

1 Acknowledgement.

Thanks are due to all students who have helped us in the implementation of the ETS and its ancestors, especially to Lukács Tamás Berki and András György Békés for their work on the exercise system.

Bibliography

1
Dávid Hanák: Computer Support for Declarative Programming Courses (in Hungarian), 2001, MSc Thesis, see also http://dp.iit.bme.hu:4321/

2
András György Békés, Lukács Tamás Berki: A Web-based Exercise System for Programming Languages (in Hungarian), 2001, Students' Conference, Budapest, Hungary

3
Péter Hanák, Péter Szeredi, Tamás Benkő, Dávid Hanák: ``Yourself, my lord, if no servants around'' - A Web Based Intelligent Tutoring System (in Hungarian), 2001, NETWORKSHOP01, Sopron, Hungary

Hanák Dávid <dhanak@inf.bme.hu>