The project is voluntary and students may earn maximum of 15 points for successfully implementing the project and presenting it to their TA. These points count towards the exam, not towards the tutorials.
During the presentation of their work, students must answer questions about their code so that it is obvious the work is theirs. Each student may choose one of the following topics:
This topic can be implemented in any of the following languages: C/C++, Java, Python, JavaScript, or Common Lisp. The task is broken down to smaller subprojects:
You must create a representation for λ expressions used in your implementation. This representation must allow for at least the following:
- variables in λcalculus (any string of lowercase letters)
- λ function
(λx. Z)wherexis variable andZis any λ expression - application in the form of
X YwhereXandYare λ expressions
As an example, you may choose the following representation in a C++ language:
class Expression { };
class Variable : public Expression {
std::string name;
};
class Lambda : public Expression {
Variable * argument;
Expression * telo;
};
class Application : public Expression {
std::vector<Expression> * exprs;
}
After you add constructors to these classes, the λ expression (λx. x x) y can bve created using the following notation:
Expression * v = new Application({
new Lambda("x", new Application({
new Variable("x"),
new Variable("x")
})),
new Variable("y")
});
Your implementation must also be able to print itself in a human readable form:
(lambda x . (x x)) y
The selected representation does not have to be identical to the one presented here, but must not be ambiguous (i.e. you may leave out the dot if supporting only single argument lambdas, etc.).
If you decide to use lisp, you may represent everything using a list (you must describe how precisely) and so the expression from above can be represented like this:
`( (lambda x (x x)) y)
In given λ expression, determine for each variable whether it is free or bound and display this information to the user, i.e. for instance:
(λ. x (λy. y x) x y) z
prints:
y bound
x bound
x bound
y free
z free
Write a function that performs a β reduyction on given λ expression, for example:
(λx. x x ) (λz. z)
will become:
(λz.z)(λz.z)
and finally:
(λz.z)
Add an option for the user to select between applicative and normal evaluation order and demonstrate this successfully on the following λ expression:
(λab. aabb)((λxa. a)(λx. xx)a)d
Implement α-reduction and correctly detect when the reduction should be used, so that for instance::
(λx. (λz. x z)) (z g)
&alpha-reduction:
(λx. (λt. x t)) (z g)
and then β-reduction:
(λt. (z g) t)
If your evaluator is robust enough to properly evaluate at least factorial of 5, you will be awarded all 15 points regardless of whether you support applicative/normal evaluations, α reduction, or free/bound variable detection & printouts.
YR5
where
Y = (λf. (λx. f (xx)) (λx. f (xx)))
R = (λf. (λn. zero n 0 (* n f (-n 1))))
(zero, numbers and operators must of course be described using the proper λ expressions (church literals, etc.))
Your mission, if you choose to accept it will be to program a simple text adventure game in prolog, in which the user will be walkimng through different rooms, searching for treasures, collecting stuff and killing enemies.
For more information about the genre, see Zork.
The following prolog functions will be handy for the game:
assert/1
Adds the given fact to the database:
assert(mother(jana, lucie)).
?- mother(jana, X)
X = lucie
retract/1
Removes the given fact from the database:
retract(mother(jana, lucie)).
?- mother(jana, X)
false
write/1
Writes given string to the output.
nl
Writes new line to the output.
Describe the way in which the dungeon will be encoded in teh prolog database and define such a dungen, which consists of at least the following:
- 20 rooms with textual description
- paths between these rooms
When your program will be launched, you must write the room at which the player is located and present the player with his/her options. If the player reaches the final room, the game must inform him/her that the objective has been reached:
You are in a dark room without any windows. The floor is cold and dump and water drips from the walls.
Doors are to the south.
Doors are to the north.
Define functions north(), south(), west() and east() that would allow the player to move in the dungeon.
?- south().
If the player uses wrong direction (i.e. direction where there are no doors), the game must not move the player and inform him/her of the error.
Add an inventory to the game and put various objects into the game that the player can pick up and drop. Implement functions pick and drop which pick the item from the room and put it into the inventory and drop the item from the inventory to the room. Decide how many elements may a player or room hold at one time and check the user actions accordingly.
Update the game descriptions accordingly, i.e:
You are in a cold room that used to be a prison or a lunatic asylum. Lambda signs are carved to the walls with fingernails, obviously by a madman.
There is a flashdrive on the floor
Your inventory contains a wooden horse toy.
Doors are to the south.
Add locked doors of two colors (red and blue), which the player can open only if he/she holds a key of appropriate color in the inventory. By walking through the doors with the key, the doors remain open and the player looses the key:
You are in a room I am too lazy to describe.
Red doors are to the south (locked).
Doors are to the west.
Your inventory contains red key.
V inventorari mas cerveny klic.
Player walks through the doors and looses the key:
?- south().
You are in a great room filled with old computers.
Red doors are to the north (unlocked)
Doors are to the south.
Your inventory is empty.
Add at least two types of weapons and two types of enemies in the rooms, which are immune to one of the weapons. The player receives a certain lives and if he/she enters a room with an enemy without the proper weapon, he/she looses a life. If the player enters the room with the proper weapon, he kills the enemy. Add extra lives as items to some rooms for the player to collect.
Add the possibility to teleport, i.e. if a player holds the teleport in the inventory, he/she may return to the room where the teleport was picked by using it. Define function use() to fo this.