Изучи программирование за 21 год

Table of Contents

Интро

Этот курс задуман как несколько более фундаментальный, чем обычно предлагаемые курсы, так что у него даже есть неофициальное название "Изучи программирование за 21 год".

Материалы и план курса сформированы но уточняются и дополняются. Ожидается, что курс будет рассматривать все вопросы программирования от архитектуры низкоуровневых средств до абстракций лямбда-исчисления.

Прикосновение к магии

Hello World

Транслятор кода Морзе

Первая осмысленная программа в процедурном стиле.

var array =[
  ['a','._'],
  ['b','1'],
  ['c','2'],
  ['d','3'],
  ['e','4'],
  ['f','5'],
  ['g','6'],
  ['h','7'],
  ['i','8'],
  ['j','9'],
  ['k','a'],
  ['l','b'],
  ['m','__'],
  ['n','_.'],
  ['o','d'],
  ['p','e'],
  ['q','f'],
  ['r','g'],
  ['s','h'],
  ['t','_'],
  ['u','j'],
  ['v','k'],
  ['w','l'],
  ['x','m'],
  ['y','n'],
  ['z','o']
];



function binary_search (data, target, start, end) {
  console.log("target="+target);
  console.log("start="+start);
  console.log("end="+end);

  if (end < data[0]) {
    console.log("return 1");
    return false;
  }

  // Находим среднее значение
  const middle = Math.floor(start + (end - start) / 2);
  console.log(middle);
  console.log(data[middle][0]);
  console.log(target);
  // Если содержимое элемента с индексом, равным среднему значению оказалось равно target

  if (target === data[middle][0]) {
    // возвращаем соответствие
    console.log("return found");
    return data[middle][1];
  }

  // Если осталось два элемента: на который указывает start и на который указывает end
  if (data[end] - 1 === data[start]) {
    if (target === data[end][0]) {
      // возвращаем соответствие
      console.log("return from found on end");
      return data[end][1];
    }
    if (target === data[start][0]) {
      // возвращаем соответствие
      console.log("return from found on start");
      return data[start][1];
    }
    console.log("return 2");
    return false;
  }

  if (target.charCodeAt() > data[middle][0].charCodeAt()) {
    console.log("we need to go deeper! >");
    var pre_result = binary_search(data, target, middle, end);
    console.log("return from found on >");
    return pre_result;
  }

  if (target.charCodeAt() < data[middle][0].charCodeAt()) {
    console.log("we need to go deeper! <");
    var pre_result = binary_search(data, target, start, middle);
    console.log("return from found on <");
    return pre_result;
  }
  console.log("return 3");
  return false;
}

function helper () {
  var getText = document.getElementById('translate');
  console.log("getText="+document.getElementById('translate'));
  var param = getText.value;
  console.log("param="+param);
  document.getElementById('Translate_ready').value = translate(param);

}

function translate (param) {
 return param.split('').map(function(symbol) {
    var result_value = binary_search(array, symbol, 0, array.length-1);
    if (false === result_value) {
      alert("something wrong");
    }
    return result_value;
  });
}

// var return_value = translate('abc');
// console.log("translate result is " + return_value);

HTML и CSS

Декларативные языки разметки

Создание игры на Java

Этот интенсив рассчитан на 3-5 дней. За это время мы создаем простую игру Breakout (Arkanoid) с использованием JavaSE и графической библиотеки libGDX.

Геймплей: Игрок контролирует небольшую платформу-ракетку, которую можно передвигать горизонтально от одной стенки до другой, подставляя её под шарик, предотвращая его падение вниз. Удар шарика по кирпичу приводит к разрушению кирпича.

Низкоуровневое программирование

Стек и вызов процедур

Пролог и эпилог функции

Указатели

Транслятор кода Морзе на Ассемблере

  • Табличный перекодировщик

    Работа с массивом структур, содержащих указатели

    a:
        .ascii "_."
        .byte 0
    b:
        .ascii "_..."
    c:
        .ascii "_._."
        .ascii "AAAA"
    table:
    table_a:
        .ascii "a"
        .int a
    table_b:
        .ascii "b"
        .int b
    table_c:
        .ascii "c"
        .int c
    
  • Списковый перекодировщик

    Работа со списком структур, содержащих указатели

    a:
        .int 0
        .ascii "a"
        .ascii "_."
        .byte 0
    b:
        .int a
        .ascii "b"
        .ascii "_..."
        .byte 0
    c:
        .int b
        .ascii "c"
        .ascii "_._."
        .byte 0
    last:
        int c
    

