Welcome! Let’s get to know each other with an icebreaker. Answer these questions:
-
What is your name?
-
Why is Computer Science your major?
-
Tell us something nobody else in the room knows about you.
This course introduces programming languages (hence the name) beyond the familiar structured imperative object-oriented and procedural programming paradigms.
We’ll have a midterm, labs and assignments, but for the final project, we’ll implement a compiler or interpreter for a programming language.
We’ll focus on a few languages in depth, and cover other languages briefly. Please download SWI-Prolog, Haskell Platform and SBCL (links in table).
| Language | Implementation | Paradigm | Textbook |
|---|---|---|---|
Prolog |
Logic programming |
||
Haskell |
Functional programming |
||
LISP |
Metaprogramming |
||
Others |
Various |
Download SWI-Prolog, Haskell Platform and SBCL (links in table above), if you haven’t already done so.
|
Note
|
Mac users may need to install XQuartz |
- Windows
-
Note
Select KDiff, and choose OpenSSH (not PuTTY); otherwise, stick to the default settings. - Mac OS X
-
Install GitX-dev, then Install XCode developer tools which ships with git (recommended) or install git from here.
- Linux
-
Install git using your package manager.
NoteDon’t forget to use sudo with your package manager.
Don’t forget a text editor.
Starterupper sets up git and project hosting for this class; it is safe to run even if you already have git and SSH keys set up on your machine.
Open Git Bash (Windows) or Terminal (Linux, Mac OS X) and paste in the command below.
Press Shift-Insert to paste in Git Bash.
curl https://gitlab.com/lawrancej/COMP3071-2015/raw/master/main.sh | bash
A set is unordered and has no duplicates (no repeated values).
{ "hello", "world" } == { "world", "hello" }
A bag is unordered and allows duplicates (repeated values).
{ "buffalo", "my", "buffalo" } == { "my", "buffalo", "buffalo" }
A sequence is ordered and allows duplicates.
[ "hello", "cruel", "world" ] != [ "cruel", "world", "hello" ]
An ordered set is ordered and has no duplicates.
To summarize:
English subset
{
"This is a sentence in English.",
"This is another sentence in English."
}
Espanol subseto?
{
"Yo quiero Taco Bell",
"Donde esta el bano?"
}
An alphabet is a set of symbols (e.g., char).
A string is a sequence of symbols chosen from some alphabet.
Languages are (possibly infinite) sets of strings. A grammar constructs a language; regular expressions construct regular languages.
cd ~/COMP3071-2015 # Hexadecimal words grep -E "^[a-f]+$" american-english.txt | less
A regular expression (regex) defines a language with these primitives and operators.
| Name | Notation | Meaning |
|---|---|---|
Primitives |
Regular expression building block. |
|
Empty Set |
{} |
Reject everything. |
Empty String |
"" |
Match the empty string. |
Symbol |
|
Match a single character. |
Operator |
Make a new regex from existing regexes. |
|
Sequence |
|
Match regex |
Alternation |
|
Match regex |
Kleene Star |
|
Match regex |
The primitives and operators above can define other regular expression operators
in terms of themselves.
For example, a? optionally matches a. This is equivalent to: a|"".
Another example: a+ matches a 1 or more times. This is equivalent to a*a.
Trivially, finite languages are regular:
finite language: {"hello","cruel","world"}
equivalent regex: hello|cruel|world
Since regular languages can be infinite, they encompass the finite languages.
.* (Matches everything)
Regular languages can’t express everything; for example, they cannot check matching brackets in the general case.
The Chomsky hierarchy is a containment hierarchy of languages. What distinguishes one language category from another is restrictions placed on grammars or the underlying automaton.
A grammar consists of a finite set of nonterminals (variables), a starting nonterminal, terminals (literals, words or symbols), and productions (rules) that map among terminals and nonterminals. Grammars define languages: they generate the set of strings in the language and test membership of a string in the language.
The example grammar below defines a small subset of English, with an example sentence. The example grammar is context-free because the left side of each arrow is a nonterminal.
Pull from upstream.
cd ~/COMP3071-2015 git pull upstream master
Prolog is a logic programming language. Prolog typically compiles into code for the WAM
In SWI-Prolog, File → Consult ~/COMP3071-2015/in-class/intro.pl for an introduction to Prolog syntax.
Open the same file in an editor, and run queries.
Due: By next Friday at the latest.
Save your work in a file called lab1.pl in your repo.
cd ~/COMP3017-2015 touch lab1.pl
|
Note
|
Use a proper text editor, such as this. |
directTrain(avon, braintree). directTrain(quincy,avon). directTrain(newton,boston). directTrain(boston,avon). directTrain(braintree,milton). directTrain(westwood,newton). directTrain(canton, westwood).
This knowledge base holds facts about towns it is possible to travel between by taking a direct train.
But of course, we can travel further by chaining together direct train journeys.
Write a recursive predicate travelBetween/2 that tells us when we can travel by train between two towns.
Example: travelBetween(canton,braintree). Prolog should reply true
Example: Whenever it is possible to take a direct train from A to B,
it is also possible to take a direct train from B to A.
For example, query travelBetween(braintree, canton). should return true.
tran(eins,one). tran(zwei,two). tran(drei,three). tran(vier,four). tran(fuenf,five). tran(sechs,six). tran(sieben,seven). tran(acht,eight). tran(neun,nine).
Write a predicate listtran(G,E) which translates a list of German number words to the corresponding list of English number words.
Example: listtran([eins,neun,zwei],X). should yield: X = [one,nine,two].
Your program should also work in the other direction.
Example: listtran(X,[one,seven,six,two]). should yield: X = [eins,sieben,sechs,zwei].
Hint: Handle the base case (the empty list) first, then for non-empty lists, first translate the head of the list, and then use recursion to translate the tail.
Use Prolog to solve a logic puzzle, by encoding facts as predicates.
Use the "Animal Logic Puzzle" available here: Logic puzzles for kids
Pull from me. Look in labs/Lab1.hs
cd ~/COMP3071-2015 git pull upstream master
Solve problems.
cd ~/COMP3071-2015 git commit -am "Lab 1 done" git push origin master
Challenge: Make a sliding tile puzzle, or Connect4, or a snake game, or hangman, or pong. Use the tic-tac-toe source as inspiration. Feel free to work in pairs or small groups of 3.
cd ~/COMP3071-2015 git pull upstream master cabal update cabal install gloss cd labs ghc tictactoe.hs ./tictactoe.exe
TODO:
-
Add collaborators in your team:
- On Github
-
Right hand side
Settings→ Left hand sideCollaborators - On Gitlab
-
Left hand side Group of people
Members→ Add Members →lawrancej. And Project Access →Developer
-
Make sure I have access to it (I’m
lawrancejon github and gitlab) -
Make sure everybody on the team has access
-
Clone the repo:
cd git clone the-repo-goes-here
-
If you’re using a shared repo, you’re done! Otherwise, be sure to add remotes for each remote
git remote add remote-goes-here
-
Decide on a program to implement
-
Determine the data and functions in the Model
-
Determine how to show stuff to the user
-
Determine how to handle events from the user