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.
The style of presentation will be 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.
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.
(This course is a rather idiosyncratic approach to a revised CS Theory curriculum;
but the general topic is not without some precedent, as evidenced by, e.g.,
the Tbilisi Symposium on Language, Logic and Computation,
the Institute for Logic, Language and Computation at Universiteit van Amsterdam
(also here),
the Journal of Language, Logic and Computation,
the book Algebras, Diagrams and Decisions in Language, Logic and Computation,
the breadth studies program in Language, Logic and Computation at The University of Melbourne,
the Centre for Logic, Language and Computation at the University of Melbourne,
the workshop Language, Logic, and Computation in Honor of Prof. Nachum Dershowitz,
the The Association for Logic, Language and Information,
and the Workshop on Logic, Language, Information and Computation, among others.)
News
Welcome to the Spring 2019 teaching of the course!
- Just to be clear, homework solutions for the Turing Machine questions
are posted here.
Fritz will be available, at the following times and dates to provide
extra help and “demo” labs, in the Ford 202 CS lab:
Wed., May 8th, noon-2:00 (or 3:00) pm;
Tue., May 14th, noon-2:00 (or 3:00) pm.
(The timing specs mean: I'll be there between noon and 2:00 for sure, and
will stay as late as 3:00 if there is continuing need.)
- A homework assignment on Turing Machines and computability is
here.
Adding soon: … and the solutions will soon be posted …
here.
- The final exam study guide is located
here.
- You can find the
code for the Lambda Calculator here, in both
“raw folder” format and also in a
_.zip file, for convenience.
- During lecture, we may want to refer to this
very old lab on combinators.
And, as long as we’re here, this is
the Wkipedia page on combinators.
- What it looks like when higher-order function grids fall down.
- Here are some outline-formatted notes on lambda calculus (study-guide style):
notes on lambda calculus.
- A homework assignment on lambda calculus and combinators is
here.
Added later: … and the solutions are now posted
here.
- … and some outside reading materials on lambda calculus:
- Study for the midterm exam using
these midterm exam review notes.
Note: review now upgraded with links!
- Homework 3 on Regular Languages
(REs and DFAs) is now available!
- Announcement! I think we need to push back the date of
the Midterm Exam: I will discuss this in lecture on Weds. 13 March,
so come to class if you wish to help make the decision!
Update! So the class has voted to move the
Midterm Exam until after Spring Break, specifically
to Wednesday 3 April (see lecture
for more details).
- Homework 2 on Numbers,
Numerals, and Polynomials is now available!
- Lab 3 on Regular Languages
is now available!
- Here is a
quick summary of regular language definitions (now updated!),
including REs, DFAs, and NFAs
… and here are the
hints about the state-ripping transformation from NFAs to REs.
… and, finally, you can find a broad summary “road map”
of the various concepts and constructions involved here:
regular languages roadmap.
- For Monday 4 March, we have a quick follow-up
diagram on univariate polynomials and then an overview
diagram of architecture before we dive into a section
on regular expressions (see some actual code here)
(… and expect a new lab soon, before the midterm).
- Here is a very short example in the “experimental” format,
showing what a tracing calculator for polnomials might look like:
traced polynomial.
- Here is the code for polynomials, where
we add variables to our arithmetic term structures.
Note that there
are some slight naming differences: our fold from
Lab 1 on FAST types is here called
foldx, whereas the App constructor is
called Bop, for ‘binary operator’.
(Plus, as discussed in lecture, we drop
exponentials/functions here, so just constants, sums, and products
… plus variables!).
- … and here is a cartoon
to celebrate adding variables to expressions.
- I’m not sure how useful these will be, but here are:
(Both of these are written in an experimental style, with regular
“diffs” of the code as they progress; the second
experimental lecture is also still woefully incomplete.)
- According to popular vote, the
midterm exam
has been scheduled for Monday 18 March; a midterm
review sheet will be posted beforehand and we will spend
at least one day during lecture just doing a review.
- Here is some Haskell code for
Smullyan's dyadic numerals and
Fritz's prime factor representation …
and the numbers from 1 to 1,000 in prime factor form.
- Here is the pictures for
unfolding numbers into strings (i.e., numerals).
- A “written homework” assignment on
FAST types and grids
is now available.
- Here is the link I can never find to that nice
little Haskell Diagrams tutorial.
- … and here are some notes and diagrams about
construing grid operations as repetitions
and
the whole FAST architecture.
- Lab 2 on Discrete Probability Distributions
is now available!
- Quick links for lecture:
-
Some old news items from earlier teachings of the course are
“below the fold” (i.e., the blue line).
Lab write-ups, homework assignments, and hand-outs will appear in the
appropriate sections below as they become available.
New news items will be added to the top, as we go along,
so that the most recent ones appear first.
- Here are links to diagrams about:
- Here are some diagrams about
tallies derived from biased choice and
binary codes derived from balanced choices.
- Here is the Spectrum of Language diagram.
- Lab 1 is now available!
- For starters,
here is the Spring 2019 syllabus
(I will also give you a paper copy in class on the first day).
Hereafter starts the old news part of the section …
- Study for the final exam using
these final exam review notes.
... and check out this list of skills.
- Here is the promised paper on the phenomenon of reflection in various
systems, including biology (DNA and protein structure), linguistics, and
lambda calculus (see esp. pages 1-10):
Reflection and its Use
by Henk Barendregt.
- Some links on combinators (variable-free theory of functions):
- Just for fun:
The Mathematician‘s Alphabet
(from lab).
- According to this article in the research journal of the
British Psychological Society, we
think more rationally in a non-native language.
Shirley,
this must have implications for the psychology of formal languages.
- Once we’re done with the midterm, we will take a look at this
application of “folds-as-compositional-semantics” to
print out full truth tables (which would have been helpful for
doing and grading homework and exam problems):
TTable.pdf.
- The midterm is still being graded; hopefully
it will turn out better than
the 2011 midterm.
- Some materials on monadic parser combinators:
- For Friday, March 6, we’ll clean up loose ends on semantics
for algebraic terms, including polynomial function semantics and
propositional logic; see these files:
(Perhaps we should also consider porpositional logic,
which concerns reasoning about the location of dolphins … .)
- Materials on terms with variables and (polynomial) function semantics
are in this file:
PolyL15.hs.
- Some links for lecture (Wed 25 Feb):
- Regarding algebraic terms, see
this diagram and
these notes.
(Plus, see this diagram re last lecture.)
- Get the latest lecture/outline
here
… and
here is the code file for Peano-style natural numbers (or Nats).
- Some links for lecture, Wed 18 Feb 2015:
- Here is a
quick summary of regular language definitions,
including REs, DFAs, and NFAs.
- Here are the
hints about the state-ripping transformation
from NFAs to REs.
- Slight (or is it “sleight”?) change of plans: we will
move right from [Symbols, strings, and sequences] to [Regular languages],
topically speaking. You can find a broad summary “road map”
of the various concepts and constructions involved here:
regular languages roadmap.
- You can read the details of the UTF-8 encoding scheme for Unicode characters at
Wikipedia page on UTF-8;
you might pay special attention to the
technical description
and the “salient features” bullet list that follows. Since the encoding
is pretty straightforward, but also technically adept (and cute/slick), I will
include it amongst the skills I allow myself to test on exams.
- Here are the “chunking” exercises for those who are new to Haskell.
Labs (in rev. chron. order)
Handout and homework archive
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.
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 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 some review notes (to be 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
- Some links at Wikipedia relevant to logic:
