1

Wykład VIII

Języki programowania

Algorytmy i struktury danych
Wyższa Szkoła Biznesu
Semestr III Informatyka
stosowana

2

Interesuje nas

wykonywanie algorytmów

przy pomocy komputera

Naszym

największym

zainteresowaniem są jednak objęte
algorytmy przeznaczone do wykonania
przez komputery, a zatem powinniśmy
poświęcić nieco czasu na odniesienie
algorytmów

do

prawdziwych

komputerów.

3

Komputer potrafi zwykle

wykonać niewielką ilość

prostych operacji

Nawet najbardziej wyrafinowany komputer jest w

rzeczywistości tylko ogromną, dobrze zorganizowaną

masą bitów i, co więcej, normalnie potrafi on wykonywać

na nich jedynie niewielką liczbę krańcowo prostych

operacji,

takich

jak

zerowanie,

przerzucanie

i sprawdzanie.
W jaki sposób przedstawiamy algorytm prawdziwemu

komputerowi i jak sprawiamy, że wykonuje on

odpowiedni proces tak, jak to zamierzono?
Powiedzmy to jeszcze bardziej bezceremonialnie. Jak

sprawiamy, że głupia maszyna o tak małych

zdolnościach w imponujący sposób realizuje nasze

subtelne i starannie opracowane algorytmy?

4

Algorytmy muszą być

zapisane w jednoznaczny i

formalny sposób

Pierwszym spostrzeżeniem jest to, że nasze algorytmy

muszą być zapisane w jednoznaczny i formalny

sposób.
Zanim spróbujemy zrozumieć, w jaki sposób obracając

bitami można wypełnić proste zadanie, np. „przebiegnij

listę, dodając każdą płacę do liczby «na boku»”, musimy

zadanie to dokładnie określić odpowiadając na pytania:

– Gdzie komputer znajdzie tę listę?
– Jak ją przebiegnie?
– Gdzie znajdzie płacę i liczbę ,,na boku”? Itd.

Zadanie „przebiegnij listę” nie jest wcale wiele bardziej

dokładne i jednoznaczne niż „ubijaj białka aż do

spienienia”.

5

Języki programowania,

programy, programiści

Aby opisać algorytm na użytek komputera,
posługujemy się językiem programowania, w
którym piszemy programy.
Program to oficjalne i formalne wydanie algorytmu,
nadające się do wykonania przez komputer.
Język programowania składa się z notacji i reguł,
według których pisze się programy, a osoba pisząca
program zwie się programistą. (Ta osoba nie musi
być autorem algorytmu, na którym opiera się
program.)

6

Programy wymagają

precyzyjnej składni

Język programowania wiąże się zwykle ze sztywną składnią,

dopuszczającą używanie jedynie specjalnych kombinacji wybranych

symboli i słów kluczowych.
Każda próba nadużycia tej składni może okazać się fatalna: jeśli np.

napisze się wczytaj X w języku, którego instrukcje wczytywania są

postaci

wprowadź

X,

możliwe,

że

wynikiem

będzie

bezceremonialne BŁĄD SKŁADNIOWY E5414 W WIERSZU 108. To

oczywiście wyklucza nawet tak uprzejme, ale nieprecyzyjne

żądania, jak „proszę wczytać wartość X z wejścia”.
To prawda, że uprzejme, obszerne instrukcje są przyjemniejsze dla

ludzi i być może są dla nich bardziej jednoznaczne niż ich zwięzłe i

bezosobowe odpowiedniki; jest także prawdą, że chcielibyśmy, aby

komputery były tak przychylne użytkownikowi, jak to tylko jest

możliwe. Jednakże trzeba przeciwstawić te fakty aktualnemu

brakowi zdolności rozumienia przez komputery swobodnie

mówionego (lub pisanego) języka naturalnego.

7

Co zawiera formalna

składnia języka

programowania ?

Formalna składnia typowego języka programowania

zawiera:

– systematyczne warianty kilku struktur sterujących,
– systematyczne sposoby definiowania rozmaitych

struktur danych

– systematyczne wzorce podstawowych instrukcji.

Muszą one należeć do zbioru dopuszczalnych

instrukcji

stosowanego

języka

programowania,

ponieważ komputer nie wykona żadnej instrukcji,

nawet najbardziej jasnej i jednoznacznej, jeśli nie ma