Эквивалентность программ

  • Построение трасс
  • Эквивалентность по трассам
  • Обратная трассировка
  • Построение остаточной программы из заданной точки графа управления

Взамодействие с операционной системой

Ввод-вывод

Интепретатор команд

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <SDL2/SDL.h>

#define QUEUE_SIZE 400
#define LEFT  1
#define UP    2
#define DOWN  3
#define RIGHT 4
#define MAX_X 24
#define MAX_Y 14
#define TILE_SIZE 32
#define SIZE_OF_COMMAND_NAME 10
#define FOR_ALL_COMMAND for (int i=0; i<(sizeof(cmds)/sizeof(struct command)); i++)

int exit_flag = 0;
int cur_priv_lvl  = 0;

typedef void (*pcmd)();

struct command {
    int  active;
    int  privileged;
    int  num;
    char name[SIZE_OF_COMMAND_NAME];
    void (*pf)();
};

void game();
void hello();
pcmd get_command();
void login();
void badcmd();
void quit();
void badcmd() {    printf("error: bad command or low privilegies\n"); }
void quit()   {    exit_flag = 1; }

struct command cmds[] = {
    {1,0,1,"quit",  &quit  },
    {1,0,2,"login", &login },
    {1,1,5,"game",  &game  }
};

char log_ok[] = "success: you are logged";

void login() {
    char passbuf[50];
    puts("enter password:");
    gets(passbuf);
    if (0 == strcmp(passbuf, log_ok+19)) {
        cur_priv_lvl = 1;
        puts(log_ok);
    } else {
        puts("error: wrong password");
    }
}

void hello() {
    printf("available comands:\n- for logged users: ");
    FOR_ALL_COMMAND
    {
        printf("%s, ", cmds[i].name);
    }
    printf("\n- for unprivileged users: ");
    FOR_ALL_COMMAND
    {
        if (0 == cmds[i].privileged) { printf("%s, ", cmds[i].name); }
    }
    puts("");
}

pcmd get_command() {
    char cmdbuf[50];
    puts("enter your command here:");
    gets(cmdbuf);
    FOR_ALL_COMMAND
    {
        if (cmds[i].privileged <= cur_priv_lvl) {
            if (0 == strcmp(cmdbuf, cmds[i].name)) {
                return cmds[i].pf;
            }
        }
    }
    return &badcmd;
}

int main(int argc, char** argv)
{
    hello();
    while(0 == exit_flag) {
        (get_command())();
    }
}


////////////////////////////////////////////////////////////////////



char dir;
char old_dir;
char eaten;
char mat[MAX_X+1][MAX_Y+1];

int delay = 16;

typedef struct tag_node {
    char x;
    char y;
} node;

node body;
node head;
node tail;
node fruit;

typedef struct tag_queue {
    int first;
    int last;
    int len;
    node elems[QUEUE_SIZE];
} queue;

queue snake;

SDL_Renderer* renderer = NULL;
SDL_Surface*  field_surface = NULL;
SDL_Surface*  fruit_surface = NULL;
SDL_Surface*  shead_surface = NULL;
SDL_Surface*  snake_surface = NULL;
SDL_Texture*  field_texture = NULL;
SDL_Texture*  fruit_texture = NULL;
SDL_Texture*  shead_texture = NULL;
SDL_Texture*  snake_texture = NULL;

void init(void);
void input(void);
int  update(void);
void render(void);
void pop_tail(void);
void push_head(void);
void draw_body(void);
void draw_head(void);
void draw_fruit(void);
void clear_tail(void);
void next_fruit(void);

int run_snake = 0;

