For the english variant of PA1, please click here.

BI-PA1.21

Kontakt

  • milan.spinka@fit.cvut.cz
  • prosím tykejte, jsem student stejně jako vy :D
  • do předmětu e-mailu ideálně napište prefix [PA1], ať ho kdyžtak snadno dohledám
  • e-maily posílejte ze školní adresy a do kopie přidejte druhého cvičícího
  • možnost je zeptat se i na neoficiálním studentském Discordu

Materiály ze cvičení

Doporučení pro úspěšné studium

  • Nenechte si ujet vlak. Nejdůležitější látka skoro v každém předmětu je na začátku — když nebudete rozumět základům, bude pro vás celý semestr strašně náročný. I když třeba už nějakou dobu programujete a v prvním týdnu se vám bude zdát, že je to přece věechno jasné, nenabyjte mylného dojmu, že nemusíte předmětu věnovat úsilí. Zaprvé je rozdíl mezi programováním v Javascriptu nebo Pythonu a programováním v Céčku, zadruhé si s sebou spousta programátorů-samouků přinese špatné návyky, které je potřeba se odnaučit. Naopak pokud hned na začátku semestru zjistíte, že máte v něčem mezery, snažte se je co nejrychleji doplnit, abyste mohli plně věnovat pozornost tomu, co se probírá.
  • Ptejte se cvičících, když něčemu nerozumíte. Ať už v pátek osobně na cvičení, e-mailem, discordem, nebo poštovním holubem. Pokud se váš dotaz bude týkat předmětu PA1 nebo programovacího jazyka C, pak nemůže být špatný, hloupý nebo nevhodný. Tím, že se nezeptáte, tak ubližujete nejen sobě, ale všem ostatním studentům, kteří se neodhodlali zeptat na to samé. My cvičící už nějakou dobu programujeme a koncepty, které vám předáváme, nám přijdou úplně přirozené, tím pádem se ale může stát, že něco nevysvětlíme dostatečně dobře a vám to pak bude bránit v chápání navazujících témat. Takže se ptejte. (Just do it!)
  • Choďte do školy. Pokud zjistíte, že s programováním bojujete, a budete mít pocit, že vám účast na cviku nic nedá, protože jste stejně už ztracení, stejně přijďte. I když půjdete na cviko a třeba nebudete chápat úplně všechno, i tak vám to dá zase o jeden kousek zkušenosti s programováním navíc. Neexistuje cesta zpátky, jen vpřed, a s každým řádkem kódu, který napíšete, a každým přednáškovým slidem, který vám Láďa Vagner odpřednáší, se posouváte blíž k porozumění a úspěšnému absolvování předmětu. Kdosi to nazval The unreasonable effectiveness of just showing up everyday a já bych to asi lépe nepojmenoval.
  • Nezapomínejte na znalostní testy! Týden před každým znalostním testem je navíc puštěný demotest, který si můžete pustit kolikrát chcete a který vás v podstatě zadarmo připraví na ostrý test. Vedle progtestových domácích úloh se na znalostní testy snadno zapomene, ale získání bodů z nich je nutnou podmínkou pro absolvování předmětu!
  • Neodkládejte progtesty!! (Vizte níž.)

Jak zvládnout Progtest?

Hlavně ho nedělat na poslední chvíli. Osobně bych vám doporučil následující strategii, která se mi osobně jako studentovi osvědčila:

  1. V sobotu v 0.00 hodin dropne progtestová úloha. Pokud jste zrovna v bdělém stavu, přečtěte si zadání, postěžujte si na fakultním discordu a běžte spát. Pokud jste ve stavu jiném než bdělém, vyčkejte na přechod do bdělého stavu a pokračujte bodem č. 2.
  2. V sobotu dopoledne si udělejte nějakou dobrou snídani, přečtěte si (znovu) zadání a promyslete si nástřel řešení. Většinou to první, které vás napadne, bude (víc nebo míň) blbě, ale to nevadí. Taky doporučuju, než si vůbec sednete za počítač a začnete bušit kód, vemte si tužku a papír a nakreslete si obrázek nebo si rozepište pár instancí problému, který máte řešit, a ověřte si, že vaše intuitivní chápání sedí s realitou.
  3. Zbytek dne zkoušejte úlohu vyřešit. Není to proto, abyste byli první nebo abyste ji vyřešili hned první víkend (byť to doporučuju a považuju to za velmi reálné). Ale tím, že se s ní seznámíte už o víkendu, si dost pomůžete — jednak přirozeně budete mít náskok a víc času na vyřešení, ale hlavně pak budete moct během týdne úlohu diskutovat s ostatními studenty a studentkami a se svými cvičícími, protože budete chápat, o co v ní jde a kde je problém.
  4. Pokud Až nastane situace, že vám z progtestu už půjde hlava kolem nebo prostě nebudete vědět jak dál, běžte se projít, najíst, prostě si dejte pauzu, udělejte něco pro sebe a nemyslete vůbec na programování. Buďto se stane, že dostanete během procházky nápad, který vás dovede k úspěšnému vyřešení (jednou jsem si takhle uvědomil bug v metru, opravil jednu řádku a mobilem poslal řešení na plný počet…), nebo žádný nápad nedostanete, ale přijdete zpátky k počítači s čerstvým pohledem a jasnější myslí.
  5. Pokud ani to nepomůže, nebojte se poprosit o pomoc cvičícího nebo cvičící, případně kolektivní moudro FIT Discordu.

FAQ

Můžu se o řešení progtestu bavit s kamarády? Jak se pozná, že někdo opsal řešení?

O progtestových úlohách se s kamarády a kamarádkami můžete bavit, můžete si napovídat, můžete si prozradit celou podstatu řešení — morální úsudek je čistě na vás. Nicméně pokud byste byli v napovídání natolik sugestivní, že by se vaše a kamarádovo nebo kamarádčino řešení podezřele podobalo (ne nutně ve smyslu doslovné textové shody zdrojáků, ale prostě struktury toho kódu jako takového), riskujete, že budete čelit zvídavým otázkám u ústní části zkoušky předmětu.

Vždy stačí použít selský rozum — funkci na porovnání dvou floatů, nalezení počtu přestupných roků v intervalu nebo rozhodnutí o sudosti celého čísla budou mít všichni studenti stejně, protože není zas tolik způsobů, jak ji napsat. Nicméně s rostoucí komplexitou problému se pravděpodobnost identických řešení velmi rychle zmenšuje, takže se nemusíte bát, že byste omylem napsali úplně stejný program, jako nějaký kolega nebo kolegyně.

Můžu v předmětu PA1 používat AI (GitHub Copilot, ChatGPT, atd.)?

Důrazně to nedoporučujeme. Zaprvé hrozí, že nebudete sami, a tím pádem se objeví problém s plagiátorstvím, a zadruhé, když se naučíte psát kód za pomoci AI, tak u zkoušky zjistíte, že sami nic nenapíšete.

Můžu v předmětu PA1 používat IDE (CLion, Visual Studio, atd.)?

Zezačátku od toho mírně odrazujeme, protože chceme, abyste viděli, že na vytvoření programu není potřeba nic jiného než textový soubor a překladač, a chceme, abyste procesu kompilace trochu rozuměli. Celé PA1 si bohatě vystačíte s textovým editorem (dobrý nápad je asi mít editor se zvýrazňováním syntaxe a language supportem, abyste sémantické chyby mohli opravit rovnou a ne teprve, až vás seřve překladač) a příkazovou řádkou, nicméně pokud jste si jistí, že víte, co za vás IDE dělají “pod kapotou”, pak není problém je používat.

Jak mám odevzdat úlohu na code review?

TBA.

Můj kód u mně na počítači funguje, ale na Progtestu ne :( Proč?

Nejprve zkuste program zkompilovat s přepínači -Wall -pedantic -O2 -g -fsanitize=address,undefined, případně zkompilovat ProgTestím kompilátorem (hlavní stránka -> kompilace a spuštění). Pokud toto neuspěje, je problém se samotnou kompilací. Pokud to uspěje, ale odevzdání úlohy přesto selhává, nejspíš se bude jednat o jeden z následujících problémů:

1. Odevzdáváte špatný soubor.

Je to hloupé, ale každému se to někdy stalo. Odevzdávejte zdrojový kód (*.c), nikoli spustitelný program, a zkontrolujte si, že odevzdáváte opravdu ten, na kterém pracujete.

2. Používáte funkce z hlavičkových souborů, které v úloze nejsou povolené.

U některých úloh na začátku vzorového souboru uvidíte typicky něco jako:

#ifndef __PROGTEST__
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
...
#endif

Pokud používáte IDE, je možné, že vám chytře napoví použít funkci ze standardní knihovny a samo ji naincluduje, ale na progtestu k dispozici není. Zkontrolujte, jestli se vaše includes shodují s těmi ve vzorovém souboru.

3. Část kódu, který je součástí řešení, je umístěn v bloku podmíněného překladu.

Stručně řečeno, všechno, co leží mezi direktivy #ifndef __PROGTEST__ a #endif, je pro kompilátor na progtestu neviditelné. Tudíž je poměrně nevhodné do něj umístit svoje řešení nebo jeho část.

4. Váš kód obsahuje nedefinované chování (undefined behaviour, UB).

Nedefinované chování je použití jazyka C takovým způsobem, u nějž vám specifikace nezaručuje, co “bude dělat” program, který vznikne překladem.

Typickým příkladem je čtení neinicializované proměnné:

int main(void) {
    int n;

    printf("%d\n", n);

    return 0;
}

Výsledek takového kódu je závislý na konkrétní implementaci překladače (gcc / clang / Microsoft Visual C), stupni optimalizace při překladu (-O0, -O1, -O2, …), na stavu paměti počítače v době běhu, atd. Jinými slovy nemůžete předem spolehlivě říct, co váš program bude dělat — to je krajně nežádoucí.

Pokud se váš program chová nevysvětlitelně, obzvláště pokud se chová jinak bez zapnutých optimalizací (-O0) a se zapnutými optimalizacemi (např. -O2), téměř jistě máte v kódu případ nedefinovaného chování.

Co znamená Segmentation fault a jak to opravím?

Ve většině případů vám program spadne na Segmentation fault tehdy, když čtete z / zapisujete do paměti, která programu nebyla přidělená. Jinými slovy je váš program špatně nebo obsahuje bug.

Jak postupovat:

Zkompilujte program s debugovými informacemi (-g) a address sanitizerem (-fsanitize=address):

g++ -Wall -pedantic -g -fsanitize=address program.c

Spusťte program, zadejte problémový vstup a najděte ve výstupu address sanitizeru číslo řádky, kde probíhá INVALID READ nebo INVALID WRITE. Pokud je adresa 0x0000…, dereferencovali jste NULL pointer. V opačném případě nejspíš přetékáte z pole nebo přistupujete na již uvolněnou paměť.

Alternativně:

Zkompilujte program s debugovými informacemi (-g):

g++ -Wall -pedantic -g program.c

a předejte program jako argument nástroji valgrind:

valgrind a.out

Opět zadejte problémový vstup a analyzujte výstup nástroje valgrind.

Pozn. Někdy (obsahuje-li kód nedefinované chování) se může stát, že se chyba projeví pouze po kompilaci s optimalizacemi, v takovém případě zkuste kompilovat navíc s přepínači -O1, -O2, nebo -O3.

Můj program se chová jinak, než očekávám, že se bude chovat.

Odlaďte (oddebugujte) si ho. Ujistěte se, že spouštíte správnou verzi programu a při kompilaci nedostáváte varování. Kompilujte bez optimalizací a s debugovými informacemi:

g++ -Wall -pedantic -g -O0 program.c

Spusťte program v GNU debuggeru (gdb). (Pokud přesměrováváte vstup ze souboru, nesměrujte ho do programu gdb, přesměrování zajistíte až v rozhraní debuggeru.)

gdb a.out

Přehled užitečných příkazů v rozhraní gdb:

  • run, run < in.txt — spusť program (s případným přesměrovaným vstupem)
  • s, start, start < in.txt — nastav breakpoint na funkci main a spusť program (s případným přesměrovaným vstupem)
  • b <funkce | cisloradku>, break <funkce | cisloradku> — nastav breakpoint na funkci <funkce> nebo na řádek <cisloradku>
  • d <cislo>, delete <cislo> — smaž breakpoint s číslem <cislo>
  • n, next — vykonej jednu řádku
  • s, step — vykonej jednu řádku, ale pokud je v ní volání funkce, zastav se po vstupu do té funkce
  • fin, finish — pokračuj ve vykonávání programu až do návratu z funkce
  • c, continue — pokračuj ve vykonávání programu do dalšího breakpointu (nebo do konce)
  • p <expression>, print <expression> — zobraz hodnotu výrazu <expression> (např. proměnné, prvku v poli, registru…)
  • display <expression> — zobrazuj průběžně hodnotu výrazu <expression> po každém kroku (n, s…)
  • list — zobraz několik následujících řádek zdrojového kódu — spíše bych doporučil visual mode (vizte níž)
  • help — zobraz dokumentaci / nápovědu
  • Enter — zopakuj poslední příkaz (nezahlcuje historii příkazů)
  • Šipky nahoru a dolů — procházení historie příkazů, nefunguje ve visual módu
  • bt — backtrace, užitečné po pádu programu, ukáže vám, kde program spadl a kterými funkcemi se tam dostal
  • Ctrl+X A — přepni mezi command line módem a visual módem

Nastavte si breakpoint na místo v kódu, které vás zajímá, prokrokujte si ho a pozorujte, jestli obsahy všech relevantních proměnných sedí s vaším očekáváním.

Pokud používáte IDE, debugování pro vás bude podstatně jednodušší díky grafickému rozhraní, nicméně myšlenka je totožná.

Pro odhalení nedefinovaného chování ve vašem kódu lze využít přepínače -fsanitize=undefined (při překladu).

Secret tip: Pokud byste se při debugování chtěli zastavit na nějakém místě pouze v případě, že je splněná nějaká podmínka (například vás zajímají pouze některé iterace smyčky), dá se překladači “vnutit” umístění instrukce breakpointu do samotného programu:

#ifndef __PROGTEST__
/* This will trigger a breakpoint only when my_condition(x) is true */
if (my_condition(x)) __asm__("int $3");
#endif

Takový program lze pak spouštět pouze v debuggeru, jinak spadne s chybou SIGTRAP (trace/breakpoint trap).

BIE-PA1.21

How to reach me

  • milan.spinka@fit.cvut.cz
  • ideally, prepend [PA1] or [BIE-PA1] to the mail subject, so that I can easily find your emails
  • please use your school mailbox to send school-related emails, and make sure to send a copy to both of your practical lesson teachers
  • feel free to ask for help also on the unofficial FIT Discord server

Frequently Asked Questions

Can I discuss homework solutions with my friends? How can you tell someone plagiarized their solution?

It is up to you how much you wish to share with your classmates. Simple code, such as a function to compare two floating-point numbers, will always be almost identical across all of you. However, the homework assignments are complex enough for it to be nearly impossible for two people to write structurally identical code solving the given problem just by chance.

In case of serious suspicion that your code may have been plagiarized, you will be forced to take an oral exam after completing the practical and theoretical tests, where you will be asked to explain your solutions in detail.

Can I use Artifical Intelligence (GitHub Copilot, ChatGPT, and the like) to help me write code?

It is strongly discouraged that you do. First of all, you are putting yourself at risk of getting the same answers from the AI as your classmates, resulting in (unintentional) plagiarism, but also you will gain very little from having a computer write computer code for you. There is no AI allowed in the final exam, so keep that in mind.

Can I use an Integrated Development Environment (CLion, Visual Studio, etc.) to write code?

At first, we recommend starting with just a text editor and a command line, so that you learn exactly (in some sense…) how your source code becomes an executable program. All of the PA1 course can be done comfortably with just a basic text editor with syntax highlighting.

Nevertheless, if you understand the compilation process and solely wish to be more efficient when writing code or debugging, you are free to use any IDE that you like.

Again, keep in mind that your favourite IDE might not be available to you during the final exam.

How do I submit an assignment solution for code review?

TBA.

My program works on my machine, but not on ProgTest.

First, try compiling the program with the following flags set: -Wall -pedantic -O2 -g -fsanitize=address,undefined. Alternatively, you can take advantage of the compiler available in the ProgTest interface (main page -> compiler). If you can’t get your program to compile this way, read the error messages you’re getting, they will tell you everything you need to know.

Otherwise, one of the following issues may be at play:

1. You are submitting the wrong file.

Everyone goes through this at some point. Make sure you’re submitting source code (*.c), not an executable binary file, and make sure it is really the one you’re working on in your text editor or IDE.

2. You are using includes that are not allowed for the assignment.

With some assignments, you will get a list of headers that you may use at the beginning of the sample source file:

#ifndef __PROGTEST__
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
...
#endif

If you happen to use an IDE, it can happen that your IDE auto-suggests a function to use and automatically includes the corresponding header file without your knowledge. If that header file is not available in the test environment, you will get a compilation error.

3. A part of your solution is placed in a conditionally compiled block.

Any code that lies between the preprocessor directives #ifndef __PROGTEST__ and #endif is simply invisible to the ProgTest compiler. Therefore it is prudent to put the code for your solution elsewhere.

Vice versa, moving anything that was originally inside the conditionally compiled block outside may (and probably will) result in redeclarations of symbols or other compilation errors.

4. Your code has undefined behaviour.

Undefined behaviour in source code for a program means using the language in a way that the language specification does not guarantee the outcome.

A typical example is reading from uninitialized memory:

int main(void) {
    int n;

    printf("%d\n", n);

    return 0;
}

The result of the above snippet is dependent on the particular compiler implementation used, the level of optimizations, the state of the memory at run-time, and more. In other words, if the resulting program reaches this code, you can not rely on anything the program does next, which is somewhat undesirable.

Whenever your program behaves in an unexplainable way, and especially if the behaviour is different with and without optimizations turned on (-O0 vs. -O1, -O2, etc.), your code almost certainly contains undefined behaviour.

What does Segmentation fault mean?

A segmentation fault is a type of crash caused by accessing memory that does not “belong” (was not allocated) by the running process. Meaning your code is wrong or contains a bug.

How to troubleshoot:

Recompile the program with debug info and address sanitization:

g++ -Wall -pedantic -g -fsanitize=address program.c

Run the program with the critical input and read the output of the address sanitizer. Specifically, look for lines with either “INVALID READ” or “INVALID WRITE” and take note of the corresponding line number. If the address being read or written is 0x0000…, you have tried to de-reference a NULL pointer. Otherwise, you’re probably reading or writing out of bounds of an array or from/to a previously freed memory block.

Alternatively, you can use valgrind to find the crash:

Compile the program with debug info:

g++ -Wall -pedantic -g program.c

and run valgrind, supplying the name of the executable as an argument:

valgrind a.out

Enter the critical input and analyze the output.

Note that sometimes (if your code contains undefined behaviour), the problem might only reveal itself after optimizations are enabled. Hence, you can try compiling with the flags -O1, -O2 or -O3.

My program is behaving differently from what I’m expecting.

Debug it! First, make sure you are running the correct version of the correct executable file. Then, recompile the program with debug info and no optimizations:

g++ -Wall -pedantic -g -O0 program.c

Run the program in the GNU debugger (gdb). (Note that if you wish to redirect input from a file, you do that inside of gdb, not when invoking gdb from the shell).

gdb a.out

The following is an overview of useful commands in the debugger:

  • run, run < in.txt — run the program (opt. with redirected input)
  • s, start, start < in.txt — set a breakpoint for main and run the program (opt. with redirected input)
  • b <func | linenumber>, break <func | linenumber> — set a breakpoint at the specified location
  • d <num>, delete <num> — delete breakpoint number <num>
  • n, next — step one line forward
  • s, step — step one line forward, but follow function calls
  • fin, finish — continue until the current function returns
  • c, continue — continue until the next breakpoint (or the end)
  • p <expression>, print <expression> — print the given expression (can be a variable, pointer, register, …)
  • display <expression> — display the result of the given expression after every step (n, s, …)
  • list — list the next few lines of source code (I’d recommend using visual mode instead)
  • help
  • Enter — repeat the last command (does not litter the command history)
  • Up/Down arrows — browse command history (does not work in visual mode, see below)
  • bt — backtrace, useful after a crash, shows where the program crashed and what functions were called (call stack)
  • Ctrl+X A — toggles between visual mode and CLI mode

Set a breakpoint to the function / line number, where you wish to inspect how the program runs. Step through indiviual lines of code and observe how variables change and whether these changes align with your expectations.

If you use an IDE, debugging may be significantly easier thanks to the provided graphical interface. However, the process is largely the same.

To make the compiler scan for undefined behaviour in your code, use the -fsanitize=undefined switch.

Secret tip: Should you ever need to set a breakpoint at a particular place in code but only trigger it when a certain condition is met (for instance only on certain iterations of a loop), you can insert a breakpoint trigger directly into the program:

#ifndef __PROGTEST__
/* This will trigger a breakpoint only when my_condition(x) is true */
if (my_condition(x)) __asm__("int $3");
#endif

Such a program can then only be run in a debugger, otherwise it will crash with a SIGTRAP (trace/breakpoint trap) signal.


(Last update 28/9/2023.)