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.

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.

**Welcome to the 2015 version of the course!**- Here are links to diagrams about:
- The review of math is available, although not complete (as of Wed 21 Jan); more to come soon!
- Here are the “chunking” exercises for those who are new to Haskell.

*(labs to be posted as they are assigned)*

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. For example, you can try haskell out in your browser, including a nice set of guided lessons and exercises.

You might also want to take a look at a tutorial or two from
this list
at the Haskell Wiki pages. I especially recommend the book, available
on-line for free,
*Learn You a Haskell for Great Good* (complete with cartoons).

You also might want to download an implementation for use on your own machine;
there is a fully-featured, multi-platform version available as
**the Haskell Platform**;
it includes an industrial-strength compiler and a bunch of libraries.

On the other hand, we really don‘t need all this power, so you might want to get the simpler

- If you use a Mac, try this MacHugs installer which uses the command line (Terminal app) under Mac OS X.
- For Windows, try the WinHugs installation.
- For other operating systems (e.g., Linux), look for Hugs installers at this page.

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.

**Math review**We will need some basic background in set theory and related topics (orderings, functions, relations and some basic logic) as a foundation for later work. You should have some exposure to this material already, but I will work (quickly) through some review notes (to be linked above) in lecture. You can also read about some of the same topics at Wikipedia:

- top-level set theory links
- functions
- countable sets
- cardinality
- relations
- equivalence relations
- partial orderings
- Boolean algebra

**Sets, domains and types**- Wikipedia on Domain Theory
- Wikipedia on Denotational Semantics
- Math usage of "image"
- Math usage of "domain" (
**not**as in "domain theory") - Wikipedia on Abstraction in CS
- Wikipedia on Semantics of Programming Languages

**Some references on symbols (Unicode and semiotics)**- The Unicode home page
- Wikipedia on Unicode
- Joel Spolsky (software pundit) on Unicode
- A unix/linux Unicode FAQ
- A free on-line Unicode character map
- Wikipedia on grapemes versus glyphs
- Wikipedia entry on semiotics
- Semiotics for Beginners by Daniel Chandler

**Formal languages, finite automata and regular expressions**- Wikipedia on Formal Languages
- Wikipedia on Finite State Machines
- Wikipedia on Context-Free Grammars
- Wikipedia on the Chomsky Hierarchy
- Wikipedia on Formal Grammars
- Wikipedia on Parsing
- Wikipedia on NFAs

**Tries and related data structures (reifying functions on strings)****Lambda calculus, types and type theory**- Lambda calculus - Wikipedia, the free encyclopedia
- SKI combinator calculus - Wikipedia, the free encyclopedia
- Church encoding - Wikipedia, the free encyclopedia
- Type system - Wikipedia, the free encyclopedia
- Typed lambda calculus - Wikipedia, the free encyclopedia
- Curry-Howard - Wikipedia, the free encyclopedia
- Intuitionistic Type Theory - Wikipedia, the free encyclopedia

**Some references on the Collatz ("3n+1") problem**