You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This writes a list of the prime numbers from 2 to 100.
program prime_list;
functionisPrime(i : longint) : boolean;
var n : integer;
beginfor n := 2to i div2dobeginif (i mod n) = 0thenbegin
isPrime := false;
exit;
end;
end;
isPrime := true;
end;
var
it : longint;
beginfor it := 2to100dobeginif isPrime(it) then
writeln(it);
end;
end.
2
3
5
...
97
Sorting Algorithms
Selection Sort
The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. This algorithm has time complexity O(N^2) for comparisons and O(N) for swaps and space complexity O(1).
program selection_sort;
const SIZE = 10;
var
sorted : array[1..SIZE] of double;
{ Prints the array to the console }procedureprintList(arr : arrayof double);
var it : integer;
beginfor it := 0to length(arr)-1do
write(arr[it]:6:3);
writeln;
end;
{ Randomizes the list }procedurerandomizeList(var arr : arrayof double);
var it : integer;
begin
Randomize;
for it := 0to length(arr)-1do
arr[it] := Random;
end;
{ Sorts the list linearly }proceduresortList(var arr : arrayof double);
var
it, curr, next : integer;
min, buffer : double;
beginfor curr := 0to length(arr)-1dobegin{ initializes the min var with the most left element }
min := arr[curr];
{ finds the minimum value of the right of the array }{ the minimum value index is in next }{ its value is stored on min }for it := curr to length(arr)-1dobeginif arr[it] <= min thenbegin
min := arr[it];
next := it;
end;
end;
{ swaps both the values }
buffer := arr[curr];
arr[curr] := arr[next];
arr[next] := buffer;
end;
end;
begin
randomizeList(sorted);
printList(sorted);
sortList(sorted);
printList(sorted);
end.
This is an efficient divide and conquer algorithm that sorts a list with O(N * ln(N)) time complexity.
This algorithm works by exploring the fact that joining two sorted lists into a sorted list only takes O(N) time complexity. So, the algorithm partitions the list into 2 and calls it recursively to each list. At the bottom level the algorithm is only called ether with a list of size 2 or 1, doing nothing or swapping the 2 elements. So this are the operations done by the algorithm for a 5 element array. Partitions were expressed by right brackets ([]).
program ProgramName;
(* all declarations of the program *)(* like type, var, const and functions/procedures *)begin(* all program instructions *)end.
Basic Data
Variables or Constants
Variables and constants both store data, with the difference that with variables the data is mutable and with constants the data is immutable. They both need to be declared in the following way:
var identifier : type = value;
const identifier : type = value;
The value in variables is optional, as well as the type in constants (the compiler can deduce it). All of the following variable constant declarations are valid:
var
height : Real;
year : 1970..2015;
money : Integer = 0;
const
max_elements = 100; (* type is integer *)name = "Alex"; (* type is string *)
first_letter : char = 'a';
Also, numeric variables can have a range specifier, to constrain the range of values of the variable. This can be done by the following syntax:
var ranged_int : 0..1000;
var ranged_char : 'a'..'z';
Data Types
Integer Numeric Types
Name
Size (bytes)
Range
Byte
1
0 .. 255
ShortInt
1
-128 .. 127
SmallInt
2
-2^15 .. 2^15-1
Word
2
0 .. 2^16-1
LongInt
4
-2^31 .. 2^31 -1
Integer
4 or 8
?
Real (Floating-Point) Numeric Types
Name
Size (bytes)
Bytes S/E/M
Single
4
1/8/23
Double
8
1/11/52
Extended
10
1/15/63
Real
4 or 8
?
Character Types
Name
Size (bytes)
Common Encoding
Char
1
ASCII / UTF8
WideChar
2
UTF16 / Latin1
Operators
These are the list of operators for different types of data:
Operator Family
Operators
Integer Algebra
+, -, *, DIV, REM
Real Algebra
+, -, *, /
Boolean Algebra
NOT, AND, XOR
Comparison
=, >, >=, <, <=, <>
Control Flow
There are a number of constructs in pascal to change the flow of the program, for creating conditionals or loops.
If-Then-Else
This branches the execution based on a Boolean condition. If one branch condition is true, then no other branch will be checked. The syntax is if-then-else ::= if condition then block [else if condition block]+ [else block];. For example this checks if a number is positive or negative or zero:
if number > 0then
answer := 'pos'elseif number < 0then
answer := 'neg'else
answer := 'zero';
Case
This checks a value against a number of possibilities. This is the same as writing if-then-else for each of the possibilities, but this form is more compact and more readable. However, this only runs if the case if equal to the variable checked against. So, this only checks for equality. The syntax is case-of ::= (Constant [, Constant]* : block ;)+ [else block;] end;
case number of0 : writeln('zero');
1 : writeln('one');
2 : writeln('two');
else writeln('another');
end;
For Loop
This loops a variable (called iterator) through a range. The syntax is for ::= FOR var := int (downto|to) int do block. For example, this prints all the numbers from 0 to 100:
for i := 0to100dobegin
writeln(i);
end;
While Loop
This loop repeats while a condition is met. This condition is evaluated in the beginning, so if the condition is not met in the beginning, the loop will never be executed. The syntax is while ::= while condition do block. For, example, this prints the numbers from 100 to 1:
i := 100while i > 0dobegin
writeln(i);
i := i - 1;
end;
Repeat-Until Loop
This loop, like while, also repeats until a condition is met. However, the condition is only evaluated at the end of each loop. This ensures that the loop is run at least once. The syntax is repeat-until ::= repeat block until condition;. For example, this prints what the user types, until he types exit.
repeatbegin
readln(input);
writeln(input);
end;
until compareStr(input, 'exit') = 0;
Procedures and Functions
Procedures and Functions are ways to group blocks of code. This increases abstraction, cleaner code and fewer errors. Both procedures and functions have input variables, but only functions can have output.
Procedures
A procedure groups blocks of code without any output. The syntax is:
procedurename (arg1 : type1, arg2 : type2);
(* declaration of vars and consts *)begin(* code instructions *)end;
Functions
Functions groups code and has an output. The syntax is very similar to a procedure:
functionname (arg1 : type1, arg2 : type2) : return-type;
(* declaration of vars and consts *)begin(* code instructions *)end;
Return
Return is the output of a function. To set the output, a variable is created inside the function body with the same name of the function. To change the output is just to change this variable. For example, take a loop at this identity function (returns the input unchanged):
functionidentity(input : Integer) : Integer;
begin
identity := input;
end;
How to call the procedures and functions
To call a function or procedure just pass the input arguments inside round brackets (()) after the function/procedure name, for example, num := identity(123);.
Scope
Each procedure or function have a local scope. This means that each variable that is declared inside the function/procedure body is only available to the function itself. This is called local variables. Also, the variables are initialized each time a function is called, and are destructed in the end of execution. There are on persistent of this values. For example:
functioni_have_scope() : integer;
var
i_am_inside : integer = 10;
begin
i_have_scope := i_am_inside;
end;
(* ... *)(* program code *)(* this will not compile, as i_am_inside does not exists in this scope *)
number1 := i_am_inside;
number2 := i_have_scope(); (* number1 is now 10 *)
number2 := number2 + 1;
number3 := i_have_scope(); (* number2 will still be 11 *)
However, functions can change variables outside its scope, if they are defined in a higher scope. This is called side-effects. For example:
(* declaration of a global variable *)var global_var : Integer;
(* procedure that changes global_var *)procedurechanges_var();
begin
global_var += 1;
end;
(* program code *)
global_var := 0; (* global_var is now 0 *)
changes_var(); (* global_var is now 1 *)
This side effects can be bad because there are no explicit change of the outside variables, with can lead to unpredictable behavior. To avoid this bugs caused by this side-effects, it is recommended to write functions that do not change any global variables. This functions are called pure-functions and its output is only dependent on its input, and not on external variables.
Arguments by value or reference
Lets look at the following procedure add_one:
procedureadd_one(n : integer);
begin
n := n + 1;
end;
Now, if we call the procedure in the variable n, add_one(n), we verify that the variable did not change. Why? This is because the variable was passed to the function by value. When the function is called, the arguments are copied inside the scope of the function. So, when the variable n was changed, only the local copy it was changed, which then was destroyed when the function was ended. In the end, the variable n was not changed.
To actually change the variable n inside the scope of the procedure, we need to pass the argument by reference. This means that the real variable is passed, and not a copy of it. To do that in pascal, just write var before the variable name of the argument. The new procedure add_one will the be:
procedureadd_one(var n : integer);
begin
n := n + 1;
end;
Now, if we call add_one(n), we can then see that n was incremented.
Another example of the power of this feature is the procedure swap:
procedureswap(var a, b : integer);
var c : integer;
begin
c := a;
a := b;
b := c;
end;
However, because we are changing the state of outside variables, passing the variables by reference is a method only used if we really want to change the input variables. So, a pure function do not need to have its arguments passed by reference.
Recursive Functions
A recursive function is such a function that calls itself, unless a exit condition is met (tail-call). For example, factorial is a function that can be defined recursively: 0! = 1 and n! = n * (n-1)!
functionfactorial(n : longint) : longint;
beginif n = 0then
factorial := 1else
factorial := n * factorial(n-1);
end;
A lot of algorithm can be more easily defined with recursively, however, if the function never reaches the end condition, the program will crash, due to a stack overflow. So, the definition of exit conditions is critical for the stability of the program. Also, each time the function is called, more space needs to be used to store the local variables. So, deep recursion can be memory intensive.
Function Overloading
Overloading is the ability in a programming language to create multiple function with the same name, but with a different argument arity (number and order) and/or type. At compile time, the compiler will call the right function based on the arguments.
For example, suppose we wanted to create a function that returns the volume of solids (cube, cylinder and a cuboid in this example). We can create a overloaded function called volume with 3 implementations, one for each solid. Then, base on the arguments, the correct function will be called.
--- volume of a cubefunctionvolume(side : real);
begin
volume := side * side * side;
end;
--- volume of a cylinderfunctionvolume(radius * height : real);
begin
volume := 2 * PI * radius * radius * height;
end;
--- volume of a cuboidfunctionvolume(height, width, length : real);
begin
volume := height * width * length;
end;
...
volume(2.0); --- returns the volume of the cube
volume(2.0, 3.0); --- returns the volume of a cylinder
volume(2.0, 3.0, 4.0); --- returns the volume of a cuboid
Sometimes the compiler will implicitly convert the types of the arguments to match the right function to be called. For example, if we called the function volume like volume(3); the compiler will convert the integer 3 to the float 3.0 and call volume(3.0).
Arrays
Arrays is a data structure capable of storing a fixed number of homogeneous data (same data type). To declare a array we use the following syntax:
var array_name : array [range] of el_type;
For example:
var numbers : array[0..5] of double;
Array elements can be accessed with right brackets with the index of the element, like array[4] := 10;
Initialization is also possible, by using literal arrays like (1, 2, 3, ..). For example:
var first_numbers : array[1..5] of integer = (1, 2, 3, 4, 5);
Multidimensional arrays, like matrices, can be defined by defining multiple index ranges or by defining multiple level arrays. To access the elements use multiple indexes, one for each dimension, comma separated.
var agenda : array[1..31] ofarray[0..23] of OccupationType;
agenda[1][8] := Job; (* At day 1 at 8 hours the Occupation is Job*)var matrix : array[1..5, 1..5] of double;
matrix[1, 1] := 0.0;
Type Declaration
It is possible to define new types inside the program. This helps create less alias of the same type. For example, if using always a 3x3 matrix, we can just define a new type called Matrix3, like so:
type Matrix3 = array[1..3, 1..3] of double;
Now we can use this type concisely in our entire code, without the need to write its definition all the times. For example, we can now define functions that uses this type, as well as variables, like always.
We can also use the type keyword to declare enumerated types. This creates new identifiers that have an unique values (usually numeric). This can be declared as following:
type MonthType = (January = 0, February, March, ..., December);
var Month : MonthType = January;
This provides a safe abstraction instead of using numeric types. This is usually used with the case-of.
case month of
January : writeln('New year!');
...
December : writeln('Prepare for Christmas!');
Records
Record is a structured data type, which can contain heterogeneous data types together, unlike arrays, which can only contain homogeneous data. Each element of the record is called a field and have an unique identifier inside the record. Records are defined like
record
field1 : type1;
field2 : type2;
...
end;
For example, look at this record representing the type Person:
type Person = recordname : record first, last : string;
sex : (Male, Female);
age : integer;
end;
Each field can be accessed using the dot operator (.) like
var anna : Person;
...
anna.name.first = 'Anna';
anna.name.last = 'Mathias';
anna.sex = Female;
anna.age = 25;
Literal record are build like:
var petro : Person = (
name : (first : 'Petro'; last : 'Diaz');
sex : Male;
age : 32;
);
As records are compacted data types, we can pass record variables directly to functions and procedures:
Writing and reading streams are a must for every program. In pascal, there is possible to write and read from the stdout and stdin (console), as well as from files. It's possible to use binary data or text data, usually encoded in ASCII.
IO to the standard buffers
Each program has a stdout and stdin. These are streams that interface with the terminal. To write to the stdout, we use the procedures write and writeln. The later just writes a newline (\n) at the end of each write. read and readln are the procedures to read from the stdin. Those functions are overloaded for each data type.
Files are a way to store data permanently in the disk. There are 1 types of files in pascal, Untyped Files, Typed Files and Text Files. The first ones are binary files and the last one is a text file (human-readable). In Untyped Files, data is read in byte chunks and very low level. In Typed Files, the data type is known but is stored in binary form (raw). In Text Files data is stored as a character stream. This is much more expensive to read and write and takes much more disk space compared to binary files, but it's human-readable, which makes it very convenient for storing information.
To create a file variable, just use the types file (untyped), file of something (typed) or text (text).
var binary_file : file;
var integer_file : fileof integer;
var text_file : text;
Open files
To open a file, we must first assign the file variable to the filename. This is done with the function assign. Then, we must choose if we want to create a new file, append to a already created file or read from a file. There are 3 functions for this: rewrite (create new file), append (append to file) and reset (read from file). Then, to close the file, we must call the close function.
Writing and reading data
Reading and writing to a file is done in the same as with the standard buffers, but the file variable needs to be specified as the first parameter. Also, only in text file we can call the writeln and readln procedures. Writing is done with write(file, ...) and reading is done with read(file, ...).
Position in the file
File io operations are done in a certain position of the file. To keep track of this position, as with indexes in arrays, there is a cursor that stores the current position in the file. This cursor is not available directly but some there are functions to interface with it. Eof, for example, checks if we reached the end of the file (for reading operations).
File handling function
Here are all the functions to handle with files
Name
Description
assign
Assign a filename to a file
close
Closes an open file
rewrite
Open a file for writing
append
Open a file for appending
reset
Open a file for reading
eof
Checks for the end of file
filePos
Gets the current position
seek
Sets the current position
seekEOF
Sets the position to the EOF
seekEOLN
Set the position to the end of line
write
Writes to the file
writeln
Writes to the file and writes a NL character
read
Reads from the file
readln
Reads from the file until it find a NL character
blockRead
Reads a block of data from an untyped file
blockWrite
Writes a block of data from an untyped file
erase
Erases the file from the disk
truncate
Truncates the file at position
Example of a typed file
Program that writes the first 100 squares to the file squares.dat:
program squares;
varfile : typeof integer;
var it : integer;
const filename = 'squares.dat';
begin
assign(file, filename);
rewrite(file);
for it := 1to100do
write(file, it*it);
close(file);
end.
This program reads the file squares.dat and sums all the numbers in that file:
program sum;
varfile : typeof integer;
var num : integer;
var sum : integer = 0;
const filename = 'squares.dat';
begin
assign(file, filename);
reset(file);
whilenot eof(file) dobegin
read(file, num);
sum := sum + num;
end;
close(file);
writeln(sum);
end.
amazin~
i apreciate what u did