Language, Logic and Computation
About the course
This is the homepage for
CS 451: Special Topics (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 include
basic semiotic issues;
finite symbols sets;
partial and total functions;
the combinatorics of compound symbols;
natural numbers and numerals in positional notation;
algebraic expressions and theories;
traditional formal languages via grammars and automata;
declarative variables, polynomials and scope;
imperative variables and state-based semantics;
while programs and fixed-points;
lambda calculus and combinatory logic;
and type theory.
The style of presentation is influenced by functional programming, category theory,
the Curry-Howard correspondence and the Squiggol school of constructive programming
(catamorphisms, anamorphisms, etc.);
Haskell is used as an implementation meta-language.
News
- There is now a set of notes on review for the final posted
(I will hold a special review session closer to the final, time and day TBA)
- Here are some references on Monads:
- See the revised version of the expression/statement combination (with
uniform environments and numeric values) in the
Prog.hs file (including the imperative
computation of 2 to the 10th example).
- The Haskell code for converting DFAs to regular expressions is in the file
REConv.hs; other code files you might
want for exam study are in the same directory
and in the code directory.
- Check out Oliver Steele's
regular expression visualizer (edit the pattern itself on the upper left,
input on the upper right)
- The new lab on parsing regular expressions is up;
there is also a final version
of the midterm review posted (now with extra chewy goodness and
fully expanded outline!)
- in lecture on Weds to Fri (22-24 March) we discussed choices for
representing regular expressions and DFAs in Haskell and some different
semantic spaces we might use for REs (lists of strings, nested lists of
strings, DFAs, predicates, etc. An interesting question arose about using
dynamic programming techniques for the semantics of the Kleene star operator.
The relevant Haskell file is
RegEx.hs
We also (on Friday) reviewed a presentation about parser combinators
and peeked at monads. You might want to read
this paper by Hutton and Meijer on monadic
parser combinators over break (especially if you weren't in class ...).
- in lecture on Friday (17 March) we explored the use of folds over expressions with
a distinguished variable to implement evaluation, pretty-printing, calculation
traces and conversion to polynomials. We also saw how to parse directly to a
semantic domain by using a parser parameterized by semantic functions. You can
see the code in these three files:
Expr0.hs (simple start);
Expr1.hs (parsing, tracing);
and Expr2.hs (full version).
- the latest lab is: Regular Expressions and Finite Automata,
now due on after Spring Break
- the just previous lecture notes are:
Algebraic Expression Languages;
we will start on formal languages on Mon 27 Feb
- I have sketched out a sample HTML presentation of
polynomial calculation traces
- I have begun (but not finished) a short
explanation of Haskell type classes
- you can look up Haskell functions (and functionality) with Neil Mitchell's
Hoogle
Labs (in rev. chron. order)
Lectures (in rev. chron. order)
These lecture notes are under development and there are currently significant
gaps. Each lecture should ultimately link to sample code files.
Topical references (in rev. chron. order)
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 (you might want to consider donating some portion of your textbook
savings to their efforts).
- Lambda calculus, types and type theory
- Formal languages, finite automata and regular expressions
- Tries and related data structures (reifying functions on strings)
- Sets, domains and types
- Some references on the Collatz ("3n+1") problem
- Some references on symbols (Unicode and semiotics)
- Math review (for lecture, Jan 23-25)
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:
Haskell references
We will be using the Haskell programming language as
our main implementation vehicle. There are plenty of links there about the
language, how to use it and some implementations (check out the wiki in
particular for programming advice).
Handout archive
I will try to make some of the class hand-outs available here in PDF format when I have
the time.
“Pop culture”, Haskell advocacy and miscellaneous links
Here are a few fun, interesting or otherwise difficult to categorize links that came up
in lecture at various points.
- 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.
- Haskell, Epic Games and Unreal Tournament: here's a presentation on
the next mainstream programming language by
Tim Sweeney,
CEO and Chief Architect of Epic Games, creator of Unreal Tournament and
the Unreal game engine, about how Haskell, advanced type systems, proofs
of programs and other topics in this class are crucial to the gaming
architectures of the future.
- Sweeney interview: just for good meaure, here's an interview
Sweeney did about
programming language issues for games
(this was in January 2000, before he'd been completely bitten by the Haskell bug
☺ ).
- Haskell in perspective: you might also want to read one of the
Haskell designer's talks to the same audience, a few years before,
giving a retrospective on the Haskell language.
- A proposed draft syllabus for a CS Discrete Math course.
- The abyss (in Alan Moore's Promethea comic,
as analyzed in Eroom Nala's exegesis.
- For what it's worth, here's a link to the old course homepage,
in case I forgot to transfer anything over.
