Introduction to the Code Examples

This page gives access to code examples related to subjects covered in COP 4020 at UCF, as taught by Gary T. Leavens. It does not cover concepts, definitions, proofs, and examples of such that are not embodied in code.

Throughout this index, chapter numbers refer to the course textbook, Concepts, Techniques, and Models of Computer Programming, by Peter Van Roy and Seif Haridi (MIT Press, 2004).

See also the Supplements Web Site for the textbook. On that web site you will find a link to source code for all the book's figures, several supplements to the Mozart system (including a set of basic system supplements to be put in your .ozrc file), and links to other Mozart source code.

The examples presented here are (generally) not found in the book (for those, see above), but originate with the course.

For a reference to Oz's syntax and semantics, see Appendix B and Appendix C of the textbook, and the on-line documentation for Mozart. In particular The Oz Notation defines the language and The Oz Base Environment defines the built-in procedures and functions available on various types of data. This documentation also ships with the Mozart installation, and so should be accessible directly from your computer if you have Mozart installed.

Another source of information on Oz's semantics is the Reducer, which embodies the operational semantics of the declarative model as explained in chapter 2. It also has several examples of Oz code, some of which are fairly large examples of following the grammar (as in chapter 3).

Examples

Chapter 1: Introduction to Programming Concepts

1.3: Functions

Write recursive functions on numbers:

ProdFromTo.oz (see also ProdFromToTest.oz)

SumFromTo.oz (see also SumFromToTest.oz)

Sqrt.oz (see also SqrtTest.oz)

Count.oz (see also CountTest.oz)

FibIterative.oz (see also FibIterativeTest.oz)

1.5: Functions over lists

Write recursive functions on lists:

Assoc.oz (see also AssocTest.oz)

ListLength.oz (see also ListLengthTest.oz)

Product.oz (see also ProductTest.oz)

1.8: Lazy evaluation

What is lazy evaluation? Given an example.

FibLazy.oz (see also FibLazyTest.oz)

1.9: Higher-order programming

What is higher-order programming?

CAdd.oz (see also CAddTest.oz)

Compose.oz (see also ComposeTest.oz)

1.14: Classes

What is a class?

Toggle.oz (see also ToggleTest.oz)

1.17: Where do we go from here?

What are the features of the relational model?

FourLetter.oz (see also FourLetterTest.oz)

Chapter 2: Declarative Computation Model

2.3: Kernel language

What is a closure? How would you implement a closure in C or C++?

cadd_corrected.c

cadd_corrected.cpp

2.6: From kernel language to practical language

How do you desugar into the kernel language?

Discrim.oz desugars to DiscrimDesugared.oz

Inc.oz desugars to IncDesugared.oz

How does pattern matching work for function formal parameters?

FunPatMatch.oz (see also FunPatMatchTest.oz)

Chapter 3: Declarative Programming Techniques

3.2: Iterative computation

Write tail recursive functions:

See ProductI in Product.oz (see also ProductTest.oz)

FibIterative.oz (see also FibIterativeTest.oz)

SumFromTo.oz (see also SumFromToTest.oz)

Sqrt.oz (see also SqrtTest.oz)

ArrayFindEqual.oz (see also ArrayFindEqualTest.oz and ArrayFindEqualBodyTest.oz)

ArrayFindGreater.oz (see also ArrayFindGreaterTest.oz and ArrayFindGreaterBodyTest.oz)

A higher-order abstraction of ArrayFindEqual.oz and ArrayFindGreater.oz is ArrayFindMaker.oz. (See also ArrayFindMakerTest.oz and ArrayMaker.oz and ArrayMakerTest.oz and ArrayFindEqualBodyTest.oz and ArrayFindGreaterBodyTest.oz.)

A higher-order abstraction of iteration is found in Iterate.oz (see also IterateTest.oz).

3.4: Programming with recursion

ProdFromTo.oz (see also ProdFromToTest.oz)

3.4.2: Programming with lists

Write recursive functions on lists:

Assoc.oz (see also AssocTest.oz)

ListLength.oz (see also ListLengthTest.oz)

Product.oz (see also ProductTest.oz)

DeleteFirst.oz (see also DeleteFirstTest.oz)

Filter.oz (see also FilterTest.oz), which is built in to Oz.

Map.oz (see also MapTest.oz), which is built in to Oz.

All.oz (see also AllTest.oz), which is built in to Oz.

3.4.4: Difference lists

DiffList.oz (see also DiffListTest.oz)

3.4.6: Trees

Write functions that work on a given grammar, following the grammar, even if the grammar is previously unknown to you and for which you have never seen examples.

TreeFuns.oz (see also TreeFunsTest.oz)

Other grammars

Write functions that work on a given grammar, following the grammar, even if the grammar is previously unknown to you and for which you have never seen examples.

See also section 3.4.2.6 and Gary T. Leavens's paper Following the Grammar (UCF CS-TR-07-10a, October 2007).

Naturals.oz (see also NaturalsTest.oz)

NthNEL.oz (see also NthNELTest.oz)

AppendNEL.oz (see also AppendNELTest.oz)

MaxNEL.oz (see also MaxNELTest.oz)

SuperSize.oz (see also SuperSizeTest.oz)

Eval.oz (see also EvalTest.oz)

MaxAmounts.oz (see also MaxAmountsTest.oz and MaxAmountsTestBody.oz). Some students try to not use separate helping procedures for the lists in the sales data grammar, and in similar problems. To see what troupble this causes, look at the (very) incorrect version in MaxAmountsWrong.oz (and try the tests in MaxAmountsWrongTest.oz and MaxAmountsTestBody.oz).

3.6: Higher-order programming

Genericity

Write higher-order abstractions of other functions, and use the abstraction to define the original other functions.

Filter.oz (see also FilterTest.oz), which is built in to Oz.

Map.oz (see also MapTest.oz), which is built in to Oz. This is an abstraction of functions that apply a function uniformly to all elements of a list and form a list of the results.

All.oz (see also AllTest.oz), which is built in to Oz.

TreeFuns.oz (see also TreeFunsTest.oz). This is an example of abstraction, as described in the file TreeFuns.oz.

In the book Iterate.oz (see also IterateTest.oz) is treated in section 3.2.4. This can be seen as an abstraction of examples like the iterative helpers in SumFromTo.oz and Sqrt.oz. There is also an example of currying here (Iterate2c).

A higher-order abstraction of ArrayFindEqual.oz and ArrayFindGreater.oz is ArrayFindMaker.oz. (See also ArrayFindMakerTest.oz and ArrayMaker.oz and ArrayMakerTest.oz and ArrayFindEqualBodyTest.oz and ArrayFindGreaterBodyTest.oz.)

NewPortObjectDebug.oz, which has several higher-order functions for debugging in the message passing model of Chapter 5

Embedding

Use functions embedded in data to implement a specification.

Seq.oz (see also SeqTest.oz)

Environment.oz (see also EnvironmentTest.oz)

3.6.2: Loop abstractions

Use FoldR and other higher-order functions to write recursive functions on lists.

FoldRExamples.oz (see also FoldRExamplesTest.oz)

3.6.3: Linguistic support for loops

Use the for loop notation (with collect:):

ForLoopExamples.oz

ForLoopMap.oz (see also ForLoopMapTest.oz)

3.7: Abstract data types

Write functions that implement the operations of some declarative ADT.

See the specification of SampleSecures in SampleSecureTest.oz (see also SampleSecure.oz)

3.7.1: A declarative stack

See the specification of Stacks in StackTest.oz (see also Stack.oz)

3.7.5: The declarative model with secure types

How could we prevent problems related to the security of ADTs?

Stack.oz (see also StackTest.oz)

SampleSecure.oz (see also SampleSecureTest.oz)

Higher-order representations (embedding)

Use functions embedded in data to implement a specification.

Seq.oz (see also SeqTest.oz)

