2021-12-24 / Bartłomiej Kurek
Project Euler: Krótki przegląd języków programowania

• algo • euler • languages

Project Euler to bogate archiwum ciekawych problemów algorytmicznych, których rozwiązania wymagają zarówno zrozumienia danego problemu, jak i znajomości języka programowania, którego do rozwiązania użyjemy. W tym artykule podejdziemy do pierwszego z problemów w archiwum. Jest on poniekąd rozszerzeniem popularnego fizz/buzz. Problem jest na tyle trywialny, że wykorzystamy go do przyglądnięcia się kilku odmiennym językom programowania. Omówimy po krótce dziedziny, w których te języki najczęściej mają zastosowanie, a ponadto przyjrzymy się ich podstawowej, minimalnej składni, która wystarczy do rozwiązania pierwszego z problemów Project Euler.

Istotą rozwiązań problemów zebranych w Project Euler jest efektywne wykorzystanie języków programowania i zasobów maszyny. Niektóre z problemów wymagają "pogłówkowania" nad złożonością obliczeń, a naiwna implementacja może się okazać bardzo wolna.

Krótką charakterystykę językow i ich składni zrealizujemy wykonując podstawowe: "hello world" lub 2 + 2, a następnie rozwiązując sam problem.

Kod rozwiązań w prezentowanych językach dostępny jest w repozytorium git.

Definicja problemu

Pierwszy problem zdefiniowany jest następująco:

  Multiples of 3 and 5
  Problem 1

  If we list all the natural numbers below 10 that are multiples of 3 or 5,
  we get 3, 5, 6 and 9. The sum of these multiples is 23.
  Find the sum of all the multiples of 3 or 5 below 1000.

Naszym zadaniem jest zatem znalezienie w przedziale [0, 1000) sumy wszystkich liczb naturalnych, które są wielokrotnością liczb 3 lub 5.

Python

Python to język dynamiczny, ogólnego zastosowania (generic purpose). Referencyjna implementacja jest stworzona w języku C (CPython). Zastosowanie tego języka jest bardzo szerokie: narzędzia, aplikacje webowe, sieci, data science, automatyzacja, wizualizacja, narzędzia GUI, gry... Ogólnie - w Pythonie pisze się praktycznie wszystko. Istnieje wiele środowisk dedykowanych do tego języka. Składnia (syntax) jest jedną z najprzyjemniejszych i najbardziej oczywistych. Język pozwala na korzystanie z bibliotek innych języków (ctypes, ffi). Intepreter uruchamiamy komendą python.

Pierwsze wrażenie

Hello world.

# python -q
>>> print("hello world")
hello world
>>> 2 + 2
4

"Sanity check":

>>> 1 + "11"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'

Rozwiązanie problemu

Składnia języka Python pozwala nam wykorzystać mechanizm list comprehension. W ten sposób uzyskamy od razu listę wartości spełniających warunek, które następnie zsumujemy wbudowaną funkcją sum(). Rozwiązanie problemu można zatem sprowadzić do jednej linii kodu:

>>> sum([_  for _ in range(1000) if _ % 3 == 0 or _ % 5 == 0])
233168

R

R to bardzo bogate środowisko do zastosowań w dziedzinie statystyki. Oficjalna implementacja (GNU: r-project.org) jest stworzona w C, w Fortranie i w samym R. Do R znajdziemy również wiele dedykowanych środowisk umożliwiających wygodną pracę, włączając w to analizy i wizualizacje. Sam interpreter możemy uruchomić w terminalu.

Pierwsze wrażenie

# R -q
> print("hello world")
[1] "hello world"
> 2 + 2
[1] 4

> 1 + "11"
Error in 1 + "11" : non-numeric argument to binary operator

Rozwiązanie problemu

Składnia R pozwala na podobne rzeczy jak w Python:

n <- 1:1000 - 1
> sum(n[n %% 3 == 0 | n %% 5 == 0])
[1] 233168

