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.

**Welcome to the 2013 version of the course!**

(new news below in reverse chronological order).- Study for the final using the Final Exam Study Guide and look here for a overview of the Lambda Calculus.
- Look here for the polynomial code.
- Here's a link to that “functional pearl”
paper on monadic parsing
by Graham Hutton and Erik Meijer from the
**Journal of Functional Programming**.

*(See especially the example in Section 8.)* - There is a
preliminary version of the midterm review here;
I’ll try to fill out the details before Sunday so you can ask informed questions
during Monday’s review session (exam on
**Wednesday**). - Powerpoint presentations (by Graham Hutton) and videos (by Erik Meijer), and code, all centered around Graham Hutton's Haskell text, can be found here; especially relvant in the next few days are the ones from Chapter 8 on parser monads.
- Here's Wikipedia again, on syntax diagrams, a more visual/diagrammatic way of representing CFGs
- Some links from Wikipedia about various grammar classes (you can find more, and more relevant ones, if you research it yourself ...):
- Here are some links from other classes and elsewhere giving sample context-free grammars (in BNF notation):
- You can find the code for “ripping” an RE out from a DFA here, and some notes on reducing sample results along with it.
- Lab 4 (dice rolls and DPDs) is now posted!
- Look here for hints on transforming DFAs to regular expressions.
- More handy links, now for lecture material on types and algebras:
- the two diagrams on punch-hole types;
- a(n older) lecture on algebraic terms;
- an(nother older) lecture on positional notation in that same style;
- see especially this slide on
`divMod`

and`sumProd`

.

- Lab 3 is now posted!
- Handy links for the lecture on folds, unfolds and positional notation:
- Here are some links into Wikipedia articles on topics we‘ll want to have handy as we move into the realm of natural and other numbers:
- Josh made a great suggestion in lab, that I go over some larger Haskell
example in detail to explain the programming process. I happen to have
just such a thing lying around from one semester of the Intro. Functional
course, so here is a detailed discussion of
the design of a
`segment`

function that breaks up a list based on a relational argument. (Several designs are considered, based on my own ideas and those of students in that class.) - And here are some little tidbits about the dangers of recursions, namely
Steven Colbert on
*One DIrection*lyrics (yeah, I know: a re-post) and some further analysis by Jesse Galef at*Measure of Doubt*. - I wrote up some Haskell code implementing sequences as pairs of lengths and functions which may make those ideas more concrete.
- Here is the Wikipedia page on the fold function, and here is the recipe for folds diagram.
- Here are a few exercises about expression “chunking” (or grouping), from the
Intro Functional class. I won't be collecting or grading them, and there are solutions on the second page of the PDF.
They may be helpful in getting used to the way Haskell syntax works.

Notice that the use of parentheses is often minimized in those examples: it usually helps when you're starting out to add a few extras, which is good for emphasis and confidence. - I may want to refer to this Math Stack Exchange discussion when talking about ordered pairs and their encoding in set theory.
- If you need some refreshers on set theory, see this Wikibook on Discrete Math or the links in the References section below.
- Here's an interesting picture about the perception of Haskell among programmers from an on-line course about Haskell (also possibly of interest).
- Here are the
Spring 2013 course syllabus
and the
Spring 2013 calendar
*(tentative!)*(in PDF format).

- Lab 5 (on monadic parsing) is now available.
- Lab 4 (on dice rolls and DPDs) is now available.
- Lab 3 (on folds) is now available.
- Lab 2 is available.
- Lab 1 is now posted!

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

*(For now, see the past class archive)*

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:

- There is a fully-featured, multi-platform version available as
**the Haskell Platform**; it includes an industrial-strength compiler and a bunch of libraries.

- If you use a Mac, try the 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 the review notes 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**

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

- Here's a science fiction story by Isaac Asimov you can read for free, on-line,
which takes an amusing look at a future in which humans rediscover
how to manipulate symbolic representations by hand (in contrast to using computers):
The Feeling of Power.
**Folds, maps and Google**: you can read a paper (with lots of source code) by Ralf Lämmel on how Google uses FP techniques.