Language, Logic and Computation
News Labs Handouts Haskell References Miscellany

About the course

This is the homepage for CS 465: Language, Logic and Computation), a course offered by Fritz Ruehr at the Computer Science Department of Willamette University. The course develops formal languages from the perspectives of logic, mathematics and computer science, but emphasizes semantics of programs, in contrast with the traditional treatment of formal languages as sets of strings. It is organized as a tour of successively enriched object languages and of the meta-linguistic techniques needed to rigorously describe them.

Topics addressed may include: • broad issues in langauge and formalisms; • finite symbols sets and their encoding; • numerals and number notations; • the hierarchy of number types; • algebraic expressions and polynomials; • abstract algebraic theories; • denotational and operational semantics; • traditional formal languages via grammars and automata; • declarative variables, polynomials and scope; • imperative variables and state-based semantics; • and lambda calculus and type theory.

The style of presentation will be influenced by functional programming, category theory, and the Curry-Howard correspondence and the Squiggol school of constructive programming (catamorphisms, anamorphisms, etc.); Haskell is used as an implementation meta-language.

The official course description reads:

Language is the basic for complex communication, whether as natural language between humans or as formal language between humans and computers. In programming, different kinds of formal languages are crucial tools in all stages of development, from the logics used to specify requirements, to the programming languages used to implement algorithms and the mathematical notations used to analyze their behavior. In this course we will study the general phenomenon of formal language by exploring the syntax, semantics and logics of a broad range of examples, beginning with the simplest numeral notations and operator algebras and continuing through to computationally complete languages and sophisticated type systems. In addition to studying abstract descriptions of syntax and semantics, students will reinforce their understanding by implementing language-based tools in a functional meta-language.


Labs (in rev. chron. order)

Handout archive

I will try to make some of the class hand-outs available here in PDF format when I have the time.

Haskell resources

We will be using the Haskell programming language as our primary meta-language and implementation vehicle. There are plenty of on-line resources on Haskell, how to use it, downloadable implementations, etc.

You might want to take a look at a tutorial or two from this list at the Haskell Wiki pages.

You also might want to download an implementation for use on your own machine:

Or you might want to get the simpler Hugs system we use in the lab:

Some topical references

We won't be using a formal textbook this semester, so I will be trying to gather links to relevant on-line material. A lot of good-quality articles are available on Wikipedia, the free on-line "open source" encyclopedia.

Miscellaneous links

Here are a few fun, interesting or otherwise difficult to categorize links that are obliquely relevant to the course.