LP (Prolog, Goedel) as a First Language

Appeared in Volume 6/4, November 1993

Keywords: goedel, teaching.

rim@csadfa.cs.adfa.oz.au
Bob McKay
23rd July 1993

Our CS Dept is soon to take a decision on a first language for students (we currently use Pascal). I've proposed either Goedel (my own preference) or Prolog, the other alternatives proposed being C, Ada, or Pascal (we should probably also consider an FP language such as Haskell, ML or Miranda, but there's no point my muddying the waters).

The decision will be made in a decision conference in a couple of weeks, for which the proponents of each option are to provide a 1-page or so summary of the arguments. The inclusion below is my response; I'm posting it:

to request comments and suggestions
in case it's of use to others in the same position

It's written with somewhat of a broad brush - there's only so much detail will fit in a one page summary, and in any case, many of the audience are not familiar with LP languages.

To explain that passage about knowing our students won't use their knowledge for a specific term: we're a university college within the Defence Academy, so we know that the bulk of our students (officer cadets):

don't have daytime computing jobs
after completing their degrees, will have a year's military training and in most cases a further two year service posting before there's much likelihood of any computing-related work.

The Logic Programming Paradigm for the First Language

A Computer Science Department has competing responsibilities to its students:

to train them in current technologies for immediate application in their work
to educate them so that they can adapt to changing technologies

A strong emphasis on the latter relative to the former is one of the hallmarks of a university education. In the case of ADFA, there are good reasons to increase this bias, since we know few of our students will actively work in computing until at least five years after completing their first year. Thus our choice of first language should reflect:

the ease of learning, particularly in the critical early stages
the assistance the language gives in introducing important comuting ideas

1. Logic programming (LP) languages embody ideas with which students are already familiar through mathematics, reinforced by experience they may have with spreadsheets or databases. Specifically, the notion of a variable is the same as the mathematical idea, avoiding the confusion that arises with the different notion of a variable introduced in imperative languages. Equally important, logic programming languages can be first treated as runnable specification languages: the students have only to describe the problem, not provide a solution. Control flow notions can then be gradually introduced as the students gain confidence. With an imperative language, the idea of an algorithm has to be introduced from the outset, when students are already struggling with a plethora of new ideas. Finally, LP systems offer an interactive development environment like that which made Basic so popular (without the attendant language infelicities), combined with sophisticated interactive source-level debugging tools.

2. Logic programming languages provide a graceful introduction to many topics

that imperative languages cannot:

databases: the transition from LP to databases is clean and simple (indeed an introductory database course could easily be taught within an LP language).
formal specification: the transition to a language such as Z is again simple.
compilation: whatever the efficiency issues, compilers can be written in LP languages more cleanly and transparently, and so are paedagogically ideal
program transformation can be readily introduced in most LP languages
concurrency is readily introduced, since sequentiality is only the result of a particular choice of proof procedure, rather than an ad-hoc extension as in most imperative languages (including Ada)

Of the enormous range of LP languages available, two possible choices stand out: Prolog or Goedel. The relationship between the two has considerable similarity to that between C and Ada:

Goedel is far more cleanly and consistently designed, with a clear and concise language specification
Goedel's language design includes support for modularity and concurrency
Prolog is more available and widely used (unsurprisingly, since Goedel is a new language)

Goedel is available on Sparcs and may be portable to PCs; on virtually any platform, there is a range of Prologs available, with some optimised for price or ease of use, and others for efficiency. I personally believe Goedel is inherently far superior to Prolog, and would prefer it as the choice, but recognise that issues of system and textbook availability may favour Prolog in the minds of Department members. I should add that I have been using Goedel solidly for the past few months, and have found the compiler as robust and usable as any other, despite its novelty.

Finally, a comment on a regularly raised issue: that LP systems are slow. While this was once a strong criticism, Prolog speeds have increased dramatically over the years. The best Prolog compilers generate code that is a relatively small linear factor slower than C compilers on simple programs. Moreover, it's probably fair to say that LP (as distinct from Prolog) compiler technology is still developing rapidly, and the gap is still closing, particularly on parallel architectures. And the greater expressive power of LP languages can allow the use of algorithms that are simply too difficult to encode in imperative languages; this is particularly the case with constraint logic programming.

mcovingt@aisun1.ai.uga.edu
Michael Covington
23rd July 1993

Although a strong proponent of Prolog, I would not advocate Prolog as a first programming language. I think there is nowadays a serious danger that CS undergraduates may not have a mental model of what actually goes on inside a computer. Teaching structured C might be better for that purpose.

