CSC324 — Content

A peek into my preparations for the course

Don't get scared: these are not prerequisites for taking the course, nor a course outline. These are my explorations that will be pared down and distilled into a course, but that some students have expressed interest in hearing about already. My 2006F site is probably a better indicator of what the course will be like. The most obvious difference will be learning logic programming gradually now in Scheme, instead of jumping into Prolog (see Logic Programming below for the benefits).

Necessary History

The first successful machine-oriented (1950's machines) language (for a vanishingly (over time) small domain: numerical recipes), was made by Backus. He made the programming profession, but did the profession keep up with machines (exponentially more, cheaper, faster, bigger), and the increasing number of domains they were being used in? By the 1970's the profession was clearly behind, to anyone who knew it well (and of course didn't just learn CS from the programming profession!).

Textbooks

Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman.

Programming Languages: Application and Interpretation by Shriram Krishnamurthi.

The Scheme Programming Language by R. Kent Dybvig.

Algorithms + Data Structures = Programs

Tree-structured Data

Prerequisite from CSC148/150/236/240/207 (including recursion).

Notations: Terms (from grammar theory), S-expressions, XML, JSON. (Examples in the blue box)

Source code syntax

Introduction to Context Free Grammars and parsing.

Semantics from syntax: post/pre-order traversal (from prerequisite courses), as calling modes in languages (call-by-value function vs other operations).

Pattern Matching

• On strings (sequences): regular expressions.
• On structures/terms: destructuring values by type in ML/Haskell (standard Scheme library); unification in Prolog (see "Logic Programming" above).
• On trees, semi-structured data: recursive destructuring (see previous); catamorphisms (Scheme IU-Match library), term rewriting (Stratego, Scheme library and one support library for users); XPath, XQuery, etc.

Lambda Calculus

As a game.

Call-by-XXX; Macros to express

Why is if not a function in most languages? Why can't conditionals be put in a library in most languages? Example: a useful conditional I added to to my library: if-differ.

Logic Programming

The course historically uses Prolog to illustrate logic programming, partly because follow-on courses use it. If it wasn't used in other courses, I would consider more seriously another logic language for pedagogical (and maybe productivity) purposes. But it's not a big deal: the three main concepts Prolog combines can be used and studied (first) independently (e.g. in scheme).

The deepest concept is backtracking search, which McCarthy (inventor of Lisp) first described as the "ambiguous choice" operator "amb" of his 1963 paper "A Basis for a Mathematical Theory of Computation". It's also discussed in the 1980's undergraduate CS textbook "Structure and Interpretation of Computer Programs", as "Nondeterministic Computing". Here is a minimal implementation in scheme, though the main point for 324 is the clarity of explicit usage (examples to follow) separated from the other unusual aspects of Prolog. For production use there are amb libraries for many schemes, e.g. in PLT.

The second concept is unification, a quite general form of pattern matching. A unifier in scheme.

The final concept is pass by reference of logic variables.

References:

• The Reasoned Schemer by Daniel P. Friedman, William E. Byrd and Oleg Kiselyov
• Sokuza Kanren
• Schelog
• Research papers from "Embedding Logic Programming in Scheme"
• Dan Friedman's "Poor Man's" Logic System for Scheme with first-class relations

Various Design Patterns

The example that made some instructors and students go "Wow", and finally get what programming can/should be.

Continuations; web app control flow

Continuations are a core control-flow abstraction, from the 1970s. In particular, they are now used in continuation based web servers to support servlets: PLT scheme servlets and the web server. SISCweb.

Macros

E.g. capturing "recurse on only some variables".

"Breaking hygiene".

"Are macros really useful?".

Parallel, Distributed, Concurrent

Schemik.

Language Oriented Programming, Domain Specific Languages (DSLs), Little Languages (LLs)

A book. His "simple example". A simpler way. Strange, because he knows where he should be looking.

Relational Databasing: SQL, Relational Algebra, Datalog

SQL.

Relational Algebra (see CSC343).

Datalog.

Regular Expressions

Structured notations: Dorai Sitaram's pregexp, Olin Shiver's SRE implemented in Alex Shinn's IrRegular Expressions.

Traditional unstructured notation: included in the previous, and in PLT.

Some Languages

ML (maybe Haskell)

Mainly for static type inference. Also functional programming, currying and pattern matching. Or Haskell for lazy evaluation as well.

The Little MLer (by one of the PLT Scheme people).

Currying in PLT Scheme: for function definition (e.g. my rewrite framework above uses it), and as higher-order function.

JavaScript

You learn it in CSC309. From the ECMAScript (ECMA standard version of JavaScript) 4 specification:

ES3 is a simple, highly dynamic, object-based language that takes its major ideas from the languages Self and Scheme.

By the way, in case the lack of mention of Java is surprising: the naming of JavaScript was a marketing ploy (that I remember unfondly) between Netscape and Sun to increase mindshare for both, with advertising of one increasing 'awareness' of both by confusing the names.

The Little Javascripter.

Scheme

Reminding myself about an old book (1998) Programming and Meta-Programming in Scheme by Jon Pearce.

Language interoperability

See CSC 488 for now.

Web Programming Language Issues

Twitter in PLT Scheme.

Some of what I'm reading.

Indiana's CSC 311 Resources.