void game() {
    int i, j;

    dir = 0;
    for (i = 0; i <= MAX_X; i++) {
        for (j = 0; j <= MAX_Y; j++) {
            mat[head.x][head.y] = 0;
        }
    }
    delay = 16;
    body.x = 0;
    body.y = 0;
    head.x = 0;
    head.y = 0;
    tail.x = 0;
    tail.y = 0;
    for (i = 0; i <= QUEUE_SIZE; i++) {
        snake.elems[i].x = 0;
        snake.elems[i].y = 1;
    }

    SDL_Window *window = NULL;
    if (SDL_Init(SDL_INIT_VIDEO) != 0) {
        fprintf(stderr, "SDL_Init: %s\n", SDL_GetError());
    }
    atexit(SDL_Quit);
    SDL_CreateWindowAndRenderer(800, 480, 0, &window, &renderer);
    SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
    SDL_RenderClear(renderer);
    SDL_RenderPresent(renderer);
    fruit_surface = SDL_LoadBMP("apple.bmp");
    shead_surface = SDL_LoadBMP("head.bmp");
    snake_surface = SDL_LoadBMP("snake.bmp");
    field_surface = SDL_LoadBMP("field.bmp");
    fruit_texture = SDL_CreateTextureFromSurface(renderer, fruit_surface);
    shead_texture = SDL_CreateTextureFromSurface(renderer, shead_surface);
    snake_texture = SDL_CreateTextureFromSurface(renderer, snake_surface);
    field_texture = SDL_CreateTextureFromSurface(renderer, field_surface);
    for (i = 0; i <= MAX_X; i++) {
        for (j = 0; j <= MAX_Y; j++) {
            tail.x = i;
            tail.y = j;
            clear_tail();
        }
    }

    snake.first = 0;
    snake.last = 0;
    snake.len = 0;
    // srand((unsigned) (NULL));
    fruit.x = /*rand() % 16 +*/ 5;
    fruit.y = /*rand() % 6 +*/ 5;
    head = fruit;
    if (head.x < (MAX_X / 2)) {
        dir = RIGHT;
    } else {
        dir = LEFT;
    }
    push_head();
    next_fruit();
    eaten = 1;
    old_dir = 0;
    printf("Level 1\n");

    render();
    run_snake = 1;
    while (run_snake == 1) {
        input();
        if (update()) {
            run_snake = 0;
            goto zzz;
        }
        render();
        SDL_Delay(delay * 10);
    }
zzz:
    SDL_DestroyTexture(field_texture);
    SDL_DestroyTexture(snake_texture);
    SDL_DestroyTexture(shead_texture);
    SDL_DestroyTexture(fruit_texture);
    SDL_FreeSurface(field_surface);
    SDL_FreeSurface(snake_surface);
    SDL_FreeSurface(shead_surface);
    SDL_FreeSurface(fruit_surface);
    SDL_DestroyRenderer(renderer);
    SDL_DestroyWindow(window);
    SDL_Quit();
    printf("Snake Length: %d\n", snake.len);
    printf("Game Over\n");
}


void input(void)
{
    const Uint8 *state = SDL_GetKeyboardState(NULL);
    SDL_PumpEvents();
    if (state[SDL_SCANCODE_UP]) {
        dir = UP;
    } else if (state[SDL_SCANCODE_DOWN]) {
        dir = DOWN;
    } else if (state[SDL_SCANCODE_LEFT]) {
        dir = LEFT;
    } else if (state[SDL_SCANCODE_RIGHT]) {
        dir = RIGHT;
    } else if (state[SDL_SCANCODE_ESCAPE]) {
        exit(0);
    }
    /* Ignore opposite direction */
    if (dir + old_dir != 5 || snake.len == 1) {
        old_dir = dir;
    } else {
        dir = old_dir;
    }
}

int update(void)
{
    body = head;
    switch (dir) {
    case UP:
        head.y = head.y - 1;
        break;
    case DOWN:
        head.y = head.y + 1;
        break;
    case LEFT:
        head.x = head.x - 1;
        break;
    case RIGHT:
        head.x = head.x + 1;
        break;
    }
    if (head.x < 0 || head.x > MAX_X || head.y < 0 || head.y > MAX_Y) {
        return 1;
    }
    if (mat[head.x][head.y]) {
        return 1;
    }
    if (head.x == fruit.x && head.y == fruit.y) {
        next_fruit();
        eaten = 1;
        switch (snake.len) {
        case 10:
            delay -= 4;
            printf("Level 2\n");
            break;
        case 20:
            delay -= 4;
            printf("Level 3\n");
            break;
        case 30:
            delay /= 2;
            printf("Level 4\n");
            break;
        case 40:
            delay /= 2;
            printf("Level 5\n");
            break;
        }
    } else {
        pop_tail();
        eaten = 0;
    }
    push_head();
    return 0;
}

void render(void)
{
    if (snake.len > 1) {
        draw_body();
    }
    if (eaten) {
        draw_fruit();
    } else {
        clear_tail();
    }
    draw_head();
    SDL_RenderPresent(renderer);
}

void pop_tail(void)
{
    tail = snake.elems[snake.first];
    snake.first = (snake.first + 1) % QUEUE_SIZE;
    snake.len--;
    mat[tail.x][tail.y] = 0;
}

void push_head(void)
{
    snake.elems[snake.last] = head;
    snake.last = (snake.last + 1) % QUEUE_SIZE;
    snake.len++;
    mat[head.x][head.y] = 1;
}

void draw_body(void)
{
    SDL_Rect rect;
    rect.h = TILE_SIZE;
    rect.w = TILE_SIZE;
    rect.x = body.x * TILE_SIZE;
    rect.y = body.y * TILE_SIZE;
    SDL_RenderCopy(renderer, snake_texture, NULL, &rect);
}

void draw_head(void)
{
    SDL_Rect rect;
    rect.h = TILE_SIZE;
    rect.w = TILE_SIZE;
    rect.x = head.x * TILE_SIZE;
    rect.y = head.y * TILE_SIZE;
    SDL_RenderCopy(renderer, shead_texture, NULL, &rect);
}

void draw_fruit(void)
{
    SDL_Rect rect;
    rect.h = TILE_SIZE;
    rect.w = TILE_SIZE;
    rect.x = fruit.x * TILE_SIZE;
    rect.y = fruit.y * TILE_SIZE;
    SDL_RenderCopy(renderer, fruit_texture, NULL, &rect);
}

void clear_tail(void)
{
    SDL_Rect rect;
    rect.h = TILE_SIZE;
    rect.w = TILE_SIZE;
    rect.x = tail.x * TILE_SIZE;
    rect.y = tail.y * TILE_SIZE;
    SDL_RenderCopy(renderer, field_texture, NULL, &rect);
    /* SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
       SDL_RenderFillRect(renderer, &rect); */
}

void next_fruit(void)
{
    do {
        fruit.x = (fruit.x * 6 + 1) % (MAX_X + 1);
        fruit.y = (fruit.y * 16 + 1) % (MAX_Y + 1);
    } while (mat[fruit.x][fruit.y]);
}

Обработка прерываний

Оверлеи

Разделяемые библиотеки

Компоновка

Системы сборки

Зависимости

Обратная инженерия

Дизассемблирование

Взлом нашего интепретатора команд

Детектирование отладчика

    .file   "bbbb.c"
    .section    .rodata
frmt_str:
    .string "%x\n"
dbg_str:
    .string "debugger!"

    .text
    .globl  main
    .type   main, @function
main:
    .LFB0:
    .cfi_startproc
    leal    4(%esp), %ecx
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    movl    %esp, %ebp

    pushl   %ecx
    subl    $4, %esp
    call    lab
    subl    $8, %esp

    pushl   %eax
    pushl   $frmt_str
    call    printf
    addl    $16, %esp

    nop

    movl    -4(%ebp), %ecx
    leave
    leal    -4(%ecx), %esp
    ret
    .cfi_endproc
end_main:
    .size   main, .-main
    .globl  lab
    .type   lab, @function
lab:
    .cfi_startproc
    pushl   %ebp
    movl    %esp, %ebp
prepare:
    xor %edx, %edx
    movl    $main, %esi
    movl    $end_main, %edi
    jmp loop_check
loop:
    movzbl  (%esi), %eax
    cmpb    $0xCC, %al
    jne     over_dbg
dbg:
    subl    $12, %esp
    pushl   $dbg_str
    call    puts
    addl    $16, %esp
over_dbg:
    add %eax, %edx
    inc %esi
loop_check:
    cmp     %esi, %edi
    jne loop
leave:
    movl    %edx, %eax
    leave
    ret
    .cfi_endproc
    .LFE1:
    .size   lab, .-lab
    .ident  "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.5) 5.4.0 20160609"
    .section    .note.GNU-stack,"",@progbit

Инструментирование кода

Перехват вызовов

Инструменты анализа систем

ESIL

Построение высокоуровнего языка

Минимальный Forth

Объектная система

Сборка мусора

Выращиваем Lisp

Построение отладчика-эмулятора

Построение трассировщика

Декомпиляция и автоматический анализ

  • Построение остаточной программы из заданной точки

Суперкомпиляция

Типизация

Сильная/слабая

Строгая/нестрогая

Вывод типов

Императивные парадигмы

Процедурная

модульная

объектно-ориентированная

Механизмы абстракции

Кольцевой буфер

Потоки

Очереди сообщений

Машины состояний

Модель взаимодействующих акторов

Сигналы

Функциональное программирование

Код как данные

Рекурсия

Функции высшего порядка

Чистота

Ленивость.

Рантайм

Менеджер памяти и умные указатели

Сборка мусора

Зеленые потоки

Супервайзинг

Логическое программирование

Пролог

Рефал

Forth

Визуальное программирование

Дракон

Написание языков и виртуальных машин

Создание компилятора

Написание среды времени выполнения

Распределенные системы

Топология сетей

Самообучающиеся системы

Линейная регрессия

Кластеризация

Деревья решений

Динамическое программирование

Генетическое программирование

Яндекс.Метрика
Home