Możemy też napisać to w sposób "standardowy":

sum = 0;
for(i in 1:1000 - 1) {
    if(i %% 3 == 0 || i %% 5 == 0) {
        sum = sum + i;
    }
}

print(sum);

Jeśli umieścimy kod w pliku (tutaj plik solution.r), to będziemy mogli uruchomić go za pomocą komendy Rscript:

$ Rscript R/solution.r
[1] 233168

Lisp

Lisp to rodzina języków funkcyjnych. Wiele języków programowania czerpie z niego inspirację. Wydawać mogłoby się, że nie jest dzisiaj w powszechnym użyciu, ale na jego podstawie budowano całe ekosystemy, systemy operacyjne (np. Genera) oraz alternatywne architektury komputerów. Prawdopodobnie najbardziej znanym ekosystemem wykorzystującym dzisiaj Lisp jest (złośliwi słusznie powiedzą - "system operacyjny") Emacs. Historia LISP sięga lat 1950+, z tego języka pochodzą elementy funkcyjne, refleksja, metaprogramming i szereg niezliczonych odkryć. Nie może zatem tego języka zabraknąć w tym zestawieniu, ale nie sposób też opowiedzieć o nim w kilku zdaniach.
Historię tego odkrycia znajdziemy u samego źródła. Ja posłużę się dwoma krótkimi cytatami:

" It's not an invention, but a discovery."

- Brian Beckman

"The most powerful programming language is Lisp.
 If you don't know Lisp (or its variant, Scheme),
 you don't appreciate what a powerful language is.
 Once you learn Lisp you will see what is missing in most other languages."

 - Richard Stallman

Pierwsze wrażenie

$ clisp -q
[1]> (prin1 "hello world")
"hello world"

Rozwiązanie problemu

(prin1
 (apply '+ (remove-if-not
        #'(lambda (x) (or (= 0 (mod x 3)) (= 0 (mod x 5))))
        (loop for n from 1 below 1000 collect n))))

Go (golang)

Go to język statycznie typowany. Kod źródłowy Go kompilujemy do programów wykonywalnych, choć istnieje możliwość wykonywania ich jako skrypty.
Obecnie jest to język, za którym stoi firma Google. Historia tego języka sięga jednak języka Alef, który powstał w czasach aktywności projektu systemu operacyjnego Plan 9 from Bell Labs. W projekcie tym brali udział autorzy języka C oraz Unix. Sam język uchodzi za "prostsze, nowoczesne C", różnice pomiędzy nimi są jednak znaczne. W Go powstaje wiele programów, narzędzi i rozwiązań w dziedzinie DevOps , ale nie tylko. Istnieje wiele gotowych bibliotek programistycznych dla tego języka, a jego popularność rośnie. Społeczność zgromadzona wokół Go zarówno ceni ten język, jak i zauważa pewne brakujące mechanizmy. W Go nie znajdziemy m.in. znanych nam mechanizmów OOP. Jest to język utrzymany na poziomie właśnie współczesnego "odpowiednika" C, wzbogaconego o garbage collection, itp.

Pierwsze wrażenie

package main

import "fmt"

func main() {
    fmt.Println("Hello world")
}

Program budujemy, a następnie uruchamiamy:

$ go build hello.go
$ ./hello
Hello world

Rozwiązanie problemu

package main

import "fmt"


func main() {
    var n = 0
    var sum int = 0

    for ; n < 1000; n++ {
        if n % 3 == 0 || n % 5 == 0 {
            sum = sum + n
        }
    }

    fmt.Println(sum)
}

JavaScript (ECMASCript)

JavaScript to język, który powstał w Netscape w ekspresowym tempie, a jego autorem jest Brendan Eich - późniejszy założyciel Mozilla.
Początkowym założeniem języka było m.in. umożliwienie dynamicznych interakcji na stronach WWW. Miał to być język funkcyjny, jednak równolegle firma Sun Microsystems promowała swój język Java, co niefortunnie wpłynęło na kształt i samą nazwę "JavaScript". Języki Java i JavaScript nie mają ze sobą niczego wspólnego. JavaScript przez wiele lat był językiem wykorzystywanym głównie w przeglądarkach internetowych, natomiast rozkwit sieci Internet zaowocował nowymi dziedzinami, w których JavaScript ma zastosowanie. Dzisiaj wiele aplikacji webowych i mobilnych jest opartych o JavaScript. Istnieją też programy serwerowe (backendowe) stworzone w JavaScript. Implementacji jest kilka, każda przeglądarka ma swoją, a ja do rozwiązania użyję interpretera node.js.

Pierwsze wrażenie

Wypisywanie na ekran w przypadku JavaScript to najczęściej console.log. Możemy też wykonać to samo w "Developer Tools" danej przeglądarki internetowej.

> console.log("hello world")
hello world
undefined
> 2 + 2
4
> 1 + "11"
'111'
> 1 - "11"
-10
> 1 + "a"
'1a'
> 1 - "a"
NaN

Język powstał "w tydzień", miał być dialektem Scheme, w połowie tygodnia zmieniły się wymagania, tak zostało. Niemniej, dzisiaj istnieje wiele narzędzi i rozszerzeń, w samym języku wiele się zmieniło, a język znalazł bardzo szeroki wachlarz zastosowań. Na co dzień używamy wielu aplikacji stworzonych właśnie w JavaScript.

Rozwiązanie problemu

Rozwiązanie można napisać na wiele sposobów - ja zastosuję tutaj paradygmat jak najbardziej zbliżony do funkcyjnego:

[...Array(1000).keys()].filter(function(idx, el) {
    return el % 3 == 0 || el % 5 == 0 ? el : null;
}).reduce((a, b) => a + b);

Haskell

Haskell to statycznie typowany język funkcyjny popularny w świecie akademickim, choć ma swoją oddaną społeczność poza nim. Powstają w nim narzędzia i większe systemy, sprawdza się w roli języka generycznego, jak i dziedzinowego. Akademicki background tego języka szybko dostrzeżemy we wszelkich tutorialach, dokumentacji, czy rozważaniach na temat samych języków programowania. Programy w Haskell mogą być uruchamiane jako skrypty, ale możemy również kompilować je do binarnych programów wykonywalnych. Wśród implementacji interpreterów/kompilatorów znajdziemy między innych GHC (Glasgow Haskell Compiler), którego użyję poniżej.

Pierwsze wrażenie

Uruchamiam najpierw tryb interaktywny:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
Prelude> print("hello world")
"hello world"
Prelude> 2 + 2
4

Kontynuuję ("sanity check"):

Prelude> 1 + "11"

<interactive>:4:1: error:
      No instance for (Num [Char]) arising from a use of '+'
      In the expression: 1 + "11"
      In an equation for 'it': it = 1 + "11"

Pilnuje typów, nie robi głupich rzeczy, wyjaśnia co jest nie tak i gdzie konkretnie.

Rozwiązanie problemu

import Data.List (foldl')

my_filter n = n `mod` 3 == 0 || n `mod` 5 == 0
solve x = foldl' (+) 0 x

main = print(solve(filter my_filter [1..1000 - 1]))

Wyżej użyłem trybu interaktywnego. Teraz uruchomię kod najpierw jako skrypt, a następnie zbuduję i uruchomię program wykonywalny.

Jako skrypt:

$ runhaskell solution.hs
233168

Buduję i uruchamiam:

$ ghc solution.hs -o solution
$ ./solution
233168

Rust

Rust to stosunkowo nowy język (pierwsze wydanie miał w roku 2010). Powstał w ramach Mozilla Research, a jednym z jego pierwszych zastosowań był silnik przeglądarki internetowej - Servo. Jest to jeden z języków, które mają na celu eliminację błędów w programach przez zapewnienie mechanizmów gwarantujących poprawność zarządzania pamięcią oraz realizacji współbieżności. Język ma coraz więcej zastosowań i zwolenników, z każdym dniem zdobywa popularność. Stworzono w nim już wiele narzędzi, a nawet system operacyjny (Redox). Ekosystem Rust zdaje się czerpać z doświadczeń i rozwiązań sprawdzonych w innych projektach. Język ma szerokie zastosowanie i jest poniekąd kandydatem do "zastąpienia C" oraz C++. Nie wszędzie jednak jeszcze działa, nie obsługuje też takiej liczby platform jak C. Bazuje na LLVM. Cykl wydawniczy ma wysokie tempo, przez co nie wszystkie systemy mogą zaadaptować najnowsze wersje, w których pojawiają się nowości.

Wielu użytkowników Rust przyjęło postawę ewengelizacyjną, której slogan można skrócić do: "rewrite everything in Rust". Mnie pozostaje dodać: "rewrite C in Rust".

Pierwsze wrażenie

fn main()
{
    println!("hello world");
}

Kompilujemy, uruchamiamy:

$ rustc hello.rs
$ ./hello
hello world

Rozwiązanie problemu

fn main()
{
    let mut n: u32 = 0;
    let mut sum: u32 = 0;

    while n < 1000 {
        if n % 3 == 0 || n % 5 == 0 {
            sum = sum + n;
        }
        n += 1;
    }

    println!("{}", sum);
}

Kompilujemy, uruchamiamy:

$ rustc solution.rs
$ ./solution
233168

C

C to jeden z najważniejszych języków w dzisiejszym świecie. Przez niektórych uważany jest za język niskopoziomowy, jednak - w gruncie rzeczy - jest językiem wysokiego poziomu (jak np. Go). W C napisano większość oprogramowania i systemów, których używamy na co dzień. W C stworzono Linux, FreeBSD, PostgreSQL, Python, sterowniki są w C, oprogrowamowanie embedded często jest w C. Świat jest napisany w C i z C pochodzi "hello world".
Nie będę tutaj opisywał czym jest C. Czytelnicy, którzy programują, na pewno się z nim już zetknęli, a stawiający pierwsze kroki w programowaniu na pewno się z nim zetkną.

Pierwsze wrażenie

Tutaj zamieszczam również poprawny, zgodny z oryginałem ciąg znaków, który wypisujemy w programach "hello, world!\n".

#include <stdio.h>

int main()
{
    printf("hello, world!\n");
}

Kompiluję, uruchamiam, patrzymy:

$ cc hello.c -o hello
$ ./hello
hello, world!

Rozwiązanie problemu

#include <stdio.h>


int main()
{
    int sum = 0;
    int n = 1000;

    int i;
    for(i = 0; i < n; i++) {
        if(i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }

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

    return 0;
}

Kompiluję, uruchamiam, patrzymy:

$ cc solution.c -o solution -Wall -Werror
$ ./solution
233168

Shell (POSIX)

Pierwsze wrażenie

$ echo "hello world"
hello world
$ echo $(expr 2 + 2)
4

Sanity check:

$ echo $(expr 1 + "11")
12
$ echo $(expr "11" - 1)
10

No proszę.

Rozwiązanie problemu

n=1000
sum=0

i=0
while test $i -lt $n; do
    if test $(expr $i % 3) -eq 0 || test $(expr $i % 5) -eq 0; then
        sum=$(expr $sum + $i)
    fi
    i=$(expr $i + 1)
done

echo $sum

Shell oczywiście zapewnia jedynie składnię, natomiast posiłkuje się zewnętrznymi programami. expr to /bin/expr, test to /bin/test. Uruchomienie skryptu spowoduje wielokrotne uruchomienie tych programów, a zatem obliczenie szukanej sumy zajmie więcej czasu niż w innych językach programowania. Niemniej - jest to język programowania i możemy w nim przedmiotowy problem rozwiązać:

$ time /bin/sh euler.sh
233168

real    0m2.022s
user    0m1.666s
sys 0m0.453s

SQL (plpgsql)

Ten problem możemy z łatwością rozwiązać również w SQL. Ja zastosuję plpgsql (PostgreSQL).

Pierwsze wrażenie

postgres=> select 'hello world';
  ?column?
-------------
 hello world
(1 row)

postgres=> select 2 + 2;
 ?column?
----------
        4
(1 row)

postgres=> select 1 + '11';
 ?column?
----------
       12
(1 row)

postgres=> select '11' - 1;
 ?column?
----------
       10
(1 row)

Umie typy i operatory, nie robi głupot.

Rozwiązanie problemu

CREATE OR REPLACE FUNCTION euler_1()
RETURNS INTEGER
AS $$
DECLARE
    n INTEGER = 1000;
    i INTEGER = 0;
    total INTEGER = 0;
BEGIN
    WHILE i < n LOOP
          IF i % 3 = 0 OR i % 5 = 0 THEN
                  total := total + i;
          END IF;
          i := i + 1;
    END LOOP;
    RETURN total;
END
$$
LANGUAGE PLPGSQL;


SELECT * FROM euler_1();

Uruchamiamy:

$ psql postgres < test.sql
CREATE FUNCTION
 euler_1
---------
  233168
(1 row)

Inne języki

Celem artykułu (i na tym poziomie) nie jest dogłębne poznawanie i rozważanie języków.
Rozwiązanie tego samego problemu (w tej skali) przy zastosowaniu kilku wybranych języków pozwala spojrzeć jedynie na podstawową ich składnię.
Języków programowania istnieją tysiące. Nie demonstruję tutaj nawet wielu z najpopularniejszych. Wybrałem taki podzbiór, jaki uważałem za stosowny, a kierowałem się raczej odmienną naturą i specyfiką języków, które czymś się wyróżniają.

Oczywiście można wspomnieć, że z tych ważnych i popularnych języków są jeszcze m.in.:

C++ - tam gdzie trzeba wydajności C, ale chcemy pisać obiektowo, wygodniej (i mamy w ogóle możliwości sprzętowe) - tam często będzie C++. Od systemów wbudowanych, przez systemy operacyjne, symulacje, gry komputerowe, computer vision, sieci neuronowe, po... bez ograniczeń. Łącznie z metaprogrammingiem (język szablonów w C++ jest Turing complete).
Ada - język stosowany w systemach wymagających wysokiej spójności i niezawodności, np. awionika, ale nie tylko.
Pascal - oraz inne języki, które opracował Niklaus Wirth, dzięki któremu dzisiejsze języki (jak Java) wykorzystują w celu przenośności własną maszynę wirtualną.
Java, Ruby, PHP, Swift, Objective-C, itd.

Każdy z języków ma jakiegoś poprzednika. Obecne języki korzystają z osiągnięć wielu poprzedzających je rozwiązań (choćby Smalltalk, Algol, Fortran). Każdy z nich miał/ma swoją rolę, każdy z nich jest cegiełką tego samego postępu technologicznego.

Podsumowanie

Project Euler to bardzo ciekawe źródło inpiracji i motywacji. Początkowe problemy są oczywiście trywialne, ale bardzo szybko ich złożoność rośnie. Trafiamy zarówno na problemy natury algorytmicznej, jak i ograniczenia języków czy maszyn. Czasem choćby liczby/wyniki są na tyle duże, że nie mieszczą się w standardowych typach danych liczbowych. Część algorytmów wymaga wypracowania pewnej strategii, gdyż "naiwne", proste rozwiązania - choć poprawne - nie dadzą nam wyników w sensownym (lub skończonym) czasie. Nie wybiegam teraz jednak w przyszłość, a zapraszam do kolejnych artykułów tej serii. Dla mnie Project Euler to okazja do użycia językow, których na co dzień nie stosuję, oraz zmierzenia się z wyzwaniami, o których na co dzień nie myślę. Mam nadzieję, że czytelnicy również odnajdą w tym coś dla siebie.