jej wśród tych, które dopuszcza dany język.

8

Przykład

Algorytm sumowania liczb

od 1 do N

W typowym (hipotetycznym)

języku

programowania

JP

można

by

zapisać,

jak

następuje:

wczytaj N;
X:=0;
dla Y od 1 do N wykonaj
X:=X+Y
koniec; wypisz X.

X:=0

jest

instrukcją

przypisania, która nadaje

zmiennej

X

wartość

początkową 0 (w algorytmach

zapisywaliśmy ją jako X←0).

Zwróć uwagę na słowa kluczowe

zapisane grubszą czcionką; są one

częścią składni JP
Oznacza to, że formalna definicja

składni

najprawdopodobniej

zawiera klauzulę stwierdzającą, że

jednym z poprawnych rodzajów

instrukcji w tym języku jest

instrukcja-dla,

której

ogólny

wzorzec składa się ze słowa

kluczowego

dla,

po

czym

następuje poprawny nagłówek-

dla, po czym następuje wykonaj,

po czym następuje poprawna

instrukcja, po czym następuje

koniec

9

Notacja BNF (Backus-Naur

Form, od nazwisk

wynalazców)

Definicje składni można zapisać symbolicznie w notacji

zwanej BNF w następujący sposób (,,|” oznacza ,,lub”):

<instrukcja>:<instrukcja-dla>|<instrukcja-

przypisania>|...
<instrukcja-dla>:

dla <nagłówek-dla>

wykonaj

<instrukcja> koniec
Opis klauzuli nagłówka mógłby brzmieć:

<nagłówek-dla>: <zmienna> od <wartość> do

<wartość>

<wartość> można wtedy określić jako zmienną, jawnie

podaną liczbę lub jakiś inny obiekt.

10

Schematyczny sposób

przedstawiania reguł

składniowych

11

Schematyczny sposób

przedstawiania reguł

składniowych

12

Podobnie są narzucane

wzorce definiowania

struktur danych

Np. tablicę TA o wymiarach 50 na 100, której wartości

mogą być liczbami całkowitymi, można by zdefiniować

w hipotetycznym języku JP instrukcją

definiuj TA tablica [1..50, 8..107] w niej liczby

całkowite

a język mógłby dopuścić odwołania do elementów

tablicy TA wyrażeniami postaci

TA(wartość, wartość)

Zauważ, jak określiliśmy nie tylko wymiary TA, lecz

także jej wartości indeksów; wiersze tablicy

ponumerowano 1, 2, ..., 50, ale jej kolumnom (z

jakiegoś powodu) nadano numery 8, 9, ..., 107.

13

Składnia wyznacza

znacznie więcej

W rzeczywistości składnia wyznacza znacznie

więcej niż tylko dostępne struktury sterujące i

struktury danych oraz operacje elementarne.
Zwykle język ma sztywne reguły nawet w tak

drobnych kwestiach, jak poprawne ciągi symboli,

których można używać do nazywania zmiennych

lub struktur danych, i maksymalna liczba cyfr

dopuszczalna w wartościach numerycznych.
Niektóre

języki

ograniczają

długości

nazw

zmiennych do najwyżej, powiedzmy, ośmiu

symboli, z których pierwszy ma być literą alfabetu.

14

Ważna jest także sprawa

interpunkcji

W językach programowania nie należy do rzadkości
wymaganie, aby po pewnych rodzajach instrukcji
następował średnik, a po innych - odstęp, aby
komentarze były ujęte w specjalne nawiasy, itd.
Biada tym, którzy do tych wymagań się nie
zastosują (dopadnie ich zapewne „choroba
średnika”).
Niedługo poznamy szczegółowy opis składni
konkretnego języka programowania, z regułami
stosowania średników i całą resztą.

15

Programy wymagają

precyzyjnej semantyki

Wyposażenie języka w precyzyjną składnię stanowi

tylko część zadania stojącego przed projektantem

języka programowania.
Bez formalnej i jednoznacznej semantyki a więc bez

znaczenia

każdego

wyrażenia

dozwolonego

składniowo, składnia jest niemal bezwartościowa.
Gdyby nie podano znaczenia instrukcji, w naszym

hipotetycznym języku JP taki oto fragment programu

dla Y od 1 do N wykonaj

mógłby, oznaczać „odejmij Y od 1 i zapamiętaj wynik