3.9.3: Software components

What is a module? What is a functor?

Combinators.oz (see also CombinatorsTest.oz)

Testing.oz (see also TestingTest.oz, Assert.oz, and Test.oz)

ListMonad.oz (see also Pred2ListMonad.oz and Pred2ListMonadTest.oz)

Chapter 4: Declarative Concurrency

4.1: The data-driven concurrent model

What is partial termination?

Double.oz (see also DoubleTest.oz)

See also Chapter 11 below for the RThread abstraction.

How is synchronization done in Java?

Queue.java (see also QueueTest.java)

4.2: Basic thread programming techniques

4.3: Streams

What is a stream? How would it be implemented?

StreamEnd.oz (see also StreamEndTest.oz)

Write programs using a producer-consumer architecture.

ForceList.oz (see also ForceListTest.oz)

Hailstone.oz (see also HailstoneTest.oz)

HailstoneMax.oz (see also HailstoneMaxTest.oz)

HailstoneSteps.oz (see also HailstoneStepsTest.oz)

4.3.2: Transducers and pipelines

Use dataflow variables to help with programming with threads.

HailstonePeaks.oz, which uses Hailstone.oz and HailstoneMax.oz (see also HailstonePeaksTest.oz which uses ForceList.oz)

4.3.3: Managing resources and improving throughput

Explain the different techniques for doing flow control in a stream-based system.

You may want to compare the examples in this section with those in section 4.5.3, which are simpler.

HailstoneDD.oz (see also HailstoneDDTest.oz)

HailstoneBB.oz (see also HailstoneBBTest.oz and BufferDD.oz)

4.3.4: Stream objects

Write programs using a producer-consumer architecture.

MakeStreamObject.oz (see also MakeStreamObjectTest.oz)

4.4.3: Concurrent composition

Write a barrier synchronization procedure.