jlee@cs.cuhk.hk
Jimmy Ho Man Lee
25th July 1993

Why would we want to teach students what goes on inside a computer in a "programming" course? Such topics should be in a computer architecture course or the likes.

A programming course should teach students how to make use of programming languages to solve problems, and maybe some programming concepts as well, but that should be it. Sure, people use C conventionally and that is why they are forced into mixing inside-the-computer stuff in the teaching too.

The idea of LP, and declarative programming in general, is to help programmers avoid having to think in terms of the inner working of computers, such as the von Neumann model, control, etc, in programming. This is a very valuable feature of LP and declarative programming. This should be taught in an early stage during undergraduate education.

However, the issue about using Prolog as a first programming language is still debatable.

paul@cs.keele.ac.uk
Paul Singleton
26th July 1993

I don't know in what ways Goedel addresses Prolog's shortcomings, but ...

Part of the blame for Prolog's lack of acceptance must surely lie with purists who have failed to see the strategic importance of industrialising Prolog, or worse still who have resisted this on the spurious grounds that it compromised Prolog's purity.

As a theorem-prover, Prolog is fairly poor, but as a meta-language for implementing better logic languages, it's great. That is how the purists should regard it: what Prolog really needed (and only belatedly got) was intercallability with 'C' etc, Unix-compatible memory management, clean I/O ('C', like Algol 60, rightly doesn't have any I/O within the language definition, while Prolog is burdened with some dismal stuff), decent garbage collection (atoms included), GUI interfaces etc.

When we sing the praises of Prolog, we should use a language and concepts which the software industry understands (or thinks it does :-): reduced development effort, improved maintainability, greater robustness. We should stress that memory leaks and dangling pointers are impossible: Prolog programs do not crash; that because Prolog is more abstract than 'C', changes to program specifications typically have less impact on Prolog code than on 'C' code, reducing the costs and risks of product evolution (there is greater continuity between the specification space and the implementation space). Please don't tell your bosses that, in Prolog, a specification is an implementation: this is not generally true (except for append/3 :-). Tell him that it is a far better language for software reuse than 'C', thanks to: generic types, ease of writing stateless code, simplicity of cross-reference and dependence model, soundness of memory management. Not all software products are execution-speed-critical; development and maintenance costs are the main worry in many projects, and managers are willing to listen to quantified arguments on behalf of alternative development methods, languages and tools. Unfortunately, Prolog implementations are only just reaching a state of plausibility for general software development.

A challenge: try reimplementing the Unix utility 'rev' in your favourite Prolog. Produce a compact executable which doesn't prompt |: and which handles errors without jumping into a debugger or returning to top level. (Then time it against the 'C' version ...)

alberto@cs.umd.edu
Jose Alberto Fernandez R
28th July 1993

Jamie Andrews writes:
The problem is: what happens when the first-language student gets a bug in her program, and is faced with the Prolog debugger? If she doesn't know anything about stacks, pointers, the debugger "command loop" and so on, she's going to be lost; she will probably have to deduce the existence and significance of all these features herself. Why not teach her about all these things to start with, before she has to use them in Prolog?

The Prolog debuger works at a higher level than that. You never see pointers or stacks. You see Prolog variables, contexts of calls, ancestors of the recursion, etc. All natural concepts if you know the procedural semantics of Prolog (do not confuse with the implementation of the proof procedure).

jamie@cs.sfu.ca
Jamie Andrews
28th July 1993

But I'm not convinced that you can come to an understanding of the procedural semantics, without a fair amount of knowledge about how a computer works. Perhaps I shouldn't have said "pointers", but the students have to get at least the basic ideas of what a tree is, what a stack is, and how backtracking works. We're talking about teaching Prolog before the student gets any of that knowledge.

It's easy for us experts to forget that there was a time when we had to be taught all these concepts. I don't believe I would have understood them before the end of second year.

Has anyone actually tried teaching a logic programming language as a first language? What have the results been like? What difficulties did the students face?

bross@sandcastle.cosc.brocku.ca
Brian Ross
28th July 1993

The first year AI course at the DAI, Univ. of Edinburgh, uses Prolog. This course is often the first exposure to computers and programming for students, many of whom are not CS or AI majors. I don't have detailed information on these students' opinions of Prolog as a first language. But as a TA for the course, I noticed that most students had no problems, while some were lost.

I think one advantage of learning Prolog before conventional imperative languages is that you miss out on the initial conceptual confusion over logic variables and unification, versus imperative variables and the destructive assignment.