w N”.

16

Bez reguł semantycznych

nie poznamy

przeznaczenia instrukcji

Co gorsza, któż powiedział, że słowa kluczowe dla,

od, do itp. mają mieć coś wspólnego z ich

znaczeniem w konwencjonalnej polszczyźnie?
A może ten sam fragment programu oznacza „wyzeruj

całą pamięć komputera, zmień wartości wszystkich

zmiennych na 0, wypisz »DO DIABŁA Z JĘZYKAMI

PROGRAMOWANIA« i zatrzymaj się!”?
Któż powiedział, że „:=” oznacza „przypisz” i że „+”

oznacza „plus”? Któż powiedział, że instrukcje

wykonuje się w takiej kolejności, w jakiej są napisane?

A może „;” oznacza „po wykonaniu tego, co

następuje”, nie zaś ,,a potem wykonaj, co następuje”?

17

Na szczęście w językach

znaczenia symboli są podobne do

znaczeń w języku angielskim

Oczywiście moglibyśmy odgadnąć, co to oznacza,

ponieważ projektant języka JP tak dobrał zapewne słowa

kluczowe i symbole specjalne, aby ich znaczenia były

możliwie najbardziej zbliżone do ogólnie przyjętych.
Ale komputer na podstawie takich przypuszczeń działać

nie może. Gdyby nawet mógł w jakiś sposób

wywnioskować konwencjonalne znaczenie słów i takich

symboli, jak „+”, skąd wiedziałby, bez wyraźnego

pouczenia, co zrobić z nagłówkiem pętli

dla Y od 1 do N wykonaj

gdy wartością N jest powiedzmy -314.1592?

18

W poznawaniu składni i

semantyki języka wspiera

nas dokumentacja

Wydaje

się

zatem

jasne,

że

język

programowania wymaga nie tylko sztywnych
reguł

definiowania

postaci

poprawnego

programu, ale także równie sztywnych reguł
definiowania jego znaczenia.
Projektanci i producenci dostarczają jednak
szczegółową dokumentację języka, całe jej
tomy. Te podręczniki języka zawierają
bogactwo informacji dotyczących zarówno
składni, jak i semantyki.

19

Przystępujemy do

kodowania

Mamy zatem język programowania JP, składnię,

semantykę i całą resztę, i właśnie skończyliśmy

opracowywanie algorytmu A rozwiązania pewnego

zadania algorytmicznego.
Przystępujemy teraz do zaprogramowania tego

algorytmu w języku JP, czynności określanej niekiedy

jako kodowanie A w JP, i chcemy przedstawić

powstały program, nazwijmy go A

P

naszemu

komputerowi.
Cóż dzieje się dalej? Odpowiedź brzmi, że w zasadzie

istnieją dwie możliwości, zależnie od tego, jakiego

języka i komputera użyjemy.

20

Od algorytmu do języka

maszynowego

Program A

P

możemy wprowadzić do pamięci komputera

wystukując go na klawiaturze, wczytując z urządzenia

takiego jak dysk, odbierając z innego komputera za

pośrednictwem elektronicznego kanału komunikacyjnego lub

w jakiś inny sposób (same nośniki fizyczne i sposób ich

używania, nas tutaj nie interesują, w przeciwieństwie do

tego, co dzieje się potem).
Program A

P

przechodzi pewną liczbę przekształceń, które

stopniowo sprowadzają go „w dół” do poziomu, na którym

komputer już może sobie poradzić. Ostatecznym wynikiem

tych przekształceń jest program A

M

na poziomie maszyny

(mówi się o nim również, że jest napisany w języku

maszyny), gdyż już teraz komputer „rozumie” jego operacje

podstawowe, takie jak instrukcje manipulowania bitami.

21

Języki programowania

wysokiego poziomu

Liczba przekształceń bywa różna, zależnie od języka i

komputera, ale najczęściej jest ich od dwóch do czterech.
Obiektami pośrednimi są zwykle poprawne programy w coraz

to prymitywniejszych językach programowania. Ich repertuar

struktur sterujących i struktur danych stopniowo, podobnie jak

instrukcji podstawowych, staje się coraz skromniejszy, aż

wreszcie

pozostają

jedynie

najbardziej

elementarne

możliwości działania na bitach.
Dopiero po tej ostatecznej fazie przekształceń komputer może

