CIS 554 Study Guide for Final Exam
      (And second Scala quiz)
Fall 2011, David Matuszek

Notes

General concepts

Recursion

What are Dr. Dave's four rules for recursion?

Anything that can be done recursively could also be done iteratively. For what sorts of problems is recursion the simpler solution?

What data structure or structures are required to implement recursion?

What is tail recursion and why does it matter?

Functional languages

What is a functional language, anyway? There's no one universally accepted definition, but there are a number of important characteristics you should know.

Why are functional languages only now coming to center stage, after decades of being of “academic interest only”?

What is a persistent data structure?

What are the basic characteristics of the map, filter, and reduce/fold operations? Can most higher-order functions be classified as one of these? How do these operations relate to list comprehensions?

Why are lists strongly preferred over arrays in functional languages?

Concurrency

You should understand three models of concurrency: shared state with synchronization, STM (software transactional memory), and actors.

Understand: threads (compare to processes), blocking, locks, synchronization, deadlock, livelock, race conditions, starvation, asynchronous function calls, mailboxes, atomic operations.

What is wrong with the check-then-act pattern?

Important concepts from Prolog

Prolog depends heavily on unification. You should know how to unify structures of all kinds.

Unification is similar to pattern matching in Scala. You should understand the similarities and differences.

What is the difference between monotonic logic and nonmonotonic logic? How are these expressed in Prolog?

What is the resolution principle? In resolution, what is a clause? Be prepared to solve (small) problems using resolution.

Backtracking is built into Prolog. How does that work? How is it affected by a cut?

What is a predicate? Does this word mean the same in Prolog as it does in other languages?

What does it mean to say that Prolog is a declarative language?

Important concepts from Erlang

We didn't spend much time on Erlang, but it had a huge number of important concepts. Almost all of these concepts were later incorporated into Scala, with very similar syntax. What one major concept occurs in Erlang that doesn't appear in Scala (at least, in the parts of Scala we studied)?

Important concepts from REBOL and Clojure

What is a homoiconic language?

What are the advantages of having a simple, uniform syntax? What are the disadvantages?

Important concepts from REBOL

(Sigh) What is the importance of having a good online support group?

(BTW, the REBOL site with all those wonderful examples, with source code you can see and edit, is back up again. Spend 10 minutes with it, just for fun; I bet you'll be impressed.)

What is REBOL rebelling against?

What are the three kinds of “things” in REBOL? How is each of those things different from the equivalent things in more conventional languages?

How is a REBOL statement evaluated? More specifically, if foo bar baz quux is a legal statement in REBOL, where the names refer to some mix of functions and variables, how is it interpreted?

Give arguments for and against this statement: “REBOL is a functional language.”

Important concepts from Clojure

What is the syntax of a function call, and how does it differ from the syntax for a list of values? (This is the only syntax you need to know.)

What are the differences between functions, special forms, and macros?

What is a DSL?

It is said that macros add considerable power to Clojure (and other versions of Lisp). What do macros allow you to do that is essentially impossible in Java?

What is a lambda?

What is a sequence, and what are the most important operations on sequences?

What is metaprogramming?

Important concepts from Haskell

What is lazy evaluation? What is it good for?

What is currying?

Important concepts from Scala

How does pattern matching work? What are the various kinds of patterns that can be matched? Where can pattern matching be used?

What is the Option type? In what way is this an improvement over Java?

What does the use of val instead of var prevent the program from doing, and what doesn't it prevent the program from doing, with the variable being declared?

Are all the object types in Scala arranged in a hierarchy, as in Java? If not, how are they arranged?

Does every Scala method return a value? Does every Scala statement return a value?

Important concepts from Ruby

What is a closure?

Second Scala Quiz

You should be familiar with the concepts and the syntax of: