Declarative Programming

A tantárgy neve magyarul / Name of the subject in Hungarian: Deklaratív programozás

Last updated: 2023. február 26.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics
Computer Engineering
Course ID Semester Assessment Credit Tantárgyfélév
VISZAD00 7 2/1/0/f 3  
3. Course coordinator and department Dr. Szeredi Péter,
Web page of the course https://dp.iit.bme.hu
4. Instructors

Név:

Beosztás:

Tanszék, intézet:

dr. Hanák Péter

külső munkatárs

Számítástudományi és Információelméleti Tanszék

dr. Szeredi Péter

c. egyetemi tanár

Számítástudományi és Információelméleti Tanszék

6. Pre-requisites
Kötelező:
NEM ( TárgyEredmény( "BMEVISZA402" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZA402", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZA403" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZA403", "FELVETEL", AktualisFelev()) > 0)

ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

7. Objectives, learning outcomes and obtained knowledge Introduction to the declarative - also known as non-imperative - programming paradigm, the two main trends - functional and logic programming - and to practice them by solving small to medium sized problems. 
8. Synopsis
       Week 1:

(4 hours lecture - introduction and functional programming): requirements, literature, website. Motivational example in logical and functional language. Main features of declarative programming: functions or procedures, non-updatable variables, accumulators, recursive algorithms and data structures, right recursion, higher order functions or procedures.

Functional programming: programming environments. Programming environments. Types, operations, variables, expressions. Syntax. Greedy and lazy evaluation of expressions. Lists, list view. Iteration and recursion, linear and branch recursion, right recursion, accumulators. Modules.

- Week 2:

(2 hours practice): Programming in functional language.

(2 hours lecture - functional programming): Built-in functions. Compound expressions. Lists and enneses. Pattern matching. Type specification. More about modules.

- Week 3:

(4 hours lecture - functional programming): Higher order functions, function values. Common library functions. Exception handling.

Complex data structures and their handling: lists, sets, graphs. Key-value pairs, binary trees. Linear and branching recursion again. Proof of program correctness. Lazy evaluation, lazy list.

- Week 4:

(2 hours practice): programming in functional language, preparation for midterm exam.

(2 hours lecture - logic programming): Introduction through examples. Basic syntax of the language, data structures. List handling.

- Week 5:

(2 hours practice): Programming in logic language.

(2 hours lecture - logic programming): The implementation algorithm. Reduction step, union, search space. Box model of tracing.

- Week 6:

(4 hours lecture - logic programming): Operators. Additional control structures: disjunction, conditional structure, negation. Right recursion, accumulators. Narrowing the search space. Determinism and indexing. Control procedures.

- Week 7:

(2 hours of practice): Programming in a logic language.

(2 hours lecture - logic programming): Meta-logic procedures.  Solution gathering procedures. Higher order procedures.

- Week 8:

(4 hours lecture - declarative programming): Constraint-based programming methods.

- Week 9:

(2 hours of practice): Programming in functional and logical languages.

(2 hours of lecture - declarative programming):  Breadth and depth searches.

- Week 10:

(2 hours of practice): Programming in functional and logical languages.

(2 hours of lecture - declarative programming): Summary and outlook.

- Week 11:

(2 hours of practice): Programming in functional and logical languages, preparation for the final exam.

Translated with www.DeepL.com/Translator (free version)
9. Method of instruction 14*2 hours of lectures and 7*2 hours of practical training in the first 11 weeks of the semester.
10. Assessment
a) Evaluation and acceptance of final papers


During the semester, two midterm tests  will be written and must receive at least 40% of the marks to be accepted.

In the case of retake, the result of the last final examination will be valid.

b) Small assignments 

Programming assignments will be given as small homework several times during the semester. The method of submission is described in the assignment description to be published on the subject's website.

To meet the requirement for small homework assignments, at least 2/3 of the programs to be submitted must run in both programming languages with 100% completion of the test cases.

c) Large assignments, mark offered

Solving the major homework assignments is not mandatory, but their results will count towards the semester grade and may earn an offered grade if submitted.

Programmes and documentation must be submitted electronically during the scheduled teaching week. Details of how to submit will be given in the assignment descriptions to be published on the subject website. The student will be asked questions about the solutions submitted (this is a defence of the major homework assignment, a demonstration of independent work).

Programmes solving at least 80% of the test cases will be run with additional more complex, larger test cases in the so-called ladder competition. The mark offered depends on the result of the ladder competition (see below).

d) Determination of the semester grade

The semester grade will be based on a weighting of 85% for the final exam and 15% for the major homework. The score obtained for the small homework and the ladder competition will improve the overall grade, so that together they may result in an overall grade of more than 100%. 

The lower bounds for each grade as a percentage of the total score are: satisfactory - 40%, intermediate - 55%, good - 70%, excellent - 85%.

A good (4) grade will be offered to students who complete the requirements for the small homework assignments, submit solutions to the large homework assignment in both programming languages, document them properly, enter their programs into the ladder competition, and successfully defend the large homework assignment. A significant (5) marks will be awarded to the student whose programs solve at least 40% of the test cases in the ladder competition.

If the offered grade is accepted, the final exam does not have to be written and the result of any final exam written will not be taken into account.

e) Use of unauthorised devices

 Small and large homework assignments must be solved by each student individually and independently, and no other assignments, such as complete code or even parts of code, may be taken from others except for ideas. The structural similarity of the programs can be tested using automated tools.


In the case of receiving/transmitting and submitting a program or part of a program from someone else, all small and large homework assignments will be considered invalid. Those using unauthorized tools on the final exam will be penalized according to the applicable faculty or university regulations. In all other matters, the provisions of the TVS are applicable.
13. References, textbooks and resources

Szeredi Péter, Benkő Tamás: Deklaratív programozás. Oktatási segédlet. Bevezetés a logikai programozásba. Számítástudományi és Információelméleti Tanszék, Budapest, 2005. Letölthető a tárgy honlapjáról.

Ajánlott irodalom:

a. Erlang on-line documentation http://erlang.org/doc.html

b. Erlang Programming. Wiki Books. http://en.wikibooks.org/wiki/Erlang_Programming

c. Fred Hébert: Learn you some Erlang. https://learnyousomeerlang.com/

d. Erlang Tutorial. https://www.tutorialspoint.com/erlang

e. Elixir. https://elixir-lang.org/

f. Elixir Tutorial. https://www.tutorialspoint.com/elixir

g. An Introduction to Elm. https://guide.elm-lang.org/

h. Beginning Elm. https://elmprogramming.com/

i. Elm Tutorial. ttps://www.tutorialspoint.com/elm/

j. Farkas Zsuzsa, Futó Iván, Langer Tamás, Szeredi Péter: MProlog programozási nyelv. Műszaki Könyvkiadó, Budapest, 1989.

k. Márkusz Zsuzsa: Prologban programozni könnyű. Novotrade, Budapest, 1988.

l. Richard A. O'Keefe: The Craft of Prolog. MIT Press, 1990. ISBN 0-262-15039-5

m. Leon Sterling, Ehud Shapiro: The Art of Prolog. Advanced Programming Techniques, 2nd Edition, MIT Press, 1994, ISBN 0-262-19338-8

n. Peter Flach: Logikai Programozás. Az intelligens következtetés példákon keresztül. Panem-John Wiley & Sons, 2001

o. Ulf Nilsson and Jan Maluszynski: Logic, Programming and Prolog (2nd ed.). Previously published by John Wiley & Sons Ltd. http://www.ida.liu.se/%7Eulfni/lpp/

14. Required learning hours and assignment
Contact hours42
Preparation for classes13
Preparation for midterm10
Homework19
Reading assignment6
 
Összesen90
15. Syllabus prepared by

dr. Szeredi Péter