uruchomić (lub wykonać) pierwotny program A

M

.

Jest już dla nas teraz oczywiste, dlaczego języki takiego

rodzaju jak ten, w którym napisano pierwotny program

użytkownika A

P

, nazywają się językami programowania

wysokiego poziomu

22

Przypomina to

podprogramy

Przekształcenia,

o

których

mówiliśmy

przypominają nieco zastępowanie procedur ich
treścią.
Na

instrukcję

w

języku

programowania

wysokiego poziomu można patrzeć jak na
wywołanie podprogramu lub jak na instrukcję
podstawową, która jednak dla komputera nie
jest dostatecznie podstawowa.
W konsekwencji trzeba ją uściślić i sprowadzić
do poziomu kompetencji komputera.

23

Kompilacja, asembler

Pomówmy o pierwszym przekształceniu, zwanym kompilacją, w

którym program wysokiego poziomu A

P

zostaje przetłumaczony

na program A

S

w języku niższego poziomu, zwanym językiem

adresów symbolicznych lub asemblerem.
Języki adresów symbolicznych różnią się dla różnych maszyn, ale

z reguły stosuje się w nich dość proste struktury sterujące,

przypominające instrukcje skocz oraz konstrukcje jeśli-to;

operują nie tylko bitami, lecz także liczbami całkowitymi i

ciągami symboli.
Mogą one odwoływać się bezpośrednio do adresów w pamięci

komputera (ogromnego obszaru zawierającego całe stosy bitów),

mogą odczytywać spod tych adresów wszelkie zakodowane

liczby i napisy, i mogą tamże zapamiętywać kody liczb i napisów.

24

Przykład (hipotetycznego)

asemblera

Typową konstrukcję pętli wysokiego poziomu:

dla Y od 1 do N wykonaj
<treść pętli> koniec

można przetłumaczyć na jej odpowiednik w języku adresów

symbolicznych:

LDS 0,Y

(załaduj stałą 0 pod adres Y)

PĘTLA POR N, Y

(porównaj wartości pod adresami N i Y)

SKR RESZTA(jeśli równe, skocz do instrukcji o etykiecie RESZTA)
DDS 1,Y

(dodaj stałą 1 do wartości pod adresem Y)

<przetłumaczona treść pętli>
SKO PETLA (skocz z powrotem do instrukcji o etykiecie PĘTLA)

RESZTA

(reszta programu)

Przekształcanie

programu

wysokiego

poziomu na kod

maszynowy

Proces kompilacji, tłumaczący

programy

komputerowe

wysokiego poziomu na język

adresów symbolicznych sam

jest również wykonywany przez

program

komputerowy

(kompilator)
Proces

przekształcania

na

niższy

poziom,

w

którym

kompilacja jest pierwszą i

najbardziej

zawiłą

częścią,

ilustruje rys.
Pozostałe

kroki

tłumaczą

asembler na język maszynowy.

26

Oprogramowanie

systemowe

Warto zaznaczyć, że kompilatory różnych języków

wysokiego poziomu, jakie obsługuje dany komputer,

często (choć nie zawsze) należą do dużej grupy różnych

programów dostarczanych przez producenta (komputera

bądź

systemu

operacyjnego),

zwykle

zwanych

oprogramowaniem systemowym.
Ich ogólną rolą jest ułatwianie współpracy z komputerem

na wysokim poziomie i jednoczesne odgrodzenie

użytkownika od wielu szczegółów niskiego poziomu

związanych z trybem współpracy, np. uruchomieniem

programów

napisanych

przez

użytkownika,

komunikowaniem się z innymi komputerami, sprzęganiem

się ze specjalnym wyposażeniem zewnętrznym...

27

Interpretatory i

natychmiastowe

wykonanie

Jest jeszcze inny sposób, w jaki komputery wykonują

przedstawione im programy, który nie obejmuje

tłumaczenia całego programu na język niższego poziomu.
Każda

z instrukcji

wysokiego

poziomu

zostaje

przetłumaczona

na

instrukcje

poziomu

maszyny

natychmiast po jej napotkaniu, a te z kolei od razu się

wykonuje. W pewnym sensie interpreter pełni rolę

„pseudoprocesora” wykonując instrukcje wysokiego

poziomu jedną po drugiej, dokładnie tak, jak są podane.
Mechanizm odpowiedzialny za to lokalne tłumaczenie i