Barrier.oz (which is the textbook's figure 4.22) a use of which is in BarrierTest.oz

4.5.1: The demand-driven concurrent model

What was needed in the formal model to have lazy execution?

ByNeedTest.oz

4.5.3: Lazy streams

Decide when or explain why functions should be lazy. Explain how functions are incremental (or not) depending on how they are written.

LazyLists.oz (see also LazyListsTest.oz)

Write code that uses lazy functions to do stream-based computation.

What are the advantages to using lazy functions to program stream-based computation vs. explicitly programmed triggers?

FromBy.oz (see also FromByTest.oz)

HailstoneLazy.oz (see also HailstoneLazyTest.oz)

OneDimensionalCA.oz (see also Generation.oz Rules.oz RulesTest.oz OneDimensionalCATest.oz)

Partition.oz (see also PartitionTest.oz)

4.9.1: The Declarative Concurrent Model With Exceptions

Exceptions are handled within each thread. Note, if an exception is not handled in a thread, then the entire program's execution fails.

RandomWithExceptions.oz (see also RandomWithExceptionsTest.oz)

Chapter 5: Message-Passing Concurrency

5.1: The message-passing concurrent model

Be able to give the output of Oz code using the message passing model:

StreamEnd.oz (see also StreamEndTest.oz)

NewPortSemantics.oz

NewPortMerging.oz

5.2: Port objects

What is a port object?

SumPortMaker.oz (see also SumPortMakerTest.oz)

SumAgentMaker.oz (see also SumAgentMakerTest.oz and the version done using NewPortObject in NewPortObjectTest.oz).

Use NewPortObject to make port objects with state (see the NewPortObjectTest.oz file).

NewPortObject.oz (see also NewPortObjectTest.oz)

NewPortObjectDebug.oz, which is a version of NewPortObject.oz that helps with debugging port objects. (See PrintServer.oz for an example of use.)

MathAgentMaker.oz (see also MathAgentMakerTest.oz)

NewBankAccount.oz (see also NewBankAccountTest.oz)

DatingService.oz (see also DatingServiceTest.oz)

PrintServer.oz (see also PrintServerTest.oz)

NewPrintServer.oz (see also NewPrintServerTest.oz)

MakeDFV.oz which makes port objects that act like dataflow variables (see also MakeDFVTest.oz)

NewEmailServer.oz which makes port objects that act email servers (see also NewEmailServerTest.oz)

Use port objects to represent abstract data types (ADTs).

NewGauge.oz which makes a Gauge abstract data type, represented by a port object (see also NewGaugeTest.oz)

NewArray.oz which makes an Array abstract data type, represented by a port object (see also NewArrayTest.oz)

Use NewPortObject2 to make stateless port objects.

NewPortObject2.oz

MinServer.oz (see also MinServerTest.oz)

See the tests in DatingServiceTest.oz

RMI.oz

RMIcallbackthread.oz

5.3: Simple message protocols

5.3.1: RMI (Remote Method Invocation)

What is RMI?

RMI.oz

5.3.3: RMI with callback (using thread)

How do you handle callbacks in the message passing model?

RMIcallbackthread.oz

5.6: Using the message-passing model directly

How can you use NewPort and Send directly to implement concurrent data structures?

NewQueueFixed.oz (see also NewQueueFixedTest.oz and QueueTest.oz)

5.6.4: Eliminating sequential dependencies

What techniques can eliminate sequential dependencies to increase concurrency?

Filter2.oz (see also Filter2Test.oz, ListMonad.oz, Pred2ListMonad.oz, and Pred2ListMonadTest.oz)

Chapter 6: Explicit State

6.1: What is state?

How does one use cells in programming?

TestingNoStop.oz (see also TestingNoStopTest.oz)

6.5: Stateful Collections

ArrayMaker.oz (see also ArrayMakerTest.oz)

Chapter 9: Relational Programming

What is the essential idea of relational programming?

RAppend.oz (see also RAppendTest.oz)

9.1: The relational computation model

What does choice do? What does fail do?

ChoiceExamples.oz

What does Solve do?

SolveExamples.oz (see also the textbook's Solve.oz, SolveAll.oz, and SolveOne.oz, as well as our own SolveFirst.oz)

9.2: Further examples

Write relations on lists.

RAppend.oz (see also RAppendTest.oz)

AddToEnd.oz (see also AddToEndTest.oz)

Reverse.oz (see also ReverseTest.oz)

RMember.oz (see also RMemberTest.oz)

Write relations on other recursive data structures, as specified by some grammar.

Unary.oz (see also UnaryTest.oz)

Use generate and test to solve problems.

SimpleGenTest.oz (see also SimpleGenTestTest.oz)

FourLetter.oz (see also FourLetterTest.oz)

VideoTimes.oz (see also VideoTimesTest.oz)

Sorted.oz (see also SortedTest.oz)

9.3: Relation to logic programming

Use logic programming techniques to specify problems.

Sorted.oz (see also SortedTest.oz)

Explain how programs and queries in Oz correspond to logic.

Capitals.oz and CapitalsTest.oz

Agriculture.oz and AgricultureTest.oz

FamilyExample.oz and FamilyExampleTest.oz

FamilyRules.oz and FamilyRulesTest.oz

9.4: Natural langauge parsing

Use logic programming techniques to write parsers for ambiguous grammars.

ExpressionParser.oz (see also ExpressionParserTest.oz)

9.6: Databases

Use logic programming to write programs that work with relational databases.

CSClasses.oz (see also CSClassesTest.oz)

Chapter 11: Distributed Programming

Using the remote module manager to take advantage of multiple cores. Try the tests on a dual core machine and watch a performance meter that tells you when you are using both cores.

RThread.oz (see also RThreadTest.oz)

RemoteFun.oz (see also RemoteFunTest.oz)

Chapter 12: Constraint Programming

Write simple constraint solutions on integer domains

VideoTapeTime.oz (see also VideoTapeTimeTest.oz)

The textbook's Solve function is used in chapter 9

Solve.oz


Last modified $Date: 2012/03/21 14:57:45 $.