service course in logic and logic programming: crazy?

This coming fall, I'm teaching our department's service course for non-majors. The topic is open, and in the past I've offered a version using Mark Guzdial's Python-based image processing course and another surveying algorithms and algorithm analysis (a la David Harel's Algorithmics).

For this fall, I'm thinking about offering a course introducing programming from the logic programming point of view. The students will, for the most part, have the mathematical maturity of Oregon high school graduates who are afraid of math, which is to say, essentially nothing. Almost none of them will have any background in either programming or logic, and I'll have the standard "fear factor" to overcome, as well.

At a minimum, then, I'll have to include a few weeks on propositional logic before diving in to actual programming. My inclination for programming is to use Prolog, probably the SWI compiler, for its fairly rich standard library. Beyond that, however, I'm pretty much at sea, and would really appreciate some suggestions. I've never taught a logic programming course before (other than as a component in a senior-level PL class), certainly not at such a low level, and this is not, in general, an area of expertise for me.

If you were to teach such a course (or if you have already), what would you consider an appropriate range and ordering of topics? Any ideas for cool applications? Sudoku solvers are a neat possibility: I'd love other ideas. Do you know of similar courses that have been successfully deployed?

Is this idea insane?

The truth table is dead; long live the truth table

Perhaps because many people first encounter logic as a matter of truth and falsity, it may be easier for you to introduce classical logic and its models before moving to Prolog and its proof search. For example, an important idea from logic that people can use in even non-mathematical argumentation is that a valid inference is one that does not have a countermodel, where a countermodel is a model that satisfies all the premises yet not the conclusion. It is not hard to teach people to use a (counter)model search program such as Mace4 (to solve Sudoku puzzles, to schedule classes while avoiding conflicts, etc.). That would be a nice example of declarative programming.

By Chung-chieh Shan at Sat, 2008-05-10 22:50 | login or register to post comments

Wish I could attend

I don't know if it is generally insane, but I sure wish I could take a class like that. Best of luck and please blog reviews of how it went i the hopes of other people being able to embrace and extend your approach elsewhere :-)

By raould at Mon, 2008-05-12 17:36 | login or register to post comments

DSLs and frustration

First, I think you should be concerned that students become frustrated by not being able to build games, GUIs etc. easily. Prolog is good for some things, but other are hard (i.e., reasoning about control flow). Programmers would be less frustrated, since they know other languages that are out there. Non-programmers may feel that you are wasting their time.

One thing you might consider trying, which may be relevant to the above concern but is not restricted to it, is showing how Prolog can be used to build DSLs (see for example the DSL course based on Prolog mentioned on the course page. It is rather easy to use this to produce text adventure games and similar programs.

By Ehud Lamm at Tue, 2008-05-13 06:43 | login or register to post comments

Cultural Shift

It's worth remembering that for most of the current intake text adventures aren't really part of the gaming culture they grew up with[1] - they might recognise a reference to a maze of twisty little passages, but even the graphic adventure was a dying breed by the time they could type. People have this annoying tendency to want to build things like the things they have and use.

I suspect that the web's probably the way to go for interactive programs that feel like something they grew up with. On the other hand, doing that in a first course probably requires a little more unexplained 'magic' in the DSL implementation.

[1] Which probably doesn't include the Interactive Fiction community

By Philippa Cowderoy at Tue, 2008-05-13 10:41 | login or register to post comments

DSLs and frustration

Although I, too, have seen this reaction from students, it hasn't been terribly common, at least not at the "CS0" level. Perhaps that's because the majority of students in the class don't have a clue about programming, and are thus more willing to accept something that looks and feels like other math classes. Not sure. I know that my most successful version of CS0 was the "algorithmics" survey course I did last year, and that course involved, literally, no computer usage.

Further, I'm not sure I'd even want such "real world" materials. Under the hood, GUIs (and graphics of any kind) are so far beyond the abilities of neophytes that they're indistinguishable from magic. That can be alleviated in a proper CS1 class, where the focus is on abstraction and modularity, and where more programming demands can be made of students. In that setting, I think that students are able to accept that construction of such things has a relationship to the elementary programming they're learning. But it does take awhile -- several weeks -- to get them there. I taught a version of CS0 using Python and Mark Guzdial's media materials, and I don't think anyone came away with a sense of the underlying ideas that went deeper than "invoke this magic pixel-reading spell".

In the context of this nascent logic programming-oriented class, where the goal is some mastery of formal logic and its use as a basis for computation (and where both logic and computation will be unfamiliar terms), I think it would be a distraction.

Still, the point is well taken overall, and this is one of my big concerns with putting something like this together. I need applications that are both interesting and tractable. So far, I've only got examples from AI, and perhaps I should just go with that. For some reason, though, that rubs me the wrong way. I hadn't thought of a DSL approach, and that's an interesting idea. Regarding the LtU course page, were you referring to Kathi Fisher's DSL-based PL course?

Except for the interplay with Prolog's control flow, I'm not really worried about the logic part. I took a symbolic logic course my first year of college (successfully), and my fear level in mathematics was about as high as you can get (I had flatly failed Calc I the previous term). That was really the start of all this nonsense for me :-)

I would have to think very hard about what to cut from the traditional full-semester offering, though. Proof theory and most of quantification could go (though I'd probably have to include some of both).

On the other hand, I'd have to add material on induction/recursion, and probably a bit of model theory. Model theory could be very tricky, and an outright disaster if I'm not careful.

By jlasseter at Tue, 2008-05-13 16:58 | login or register to post comments

I was referring to this

I was referring to this course.

More detailed reply to follow...

By Ehud Lamm at Tue, 2008-05-13 17:17 | login or register to post comments

This does look interesting.

This does look interesting. Not sure how I missed it the first time through. Thanks.

By jlasseter at Tue, 2008-05-13 19:24 | login or register to post comments

Problem w Prolog

So far, I've only got examples from AI, and perhaps I should just go with that. For some reason, though, that rubs me the wrong way.
Part of the problem with Prolog is that it is pretty much limited to those kinds of problems, where search, and not too much else, dominate. That's why its so good for puzzles, NLP, etc. Beyond that you start to run into Prolog's limitations: its lack of datatypes (and hence data structures), lack of equality (and hence functions), and nothing comparable to monads which means updates where efficiency matters usually end up being done non-logically (and hence reasoning about such code becomes very difficult). I used to be more of a fan of Prolog but found these limitations, particularly the lack of proper datatypes, to be too restrictive. I heard Mercury deals with some of these restrictions but I've never tried it.

By snedunuri at Fri, 2008-05-16 03:46 | login or register to post comments

Lambda the Ultimate

User login

Navigation