paul@cs.keele.ac.uk
Paul Singleton
30th July 1993

The issue is the virtual machine architecture.

Although it's rather late to change the practice, when we talk/write about "programming languages" we really mean virtual machines: the language is just a syntax to represent the initial state of some machine - there's a lot more to it than that, and sadly there is rarely a decent, formal and clear notation to describe machine states other than the initial one: this is left to the designers of debuggers etc.

Incidentally, I think good graphical representations of program execution are important to understanding a "programming language": I, at least, like to visualise the machinery. I think the declarative semantics of pure Prolog are just about teachable without pictures, but the procedural semantics of Prolog and any other practicable language need illustration (maybe they can be defined algebraically, but I don't think they can realistically be taught thus).

I say: teach her about the machinery as necessary to explain procedural semantics, as abstractly as possible, and with a formal graphical/pictorial notation.

gupta@nmsu.edu
Gopal Gupta
3rd August 1993

jamie@cs.sfu.ca writes:
Has anyone actually tried teaching a logic programming language as a first language?

Yes, we have taught LP as a first language. In the experimental project we are involved in we taught a series of 2 courses over 2 semesters to CS 2nd year students that used LP. The students were taught imperative concepts towards the end of the course but by and large the emphasis was on declarative programming. These students will feed into our regular CS courses from the next semester, so we'll get an idea of our success/failure after we see how these students perform in them. One must note that judging the success/failure of such an enterprise is extremely difficult.

The students actually were very happy with the courses, liked them tremendously (but they had nothing to compare the experience to as they were all learning serious programming for the first time). Most students were quite comfortable with the new concepts introduced and had no real difficulties.

If you interested in more details of the project, send email to me (gutpa@nmsu.edu) or to Juris Reinfelds (juris@nmsu.edu).

jwl@miki.bristol.ac.uk
John Lloyd
10th August 1993

Greg Bond asked about the expressiveness of Goedel. In fact, Goedel is far from being a general-purpose theorem prover. As Fergus Henderson correctly points out, it has similar expressive power and theorem proving ability to Nu-Prolog (with the big difference that Goedel is a typed language). The crucial point is that the arbitrary formulas allowed by the language can only occur in the bodies of statements and goals. There is a well-known set of transformations (see Chapter 4 of "Foundations of Logic Programming") which transform programs and goals using the more expressive language back to the standard case where bodies are conjunctions of literals. The theory associated with a Goedel program is the completion of the program, where each statement has the form A <- W, W an arbitrary formula. The logic used by Goedel (polymorphic many-sorted logic) is completely standard (although the polymorphic extension seems partly folklore) and is explained in detail in the appendix to the Goedel book which comes with the latest distribution.

Note that it is possible to encode a general theorem proving task in various ways using the extra expressiveness provided by Goedel. For example, one can use John Shepherdson's result that, for any finite set of first order formulas, there is a program whose completion is a conservative extension of the set of formulas. But an attempt to run this directly will almost certainly flounder because of the limitations of the most commonly used proof procedure (SLDNF-resolution) which is what the current implementation uses. BTW, a general-purpose theorem prover is provided (or at least should be - it's not yet implemented!) by the predicate Prove in the module Theories, but I don't believe this is the point Greg Bond was getting at. See the Goedel book for more details on Theories.

Someone asked earlier if Goedel has a symbolic tracer. Yes, it does and it is similar to standard Prolog tracers. However, it currently doesn't cope well with Goedel's ADT's, as hidden symbols may be displayed directly. We are working on this. My own view is that eventually a declarative debugger will be the preferred method of debugging Goedel programs in most circumstances. We currently have a declarative debugger which demonstrates the viability of this approach, but it is still far from a state that would allow us to release it.

Stephen Cooper asked about making SICStus system calls from Goedel. This is easy enough, although it's not documented as we have yet to provide a foreign language interface nor even to decide what is best to do in this regard. If you want to know more about this, contact goedel@compsci.bristol.ac.uk.

Finally, there have been a few postings on Prolog as a (first) teaching language. Actually, I really think we must widen the debate on this. The real debate should be about a logic programming language as a (first) teaching language. Prolog is one possible choice if only because it is so well developed. But it has obvious and serious drawbacks as a teaching language, so we should be looking at other possibilities.

rim@csadfa.cs.adfa.oz.au
Bob McKay
22nd September 1993

Our CS Dept took a decision on a first language for students: ADA. It will be introduced in 1994.

No Prev