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.
News
- 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:
- 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).
Labs (in rev. chron. order)
- 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!
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:
- There is a fully-featured, multi-platform version available as
the Haskell Platform;
it includes an industrial-strength compiler and a bunch of libraries.
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.
- 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:
- Sets, domains and types
- Some references on symbols (Unicode and semiotics)
- Formal languages, finite automata and regular expressions
- Tries and related data structures (reifying functions on strings)
- Lambda calculus, types and type theory
- Some references on the Collatz ("3n+1") problem
Miscellaneous links
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.