natychmiastowe

wykonanie

jest

też

fragmentem

oprogramowania

systemowego,

nazywanym

interpretatorem (interpreterem).

28

Zalety i wady

interpretowania

programów

Podejście interpretacyjne ma pewne oczywiste zalety, m.in.

zwykle łatwiej napisać byle jaki, ale użyteczny

interpretator niż sensowny kompilator;
wykonywanie prowadzone przez interpretator pozwala na

łatwiejsze śledzenie i podsumowanie wykonania programu.

Są jednak cechy interpretacji niekorzystne w stosunku do

kompilacji
nie ma zwartego pliku wykonywalnego
trzeba rozpowszechniać kod źródłowy (trudno ochronić

prawa autorskie)
wolniejsze wykonanie (każdorazowo trzeba dokonywać

interpretacji)

29

Kompilować czy

interpretować ?

To, czy komputer będzie kompilował, czy
interpretował dany program, zależy od
przeznaczenia danego programu, samego
komputera,

języka

programowania,

i

konkretnego

pakietu

oprogramowania

systemowego, którego używamy.
Niektóre języki programowania nadają się do
interpretowania bardziej niż inne, wszystkie
jednak mogą w zasadzie być kompilowane.

30

Dlaczego nie

algorytmiczne Esperanto?

Od czasu, gdy we wczesnych latach pięćdziesiątych

zaczęły

pojawiać się języki programowania

wysokiego poziomu, zaprojektowano ich setki oraz

napisano dla nich kompilatory i (lub) interpretatory,

a nadal nowe języki pojawiają się jak grzyby po

deszczu.
Dlaczego? Czynie byłoby lepiej mieć jeden język

uniwersalny, takie algorytmiczne Esperanto, w

którym zapisywałoby się wszystkie algorytmy i

którego każdy mógłby się łatwo nauczyć? Skąd

taka mnogość języków? Czym się różnią ? Kto

używa których języków i w jakich celach?

31

Dlaczego nie

algorytmiczne Esperanto?

Odpowiedź

Zasadniczo są dwie przyczyny tego zjawiska:

– nowe osiągnięcia sprzętowe (choć dziś w dużej

mierze udaje się uwolnić wiele języków od
bezpośredniego, ścisłego związku ze sprzętem).

– oraz nowe i zróżnicowane dziedziny zastosowań

;

Obie stwarzają zapotrzebowanie na nowe języki
programowania.

Badania

nad

językami

programowania należą do z najbardziej się
rozwijających i przyciągających powszechną uwagę
dziedzin informatyki.

32

Badania nad językami

programowania

Ludzie chcą języków zarówno uniwersalnych, jak i przeznaczonych

do szczególnych zastosowań oraz ich precyzyjnej definicji i sprawnej

realizacji.
Wymyśla się wyrafinowane techniki kompilacji i tłumaczenia, proponuje

się nowe struktury sterujące i nowe struktury danych oraz wprowadza

się silne mechanizmy umożliwiające programistom definiowanie ich

własnych struktur danych.
Pożądane są języki zachęcające do dobrego stylu programowania

i wszyscy próbują zaprojektować je tak, aby zawrzeć w nich rozmaite

zalecane idee budowy algorytmów.
Badacze

interesują

się

opracowaniem

środowisk

programistycznych, czyli przychylnych użytkownikowi systemów

konwersacyjnych, pozwalających programiście pisać, redagować,

zmieniać, wykonywać, analizować, poprawiać i symulować programy.
Fascynujące badania dotyczą wizualnych języków programowania,

umożliwiających rysowanie programów zamiast ich pisania.

33

Uniwersalność języków

programowania

Ostatnia nasza uwaga dotyczy uniwersalności języków

programowania.
W pewnym technicznym sensie praktycznie wszystkie języki

programowania są równoważne pod względem swojej siły

wyrazu. Każde zadanie algorytmiczne rozwiązywalne w

jednym języku jest w zasadzie rozwiązywalne również w

każdym innym języku.
Różnice między językami są pragmatyczne i dotyczą

przydatności do pewnych, zastosowań, przejrzystości,

struktury, sprawności realizacji i algorytmicznych sposobów

myślenia.
Wobec znaczących różnic między językami programowania

ten fakt może być przyjmowany jako coś niespodziewanego.